C++ 顺序容器

顺序容器概述

一般来说，每个容器都定义在一个头文件中，文件名与类型相同。
容器均定义为模板类。

容器	功能	优缺点
array	固定大小数组	支持快速随机访问，不能添加或删除元素
vector	可变大小数组	支持快速随机访问，在尾部插入或删除速度很快
deque	双端队列	支持快速随机访问，在头尾位置插入或删除速度很快
list	双向列表	只支持双向顺序访问，在链表任何位置插入或删除操作速度都很快
forward_list	单向链表	只支持单向顺序访问，在链表任何位置插入或删除操作速度都很快

forward_list 和 array 是C++新标准增加的类型。
以下是一些选择容器的基本原则：

• 除非有很好的理由选择其他容器，否则使用 vector。
• 如果程序有很多小的元素，且空间的额外开销很重要，则不要使用 list 或 forward_list。
• 如果程序要求随机访问元素，应使用 vector 或 deque。
• 如果程序要求在容器的中间或删除元素，应使用 list 或 forward_list。
• 如果程序需要在头尾位置插入或删除元素，但不会在中间位置进行插入或删除操作，则使用 deque。
• 如果程序只有在读取输入时才需要在容器中间位置插入元素，随后需要随机访问元素，则
  • 首先，确定是否真的需要在容器中间位置添加元素。当处理输入数据时，通常可以很容易地向 vector 追加数据，然后再调用标准库的 sort 函数来重排容器中的元素，从而避免在中间位置添加元素。
  • 如果必须在中间位置插入元素，考虑在输入阶段使用 list，一旦输入完成，将 list 中的内容拷贝到一个 vector 中。

如果不确定应用使用哪种容器，那么可以在程序中只使用 vector 和 list 公共的操作：使用迭代器，不使用下标操作，避免随机访问。

容器类型成员

类型别名	功能
iterator	此容器类型的迭代器
const_iterator	可以读取元素，但不能修改元素的迭代器类型
size_type	无符号整数类型，足够保存此种容器类型最大可能容器的大小
diffreence_type	带符号整数类型，足够保存两个迭代器之间的距离
value_type	元素类型
reference	元素的左值类型
const_reference	元素的 const 左值类型
reverse_iterator	按逆序寻址元素的迭代器
const_reverse_iterator	不允许修改元素的逆迭代器

通过类型别名，我们可以在不了解容器中元素类型的情况下使用它。
如果需要元素类型，可以使用容器的 value_type。
如果需要元素类型的一个引用，可以使用 reference 或 const_reference。
使用作用域运算符来说明我们希望使用的类型成员；例：list<string>::iterator iter;

顺序容器定义和初始化

默认初始化

容器为空，没有任何元素。

	vector <int> V;  //容器包含 int 类型的元素，容器为空，大小为零。
	deque <char> D;  //双端队列
	list <int> List; //双向链表
	forward_list <int> L; //单向链表

指定容器大小

只有顺序容器（不包括 array）的构造函数接受大小参数。
只提供容器大小参数

	vector <int> V(5);  //内含 5 个整数,默认值为 0 
	deque <char> D(6);  //内含 6 个字符,默认值为 '\0'
	list <double> List(11); ///内含 11 个浮点数,默认值为 0 

提供容器大小，并指定显示的初始值

	vector <int> V(5, 12); //内含 5 个整数，这些元素初始值都为 12 。
	deque <char> D(5,'A'); //内含 5 个字符，这些元素初始值都为 'A' 。

如果元素类型是内置类型或有默认构造函数的类类型，可以只提供容器大小参数；如果元素类型没有默认构造函数，则必须指定一个显示的初始值。

列表初始化

初始化为初始化列表中元素的拷贝，初始化列表隐含地指定了容器的大小。

	vector <int> V{ 1,3,5,7,11,13,17,19 };  //可变数组
	deque <char> D{ 'A','B','C' }; //双端队列
	list <string> List{ "an","list","c++" }; //双向链表
	forward_list <int> L{ 1,3,5,7 }; //单向链表

