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

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)迭代不是升比（即大于或等于）值（参见cppreference）;它只适用于分类的容器。它的复杂性在std::distance(beg, end)中是对数的。

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

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

Answer 2

如果向量已经排序，可以很容易地通过二分法找到更新值的新位置（与大小为+2的值进行比较并迭代...）。然后你转移旧地和新地之间的所有元素。

这是因为新老地方之间的移动相当优化的方式是一个浓缩的操作组合std::erase和std::insert，但它会更繁琐的编写和测试...

Answer 3

• std::sort有复杂度为O(n log n)。
• 删除和插入的复杂度为O(n)。
• 轮换的复杂度为O(log n) + O(length_of_rotation)。

您可以使用std::lower_bound找到新的地方，std::rotate修复顺序：

void update(std::vector<int>& v, std::vector<int>::iterator old_it, int new_value) 
{ 
    if (old_it == v.end()) { 
     return; 
    } 
    auto it = std::lower_bound(v.begin(), v.end(), new_value); 
    *old_it = new_value; 

    if (old_it < it) { 
     std::rotate(old_it, old_it + 1, it); 
    } else if (it < old_it) { 
     std::rotate(it, old_it, old_it + 1); 
    } 
} 

Demo

的std::rotate VS remove/insertion优点是复制/移动的号码： 如果只需交换2个第一个元素，则std::rotate只进行交换，而移除所有元素，并在另一侧再次插入元素。