仔细选择你的容器

刺骨的言语ヽ痛彻心扉 2022-09-03 01:18 93阅读 0赞

*  **标准STL序列容器**：vector、string、deque和list。
 *  **标准STL关联容器**：set、multiset、map和multimap。
 *  **非标准序列容器**slist和rope。slist是一个单向链表，rope本质上是一个重型字符串。（“rope”是一个重型“string”。明白了吗？）你可以找到一个关于这些非标准（但常见的）容器的概览在[条款50][50]。
 *  **非标准关联容器**hash\_set、hash\_multiset、hash\_map和hash\_multimap。我在[条款25][25]检验了这些可以广泛获得的基于hash表的容器和标准关联容器的不同点。
 *  **vector<char>可以作为string的替代品。**[条款13][13]描述了这个替代品可能会有意义的情况。
 *  **vector作为标准关联容器的替代品。**就像[条款23][23]所说的，有时候vector可以在时间和空间上都表现得比标准关联容器好。
 *  几种**标准非STL容器**，包括数组、bitset、valarray、stack、queue和priority\_queue。因为它们是非STL容器，所以在本书中关于它们我说得很少，虽然[条款16][16]提到了数组比STL容器更有优势的一种情况，而[条款18][18]揭示了为什么bitset可能比vector<bool>要好。值得注意的是，数组可以和STL算法配合，因为指针可以当作数组的迭代器使用。

这是所有的选项，而且可以考虑的范围和可以在它们之间的选择一样丰富。不走运的是，STL的大多数讨论只限于容器世界的一个很窄的视野，忽略了很多关于选择适当容器的问题。就连标准都介入了这个行动，提供了以下的在vector、deque和list之间作选择的指导方案：

> vector、list和deque提供给程序员不同的复杂度，因此应该这么用：vector是一种可以默认使用的序列类型，当很频繁地对序列中部进行插入和删除时应该用list，当大部分插入和删除发生在序列的头或尾时可以选择deque这种数据结构。

如果你主要关心的是算法复杂度，我想这个方案是有理由的建议，但需要关心更多东西。

现在，我们要检查一些可以补充算法复杂度的重要的容器相关问题，但首先我需要介绍一种STL容器的分类方法，它被讨论的次数并不像它应该的那样多。那是连续内存容器和基于节点的容器的区别。

**连续内存容器**（也叫做**基于数组的容器**）在一个或多个（动态分配）的内存块中保存它们的元素。如果一个新元素被查入或者已存元素被删除，其他在同一个内存块的元素就必须向上或者向下移动来为新元素提供空间或者填充原来被删除的元素所占的空间。这种移动影响了效率（参见[条款5][5]和[14][]）和异常安全（就像我们将会看到的）。标准的连续内存容器是vector、string和deque。非标准的rope也是连续内存容器。

**基于节点的容器**在每个内存块（动态分配）中只保存一个元素。容器元素的插入或删除只影响指向节点的指针，而不是节点自己的内容。所以当有东西插入或删除时，元素值不需要移动。表现为链表的容器——比如list和slist——是基于节点的，所有的标准关联容器也是（它们的典型实现是平衡树）。非标准的hash容器使用不同的基于节点的实现，就像我们将会在[条款25][25]中看到的。

利用这个不恰当的术语，我们已经准备好描述一些大多数关于在容器间选择的问题。在这个讨论中，我略过考虑非STL类容器（比如，数组、bitset等），因为毕竟这是本关于STL的书。

