C++ за 21 день седьмое издание

Преимущества и недостатки использования наборов и мультимножеств

Классы s e t и m u l t i s e t библиотеки STL предоставляют существенные преимущества приложениям, нуждающимся в частых поисках. Поскольку их содержимое отсортировано, поиск осущ ествляется быстрей. Но, чтобы предоставить это преимущ ество, контейнер должен сортировать элементы во время вставки. Таким образом, при вставке элементов есть дополнительные затраты на их сортировку, являющиеся необходимой платой за воз­ можность часто использовать такие функции, как f i n d ().

Функция f i n d () использует внутреннюю двоичную древовидную структуру. Эта от­ сортированная двоичная древовидная структура является причиной другого неявного не­ достатка по сравнению с таким последовательным контейнером, как вектор. Элемент в векторе, на который указывает итератор (скажем, возвращенный функцией s t d : : f i n d ()), может быть перезаписан новым значением. Но в случае набора элементы сортируются согласно их значениям, а потому никогда не следует допускать перезаписи элемента с по­ мощью итератора, даже если бы программно это было возможно.
С++11____________________________________________


Реализация хеш-набора библиотеки STL — классы


std ::unordered_set и std ::unordered_multiset

Контейнеры s t d : : s e t и s t d : :m u l t i s e t библиотеки STL сортируют элементы (кото­ рые одновременно являются ключами) на основании предиката s t d : : le s s < T > или пре­ диката, предоставленного пользователем. Поиск в отсортированном контейнере быстрее, чем в не отсортированном, таком, как вектор, а метод s o r t () обеспечивает логарифми­ ческую сложность. Это означает, что время, потраченное на поиск элемента в наборе, не прямо пропорционально количеству элементов в нем, а скорее его логарифму. Таким об­ разом, поиск среди 10 000 элементов набора осуществляется вдвое дольше, чем среди 100 элементов (так, 100Л2 = 10000 или log(10000) = 2xlog(100)).

456 ЗАНЯТИЕ 19. Классы наборов библиотеки STL

Однако даже этого существенного увеличения производительности по сравнению с не отсортированным контейнером (где продолжительность поиска прямо пропорциональна количеству элементов) иногда недостаточно. Программисты и математики упорно ищут способ осуществления вставки и сортировки за постоянное время, и одним из них явля­ ется реализация на базе хеша, где хеш-функция используется для определения индекса сортировки. Добавляемые в хеш-набор элементы сначала обрабатываются хеш-функцией, которая создает уникальный индекс ячейки, в которой они размещаются. Библиотека STL предоставляет свой вариант хеш -набора в виде класса контейнера s t d : :u n o r d e r e d _ s e t .

_СОВЕТ Чтобы использовать классы контейнеров std: :unordered_set или