139

有一个众所周知的图像（备忘单）称为“C++ 容器选择”。这是为所需用途选择最佳容器的流程图。

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

这是上一张： eC++ 容器选择

4

4 回答 4

98

不是我知道的，但是我猜它可以通过文字完成。此外，图表略有偏差，因为list一​​般来说不是一个很好的容器，也不是forward_list。这两个列表都是针对小众应用的非常专业的容器。

要构建这样的图表，您只需要两个简单的准则：

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

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

容器有两大类：

  • 关联容器：它们有一个find操作
  • 简单序列容器

然后您可以在它们之上构建几个适配器：stack, queue, priority_queue. 我将把适配器放在这里，它们足够专业，可以识别。

问题1：联想？

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

问题 1.1：已订购？

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

问题 1.2：单独的密钥？

  • 如果键与值分开，则使用 a map，否则使用 aset

问题 1.3：重复？

  • 如果要保留重复项，请使用 a multi，否则不要。

例子：

假设我有几个人与他们关联的唯一 ID，我想尽可能简单地从其 ID 中检索一个人的数据。

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

1.1。我不在乎订单，因此是一个unordered_容器

1.2. 我的键 (ID) 与其关联的值是分开的，因此map

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

最后的答案是：std::unordered_map<ID, PersonData>。

问题2：内存稳定？

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

问题 2.1：哪个？

  • 安顿下来list；aforward_list仅对较小的内存占用有用。

问题 3：动态调整大小？

  • 如果容器有一个已知大小（在编译时），并且这个大小在程序运行过程中不会改变，并且元素是默认可构造的，或者您可以提供完整的初始化列表（使用{ ... }语法），那么使用array. 它取代了传统的 C 数组，但具有方便的功能。
  • 否则，跳至问题 4。

问题4：双端？

  • 如果您希望能够从正面和背面移除项目，则使用 a deque，否则使用 a vector。

您会注意到，默认情况下，除非您需要关联容器，否则您的选择将是vector. 事实证明，这也是Sutter 和 Stroustrup 的推荐。

于 2012-05-22T11:26:23.053 回答
52

我喜欢马蒂厄的回答，但我将重述流程图如下：

何时不使用 std::vector

默认情况下，如果您需要一个容器，请使用std::vector. 因此，只有通过提供一些替代std::vector.

构造函数

std::vector要求其内容是可移动构造的，因为它需要能够随机播放项目。这对内容来说并不是一个可怕的负担（请注意，不需要默认构造函数，多亏了emplace等等）。但是，大多数其他容器不需要任何特定的构造函数（再次感谢emplace）。因此，如果您有一个绝对无法实现移动构造函数的对象，那么您将不得不选择其他东西。

Astd::deque将是一般替代品，具有 的许多属性std::vector，但您只能在双端队列的任一端插入。中间的插入物需要移动。Astd::list对其内容没有要求。

需要布尔值

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

因此，如果您需要vector来自 s 容器的真实行为bool，您不会从std::vector<bool>. 因此，您必须使用std::deque<bool>.

搜索

如果你需要在容器中查找元素，而搜索标签又不能只是一个索引，那么你可能需要放弃std::vector使用setand map。注意关键词“可能”；排序std::vector有时是一个合理的选择。或者 Boost.Container 的flat_set/map，它实现了一个 sorted std::vector。

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

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

订购

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

或者您可以使用 sorted std::vector，但您必须保持排序。

稳定

迭代器和引用何时失效有时是一个问题。如果您需要一个项目列表，以便在其他各个地方都有指向这些项目的迭代器/指针，那么std::vector的失效方法可能不合适。任何插入操作都可能导致失效，具体取决于当前的大小和容量。

std::list提供坚定的保证：迭代器及其关联的引用/指针仅在项目本身从容器中删除时才会失效。std::forward_list如果记忆是一个严重的问题，是否存在。

如果保证太强，则std::deque提供较弱但有用的保证。无效是由中间的插入导致的，但在头部或尾部的插入只会导致迭代器的无效，而不是容器中项目的指针/引用。

插入性能

std::vector只在最后提供便宜的插入（即使那样，如果你破坏容量，它也会变得昂贵）。

std::list在性能方面是昂贵的（每个新插入的项目都需要分配内存），但它是一致的。它还提供了偶尔必不可少的能力，可以在几乎没有性能成本的情况下随机移动物品，以及std::list在不损失性能的情况下与其他相同类型的容器交易物品。如果您需要大量调整内容，请使用std::list.

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

应该注意的是，由于移动语义，std::vector插入性能可能不像以前那么糟糕了。一些实现实现了一种基于移动语义的项目复制形式（所谓的“swaptimization”），但现在移动是语言的一部分，它是由标准强制执行的。

没有动态分配

std::array如果您想要尽可能少的动态分配，这是一个很好的容器。它只是一个 C 数组的包装器；这意味着它的大小必须在编译时知道。如果您可以忍受，请使用std::array.

话虽如此，使用std::vector和reserveing 大小对于 bounded 也同样有效std::vector。这样，实际大小可能会有所不同，并且您只能获得一个内存分配（除非您破坏了容量）。

于 2012-05-23T07:35:25.400 回答
27

这是上述流程图的 C++11 版本。[最初发布时未注明原作者Mikael Persson ]

于 2014-06-22T01:47:27.467 回答
1

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

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 版本有很大不同，主要是因为我真的不喜欢链接节点。链接节点容器通常可以在性能上被非链接容器击败，除非在极少数情况下。如果您不知道这些情况是什么，并且可以访问 boost，请不要使用链接节点容器。（std::list、std::slist、std::map、std::multimap、std::set、std::multiset）。此列表主要关注小型和中型容器，因为 (A) 这是我们在代码中处理的 99.99%，并且 (B) 大量元素需要自定义算法，而不是不同的容器。

于 2014-05-16T16:55:38.087 回答