Эффективное использование STL полностью

Конечно, сортированный vector обладает серьезным недостатком — он должен постоянно сохранять порядок сортировки! При вставке нового элемента все последующие элементы сдвигаются на одну позицию. Операция сдвига обходится довольно дорого и становится еще дороже при перераспределении памяти (см. совет 14), поскольку после этого обычно приходится копировать всеэлементы вектора. С другой стороны, при удалении элемента из вектора все последующие элементы сдвигаются на одну позицию к началу. Операции вставки-удаления дорого обходятся для контейнеров vector, но относительно дешевы для ассоциативных контейнеров. По этой причине сортированные контейнеры vector используются вместо ассоциативных контейнеров лишь в том случае, если вы знаете, что при использовании структуры данных операции поиска почти не смешиваются со вставкой и удалением.

В этом совете было много текста, но катастрофически не хватало примеров. Давайте рассмотрим базовый код использования сортированного vector вместо set:

vector vw; // Альтернатива для set

…                  // Подготовительная фаза: много вставок,

                   // мало операций поиска

sort(vw.begin, vw.end); // Конец подготовительной фазы (при эмуляции

                            // multiset можно воспользоваться

                            // алгоритмом stable_sort - см. совет 31).

Widget w;// Объект с искомым значением

…        // Начало фазы поиска

if (binary_search(vw.begin, vw.end, w))… // Поиск с применением

                                             // binary_search

vector::iterator i =

 lower_bound(vw.begin, vw.end, w); // Поиск с применением

if (i != vw.end && !(*i < w))…       // lower_bound: конструкция

                                       // !(*i

pair::iterator, vector::iterator> range =

 equal_range(vw.begin, vw.end, w); // Поиск с применением

if (range.first != range.second)…      // equal_range

… // Конец фазы поиска,

  // начало фазы реорганизации

sort(vw.begin, vw.end); // Начало новой фазы поиска…

Как видите, все реализуется достаточно прямолинейно. Основные затруднения связаны с выбором алгоритма поиска (binary_search, lower_bound и т. д.), но в этом вам поможет совет 45.

При переходе от map/multimap к контейнеру vector ситуация становится более интересной, поскольку vector должен содержать объекты pair, входящие в map/multimap. Но при объявлении объекта типа map (или его multimap-аналога) элементы, хранящиеся в контейнере, в действительности относятся к типу pair. Чтобы эмулировать map или multimap на базе vector, признак константности необходимо устранить, поскольку в процессе сортировки элементы вектора перемещаются посредством присваивания, а это означает, что оба компонента пары должны допускать присваивание. Следовательно, при эмуляции map на базе vector данные, хранящиеся в векторе, должны относиться к типу pair, а не pair.

Содержимое map/multimap хранится в отсортированном виде, но при сортировке учитывается только ключевая составляющая элемента (первый компонент пары), поэтому при сортировке vector должно происходить то же самое. Нам придется написать собственную функцию сравнения для пар, поскольку оператор < типа pair сравнивает обесоставляющие пары.

Интересно заметить, что для выполнения поиска требуется вторая функция сравнения. Функция сравнения, используемая при сортировке, получает два объекта pair, но поиск выполняется только по значению ключа. С другой стороны, функция сравнения, используемая при поиске, должна получать два разнотипных объекта — объект с типом ключа (искомое значение) и pair (одна из пар, хранящихся в векторе). Но это еще не все: мы не знаем, что передается в первом аргументе — ключ или pair, поэтому в действительности для поиска необходимы две функции: одна получает ключ, а другая — объект pair. В следующем примере объединено все сказанное ранее:

typedef pair Data; // Тип, хранимый в "map" в данном примере

class DataCompare{ // Класс для функций сравнения

public:

 bool operator(constData& lhs, // Функция сравнения

  constData& rhs) const          // для сортировки

 {