Item 1:小心地选择你的容器
scott meyers 著
刘未鹏 译
你知道C++提供了多种容器让你支配，但是你了解它们到底有多少种吗？为了使你能对自己能够做出的选择有一个清晰的概观，这儿提供了一个快速的回顾：
* standard STL sequence containers(标准的STL序列式容器)有vector,string,deque,list。
* standard STL associative containers(标准的STL关联式容器)有set,multiset,map,multimap。
* nonstandard sequence containers(非标准的序列式容器)有slist,rope。slist是单向链表而rope从本质上是一个heavy-duty string。在条款50你可以看到关于这些非标准的(但一般是有用的)容器的一个简要的概观。
* nonstandard associative containers(非标准的关联式容器)有hash_set,hash_multiset,hash_map, hash_multimap.我考察了这些被广泛使用的“hash-table-based”容器(条款25)。
* 以vector<char>来替代string。条款13描述了在什么样的情况下这样的替换可能是有意义的。
* 以vector来替代标准关联式容器。如条款23所表明的，有些时候vector在空间和时间上都要胜过关联式容器。
* standard non-STL containers(一些标准的非STL容器)有array,bitset,valarray,stack ,queue,priority-queue.因为这些是non-STL容器。在这本书里我对它们讲得很少，尽管条款16提到了一种arrays比STL容器好的情况。条款18解释了为什么bitset比vector<bool>要好。还有，值得记住的是array可以与STL算法合作无间，因为指针(译注：指原生指针)可被用来作为array的迭代器(译注：事实上，迭代器正是一种类似指针行为的concept)。
可选择的如此之多。在可以考虑的范围内仍有大量符合的结果，你得在它们之中选择。不幸的是，绝大多数有关STL的讨论在容器方面的笔墨相当贫乏，忽略了关于”如何选择最合适的容器”的问题的讨论。甚至连C++ Standard都介入了，并提供了以下在vector，deque，和list之间选择的原则：
vector,list,deque提供了不同的复杂性协定，应该依照使用。vector是缺省使用的序列式容器，list应该在频繁需要在序列式容器中部插值或删值的情况下使用(译注：这时如果使用vector会因为可能大量搬动元素或甚至重分配空间而效率低下)。而当绝大多数插入和删除操作都是在容器头部和尾部时就该用deque(译注：deque的头尾都可扩展的特点保证了这一点)。
如果你的主要考虑是算法复杂度，我想这是合理的建议，但是有太多其他的东西得考虑。
我们马上就来考察一些重要的容器相关的使算法完备的问题，但首先我需要向你介绍一种将STL容器分类的方法(这并没有象它应该的那样经常被讨论)。那就是“内存连续式”(contiguous-memory)容器和”基于节点的”(node-based)容器之间的区别。
“内存连续式”容器(也被称为array-based容器)把它的对象保存在动态分配的大块连续内存(chunk)中。每个chunk都含有一个以上的元素。如果插入(insert)一个新的元素或擦除(erase)现有的元素，则其它在同一个chunk中的元素都需要向前或向后移动，以便给新元素挪出空间(insert的时候)或是去占据被擦除元素原来所占的空间(erase的时候)。这种移动对性能(见条款5和14)和异常安全(不久我们就会看到)都会产生影响。标准“内存连续式”容器有vector,string,deque。非标准的rope也是“内存连续式”的。
node-based容器在一个动态分配的chunk(一块连续的内存)中有且仅有一个元素。insert或是erase只会影响指向节点的指针，而不会影响节点本身的内容，所以当insert或是erase时元素的值并不需要被移动。链表形式的容器如list,slist是node-based容器，所有的标准关联式容器也一样(典型的，它们在内部以平衡树的形式实现(译注：如红黑树))。非标准的哈希(hashed)容器在内部以可以有多种不同的node-based实现，正如你将在条款25所看到的。
我们将会讨论一些与容器的选择息息相关的问题。在讨论中，我忽略了non-STL-like的容器(arrays,bitsets.etc.)，因为这毕竟是一本关于STL的书。
* 你需要能在容器的任意位置插入新元素的能力吗？如果是的，你需要一个序列式容器，关联式容器不行。
* 你关心元素在容器中是如何排序的吗？如果不，哈希容器会是个有价值的选择。其它时候你应该避免哈希容器。
* 你的容器一定要是C++标准的一部分吗？如果是，请排除掉哈希式容器，slist和rope。
* 你需要哪一类迭代器？如果如果它们必须是随机存取迭代器，从技术上讲你就只能选择vector,deque,和string，但是你也可能会想要考虑rope(见条款50)。如果你需要双向迭代器，避免使用slist，和”以通常的方式实现”的哈希容器。
* 你不想现有元素在插入和擦除时被移动吗？如果是，请与“内存连续式”容器保持距离(条款5)。
* 容器中的数据布局需要与C兼容吗？如果是，你只能选择vector(条款16)
* 查找速度是一个重要的考虑因素吗？如果是，你得看看哈希容器(条款25)，sorted vector(经过排序的vector)(条款23)，和标准关联式容器
* 你介意底层容器采用引用记数(reference-counting)吗？如果介意的话，你得避开string,因为许多string的实现都采用了引用记数技术(条款13)。你也要避免使用rope，因为明确定义的rope是在引用记数的基础上实现的(条款50)。当然，你总要以某种方法来表现你的string吧，所以你可以考虑使用vector<char>。
* 在插入或擦除元素时你需要”原子事务处理”的语义吗？也就是说，你需要可靠的撤消或回退操作(roll back)吗？如果是，你可以使用node-based容器。更进一步，你需要对多个元素的插入移除也具有”原子事务处理”语义的容器吗(条款5)？如果是，你可以选择list,因为它是唯一提供多元素原子事务处理语义的容器。”原子事务处理”语义对异常安全(exception-safty)的代码特别重要(原子事务处理语义也能在“内存连续”式容器里实现，但是会有性能开销，代码也会变得不易懂，Sutter的《Exceptional C++》条款17提供了这方面更多的信息)(译注：当异常产生时必须保证进行到一半的操作能够回退，以保持数据的一致性)。
* 你想使迭代器、指针、引用的失效降到最低吗？如果是，你得使用node-based容器，因为在这类容器上插入和擦除从不会使迭代器、指针、引用失效(当然，除非它们刚好指向你要擦除(erase)的元素)。而在“内存连续式”容器上插入或擦除则可能使迭代器、指针、引用失效。
* 使用一个只要在尾部插入或擦除就不会使迭代器、指针、引用失效的，并具有随机存取迭代器的序列式容器会有帮助吗？这是一种非常特殊的情况，但如果这恰恰是你所遭遇的情况，deque就是你梦寐以求的容器(有趣的是，在deque的尾部插入新元素也可能使迭代器失效(译注：事实上，当插入元素导致deque的中控器重新配置时这种情况就会出现)，deque是唯一的可以在迭代器失效的同时指针和引用却不失效的标准STL容器)。
以上这些考虑还远远不是问题的尽头。比如，它们并没有将不同类型容器间的多样化的内存配置策略考虑进去(条款10和条款14讨论了这些策略的一些方面。尽管如此，以上所列举的已经足够让你相信：除非你对元素的排序、与标准的一致性、迭代器的能力(译注：指的是迭代器是input,output,forward,bidirectional还是random)、与C的内存布局的兼容性、查找速度、引用记数带来的行为反常、实现了原子事务所带来的安逸、在怎么样的情况下迭代器会失效，统统都没有兴趣，否则你会有更多的要去考虑，而不是简单的只考虑容器的操作的算法复杂度。当然，算法复杂度是重要的，然而这它只是整个故事的一小部分。
在容器方面，STL给了你许多选择。如果你跳出STL的圈子，甚至还会有更多的选择。在选择一个容器之前，一定要考虑你的选择的方方面面。一个“缺省的容器”？我不这样认为。
