vector的介绍及使用

【写在前面】

相比于 string，vector 的使用更加容易上手的，且它的接口比 string 要少上许多，再加上我们已经学过类似的 string，并且在数据结构篇的顺序表就已经触及过了。vector 在实际中也非常的重要，在实际中我们熟悉常见的接口就可以了。
在 vector 开始我们就可以尝试着去瞅一瞅 STL 的源码了，string 为什么没看的原因，在之前也说过，对于 string 是在 STL 这个规范前被设计出来的。我们的瞅的源码主要参考 P.J 版本和 SGI 版本。

怎么看 ❓

1. P.J

   对如下代码打断点后调试，单步执行就可以查阅了
   
   Visual Studio 2017 参考如下目录：
   
   但是对于 P.J 版本的有些地方还涉及了 C++11 的优化，可能会看不懂，所以我们主要参考 SGI 版本。

2. SGI

   这里有一本书《STL源码剖析》，它用的是 STL3.0 的版本，有需要的同学可私信电子版本。当然这本上核心的内容我们都会学习。
   

stl3.0 一览 ❓

1. 解包后，找到 vector 并打开
   

2. 找到 stl_vector.h 并打开(核心代码也就 500 多行)

   

3. 怎么阅读

   众所周知，看别人的代码是一件很痛苦的事情，如果他的水平高于你，那么你是能成长的，但是看的过程中不要一行一行的去看，这样会导致你只见树木不见森林。这里记住 “二八原则”，一个 1000 行的代码，只有 200 行是最核心的，只要把这 200 行看懂了，那么就都懂了。

4. 核心代码简单筛选如下

   需要查阅的文件：vector ➡ stl_vector.h ➡ stl_construct.h

💨vector

#include <stl_algobase.h>
#include <stl_alloc.h>
#include <stl_construct.h>
#include <stl_uninitialized.h>
#include <stl_vector.h>
#include <stl_bvector.h>

💨stl_vector.h

//这里的模板给的是缺省参数,也就意味着不传也行。Alloc是空间配置器,是一个内存池去申请和释放空间,我们直接用new也行,只不过内存池的效率要高一点
template <class T, class Alloc = alloc>
class vector {
public:
	typedef T value_type;
	typedef value_type* iterator;
protected:
	//这里为啥没有看到指针、size、capacity之类的东西? ———— 我们可以先看下iterator是啥(在public里已经指明了)
	//所以这里就给了三个T*的指针
	iterator start;
 	iterator finish;
 	iterator end_of_storage;
public:
	//其次还可以去看下它的构造函数,它完成了对3个成员变量的初始化工作
	vector() : start(0), finish(0), end_of_storage(0) {}
	//其次再看下push_back的实现
	//现阶段我们看源码还是有些难度的,等到后期我们会深挖
 	void push_back(const T& x) {
 	//说明没满
    if (finish != end_of_storage) {
    //这里不是直接赋值,而是调用construct,原因这里要对一块已有的空间显示调用构造函数初始化,我们在stl_vector.h里并没有找到有关实现
    //其实这里就要结合vector来看了,上面我们不是有一堆头文件嘛,那么它的实现肯定就在stl_vector.h上面的头文件中————stl_construct.h
      construct(finish, x);//怎么实现的?
      ++finish;
    }
    //满了,增容
    else
      insert_aux(end(), x);//怎么实现的?
  }
}

💨stl_construct.h

//construct是一个函数模板2
template <class T1, class T2>
inline void construct(T1* p, const T2& value) {
  new (p) T1(value);//定位new表达式
}

📝补充

对于顺序表而言，虽然它改名为 vector 了，但它的实现跟以前的了解的还是大同小异的。

一、vector的介绍及使用

💦 vector的介绍

vector的文档介绍

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

💦 vector的使用

1、vector的定义

📝说明

• default(1)
  这里给的是一个缺省值，现在这个阶段我们只要看到 alloc 就可以直接忽略它，它是 STL 六大组件中的空间配置器。

• fill(2)
  value_type 是第一个模板参数，它是一个 \0
  

• range(3)
  这里的迭代器还是一个函数模板，也就是说这里的迭代器不一定是 vector 的迭代器

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

