Здравствуйте, MaximE, Вы писали:

ME>Возможно, что сортировать вектор не очень удачное решение, по сравнению с использованием upper/lower_bound. После вставки sort будет перелопачивать весь массив, lower_bound же найдет тебе нужное место вставки бинарным поиском.

ME>Хотя опять же, сложность lower_bound — гарантировано log2(n), быстрой сортировки std::sort — в среднем c * n * log2(n), в худшем — n ** 2...

А вставку элемента в середину вектора, в случае использования upper/lower_bound, вы учли?