STL解析——vector的使用及模拟实现

目录

1.使用篇

1.1默认成员函数

1.2其他常用接口

2.模拟实现

2.1源码逻辑参考

2.2基本函数实现

2.3增

2.4删

2.5迭代器失效

2.6拷贝构造级其他接口

2.7赋值运算符重载(现代写法)

2.8深层次拷贝优化

3.整体代码

---

在C++中vector算正式STL容器，功能可以类比于数据结构中的顺序表，用法可以看作简化版的string。

1.使用篇

vector中的接口相比string会少很多，设计逻辑会更为合理，下面对常用接口进行讲解。

1.1默认成员函数

vector中显示的默认成员函数包括构造，析构和赋值运算符重载。

构造函数

(1)将vector对象初始化成一个空对象。

(2)将对象初始化为n个val值。

(3)将对象初始化为某一迭代器区间内的值.

(4)将对象x拷贝给对象。

代码示例如下：

#include<iostream>
#include<vector>using namespace std;void test01()
{vector<int> v1;vector<int> v2(10, 1);vector<int> v3(v2.begin(), v2.end());
}int main()
{test01();return 0;
}

通过调试观察如下：

析构

销毁每个容器元素，并释放所有申请的空间

 赋值运算符重载

将另一同模板对象赋值给目前对象 

1.2其他常用接口

在讲其他接口前，需要注意的是vector并没有重载流插入运算符，因此想给vector进行流插入时需要遍历vector元素，给每个可进行流插入的元素进行输入，这时便常用resize进行大小初始化，防止越界访问报错。

 功能是将对象的大小初始化为n，并值为val。代码示例如下：

#include<iostream>
#include<vector>using namespace std;void test02()
{vector<int> v1;v1.resize(10);
}int main()
{test02();return 0;
}

调试结果如下:

这样resize后便能进行流插入： 

下面介绍与resize看着类似的reserve,reserve功能是提前预留看见，适用于知道大体空间大小的情况下插入数据 

但预留空间里面还是个空容器， 只能进行插入操作。下面便介绍插入接口

在数据结构中顺序表最典型的插入操作便是尾插，vector中则是push_back()

即在尾部新增一个元素val，若空间不足会自动进行空间的扩容。

后面一些接口会在模拟实现中逐步讲解。

2.模拟实现

对于vector的模拟实现主要是对vector增，删，查，改功能的实现，vector作为正式STL容易，这里模拟实现参考stl3.0版本源码实现逻辑，进而深入理解vector容器。

2.1源码逻辑参考

在STL3.0源代码中可以看到，与C顺序表不同的是vector容器实现逻辑是通过三个迭代器，而这个版本的迭代器代表是指针，因此下面的模拟实现也会通过给出三个迭代器指针来实现。

2.2基本函数实现

这里的基本函数实现主要包括：vector的创建，实现增删查改功能之前的基本函数(构造，析构，扩容等)

对于vector的创建：首先为了对容器储存类型的不确定性进行处理，这里要使用C++的模板功能。成员变量主要是开始位置迭代器(_start)，最后一个元素位置迭代器(_finish)，空间最后一个位置迭代器(_end_of_storage)。其次为了不与库中的vector命名冲突，模拟实现的vector放在命名空间my_vector下。代码如下：