void test_vector1()
{
	vector<int> v;   
	//在C实现数据结构中我们的代码风格是驼峰法，而STL整体的风格是小写和下划线分隔的风格
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);

	//遍历vector
	//1、operator[]
	for(size_t i = 0; i < v.size(); ++i)
	{
		v[i] -= 1;
		cout << v[i] << " ";	
	}
	cout << endl;
	//2、迭代器
	vector<int>::iterator it = v.begin();
	while(it != v.end())
	{
		*it += 1;
		cout << *it << " ";	
		++it;
	}
	cout << endl;
	//3、范围for
	for(auto& e : v)
	{
		++e;
		cout << e << " ";	
	}
	cout << endl;
	
	//为什么有了vector,还要有string呢
	//vector里给char，虽然它们底层都是数组中存储char,但是还是不一样的
	//相比T是char的vector,s对象中指向的空间结尾有\0,这样符合很多规范,比如需要去玩strstr、strcpy等,而vector不能玩+=字符串等
	//所以说T是char的vector不能去替代string 
	string s("111111");
	vector<char> vc(6, '1');

	//可以使用一段迭代器区间去构造,也可以控制这一段区间,且这里属于深拷贝(所有自己有独立空间的都要深拷贝)
	vector<int> v1(v.begin(), v.end());
	vector<int> v2(++v.begin(), --v.end());
	//可以使用其它容器的迭代器去构造,只要数据类型可以匹配上(*iterator对象的类型跟vector中存的数据类型是一致的)
	string s1("hello world");
	vector<char> v3(s1.begin(), s1.end());
	//vector<char*> v3(s1.begin(), s1.end());//err,无法从char转换到char*
	//怎么实现的
	/*template<class InputIterator>
	vector(InputIterator first, InputIterator last)
	{
		 while(first != last)
		 {
		 	push_back(*first);
		 	++first;	
		 }	
	}*/

	//拷贝构造
	vector<int> v4(v);
}
int main()
{
	test_vector1();
	return 0;
}

📝补充

1. List item
   
   这里我们发现一个问题，我们在用容器时，都不关心析构，因为出了作用域它自动调用，但是你得知道析构函数的价值。

2. List item

   vecor 是没有设计写时拷贝的，string 有可能设计了，并且之前也说了在 STL 容器上，写时拷贝也是存在缺陷的，所以并不是特别主流，g++ 下有用过，但好像后面还是舍弃了(这里后面会验证)

2、vector iterator的使用

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

void test_vector1()
{
	vector<int> v;   

	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);

	//begin+end,这里和string非常相似，可以说迭代器就是指针
	vector<int>::iterator it = v.begin();
	while(it != v.end())
	{
		cout << *it << " ";	
		++it;
	}
	cout << endl;

	//rbegin+rend,rbegin(rit)指向5,rend指向1,++rit怎么会倒着走呢
	//这里rit其实不再是原生指针了,它是一个被封装的类对象,重载operator++,才能实现++rit时是反向走,具体细节后面会说明
	//所以这就是之前为什么说迭代器不一定是(原生)指针的原因
	vector<int>::reverse_iterator rit = v.rbegin();
	while(rit != v.rend())
	{
		cout << *rit << " ";
		++rit; 
	}
	cout << endl;
}
int main()
{
	test_vector1();
	return 0;
}

📝补充

3、vector空间增长问题

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

void test_vector1()
{
	vector<int> v;   

	//开空间,改变容量,如果确定知道需要多少空间,reserve可以缓解vector增容所带来的代价
	v.reserve(10);
	/* err,错误访问,在之前string里就说明了operator[]会去检查下标是否小于size,[]只能去对size范围内的数据使用
	for(size_t i = 0; i < 10; ++i)
	{
		v[i] = i;	
	}
	*/
	//ok,正确访问
	for(size_t i = 0; i < 10; ++i)
	{
		v.push_back(i);	
	}
	
	//开空间+默认初始化,resize会影响size
	v.resize(20);	
	//开空间+指定初始化
	v.resize(20, 1);
}
int main()
{
	test_vector1();
	return 0;
}

📝补充

1. List item

   operator[] 和 at 的区别 ❓

   它们的功能类似，区别点在于：operator[] 检查越界比较粗暴，如果下标大于等于 size，它会直接断言报错，并中止程序；而 at 报错会抛异常，捕获后，它不会直接中止掉程序。

2. List item

   在 string 里也说明过了。这里vector 的 capacity 的代码在 vs 和 g++ 下分别运行会发现：vs 下 capacity 是按 1.5 倍增长的，且这里的初始容量是 0；g++ 是按 2 倍增长的，且这里的初始容量也是 0。这个问题经常会考察，不要固化的认为，顺序表的增容都是 2 倍，具体增长多少是根据具体的需求定义的。vs 是 PJ 版本的 STL，g++ 是 SGI 版本的 STL.

4、vector增删查改

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

