有一张众所周知的图片(小抄)叫做"C++容器选择“。这是一个为想要的用途选择最佳容器的流程图。
有没有人知道它是否已经有了C++11版本?
这是前一个:
发布于 2012-05-22 19:26:23
据我所知没有,但我猜可以在文本中完成。此外,图表略有偏离,因为
通常不是一个很好的容器,也不是。
..。这两个列表都是利基应用程序的专用容器。
要构建这样的图表,您只需要两个简单的指导原则:
首先选择语义
当有几个选择时,选择最简单的
一开始,担心性能通常是无用的。只有当你开始处理几千个(或更多)项目时,大O考虑因素才会真正发挥作用。
有两大类容器:
关联
容器:它们有一个
操作
简单序列
容器
然后,您可以在它们之上构建几个适配器:
..。我将把适配器留在这里,它们已经足够专业,可以识别了。
问题1:
关联
什么?
如果您需要通过以下方式轻松地进行搜索
一个
键,则需要一个关联容器。
如果需要对元素进行排序,则需要一个有序的关联容器
否则,跳到问题2。
问题1.1:
已排序
什么?
如果不需要特定的顺序,请使用
容器,否则使用其传统的有序副本。
问题1.2:
单独密钥
什么?
如果键与值是分开的,则使用
,否则使用
问题1.3:
副本
什么?
如果要保留副本,请使用
,否则请不要这样做。
示例:
假设我有几个具有唯一ID的person,并且我希望尽可能简单地从ID中检索person数据。
我想要一个
函数,因此是一个关联容器。
1.1。我不能不关心顺序,因此一个
容器
1.2。我的键(ID)与它关联的值是分开的,因此
1.3。该ID是唯一的,因此不应出现重复项。
最后的答案是:
..。
问题2:
内存稳定
什么?
如果元素在内存中应该是稳定的(即,当容器本身被修改时,它们不应该到处移动),那么使用一些
否则,跳到问题3。
问题2.1:
其中
什么?
满足于一个
;a
仅适用于占用内存较少的情况。
问题3:
动态调整大小
什么?
如果容器具有已知大小(在编译时),
和
该大小在程序过程中不会改变,
和
元素是默认可构造的
或者
您可以提供完整的初始化列表(使用
语法),然后使用
..。它取代了传统的C数组,但具有方便的函数。
否则,跳到问题4。
问题4:
双端
什么?
如果您希望能够同时从正面和背面移除项目,则使用
,否则使用
..。
您将注意到,默认情况下,除非需要关联容器,否则您的选择将是
..。事实证明它也是
Sutter和Stroustrup的建议
..。
发布于 2012-05-23 15:35:25
我喜欢Matthieu的回答,但我将把流程图重申如下:
何时不使用std::vector
默认情况下,如果需要一个容器,可以使用
..。因此,其他每个容器只能通过提供一些替代功能来调整
..。
构造函数
要求它的内容是可移动构造的,因为它需要能够打乱项目。这并不是放在内容上的一个可怕的负担(请注意,默认构造函数是
不需要
,感谢
等等)。但是,大多数其他容器都不需要任何特定的构造函数(同样,这要归功于
)。所以如果你有一个物体,你绝对可以
不能
实现一个移动构造函数,然后你将不得不选择其他的东西。
A
将是通用的替代品,它具有以下许多属性:
,但只能在双队列的两端插入。中间的插件需要移动。A
对其内容没有任何要求。
需要Bools
是..。不是。好吧,这是标准的。但这不是
在通常意义上,作为
通常情况下,允许是被禁止的。而且可以肯定的是
不包含
__s
..。
因此,如果您需要real
的容器中的行为
s,你不会从
..。所以你必须用一个
..。
搜索
如果您需要在容器中查找元素,并且搜索标记不能只是一个索引,那么您可能需要放弃
赞成
和
..。注意关键词“
五月
";排序后的
有时是一个合理的选择。或Boost.Container的
,它实现了排序后的
..。
现在有四种不同的版本,每一种都有自己的需求。
使用
当搜索标签与你正在寻找的商品不是一回事的时候。否则,请使用
..。
使用
当你有一个
地段
容器中的项的数量和搜索性能绝对需要
,而不是
..。
使用
如果您需要多个项目具有相同的搜索标记。
排序
如果需要始终根据特定比较操作对项的容器进行排序,则可以使用
..。或者
如果您需要多个项具有相同的值。
或者,您可以使用排序后的
,但你必须保持它的排序。
稳定性
当迭代器和引用失效时,有时会引起人们的关注。如果您需要一个项目列表,以便在其他不同位置有指向这些项目的迭代器/指针,那么
的无效方法可能不合适。任何插入操作都可能导致无效,具体取决于当前的大小和容量。
提供了一个可靠的保证:迭代器及其相关的引用/指针只有在项本身从容器中移除时才会失效。
如果记忆是一个严重的问题。
如果这是一个强有力的保证,
提供了一个较弱但有用的保证。在中间插入会导致无效,但在头部或尾部插入只会导致
迭代器
,而不是指向容器中项的指针/引用。
插入性能
只在最后提供廉价的插入(即使这样,如果你耗尽了容量,它也会变得昂贵)。
在性能方面是昂贵的(每个新插入的项都会占用一个内存分配),但它是
一致性
..。它还提供了有时必不可少的能力,可以在几乎没有性能成本的情况下洗牌物品,以及与其他人交换物品。
相同类型的容器,性能不会降低。如果你需要把事情弄得乱七八糟
很多
,使用
..。
在头部和尾部提供恒定时间的插入/移除,但在中间插入可能相当昂贵。因此,如果您需要从正面和背面添加/删除内容,
可能就是你需要的。
应该注意的是,由于移动语义,
插入性能可能不会像以前那么差。一些实现实现了一种基于移动语义的项复制形式(所谓的"swaptimization"),但现在移动是语言的一部分,它是标准所要求的。
无动态分配
如果你想要尽可能少的动态分配,它是一个很好的容器。它只是一个C数组的包装器;这意味着它的大小必须在
编译时
..。如果你能接受这一点,那就使用
..。
也就是说,使用
和
指定一个大小对于有界的
..。这样,实际大小可能会有所不同,并且您只会得到一次内存分配(除非您耗尽了容量)。
发布于 2014-06-22 09:47:27
以下是上述流程图的C++11版本。[最初在没有归因于其原始作者的情况下发布,
Mikael Persson
]
https://stackoverflow.com/questions/10699265
复制相似问题