【C/C++】STL——深度剖析vector容器

​👻内容专栏： C/C++编程
🐨本文概括：vector的介绍与使用、深度剖析及模拟实现。
🐼本文作者： 阿四啊
🐸发布时间：2023.10.8

一、vector的介绍与使用

1. vector的介绍

像string的学习一样，我们依旧得学会在cplusplus网站中学会查看文档。

关于vector的文档介绍

1. vector是表示可变大小数组的序列容器。
2. 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素
   进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自
   动处理。
3. 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小
   为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是
   一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大
   小。
4. vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存
   储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是
   对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
5. 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增
   长。
6. 与其它动态序列容器相比（deque, list and forward_list）， vector在访问元素的时候更加高效，在末
   尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起list和forward_list
   统一的迭代器和引用更好。
   使用STL的三个境界：能用，明理，能扩展 ，那么下面学习vector，我们也是按照这个方法去学习

2. vector的使用

vector在实际中非常的重要，在实际中我们熟悉常见的接口就可以。我们一一介绍学习常见的vector接口。

2.1 vector的定义

constructor构造函数声明	接口说明
vector()（重点）	无参构造
vector（size_type n, const value_type& val = value_type()）	构造并初始化n个val
vector (const vector& x);（重点）	拷贝构造
vector (InputIterator first, InputIterator last)	使用迭代器进行初始化构造

//vector的构造
void test_vector1()
{vector<int> v1; // 无参初始化vector<int> v2(10, 1); //带参初始化//利用迭代区间进行初始化vector<int> v3(v1.begin(), v1.end());vector<int> v4(v2); //拷贝构造//也利用string的迭代区间也可以进行初始化string s1("hello world");vector<int> v5(s1.begin(), s1.end());vector<int>::iterator it = v5.begin();while (it != v5.end()){//打印字符所对应的ascii码值cout << *it << " ";it++;}
}

2.2 vector 迭代器的使用

iterator的使用	接口说明
begin/cbegin + end/cend	获取第一个数据位置的iterator/const_iterator， 获取最后一个数据的下一个位置的iterator/const_iterator
rbegin + rend	获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的reverse_iterator

void PrintVector(const vector<int>& v)
{// const对象使用const迭代器进行遍历打印vector<int>::const_iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;
}void test_vector2()
{vector<int> vec(10,0);vector<int>::iterator it = vec.begin();while (it != vec.end()){cout << *it << " ";it++;}cout << endl;//使用迭代器进行修改it = vec.begin();int i = 1;while (it != vec.end()){*it += i;it++;i++;}//反向迭代器auto rit = vec.rbegin();while (rit != vec.rend()){cout << *rit << " ";rit++;}cout << endl;//迭代器遍历打印vecPrintVector(vec);
}

2.3 空间增长问题

容量空间	接口说明
size	获取数据个数
capacity	获取容量大小
empty	判断是否为空
resize	改变vector的size
reserve	改变vector的capacity

• capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。
• reserve只负责开辟空间，如果预知需要用多少空间，reserve可以缓解vector频繁增容的代价缺陷问题。resize在开空间的同时还会进行初始化，影响size。

// 测试vector的默认扩容机制
void TestVectorExpand()
{size_t sz;vector<int> v;sz = v.capacity();cout << "making v grow:\n";for (int i = 0; i < 100; ++i){v.push_back(i);if (sz != v.capacity()){sz = v.capacity();cout << "capacity changed: " << sz << '\n';}}
}
vs：运行结果：vs下使用的STL基本是按照1.5倍方式扩容
making foo grow:
capacity changed: 1
capacity changed: 2
capacity changed: 3
capacity changed: 4
capacity changed: 6
capacity changed: 9
capacity changed: 13
capacity changed: 19
capacity changed: 28
capacity changed: 42
capacity changed: 63
capacity changed: 94
capacity changed: 141g++运行结果：linux下使用的STL基本是按照2倍方式扩容
making foo grow:
capacity changed: 1
capacity changed: 2
capacity changed: 4
capacity changed: 8
capacity changed: 16
capacity changed: 32
capacity changed: 64
capacity changed: 128