void test_vector1()
{
	std::vector<int> first;
	std::vector<int> second;
	std::vector<int> third;

	//assign可以分配新内容，替换其当前内容，并相应地修改其size
	//n个val
	first.assign(7, 100);

	//迭代器区间
	std::vector<int>::iterator it;
	it = first.begin() + 1;
	second.assign(it, first.end() - 1);
	
	//指针区间,这里myints指向1,myints+3指向4,为什么只输出1 2 3
	//这里的两个参数myints,myints+3分别传给迭代器区间first,last。迭代器一定是一个左闭右开的区间[first, last),因为迭代器的循环条件是first!=last
	int myints[] = { 1, 2, 3, 4, 5 };
	third.assign(myints, myints + 3);
	for(auto e : third)
	{
		std::cout << e << " ";	
	}

	std::cout << "Size of first:" << int(first.size()) << '\n';
	std::cout << "Size of second:" << int(second.size()) << '\n';
	std::cout << "Size of third:" << int (third.size()) << '\n';
}
void test_vector2()
{
	int a[] = { 1, 2, 3, 4, 5 };
	vector<int> v(a, a + 5);
	
	//头插
	v.insert(v.begin(), 0);
	
	//在2的前面插入,可以先find 2,但是vector没有提供find,但是算法里提供了函数模板的find
	//之所以算法里提供find的原因是vector要find,list要find,所以这里的find提供一个模板就解决了,你可以是vector的迭代器,也可以是list的迭代器,string的迭代器没必要,当然string里自己提供了,为什么string要自己提供呢
	//因为string不仅要支持find一个字符,还要支持查找一个字符串,使用find要包algorithm
	vector<int>::iterator pos = find(v.begin(), v.end(), 2);
	if(pos != v.end())//找不到返回last
	{
		v.insert(pos, 20);	
	}
}
void test_vector3()
{
	//讲了算法里的find后,顺道再讲一下比较常用的sort
	int a[] = { 1, 20, 2, 3, 4, 5 };
	vector<int> v(a, a + 6);
	//升序
	sort(v.begin(), v.end());
	//降序,这里需要传一个比较器对象,这里就涉及仿函数,具体在后面优先级队列会详细介绍,使用它需要包functional
	/*greater<int> gt;
	sort(v.begin(), v.end(), gt);*/
	sort(v.begin(), v.end(), greater<int>());//同上,更推荐使用匿名对象

	//sort不仅可以对容器排序,还可以对数组排序,因为指向数组空间的指针是天然的迭代器
	//也就是说从现在开始就可以把C语言的qsort放弃了 
	int b[] = { 30, 4, 50, 6, 7 };
	sort(b, b + 5);
}
void test_vector4()
{
	int a[] = { 1, 20, 2, 3, 4, 5 };
	vector(int> v(a, a + 6);
	
	//头删
	v.erase(v.begin());
	
	//删除2
	vector<int>::iterator pos = find(v.begin, v.end(), 2);
	if(pos != v.end))
	{
		v.erase(pos);
	}	
}
int main()
{
	test_vector1();
	test_vector2();
	test_vector3();
	test_vector4();
	return 0;
}

📝说明

1. List item
   

2. List item
   
   

3. List item

   operator[] 和 at 的区别 ❓

   它们的功能类似，区别点在于：operator[] 检查越界比较粗暴，如果下标大于等于 size，它会直接断言报错；而 at 报错会抛异常，捕获后，它不会直接中止掉程序。

5、vector迭代器失效问题(建议与vector的模拟实现一起分析)

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector 的迭代器就是原生态指针 T*。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了(迭代器失效问题就类似于野指针问题)，而使用一块已经被释放的空间，造成的后果就是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)

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

void test_vector1()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4):
	
	vector<int>::iterator pos = find(v.begin(), v.end(), 2);
	if(pos != v.end())
	{
		v.insert(pos, 20);	
	}
	//在insert以后,pos有可能就失效了,失效了程序有可能就会崩溃，迭代器失效问题就类似于野指针问题
	//如下分别进行访问和修改,注意不同的编译器结果有可能不同,在VS下连访问都过不了(insert时增容导致的)
	cout << *pos << endl;
	*pos = 100;
}
void test_vector2()
{
	vector<int> v;
	//提前增容下面就不会增容了,所以就不会失效了?
	v.reserve(6);
	
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4):
	
	vector<int>::iterator pos = find(v.begin(), v.end(), 2);
	if(pos != v.end))
	{
		v.insert(pos, 20);
	}
	//在VS下运行程序后没有报错,这里我们就可以认定只要发生了增容,那么它一定就会失效
	//这里虽然没有发生增容,但严格来说还是失效了,这里的失效指的是pos的意义变了,它不再指向原来的值2,而是指向20,所以说迭代器失效并不一定是野指针,还有意义变了
	cout << *pos << endl;
	*pos = 100;
}
void test_vector3()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);

	vector<int>::iterator pos = find(v.begin(), v.end(), 2);
	if(pos != v.end()）
	{
		v.erase(pos);	
	}
	//这里erase后,导致pos失效了,失效的原因是pos的意义被改变了,且虽然pos没有野指针,但是意义变了,vs(p.j)版本下进行了强制检查,所以这里*pos就会报错
	cout << *pos << endl;
	*pos = 100; 
}
int main()
{
	//insert
	test_vector1();
	test_vector2();
	//erase
	test_vector3();
	return 0;
}

