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

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (43)

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

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

这是之前的一个:

提问于
用户回答回答于

不是我所知道的,但是我猜可以按照文字进行。另外,图表稍微偏离了原因,因为list一般来说这不是一个好的容器,也不是forward_list。这两个列表都是专门针对特定应用的专用容器。

要建立这样的图表,您只需要两个简单的指导方针:

  • 首先选择语义
  • 当有几个选择可用时,请尽量简单

首先担心性能通常毫无用处。当你开始处理数千(或更多)项目时,大O的考虑才真正起作用。

有两大类容器:

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

然后你就可以建立在它们上面几个适配器:stackqueuepriority_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)与它所关联的值分开,因此amap 1.3。该ID是唯一的,因此不应有重复。

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

问题2:内存稳定

  • 如果元素在内存中应该是稳定的(即当容器本身被修改时它们不应该四处移动),然后使用一些 list
  • 否则,跳转到问题3。

问题2.1:哪个

  • 解决一个list; a forward_list仅对较小的内存占用有用。

问题3:动态大小

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

问题4:双端

  • 如果希望能够从正面和背面移除物品,请使用a deque,否则使用a vector
用户回答回答于

何时不使用std :: vector

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

构造函数

std::vector要求它的内容是可移动的,因为它需要能够洗涤物品。这不是一个可怕的负担放在内容上(请注意,默认的构造函数不是必需的,感谢emplace等等)。但是,大多数其他容器不需要任何特定的构造函数(再次感谢emplace)。所以如果你有一个你绝对不能实现移动构造函数的对象,那么你将不得不选择其他的东西。

A std::deque将是常规替换,具有许多属性std::vector,但只能在双端队列的两端插入。插入中间需要移动。A std::list没有要求其内容。

需要Bools

std::vector<bool>不是。那么,这是标准的。但vector通常情况下并不是这样,因为std::vector通常允许的操作是被禁止的。它绝对不包含bools

因此,如果你需要vector从一个容器中真正的行为bool,你不会从中得到它std::vector<bool>。所以你必须做一个适当的std::deque<bool>

搜索

如果您需要在容器中查找元素,并且搜索标记不能仅仅是一个索引,那么您可能需要放弃std::vector而选择setmap。注意关键词“ 可能 ”; 排序std::vector有时是一个合理的选择。或Boost.Container的flat_set/map,它实现了一个排序std::vector

现在有四种变体,每种都有自己的需要。

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

订购

如果您需要容器中的项目总是基于特定比较操作进行排序,则可以使用a 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可能是你需要的东西。

应该指出,由于移动语义,std::vector插入性能可能不像以前那样糟糕。一些实现实现了基于语义的项目复制的移动形式(所谓的“互换优化”),但现在移动是语言的一部分,它是由标准强制的。

没有动态分配

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

这就是说,使用std::vectorreserve大小的工作,以及一个有限的std::vector。这样,实际大小可能会有所不同,并且您只能获得一次内存分配(除非您打开容量)。

扫码关注云+社区