如何在 C + + 11中有效地选择一个标准库容器？

有一个著名的图像(备忘单)称为“ C + + 容器选择”。这是一个流程图，用于选择最适合所需用途的容器。

有人知道是否已经有 C + + 11版本了吗？

这是前一个: eC++ Container choice

18026 次浏览
小开
最佳答案

据我所知没有，不过我猜可以通过文字来实现。此外，图表稍有偏差，因为 list通常不是一个很好的容器，forward_list也不是。这两个列表都是针对特定应用程序的非常专业的容器。

要构建这样一个图表，您只需要两个简单的指导原则:

  • 首先选择语义
  • 当有多种选择时，选择最简单的

一开始担心性能通常是没有用的。只有当您开始处理数千个(或更多)项目时，才真正需要考虑大 O。

有两大类集装箱:

  • 联合的 容器: 它们有一个 find操作
  • 简单序列 容器

然后可以在它们之上构建几个适配器: stack、 queue、 priority_queue。我将把适配器留在这里，它们已经足够专门化，可以被识别出来。

问题1: 联想？

  • 如果您需要通过 一键轻松搜索，那么您需要一个关联容器
  • 如果需要对元素进行排序，那么需要一个有序的关联容器
  • 否则，跳到问题2。

问题1.1: 命令？

  • 如果不需要特定的订单，请使用 unordered_容器，否则请使用其传统的有序对应容器。

问题1.2: 分开的钥匙？

  • 如果键与值分离，则使用 map，否则使用 set

问题1.3: 复制品？

  • 如果要保留副本，请使用 multi，否则不要使用。

例如:

假设我有几个具有与之关联的唯一 ID 的人，并且我希望尽可能简单地从其 ID 中检索一个人数据。

  1. 我想要一个 find函数，因此是一个关联容器

1.1。我一点也不在乎订单，所以我买了一个 unordered_集装箱

1.2. 我的密钥(ID)与它所关联的值是分开的，因此是 map

1.3. ID 是唯一的，因此不应该出现重复的内容。

最终答案是: std::unordered_map<ID, PersonData>。

问题2: 记忆稳定？

  • 如果元素在内存中应该是稳定的(即，当容器本身被修改时，它们不应该移动) ，那么使用一些 list
  • 否则，跳到第三题。

问题2.1: 哪个？

  • 满足于 list; forward_list只适用于内存占用较少的情况。

问题3: 动态规模？

  • 如果容器有一个已知的大小(在编译时) ，还有这个大小在程序执行过程中不会改变，还有的元素是默认可构造的 或者可以提供一个完整的初始化列表(使用 { ... }语法) ，然后使用 array。它取代了传统的 C 数组，但使用了方便的函数。
  • 否则，跳到第四题。

问题4: 双头？

  • 如果您希望能够删除项目从前面和后面，然后使用 deque，否则使用 vector。

您将注意到，默认情况下，除非需要关联容器，否则您的选择将是 vector。原来它也是 Sutter 和 Stroustrup 的推荐信。

小开

我喜欢马修的回答，但我要重述一下流程图:

何时不使用 std: : Vector

默认情况下，如果您需要一个容器的东西，使用 std::vector。因此，只有通过提供一些可替代 std::vector的功能，才能证明其他容器的合理性。

建筑工人

std::vector要求它的内容是可移动构造的，因为它需要能够随意改变项目。对于内容来说，这并不是一个可怕的负担(请注意，由于 emplace等等，默认构造函数是 不需要)。然而，大多数其他容器不需要任何特定的构造函数(再次感谢 emplace)。因此，如果您有一个对象，其中您绝对 不能实现了一个 move 构造函数，那么您将不得不选择其他内容。

std::deque将是通用的替换，它具有 std::vector的许多属性，但是只能在 deque 的两端插入。中间的插入物需要移动。std::list对其内容没有要求。

需要布尔斯

std::vector<bool>不是。这是标准程序。但它不是通常意义上的 vector，因为 std::vector通常允许的操作是被禁止的。而且肯定是 不包含 bool。

因此，如果您需要从一个包含 bool的容器中获得真正的 vector行为，那么您不会从 std::vector<bool>中获得它。所以你得用 std::deque<bool>。

搜索中

如果需要在容器中查找元素，并且搜索标记不能仅仅是索引，那么可能需要放弃 std::vector，转而使用 set和 map。注意关键词“ 梅”; 排序后的 std::vector有时是一个合理的选择。或者升职。容器的 flat_set/map，它实现排序后的 std::vector。