📝说明

1. List item

   VS 下insert 时有两种情况(调试可证)
   

2. List item

   已验，在 Linux g++ 下，test_vector1() 和 test_vector2() 都没有崩溃，这可能是因为不同的环境下，它的增容机制不同(可能一开始就有足够的空间)，但要注意是虽然在 g++ 下没有崩溃，但是 pos 依然还是失效了，原因是 pos 的意义被改变了。
   随后我们直接在 push_back 前先 reserve 4 个空间，让它达到增容的效果，之后再去访问和修改，它依然没有报错，这就推翻了上面说的增容机制不同。
   我们又猜想 g++ 下 vector 的增容会不会是原地增容，而不需要另外开辟空间，但随后也印证了猜想是错误的，因为如果原地增容，*pos 的值就不会是 0 了。
   所以这里十有八九 g++ 下并没有把野指针的访问修改操作检查出来(很早之前我们就说明了，关于内存的越界是抽查的形式)，已验：把增容前后的 v.begin() 的地址打印出来(注意不是打印 pos，之前打印 pos 的地址两次都是一样，让豌豆误以为 g++ 下是原地扩容的机制，还和上面的 *pos 是 0 的矛盾纠结了好久)

   

3. List item

   对于 test_vector3() 在 g++ 下没有报错，且打印的值是 3。这里就说明两个环境的检查机制不一样。但是无论这里的编译器是否报错，在 erase(pos) 后，我们都认为 pos 失效了，要注意的是失效后，就不要访问了，原因如下：

   因为如果我 erase 的是最后一个数据的话，再去访问，那么程序本身就已经存在问题了。

还有些擦边球的情况，如下代码所示。这段代码无论如何，在 vs 下都一定会报错(上面说过了)，但是在 Linux 下就有不同的境遇了。

1、出现了段错误

2、再 push_back 5，运行不会报错

为啥 push_back 5 后就不会报错了 ❓

所以这里最后一个是偶数运行就会出现段错误，最后一个是奇数就让你避开了这个错误。

所以这段代码的正确规范的写法应该如下

💨小结：对于失效的迭代器最好的方法就是不要去做任何的访问。

1.我们在 insert 时分为两种情况：其一是原空间不够，需要扩容(原地扩、异地扩【VS 和 g++ 下都是异地扩】)，之后 pos 还是指向原空间原位置的指针，所以 pos 就失效了，失效了再去访问就有可能会崩溃(VS 下会崩溃，g++ 下不会崩溃【检查内存越界是抽查的形式，不能说没被检查出能，我们就能随便酒驾】)；其二是原空间足够，不需要扩容，之后 pos 还是指向原空间原位置，但是 *pos 的值已经被改变了，所以我们也认为它失效了，因为它的意义已经变了。所以说 insert(pos, x) 以后，都认为 pos 失效了，此时就不要再去使用 pos 了，不要说程序没有崩溃，就依然去使用它，否则可能会出现各种不可预测的结果，STL 只是一个理论，它只是告诉我们 insert 后，pos 会失效，但它并没有规定什么时候失效，哪种场景失效。

2.对于 erase，我们在 erase 后也可能会失效，失效的原因有两种：其一，你有没有想过这样一个问题，insert 会扩容，那么 erase 也会缩容(比如有 100 个容量的空间、100 个有效数据，现在删除后，只剩下 30 个有效数据，然后想把容量给缩容至一半【开 50 个容量的空间，把旧空间内容拷贝后释放，pos 就是野指针了】)；其二，永远不动这块空间，直接把后面的数据往前覆盖。这两种方式有是有可能的，STL 并没有对它们进行规定，但是不管缩容与否，都认为它们失效了，因为意义已经变了。并且在 VS 下做了非常严格的检查(pos 仅仅是意义改变了，并没有野指针，都不能进行访问)，而 g++ 下没有问题。
对于失效，我们也有对应的机制来处理：比如 insert 是有一个返回值的，它返回一个迭代器指向新插入的那个元素，也就是说你想去访问那个指向的新插入的元素就可以 pos 接收 insert 的返回值。同理 erase 也是一样的，它返回被删除数据的下一个数据的位置。