vector的模拟实现
类的设计
用三个指针分别指向开始位置，最后一个数据的下一个位置，空间分配的最大位置，通过指针运算来确定数据大小和容量
vector类的设计要用模板来实现，实现元素的可变性，把vector的变量参数设置成_Ty，
指针可以直接进行访问操作，所以vector的迭代器就可以用指针封重命名得到。
template<class _Ty>
class vector {
public:
typedef _Ty* iterator;
iterator begin() {
return _start;
}
iterator end() {
return _finish;
}
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
};
vector的构造和析构
//空构造
vector()
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{}
//构造n个val
vector(int n, const _Ty& value = _Ty())
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
//扩容空间到n
reserve(n);
while (n--) {
//数据遍历尾插
push_back(value);
}
}
//拷贝构造
vector(vector<_Ty>& v)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
reserve(v.capacity());
//数据遍历拷贝
for (int i = 0; i < v.size(); ++i) {
_finish[i] = v[i];
}
//更新size大小
_finish = _start + v.size();
}
//用迭代器区间构造
// 如果使用iterator做迭代器，会导致初始化的迭代器区间[first,last)只能是vector的迭代器
// 重新声明迭代器，迭代器区间[first,last]可以是任意容器的迭代器
template<class InputIterator>
vector(InputIterator first, InputIterator last) {
reserve(last - first);
while (first != last) {
push_back(*first);
++first;
}
}
//赋值运算符重载
vector<_Ty>& operator=(vector<_Ty> t) {
swap(t);
return *this;
}
//析构vector对象
~vector() {
if (_start) {
delete[] _start;
_start = nullptr;
_finish = nullptr;
_end_of_storage = nullptr;
}
}
string容量操作
//容量操作
size_t size() const {
return _finish - _start;
}
size_t capacity() const {
return _end_of_storage - _start;
}
bool empty() const {
return size() == 0;
}
//预留空间
void reserve(size_t n) {
//先把以前的数据大小保存起来
size_t oldSize = size();
if (n > capacity()) {
_Ty* new_start = new _Ty[n];
//遍历拷贝以前的数据
//不能直接用memcpy拷贝数据，memcpy是浅拷贝
if (_start) {
for (int i = 0; i < oldSize; ++i) {
new_start[i] = _start[i];
}
}
//这里要先释放以前申请的空间，防止内存泄漏
delete[] _start;
//更新指针位置
_start = new_start;
_finish = _start + oldSize;
_end_of_storage = _start + n;
}
}
void resize(size_t n, const _Ty& value = _Ty()) {
//要设置容量小于size()
if (n <= size()) {
_finish = _start + n;
return;
}
//要设置容量大于capacity()，扩容
if (n > capacity()) {
reserve(n);
}
size_t offset = n - size();
while (offset--) {
*_finish = value;
++_finish;
}
}
vector访问操作
//重载[]
_Ty& operator[](size_t pos) {
return _start[pos];
}
const _Ty& operator[](size_t pos)const {
return _start[pos];
}
vector增删查改
//尾插
void push_back(const _Ty& val) {
insert(end(), val);
}
//尾删
void pop_back() {
erase((end() - 1));
}
//删除pos位置元素
iterator erase(iterator pos) {
iterator begin = pos;
while (begin != end()) {
*begin = *(begin + 1);
++begin;
}
--_finish;
return pos;
}
//pos位置插入val值
iterator insert(iterator pos, const _Ty& val) {
assert(pos >= _start && pos <= _finish);
if (_finish == _end_of_storage) {
size_t oldPos = pos - _start;
reserve(capacity() == 0 ? 1 : 2 * capacity());
//如果发生增容，pos迭代器失效，需要更新pos
pos = _start + oldPos;
}
iterator end = _finish - 1;
while (end >= pos) {
*(end + 1) = *end;
--end;
}
*pos = val;
++_finish;
return pos;
}
//交换两个vector
void swap(vector<_Ty>& v) {
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
完整代码实现
#include<iostream>
#include<vector>
#include<assert.h>
namespace xiaomage {
template<class _Ty>
class vector {
public:
typedef _Ty* iterator;
typedef const _Ty* const_iterator;
iterator begin() {
return _start;
}
iterator end() {
return _finish;
}
//vector构造
//无参构造
vector()
:_start(nullptr)
,_finish(nullptr)
,_end_of_storage(nullptr)
{}
//构造n个val
vector(int n, const _Ty& value = _Ty())
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
reserve(n);
while (n--) {
push_back(value);
}
}
//拷贝构造
vector(vector<_Ty>& v)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
reserve(v.capacity());
for (int i = 0; i < v.size(); ++i) {
_finish[i] = v[i];
}
_finish = _start + v.size();
}
//用迭代器区间构造
// 如果使用iterator做迭代器，会导致初始化的迭代器区间[first,last)只能是vector的迭代器
// 重新声明迭代器，迭代器区间[first,last]可以是任意容器的迭代器
template<class InputIterator>
vector(InputIterator first, InputIterator last) {
reserve(last - first);
while (first != last) {
push_back(*first);
++first;
}
}
//赋值运算符重载
vector<_Ty>& operator=(vector<_Ty> t) {
swap(t);
return *this;
}
//析构vector对象
~vector() {
if (_start) {
delete[] _start;
_start = nullptr;
_finish = nullptr;
_end_of_storage = nullptr;
}
}
//重载[]
_Ty& operator[](size_t pos) {
return _start[pos];
}
const _Ty& operator[](size_t pos)const {
return _start[pos];
}
//容量操作
size_t size() const{
return _finish - _start;
}
size_t capacity() const {
return _end_of_storage - _start;
}
bool empty() const {
return size() == 0;
}
void reserve(size_t n) {
size_t oldSize = size();
if (n > capacity()) {
_Ty* new_start = new _Ty[n];
if (_start) {
for (int i = 0; i < oldSize; ++i) {
new_start[i] = _start[i];
}
}
delete[] _start;
_start = new_start;
_finish = _start + oldSize;
_end_of_storage = _start + n;
}
}
void resize(size_t n, const _Ty& value = _Ty()) {
//要设置容量小于size()
//要设置容量大于size()小于capacity()
//要设置容量大于capacity()
if (n <= size()) {
_finish = _start + n;
return;
}
if (n > capacity()) {
reserve(n);
}
size_t offset = n - size();
while (offset--) {
*_finish = value;
++_finish;
}
}
//增删改查
void push_back(const _Ty& val) {
insert(end(), val);
}
void pop_back() {
erase((end() - 1));
}
iterator erase(iterator pos) {
iterator begin = pos;
while (begin!=end()) {
*begin = *(begin + 1);
++begin;
}
--_finish;
return pos;
}
iterator insert(iterator pos, const _Ty& val) {
assert(pos >= _start && pos <= _finish);
if (_finish == _end_of_storage) {
size_t oldPos = pos - _start;
reserve(capacity() == 0 ? 1 : 2 * capacity());
//如果发生增容，pos迭代器失效，需要更新pos
pos = _start + oldPos;
}
iterator end = _finish-1;
while (end>=pos) {
*(end + 1) = *end;
--end;
}
*pos = val;
++_finish;
return pos;
}
void swap(vector<_Ty>& v) {
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
};
}