c++ - 对 vector 中的一个元素进行排序的最有效方法？

Question

我有一个基于某些外部值排序的元素 vector 。它是一个大容器，查找 sort-value 的成本相对较高。在某些时候，一个元素(仅)需要重新排序。重新排序该元素的最有效方法是什么？ std::sort() vector ？删除插入元素？将元素与其直接相邻的元素进行比较？

编辑:澄清一下，通过删除插入元素我的意思是这样的:

// erase the key and then insert-sort it
auto iter = std::find(keys.begin(), keys.end(), key);

keys.erase(iter);
SortedInsert(keys, index, <cmp>);

EDIT2:出于其他性能原因，容器需要是 vector

Answer 1

如果你想直接在一个排序 vector 的正确位置插入一个元素，你应该使用upper_bound得到一个迭代器并将它传递给insert来放置元素元素在正确的位置:

vec.insert(std::upper_bound(vec.begin(), vec.end(), item), item);

请注意 upper_bound 会很快 (O(log n)) 但插入可能会很慢 (O(n)) 因为它将不得不移动插入点之后的所有元素。

但是，在 vector 末尾插入并调用 std::sort 是 O(n log n) 所以它是最糟糕的，至少在大 vector 上是这样!

vec.insert(item);
std::sort(vec.begin(), vec.end());

另一种选择是在 vector 的末尾插入，然后与前一个元素一起移动，直到它小于或等于。在这种情况下，插入被分摊 O(1) 并且您必须进行 O(n) 交换。

恐怕不会有O(log n) 解决方案，因为您可以使用list。