// 如果已经确定vector中要存储元素大概个数，可以提前将空间设置足够
// 就可以避免边插入边扩容导致效率低下的问题了
void TestVectorExpandOP()
{vector<int> v;size_t sz = v.capacity();v.reserve(100); // 提前将容量设置好，可以避免一遍插入一遍扩容cout << "making bar grow:\n";for (int i = 0; i < 100; ++i){v.push_back(i);if (sz != v.capacity()){sz = v.capacity();cout << "capacity changed: " << sz << '\n';}}
}

2.4 vector的增删查改

vector的增删查改	接口说明
push_back	尾插
pop_back	尾删
insert	在position位置之前插入val值
erase	删除position位置的元素
swap	交换两个vector的数据空间
operator[ ]	像数组一样访问
clear	删除容器的所有元素，将size置为0，但并不改变capacity的大小

// 尾插和尾删：push_back/pop_back
void test_vector3()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);auto it = v.begin();while (it != v.end()) {cout << *it << " ";++it;}cout << endl;v.pop_back();v.pop_back();it = v.begin();while (it != v.end()) {cout << *it << " ";++it;}cout << endl;
}// 任意位置插入：insert和erase，以及查找find
// 注意find不是vector自身提供的方法，是STL提供的算法
void test_vector4()
{// 使用列表方式初始化，C++11新语法vector<int> v{ 1, 2, 3, 4 };// 在指定位置前插入值为val的元素，比如：3之前插入30,如果没有则不插入// 1. 先使用find查找3所在位置// 注意：vector没有提供find方法，如果要查找只能使用STL提供的全局findauto pos = find(v.begin(), v.end(), 3);if (pos != v.end()){// 2. 在pos位置之前插入30v.insert(pos, 30);}vector<int>::iterator it = v.begin();while (it != v.end()) {cout << *it << " ";++it;}cout << endl;pos = find(v.begin(), v.end(), 3);// 删除pos位置的数据v.erase(pos);it = v.begin();while (it != v.end()) {cout << *it << " ";++it;}cout << endl;v.clear();//调用clear后，vector的size将变成0，但是它的容量capacity并未发生改变
}

二、vector的底层实现

1.说明和准备工作

创建一个vector的源文件，写一个vector的类模板，放入一个自己的MyVector的命名空间里面，以免与库里面的vector发生冲突。
在模拟vector时，我们并没有和string一样使用动态分配的指针_Ptr、_size、_capacity，在类中我们使用了三个iterator，贴近stl库里面的实现方式，其实本质就是原生指针。

_start: _start指向动态数组或容器的第一个元素的位置。它用于表示容器的起始位置。

_finish: _finish 也是一个指针，指向容器中当前元素的下一个位置。它表示容器中元素的结束位置。通常，_finish 处于有效元素的末尾，但它之后的内存可能已经分配，但未被使用。

_end_of_storage: _end_of_storage 指向容器内存分配的末尾位置。这个位置之后的内存是容器为将来添加更多元素而预留的。当容器的大小接近容量时，它可能需要重新分配内存，并将新的_end_of_storage更新为新的内存末尾。

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

2.push_back操作

首选我们提前需要写好构造函数与析构函数，构造函数在初始化列表将三个iterator置为nullptr即可，析构函数进行释放资源与指针置空操作。
size()接口函数：表示vector的有效数据个数，即：_finish - _start
capacity()接口函数：表示vector的容量大小，即：_end_of_storage - _start

在push_back尾插之前，我们还需要进行判断是否要进行扩容，扩容机制我们在数据结构学习了很多，不作细致讲解，下面直接放代码：

