4

我正在寻找各种 C++11 标准容器和容器适配器(可选还包括 boost/Qt)的重要属性的综合摘要/参考,但由这些属性而不是通常的每个容器文档索引(更多关于以下)。

我想到的属性包括:

  • 插入功能(前/后/任意)。
  • 移除功能(前/后/任意)。
  • 访问能力(前/后/单/双向遍历/随机访问)。
  • 上述操作的复杂性,以及迭代器失效规则。
  • 独特性?订购?联想?连续存储?提前预约?

我可能忘记了一些在这种情况下不要犹豫评论/编辑。

目标是使用该文档作为帮助,为正确的工作选择正确的容器/适配器,而不必每次都一遍又一遍地浏览各种单独的文档(我的记忆力很糟糕)。

理想情况下,它应该按属性和容器类型(例如类似表)进行索引,以便做出决策以及快速参考基本约束。但实际上每个属性索引对我来说是最重要的,因为这是在文档中搜索最痛苦的。

如果没有人制作过这样的文件,我会感到非常惊讶,但我的 Search-fu 在这个文件上让我失望了。

注意:我不是要求您总结所有这些信息(如果我真的需要,我会自己做,在这种情况下我会在这里发布结果),但前提是您碰巧知道适合的现有文档那些要求。像这样的东西是一个好的开始,但正如你所看到的,它仍然缺乏我想要的许多信息,因为它仅限于成员函数。

感谢您的关注。

4

1 回答 1

3

我不知道有一个文档可以提供您需要的一切,但其中大部分都已编目在某个地方。

容器成员函数的复杂性要求并不难记住,因为只有 4 个类别: (amortized) O(1)O(log N)O(N)和(真正跨入标准库算法域的O(N log N)成员函数) 所以如果你愿意,你可以制作std::list::sort()cpp 参考容器表的 4 色编码版本。

std::vector除非您的分析器指示瓶颈,否则选择正确的容器可以像始终使用一样简单。达到这一点后,您必须在空间/时间复杂度、数据局部性、查找的难易程度与插入/修改的难易程度以及额外的不变量(排序性、唯一性、迭代器失效规则)之间做出艰难的权衡。

最困难的部分是你必须平衡你的容器(空间要求)和你正在使用的算法(时间要求)。std::map容器可以保持其他容器只能使用算法模仿的不变量(例如,按其键排序)(例如std::vector,使用std::sort,但没有相同的插入复杂度)。所以在你完成容器表之后,一定要对算法做类似的事情!

最后,如果不提及Boost.MultiIndex ,任何容器摘要都是不完整的:因为有时您不必选择!

于 2013-05-03T18:35:55.640 回答