Эффективный способ вставки данных в отсортированный вектор ⇐ C++

[Гость]

Имея отсортированный std::vector, вставить элемент по порядку можно с помощью этого кода.
После вставки одного элемента мне требуется, чтобы вектор был отсортирован для обработки.

Код: Выделить всё

template< typename T >
typename std::vector::iterator
insert_sorted( std::vector & vec, T const& item )
{
return vec.insert
(
std::upper_bound( vec.begin(), vec.end(), item ),
item
);
}

Этот код не очень эффективен по сравнению с вызовом emplace_back.
Существует ли лучшая реализация для вставки данных в отсортированный вектор, возможно, использует std::rotate, чтобы избежать перераспределения/перехода данных
NB. Я не сравниваю две вставки, а просто чтобы иметь представление об номинальном случае (т. е. вставке упорядоченных чисел)< /п>

Подробнее здесь: https://stackoverflow.com/questions/781 ... ted-vector