namespace MyVector
{template<class T>class vector{public:typedef T* iterator;vector(): _start(nullptr), _finish(nullptr), _end_of_storage(nullptr){}size_t capacity(){return _end_of_storage - _start;}size_t size(){return _finish - _start;}void push_back(const T& val){//扩容if (_finish == _end_of_storage){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;T* tmp = new T[newcapacity];if (_start){memcpy(tmp, _start, sizeof(T)* size());delete[] _start;}_start = tmp;_finish = _start + size();_end_of_storage = _start + newcapacity;}*_finish = val;_finish++;}//通过[]进行访问vectorT& operator[] (size_t n){assert(n < size());return *(_start + n);}~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}private:iterator _start;iterator _finish;iterator _end_of_storage;};void test_vector1(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);for (size_t i = 0; i < v1.size(); i++){cout << v1[i] << " ";}cout << endl;}
};

在main函数中我们调用MyVector::test_vector1()，将程序运行起来之后程序就出问题了：

报错说_finish是nullptr，什么原因呢？

我们将程序调试起来，观察发现vector发生了扩容，其_start与_end_of_storage均发生了改变，我们讲他俩相减等于16字节，1个int占4个字节，说明确实刚开始扩容了4个元素，但是我们细心观察发现_finish的值还是为空指针，原因其实就在于_finish = _start + size()，这里更新了_start，而size()里面的_finish还是指向原来的空间，也就是0x00000000，属于迭代器失效问题，解决办法就是在扩容之前，提前用sz变量记录好偏移量。

解决方案：

void push_back(const T& val)
{if (_finish == _end_of_storage){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;size_t sz = size();T* tmp = new T[newcapacity];if (_start){memcpy(tmp, _start, sizeof(T)* sz);delete[] _start;}_start = tmp;_finish = _start + sz;_end_of_storage = _start + newcapacity;}*_finish = val;_finish++;
}

3.vector的访问与遍历

第一种：[]下标访问遍历
第二种：将迭代器_start与_finish用begin与end方法进行封装为成员函数，利用iterator进行遍历。
第三种：一旦有了迭代器，就可以支持范围for语句，因为其底层就是迭代器。

namespace MyVector
{template<class T>class vector{public:typedef T* iterator;vector(): _start(nullptr), _finish(nullptr), _end_of_storage(nullptr){}iterator begin(){return _start;}iterator end(){return _finish;}size_t capacity(){return _end_of_storage - _start;}size_t size(){return _finish - _start;}void push_back(const T& val){if (_finish == _end_of_storage){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;size_t sz = size();T* tmp = new T[newcapacity];if (_start){memcpy(tmp, _start, sizeof(T)* sz);delete[] _start;}_start = tmp;_finish = _start + sz;_end_of_storage = _start + newcapacity;}*_finish = val;_finish++;}T& operator[] (size_t n){assert(n < size());return *(_start + n);}~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}private:iterator _start;iterator _finish;iterator _end_of_storage;};void test_vector1(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);for (size_t i = 0; i < v1.size(); i++){cout << v1[i] << " ";}cout << endl;vector<int> v2;v2.push_back(10);v2.push_back(20);v2.push_back(30);v2.push_back(40);v2.push_back(50);vector<int>::iterator it = v2.begin();while (it != v2.end()){cout << *it << " ";it++;}cout << endl;for(auto e:v2){cout << e << " ";}cout << endl;}
};

4.resize与reserve

resize接口函数：改变vector的size，可以增加或减少容器中的元素数量。
当使用 resize 减少size大小时，多余的元素会被移除，当使用 resize 增加size大小时，会发生扩容。
reserve接口函数：改变vector的容量大小，它能够预留足够的空间，使用 reserve 可以减少因为频繁扩容而带来的性能开销。
ps：reserve本身有检查扩容机制的意思，我们直接使用push_back写的扩容机制代码，然后用push_back复用reserve.

void reserve(size_t n)
{if (n > capacity()){T* tmp = new T[n];size_t sz = size();if (_start){memcpy(tmp, _start, sizeof(T) * sz);delete[] _start;}_start = tmp;_finish = _start + sz;_end_of_storage = _start + n;}
}//为什么这里的val要给匿名对象初始化，而不是0，
//因为这里写的是vector类模板，
//传进来的参数类型可能是int，double,也可能是vector<string>,vector<int>……
//C++泛型编程对内置类型也支持构造函数（匿名对象)，不然C++模板很难用
//添加const说明匿名对象具有常属性，添加&可以延长匿名对象的生命周期
void resize(size_t n, const T& val = T())
{//分为三种情况//小于等于size =>缩容(多余元素被移除)// 大于size 小于capacity//大小capacity =>扩容if (n <= size()){_finish = _start + n;}else{reserve(n);while (_finish < _start + n){*_finish = val;_finish++;}}
}
void push_back(const T& val)
{if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = val;_finish++;
}

测试：

void test_vector2()
{vector<int*> v1;v1.resize(5);vector<string> v2;v2.resize(10,"xxx");for (auto e: v1){cout << e << " ";}cout << endl;for (auto e : v2){cout << e << " ";}cout << endl;
}

5.insert和erase

5.1 insert插入操作

void insert(iterator pos,const T& val)
{assert(pos >= _start);assert(pos <= _finish);//判断是否需要扩容if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}//挪动数据iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}*pos = val;_finish++;
}

测试：

