Контейнер set (множество)
Множество — это структура данных, эквивалентная множествам в математике. Множество состоит из различных элементов заданного типа и поддерживает операции добавления элемента в множество, удаления элемента из множества, проверка принадлежности элемента множеству. Одно и то же значение хранится в множестве только один раз.
Для представления множеств в библиотеке STL имеется контейнер set , который реализован при помощи сбалансированного двоичного дерева поиска (красно-черного дерева), поэтому множества в STL хранятся в виде упорядоченной структуры, что позволяет перебирать элементы множества в порядке возрастания их значений. Для использования контейнера set нужно подключить заголовочный файл .
Подробней о возможностях контейнера set можно прочитать, например, на сайте cppreference.com.
В простейшем случае множество, например, данных типа int объявляется так:
Для добавления элемента в множество используется метод insert :
Для проверки принадлежности элемента множеству используется метод count . Этот метод возвращает количество вхождения передаваемого параметра в данный контейнер, но поскольку в множестве все элементы уникальные, то count для типа set всегда возвращает 0 или 1. То есть для проверки принадлежности значения x множеству S можно использовать следующий код:
Для удаления элемента используется метод erase . Ему можно передать значение элемента, итератор, указывающий на элемент или два итератора (в этом случае удаляется целый интервал элементов, содержащийся между заданными итераторами). Вот два способа удалить элемент x :
Метод size() возвращает количество элементов в множестве, метод empty() , возвращает логическое значение, равное true , если в множестве нет элементов, метод clear() удаляет все элементы из множества.
Итераторы
С итераторами контейнера set можно выполнять операции инкремента (что означает переход к следующему элементу) и декремента (переход к предыдущему элементу). Итераторы можно сравнивать на равенство и неравенство. Операции сравнения итераторов при помощи «», «> page_code_style»>begin() , который возвращает итератор на первый элемент множества, и метод e nd() , который возвращает фиктивный итератор на элемет, следующий за последним элементом в множестве. Таким образом, вывести все элементы множества можно так:
set ::iterator it;
for (it = S.begin(); it != S.end(); ++it)
Благодаря тому, что множества хранятся в упорядоченном виде, все элементы будут выведены в порядке возрастания значений.
В стандарте C++11 разрешается перебор всех элементом множества при помощи range-based цикла:
for (auto elem: S)
Элементы также будут выведены в порядке возрастания.
Для вывода элементов в порядке убывания можно использовать reverse_iterator аналогично векторам:
for (auto it = S.rbegin(); it != S.rend(); ++it)
Функции удаления элементов могут принимать итератор в качестве параметра. В этом случае удаляется элемент, на который указывает итератор. Например, чтобы удалить наименьший элемент:
Но для удаления последнего (наибольшего) элемента в set нельзя использовать reverse_iterator, нужно взять обычный итератор, указывающий на end(), уменьшить и удалить:
auto it = S.begin();
Поиск элемента в set
Для поиска конкретного элемента в set используется метод find . Этот метод возвращает итератор на элемент, а если элемент не найден, то он возвращает итератор end() (т.е. на фиктивный элемент, следующий за последним элементом множества. Используя этот метод проверить принадлежность элемента множеству можно так:
Также есть методы lower_bound и upper_bound , которые находят первых элемент, больше или равный x и первый элемент, строго больший x (аналогично двоичному поиску элемента в массиве).
Эти методы также возвращают итераторы, а если таких элементов (больше или равных или строго больших) нет в множестве, они возвращают end() .
Например, удалить из set минимальный элемент, строго больший x можно так:
auto it = S.upper_bound(x);
Особенности языков программирования
Мы подошли к двум наиболее интересным с точки зрения изучения STL контейнерам: set и map . С которым из них стоит познакомиться в первую очередь — вопрос, не имеющий однозначного ответа. Мнение автора заключается в том, что при академическом подходе к изучению STL, в первую очередь следует познакомиться с set , как с более простым контейнером из рассматриваемой пары. Всё, что можно сделать с set , можно сделать и с map , обратное же утверждение не всегда истинно. С алгоритмической точки зрения map является логическим продолжением set , в то время как многие программисты-практики зачастую смутно понимают назначение контейнера set , и всегда используют map , что менее элегантно и часто более сложно для понимания сторонними людьми. Контейнер set , как уже было упомянуто, содержит множество элементов. Строго говоря, set обеспечивает следующую функциональность: — добавить элемент в рассматриваемое множество, при этом исключая возможность появления дублей; — удалить элемент из множества; — узнать количество (различных) элементов в контейнере; — проверить, присутствует ли в контейнере некоторый элемент. Об алгоритмической эффективности контейнера set мы поговорим позже, вначале познакомимся с его интерфейсом.
set s; for(int i = 1; i s.insert(42); // ничего не произойдёт --- // элемент 42 уже присутствует в множестве for(int i = 2; i // set::size() имеет тип unsigned int int N = int(s.size()); // N будет равно 50
У set нет метода push_back() . Это неудивительно: ведь такого понятия, как порядок элементов или индекс элемента, в set не существует, поэтому слово «back» здесь никак не применимо. А раз уж у set нет понятия «индекс элемента», единственный способ просмотреть данные, содержащиеся в set , заключается в использовании итераторов:
set S; . // вычисление суммы элементов множества S int r = 0; for(set::const_iterator it = S.begin(); it != S.end(); it++)
Если вы пользуетесь GNU C++, то Traversing Macros будет весьма кстати. Показательный пример:
set < pair> > SS; . int total = 0; tr(SS, it) < total += it->second.first; >
Обратите внимание на синтаксис it->second.first . Ввиду того, что it является итератором, перед использованием его необходимо разыменовать. «Верным» синтаксисом было бы (*it).second.first . Однако, в C++ есть негласное правило, что если при описании некоторого объекта есть возможность обеспечить тождественное равенство конструкций (*it). и it-> , то это следует сделать, дабы не вводить пользователей в заблуждение. Разработчики STL, конечно, позаботились об этом в случае с итераторами. Основным преимуществом set перед vector является, несомненно, быстродействие. В основном это быстродействие проявляется при выполнении операции поиска. (При добавлении операция поиска также неявно присутствует, потому как дубли в set не допускаются). Однако, с операцией поиска в set / map есть существенный нюанс. Нюанс заключается в том, что вместо глобального алгоритма std::find(. ) следует использовать метод set set::find(. ) . Это не означает, что std::find(. ) не будет работать с set . Дело в том, что std::find(. ) ничего не знает о типе контейнера, с которым он работает. Принцип работы std::find(. ) крайне прост: он просматривает все элементы до тех пор, пока либо не будет найден искомый элемент, либо не будет достигнут конец интервала. Основное преимущество set перед vector заключается в использовании нелинейной структуры данных, что существенно снижает алгоритмическую сложность операции поиска; использование же std::find(. ) ануллирует все старания разработчиков STL. Метод set::find(. ) имеет всего один аргумент. Возращаемое им значение либо указывает на найденный элемент, либо равно итератору end() для данного экземпляра контейнера.
set s; . if(s.find(42) != s.end()) < // 42 присутствует >else < // 42 не присутствует >
Кроме find(. ) существует также операция count(. ) , которую следует вызывать как метод set::count(x) , а не как алгоритм std::count(begin, end, x) . Ясно, что set::count(x) может вернуть только 0 или 1. Некоторые программисты считают, что вышеприведённый код лучше выглядит, если использовать count(x) вместо find(x) :
if(s.count(42) != 0)
if(s.count(42))
Мнение автора заключается в том, что подобный код вводит читателя в заблуждение: сам смысл операции count() несовместим со случаями, когда элемент либо присутствует, либо нет. Если же вам предтавляется слишком длинным каждый раз писать «[некоторая форма find]» != container.end() , сделайте следующие макросы:
#define present_member(container, element) \ (find(all(container),element) != container.end()) #define present_global(container, element) \ (container.find(element) != container.end())
Здесь all(c) означает c.begin(),c.end() Более того, в соответствии с положением cтандарта, которое называется «конкретизация шаблонов», можно написать следующий код:
template bool present(const T& c, const T2& obj) < return find(c.begin(), c.end(), (T::element_type)(obj)) != c.end(); >template bool present(const set& c, const T2& obj)
При работе с контейнером типа set present(container, element) вызовет метод set::find(element) , в других случаях — std::find(container.begin(), container.end(), element) . Для удаления элемента из set необходимо вызвать метод erase(. ) , передав ему один элемент — элемент, который следует удалить, либо итератор, указывающий на удаляемый элемент.
set s; . s.insert(54); . s.erase(29); s.erase(s.find(57));
Как и полагается erase(. ) , set::erase(. ) имеет интервальную форму.
set s; . set::iterator it1, it2; it1 = s.find(10); it2 = s.find(100); // Будет работать, если как 10, так и 100 присутствуют в множестве if(. ) < s.erase(it1, it2); // при таком вызове будут удалены // все элементы от 10 до 100 не включительно >else < // сдвинем it2 на один элемент вперёд // set::iterator является normal iterator // операция += не определена для итераторов set'а, //но ++ и -- допускаются it2++; s.erase(it1, it2); // а при таком --- от 10 до 100 включительно // приведённый код будет работать, даже если 100 был // последним элементом, входящим в set >
Также, как и полагается контейнерам STL, у set есть интервальный конструктор:
int data[5] = < 5, 1, 4, 2, 3 >; set S(data, data+5);
Кстати, данная функция set предоставляет эффективную возможность избавиться от дубликатов в vector :
vector v; . set s(all(v)); vector v2(all(s));
Теперь v2 содержит те же элементы, что и v , но без дубликатов. Приятной особенностью также является тот факт, что элементы v2 упорядочены по возрастанию, но об этом мы поговорим позже. В set можно хранить элементы любого типа, которые можно упорядочить. Об этом мы тоже поговорим позже.
Set и multiset в C++: что это такое и как с ними работать
Сегодня мы разберем еще два контейнера STL, которые очень похожи между собой — set и multiset.
Что такое set и multiset
set — это контейнер, который автоматически сортирует добавляемые элементы в порядке возрастания. Но при добавлении одинаковых значений, set будет хранить только один его экземпляр. По другому его еще называют множеством.
multiset — это контейнер, который также будет содержать элементы в отсортированном порядке при добавлении, но он хранит повторяющееся элементы, по сравнению с множеством set. Часто его называют мультимножество.
Из-за того, что set построен на списках нельзя обратиться к определенному элементу по индексу, как в массиве или векторе:
st[3] = 19; // ошибкаДля этого придется оперировать итераторами.
Как создать set и multiset
Для использование, с самого начала нужно подключить единственную библиотеку — .
#include Далее используем данную конструкцию:
set [тип] > имя>; multiset [тип] > имя>- [тип] — это тип данных для нашего контейнера.
- [имя] — название нашего контейнера.
set int> st; // пример multiset int> mst;Чтобы добавить новый элемент нужно использовать функцию insert() :
st.insert(знач