Bell wrote:

> А>А разве такой есть, что то не могу вспомнить...
> Обычный вектор превращается в сортированный простым мановением std::sort Впрочем, можно обратить свой взор на AssocVector из Loki.

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

Хотя вполне может оказаться, что нужно вставить большое количество элементов до того момента как будет производиться поиск. В этом случае может оказаться эффективнее набить вектор, затем его отсортировать.

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

--
Maxim Yegorushkin

Those who do not understand Unix are condemned to reinvent it, poorly. © Henry Spencer