在 std::map/std::set 中存储 vs 在存储所有数据后对向量进行排序
Storing in std::map/std::set vs sorting a vector after storing all data
- 语言：C++
我能做的一件事是分配一个大小为 n 的向量并存储所有数据
然后使用 sort(begin(),end()) 对其进行排序。否则，我可以继续放
地图或集合中的数据是自己排序的，所以我不必
之后排序。但是在这种情况下插入一个元素可能会更
由于重新安排，成本高昂（我猜）。
那么对于 n（对象数量）的广泛范围来说，哪个是最短时间的最佳选择
视情况而定
map和set通常是红黑树，他们应该做很多工作来平衡，否则对它的操作会要很慢。而且不支持随机访问。所以如果你只想排序一次，你不应该使用它们。
但是，如果要继续向容器中插入元素并保持顺序，map和set将花费O(logN)时间，而排序后的vector是O(N)。后者慢很多，所以如果你想频繁插入和删除，你应该使用map或set。
两者之间的区别很明显！
使用集合，您插入的每个元素都会得到 O(log(N)) 复杂度。所以根据结果你得到 O(N log(N))，这是插入排序的复杂度。
将向量中的所有内容相加很复杂 O(1)，并且自 C++11 以来对其进行排序将是 O(N log(N))（在它之前，std::sort 具有 O(N log(N))平均的。）。
排序后，您可以使用 binary_search 来获得与集合相同的复杂性。
使用矢量作为集合的 API 并不友好，尽管它确实提供了不错的性能优势。这当然只有在您可以批量插入数据或查找量远大于内容操作时才有用。当您以后必须扩展时，可以对部分排序的向量进行排序的算法。
最后，必须指出您没有相同的迭代器失效保证。
那么，为什么向量更好？缓存位置！
一个向量将所有数据都放在一个内存块中，因此处理器可以进行预取，而对于一个集合，内存分散在需要数据找到下一个地址的地方。当您可以忍受这些限制时，这使得 vector 成为比 std::set 更好的大数据集合实现。
为了给你一个想法，在我正在处理的代码库中，我们有几个基于向量的集合和映射实现，它们有自己的功能叙述。（例如：没有擦除或没有运算符[] )
- 语言：C++
我能做的一件事是分配一个大小为 n 的向量并存储所有数据 然后使用 sort(begin(),end()) 对其进行排序。否则，我可以继续放 地图或集合中的数据是自己排序的，所以我不必 之后排序。但是在这种情况下插入一个元素可能会更 由于重新安排，成本高昂（我猜）。
那么对于 n（对象数量）的广泛范围来说，哪个是最短时间的最佳选择
视情况而定
map和set通常是红黑树，他们应该做很多工作来平衡，否则对它的操作会要很慢。而且不支持随机访问。所以如果你只想排序一次，你不应该使用它们。
但是，如果要继续向容器中插入元素并保持顺序，map和set将花费O(logN)时间，而排序后的vector是O(N)。后者慢很多，所以如果你想频繁插入和删除，你应该使用map或set。
两者之间的区别很明显！
使用集合，您插入的每个元素都会得到 O(log(N)) 复杂度。所以根据结果你得到 O(N log(N))，这是插入排序的复杂度。
将向量中的所有内容相加很复杂 O(1)，并且自 C++11 以来对其进行排序将是 O(N log(N))（在它之前，std::sort 具有 O(N log(N))平均的。）。
排序后，您可以使用 binary_search 来获得与集合相同的复杂性。
使用矢量作为集合的 API 并不友好，尽管它确实提供了不错的性能优势。这当然只有在您可以批量插入数据或查找量远大于内容操作时才有用。当您以后必须扩展时，可以对部分排序的向量进行排序的算法。 最后，必须指出您没有相同的迭代器失效保证。
那么，为什么向量更好？缓存位置！ 一个向量将所有数据都放在一个内存块中，因此处理器可以进行预取，而对于一个集合，内存分散在需要数据找到下一个地址的地方。当您可以忍受这些限制时，这使得 vector 成为比 std::set 更好的大数据集合实现。
为了给你一个想法，在我正在处理的代码库中，我们有几个基于向量的集合和映射实现，它们有自己的功能叙述。（例如：没有擦除或没有运算符[] )