【C++ STL】你真的了解vector吗？浅谈vector的底层机制

底层结构概述

SGI版本的vector，主要是由3个迭代器来维护的，而迭代器是原生指针重定义的。假设vector的第一个模版参数是T。

typedef T* iterator;
iterator _start;
iterator _finish;
iterator _end_of_storage;

其中_start指向了空间的起始位置，_finish指向了最后一个元素的下一个位置，_end_of_storage指向了当前容量的结束位置。那么，size就是_finish-_start，capacity就是_end_of_storage-_start，begin和end分别是_start和_finish！

扩容机制与深浅拷贝问题

如果空间不够了，需要扩容，扩容的步骤是：

1. 申请新的空间。
2. 把旧的空间的数据拷贝到新的空间中去。
3. 释放旧的空间。

而第2步的拷贝，本身代价就不小！因为T可以是自定义类型，那么对于空间内的每一个T，都是深拷贝！比如，对于vector<string>，每一个string内部都有一个_str指针指向堆区上存储的字符串，那么第2步的拷贝就非常麻烦了。如果对于vector内部的每一个string，都采取浅拷贝，只把_str存储的地址拷贝过去，那么就会出现2个_str指向同一块空间的问题！

从而，修改其中一个vector内的string，另一个vector内的string同样会被修改！而且，当其中一个vector析构时，会先析构内部的每一个string，而两个vector内的string的_str指针指向同一块空间，这块空间会被delete两次！所以，对于vector内的每一个string，都必须进行深拷贝，把_str指向的字符串也拷贝一份！

所以，vector扩容的代价是非常高的！这里测试下vector的扩容机制。

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main()
{
   
	vector<string> v;
	size_t capacity = v.capacity();
	cout << "init: capacity = " << capacity << endl;
	for (size_t i = 0; i < 100; i++)
	{
   
		v.push_back("111111");
		if (v.capacity() != capacity)
		{
   
			capacity = v.capacity();
			cout << "new: capacity = " << capacity << endl;
		}
	}

	return 0;
}

VS2022输出结果：

可以观察到，大概每次扩容1.5倍。再来测试下g++下的扩容机制。

每次都是严格的2倍扩容。不管是哪种环境下，都会出现大量的扩容，而扩容的代价是非常大的！所以，如果我们提前知道插入数据的个数，就可以先调用reserve保留足够的空间，从而减少甚至避免扩容！

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main()
{
   
	vector<string> v;
	// 提前保留足够的空间，从而减少甚至避免扩容！
	v.reserve(100);
	size_t capacity = v.capacity();
	cout << "init: capacity = " << capacity << endl;
	for (size_t i = 0; i < 100; i++)
	{
   
		v.push_back("111111");
		if (v.capacity() != capacity)
		{
   
			capacity = v.capacity();
			cout << "new: capacity = " << capacity << endl;
		}
	}

	return 0;
}

VS2022输出结果：

g++输出结果：

那如果我们要拷贝一份vector<string>呢？不仅要对每一个string都做深拷贝，而且vector本身也要深拷贝！所以完整的步骤是：

1. 申请新的空间存储新的vector。
2. 把旧的vector内的数据拷贝到新的vector中，若vector存储的类型是自定义类型（如string），那么每一个string也要深拷贝！

同理，如果要拷贝vector<vector<int>>，那么在拷贝外层vector的同时，内层的vector也要做深拷贝！

插入与删除

vector作为顺序容器，如果在尾部插入或者删除数据（push_back和pop_back），效率是非常高的；但是如果在中间甚至头部插入或者删除数据，效率就很低了！

以头部插入数据为例。假设空间足够，首先要把所有数据向后挪动一格，腾出空间，才能插入数据！而挪动数据的过程，也是拷贝的过程，可能会导致深拷贝！

同理，删除数据时，要把待删除数据后面的数据向前挪动，覆盖掉要删除的元素，挪动数据的过程也是拷贝的过程，可能会导致深拷贝！

所以，应尽可能地避免在vector中间甚至头部插入或者删除数据！

迭代器失效

当一个迭代器不能访问时，我们称这个迭代器失效了。

vector<int> v = {
   1,2,3,4,5};
