C++ ---- vector的底层原理剖析及其实现

一、定义

vector 是 C++ 标准模板库（Standard Template Library, STL）中的一个非常有用的容器。它是一个序列容器，可以存储具有相同数据类型的元素集合，这些元素在内存中连续存储。与数组相似，但 vector 提供了更多的灵活性和功能。

主要特点：

1.动态数组：vector 可以动态地增加或减少其大小，这意味着你可以根据需要存储更多的元素，而不需要担心数组越界的问题。
2.随机访问：vector 支持随机访问，即你可以使用下标（索引）直接访问容器中的任何元素，其时间复杂度为 O(1)。
3.内存连续：vector 中的元素在内存中是连续存储的，这使得在需要时（如使用迭代器）可以高效地遍历整个容器。
4.容量和大小：vector 有两个重要的属性：size() 和 capacity()。size() 返回容器中当前元素的数量，而 capacity() 返回容器在不重新分配内存的情况下可以存储的元素的最大数量。当 vector 的大小超过其容量时，它会分配更多的内存空间并可能移动所有元素到新的内存位置。

常用操作：

1.插入元素：可以使用 push_back() 在 vector 的末尾添加新元素，或者使用 insert() 在指定位置插入元素。
2.删除元素：可以使用 pop_back() 删除 vector 的最后一个元素，或者使用 erase() 删除指定位置的元素或元素范围。
3.访问元素：可以直接使用下标操作符 [] 访问元素。
4.遍历元素：可以使用迭代器或者范围基 for 循环遍历 vector 中的所有元素。
获取大小和容量：如前所述，可以使用 size() 和 capacity() 方法分别获取 vector 的大小和容量。

二、常用接口及模拟实现

成员变量：

/这里加缺省值的原因：当对象是通过拷贝构造形成的时，这三个指针
/就不会初始化了（默认是随机值，而不是nullptr(0)），而在拷贝构造函数里，会运用到size(),capacity()之类的需要
/这三个指针相减，而随机值相减可能是很大的数字
/而加了缺省值，进入拷贝构造函数后会先进入这里初始化这三个值iterator _start=nullptr;   /指向第一个元素
iterator _finish=nullptr;   /指向最后一个元素的下一个位置
iterator _end_of_storage=nullptr;  /指向最大容量的位置

（1）构造函数

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

模拟实现：

vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr) {
}vector(size_t n, const T& val) {_start = new T[n](val);_finish = _start + n;_end_of_storage = _finish;
}vector(const vector<T>& v) {/写法1:/_start = new T[v.capacity()];memcpy(_start, v._start, sizeof(T) * v.size());_finish = _start + v.size();_end_of_storage = _start + v.capacity();//写法2：reserve(v.capacity()); /避免push_back多次扩容for (auto& num : v) {push_back(num);}
}

 template<class Inputiterator> //说明：成员函数里面可以有模板函数vector(Inputiterator begin, Inputiterator end) {  //用迭代器区间进行构造和初始化//这里重新定义一个Inputiterator而不用vector里面的iterator，是//因为如果用了iterator,那么调用该函数构造的对象所传的实参只能是vector的迭代器//而不能是诸如list ,map等容器的迭代器，而如果想用list或者其他容器的值来//初始化vector对象的话，只能如此定义一个迭代器模板 。//该构造函数支持任意容器的迭代器来初始化，但前提是这些容器所存的数据与//该vector所存的数据类型一致，如：list<int>l 用该方法来初始化 vector<int> v//它们存的都是int类型的数据while (begin != end) {push_back(*begin);begin++;}}

（2）vector的迭代器
vector的迭代器有两种：

1. iterator：typedef T* iterator
2. const_iterator：typedef const T* const_iterator
   (T是vector存的数据类型)

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对
指针进行了封装（list容器的迭代器），比如：vector的迭代器就是原生态指针T* 。

（3）begin()/end()，rbegin()/rend()接口函数

接口	说明
begin()、end()	获取第一个数据位置的iterator/const_iterator， 获取最后一个数据的下一个位置的iterator/const_iterator
rbegin()、rend()	获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的reverse_iterator

模拟实现：

 iterator begin() const{return _start;}iterator end()const {return _finish;}

（4）空间增长函数

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

1. capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2
   倍增长的。因此vector的增容都具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。
2. reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代
   价缺陷问题。
3. resize在开空间的同时还会进行初始化，影响size。

模拟实现：