namespace my_vector
{template<class T>class vector{public://定义迭代器typedef T* iteractor;//功能private://成员变量iteractor _start;iteractor _finish;iteractor _end_of_storage;};
}

完成定义后，再进行类中最基本的拷贝构造进行完成：最简单的实现方式就是将3个迭代器都置为nullptr。代码如下：

namespace my_vector
{template<class T>class vector{public://定义迭代器typedef T* iteractor;vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}//功能private://成员变量iteractor _start;iteractor _finish;iteractor _end_of_storage;};

其次要注意这里的类定义声明和定义不能分离在不同文件，主要原因是对于使用了模板的类或函数不能在不同文件进行声明和定义。

下面实现几个基本函数来帮助完成尾插操作：为了完成插入操作，我们需要优先考虑vector的空间问题，因此要有扩容(reserve)，其次在扩容中要访问原来的元素个数来方便拷贝(size)，顺便进行空间大小的访问(capacity)，然后才能进行尾插。

因此优先完成size：对于元素个数，只需要返回末迭代器减开始位置迭代器的值即可(指针-指针表示范围内的元素个数)

对于reserve，参数需要一个表示扩容空间大小的n。其次在实现时只有条件n > capacity时才进行扩容。随后进行扩容时，需开辟一个n大小的空间，且若原来不为空时，要将原空间元素拷贝到新空间，并对原空间进行释放。再将3个迭代器都进行更新：

size_t size()const
{return _finish - _start;
}size_t capacity()const
{return _end_of_storage - _start;
}void reserve(size_t n)
{if(n > capacity()){size_t old_size = size();iterator tmp = new T[n];if(_start){memcopy(tmp, _start, old_size*sizeof(T));delete[] _start;}_start = tmp;_finish = _start + old_size;_end_of_storage = _start + n;
}

要注意这里_finish在更新时，因为涉及扩容拷贝，_start的指针位置是改变了的，若次数+的是size那么则无法更新成功，简而言之就是在start更新后，finish更新前这段代码区内size()其实是失效的这里解决方案一般是在函数开始时用old_size记录原size大小，在后面需要调用size的地方使用old_size。

在尾插前要实现的函数基本就这些，在尾插后为方便观察要实现下变量相关的迭代器和[ ]运算符重载，因逻辑比较简单，这里直接展示代码：

typedef T* iterator;
typedef const T* const_iterator;
iterator begin()
{return _start;
}iterator end()
{return _finish;
}const_iterator begin()const
{return _start;
}const_iterator end()const
{return _finish;
}T& operator[](size_t i)
{assert(i < size());return _start[i];
}const T& operator[](size_t i) const
{assert(i < size());return _start[i];
}

2.3增

尾插：尾插实现逻辑与数据结构顺序表类似，判断是否扩容 -->在尾数据处插入数据x并使末指针++。然后这里为了和STL中一致，返回值设置为原对象的引用。代码如下：

void push_back(const T& x)
{//扩容if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;
}

插入：插入这个地方模仿的是库中的insert接口，即在任意位置插入数据，这里先来看看库中给出接口

这里主要实现第一个类型接口：参数给出需要插入数据的位置和数据。插入步骤主要分为判断是否越界和是否需要扩容，挪动数据以及插入数据。具体代码如下：

iterator insert(const_iterator pos, const T& x)
{//判断assert(pos <= _finish);assert(pos >= _start);size_t len = pos - _start;if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : 2 * capacity());//更新pospos = _start + len;}//挪动数据iterator end = ++_finish;while (end != pos){*end = *(end - 1);--end;}
}

至于这里的迭代器返回值主要涉及迭代器失效问题，与下面删除的erase功能一起分析。

2.4删

库中给出的删除接口主要有尾删(pop_back)和任意位置删除(erase)。

尾删：尾删操作步骤主要可分为判断是否越界，删除数据两个步骤。代码如下：

	void pop_back(){//判断是否为空assert(_start != _finish);//删除数据--_finish;}

删除：删除操作(erase)步骤主要可分判断是否越界以及挪动数据。代码如下

iterator erase(iterator pos)
{assert(pos <= _finish);assert(pos >= _start);iterator it = pos + 1;while (it != _finish){*(it - 1) = *(it);++it;}--_finish;return pos;
}

这里依旧返回原位置迭代器，下面解释返回迭代器的原因。

2.5迭代器失效

先来看看下面的场景(在指定元素前插入数据)：

vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
print(v);auto it = find(v.begin(), v.end(), 3);
if(it != v.end())
{v.insert(it, 0);*it = 9;
}
print(v);

问：在insert后是it迭代器能赋值成功吗？

可以看到这里给it改值为9失败了。具体原因是在这里插入时进行了扩容，虽然函数内对pos进行了更新，但因为传值调用所有it是未更新的，因此导致迭代器失效。

下面再来看另一个失效场景(删除偶数) 

std::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
print(v);auto it = v.begin();
while (it != v.end())
{if (*it % 2 == 0){v.erase(it);}else{++it;}
}
print(v);

可以看到这里代码直接崩溃了，这里的原因是VS2022 Debug环境下对迭代器失效进行了仔细检查。

这里的解决方法就要提到之前的iterator返回值了，下面来看看删除偶数场景下的解决方案：

可以看到这里用it接受返回值后就可以成功运行了。

2.6拷贝构造级其他接口

拷贝构造这里主要可分为预留空间以及尾插操作。其他接口的话主要是实习clear以及resize接口：

vector(const vector<T>& v):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr)
{reserve(v.capacity());for (auto e : v){push_back(e);}
}void resize(size_t n, T val = T())
{if (n > capacity()){reserve(n);for (size_t i = size(); i <= n; i++){push_back(val);}_finish = _start + n;}else{_finish = _start + n;}
}void clear()
{_finish = _start;
}

2.7赋值运算符重载(现代写法)

赋值运算符重载的现代写法主要是通过先通过tmp拷贝，在swap交换来实现，因此需要先实习vector中的swap：

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

2.8深层次拷贝优化

深层级拷贝优化主要涉及vector容器内元素再开空间的问题，因为上面的reserve只进行了简单的memcpy，随后delete[]过程中会将元素申请的空间释放，解决方案就是利用赋值运算符重载中的深拷贝来进一步解决：

void reserve(size_t n)
{if (n > capacity()){size_t old_size = size();iterator tmp = new T[n];if (_start){for (size_t i = 0; i < old_size; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + old_size;_end_of_storage = _start + n;}
}

3.整体代码

#include<assert.h>
#include<iostream>
#include<initializer_list>using namespace std;namespace my_vector
{template<class T>class vector{public://功能//定义迭代器typedef T* iterator;typedef const T* const_iterator;iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin()const{return _start;}const_iterator end()const{return _finish;}//vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}vector(initializer_list<T> il):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){reserve(il.size());for (auto& e : il){push_back(e);}}template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}//vector(int n, int val = 0)//{//	resize(n, val);//}vector(size_t n, T val = T()){resize(n, val);}vector(int n, T val = T()){resize(n, val);}//vector() = default;vector(const vector<T>& v):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){reserve(v.capacity());for (auto e : v){push_back(e);}}~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}void swap(vector<int>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}vector<T>& operator=(const vector<T>& v){vector<T> tmp = v;swap(tmp);return *this;}void reserve(size_t n){if (n > capacity()){size_t old_size = size();iterator tmp = new T[n];if (_start){for (size_t i = 0; i < old_size; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + old_size;_end_of_storage = _start + n;}}void resize(size_t n, T val = T()){if (n > capacity()){reserve(n);for (size_t i = size(); i <= n; i++){push_back(val);}_finish = _start + n;}else{_finish = _start + n;}}void push_back(const T& x){//扩容if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;}iterator insert(const_iterator pos, const T& x){//判断assert(pos <= _finish);assert(pos >= _start);size_t len = pos - _start;if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : 2 * capacity());//更新pospos = _start + len;}//挪动数据iterator end = ++_finish;while (end != pos){*end = *(end - 1);--end;}*end = x;return end;}void pop_back(){//判断是否为空assert(_start != _finish);//删除数据--_finish;}iterator erase(iterator pos){assert(pos <= _finish);assert(pos >= _start);iterator it = pos + 1;while (it != _finish){*(it - 1) = *(it);++it;}--_finish;return pos;}void clear(){_finish = _start;}bool empty(){return _start == _finish;}T& operator[](size_t i){assert(i < size());return _start[i];}const T& operator[](size_t i) const{assert(i < size());return _start[i];}size_t size()const{return _finish - _start;}size_t capacity()const{return _end_of_storage - _start;}private://成员变量iterator _start;iterator _finish;iterator _end_of_storage;};
}