void test_vector3()
{vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);for (size_t i = 0; i < v1.size(); i++){cout << v1[i] << " ";}cout << endl;//第一次在下标为2的位置插入一个元素30v1.insert(v1.begin() + 2, 30);for (size_t i = 0; i < v1.size(); i++){cout << v1[i] << " ";}cout << endl;//第二次头插一个元素8，此时会发生扩容，导致pos失效v1.insert(v1.begin(), 8);for (size_t i = 0; i < v1.size(); i++){cout << v1[i] << " ";}cout << endl;
}

第一次我们在下标为2的位置插入一个元素30，程序能够正确运行，结果也是对的。
但是我们再次利用insert头插一个元素，此时正好是添加新的元素，需要进行扩容，最后程序发生了崩溃。
为何呢？是因为扩容的原因导致的吗？接下来，我们探究一下
在扩容之前，我们调试观察看到pos接收的地址的确和_start的地址一模一样，都是0x0122da28

一旦经过reseve扩容，我们发生三个iterator地址都发生了变化，唯独pos却纹丝不动，还是原来的地址空间，此时的问题貌似很眼熟，没错，就是在前面部分我们提到的_finish如出一辙，也属于迭代器失效问题，本质就是因为pos使用的是释放之前的空间，空间发生了扩容，pos在对以前已经释放的空间进行操作时，就会引起代码运行崩溃。

解决方案：在扩容之前，保存pos位置的偏移量，在扩容后更新pos位置。

void insert(iterator pos,const T& val)
{assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}*pos = val;_finish++;
}

5.2 erase删除操作

void erase(iterator pos)
{assert(pos >= _start);assert(pos < _finish);iterator begin = pos + 1;while (begin < _finish){*(begin - 1) = *begin;begin++;}_finish--;
}

测试：

void test_vector4()
{vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);v1.push_back(6);v1.push_back(7);for (size_t i = 0; i < v1.size(); i++){cout << v1[i] << " ";}cout << endl;auto it = v1.begin();v1.erase(it);for (auto e:v1){cout << e << " ";}cout << endl;v1.erase(it + 2);for (auto e : v1){cout << e << " ";}cout << endl;}

以上我们对头部和下标为2的元素进行了删除操作，代码的结果也能顺畅地跑出来，结果也是正确的，但是这里的it迭代器不会失效吗？答案并非如此，我们来看下面的场景：

我们给出三组样例数据，分别计算给出的样例中用erase删除偶数元素。

第一组测试数据：1 2 3 4 5 6 7

//第一种情况
void test_vector5()
{vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);v1.push_back(6);v1.push_back(7);cout << "begin:";for (auto e : v1){cout << e << " ";}cout << endl;auto it = v1.begin();while (it != v1.end()){if (*it % 2 == 0){v1.erase(it);}it++;}cout << "after:";for (auto e : v1){cout << e << " ";}cout << endl;	 
}

运行结果：结果正确

begin:1 2 3 4 5 6 7
after:1 3 5 7

第二种测试数据：1 2 3 4 5 6 7 8

//第二种情况
void test_vector6()
{vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);v1.push_back(6);v1.push_back(7);v1.push_back(8);cout << "begin:";for (auto e : v1){cout << e << " ";}cout << endl;auto it = v1.begin();while (it != v1.end()){if (*it % 2 == 0){v1.erase(it);}it++;}cout << "after:";for (auto e : v1){cout << e << " ";}cout << endl;
}

运行结果：程序崩溃

begin:1 2 3 4 5 6 7 8
error运行崩溃(触发断言)

第三种测试数据：2 2 3 4 5 6 7

//第三种情况
void test_vector7()
{vector<int> v1;v1.push_back(2);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);v1.push_back(6);v1.push_back(7);cout << "begin:";for (auto e : v1){cout << e << " ";}cout << endl;auto it = v1.begin();while (it != v1.end()){if (*it % 2 == 0){v1.erase(it);}it++;}cout << "after:";for (auto e : v1){cout << e << " ";}cout << endl;
}

打印结果：结果错误

begin:2 2 3 4 5 6 7
after:2 3 5 7

分析：
注⚠️：
以上也是Linux下g++的编译器对迭代器的检测并不严格，处理没有vs编译器果断极端。
以上代码在vs下程序会出现崩溃，vs一些编译器会进行强制检查，认为erase之后it就失效了，访问就会报错。但是在Linux下，虽然可能可以运行，但是输出的结果是不对的。

