已排序向量的插入

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
*/

- fortytoo

---

@codeling 我个人认为，有重复内容并不会造成太大的问题。只是我不确定应该关闭哪一个作为重复内容;) - 463035818_is_not_a_number

是的，我对重复问题也没有太强烈的感觉。 我主要是为了参考而发布链接，尚未投票关闭（但可能会）。 但是，这个问题似乎有点像一个“陷阱”，旨在获得积分，因为它立即出现了自我回答。 - codeling

@codeling编写问题/答案以获取积分并不是什么坏事，对吧？ ;) - 463035818_is_not_a_number

@463035818不是一个数字，我发誓我不是那么烦人。我只是眼瞎了。我想有一个重复的问答比试图搜索10年前有大量冗余答案的问题要好。 - fortytoo

@463035818 不是一个数字。噢，当然了，应该是std::multi_set ;) - Aconcagua

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 返回的迭代器，将插入所提供的值，以便向量在插入后保持排序。

- fortytoo

---

值得注意的是：std::lower_bound同样适用，将新元素排序到相等元素之前而不是之后 - 这对于std::vector来说效率较低（需要移动更多元素到末尾），但对于例如std::list来说效率更高（插入位置更早找到，无需移动）。 - Aconcagua