c++ - 应该使用插入排序还是构造堆来 boost 性能？

Question

我们有大型(超过 100,000 个元素)有序结构 vector (运算符 < 重载以提供排序):

std::vector < MyType > vectorMyTypes;
std::sort(vectorMyType.begin(), vectorMyType.end());

我的问题是，在向这些 vector 添加新元素同时保留排序顺序时，我们遇到了性能问题。目前我们正在做类似的事情:

for ( a very large set )
{
    vectorMyTypes.push_back(newType);
    std::sort(vectorMyType.begin(), vectorMyType.end());

    ...

    ValidateStuff(vectorMyType); // this method expects the vector to be ordered
}

这不是完全我们的代码的样子，因为我知道这个例子可以用不同的方式优化，但是它让你知道性能可能是一个问题，因为我正在排序在每次 push_back 之后。

我想我基本上有两种选择来 boost 性能:

1. 使用(手工制作的？)插入排序而不是 std::sort 来 boost 排序性能(对部分排序的 vector 进行插入排序是盲目的快)

2. 使用std::make_heap 和std::push_heap 创建堆以维护排序顺序

我的问题是:

• 我应该实现插入排序吗？ Boost 中有什么可以帮助我的吗？

• 我应该考虑使用堆吗？我该怎么做？

---

编辑:

感谢您的所有回复。我知道我给出的例子远非最佳，它不能完全代表我现在代码中的内容。它只是为了说明我遇到的性能瓶颈——也许这就是为什么这个问题没有得到很多赞成票的原因:)

非常感谢你Steve ，通常是最简单的答案是最好的，也许是我对问题的过度分析使我对最明显的解决方案视而不见。我确实喜欢您概述的直接插入到预定 vector 中的巧妙方法。

正如我所说，我现在只能使用 vector ，所以 std::set、std::map 等不是一个选项。

Answer 1

有序插入不需要 boost :

vectorMyTypes.insert(
    std::upper_bound(vectorMyTypes.begin(), vectorMyTypes.end(), newType),
    newType);

upper_bound 提供了一个有效的插入点，前提是 vector 已排序，因此只要您只在正确的位置插入元素，您就完成了。我最初说的是 lower_bound，但是如果 vector 包含多个相等的元素，则 upper_bound 选择需要较少工作的插入点。

这确实要复制O(n)个元素，但你说插入排序“快得要命”，这个更快。如果不够快，你必须找到一种方法来批量添加项目并在最后验证，或者放弃连续存储并切换到维护顺序的容器，例如 set 或多集。

堆不维护底层容器中的顺序，但适用于优先级队列或类似队列，因为它可以快速移除最大元素。你说你想按顺序维护 vector ，但如果你实际上从未按顺序迭代整个集合，那么你可能不需要它完全排序，这就是堆有用的时候。