Множество элементов: set

Мы подошли к двум наиболее интересным с точки зрения изучения STL контейнерам: set и map. С которым из них стоит познакомиться в первую очередь -- вопрос, не имеющий однозначного ответа. Мнение автора заключается в том, что при академическом подходе к изучению STL, в первую очередь следует познакомиться с set, как с более простым контейнером из рассматриваемой пары. Всё, что можно сделать с set, можно сделать и с map, обратное же утверждение не всегда истинно. С алгоритмической точки зрения map является логическим продолжением set, в то время как многие программисты-практики зачастую смутно понимают назначение контейнера set, и всегда используют map , что менее элегантно и часто более сложно для понимания сторонними людьми.

Контейнер set, как уже было упомянуто, содержит множество элементов. Строго говоря, set обеспечивает следующую функциональность:

-- добавить элемент в рассматриваемое множество, при этом исключая возможность появления дублей;

-- удалить элемент из множества;

-- узнать количество (различных) элементов в контейнере;

-- проверить, присутствует ли в контейнере некоторый элемент.

Об алгоритмической эффективности контейнера set мы поговорим позже, вначале познакомимся с его интерфейсом.

set<int> s;

for(int i = 1; i <= 100; i++) {
   s.insert(i); // добавим сто первых натуральных чисел
}

s.insert(42); // ничего не произойдёт --- 
   // элемент 42 уже присутствует в множестве

for(int i = 2; i <= 100; i += 2) {
   s.remove(i); // удалим чётные числа
}

// set::size() имеет тип unsigned int
int N = int(s.size()); // N будет равно 50

У set нет метода push_back(). Это неудивительно: ведь такого понятия, как порядок элементов или индекс элемента, в set не существует, поэтому слово «back» здесь никак не применимо.

А раз уж у set нет понятия «индекс элемента», единственный способ просмотреть данные, содержащиеся в set, заключается в использовании итераторов:

set<int> S;
...
// вычисление суммы элементов множества S
int r = 0;
for(set<int>::const_iterator it = S.begin(); 
                            it != S.end(); it++) {
   r += (*it);
}

Если вы пользуетесь GNU C++, то Traversing Macros будет весьма кстати. Показательный пример:

set< pair<string, pair< int, vector<int> > > 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<int> 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<typename T, typename T2> bool present(const T& c, 
                                            const T2& obj) {
    return find(c.begin(), c.end(), 
              (T::element_type)(obj)) != c.end();
}

template<typename T, typename T2> bool 
                   present(const set<T>& c, const T2& obj) {
    return c.find((T::element_type)(obj)) != c.end();
}

При работе с контейнером типа set present(container, element) вызовет метод set::find(element), в других случаях -- std::find(container.begin(), container.end(), element).

Для удаления элемента из set необходимо вызвать метод erase(...), передав ему один элемент -- элемент, который следует удалить, либо итератор, указывающий на удаляемый элемент.

set<int> s;
...
s.insert(54);
...
s.erase(29);
s.erase(s.find(57));

Как и полагается erase(...), set::erase(...) имеет интервальную форму.

set<int> s;
...
set<int>::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<int> S(data, data+5);

Кстати, данная функция set предоставляет эффективную возможность избавиться от дубликатов в vector:

vector<int> v;
...
set<int> s(all(v));
vector<int> v2(all(s));

Теперь v2 содержит те же элементы, что и v, но без дубликатов. Приятной особенностью также является тот факт, что элементы v2 упорядочены по возрастанию, но об этом мы поговорим позже.

В set можно хранить элементы любого типа, которые можно упорядочить. Об этом мы тоже поговорим позже.