Понадобилось мне поиметь отсортированный вектор размером 40 миллионов элементов. Сначала тупо сделал push_back а затем sort. Потом закрался червячок - а может сразу делать вставку в отсортированный? Решил проверить что быстрее.
Результаты на 40 тысячах элементов:
вставка перед upper_bound - 228 секунд
вставка перед lower_bound - 228 секунд
push_back + sort - 0 секунд
Вот так...

PS 40 миллионов элементов- push_back + sort - 187 секунд