现在有四种变体，每种都有自己的需求。

  • 当搜索标记与您正在查找的项目本身不同时，请使用 map。否则使用 set。
  • 使用 unordered时，你有一个项目的 很多的容器和搜索性能绝对需要是 O(1)，而不是 O(logn)。
  • 如果需要多个项目具有相同的搜索标记，请使用 multi。

点菜

如果需要总是根据特定的比较操作对项的容器进行排序，可以使用 set。如果需要多个项具有相同的值，则使用 multi_set。

或者可以使用已排序的 std::vector，但是必须保持它已排序。

稳定

当迭代器和引用无效时，有时需要考虑。如果您需要一个项目列表，比如在不同的地方有指向这些项目的迭代器/指针，那么 std::vector的无效化方法可能并不合适。根据当前的大小和容量，任何插入操作都可能导致失效。

std::list提供了有力的保证: 迭代器及其相关的引用/指针只有在项目本身从容器中移除时才会失效。如果存在严重的内存问题，std::forward_list就在那里。

如果这种担保过于强烈，std::deque则提供了一种较弱但有用的担保。失效是由中间的插入导致的，但是在头部或尾部的插入只会导致 迭代器失效，而不会导致指向容器中项目的指针/引用失效。

插入性能

std::vector只能在末端提供廉价的插入(即使这样，如果超出容量，它也会变得昂贵)。

就性能而言，std::list是昂贵的(每个新插入的项目都要花费一个内存分配) ，但它是 始终如一。它还提供了偶尔不可或缺的能力来洗牌物品几乎没有性能成本，以及贸易项目与其他同类型的 std::list容器在没有性能损失。如果你需要在 很多周围重新洗牌，使用 std::list。

std::deque在头部和尾部提供恒定时间的插入/移除，但在中间的插入可能相当昂贵。因此，如果您需要从前面和后面添加或删除东西，std::deque可能是您需要的。

值得注意的是，由于使用了 move 语义，std::vector的插入性能可能没有以前那么差了。一些实现实现了一种基于移动语义的项目复制形式(即所谓的“交换优化”) ，但是现在移动已经成为语言的一部分，它是由标准规定的。

没有动态分配

如果希望尽可能减少动态分配，std::array是一个很好的容器。它只是 C 数组的一个包装器; 这意味着它的大小必须在 编译时中知道。如果你能接受这一点，那么使用 std::array。

也就是说，对于有界的 std::vector，使用 std::vector和 reserveing 的大小也同样适用。这样，实际的大小可能会有所不同，并且您只能获得一个内存分配(除非您超出了容量)。

小开

这里是一个快速旋转，虽然它可能需要工作

Should the container let you manage the order of the elements?
Yes:
Will the container contain always exactly the same number of elements?
Yes:
Does the container need a fast move operator?
Yes: std::vector
No: std::array
No:
Do you absolutely need stable iterators? (be certain!)
Yes: boost::stable_vector (as a last case fallback, std::list)
No:
Do inserts happen only at the ends?
Yes: std::deque
No: std::vector
No:
Are keys associated with Values?
Yes:
Do the keys need to be sorted?
Yes:
Are there more than one value per key?
Yes: boost::flat_map (as a last case fallback, std::map)
No: boost::flat_multimap (as a last case fallback, std::map)
No:
Are there more than one value per key?
Yes: std::unordered_multimap
No: std::unordered_map
No:
Are elements read then removed in a certain order?
Yes:
Order is:
Ordered by element: std::priority_queue
First in First out: std::queue
First in Last out: std::stack
Other: Custom based on std::vector?????
No:
Should the elements be sorted by value?
Yes: boost::flat_set
No: std::vector

您可能注意到，这与 C + + 03版本的 疯狂不同，主要是因为我实际上不喜欢链接节点。除了极少数情况外，链接节点容器通常在性能上会被非链接容器打败。如果您不知道这些情况是什么，并且具有提升的权限，那么不要使用链接节点容器。(std: : list，std: : slist，std: : map，std: : multimap，std: : set，std: : multiset).这个列表主要关注中小型的容器，因为(A)这是我们在代码中处理的99.99% ，(B)大量的元素需要自定义算法，而不是不同的容器。

小开

下面是 C + + 11版本的上述流程图


提交答案