第一章容器

01-谨慎选择容器类型

回顾有哪些容器

标准STL序列容器：vector、string、deque 和 list。

标准STL关联容器：set、multiset、map 和 multimap。

非标准序列容器 slist 和 rope。
slist 是一个单向链表，rope 本质上是一”重型”string。可以在第 50 条中找到对这些非标准的容器的一个简要介绍。

非标准的关联容器 hash_set、hash_multiset、hash_map 和 hash_multimap。在第 25 条中，分析了这些基于哈希表的、标准关联容器的变体（它们通常是广泛可用的）。 vector作为 string 的替代。第 13 条讲述了在何种条件下这种替代是有意义的。 vector 作为标准关联容器的替代。正如第 23 条中所阐明的，有时 vector 在运行时

几种标准的非 STL 容器，包括数组、bitset、valarray、stack、queue 和 priority_queue。因为它们不是 STL 容器，所以在本书中很少提及，仅在第 16 条中提到了一种”数组优于 STL 容器”的情形，以及在第 18 条中解释了为什么 bitset 比 vector要好。值得记住的是，数组也可以被用于 STL 算法，因为指针可以被用作数组的迭代器。

容器的选择

vector、list、deque提供了不同的复杂性，使用时要对此做出权衡。vector是默认使应使用的序列类型；当需要频繁在序列中间做插入和删除操作时，应使用list;当大多数插入和删除操作发生在序列的头部和尾部时，应该考虑使用deque。

容器的另一种分类方式

连续内存容器和基于节点的容器

连续内存容器：或称为基于数组的容器，它将元素放在一块或多块内存中，每块内存中存有多个元素。当有新元素插入或已有的元素被删除时，同一内存块中的其他元素要向前或向后移动，为新元素让出空间，或者填充被删除元素所遗留下的空隙。这种移动会影响到效率和异常安全性。标准的连续内存容器有vector、string、deque。非标准的rope也是一个连续内存容器。

基于节点的容器：在每一个内存块中只存放一个元素。容器中元素的插入或者删除只会影响到指向节点的指针，而不影响节点本身的内容，所以当有插入或删除操作时，袁术的值不需要移动。表示链表的容器，如list和slist都是基于节点的；所有标准的关联容器也是如此。非标准的哈希容器使用不同的基于节点的实现（详见第25条）

选择容器的参考

1、需要容器在任意位置插入新元素？选择序列容器，而不是关联容器
2、关心容器中的元素是如何排序的？避免哈希容器
3、选择的容器必须是标准C++的一部分？排除哈希容器、slist、rope
4、需要那种类型的迭代器？如果是随机访问迭代器，限定vector、deque和string。如果是双向迭代器，避免slist(单向链表)以及哈希容器的一个常见实现
5、当发生元素的插入或删除操作时，避免移动容器中原来的元素是重要的？避免连续内存容器
6、容器中数据的布局需要和C兼容？只能选择vector
7、元素的查找速度比较关键？考虑哈希容器、排序的vector(见23条)和标准关联容器
8、介意容器内部使用了引用计数？避免使用string和rope，考虑使用vector<\char>；注意！在C++11之后，string已经禁用了COW+引用计数了，而是使用的SSD(移动语义的出现导致的变革)；现代C++容器基本都已经没有使用引用计数。
9、对于批量插入和删除操作，需要事务语义？也就是说在插入或删除操作失败时，需要回滚到操作之前的数据？使用基于节点的容器。如果对多个元素的插入操作，需要事务语义，选择list，在标准容器中，只有list对多个元素的插入操作提供了事务语义。对于希望编写异常安全代码的程序员，事务语义显得尤为重要。（使用连续内存的容器也可以获得事务语义，但是要付出性能上的代价，代码也不那么直截了当。参考Sutter的Exceptional C++[8]中的第17条）
10、需要使迭代器、指针和引用变为无效的次数最少？使用基于节点的容器，因为这类容器的插入和删除操作从来不会使迭代器、指针和引用变为无效（除非指向一个正在删除的元素）。而针对连续内存容器的插入和删除操作一般会使指向该容器的迭代器、指针和引用变为无效。
11、序列容器的迭代器是随机访问类型，而且只要没有删除操作发生，且插入操作只发生在容器的末尾，则指向数据的指针和引用就不会变为无效？使用deque,且deque是唯一的迭代器可能会变为无效但指针和引用不会变为无效的STL标准容器。