C++ ——— 模拟实现 vector 类
目录
vector 类的框架
无参数的构造函数
析构函数
获取有效数据个数
获取容量
重载 [] 运算符
可读可写版本
只可读版本
扩容
尾插
实现迭代器
可读可写版本
只可读版本
自定义设置size长度和内容
在任意位置插入
删除任意位置的数据
赋值重载
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;
}