C ++ 11容器/适配器属性的实际摘要/引用？ [英] Practical summary/reference of C++11 containers/adapters properties?

问题描述

我正在寻找各种C ++ 11标准容器和容器适配器（可选还包括boost / Qt）的重要属性的完整摘要/参考，但由这些属性索引，而不是

我想到的属性包括从头开始：

• 插入功能（前/后/任意）。


• 移除功能（前/后/任意）。


• 访问功能（前/后/单向/双向遍历/随机访问）。


• 上述操作的复杂性和迭代器无效规则。 >
  
• 唯一性？订购？关联？连续存储？提前预订？

^{我可能忘记了一些在这种情况下不要犹豫评论/ sup>}

目标是使用该文档作为辅助，为正确的作业选择正确的容器/适配器，而不必通过各种单独的文档（我有一个可怕的记忆）。

理想情况下，它应该通过属性和容器类型（例如table-like）以及快速参考基本约束。但实际上每个属性索引对我来说是最重要的，因为这是在文档中搜索最痛苦的。

如果没有人已经生成，我会很惊讶

我不是要求你总结所有的这些信息（如果我真的需要，我会自己做，在这种情况下，我会在这里发布结果），但只有当你碰巧知道一个现有文档，以满足这些要求。某些喜欢这个是一个好的开始，但你可以看到它仍然缺乏很多

感谢您的关注。

解决方案

我不知道一个单一的文档提供你需要的一切，但是大部分文档已经在某个地方编录。

• 此参考网站有一个包含所有成员的大表格所有容器的功能


• 此 SO问题具有复杂性保证的大表。


• 此 SO问题为您提供了决策树，可供选择容器。

容器成员函数的复杂性要求不难记忆，因为只有4个类别:(摊销） O（1）， O（log N）， c>和 O（N log N）（成员函数 std :: list :: sort（）交叉到标准库的算法域），所以如果你想要一个4色编码版本的cpp引用容器表。

选择正确的容器可以像使用 std :: vector 一样简单，除非分析器指示瓶颈。达到这一点后，您必须在空间/时间复杂性之间做出艰难的折衷， 数据位置 ，易于查找vs易于插入/修改，对于额外的不变量（排序，唯一性， 迭代器无效规则 ）。

最难的部分是您必须平衡容器（空间需求）与您使用的算法（时间要求）。容器可以维护不变量（例如 std :: map 在其键上排序），其他容器只能使用算法模拟（例如 std :: vector 与 std :: sort ，但没有相同的插入复杂性）。因此，在完成容器表之后，确保为算法做类似的操作！

最后，没有提到 Boost.MultiIndex ：因为有时候，不得不选择！

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?

^{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).

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.

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.

Thanks for your attention.

解决方案

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.

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.

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).

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!

Finally, no container summary would be complete without mentioning Boost.MultiIndex: because sometimes you don't have to choose!

这篇关于C ++ 11容器/适配器属性的实际摘要/引用？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！