7

如果出现以下情况，我应该使用哪个 STL 容器：

  1. 定期插入和删除数据。
  2. 定期随机访问数据。

例如：dataset(4,10,15) 如果我想找到最接近 9 的数字，那么它应该返回 10。

  1. 我只存储一个整数。
  2. 它需要排序
  3. 可以去 100k 数据集

我想过使用向量，但是向量插入和删除很昂贵。

   vector<int>

如果我要使用列表，我必须在访问数据之前访问 O(n) 个元素。

   list<int>

我正在考虑使用 set，因为如果它被排序会很好，但我不太确定使用 SET 的效率

所以我希望有人能给出一个好的解决方案！

4

5 回答 5

15

我认为您应该查看此 SO 帖子：在哪种情况下我使用特定的 STL 容器？无论您打算做什么，对于小尺寸矢量都将适合大多数情况。

该图表是一个指南，定期访问容器的事实不会影响容器的选择，除非您关心容器的大小，否则您存储 int 的事实并不重要，在这种情况下，指针的开销列表容器或地图对您来说很重要吗？

排序是由 map 自动完成的，但是如果容器大小足够小以适合内存，则对向量和列表进行排序可能会非常快。

数据插入针对容器中任何位置的列表和映射进行了优化，对于映射，您可以获得它会自行排序的好处，但是如果大小足够小，那么使用新条目构建新向量可能仍然非常快。

您可能还想考虑哈希映射，您仍然最好对您的代码进行分析，尝试根据您的使用情况来猜测什么是最佳的，并且您确实需要测量和分析。

您也可以只确定 STL<map>是一个足够好的平衡或 a<set>并使用这些容器，因为它们会自动对插入和删除进行排序并且查找速度很快，但是维护每个条目中的指针的开销会增加与向量相比使用的内存，如果您不关心这一点，那么您可以考虑使用这些容器。

尽管如此，如果它很重要，那么测试和分析并比较每个容器的性能，您会惊讶于代码将如何执行您的假设。

于 2012-05-12T19:45:31.260 回答
8

如果要求只是性能，则选择基本上应该始终是std::vector.

它避免了基于节点的数据结构（树和列表）的许多内存分配，并利用空间局部性进行更有效的遍历。

当然，向量中间的插入/删除需要移动元素，但即使这样也很少足以使向量比其他数据结构慢。

我看到使用其他数据结构的唯一真正原因是：

  • std::map/ std::set：这些非常方便。美观且易于使用，因此如果不需要最佳性能，我会在需要排序容器或键/值映射时使用它们。（为了获得最佳性能，排序向量可能更可取）
  • 所有其他容器：在面对修改时保证提供的正确性可能很有用：向量经常重新分配和移动其内容，这会使指向向量的指针和迭代器都无效。其他数据结构在那里提供更强的保证（对于 a deque，指针在末端插入/删除后保证保持有效，但迭代器仍可能无效。对于和list，指针和迭代器都保证在插入/移动）setmap

当然，这些只是经验法则。

当涉及性能时，唯一普遍正确的规则是“自己进行基准测试”。我可以告诉你 avector在许多常见场景中的典型表现，但我不能告诉你它在你的代码中的表现，以及你的编译器和标准库。因此，如果您担心性能，请测量它。尝试不同的替代方案，看看哪个更快。

于 2012-05-12T19:52:11.003 回答
2

一个集合足够有效地插入/删除/访问，并且它总是被排序的。唯一要考虑的是集合中的条目是 const （所以顺序不会被破坏），所以要改变，你应该删除、更新和插入

于 2012-05-12T19:52:00.490 回答
1

您的问题的答案完全取决于您的数据集大小，随着列表增长到巨大的大小，进行线性遍历以获取您需要删除/插入的元素所花费的时间远远超过它所花费的时间用于向量进行删除/插入。因此，如果您的数据集很小，请使用列表，如果很大，请使用向量。

于 2012-05-12T19:43:54.560 回答
1

如果需要排序，使用二叉搜索树

于 2012-05-12T19:44:31.080 回答