对已排序容器中的一个元素进行排序

Question

我有一个排序对象的向量。在某一时刻，其中一个对象被更新，并且该元素（仅）必须再次排序。

最好的方法是什么？整个容器上的 std::sort() （如果容器已经排序，是不是更快？）或者擦除（）对象并将其插入（）它应该在的位置？

编辑：在这种情况下我必须使用矢量容器

Answer 1

std::lower_bound理论上，您应该使用和的组合std::insert，如下例所示：

#include <iostream>
#include <vector>
#include <algorithm>

template<typename T>
void insert(T value, std::vector<T>& data) {
  auto it = std::lower_bound(data.begin(), data.end(), value);
  data.insert(it, value);
}

template<typename C>
void show(const C& data) {
  for(const auto & item : data) {
    std::cout << item << " ";
  }
  std::cout << "\n";
}

int main() {

  std::vector<int> data { 1, 2, 4, 5, 7, 9 };
  show(data);
  insert(3, data);
  show(data);
  insert(6, data);
  show(data);
}

输出：

$ g++ example.cpp -std=c++14
./a.out
1 2 4 5 7 9
1 2 3 4 5 7 9
1 2 3 4 5 6 7 9

std::lower_bound(beg, end, val)将找到指向范围内[beg, end)不小于（即大于或等于）value 的第一个元素的迭代器（参见cppreference）；它仅适用于已排序的容器。其复杂度为对数std::distance(beg, end)。

std::vector<T>::insert(it, value)将插入value之前it。

在实践中（对于相对较少数量的元素），您可能最好使用线性搜索直到插入点，然后std::insert。换句话说：线性搜索是O(N)、 和std::lower_bound，O(log N)但是对于具有大约 10-50 个元素的向量（您的情况可能会有所不同），线性搜索速度更快（由于缓存效应）。