Vector

　　Vector描述的是一个动态数组（dynamic array），并提供了相关操作和接口。

　　在使用Vector之前，需要引入头文件#include<vector>，在此头文件中，类型vector是一个定义于namespace std内的template：

template<
    class T,
    class Allocator = std::allocator<T>
> class vector;

• 1
• 2
• 3
• 4

　　其中T可以是任意类型，Allocator用来定义内存模型，默认是C++标准库提供的allocator

Vector的能力

　　Vector将元素复制到dynamic array内部，是一种动态的顺序表结构。Vector支持随机访问，可以以常量时间访问元素，Vector支持随机访问迭代器，以及STL提供的任何算法（排序、查找等）。但对于插入、删除和移动等操作，Vector效率较低（类似于数组的特性）。

大小（size）和容量（capacity）

　　vector区别于一般数组的特性之一就是能够动态的“扩容”，在容量能够容纳所有元素的前提下，提供基于pointer、reference、iterator的访问，以及元素的操作等，因此，大小和容量的概念至关重要。
　　Vector的大小（size）是指当前元素所占用空间，而容量（capacity）则是指vector分配内存预留大小，当size超过capacity时，vector会自动进行扩容，重新分配内存。举个例子——

vector<int> v;
	for (int i=0; i < 20; i++) {
		v.push_back(i);
		cout<<"i = "<<i
			<< " size = " << v.size()
			<< " capacity = " << v.capacity() << endl;
	}

• 1
• 2
• 3
• 4
• 5
• 6
• 7

　　可以看出，vector的大小是随着插入元素不断增加的，也就是说，size()的作用其实和sizeof的作用类似，但是由于vector都是reference语义的操作，sizeof一个vector对象，无法得到实际大小，所以vector提供了size成员函数。而capacity()则反映了vector的动态扩容机制。
　　vector容量的概念之所以重要，有两个原因——
　　1.一旦内存重新分配，vector相关元素的所有reference、pointer、iterator都会失效。这里的失效是指，原来的值需要更新到重新分配后的内存地址。
　　2.内存的重新分配需要一定时间。

reserve函数

　　通过reserve函数可以显式的指定预留空间的大小，而避免vector反复的进行内存重新分配， 从而提高vector的使用效率。但reserve不能减小vector容量，比如，已存在vector.capacity = 100，使用reserve(80)不会有任何作用。

	vector<int> v(100);
	cout<<v.size()<<" "<<v.capacity()<<endl;
	v.reserve(80);
	cout<<v.size()<<" "<<v.capacity()<<endl;

• 1
• 2
• 3
• 4

　　此外，还可以通过vector的构造函数显式的指定容量大小，比如：

	vector<int> v(100);

• 1

　　使用这种方法的时候，vector会调用元素的default构造函数进行初始化，对于基础类型，vector会进行零值初始化（类似于Java的初始化机制），比如说——

class test{
	static int count;
public:
	test(){
		count++;
		cout<<"test constructor function:"<<count<<endl;
	}
};

int test::count = 0;

int main(){
	vector<test> v(10);// 调用10次test默认构造函数	
	return 0;
} 

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15

　　这种方法可能会频繁调用构造函数，因此效率不如reverse的高。

shrink_to_fit函数

　　reverse函数无法缩减容量，但是很多时候，vector自动扩容机制分配的内存往往是多余的，如果频繁使用vector的话，这种内存浪费会相当可观。C++11提供了缩减容量以符合当前需求的函数，shrink_to_fit函数。该函数不具有强制力的要求，换言之，具体实现可能会因编译器实现而不同。但大多数情况下，缩减容量是有效的，比如——

	vector<int> v;
	cout<<"capacity = "<<v.capacity()<<endl;
	v.reserve(10);
	cout<<"capacity = "<<v.capacity()<<endl;
	v.shrink_to_fit();
	cout<<"capacity = "<<v.capacity()<<endl;

• 1
• 2
• 3
• 4
• 5
• 6

Vector操作

构造函数、析构函数

　　vector的构造函数和析构函数如下表所示——