size_t size()const {return _finish - _start; //两指针相减，结果为两指针之间的数据个数
}
size_t capacity() const{return _end_of_storage - _start;
}
void resize(size_t n, T val = T()) {if (n < size()) {//保留n个数据    _finish = _start + n;}else {reserve(n);while (_finish < _start + n) {  //扩容并追加n-size()个val值(*_finish) = val;_finish++;}}
}

 void reserve(size_t n) {if (n > capacity()) {size_t presize = size(); //要提前记录_start 与_finish 的相对位置//因为下面的_start先更新了，会导致size()函数//出错 (除非_finish先更新：_finish=tmp+size(),_start=tmpT* tmp = new T[n];//不严谨的拷贝数据：//memcpy(tmp, _start, sizeof(T) * presize); //拷贝数据//严谨的拷贝数据：for (size_t i = 0; i < presize; i++) {tmp[i] = _start[i];}//这是因为假如类型T是string或者是vector<int>，而memcpy又是单纯的将内存的空间逐个字节拷贝//就导致vector存的string对象的char*指针（或者vector<int>的int*）// 也是单纯的直接拷贝给tmp,//即tmp里的string对象里的指针指向的空间和待释放的vector对象存的//string对象里的指针指向的空间是一样的。//下面delete[] _start 时，会先调用每个string对象的析构函数。//其实就是，vector深拷贝了，但是vector存的string没有深拷贝//而如果将该this对象的内容逐个拷贝给tmp，每次拷贝时都会调用string的深拷贝//从而避免了该情况。// tmp[i]=_start[i]本质上是：string s =string s'（string的拷贝构造) delete[] _start;//更新三个迭代器所指向的位置：_start = tmp;_finish = tmp + presize;_end_of_storage = tmp + n;}}

测试vector在不同平台下的扩容机制：

// 测试vector的默认扩容机制
void TestVectorExpand()
{size_t sz;vector<int> v;sz = v.capacity();cout << "making  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  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: 141/g++运行结果：linux下使用的STL基本是按照2倍方式扩容
making  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';}}
}

（5）vector的增删查改

vector增删查改	接口说明
push_back()（重点）	尾插
pop_back() （重点）	尾删
find()	查找。（注意这个是算法模块实现，不是vector的成员接口）
insert()	在position之前插入val
erase()	删除position位置的数据
swap()	交换两个vector的数据空间
operator （重点）	像数组一样访问

模拟实现：

void push_back(const T& x) { //T可能是自定义类型，所以用const引用较好if (_finish == _end_of_storage) {//扩容reserve(capacity() == 0 ? 4 : 2 * capacity());}*_finish = x; //如果T是string ,这里会调用string的拷贝构造_finish++;
}void pop_back() {		assert(_start != _finish);--_finish;} iterator find(iterator begin, iterator end, const T& x) {vector<T>::iterator it = begin;while (it != end) {if (*it == x) {return it;}it++;}return end;}void insert(iterator pos, const T& x) {if (_finish == _end_of_storage) {//扩容size_t pre_distance = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());pos = _start + pre_distance;  //因为_start在扩容时指向的空间变化了，//因此pos也要相应的变化}                                 //否则会出现迭代器失效的情况iterator end = _finish-1;while (end >=pos) {*(end + 1) = *end;end--;}*pos = x;++_finish;
}void erase(iterator pos) {assert(pos >= _start);assert(pos < _finish);iterator it = pos;while (it < _finish-1) {*(it) = *(it + 1);it++;}_finish--;}void swap(vector<T>& v) {std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}T& operator[](int i) {assert(i < size() && i >= 0);return _start[i];}

三、vector迭代器失效问题

迭代器失效实际就是迭代器
底层对应指针所指向的空间被销毁了，而仍然使用这一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)。

对于vector可能会导致其迭代器失效的操作有：

1. 会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back等。即如果已经有了一个迭代器指向一块空间，但是这个空间被上述可以改变空间结构的函数给销毁了，那么这个迭代器也就失效了。
2. 指定位置元素的删除操作–erase

using namespace std;
#include <vector>
int main()
{int a[] = { 1, 2, 3, 4 };vector<int> v(a, a + sizeof(a) / sizeof(int));//发生隐式类型转化，调用迭代器区间构造函数// 使用find查找3所在位置的iteratorvector<int>::iterator pos = find(v.begin(), v.end(), 3);// 删除pos位置的数据，导致pos迭代器失效。v.erase(pos);cout << *pos << endl; // 此处会导致非法访问return 0;
}

说明：
erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理
论上讲迭代器不应该会失效。但是，如果pos刚好是最后一个元素，删完之后pos刚好是end
的位置，而end位置是没有元素的，那么pos就失效了。因此删除vector中任意位置上元素
时，vs就认为该位置迭代器失效了。

3.注意：Linux下，g++编译器对迭代器失效的检测并不是非常严格，处理也没有vs下极端。

/ 1. 扩容之后，迭代器已经失效了，程序虽然可以运行，但是运行结果已经不对了
int main()
{
vector<int> v{1,2,3,4,5};
for(size_t i = 0; i < v.size(); ++i)
cout << v[i] << " ";
cout << endl;
auto it = v.begin();
cout << "扩容之前，vector的容量为: " << v.capacity() << endl;
// 通过reserve将底层空间设置为100，目的是为了让vector的迭代器失效
v.reserve(100);
cout << "扩容之后，vector的容量为: " << v.capacity() << endl;
// 经过上述reserve之后，it迭代器肯定会失效，在vs下程序就直接崩溃了，但是linux
下不会
// 虽然可能运行，但是输出的结果是不对的
while(it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
return 0;
}
程序输出：
1 2 3 4 5
扩容之前，vector的容量为: 5
扩容之后，vector的容量为: 100
0 2 3 4 5 409 1 2 3 4 5/ 2. erase删除任意位置代码后，linux下迭代器并没有失效
// 因为空间还是原来的空间，后序元素往前搬移了，it的位置还是有效的
#include <vector>
#include <algorithm>
int main()
{
vector<int> v{1,2,3,4,5};
vector<int>::iterator it = find(v.begin(), v.end(), 3);
v.erase(it);
cout << *it << endl;
while(it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
return 0;
}
程序可以正常运行，并打印：
4
4 5/ 3: erase删除的迭代器如果是最后一个元素，删除之后it已经超过end
/ 此时迭代器是无效的，++it导致程序崩溃
int main()
{
vector<int> v{1,2,3,4,5};
// vector<int> v{1,2,3,4,5,6};
auto it = v.begin();
while(it != v.end())
{
if(*it % 2 == 0)
v.erase(it);
++it;
}
for(auto e : v)
cout << e << " ";
cout << endl;
return 0;
}

总结：
从上述三个例子中可以看到：SGI STL中，迭代器失效后，代码并不一定会崩溃，但是运行
结果肯定不对，如果it不在begin和end范围内，肯定会崩溃的。

四、使用memcpy拷贝会出现的问题

注：reserve接口：

 void reserve(size_t n) {if (n > capacity()) {size_t presize = size(); //要提前记录_start 与_finish 的相对位置//因为下面的_start先更新了，会导致size()函数//出错 (除非_finish先更新：_finish=tmp+size(),_start=tmpT* tmp = new T[n];memcpy(tmp, _start, sizeof(T) * presize); //拷贝数据delete[] _start;//更新三个迭代器所指向的位置：_start = tmp;_finish = tmp + presize;_end_of_storage = tmp + n;}}

#include<string>
int main()
{
Myvector::vector<string> v;  //vector是自己实现的，string是库实现的v.push_back("wwww");
v.push_back("eeee");
v.push_back("rrrr");
return 0;
}

上述代码所导致的问题剖析：


正确拷贝数据的方法：（逐个数据拷贝）

 void reserve(size_t n) {if (n > capacity()) {size_t presize = size(); //要提前记录_start 与_finish 的相对位置//因为下面的_start先更新了，会导致size()函数//出错 (除非_finish先更新：_finish=tmp+size(),_start=tmpT* tmp = new T[n];for (size_t i = 0; i < presize; i++) {tmp[i] = _start[i];}//这是因为假如类型T是string或者是vector<int>，而memcpy又是单纯的将内存的空间逐个字节拷贝//就导致vector存的string对象的char*指针（或者vector<int>的int*）// 也是单纯的直接拷贝给tmp,//即tmp里的string对象里的指针指向的空间和待释放的vector对象存的//string对象里的指针指向的空间是一样的。//下面delete[] _start 时，会先调用每个string对象的析构函数。//其实就是，vector深拷贝了，但是vector存的string没有深拷贝//而如果将该this对象的内容逐个拷贝给tmp，每次拷贝时都会调用string的深拷贝//从而避免了该情况。// tmp[i]=_start[i]本质上是：string s =string s'（string的拷贝构造) delete[] _start;//更新三个迭代器所指向的位置：_start = tmp;_finish = tmp + presize;_end_of_storage = tmp + n;}}

总结：不仅vector存stirng类型会出现该问题，只要是存的对象里有指向堆空间的类型（如还有下面的二维数组），都是有memcpy拷贝问题的，而存储自定义类型就不会。

五、二维数组vector<vector< T >> vv

对c语言来说，创建一个二维数组的方法：

test()
{//三行四列int **two=(int**)malloc(sizeof(int*)*3);for(int i=0;i<3;i++){two[i]=(int*)malloc(sizeof(int)*4);}
}

vector<vecot< T >> vv 的底层空间示意图：