Effecective STL: 容器 (条款1: 小心选择你的容器)
[缘起] 最近一直在学习STL，从《C++标准库（The C++ Standard Library）》到《STL 源码剖析》再到《泛型编程与STL（Generic Programming and the STL）》，自认为对STL有一定认识。为了让自己有进一步的提高，试着翻译这部《Effective STL》，错误再所难免，欢迎大家批评指正，我的email是smart_ttc@yahoo.com.cn， 有任何想法或错误请发信给我。在翻译过程中，我会根据自己的理解，对原文有一些增删，如想要原汁原味，建议看原版（最好的阅读方式）。我会陆续把所有50个条款翻译出来，谢谢大家支持。
[译者按] Scott Meyers, C++软件开发的最权威人士，已出版的作品有《Effective C++》、《Move Effective C++》和《Effective C++ CD》。他曾是《C++ Report》的专栏作家，是《C/C++ Users Journal》和《Dr. Dobb’s Journal》的撰稿人，还是一个客户遍及世界各地的顾问。他是NumeriX LLC 和InfoCruiser Inc.的顾问委员会成员之一，拥有布朗大学计算机科学的博士学位。《Effective STL》—— 改善标准模板库使用的50种特殊方法是其最新的作品。
毫无疑问，STL有迭代器（iterators）、算法（algorithms），还有函数对象（function objects），但对大多数C++程序员来说，STL就是容器（containers）。它们比数组更强大更灵活，可以动态的增长和收缩（尺寸），能自己管理内存，知道自己容纳了多少对象，隔离其所支持操作的算法复杂性（the algorithm complexity of the operations），还有更多更多。它们如此流行是很容易理解的。它们就是比它们的竞争者好，不管其竞争者是来自其他库中的容器还是你自己写的容器类型。STL容器不是刚刚好（just good），而是确实是好（really good）——有点强词夺理（J）。
本章的内容主要是一些应用于所有STL容器的指导方针（guidelines）。后面的章节则会关心特定的容器类型。这里关注的主题包括面对给定的约束条件（constraints）选择合适的容器；避免造成这样一种错觉，就是为一种容器类型所写的代码可能也适用于其它容器类型；复制操作的重要性；当把指针或auto_ptrs保存在容器内时难度的提高；插入与擦除；使用自定义的分配器（allocators）你能够完成什么和不能够完成什么；得到最佳效率的技巧；以及在多线程环境下使用容器的注意事项。
恩，有好多东东，但是请不要担心。所有这些都被分成一小块一小块的条目，循条而行，你肯定可以捡到（pick up）几条原则应用到你所写的代码中去。
条款1: 小心地选择你的容器 （Choose your containers with care.）
你知道在C++中，你可以自由自在的处置多种容器，但是你知道这些容器到底是如何多种多样的呢？为了确保你没有忽视任何可能的选择，这里是一个简短的回顾。
n 标准STL序列式容器（sequence containers），vector, string, deque, and list.
n 标准STL关联式容器（associative containers），set, multiset, map, and multimap.
n 非标准序列式容器（nonstandard sequence containers） slist 和 rope。slist 是一个单向链表，rope从本质上讲是一个重型的string。（一个”rope”就是一个重型”string”。明白了吗？）（有一个比喻，可以更好的理解rope与string之间的区别，rope是粗绳，string是细线。） 你可以在第50条找到这些非标准容器的简短概览（这些容器一般来讲都是可用的）。（译注：这里所说的“一般来讲都是可用的”是指大多数stl标准库都会实现这些非标准容器。）
n 非标准关联式容器（nonstandard associative containers）hash_set, hash_multiset, hash_map, hash_multimap。我会在条款25仔细讲解这些符合标准关联式容器的基于散列表的高度可用的各种类型（容器）。
n String 的替代物vector<char>。条款13描述了合理替换的条件。
n vector 作为标准关联式容器的替代物。在条款13中你可以看到，在时间和空间方面vector有时比标准关联式容器要做得好。
n 几种标准的非STL容器，包括arrays, bitset, valarray, stack, queue, 和priority_queue。因为这些是非STL容器，所以除了在条款16提到有一种情况使用数组要优于STL容器以及在条款18解释为什么bitset可能要好于vector<bool>，本书几乎没有讨论它们。同样，记住数组可以用于STL算法（algorithms），因为指针可以被当作数组的iterators。
这就是所有的选择了，考虑了各种情况，你选择容器时就应该从它们当中抽取。不幸的是，对大多数STL的讨论仅限于容器世界（world of containers）极小的一部分，而忽略了许多关于选择最合适容器的主题。即使标准本身，也只提供了下列在vector, deque和list中进行选择的指导：
vector, list 和 deque 为程序员提供不同的复杂度平衡，应权衡使用。vector 是序列式容器，作为缺省使用。List应当用于频繁在序列中部进行插入和删除操作的情况。当大多数插入和删除操作发生在序列的头和尾时请选择deque。
如果你主要的关心是算法复杂性，我认为这个章程（constitutes）是合理的建议，但还有更多的东西需要关心。
现在，我们来考虑重要的和容器相关的主题，这个主题能更好的说明算法复杂性，但是首先我要介绍一种容器分类的方法，这种方法应当被经常的讨论，但是却没有（真理总是掌握在少数人手中J）。这就是连续内存容器（contiguous-memory containers）与基于节点容器（node-based containers）之间的区别。
连续内存容器（contiguous-memory containers）（也叫做基于数组的容器（array-based containers））在一个或多个连续的内存块（动态分配的）存贮它们的元素，任一内存块容纳多于一个的容器元素。如果一个新元素被插入（inserted）或一个存在的元素被擦除（erased），在同一内存块中其它元素必须搬移为新元素提供空间或回收已擦除元素所占用的空间。这种移动会影响性能（见条款5和14）和异常安全（不久我们就会看到）。标准的连续内存容器（contiguous-memory containers）是vector，string和deque。非标准的rope也是一种连续内存容器（contiguous-memory containers）。
基于节点的容器（node-based containers）在每一个内存块（动态分配的）内只存贮一个单独元素。插入和擦除（erasure）只影响指向节点的指针，不影响节点本身的内容，所以执行插入或擦除操作时元素值不需要移动（意思是不需要移动内存块）。表示链表的容器如list和slist，以及所有的关联式容器都是基于节点（node-based）的。（它们一般都用平衡树实现。）非标准的散列容器（hashed containers）使用各种基于节点（node-based）的实现，请见条款25。
使用这种不太常用的（out of the way）术语，我们开始提出一些在选择容器时最相关的问题。在以下讨论中，我会忽略非类STL（non-STL-like）的容器（例如，arrays, bitsets等等），毕竟，这是一本关于STL的书。
n 你需要在容器中任意位置插入新元素的能力吗？如果是，你需要的是序列式容器，关联式容器没有这种功能。
n 你关心容器内的元素如何排序吗？如果不是，散列容器（hashed container）是一种可能的选择。否则，避免使用散列容器（hashed container）。
n 容器必须是标准C++的一部分吗？如果是，不要考虑散列容器（hashed containers），slist以及rope。
n 你需要哪种类型的迭代器呢？如果必须是random access iterators，从技术上讲，你只能使用vector, deque,和string，当然，你可能也想用rope。（关于rope更多的信息见条款50。）如果需要的是双向的迭代器，你必须避免使用slist（见条款50）以及散列容器（hashed container）的一般实现品（用普通方法实现的）（见条款25）。
n 当进行插入或擦除操作时，避免移动容器内已经存在的元素重要吗？如果是，那就请离连续内存容器远点（contiguous-memory containers）（见条款5）。
n 容器内的数据需要与C保持布局兼容（layout-compatible）吗？如果是，你只能使用vectors（见条款16）。
n 查找速度是个关键考虑因素吗？如果是，那你需要去看散列容器（hashed container）（见条款25），排序的vectors（见条款23），还有标准关联容器——按此顺序选择。
n 你介意底层容器使用引用计数（reference counting）吗？如果是，那你需要好好驾驭string，这是因为许多string实现是基于引用计数（reference-counted）的（见条款13）。你也要避免使用rope，因为确定的rope实现是基于引用计数的（见条款50）。你必须描绘自己的strings，当然，你应当考虑vector<char>。
n 你需要插入和擦除的事务语义（transactional semantics）吗？就是说，你需要可信赖的回滚（roll back）插入和擦除操作的能力吗？如果是，你需要使用基于节点的容器。如果你需要多元素插入的事务语义（transactional semantics）（例如：区间形式——见条款5），你应当选择list，这是因为list是仅有的提供多元素插入事务语义的标准容器。事务语义（transactional semantics）对有兴趣写异常安全代码的程序员尤其重要。（事务语义（transactional semantics）也可以用连续内存容器达到，但是会有性能代价，代码也不简单。要了解更多，请看Sutter’s Exceptional C++[8]的条款17。）（译注：Exceptional C++已经由电力出版社出版中文版。）
n 你需要使iterator，pointer以及reference的失效最少化吗？如果是，你应当使用基于节点的容器，因为在这些容器中插入和擦除永远不会使iterators，pointers或references失效（除非它们指向你正在擦除的元素）。一般来讲，在连续内存容器上插入或擦除可能导致容器内任何存在的iterators, pointers以及references失效。
n 有这样一种序列式容器，它的迭代器类型是random access iterator，只要没有擦除操作发生并且总是在容器的尾部插入新元素，（迭代器中）指向数据的指针和引用不会失效，拥有这样的容器有帮助吗？这是一种非常特殊的情况，但是如果这是你的情况，deque就是你梦想中的容器。（有趣的是，当在deque的尾部插入元素时其迭代器可能会失效。deque是仅有的迭代器可能会失效而指针和引用却不会失效的标准STL容器。）
这些问题几乎不可能是所有事情的结束。例如，它们没有考虑不同容器类型所采用的各种各样的内存分配策略。（条款10和条款14讨论了这些策略的某些方面。）还有，除非你对元素排序，标准一致性，迭代器兼容，与C的布局兼容，查找速度，由于引用计数而导致的行为不规则，事务语义的轻松实现，或迭代器失效的条件没兴趣，它们应当足够使你确信，你并不仅仅只要考虑容器操作的算法复杂性，而是比这多的多。当然，这种复杂性很重要，但它只是所有问题中的一小部分。
在容器方面，STL给了你许多选择。如果你不局限于STL，甚至有更多的选择。在选择一种容器之前，确保考虑了所有的选择。“缺省容器”吗？我不认为是这样。
