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;
}