如何在C ++ 11中有效地select标准库容器？
有一个众所周知的图像（备忘单）称为“C ++容器的select”。 这是一个stream程图，select最好的容器为所需的用法。
有人知道它是否已经有了C ++ 11的版本吗？
这是前一个： 
不是我所知道的，但是我猜可以用文本来完成。 此外，图表略有偏差，因为list通常不是一个好的容器， forward_list也不是。 这两个列表都是专门针对特定应用的专用容器。
要build立这样的图表，你只需要两个简单的指导：
- 首先select语义
- 当有几个select可用时，请尽量简单
担心性能通常是无用的。 当你开始处理几千（或更多）项目时，大O的考虑才真正起作用。
有两大类容器：
- 关联容器：他们有一个
find操作 - 简单的序列容器
然后你可以在它们之上build立几个适配器： stack ， queue ， priority_queue 。 我将把适配器放在这里，它们足够专业化以便被识别。
问题1： 联想 ？
- 如果您需要通过一个键轻松search，那么您需要一个关联容器
- 如果您需要对元素进行sorting，那么您需要一个有序的关联容器
- 否则，跳转到问题2。
问题1.1： 命令 ？
- 如果您不需要特定的订单，请使用
unordered_容器，否则使用传统的订购对象。
问题1.2： 单独的密钥 ？
- 如果密钥与值分开，则使用
map，否则使用一setmap
问题1.3： 重复 ？
- 如果你想保持重复，使用
multi，否则不要。
例：
假设我有几个人拥有与他们相关的唯一ID，并且我希望尽可能简单地从其ID中检索个人数据。
-
我想要一个
findfunction，因此一个关联的容器1.1。 我不能不在乎订单，因此是一个
unordered_容器1.2。 我的密钥（ID）与它所关联的值分开，因此是一张
map1.3。 该ID是唯一的，因此不应该重复。
最后的答案是： std::unordered_map<ID, PersonData> 。
问题2： 内存稳定 ？
- 如果元素在内存中应该是稳定的（即当容器本身被修改时，它们不应该四处移动），然后使用一些
list - 否则，跳转到问题3。
问题2.1： 哪个 ？
- 安顿一个
list;forward_list只对较小的内存占用有用。
问题3： dynamic大小 ？
- 如果容器具有已知的大小（在编译时）， 并且在程序过程中这个大小不会被改变， 并且这些元素是默认的可构造的， 或者你可以提供一个完整的初始化列表（使用
{ ... }语法），然后使用一个array。 它取代了传统的C型arrays，但function方便。 - 否则，跳到问题4。
问题4： 双端 ？
- 如果你希望能够从前面和后面移除物品，那么使用一个
deque，否则使用一个vector。
你会注意到，默认情况下，除非你需要一个关联容器，否则你的select将是一个vector 。 原来这也是Sutter和Stroustrup的build议 。
我喜欢Matthieu的回答，但是我要重申这个stream程图：
何时不使用std :: vector
默认情况下，如果你需要一个容器的东西，使用std::vector 。 因此，每个其他的容器只能通过提供一些替代std::vectorfunction来certificate是正确的。
构造函数
std::vector要求其内容是可移动的，因为它需要能够随机播放项目。 这不是一个可怕的负担放置在内容（请注意，默认的构造函数不是必需的 ，感谢emplace等）。 然而，大多数其他容器不需要任何特定的构造函数（再次感谢emplace ）。 所以，如果你有一个对象，你绝对不能实现一个移动构造函数，那么你将不得不select其他的东西。
一个std::deque将是一个普通的替代品，具有std::vector许多属性，但是你只能在deque的两端插入。 插入中间需要移动。 std::list对其内容没有要求。
需要Bools
std::vector<bool>是…不是。 那么，这是标准的。 但它不是通常意义上的vector ，因为std::vector通常允许的操作是被禁止的。 而且它绝对不包含bool s 。
因此，如果你需要从一个容器的bool实际vector行为，你不会从std::vector<bool>得到它。 所以你必须做一个std::deque<bool> 。
search
如果您需要在容器中查找元素，并且search标记不能只是一个索引，那么您可能需要放弃std::vector以支持set和map 。 注意关键词“ 可能 ”; 一个有序的std::vector有时是一个合理的select。 或Boost.Container的flat_set/map ，它实现了一个sorting的std::vector 。
现在有四种变化，每种都有自己的需求。
- 当search标记与您正在查找的项目不同时，请使用
map。 否则使用set。 - 在容器中有很多项目时使用
unordered，search性能绝对需要是O(1)，而不是O(logn)。 - 如果您需要多个项目来使用相同的search标签，请使用
multi。
订购
如果您需要一个容器的项目总是基于特定的比较操作进行sorting，您可以使用一个set 。 或者如果您需要多个项目具有相同的值multi_set 。
或者你可以使用一个有序的std::vector ，但你必须保持它的sorting。
稳定性
当迭代器和引用无效时，有时会担心。 如果你需要一个项目列表，这样你有其他地方的这些项目的迭代器/指针，那么std::vector的无效方法可能是不合适的。 任何插入操作都可能导致失效，具体取决于当前的大小和容量。
std::list提供了一个坚定的保证：迭代器及其关联的引用/指针只在从容器中移除项时才会失效。 std::forward_list是否存在，如果内存是一个严重的问题。
如果这太保证了， std::deque提供了一个较弱但有用的保证。 中间插入的结果是无效的，但在头部或尾部的插入只会导致迭代器失效，而不会导致容器中项目的指针/引用。
插入性能
std::vector只在最后提供廉价的插入（即使这样，如果你打出容量，它也变得很昂贵）。
std::list在性能方面是昂贵的（每个新插入的项目都花费一个内存分配），但它是一致的 。 它还提供偶尔不可缺less的洗牌function，几乎不需要性能成本，也可以在不损失性能的情况下与其他std::list容器进行交易。 如果你需要洗牌很多东西 ，使用std::list 。
std::deque在头部和尾部提供了恒定时间的插入/移除，但是在中间插入可能相当昂贵。 所以如果你需要从前面和后面添加/删除东西， std::deque可能是你需要的东西。
应该指出，由于移动语义， std::vector插入性能可能不会像以前那样糟糕。 一些实现实现了基于语义的项目复制（即所谓的“互换优化”）的forms，但是现在移动是语言的一部分，它是由标准所规定的。
没有dynamic分配
std::array是一个很好的容器，如果你想要尽可能less的dynamic分配。 这只是一个Carrays的包装; 这意味着它的大小必须在编译时已知。 如果你能忍受，那么使用std::array 。
这就是说，使用std::vector并reserve一个大小对于一个有界的std::vector 。 这样，实际的大小可以改变，你只能得到一个内存分配（除非你吹的能力）。
以上是上述stream程图的C ++ 11版本。 [最初没有归属于其原作者Mikael Persson ]
这是一个快速的旋转，虽然它可能需要工作
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版本大不相同，主要是因为我真的不喜欢链接的节点。 链接的节点容器通常可以通过非链接的容器击败，除了less数情况。 如果您不知道这些情况是什么，并且有权访问boost，请不要使用链接的节点容器。 （std :: list，std :: slist，std :: map，std :: multimap，std :: set，std :: multiset）。 （A）这是我们在代码中处理的99.99％，（B）大量元素需要自定义algorithm，而不是不同的容器。
