C++容器
通用特性
所有容器都具有的一个基本特性：它保存元素采用的是“值”（value）语义。
也就是说，容器里存储的是元素的拷贝、副本，而不是引用。
代价：开销大，性能降低。
解决方法：
1. 尽量为元素实现转移构造和转移赋值函数
在加入容器的时候使用 std::move() 来“转移”，减少元素复制的成本：
Point p; // 一个拷贝成本很高的对象
v.push_back(p); // 存储对象，拷贝构造，成本很高
v.push_back(std::move(p)); // 定义转移构造后就可以转移存储，降低成本
**2. 使用 C++11 为容器新增加的 emplace 操作函数 **
它可以“就地”构造元素，免去了构造后再拷贝、转移的成本，不但高效，而且用起来也很方便：
v.emplace_back(...); // 直接在容器里构造元素，不需要拷贝或者转移
3、容器里存放元素的指针，间接保存元素
缺点：不能利用容器自动销毁元素的特性。得手动管理元素的生命周期，容易出错，可能造成内存泄漏。
具体特性
一种分类是依据元素的访问方式，分成顺序容器、有序容器和无序容器三大类别
顺序容器
顺序容器就是数据结构里的线性表，一共有 5 种：array、vector、deque、list、forward_list。
按照存储结构，这 5 种容器分成（数组和链表）结构
? 1. 连续存储的数组：array、vector 和 deque；
? 2. 指针结构的链表：list 和 forward_list。
array 和 vector 直接对应 C 的内置数组，内存布局与 C 完全兼容，所以是开销最低、速度最快的容器。
区别：能否动态增长。array 是静态数组，大小在初始化的时候就固定；vector 是动态数组，虽然初始化的时候设定了大小，但可以在后面随需增长，容纳任意数量的元素。
array<int, 2> arr; // 初始一个array，长度是2
assert(arr.size() == 2); // 静态数组的长度总是2
vector<int> v(2); // 初始一个vector，长度是2
for(int i = 0; i < 10; i++) {
v.emplace_back(i); // 追加多个元素
}
assert(v.size() == 12); // 长度动态增长到12
deque和vector的差异：
共同点：都是动态增长的数组，连续存储的，在中间插入删除效率较低。
不同点：deque是可以在两端高效率插入删除元素的。vector只能用push_back在末端追加元素。
deque<int> d; // 初始化一个deque，长度是0
d.emplace_back(9); // 末端添加一个元素
d.emplace_front(1); // 前端添加一个元素
assert(d.size() == 2); // 长度动态增长到2
链表的缺点是查找效率低，只能沿着指针顺序访问。
list和forward_list区别：
? list 是双向链表，可以向前或者向后遍历，而 forward_list，顾名思义，是单向链表，只能向前遍历，查找效率就更低了。
链表结构和数组结构的比较：
? 链表存储成本略高，因为必须要为每个元素附加一个或者两个的指针，指向链表的前后节点。
? 链表的缺点是查找效率低，只能沿着指针顺序访问。
? 数组中间插入删除效率较低。
vector/deque 和 list/forward_list 都可以动态增长来容纳更多的元素。
vector每次都是2倍扩容，短时间内插入大量数据的时候效果较好。代价是每次扩容的时候进行元素的拷贝或者移动代价成本很大，尽量预估好空间，使用reserve提前分配足够的空间。
deque\list的扩容按指定字节数去扩容。
首选容器 array 和 vector
速度最快、开销最低，数组的形式也令它们最容易使用，搭配算法也可以实现快速的排序和查找。
deque、list 和 forward_list 则适合对插入删除性能比较敏感的场合，如果还很在意空间开销，那就只能选择非链表的 deque 了
有序容器
特点：顺序容器是按插入顺序，访问元素按照最初插入的顺序。
有序容器则不同，它的元素在插入容器后就被按照某种规则自动排序，所以是“有序”的。
结构：树结构，通常是红黑树——有着最好查找性能的二叉树。
标准库里一共有四种有序容器：set/multiset 和 map/multimap。set 是集合，map 是关联数组（在其他语言里也叫“字典”）。
有 multi 前缀的容器表示可以容纳重复的 key，也可以认为只有两种有序容器。
如何正确理解有序？
也就是说，容器是如何判断两个元素的“先后次序”
有序容器与顺序容器的另一个根本区别，在定义容器的时候必须要指定 key 的比较函数
只不过这个函数通常是默认的 less，表示小于关系，不用特意写出来：
template<
class T // 模板参数只有一个元素类型
> class vector; // vector
template<
class Key, // 模板参数是key类型，即元素类型
class Compare = std::less<Key> // 比较函数
> class set; // 集合
template<
class Key, // 第一个模板参数是key类型
class T, // 第二个模板参数是元素类型
class Compare = std::less<Key> // 比较函数
> class map; // 关联数组
除了基本类型int , string等，自定义的类型是没有默认的比较函数的，要作为容器的key就有点麻烦。
解决这个问题有两种办法：一个是重载“<”，另一个是自定义模板参数。
比如说我们有一个 Point 类，它是没有大小概念的，但只要给它重载“<”操作符，就可以放进有序容器里了：
bool operator<(const Point& a, const Point& b)
{
return a.x < b.x; // 自定义比较运算
}
set<Point> s; // 现在就可以正确地放入有序容器
s.emplace(7);
s.emplace(3);
另一种方式是编写专门的函数对象或者 lambda 表达式，然后在容器的模板参数里指定。这种方式更灵活，而且可以实现任意的排序准则：
set<int> s = {7, 3, 9}; // 定义集合并初始化3个元素
for(auto& x : s) { // 范围循环输出元素
cout << x << ","; // 从小到大排序，3,7,9
}
auto comp = [](auto a, auto b) // 定义一个lambda，用来比较大小
{
return a > b; // 定义大于关系
};
set<int, decltype(comp)> gs(comp) // 使用decltype得到lambda的类型
std::copy(begin(s), end(s), // 拷贝算法，拷贝数据
inserter(gs, gs.end())); // 使用插入迭代器
for(auto& x : gs) { // 范围循环输出元素
cout << x << ","; // 从大到小排序，9,7,3
}
有序容器使用法则：
集合关系就用 set，关联数组就用 map。
注意：，因为有序容器在插入的时候会自动排序，所以就有隐含的插入排序成本，当数据量很大的时候，内部的位置查找、树旋转成本可能会比较高。
需要实时插入排序，那么选择 set/map 是没问题的。如果是非实时，那么最好还是用 vector，全部数据插入完成后再一次性排序，效果肯定会更好。
无序容器unordered（无序）
无序容器也有四种，名字里也有 set 和 map，只是加上了 unordered（无序）前缀，分别是 unordered_set/unordered_multiset、unordered_map/unordered_multimap。
用法与有序容器几乎一样。
区别：内部数据结构不同。
内部数据结构：它不是红黑树，而是散列表（也叫哈希表，hash table）。
例子：
using map_type = // 类型别名
unordered_map<int, string>; // 使用无序关联数组
map_type dict; // 定义一个无序关联数组
dict[1] = "one"; // 添加三个元素
dict.emplace(2, "two");
dict[10] = "ten";
for(auto& x : dict) { // 遍历输出
cout << x.first << "=>" // 顺序不确定
<< x.second << ","; // 既不是插入顺序，也不是大小序
}
无序容器对key的要求比有序容器”苛刻“点：
第一个是因为散列表的要求，只有计算 hash 值才能放入散列表；
第二个则是因为 hash 值可能会冲突，所以当 hash 值相同时，就要比较真正的 key 值。
举例：
template<
class Key, // 第一个模板参数是key类型
class T, // 第二个模板参数是元素类型
class Hash = std::hash<Key>, // 计算散列值的函数对象
class KeyEqual = std::equal_to<Key> // 相等比较函数
> class unordered_map;
要把key放入容器必须实现 一下这两个函数：
“==”函数比较简单，可以用与“<”函数类似的方式，通过重载操作符来实现：
bool operator==(const Point& a, const Point& b)
{
return a.x == b.x; // 自定义相等比较运算
}
散列函数就略麻烦一点，你可以用函数对象或者 lambda 表达式实现，内部最好调用标准的 std::hash 函数对象，而不要自己直接计算，否则很容易造成 hash 冲突：
auto hasher = [](const auto& p) // 定义一个lambda表达式
{
return std::hash<int>()(p.x); // 调用标准hash函数对象计算
};
把一个自定义类型放入无序容器中时，容器必须支持相等函数和散列函数。
unordered_set<Point, decltype(hasher)> s(10, hasher);
s.emplace(7);
s.emplace(3);
有序和无序容器的选择：
如果只想要单纯的集合、字典，没有排序需求，就应该用无序容器，没有比较排序的成本，它的速度就会非常快。
) // 定义一个lambda表达式
{
return std::hash()(p.x); // 调用标准hash函数对象计算
};
把一个自定义类型放入无序容器中时，容器必须支持**相等函数和散列函数。**
```c++
unordered_set<Point, decltype(hasher)> s(10, hasher);
s.emplace(7);
s.emplace(3);
有序和无序容器的选择：
如果只想要单纯的集合、字典，没有排序需求，就应该用无序容器，没有比较排序的成本，它的速度就会非常快。
实战小技巧：多用类型别名，不要写死容器定义。 因为大部分接口相同，所以只要变动别名定义，就能够随意改换不同的容器。