vector<int>::iterator it = v.begin();
// ...
++it;
*it;

在上面的代码中，中间执行了什么操作，会导致++it和*it等操作变得危险了？答案是：所有的扩容、插入和删除操作！在经过reserve、insert、push_back、erase等操作后，迭代器就失效了！

在insert之后，有可能导致扩容。而根据前面的讲解，扩容时会申请新的空间，拷贝数据，再释放旧的空间。vector的迭代器可以是原生的指针，当旧的空间被释放掉后，这个指针指向一块已经释放掉的空间，成为了野指针！而访问野指针是很危险的！所以此时的迭代器就失效了。

你可能会问了，那为什么删除数据也会导致迭代器失效？删除数据又不会扩容呀。事实上，迭代器失效不一定是野指针导致的，也有可能是因为迭代器指向的位置不是你想要的位置！比如下面的代码，本意是删除所有的偶数：

#include <iostream>
#include <vector>
using namespace std;

int main()
{
   
	vector<int> v = {
    1,2,3,4 };
	vector<int>::iterator 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;
}

在VS2022环境下，运行时进程会崩溃，因为VS2022认为，当erase之后，迭代器it已经失效了，如果继续使用，就会报错。而g++没有对迭代器失效做严格的检查，会输出：

这是为什么呢？

1    2    3    4
^
it

++it
1    2    3    4
     ^
     it

erase(it)
1    3    4
     ^
     it
     
++it
1    3    4
          ^
          it

erase(it)
1    3    
          ^
          it

++it
1    3    
               ^
               it

最后一次删除it之后，it已经指向end的下一个位置了，循环条件永远为假，且此时已经越界了。所以，当最后一个数是偶数时，会有段错误。

那么，如果把vector的元素初始化成{1,2,3,4,5}呢？g++输出结果如下：

怎么运行结果又正常了呢？大家可以自己分析一下。原因是：删除4后，it指向5，it++后指向end，刚好跳出循环了，结果恰好正确。

那么，如果把vector的元素初始化成{1,2,4,3,5}呢？g++输出结果如下：

没有出现段错误，但结果是错的！这是因为vector里有连续的偶数，当删除2之后，it指向4，it++后指向5，相当于跳过了4！

我们发现，当迭代器失效后，执行结果是未定义的！有可能正常运行且结果正确，有可能正常运行但结果错误，有可能程序崩溃……而且，不同编译器的行为也不一样，VS2022非常严格，如果迭代器失效后强行访问，无论如何都会终止进程！g++就相对温和一些，没有做严格的检查。这是由于，VS2022底层的vector迭代器是一个类，在类里面对迭代器是否失效做了检查。而g++底层的vector迭代器是一个原生指针，无法严格检查迭代器是否失效。我们可以用typeid(it).name()来获取迭代器底层的类型。VS2022下输出：

g++输出：

看不出是什么类型，但可以打印出它的大小sizeof(it)，在x86环境下大小是4字节，在x64环境下大小是8字节，可以间接说明它是原生指针。

归根结底，it在erase之后已经失效了，指向的元素已经不是原来的元素了，我们需要对it重新赋值！而erase会返回指向当前删除元素的下一个元素的迭代器，每当删除一个偶数，就让it接收erase的返回值，否则it++，正确的代码如下：

#include <iostream>
#include <vector>
using namespace std;

int main()
{
   
	vector<int> v = {
    1,2,3,4,6 };
	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
   
		if (*it % 2 == 0)
		{
   
			it = v.erase(it);
		}
		else
		{
   
			++it;
		}
	}

	for (auto e : v)
	{
   
		cout << e << " ";
	}
	cout << endl;

	return 0;
}

上面的代码中，vector里存有连续的偶数，且最后一个数是偶数，这是最强的测试用例了，输出结果：

1 3 

所以，解决迭代器失效的方法是，对迭代器重新赋值！

总结

1. vector可以用3个原生指针来维护。
2. vector扩容和深拷贝代价都很大，灵活使用reserve，尽可能减少甚至避免扩容和深拷贝。
3. 尽可能少地在vector的中间甚至头部插入或者删除数据。
4. 当一个vector扩容、插入或者删除数据后，原先的迭代器失效，需要重新赋值。