C ++ 11容器/适配器属性的实用总结/参考？ [英] Practical summary/reference of C++11 containers/adapters properties?
问题描述
我正在寻找各种C ++ 11标准容器和容器适配器（可选还包括boost / Qt）的重要属性的全面总结/参考，但是由这些属性索引的比通常的每个容器文档（下面更多的）。
I'm looking for a comprehensive summary/reference of important properties of the various C++11 standard containers and container adapters (optionally also including boost/Qt), but indexed by those properties rather than the usual per container documentation (more on that below).
我想到的属性包括，从我的头顶部：
The properties I have in mind include, from the top of my head:
- 插入功能（前/后/任意）。
- 删除功能（前/后/任意）
- 访问功能（前/后/单向/双向遍历/随机访问）。
- 上述操作的复杂性和迭代器无效规则。 >
- 唯一性有序？联想？相邻存储？提前预订？
- Insertion capabilities (front / back / arbitrary).
- Removal capabilities (front / back / arbitrary).
- Access capabilities (front / back / uni/bi-directional traversal / random access).
- Complexity of the aforementioned operations, and iterator invalidation rules.
- Uniqueness? Ordered? Associative? Contiguous storage? Reservation ahead of time?
我可能已经忘记了一些，在这种情况下，请不要犹豫，评论/编辑。 sup>
I may have forgotten some in which case don't hesitate to comment/edit.
目标是使用该文档作为帮助，为正确的工作选择合适的容器/适配器，而无需通过各种单独的文档和每一次（我有一个可怕的记忆）。
The goal is to use that document as an aid to choose the right container/adapter for the right job, without having to wade through the various individual documentations over and over every time (I have a terrible memory).
理想情况下，它应该由属性和容器类型（例如，table-like）进行索引，制作以及基本约束的快速参考。但是，真正的每个属性索引对我来说最重要，因为这是在文档中搜索最痛苦的。
Ideally it should be indexed both by property and by container type (eg. table-like) to allow for decision-making as well as for quick reference of the basic constraints. But really the per property indexes are the most important for me since this is the most painful to search in the documentation.
如果没有人已经产生这样一个文件，但是我的Search-fu在这个失败了我。
I'd be very surprised if nobody had already produced such a document, but my Search-fu is failing me on this one.
注意：我不是要求你总结一下这些信息（如果我真的需要，我会自己做，在这种情况下，我会在这里发布结果），但只有当你碰巧知道一个符合这些要求的现有文档。某些喜欢这个是一个很好的开始，但是你可以看到它仍然缺少很多我想要的信息仅限于成员函数。
NOTE: I'm not asking for you to summarize all these informations (I'll do that myself if I really have to, in which case I'll post the result here) but only if you happen to know an existing document that fits those requirements. Something like this is a good start but as you can see it still lacks many of the information I'd like to have since it's restricted to member functions.
感谢您的关注。
推荐答案
我不知道一个文档提供了您需要的一切，但大部分文档已经在某个地方编目。
I am not aware of a single document that provides everything you need, but most of it has been catalogued somewhere.
- This reference site has a large table with all the member functions of all the containers
- This SO question has a large table of the complexity guarantees.
- This SO question gives you a decision tree to choose between containers.
容器成员函数的复杂性要求并不难记住，因为只有4个类别：（摊销） O（1）， O（log N）， O（N）和 O（N log N）（成员函数 std :: list :: sort（），这真的跨越了标准库的算法域），所以如果你想要制作一个4色编码版本的cpp参考容器表。
The complexity requirements for container member functions are not too hard to memorize since there are only 4 categories: (amortized) O(1), O(log N), O(N), and O(N log N) (member function std::list::sort() which really crosses into the algorithms domain of the Standard Library) so if you want you could make a 4-color-coded version of the cpp reference container table.
选择正确的容器可以像往常一样使用 std :: vector 除非您的分析器指示瓶颈。达到这一点后，您必须在空间/时间复杂性之间作出艰难的权衡， 数据局部性 ，易于查找vs易于插入/修改，与额外的不变量（排序，唯一性， 迭代器无效规则 ）。
Choosing the right container can be as simple as always using std::vector unless your profiler indicates a bottleneck. After you reach that point, you have to make hard tradeoffs between space / time complexity, data locality, ease of lookup vs ease of insertion / modification, vs extra invariants (sortedness, uniqueness, iterator invalidation rules).
最难的部分是您必须平衡您的容器（空间要求）与您使用的算法（时间要求）。容器可以维护不变量（例如 std :: map 在其键上排序），其他容器只能使用算法模拟（例如 std :: vector 与 std :: sort ，但没有相同的插入复杂性）。所以在完成容器表之后，请确保为算法做类似的操作！
The hardest part is that you have to balance your containers (space requirements) against the algorithms that you are using (time requirements). Containers can maintain invariants (e.g. std::map is sorted on its keys) that other containers can only mimic using algorithms (e.g. std::vector with std::sort, but without the same insertion complexity). So after you finish the container table, make sure to do something similar for the algorithms!
最后，没有提及 Boost.MultiIndex ：因为有时你会不得不选择！
Finally, no container summary would be complete without mentioning Boost.MultiIndex: because sometimes you don't have to choose!
这篇关于C ++ 11容器/适配器属性的实用总结/参考？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