将一个新容器创建为另一个容器的拷贝

拷贝整个容器

	vector <int> V1{1,3,5,7,11,13,17,19};
	vector <int> V2{ V1 }; 
	deque <char> D1{ 'A','B','C' };
	deque <char> D2{ D1 };

拷贝迭代器指定范围中的元素

	vector <int> V1{1,3,5,7,11,13,17,19};
	auto begin = &V1[2]; //元素 5 的位置
	auto end = &V1[6];   //元素 17 的位置
	vector <int> V2( begin, end ); //拷贝元素：5,7，11,13
	vector <int> V3( V1.begin(), V1.end() ); //拷贝容器 V1 内的所有元素

当将一个容器初始化另一个容器的拷贝时，两个容器的类型和元素类型都必须相同（或可隐式类型转换）。

数组的定义和初始化

标准库 array 具有固定大小；定义一个 array 时，必须指定元素类型的同时，还要指定容器大小。

1. 在定义数组时对全部数组元素赋予初值。
   例：array <int, 5> arr{ 1,2,3,4,5 };
2. 可以只对一部分元素赋值，剩余未被赋予初值的元素赋予默认值 0。
   例：array <int, 5> arr{ 1,2,3 }; //等价于array <int, 5> arr{ 1,2,3,0,0 };
3. 数组初始化为 0。
   例：array <int, 5> arr { 0 };
4. 不能对内置数组类型进行拷贝或对象赋值操作，但 array 并无此限制：

	array <int, 5> arr1 { 1,2,3,4,5 };
	array <int, 5> arr2 = arr1; //数组拷贝

array 的拷贝要求容器的类型和大小必须相同，容器内元素类型必须相同。

容器的赋值运算

赋值运算符将其左边容器中的全部元素替换为右边容器中元素的拷贝。
赋值运算符要求左边和右边的运算对象具有相同的类型。

	vector <int> V1 { 1,3,5,7,11,13,17,19 };
	vector <int> V2 { 3,3,7 };
	V1 = V2; // V1 内的元素变为3,3,7
	V1 = { 3,4,5,6 }; // V1 的大小变为 4  

assign 函数

顺序容器（array除外）还定义了一个 assign 成员，允许我们从一个不同但相容的类型赋值，或者从容器的一个子序列赋值。用参数指定的元素（的拷贝）替换左边容器中的所有元素。

	vector <int> V1{ 2,3,4 };
	vector <int> V2 { 1, 3, 5, 7, 11, 13, 17, 19 };
	V1.assign( V2.begin(), V2.end() ); //将V1中的元素替换为一对迭代器指定范围中的元素
	V1.assign( {1,2,3,4} ); //将V1中的元素替换为列表中的元素
	V1.assign( 5,12 );      //将V1中的元素替换为 5 个 12 

swap 函数

swap 操作交换两个相同类型的容器的内容；调用 swap 函数后，两个容器的元素将会交换：

	vector <int> V1{ 2,3,4 };
	vector <int> V2 { 1, 3, 5, 7, 11, 13, 17, 19 };
	swap(V1,V2); 
	/*交换后：
		V1 包含八个元素：1, 3, 5, 7, 11, 13, 17, 19 
		V2 包含三个元素：2,3,4 
	*/

除 array 外，swap 不对任何元素进行拷贝、删除或插入操作。
交换两个容器内容的操作会很快，swap 只是交换了两个容器的内部数据结构。
swap 操作两个 array 会真正交换它们的元素。

数组的赋值运算

	array <int, 5> arr1{ 1,2,3,4,5 };
	array <int, 5> arr2{ 0 };
	arr2 = arr1;          
	arr2 = { 3,4,5,6,7 }; 
	arr2 = { 3,4 };       //等价于arr2 = { 3,4,0,0,0 };  

array 的赋值要求容器的类型和大小必须相同，容器内元素类型必须相同。

关系运算符

每个容器类型都支持相等运算符（==和!=）；除了无序关联容器外的所有容器都支持关系运算符（>、>=、<、<=）。
比较两个容器实际上是进行元素的逐对比较：

