mis*_*ter 7 c++ containers stl
我应该使用哪个STL容器:
例如:数据集(4,10,15)如果我想找到最接近9的数字,那么它应该返回10.
我想过使用矢量,但矢量插入和移除是昂贵的.
vector<int>
如果我要使用list,我必须在到达数据之前访问O(n)元素.
list<int>
我正在考虑使用set,因为如果它被排序会很好,但我不太确定使用SET的效率
所以我希望有人能给出一个好的解决方案!
EdC*_*ica 15
我想你应该检查这个SO帖子:我在哪种情况下使用特定的STL容器？对于小尺寸,矢量将适合大多数情况,无论您打算做什么.
虽然图表是一个指南,但是定期访问容器的事实并不影响容器的选择,你存储int的事实并不重要,除非你关心容器的大小,在这种情况下指针的开销是多少列表容器或地图对您有影响吗？
排序是通过映射自动完成的,但如果容器大小足够小以适合内存,则排序向量和列表可以非常快.
数据插入针对容器中任何位置的列表和映射进行了优化,对于地图,您将获得它将自行排序的好处,但如果大小足够小,那么使用新条目构建新向量可能会非常快.
您可能还需要考虑哈希映射,您仍然最好对自己的代码进行分析,然后尝试再次猜测什么是最佳的,具体取决于您的使用情况,并且您确实需要测量和分析.
您还可以确定STL <map>是足够好的平衡或者<set>使用这些容器,因为它们会自动对插入和删除进行排序,并且查找速度很快但是在每个条目中维护指针的开销增加了与vector相比使用的内存,如果你不关心这个,那么你可以考虑这些容器.
如果它很重要,那么测试和分析并比较每个容器的性能,你会惊讶于代码将如何执行你的假设.
如果要求只是表现,那么选择基本上应该是a std::vector.
它避免了基于节点的数据结构(树和列表)的许多内存分配,并且它利用空间局部性来实现更有效的遍历.
当然,向量中间的插入/移除需要移动元素,但即使这样也很少使向量比其他数据结构慢.
我看到使用其他数据结构的唯一真正原因是:
std::map/ std::set:那些非常方便.好用且易于使用,因此如果不需要最佳性能,我会在需要排序容器或键/值映射时使用它们.(为了获得最佳性能,排序的矢量可能更好)deque,指针保证在插入/删除结束后保持有效,但迭代器可能仍然无效.对于list,set并且map,指针和迭代器保证在插入期间保持有效/去除)当然,这些只是经验法则.
涉及绩效时唯一普遍适用的规则是"自己做基准".我可以告诉你如何vector通常在许多常见的场景进行,但我不能告诉你如何在执行你的代码,用你的编译器和你的标准库.因此,如果您担心性能,请进行测量.尝试不同的替代方案,看看哪个更快.