序号	操作	效果
1	vector<Elem> c	Default构造函数，产生一个vector，没有任何元素
2	vector<Elem>c(c2) vector<Elem>c=c2	Copy构造函数，建立c2同型vector并成为c2的一份副本，该复制是深度复制
3	vector<Elem>c(rv) vector<Elem>c=rv	rv是一个vector右值引用，那么这里的构造函数是一个Move构造函数，建立一个新的vector，取右值内容（C++11新特性）
4	vector<Elem>c(n)	利用元素的默认构造函数生成一个大小为n（容量也为n）的vector
5	vector<Elem>c(n,elem)	建立一个大小为n的vector，并初始化为elem
6	vector<Elem>c(beg,end)	建立一个vector，并以迭代器所指向的区间[beg,end）作为元素值
7	vector<Elem>c(initlist) vector<Elem>c=initlist	建立一个vector，以初值列initlist元素为初值（C++11新特性）
8	c.~vector()	销毁所有元素，释放内存

　　其中3和7是C++11新特性，6是基于迭代器的，第一次见可能会比较陌生，但使用起来很方便，比如——

	vector<int> v{ 1,2,3,4,5,6,7,8,9 };// initlist初始化
	vector<int> v2(v.begin(), v.end());// 基于迭代器的初始化
	vector<int> v3 = move(v2); // Move构造函数
	for (const auto&elem : v3) // range-based for循环
	{
		cout << elem << " ";
	}

• 1
• 2
• 3
• 4
• 5
• 6
• 7

非更易型操作(Nonmodifying Operating)

　　STL中有非更易的概念，即不改变容器内元素.

序号	操作	效果
1	c.empty()	容器为空返回true，不为空返回false，相当于size()==0
2	c.size()	返回当前元素的个数
3	c.max_size()	返回元素个数之最大可能量
4	c.capacity()	返回容器当前最大容量
5	c.reserve(n)	如果容器不足，显示扩容，该操作会引起迭代器、指针、引用的失效，但并未改变元素的值，因此仍旧视为非更易型操作
6	c.shrink_to_fit()	降低容量，使得size()==capacity()，（C++11新特性）
7	c1==c2	对每个元素调用c1==c2，全部相等返回true
8	c1！=c2	只要有一个元素相等，返回true，相当于!(c1==c2)
9	c1>c2,c1>=c2,c1<c2,c1<=c2	同上，依次类推

赋值操作(Assignment Operating)

　　赋值操作可能会引起元素的默认构造函数、复制构造函数、赋值操作符等，详细如下表——

序号	操作	效果
1	c1=c2	把c2的全部元素赋值给c
2	c=rv	将rvalue 右值引用以 move assignment的方式赋值给c（C++11新特性）
3	c = initlist	将初值列initlist的所有元素赋值给c(C++11新特性)
4	c.assign(n,elem)	复制n个elem，赋值给c
5	c.assign(beg,end)	复制迭代器指向区间[beg,end)内容，赋值给c
6	c.assign(initlist)	将初值列initlist的所有元素赋值给c
7	c.swap(c2)	置换c和c2的数据
8	swap(c1,c2)	置换c1和c2的数据

元素访问（Element Access）

　　下表列出了所有访问vector元素的方法，对于所有non-const元素，返回的都是元素的reference，这些操作中，只有at()会检查边界，如果越界，抛出out_of_range异常。——

序号	操作	效果
1	c[index]	返回索引index所指向的元素
2	c.at(index)	返回index所指向的元素（会进行边界检查）
3	c.front()	返回第一个元素（不会检查第一元素是否存在）
4	c.back()	返回最后一个元素（不会检查最后一个元素是否存在）

　　 由于vector只提供了at函数的检查元素，所以对于越界或者访问空元素的情况，其结果是未定义的，视编译器而异。Visual Studio比较严格，将此行为定义为运行时异常，而GCC则较为宽松，允许这一非法操作。

	vector<int> v{ 1,2,3,4,5,6,7,8,9 };
	v.clear();
	cout << v.front() << endl;// Expression:front() called on empty vector.
	cout<< v[10]<<endl;// Expression:vector subscript out of range.

• 1
• 2
• 3
• 4

迭代器函数（Iterator Function）

　　 vector支持随机访问（random access）迭代器，理论上STL提供的所有迭代器都能为其所用。迭代器是STL提供操作容器的重要工具，熟练使用迭代器能够将STL各大容器的性能发挥到极致。

序号	操作	效果
1	c.begin()	返回一个randrom access iterator指向第一个元素
2	c.end()	返回一个random access iterator指向的之后一个元素
3	c.cbegin()	返回一个const random access iterator指向的第一个元素（C++11新特性）
4	c.cend()	返回一个const random access iterator指向的最后一个元素（C++11新特性）
5	c.rbegin()	返回一个反向迭代器（reverse iterator）指向的第一个元素
6	c.rend()	返回一个reverse iterator指向的最后一个元素
7	c.crbegin()	返回一个const reverse iterator指向的第一个元素（C++新特性）
8	c.crend()	返回一个const reverse iterator指向的最后一个元素（C++11新特性）

　　迭代器结合auto以及range-based for循环，能够将元素的访问以一种清新脱俗的方式展现出来——

	vector<int> v{ 1,2,3,4,5,6,7,8,9 };
	for (auto it = v.cbegin(); it != v.cend();++it) {
		cout << *it << " ";
	}

• 1
• 2
• 3
• 4

　　再比如说容器元素的逆序输出——

	vector<int> v{ 1,2,3,4,5,6,7,8,9 };
	for (auto it = v.crbegin(); it != v.crend();++it) {
		cout << *it << " ";
	}

• 1
• 2
• 3
• 4

插入和移除(Inserting and Removing)

　　插入和移除无疑是最常用的操作，掌握了这些，基本上就可以使容器在自己的代码中产生战斗力——

序号	操作	效果
1	c.push_back(elem)	在vector末尾插入元素elem
2	c.pop_back()	移除最后一个元素，但是不返回该元素
3	c.insert(pos,elem)	在iterator指向的pos位置的前方插入一个元素elem的副本，并返回新元素的位置（此时返回的是整型，而非iterator）
4	c.insert(pos,n,elem)	在iterator指向的pos位置的前方插入n个元素的副本，并返回第一个新元素的位置
5	c.insert(pos,beg,end)	在iterator指向的pos位置的前方插入区间[beg,end)内所有元素的副本，并返回第一个新元素的位置
6	c.insert(pos,initlist)	在iterator指向的pos位置的前方插入初始化列表所有元素的副本，并返回第一个元素的位置（C++11新特性）
7	c.emplace(pos,args…)	在iterator指向的pos位置的前方插入一个以args为初值的元素，并返回新元素的位置（C++11新特性）
8	c.emplace_back(args…)	在vector末尾附加一个args为初值的元素，不返回任何东西
9	c.erase(pos)	移除iterator位置pos上的元素，返回下一个元素的位置
10	c.erase(beg,end)	移除区间[beg,end)所指向的元素所有内容，返回下一个元素的位置
11	c.resize(num)	将vector大小调整为num，若大小增大，新元素以默认构造函数或者零值进行初始化
12	c.resize(num,elem)	将vector大小调整为num，若大小增大，新元素以elem进行初始化
13	c.clear()	移除所有元素，容器清空

　　我们演示一个插入到删除的过程——

	vector<int>v;
	vector<int>v2{ -1,-2,-3,-4 };
	cout << "Source data:";
	for (int i = 0; i < 10; i++) {
		v.push_back(i);
	}
	for (const auto&elem : v) {
		cout << elem << " ";
	}
	
	cout << endl << "insert vector 2:";
	v.insert(v.end(), v2.begin(), v2.end());
	for (const auto&elem : v) {
		cout << elem << " ";
	}
	
	cout << endl << "remove vector 2:";
	auto begin_it = v.begin();
	while (*begin_it != *v2.begin()) {
		begin_it++;
	}
	v.erase(begin_it, v.end());
	for (const auto&elem : v) {
		cout << elem << " ";
	}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26

异常处理

　　vector仅支持最低限度的逻辑差错检查，Subscript操作符的安全版本at()是唯一一个被C++ standard认可得以抛出异常的函数，此外C++ standard 同时规定，只有一般标准异常或者被用户自定义的异常才可能发生，也就是说，vector的一些非法操作，在运行时都不会抛出异常，但程序员需要对自己的非法操作负责。
　　1. 如果push_back安插元素时发生异常，函数不产生效用；
　　2. 如果元素remove/copy操作不抛出异常， 那么insert/emplace等要么成功，要么不抛出异常；
　　3. pop_back绝对不会抛出任何异常；
　　4. 如果元素remove/copy操作不抛出异常,erase也不会抛出异常；
　　5. swap和clear不会抛出异常；
　　6. 如果元素remove/copy操作不抛出异常，那么所有的操作不是成功，就是不产生任何效果，包括不抛出异常。
　　以上所有都基于“析构函数不得抛出任何异常”的前提。但实际上，编译器会做不同程度的优化，比如热心的VS，几乎在所有vector可能出现的异常检测上都做了处理，在C++ Standard未定义的部分做了诸多工作。