*  **你需要“可以在容器的任意位置插入一个新元素”的能力吗？**如果是，你需要序列容器，关联容器做不到。
 *  **你关心元素在容器中的顺序吗？**如果不，hash容器就是可行的选择。否则，你要避免使用hash容器。
 *  **必须使用标准C++中的容器吗？**如果是，就可以除去hash容器、slist和rope。
 *  **你需要哪一类迭代器**？如果必须是随机访问迭代器，在技术上你就只能限于vector、deque和string，但你也可能会考虑rope（关于rope的更多信息在[条款50][50]）。如果需要双向迭代器，你就用不了slist（参见[条款50][50]）和hash容器的一般实现（参见[条款25][25]）。
 *  **当插入或者删除数据时，是否非常在意容器内现有元素的移动？**如果是，你就必须放弃连续内存容器（参见[条款5][5]）。
 *  **容器中的数据的内存布局需要兼容C吗？**如果是，你就只能用vector（参见[条款16][16]）。
 *  **查找速度很重要吗？**如果是，你就应该看看hash容器（参见[条款25][25]），排序的vector（参见[条款23][23]）和标准的关联容器——大概是这个顺序。
 *  **你介意如果容器的底层使用了引用计数吗？**如果是，你就得避开string，因为很多string的实现是用引用计数（参见[条款13][13]）。你也不能用rope，因为权威的rope实现是基于引用计数的（参见[条款50][50]）。于是你得重新审核你的string，你可以考虑使用vector<char>。
 *  **你需要插入和删除的事务性（transactional）语义吗？**也就是说，你需要有可靠地回退（roll back）插入和删除的能力吗？如果是，你就需要使用基于节点的容器。如果你需要多元素插入（比如，以范围的方式——参见[条款5][5]）的事务性语义，你就应该选择list，因为list是唯一提供多元素插入事务性语义的标准容器。事务性语义对于有兴趣写异常安全代码的程序员来说非常重要。（事务性语义也可以在连续内存容器上实现，但会有一个性能开销，而且代码不那么直观。要了解这方面的知识，请参考Sutter的《Exceptional C++》的条款17 \[8\]。）
 *  **你要把迭代器、指针和引用的失效次数减到最少吗？**如果是，你就应该使用基于节点的容器，因为在这些容器上进行插入和删除不会使迭代器、指针和引用失效（除非它们指向你删除的元素）。一般来说，在连续内存容器上插入和删除会使所有指向容器的迭代器、指针和引用失效。
 *  **你需要具有有以下特性的序列容器吗：1）可以使用随机访问迭代器；2）只要没有删除而且插入只发生在容器结尾，指针和引用的数据就不会失效？**这个一个非常特殊的情况，但如果你遇到这种情况，deque就是你梦想的容器。（有趣的是，当插入只在容器结尾时，deque的迭代器也可能会失效，deque是唯一一个“在迭代器失效时不会使它的指针和引用失效”的标准STL容器。）

这些问题几乎不是事情的完结。比如，它们没有关注不同的容器类型使用不同的内存配置策略（[条款10][10]和[14][]讨论了这些策略的一些方面）。但是，它们已经足够是你信服了，除非你对元素顺序、标准的一致性、迭代器能力、内存布局和C的兼容性、查找速度、因为引用计数造成的行为不规则、事务性语义的轻松实现和迭代器失效的条件没兴趣，你得在容器操作的算法复杂度上花更多的考虑时间。当然这样的复杂度是重要的，但这离整个故事很远。

当面对容器时，STL给了你很多选项。如果你的视线超越了STL的范围，那就会有更多的选项。在选择一个容器前，要保证考虑了所有你的选项。一个“默认容器”？我不这么认为。

[50]: http://blog.csdn.net/AMin2001/archive/2003/12/23/item_50.html
[25]: http://blog.csdn.net/AMin2001/archive/2003/12/23/item_25.html
[13]: http://blog.csdn.net/AMin2001/archive/2003/12/23/item_13.html
[23]: http://blog.csdn.net/AMin2001/archive/2003/12/23/item_23.html
[16]: http://blog.csdn.net/AMin2001/archive/2003/12/23/item_16.html
[18]: http://blog.csdn.net/AMin2001/archive/2003/12/23/item_18.html
[5]: http://blog.csdn.net/AMin2001/archive/2003/12/23/item_05.html
[14]: http://blog.csdn.net/AMin2001/archive/2003/12/23/item_14.html
[10]: http://blog.csdn.net/AMin2001/archive/2003/12/23/item_10.html