Auto-sorted vector

Помнится еще Александреску в одной из своих книг упоминал как может сортированный vector или deque по скорости поиска элементов превосходить std::set и std::multiset. В последних контейнерах идет большой оверхед по размеру потребляемой памяти, из-за чего процессору приходится больше данных читать из памяти. Недостаток сортированных vector/deque при вставке - слишком часто придется двигать элементы, если вставлять сразу в нужное место. Однако часто вставка идет большой порцией элементов, что позволяет сначала накидать новые элементы как попало (через push_back), а потом отсортировать контейнер.

Что удивительно, ни в boost, ни в Loki я подобного сортированного вектора в виде отдельного класса (шаблона классов) не нашел. В Loki есть подобная штука - AssocVector, но реализует она функциональность не set/multiset, а map. Тоже, кстати, весьма полезная вещь.

Google навел меня на класс с нужной функциональностью на сайте codeproject. Однако там он какой-то сыроватый, VC++-only, да и без набора юнит-тестов, так что использовать его в реальном проекте я бы не стал. Те, кому наплевать на сырость могут вполне его использовать, а к более продвинутым людям просьба сделать подобную вещь нормально и пропихнуть ее таки в boost, т.к. предыдущие "пропихиватели" похоже не справились (см. здесь и здесь).

Остальные же могут использовать std::vector и std::deque, просто сортируя их и получая прирост производительности (по сравнению с std::set/multiset). Ключевых функций для написания будет две: insert и find. Их можно легко реализовать через родные сердцу алгоритмы бинарного поиска - std::lower_bound() и std::upper_bound().

Ссылка по теме: Why you shouldn't use set (and what you should use instead)