• 如果两个容器元素数目相同且所有元素都两两对应相同等，则这两个容器相等。
• 如果两个容器元素数目不同，但较小容器中的每个元素都等于较大容器中的对应元素，则较小容器小于较大容器。
• 如果两个容器都不是另一个容器的前缀子序列，则比较它们的结果取决于第一个不想等的元素的比较结果。

	vector <int> V1 { 1, 3, 5, 7, 11 };
	vector <int> V2{ 1, 3, 5 };
	vector <int> V3{ 1, 3, 5, 7, 11 };
	vector <int> V4{ 1, 7, 3 };
	cout << ( V2 < V1 ) << endl;  //true，每个元素都相等，但 V2 中元素数目更少
	cout << ( V1 == V3 ) << endl; //true，每个元素都相等，且 V1 和 V3 大小相同 
	cout << ( V3 < V4 ) << endl;  //true，V3 和 V4 在元素[1]处不同，且 V3[1] < V4[1]

关系运算符左右两边的运算对象必须是相同类型的容器，且必须保存相同类型的元素。
只有当其元素类型也定义了相应的比较运算符时，我们才可以使用关系运算符来比较容器。

顺序容器访问元素

包括 array 在内的每个顺序容器都有一个 front 成员函数，除 forward_list 以外的所有顺序容器都有一个 back 成员函数。
这两个操作分别返回首元素和尾元素的引用。

	vector <char> V{ 'A','B','C','D' };
	char  C1 = V.front(); //获取首元素的拷贝
	C1 = 'Z'; //未改变首元素的值
	char & C2 = V.front(); //获取首元素的引用
	C2 = 'F'; //首元素的值变为 'F'
	char& C3 = V.back();  //获取尾元素的引用
	C3 = 'E'; //尾元素的值变为 'E'

对一个空容器调用 front 和 back，就象使用一个越界的下标一样，是一种严重的程序设计错误。

下标操作和安全的随机访问

提供快速随机访问的容器（string、vector、deque 和 array）都提供下标运算符。
给定的下标必须大于等于 0，且小于容器的大小。

	vector <char> V{ 'A','B','C','D' };
	for (unsigned int i = 0; i < 4; i++)
	{
		cout << V[i] << ' ';  //下标访问
	}

at 成员函数类似下标运算符，但如果下标越界，at 会抛出一个 out_of_range 异常。

	vector <char> V{ 'A','B','C','D' };
	for (unsigned int i = 0; i < 4; i++)
	{
		cout << V.at(i) << ' ';  // at 成员函数访问
	}

在容器中访问元素的成员函数（front、back、下标 和 at）返回的都是引用。

	vector <char> V{ 'A','B','C','D' };
	V[2] = 'Z';    //改变元素V[2]的值
	V.at(3) = 'N'; //改变元素V[3]的值

如果容器是一个 const 对象，则返回值是 const 对象的引用。

向顺序容器添加元素

除 array 外，所有标准库都提供灵活的内存管理。
在一个 vector 或 string 的尾部之外的任何位置，或是一个 deque 的首尾之外的任何位置添加元素，都需要移动元素。
向一个 vector 或 string 添加元素可能引起整个对象存储空间的重新分配。

push_back 函数

除了 array 和 forward_list 之外，每个顺序容器（包括 string 类型）都支持 push_back。
push_back 将一个元素追加到一个顺序容器的尾部。

	vector <int> V; //可以先定义一个空的容器
	V.push_back(4); //然后向容器的尾部添加元素
	V.push_back(5);

push_front 函数

vector 和 string 不支持 push_front 操作。
list、forward_list 和 deque 容器支持 push_front 操作，此操作将元素插入到容器头部。

	forward_list <char> L; //可以先定义一个空的容器
	L.push_front('A'); //然后向容器的首部添加元素
	L.push_front('B');
	L.push_front('C');

在容器中的特定位置添加元素

