C++ ——— 模拟实现 vector 类

vector%20%E7%B1%BB%E7%9A%84%E6%A1%86%E6%9E%B6-toc" name="tableOfContents" style="margin-left:0px">vector 类的框架

无参数的构造函数

析构函数

获取有效数据个数

获取容量

重载 [] 运算符

可读可写版本

只可读版本

扩容

尾插

实现迭代器

可读可写版本

只可读版本

自定义设置size长度和内容

在任意位置插入

删除任意位置的数据

赋值重载

vector%20%E7%B1%BB%E7%9A%84%E6%A1%86%E6%9E%B6">vector 类的框架

namespace rjj
{template<class T>class vector{public:    typedef T* iterator;private:iterator _start;iterator _finish;iterator _endofstorage;};
}

首先把要模拟实现的 vector 类用命名空间区分开来，以免和编译器自带的 vector 类冲突

vector 类要支持不同类型的实例化，所以使用模板来定义，这样在实例化的时候就能实例化不同的类型：vector<int>、vector<char>、vector<string> 等

_start 是指向空间起始位置的指针

_finish 是指向有效数据后一个位置的指针

_endofstorage 是指向开辟的动态空间末尾的指针

无参数的构造函数

vector():_stat(nullptr),_finish(nullptr),_endofstorage(nullptr)
{}

析构函数

~vector()
{delete[] _start;_start = _finish = _endofstorage = nullptr;
}

获取有效数据个数

size_t size() const
{return _finish - _start;
}

获取容量

size_t capacity() const
{return _endofstorage - _start;
}

重载 [] 运算符

可读可写版本

T& operator[](size_t pos)
{assert(pos < size());return _start[pos];
}

只可读版本

const T& operator[](size_t pos) const
{assert(pos < size());return _start[pos];
}

扩容

void reserve(size_t n)
{// 要保证扩容的大小大于当前容量if (n > capacity()){size_t sz = size();// 开辟新空间T* tmp = new T[n];// 拷贝并且释放旧空间if (_start){// 这样会出现浅拷贝问题// memcpy(tmp, _start, sizeof(T) * size());// 深拷贝for (int i = 0; i < sz; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;_endofstorage = _start + n;}
}

尾插

void Push_back(const T& x)
{// 先判断是否需要扩容if (_finish == _endofstorage){reserve(capacity() == 0 ? 4 : capacity() * 2);}// 尾插数据*_finish = x;_finish++;
}

测试代码：

实现迭代器

可读可写版本

iterator begin()
{return _start;
}iterator end()
{return _finish;
}

直接使用原生指针即可实现

代码演示：

只可读版本

typedef const T* const_iterator;
const_iterator begin() const
{return _start;
}
const_iterator end() const
{return _finish;
}

自定义设置size长度和内容

void resize(size_t n, const T& val = T())
{if (n <= size()){_finish = _start + n;}else{// 先判断是否需要扩容reserve(n);while (_finish < _start + n){*_finish = val;_finish++;}}
}

当要设置的长度小于或等于 size() 时，也就是小于有效数据长度时，直接减小 _finish 的指向即可

当要设置的长度大于 size() 时，先判断是否需要扩容，在从 _finish 的位置依次往后赋值

测试代码：

小于时：

大于时：

在任意位置插入

void insert(iterator pos, const T& x)
{assert(pos >= _start);assert(pos <= _finish);// 先判断是否需要扩容if (_finish == _endofstorage){// 防止异地扩容后 pos 变成野指针，先记录长度size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);// 再重新赋值pos = _start + len;}// 指向最后一个数据的下一个位置iterator end = _finish;// 向后挪动while (end > pos){*end = *(end - 1);end--;}// 插入数据*pos = x;_finish++;
}

插入数据就会存在会扩容情况，如果扩容的话，pos 还是指向原来的空间，只要发生了扩容就会导致 pos 变成野指针，所以要使用 pos - _start 计算出长度先存储，不论是否扩容，再重新赋值 pos

测试代码：

删除任意位置的数据

iterator erase(iterator pos)
{assert(pos >= _start);assert(pos < _finish);// 指向 pos 位置的后一个位置iterator next = pos + 1;// 向前覆盖while(next < _finish){*(next - 1) = *next;next++;}_finish--;return pos;
}

测试代码：

赋值重载

void swap(vector<T>& v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);
}
vector<T>& operator=(vector<T> tmp)
{swap(tmp);return *this;
}