C++——vector的模拟实现
文章目录
vector接口总览
namespace nzb
{
//模拟实现vector
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
//默认成员函数
vector(); //构造函数
vector(size_t n, const T& val); //构造函数
template<class InputIterator>
vector(InputIterator first, InputIterator last); //构造函数
vector(const vector<T>& v); //拷贝构造函数
vector<T>& operator=(const vector<T>& v); //赋值重载
~vector(); //析构函数
//迭代器相关函数
iterator begin();
iterator end();
const_iterator begin()const;
const_iterator end()const;
//容量相关函数
size_t size()const;
size_t capacity()const;
void reserve(size_t n);
void resize(size_t n, const T& val = T());
bool empty()const;
//修改容器相关函数
void push_back(const T& x);
void pop_back();
void insert(iterator pos, const T& x);
iterator erase(iterator pos);
void swap(vector<T>& v);
//访问容器相关函数
T& operator[](size_t i);
const T& operator[](size_t i)const;
private:
iterator _start; //指向容器的头
iterator _finish; //指向有效数据的尾
iterator _endofstorage; //指向容器的尾
};
}
默认成员函数
构造函数
- 无参构造，将所有成员变量初始化为空指针即可
vector()
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{}
- 构造一个含有n个值为val的vector容器。
先将容器容量扩大到n，再尾插val
vector(size_t n, const T& val)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(n); //扩容
for (size_t i = 0; i < n; i++) //尾插
{
push_back(val);
}
}
- 利用迭代器区间进行构造
因为迭代器区间可以是其他迭代器区间，所以我们要重新定义一块模板，再将迭代器中的数据尾插
template <class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
while (first != last)
{
push_back(*first);
first++;
}
}
拷贝构造
传统写法
先将容器容量扩大到n，再尾插原vector类中的数据（这里扩容和尾插调整了容器尾指针和数据尾指针，我们不必再次调整）
vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(v.capacity());
for (const auto& e : v)
{
push_back(e);
}
}
现代写法
利用迭代器构造一份vector类，再交换该类和拷贝构造的类
vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
vector<T> tmp(v.begin(), v.end());
swap(tmp);
}
赋值重载
传统写法
先初始化原来vector类的空间，再将数据拷贝过来
vector<T>& operator=(const vector<T>& v)
{
if (this != &v)
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;
reserve(v.capacity());
for (const auto& e : v)
{
push_back(e);
}
}
return *this;
}
现代写法
现代写法极为巧妙，利用传值的特性（出了函数立即销毁）传入vector类，再交换该类和拷贝构造的类达到赋值的效果
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
析构函数
释放开辟存储数据的空间，再将容器的各个成员变量置为空
~vector()
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;
}
迭代器相关函数
vector当中的迭代器实际上就是容器当中所存储数据类型的指针。
typedef T* iterator;
typedef const T* const_iterator;
begin和end
vector当中的begin函数返回容器的首地址，end函数返回容器当中有效数据的下一个数据的地址。
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
我们还需写一份const版本，const版本只能读不能写，防止vector中数据被修改
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
容量相关函数
size和capacity
size表示vector容器中已存储有效数据个数而capacity表示vector容器的最大容量，那如何得出该组数据呢？
我们知道vector成员函数_start,_finish,_endofstorage是指针，而指针减指针得到两个指针间的数据个数，我们可以用_finish-_start得到size,用_endofstorage-_start得到capacity
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _endofstorage - _start;
}
reserve
- 当n大于当前的capacity时，将capacity扩大到n或大于n。
- 当n小于当前capacity时什么也不做。
void reserve(size_t n)
{
if (n > capacity())
{
size_t sz = size(); // 记录原容器中数据个数
T* tmp = new T[n]; // 开辟一块容量为n的空间
if (_start) //判空
{
for (size_t i = 0; i < sz; i++) // 拷贝数据
{
tmp[i] = _start[i];
}
delete[] _start; // 释放原容器中的数据
}
_start = tmp; // 调整指针
_finish = _start + sz;
_endofstorage = _start + n;
}
}
注意：这里拷贝数据不能用memcpy。当我们拷贝的是一些简单的常量时是没有问题的，但是当我们拷贝的是另一个类，如string类时，拷贝的string还是指向原来string类指向的空间。当原来string被释放时，原string类指向的空间也被释放，此时拷贝的string类指向的是一块已被释放的空间，程序结束时它将再次被释放，释放一块已被释放的空间程序报错。
resize
- 当n大于当前的size时，将size扩大到n，扩大的数据为val，若val未给出，则默认为容器所存储类型的默认构造函数所构造出来的值。
- 当n小于当前的size时，将size缩小到n。
void resize(size_t n, const T& val = T())
{
if (n <= size())// 当n小于当前的size时
{
_finish = n + _start;// 将size缩小到n
}
else // 当n大于当前的size时
{
if (n > capacity())// 当n大于容量时，扩容
{
reserve(n);
}
while (_finish < _start + n)// 给size到容器结尾赋值
{
*_finish = val;
_finish++;
}
}
}
这里用了匿名对象T（）来作为缺省参数
empty
通过比较_start和_finish指针来判断容器是否为空
bool empty()const
{
return _start == _finish;
}
修改容器相关函数
push_back
先判断容器是否已满，如果满了先扩容再尾插，如果没满，直接尾插
void push_back(const T& x)
{
if (_finish == _endofstorage)// 判断是否需要扩容
{
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
// 尾插数据
*_finish = x;
_finish++;
}
pop_back
先判空处理，再–_finish
void pop_back()
{
assert(!empty());// 判空
--_finish;
}
insert
功能：利用迭代器再指定位置插入数据。
实现方式：插入前判断是否需要扩容，再将指定位置后的数据往后挪动一位，把数据插入指定位置。
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start&&pos <= _finish);// 判断传入数据的合法性
if (_finish == _endofstorage)// 扩容
{
size_t len = pos - _start;// 记录pos的位置
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos)// 挪动数据
{
*(end + 1) = *end;
--end;
}
*pos = x;// 插入数据
_finish++;
return pos;
}
注意:扩容时要记录pos和_start的相对位置，避免扩容后迭代器失效问题
erase
功能：删除指定位置数据。
实现方式：先判断传入数据的合法性，在将pos位置后的数据全部往前挪动一位，覆盖掉原pos位置的数据
iterator erase(iterator pos)
{
assert(pos >= _start&&pos < _finish);// 判断传入数据的合法性
iterator it = pos + 1;// 利用迭代器记录pos的后一位
while (it != _finish)// 将pos后的数据往前挪动一位
{
*(it - 1) = *it;
it++;
}
_finish--;
return pos;
}
swap
功能：交换两个vector中的数据
实现方式：利用库函数中的swap进行交换
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}
访问容器相关函数
operator[ ]
为了方便访问数据vector中也加入了“下标+[ ]”操作
T& operator[](size_t i)// 可读可写
{
assert(i < size());
return _start[i];
}
const T& operator[](size_t i) const// 只能读
{
assert(i<size());
return _start[i];
}