Всем доброго времени суток!

Сегодня мне захотелось написать статью о таких зачастую важных на олимпиадах элементах STL, как map и set, то есть, о множествах. Понимаю, что практически все участники div. 1, которые пишут на С++ с ними знакомы и для них статья будет малополезной. Однако, как мне кажется, многие участники div. 2 напротив, могут о них не знать. В первую очередь на них и ориентирована данная статья. Также хочу отметить, что буду рад всякой критике, если Вы сочтёте её необходимой.

Итак, приступим. Как многие знают, "set" переводится с английского как "множество". Отсюда можно сделать логичный вывод, что set — это некая структура данных, которая реализует множество как математический объект. В С++11 есть две различные реализации множества. Первая пришла к нам из С++98. Это обычный set и основан он на реализации красно-чёрного дерева. Вторая реализация — unordered_set, которая была "узаконена" с введением стандарта С++11. Она основана на хеш-таблицах.

Для сета определены следующие полезные для нас операции:

1. Создание.

Как и для множество других контейнеров stl, чтобы объявить set, необходимо прописать

set<type_here> set_name_here;

Можно также использовать конструктор, чтобы сразу инициализировать контейнер. Инициализацию можно провести другим контейнером или парой итераторов [first, last).

2. Добавление.

Выполняется посредством перегруженной функции insert. Синтаксис её вызова:

set<*тип данных элементов, хранящихся в a*> a;
a.insert(*аргументы здесь*);

Вот её основные варианты:

pair<iterator,bool> insert( const value_type& value );

Принимает value — значение, которое следует вставить в множество и возвращает пару — итератор, указывающий на вставленный элемент и bool'еву переменную, обозначающую "успешность" вставки. Т.е. 1 — вставка произошла, 0 — нет. Данная функция выполняется за логарифм от размера контейнера, то есть, за O(logn).

iterator insert( iterator hint, const value_type& value );

Принимает значение value и итератор hint и пытается вставить элемент как можно ближе к итератору hint. Если вставка будет произведена сразу после или перед итератора hint, то функция отработает за O(1), иначе за O(logn).

template< class InputIt >
void insert( InputIt first, InputIt last );

Добавляет в set все элементы, находящиеся на промежутке [first;last) за O((last - first)logn). InputIt должен соответствовать требованиям InputIterator, т.е. поддерживать следующие операции:

1. Сравнение (a!=b);
2. Разыменование (*a);
3. Инкремент (a++ и ++a);
4. Инкремент значения (*a++);

При этом все указатели и итераторы на элементы set остаются в рабочем состоянии. Стоит также отметить, что set поддерживает лишь одно вхождение элемента с одинаковым значением, если же в множестве уже есть элемент с таким значением, он добавлен не будет. Однако, есть структура multiset, которая поддерживает множественные вхождения одного и того же элемента. Однако, операции над ней, за исключением небольших нюансов тождественны операциям над set и поэтому здесь она рассматриваться не будет.

3. Поиск элемента.

Существует несколько различных функций для поиска элементов в set. Вот они:

size_type count( const Key& key ) const;

Считает количество вхождений элемента с ключём key в контейнер. Очевидно, что в силу свойств контейнера, эта функция возвращает либо 0, либо 1. Работает за O(logn).

iterator find( const Key& key );

Находит элемент с ключём key. Если элемент найден, возвращает итератор на него, иначе на end() контейнера. Работает за O(logn).

iterator lower_bound( const Key& key );

Возвращает итератор на первый элемент в множестве, который больше, либо равен искомому. O(logn).

iterator upper_bound( const Key& key );

Возвращает итератор на первый элемент в множестве, который строго больше искомого. O(logn).

Обратите внимание! Для правильного использования этих функций, надо вызывать их как функции-члены контейнера.

set<int> t;
lower_bound(t.begin(),t.end(),number); // Неправильно! Работает за О(n)
t.lower_bound(number); // Правильно!

4. Удаление.

Существует также перегруженная функция erase(), которая позволяет удалять элементы. Вот её основные варианты:

iterator erase( const_iterator position );

Удаляет элемент, находящийся в позиции, указанной итератором. Амортизированная сложность — O(1).

size_type erase( const key_type& key );

Удаляет все элементы с ключевым значением key. Понятно, что, если это просто set, а не multiset, кол-во таких элементов не превышает 1. Работает за O(logn + count(key)).

void erase( iterator first, iterator last );

Удаляет все элементы в диапазоне [first;last). Работает за O(logn + distance(first, last)).

Теперь поговорим о map. Название происходит от mapping — ассоциативный массив. Операции на нём практически тождественны set, однако в элементах контейнера хранится не одно значение, а пары ключ-значение. Сортировка в данном случае будет проходить таким же образом, как при обычной сортировке пар — вначале приоритетом идёт сравнение первых элементов в паре, потом, в случае их равности, сравниваются вторые элементы. Также стоит отметить весьма удобную реализацию обращения по индексам. Например, вот такой код:

map<string,int> test_map;
test_map["ten"]=10;
test_map["ten"]=8;

Вначале создаст в контейнере test_map пару ("ten",10), а затем изменит второй элемент в ней на 8.

unordered_set и unordered_map поддерживают большинство операций, поддерживаемых set и map, но, в среднем, выполняют их за О(1). Несмотря на это, их не всегда выгодно использовать, т.к. unordered означает неупорядоченный, т.е. элементы в них не поддерживаются в отсортированном порядке. В связи с этим, мы не сможем использовать такие контейнеры для, например, пирамидной сортировки, а также мы не сможем за О(1) получать доступ к наибольшему и наименьшему элементу, как в set и map. И, как следствие неупорядоченности, мы не сможем использовать на этих контейнерах операции lower_bound и upper_bound.

Напоследок могу предложить несколько задач, которые можно достаточно легко (по сравнению с решением без STL) решить с использованием этих структур данных:

1. 1496 (Timus)
2. 1196 (Timus)
3. 1837 (Timus)
4. Задача 13 (Codeforces, тренировка по мотивам UOI 2013)

Что ж, надеюсь, что моя статья была полезной кому-нибудь. С нетерпением жду ваших отзывов о ней :)

P.S. понимаю, что в статье материал раскрыт не полностью, хоть я и старался это сделать. Если после прочтения остались какие-то вопросы или замечания, можете их высказать.