[C++知识库]C++ STL(一)容器总结

一、容器库概述

1.1 迭代器

所有标准库容器都可以使用迭代器，但是只有少数几种支持下标运算符(vector、deque、map)。有效迭代器指向容器中的某个元素，或者指向容器中尾元素的下一个位置，后者成为尾后迭代器，其余都是无效的。

迭代器运算符
使用==和!=可以比较两个有效迭代器是否相等；和指针类似，也能通过解引用有效迭代器获取它所指的元素(不包括尾后迭代器)。

一个迭代器范围由一对迭代器表示，一个指向容器C中的元素，一个是容器C的尾后迭代器，如左闭合区间[begin, end)。

1.2 容器类型别名

通过类型别名，可以在不了解容器中元素类型的情况下使用它。如果需要元素类型，可以使用value_type，如果需要一个元素的引用可以使用reference或const_reference。

1.3 容器的定义与初始化

array与其他容器不同，大小也是其类型的一部分，定义时除了指定元素类型，还要指定容器大小，如：array<int, const_n> a1;。

	C c1;    //默认初始化，c1为空
	array<int, const_n> a1; //array默认初始化有别于其它容器，元素个数为const_n

	C c2(c1);  //c2初始化为c1的拷贝，c1和c2必须类型相同，如果是array，大小还要相同
	C c3 = c1;  //同上

	C c4 { a, b, c... }; //c4初始化为列表中元素的拷贝，列表元素与容器元素类型需兼容，如果是array，列表元素数小于等于array大小
	C c5 = { a, b, c... };  // 同上

	C c6(begin, end);  //初始化为迭代器begin，end所指范围元素的拷贝，类型需兼容，array不适用

	// 只有顺序容器才会用
	C c7(n);    //c7包含n个元素，元素值会按照类型默认初始化，string不适用
	C c8(n, t);  //c8包含n个初始值为t的元素

1.4 赋值和swap

容器赋值运算：assign只适用于顺序容器；array的类型包括元素数目，所以可能改变大小的赋值都不支持。

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

• 对于非array类型，赋值运算与左右两边容器的大小没有关系，如c1.size() == 1，c2.size() == 3，赋值完后两个size都为3。
• 而array类型与内置数组不同，它允许赋值，赋值号左右两边的类型必须相同(array的大小也属于类型)。由于右边运算对象的大小可能与左边运算对象的大小不同，因此array类型不支持assign，也不允许用值列表赋值，但是可以列表初始化。

  	array<int, 3> a1 = { 1, 2, 3 }
  	array<int, 3> a2 = { 0 };
  	a1 = a2;
  	a2 = { 0 }; // 错误：不能将一个花括号列表赋予数组
  

1）assign（仅顺序容器）

顺序容器定义了一个名为assign的成员，允许我们从一个不同但相容的类型赋值，或者从容器的一个子序列赋值。由于被旧元素替换，因此传递给assign的新迭代器不能指向调用assign的容器。

	list<string> names;
	names.push_back("123");
	vector<const char*> old_style;
	old_style.push_back("abc");
	list<string>::iterator names_it_begin = names.begin();
	list<string>::iterator names_it_end = names.end();

	// 此时的迭代器指向原来的容器
	for (list<string>::iterator it = names_it_begin; it != names_it_end; it++)
		cout << *it << endl; //输出：123

	//names = old_style; // 错误：容器类型不匹配
	names.assign(old_style.begin(), old_style.end());
	// 此时的迭代器指向新的容器
	for (list<string>::iterator it = names_it_begin; it != names_it_end; it++)
		cout << *it << endl; //输出：abc

2）swap

二、顺序容器

1.1 顺序容器的类型

除了array外，其他容器都有高效的内存管理；array大小固定，不支持添加删除等改变数组大小的操作，现代C++更应该使用array而不是内置数组；forward_list设计目标是与最好的手写单链表性能相当，因此没有size操作，因为size的保存和计算都会产生额外的开销。

1.2 确定使用哪种容器

选择容器遵从以下基本原则：

1. 通常使用vector是最好的选择，如果有足够的理由可以选择其他容器。
2. 需要随机访问，或在头部尾部插入删除，vector、deque。
3. 需要在容器中间插入删除，list、forward_list。
4. 如果程序只需在读取输入时才需要在中间位置插入元素，随后需要随机访问。
   a）先将插入元素放在vector的尾部，再调用sort函数重排容器。
   b）考虑插入阶段使用list，输入完成后将list中的内容拷贝到vector中。
5. 如果不确定使用哪种容器，可以在程序中只是用vector和list的公共操作：使用迭代器，不使用下标，这样在必要时可以切换。

1.3 容器的定义与初始化

	vector<int> vec1;    //默认初始化，vec1为空

	vector<int> vec2(vec1);  //使用vec1初始化vec2
	vector<int> vec3(vec1.begin(), vec1.end());  //使用vec1初始化vec2

	vector<int> vec4(10);    //10个值为0的元素
	vector<int> vec5(10, 4);  //10个值为4的元素
	vector<string> vec6(10, "hello");    //10个值为hello的元素

	vector<int> vec7 { 10 };    // 列表初始化vector，1个元素，值为10
	vector<string> vec8 { "qwe", "asd", "zxc" };  // 3个元素，分别是"qwe", "asd", "zxc"
	vector<string> vec9 = { "qwe", "asd", "zxc" };  // 等同与vec7

1.4 容器基本操作

在这里插入代码片

二、关联容器

三、容器适配器

四、容器总结