如何在C++ 11中有效地选择标准库容器？
Bla*_*Bat 131 c++ c++-faq c++11
有一个众所周知的图像(备忘单)称为"C++容器选择".这是为所需用途选择最佳容器的流程图.
有人知道是否已有C++ 11版本吗？
这是前一个:
Mat*_* M. 93
不是我所知道的,但我猜它可以用文字方式完成.此外,图表略有偏差,因为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中检索人员数据.
我想要一个
find函数,因此是一个关联容器1.1.我不在乎订单,因此是一个
unordered_容器1.2.我的密钥(ID)与它关联的值是分开的,因此a
map1.3.ID是唯一的,因此不会出现重复.
最后的答案是:std::unordered_map<ID, PersonData>.
问题2:记忆稳定吗？
- 如果元素在内存中应该是稳定的(即,当容器本身被修改时它们不应该移动),那么使用一些
list - 否则,跳到问题3.
问题2.1:哪个？
- 定居
list; aforward_list仅对较小的内存占用量有用.
问题3:动态大小？
- 如果容器具有已知大小(在编译时),并且在程序过程中不会更改此大小,并且元素是默认构造的,或者您可以提供完整的初始化列表(使用
{ ... }语法),则使用array.它取代了传统的C阵列,但功能方便. - 否则,跳到问题4.
问题4:双端？
- 如果您希望能够从正面和背面移除物品,请使用a
deque,否则使用avector.
您将注意到,默认情况下,除非您需要关联容器,否则您的选择将是a vector.事实证明这也是Sutter和Stroustrup的推荐.
- +1,但有一些注意事项:1)`array`不需要默认的可构造类型; 2)选择`multi`s并不是关于重复*被允许*更多关于*保持*它们是否重要(你可以将重复项放在非`多个容器中,只是恰好只保留了一个). (5认同)
- @BlakBat:`map.find(key)`比`std :: find(map.begin(),map.end(),[&](decltype(map.front())p)更加可口.{return p.first <key;}));`因此,从语义上讲,`find`是一个成员函数而不是来自`<algorithm>`的函数是很重要的.至于O(1)vs O(log n),它不会影响语义; 我将从示例中删除"有效"并将其替换为"easy". (4认同)
- 这个例子有点过时了.1)我们可以在非关联容器上找到(不是成员函数,"<algorithm>"),如果我们需要找到"有效",而无序_将是O(1)而不是O(记录n). (2认同)
Nic*_*las 50
我喜欢Matthieu的答案,但我要重申流程图:
何时不使用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来自bools 容器的真实行为,你就不会从中获取它std::vector<bool>.所以你必须用一个std::deque<bool>.
搜索
如果您需要在容器中查找元素,并且搜索标记不能只是一个索引,那么您可能需要放弃std::vector赞成set和map.注意关键词" 可能 "; 排序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::vector和reserve尺寸对于有界也会起作用std::vector.这样,实际大小可能会有所不同,您只能获得一次内存分配(除非您将容量降低).
- 好吧，我也很喜欢你的答案:) WRT 保持向量排序，除了 `std::sort` 之外，还有 `std::inplace_merge` ，它可以轻松地放置新元素（而不是 `std::inplace_merge` ）。 :lower_bound` + `std::vector::insert` 调用）。很高兴了解 `flat_set` 和 `flat_map`！ (2认同)
- 您也不能使用具有16字节对齐类型的向量.同样也是`vector <bool>`的一个很好的替代品是`vector <char>`. (2认同)
- @Inverse:C++ 11的[`std :: vector :: resize`](http://en.cppreference.com/w/cpp/container/vector/resize)有一个不带值的重载(它只需要新的大小;任何新元素都将默认构建为就地).另外,为什么编译器无法正确对齐值参数,即使它们被声明具有该对齐？ (2认同)
Was*_*aze 24
这是上面流程图的C++ 11版本.[最初发布时没有归属于原作者Mikael Persson ]
- 以下是此图片的作者:http://stackoverflow.com/a/22671607/3052438 (2认同)
- @NO_NAME哇,我很高兴_somebody_不屑于引用消息来源. (2认同)