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

Классы наборов библиотеки STL
Стандартная библиотека шаблонов (STL) предоставляет разработ­ чикам классы контейнеров, обеспечивающих частый и быстрый поиск. Классы s t d : : s e t и s t d : :m u l t i s e t используются для хранения отсо­ ртированного набора элементов и предоставляют возможность поиска с логарифмической зависимостью его продолжительности от количе­ ства данных. Их неупорядоченные аналоги обеспечивают возможность вставки и поиска за постоянное время.

	На сегодняшнем занятии.
■	Чем могут быть полезны контейнеры s e t, m u l t i s e t ,
	u n o r d e r e d _ s e t и u n o r d e r e d _ m u ltis e t библиотеки STL.
■	Вставка, извлечение и поиск элементов.
■	Преимущества и недостатки использования этих контейнеров.

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

Введение в классы наборов библиотеки STL

Контейнеры s e t и m u l t i s e t обеспечивают быстрый поиск ключей в хранящем их кон­ тейнере, т.е. значений ключей, содержащихся в одномерном контейнере. Различие межл> набором (set) и мультимножеством (multiset) в том, что последний допускает дубликаты, тогда как первый позволяет хранить только уникальные значения.

На рис. 19.1 показано, что набор имен содержит только уникальные имена, тогда как мультимножество допускает дубликаты. Будучи шаблонами классов, контейнеры библио­ теки STL — это обобщения, применимые для хранения объектов любых типов, включая строки, целые числа, структуры или классы.

Мультимножество строк

Р И С . 19.1. Визуальное представление набора и мультимножества имен

Чтобы облегчить быстрый поиск, классы s e t и m u l t i s e t библиотеки STL внутренне реализованы как двоичное дерево. Это означает, что для ускорения поиска элементы со­ ртируются при вставке. Это также означает, что, в отличие от вектора, где элемент в опре­ деленной позиции может быть заменен другим, элемент набора в определенной позиции не может быть заменен новым элементом с другим значением. Дело в том, что класс s e : поместит его в другую область внутреннего дерева в соответствии с его значением.

СОВЕТ Чтобы использовать классы std: :set или std: imultiset, включите в код

их заголовок:

#include