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

Question

我有一个排序对象的 vector 。在某个时候，其中一个对象得到更新，并且该元素(仅)必须再次排序。

什么是最好的方法？ std::sort() 在整个容器上(如果容器已经排序，它更快吗？)或 erase() 对象和 insert() 它应该在什么地方？

编辑:在这种情况下我必须使用 vector 容器

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) 中第一个元素的迭代器不小于(即大于或等于)值(参见 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 个元素的 vector (您的里程数可能会有所不同)，线性搜索速度更快(由于缓存效应)。