vector、deque、list 和 string 都支持 insert 成员。
forword_list 有自己专有版本的 insert 操作。
insert 成员提供更一般的添加功能，它允许我们在容器中任意位置插入 0 个或多个元素。
在迭代器指向的元素之前插入一个值。

	list <char> L{ 'A','B','C','D' };
	for (auto it = L.begin(); it != L.end(); ++it )
	{
		if ( *it == 'B' )
		{//在元素'B'之前，插入元素'Z'
			 L.insert( it,'Z' );
			 break;
		}
	}

在迭代器指向的元素之前插入 n 个相同的值；若 n 为零，insert 函数返回第一个参数。

	list <char> L{ 'A','B','C','D' };
	for (auto it = L.begin(); it != L.end(); ++it )
	{
		if ( *it == 'B' )
		{//在元素'B'之前，插入 4 个'i'
			 L.insert( it,4,'i' );
			 break;
		}
	}

在迭代器指向的元素之前插入一个花括号包围的元素值列表；若元素值列表为空，insert 函数返回第一个参数。

	list <char> L{ 'A','B','C','D' };
	for (auto it = L.begin(); it != L.end(); ++it )
	{
		if ( *it == 'B' )
		{//在元素'B'之前，插入元素'a','b','c'
			L.insert( it, {'a','b','c'} );
			 break;
		}
	}

在迭代器指向的元素之前插入一对迭代器指定范围的所有元素；第一个迭代器指向要插入的第一个元素，第二个迭代器指向要插入的最后一个元素之后的位置。
如果范围为空，不插入任何元素，insert 函数返回第一个参数。

	list <char> L1{ 'a','b','c' };
	list <char> L2{ 'A','B','C','D' };
	for (auto it = L2.begin(); it != L2.end(); ++it )
	{
		if ( *it == 'B' )
		{//在元素'B'之前，插入列表L1内的所有元素。
			L2.insert( it,L1.begin(), L1.end() ); 
			break;
		}
	}

insert 函数返回指向第一个新加入元素的迭代器。

	char L1[] = {'a','b','c'};
	list <char> L2{ 'A','B','C','D' };
	auto it = L2.begin();
	for ( unsigned int i = 0; i < 3; ++i )
	{//在 L2 列表头部先后插入元素'a','b','c'
		it1 = L2.insert( it, L1[i] );
	}

如果传递给 insert 一对迭代器，它们不能指向添加元素的目标容器。

使用 emplace 操作

新标准引入了三个新成员——emplace、emplace 和 emplace_back，这些操作是构造而不是拷贝元素；这些操作分别对应 push_front、insert 和 push_back。

当调用 push 或 insert 成员函数时，我们将元素类型的对象传递给他们，这些对象被拷贝到容器中。
当调用顺序容器的 empalce 成员函数时，则是将参数传递给元素类型的构造函数；empalce 成员使用这些参数在容器管理的内存空间中直接构造元素。
emplace 函数的参数根据元素类型而变化，参数必须与元素的构造函数相匹配。

删除元素

成员函数 pop_front 和 pop_back 分别删除首元素和尾元素。
vector 和 string 不支持 pop_front，forward_list 不支持 pop_back。

	deque <char> D{ 'A','B','C','D' };
	char C1 = D.front(); //保存首元素
	D.pop_front(); //弹出首元素
	char C2 = D.back();  //保存尾元素
	D.pop_back();  //弹出尾元素

pop_front 和 pop_back 操作返回 void；弹出元素之前，最好保存它。
不能对一个空容器执行弹出操作。

从容器指定位置删除元素

forward_list 有特殊版本的 erase。
成员函数 erase 从容器中删除迭代器指定的元素。

	list <char> L{ 'A','B','C','D','E' };
	for (auto it = L.begin(); it != L.end(); ++it )
	{
		if ( *it == 'C' )        //删除指定的元素
		{
			it = L.erase(it);
			cout << *it << endl; //输出被删除的元素之后位置的迭代器。
			break;
		}
	}