那么对于以上it等迭代器失效问题，该如何解决呢？
其实erase有具体的返回值，返回的是一个iterator，指向被删除元素的下一个元素的位置。

👇修正erase的代码：

iterator erase(iterator pos)
{assert(pos >= _start);assert(pos < _finish);iterator begin = pos + 1;while (begin < _finish){*(begin - 1) = *begin;begin++;}_finish--;return pos;
}	//迭代器失效的解决方案
//在使用前，对迭代器进行重新赋值
void test_vector8()
{vector<int> v1;v1.push_back(2);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);v1.push_back(6);v1.push_back(7);cout << "begin:";for (auto e : v1){cout << e << " ";}cout << endl;auto it = v1.begin();while (it != v1.end()){if (*it % 2 == 0){//在下次操作it之前，对迭代器进行重新赋值it = v1.erase(it);		}else{//不删除++即可it++;}}cout << "after:";for (auto e : v1){cout << e << " ";}cout << endl;
}

结论：在使用了 insert 和 erase 之后，迭代器失效了，不能再访问，需要谨慎处理。

6.关于具体迭代器失效问题的分析

关于剖析迭代器失效问题 博客==>关于迭代器失效问题

7.memcpy浅拷贝问题

使用memcpy拷贝的是内置类型，那么通常是高效又安全的，但是如果对于自定义类型，涉及动态资源管理，会导致浅拷贝问题，造成内存泄露等不可预知的结果！

//测试对于自定义类型，扩容时使用memcpy会导致浅拷贝问题
void test_vector9()
{vector<string> v1;v1.push_back("11111111111");v1.push_back("11111111111");v1.push_back("11111111111");v1.push_back("11111111111");v1.push_back("11111111111");for (auto e : v1){cout << e << " ";}cout << endl;}

解决方案：
很简单，使用一个for循环，对每个字节进行赋值操作，对于内置类型是赋值，对于自定义类型就会调用自身的赋值重载函数！

void reserve(size_t n)
{if (n > capacity()){T* tmp = new T[n];size_t sz = size();if (_start){//memcpy(tmp, _start, sizeof(T) * sz);for (size_t i = 0; i < sz; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;_end_of_storage = _start + n;}
}

8.vector的拷贝构造与赋值重载

//拷贝构造
//v2(v1)
vector(const vector<T>& x): _start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{//开辟和x一样大的空间reserve(x.capacity());for (size_t i = 0; i < x.size(); i++){push_back(x[i]);}
}void swap(vector<T>& v)
{std::swap(_start, v._start);std::swap(_finish, v.finish);std::swap(_end_of_storage, v._end_of_storage);
}//赋值重载
//v2 = v1
vector<T>& operator=(vector<T> tmp)
{swap(tmp);return *this;
}

测试赋值重载：

//测试赋值重载void test_vector10(){vector<int> v1;v1.push_back(10);v1.push_back(20);v1.push_back(30);v1.push_back(40);vector<int> v2;v2 = v1;for (auto e : v2){cout << e << " ";}cout << endl;}

9.迭代区间初始化与n个val初始化

类模板里面可以嵌套函数模板，可以传入任意类型的迭代区间初始化，在形参部分用InputIterator进行接收，具体细节可下面的测试用例。
对于n个val初始化，不能直接写成vector(size_t n, const T& val = T())，在编译器认为会优先去调用最匹配的，就会调用迭代区间的初始化，此时编译就会出错，那么我们就需要写一个更匹配的vector(int n, const T& val = T())，此时就能正确编译并执行了。

//利用迭代器区间进行初始化
//函数模板
template <class InputIterator>
vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{while (first != last){push_back(*first);first++;}
}vector(size_t n, const T& val = T())
{reserve(n);for (size_t i = 0; i < n; i++){push_back(val); }
}vector(int n, const T& val = T())
{reserve(n);for (int i = 0; i < n; i++){push_back(val);}
}

测试迭代器区间初始化与n个val初始化：

//测试迭代器区间初始化与n个val初始化
void test_vector11()
{//n个val初始化vector<int> v1(10, 0);//利用迭代器区间初始化string str("hello world");vector<int> v2(str.begin(), str.end());for (auto e : v2){cout << e << " ";}cout << endl;
}

10.vector模拟实现源代码

vector的深度剖析及模拟实现