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

我不知道，但是我想它可以在文本上完成。此外，图表略有偏差，因为通常不是一个好的容器，也不是.这两个列表都是用于利基应用程序的非常专业的容器。listforward_list

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

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

一开始担心性能通常是无用的。只有当您开始处理数千（或更多）物品时，大 O 考虑才会真正发挥作用。

容器有两大类：

• 关联容器：它们有一个操作find
• Simple Sequence 容器

然后，您可以在它们之上构建多个适配器：、、.我将把适配器留在这里，它们足够专业，可以识别。stackqueuepriority_queue

---

问题 1：关联？

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

问题 1.1： 有序 ？

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

问题 1.2：单独的密钥？

• 如果键与值分开，请使用 ，否则使用mapset

问题 1.3： 重复 ？

• 如果要保留重复项，请使用 ，否则不要。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： 哪个 ？

• 安顿下来 ;a 仅对较小的内存占用有用。listforward_list

---

问题 3：动态调整大小？

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

---

问题 4：双端？

• 如果您希望能够从正面和背面删除项目，请使用 ，否则使用 .dequevector

---

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

我喜欢 Matthieu 的回答，但我要重述流程图如下：

何时不使用 std：：vector

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

构造 函数

std::vector要求其内容是可移动构造的，因为它需要能够对项目进行洗牌。这并不是给内容带来的可怕负担（请注意，默认构造函数不是必需的，这要归功于等等）。但是，大多数其他容器不需要任何特定的构造函数（再次感谢 ）。因此，如果你有一个对象，你绝对无法实现移动构造函数，那么你将不得不选择其他东西。emplaceemplace

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

需要布尔斯

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

因此，如果你需要从 s 容器中获取真实行为，则不会从 .因此，您必须使用 .vectorboolstd::vector<bool>std::deque<bool>

搜索

如果您需要在容器中查找元素，并且搜索标签不能只是一个索引，那么您可能需要放弃 and 来支持 和 。注意关键词“可能”;排序有时是一个合理的选择。或者 Boost.Container 的 flat_set/map，它实现了排序的 .std::vectorsetmapstd::vectorstd::vector

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

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

订购

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

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

稳定性

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

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

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

插入性能

std::vector最后只提供廉价的插入（即使这样，如果你吹容量，它也会变得昂贵）。

std::list在性能方面成本高昂（每个新插入的项目都需要分配内存），但它是一致的。它还提供了偶尔不可或缺的功能，可以在几乎没有性能成本的情况下对物品进行洗牌，以及在不损失性能的情况下与其他相同类型的容器交换物品。如果您需要经常洗牌，请使用 .std::liststd::list

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

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

无动态分配

std::array如果您想要尽可能少的动态分配，则是一个很好的容器。它只是 C 阵列的包装器;这意味着在编译时必须知道其大小。如果你能忍受，那就用.std::array

话虽如此，使用和 ing 大小同样适用于有界 .这样，实际大小可能会有所不同，并且您只能获得一个内存分配（除非您耗尽容量）。std::vectorreservestd::vector

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

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 版本。[最初发布时未注明原作者Mikael Persson]