成员函数 erase 删除一对迭代器指定范围内的所有元素；第一个迭代器指向被删除的第一个元素，第二个迭代器指向被删除的最后一个元素之后的位置。

	list <char> L{ 'A','B','C','D','E' };
	for (auto it = L.begin(); it != L.end(); ++it )
	{
		if ( *it == 'D' ) //迭代器指向被删除元素之后的位置
		{
			 L.erase( L.begin(), it ); //删除元素'A','B','C'
			 break;
		}
	}

两个版本的 erase 函数返回指向被删除的元素（或最后一个元素）之后位置的迭代器。

删除容器内所有的元素

成员函数 clear 删除容器内所有元素。

	list <char> L{ 'A','B','C','D','E' };
	L.clear(); //与 L.erase( L.begin(), L.end()); 等价

特殊的 forward_list 操作

当在 forward_list 中添加或删除元素时，我们必须关注两个迭代器：一个指向我们要处理的元素，另一个指向其前驱。
forward_list 定义了 before_begin 成员函数，它返回一个首前迭代器（这个迭代器不能解引用）。
这个迭代器允许我们在链表首元素之前并不存在的元素“之后”添加或删除元素。（即在链表首元素之前添加删除元素。）
成员函数 insert_after 在迭代器指向的元素之后插入元素；返回一个指向最后一个插入元素的迭代器。

	vector <int> v{ 6,8,10 };
	forward_list <int> list{ 1,3,5,7,9 };
	auto it = list.begin();
	list.insert_after( it,12 );              //插入一个元素
	list.insert_after(it,v.begin(),v.end()); //插入 n 个相同的元素
	list.insert_after( it, {0,2,4} );        //插入一对迭代器范围内的元素
	list.insert_after(it, 3, 11);            //插入花括号列表内的元素

成员函数 erase_after 删除迭代器指向的元素之后的元素；返回一个指向被删除的最后一个元素之后元素的迭代器。

	forward_list <int> list{ 1,3,5,7,9 };
	auto it = list.begin();
	list.erase_after( it ); //删除 3
//	list.erase_after(list.begin(),list.end());

在迭代器指向的元素之前插入元素。

	vector <int> v{ 6,8,10 };
	forward_list <int> list{ 1,3,5,7,9 };
	auto it = list.before_begin(); //首前迭代器
	list.insert_after( it,12 );
	list.insert_after(it,v.begin(),v.end());
	list.insert_after( it, {0,2,4} );
	list.insert_after(it, 3, 11);	

容器大小和容量

容器大小

除了一个例外，每个容器类型都有三个与大小相关的操作。
成员函数 size 返回容器中元素的数目。
成员函数 empty 判断容器是否为空。
成员函数 max_size 返回容器一个大于或等于该类型容器所容纳的最大元素数的值。
forward_list 支持 empty 和 max_size，但不支持 size。

	vector<int> V;
	cout << V.size() << endl;  //容器中元素的数目为零
	cout << V.empty() << endl; //容器为空，返回 ture
	cout << V.max_size() << endl; 

管理容量的成员函数

shrink_to_fit 只适用于 vector、string 和 deque。
成员函数 capacity 操作告诉我们容器在不扩张内存空间的情况下可以容纳多少个元素。
成员函数 reserve 操作允许我们通知容器它应该准备保存多少个元素。
成员函数 shrink_to_fit 操作请求退回不需要的内存空间。
capacity 至少与 size 一样大。

	vector<char> V;   //空容器，size = 0，capacity = 0
	V.push_back('A');
	V.push_back('B');
	cout << V.size() << endl; //添加元素后，size = 2
	cout << V.capacity() << endl;//添加元素后，capacity = 2

只有当需要的内存空间超过当前容量时，调用 reserve 函数才会改变 vector 的容量。

	vector<char> V;  //空容器，size = 0，capacity = 0
	V.reserve(5); //将 capacity 设定为 5
	V.push_back('A');
	V.push_back('B');
	cout << V.size() << endl; //添加元素后，size = 2
	cout << V.capacity() << endl;//添加元素后，capacity = 5

