插入排序向量

Question

如何将元素插入排序向量，使插入后的向量仍然被排序？

std::vector<int> myVec {1, 1, 3, 6, 9};

sortedInsert(myVec, 4);

for(auto& out : myVec) std::cout << out << " ";
std::cout << std::endl;

/*
* Expected output: 
* 1 1 3 4 6 9
*/

Answer 1

您可以使用<algorithm>库函数std::upper_bound查找插入元素的位置。

#include <algorithm>

template <class T, class Compare = std::less<>>
std::vector<T>::iterator sorted_insert(std::vector<T>& vec, const T& val, Compare comp = Compare{}) {
    return vec.insert(std::upper_bound(vec.begin(), vec.end(), val, comp), val);
}

在执行排序插入时，要插入的位置正好在大于要插入的值的元素之前。即：

std::vector<int> myVec { 1, 1, 3, 6, 9};
//                             ^
// A sorted insert on this vector with value = 2 would insert here

std::upper_bound将迭代器返回到排序容器中的第一个元素，该元素大于所提供的值，或者，如果没有大于所提供值的元素，std::upper_bound将返回该排序容器的结束迭代器。

因此，使用向量的insert方法和从std::upper_bound返回的迭代器将插入所提供的值，以便向量在插入后保持排序。