undefined

1. string

string 是模版 basic_string 对于char 类型的特化，可以认为是一个只存放字符 char 类型数据的容器。string 一般并不被认为是一个C++的容器，但是和容器有很多共同点

对于对外暴露的接口，一般不建议在接口中使用 const string&，除非确知调用者已经持有 string，如果函数里不对字符串做复杂处理的话，使用 const char* 可以避免在调用者只有 C 字符串时编译器自动构造 string，这种额外的构造和析构代码并不低。如果实现较为复杂、希望使用 string 的成员函数的话，那应该考虑下面的策略：
1. 如果如果不修改字符串的内容，使用 const string& 或 C++17 的 string_view 作为参数类型。后者是最理想的情况，因为即使在只有 C 字符串的情况，也不会引发不必要的内存复制
2. 如果需要在函数内修改字符串内容、但不影响调用者的该字符串，使用 string 作为参数类型(自动拷贝)
3. 如果需要改变调用者的字符串内容，使用 string& 作为参数类型(通常不推荐)

2. vector

vector 底层是一个动态数组，他维护了一段连续的动态内存空间，然后有三个成员变量分别保存开始位置、当前已使用位置、申请的动态内存的最后一个位置的下一个位置。每当当前所申请的动态内存已经用完时，他会按照原来空间大小的两倍重新申请内存块，并把原来的元素都拷贝过去。

特别注意：当 push_back、insert、reserve、resize 等函数导致内存重分配时，或当 insert、erase 导致元素位置移动时，vector 会试图把元素“移动”到新的区域。vector 通常保证强异常安全性，如果元素类型没有提供一个保证不抛出异常的移动构造函数，vector 通常会使用拷贝构造函数。解决办法：我们应该定义移动构造函数，并标其为 noexcept，或只在容器中放置对象的智能指针。

特别注意：C++11提供的 emplace… 系列函数是为了提升容器的性能而设计的，将元素构造在指定位置。如果使用 push_back 会额外生成临时对象，多一次(移动或拷贝)构造和析构。

vector 的一个主要缺陷是大小增长时导致的元素移动。如果可能，尽早使用 reserve 函数为 vector 保留所需的内存。

什么情况下 vector 的迭代器会失效？ 第一是当调用 erase 函数使用迭代器删除元素时，当前位置会被后面的元素覆盖，会导致该指定迭代器失效，不过可以通过 erase 的返回值重新得到当前位置的正确迭代器。第二是在 vector 需要新申请内存的时候，比如扩容等，因为内存有了变动，此时就需要重新获得迭代器。

vector如何快速释放内存？ 使用 reserver、resize、clear 这些都不行，reserver 只有在传入大小比原有内存大的时候才会重新申请内存，否则不进行任何操作。resize 或者 clear 只会对当前已保存在容器中的所有元素进行析构，但对容器本身所在的内存空间是不会进行释放的。1. 我们可以使用 swap 函数，使用一个空的 vector 与当前 vector 进行交换，这样当前 vector 的内存空间等于被释放了，而这个临时的空的 vector 一般在代码运行结束后，会自动调用析构函数释放内存空间。 2. 在 c++11 后增加了 shrink_to_fit 函数，可以释放掉未使用的内存。可以先调用 clear 把所有元素清空，这样 vector 的空间都变成了未使用的，然后调用 shrink_to_fit 即可把未使用的内存释放掉，相当于释放了 vector 的内存。

3. deque

双端队列，主要用来满足下面这个需求：

容器不仅可以从尾部自由的添加和删除元素，也可以从头部自由的添加和删除。
如果只从头、尾两个位置对 deque 进行增删操作的话，容器里的对象永远不需要移动。
容器里的元素只是部分连续的，因而没法提供 data 成员函数
由于元素的存储大部分仍然连续，它的遍历性能是比较高的
由于每一段存储大小相等，deque 支持使用下标访问容器元素，大致相当于 index[i / chunk_size][ i % chunk_size]
deque对比vector，提供 push_front、emplace_front、pop_front成员函数，不提供 data、capacity、reserve 成员函数

4. list

双向链表。注意：因为某些标准算法在 list 上会导致问题，list 提供了成员函数作为替代，包括 merge、remove、remove_if、reverse、sort、unique

1
2
3

std::list<int> lst{1,2,3};
sort(lst.begin(), lst.end()); // 编译出错 
lst.sort(); // 正常

5. forward_list

单向链表。在元素大小较小的情况下，forward_list 能节约的内存是非常可观的

6. queue

类容器，不是完整的实现，依赖于某个现有的容器，因而被称为容器适配器。queue 缺省用 deque 来实现。

队列：先进先出的数据结构

7. stack

类容器，容器适配器。stack 缺省用 deque 来实现

栈：后进先出的数据结构

问题

stack(queue)的pop 函数返回类型为 void，而不是返回容器的 top(front) 成员?

为了保证强异常安全性，C++98还没有移动构造的概念，如果要返回成员，必须要调用拷贝构造函数，这时就有可能出现异常，导致构造失败，所以没必要返回成员。拷贝不影响旧的容器，移动会影响到旧的容器。

8. priority_queue

优先级队列，容器适配器

使用缺省的 less 作为其 compare 模版参数时，最大的数值会出现在容器的顶部。如果需要最小的数值出现在容器顶部，则可以传递 greater 作为 compare 模版参数

9. 关联容器

关联容器有 set(集合)、map(映射)、multiset(多重集)、multimap(多重映射)。关联容器是一种有序的容器。名字带 multi 的允许键重复，不带的不允许键重复。set和multiset 只能用来存放键，而map和multimap 则存放一个个键值对

关联容器都有 find、lower_bound、upper_bound 等查找函数，结果是一个迭代器：

find(k) 可以找到任何一个等价于查找键 K 的元素 (!(x < k || k < x))
lower_bound(k) 找到第一个不小于查找键 K 的元素 (!(x < k))
upper_bound(k) 找到第一个大于查找键 K 的元素 (k < x) 
需要在 multimap 中精确查找满足某个键的区间的话，建议使用 equal_range, 可以一次性取的上下界(半开半闭)

10.无序关联容器

unordered_set、unordered_map、unordered_multiset、unordered_multimap 他们是无序的，这些容器不要求提供一个排序的函数对象，而要求一个可以计算哈希值的函数对象。可以在声明对象时手动提供这样一个函数对象类型，但常见情况是使用标准的 hash 函数对象及其特化

无序关联容器的实现使用哈希表，可以达到平均 O(1)，但这取决于是否使用了一个好的哈希函数：在哈希函数选择不当的情况下，无序关联容器的插入、删除、查找性能可能成为最差情况 O(n)

11. array

如果数组较大的话，应该考虑 vector。vector 有最大的灵活性和不错的性能
对于字符串数组，应该考虑 string
如果数组大小固定(C 的数组在 C++ 里本来就是大小固定的) 并且较小的话，应该考虑 array。array 保留了 C 数组在栈上分配的特点，同时提供了 begin、end、size 等通用成员函数