如果需求大小小于或等于当前容量，调用 reserve 函数什么也不会做。

	vector<char> V{ 'A','B','C','D','E','F' };
	cout << V.capacity() << endl; //capacity = 6
	V.reserve(4);
	cout << V.capacity() << endl; //capacity = 6

改变容器大小

可以使用 resize 来增大或缩小容器，array 不支持 resize。
如果当前大小大于所要求的大小，容器后部的元素会被删除；

	vector<int> V{ 1,2,3,4,5 };
	cout << V.capacity() << endl; //capacity = 6
	V.resize(3);  //V容器内的元素变为：1,2,3       
	cout << V.capacity() << endl; //capacity = 6         

如果当前大小小于新大小，会将新元素添加到容器后部。

	vector<int> V{ 1,2,3,4 };
	cout << V.capacity() << endl; //capacity = 4
	V.resize(8, 10); //V容器内的元素变为：1,2,3,4,10,10,10   
	cout << V.capacity() << endl; //capacity = 8

如果元素类型是内置类型或有默认构造函数的类类型，可以只提供容器大小参数；如果元素类型没有默认构造函数，则必须指定一个显示的初始值。

容器适配器

除了顺序容器外，标准库还定义了三个顺序容器适配器（adaptor）：stack、queue 和 priority_queue。
容器、迭代器和函数都有适配器。
本质上，一个适配是一种机制，能使某种事物的行为看起来像另外一种事物一样。

定义一个适配器

每个适配器都定义两个构造函数：
默认构造函数创建一个空对象。

	stack <char> S; //空栈

接受一个容器的构造函数拷贝该容器来初始化适配器。

	deque <int> D{ 1,2,3,4,5 };
	stack <int> S2{ D };
	queue <int> Q{ D };

默认情况下，stack 和 queue 是基于 deque 实现的，priority_queue 是在 vector 之上实现的。
我们可以创建一个适配器时将一个命名的顺序容器作为第二个类型参数，来重载默认容器类型。

	vector <int> V{ 1,2,3,4,5 };
	stack <int,vector<int>> S{ V };
	list <char> L{ 'A','B','C' };
	queue <char,list<char>> Q{ L };

对于一个给定的适配器，可以使用那些容器是有限制的。
所有适配器都要求容器具有添加、删除以及访问尾元素的能力；因此，适配器不能构造在 array 和 forward_list 来构造适配器。

栈适配器

stack 适配器定义在 <stack> 头文件中。
stack 只要求 push_back、pop_back 和 back 操作；因此，可以使用除 arrary 和 forward_list 之外的任何容器类型来构造 stack。

	stack <char> S; //空栈
	S.push('A');    //'A' 入栈 
	S.push('B');    //'B' 入栈 
	S.push('C');    //'C' 入栈 
	cout << S.top() << endl; //获取栈顶 'C'
	S.pop();  //'C' 出栈 
	cout << S.top() << endl; //获取栈顶 'B'

每个容器适配器都基于底层容器类型的操作定义了自己的特殊操作。
我们只可以使用适配器操作，而不能使用底层容器类型的操作。

队列适配器

queue 和 priority_queue 适配器定义在 <queue> 头文件中。
queue 要求 back、push_back、front 和 push_front 操作；因此，可以构造于 list 或 deque 之上，但不能基于 vector 构造。
priority_queue 除了 front、push_back 和 pop_back 操作之外还要求随机访问能力；因此，priority_queue 可以构造于 vector 或 deque 之上，但不能基于 list 构造。

	queue <char> Q; //空队
	Q.push('A'); //'A' 入队 
	Q.push('B'); //'B' 入队 
	Q.push('C'); //'C' 入队 
	cout << Q.front() << endl; //返回队头 'A' 
	cout << Q.back() << endl;  //返回队尾 'C' 
	Q.pop(); //'A' 出队
	cout << Q.front() << endl; //返回队头 'B' 

priority_queue 允许我们为队列中的元素建立优先级。
新加入的元素会排在所有优先级比它低的已有元素之前。
默认情况下，标准库在元素类型上使用<运算符来确定相对优先级。