存储在 std::map/std::set 与存储所有数据后对向量进行排序

Question

• 语言：C++

• 我能做的一件事就是分配一个大小为 n 的向量并存储所有数据 然后使用 sort(begin(),end()) 对其进行排序。不然我可以继续放 地图或集合中的数据是自行排序的，因此我不必 之后排序。但在这种情况下插入一个元素可能会更多 由于重新安排而成本高昂（我猜）。

  那么对于大范围的n（对象数量）来说，这是最短时间的最佳选择

Answer 1

视情况而定。

map

和

set

是通常红黑树，它们需要做很多工作才能平衡，否则对其的操作会很慢。而且它不支持随机访问。因此，如果您只想排序一次，则不应使用它们。

但是，如果要继续向容器中插入元素并保持顺序，

map

和

set

将花费

O(logN)

时间，而排序后的

vector

是

O(N)

。后者慢得多，所以如果你想频繁插入和删除，你应该使用

map

或

set

。

Answer 2

两者之间的差异是显而易见的！

使用集合，您插入的每个元素都会获得

O(log(N))

的复杂性。因此，根据结果，您得到

O(N log(N))

，这就是插入排序的复杂性。

将向量中的所有内容相加非常复杂

O(1)

，从 C++11 开始对其进行排序将是

O(N log(N))

（在它之前，

std::sort

平均具有

O(N log(N))

。）。 排序后，您可以使用

binary_search

获得与集合中相同的复杂性。

使用向量作为集合的 API 并不友好，尽管它确实提供了很好的性能优势。当然，仅当您可以批量插入数据或查找量远大于内容操作时，这才有用。当您稍后必须扩展时，可通过算法对部分排序的向量进行排序。 最后，必须指出的是，您没有相同的迭代器失效保证。

那么，为什么向量更好？缓存局部性！ 向量将所有数据存储在单个内存块中，因此处理器可以进行预取，而对于集合，内存分散在需要数据找到下一个地址的地方。当您可以忍受这些限制时，对于大数据，这使得向量比 std::set 更好的集合实现。

为了给你一个想法，在我正在开发的代码库上，我们有几个基于向量的集合和映射实现，它们有自己的功能叙述。（例如：没有擦除或没有运算符[]）

Answer 3

经验法则

一如既往，这取决于容器的平均大小以及您用它做什么。

说到迭代，没有什么比连续内存更好的了。因此，数据更改越少，迭代次数越多，基于矢量的解决方案的性能就越好。由于随机访问迭代器，如果使用二分搜索完成，即使查找也应该很快。 （注意：

std::binary_search()

仅测试某个值是否存在，以访问您需要的值

std::lower_bound()

或

std::upper_bound()

）

但是，更改数据越频繁，std::lib 中的关联容器的性能就越好。在插入或删除时，后者需要做一些工作来找出如何重新平衡其内部树结构，但这只是交换一些指针。另一方面，在这种情况下，向量平均需要移动（或复制）一半的数据。

如有疑问，请简介！

扁平关联容器

如果您倾向于基于矢量的解决方案，您可以尝试平面关联容器。它们提供了更自然和方便的界面作为原始向量。最值得注意的实现是：

• Boost 提供 boost::container::flat_set 及其兄弟姐妹。在内部，他们使用

  std::vector

  （或类似的数据结构），并用

  std::set

  等已知的大部分接口包装它们。出于明显的原因，他们不支持拼接，相反，他们提供从

  std::vector

  已知的成员，例如

   reserve()

  、

  capacity()

  、

  shrink_to_fit()

  和

  max_size()

  。还有提取内部序列或同时采用有序和无序序列的函数。 （前者允许填充向量，对其进行一次排序，采用它，然后使用方便的接口访问它）
• 同样，C++23为我们带来了

  std::flat_set

  等与Boost的扁平容器非常相似的东西。一个主要的区别是它们缺少

  reserve()

  ，这对我来说似乎是一个很大的疏忽。但人们可以通过提取底层序列、调用保留然后再次采用它来解决这个问题。

连续指针

我想参加的最后一位参赛者是

std::vector<std::unique_ptr<T>>

。 （或者，等价地，

boost::container::stable_vector

）它的缓存局部性不如

std::vector<T>

，这使得迭代速度不那么快（指针是连续的，并且指针应该被预取，所以仍然比

std::set

更好）。但如果

T

相当大，那么插入和删除就会变得更快，因为只需要复制指针，而不必移动整个实例。