Глава 12. Контейнерные классы

321

Функция equal_range возвращает пару итераторов (lower_bound(x), upper_bound(x)) для переданного ей значения х:

pair<iterator.iterator> equal_range(const key_type& x); pair<const_iterator, const_iterator> equal_range(const key_type& x) const;

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

Словари с дубликатами (multimap)

Как уже упоминалось, словари с дубликатами (multimap) допускают хранение элементов с одинаковыми ключами. Поэтому для них не определена операция доступа по индексу [ ], а добавление с помощью функции insert выполняется успешно в любом случае. Функция возвращает итератор на вставленный элемент.

Элементы с одинаковыми ключами хранятся в словаре в порядке их занесения. При удалении элемента по ключу функция erase возвращает количество удаленных элементов. Функция equal_range возвращает диапазон итераторов, определяющий все вхождения элемента с заданным ключом. Функция count может вернуть значение, большее 1. В остальном словари с дубликатами аналогичны обычным словарям.

Множества (set)

Множество — это ассоциативный контейнер, содержащий только значения ключей, то есть тип value_type соответствует типу Key. Значения ключей должны быть уникальны. Шаблон множества имеет два параметра: тип ключа и тип функционального объекта, определяющего отношение «меньше»:

template <class Key. class Compare = less<Key> >

class set{

public:

typedef Key key_type:

typedef Key value_type:

explicit set(const Compare& comp = CompareO):

template <class Inputlter>

setdnputlter first. Inputlter last. const Compare& comp = CompareO):

set(const set<Key. Compare>& x);

pair<iterator.bool> insert(const value_type& x):

iterator insert(iterator position, const value_type& x):

template <class Inputlter>

void insertdnputlter first. Inputlter last):

void erased'terator position):

size_type erase(const key_type& x):

void erase(iterator first, iterator last):

322

Часть III. Стандартная библиотека

void swap(set<Key, Compare>&);

void clearO;

iterator find(const key_type& x) const;

size_type count(const key_type& x) const;

iterator lower_bound(const key_type& x) const;

iterator upper_bound(const key_type& x) const;

pair<iterator,iterator> equal_range(const key_type& x) const;

Из описания, приведенного с сокращениями, видно, что интерфейс множества аналогичен интерфейсу словаря. Ниже приведен простой пример, в котором создаются множества целых чисел:

#include <iostream>

#include <set>

using namespace std;

typedef set<int. less<int> > setj;

set'i::iterator i;

int main(){ int a[4] set_i si; set_i s2(a. a set_i s3(s2); s2.insert(10); s2.insert(6); for ( i = s2.begin(); cout « *i « " ";

{4, 2, 1, 2};

4);

// Создается пустое множество

// Множество создается копированием массива

// Работает конструктор копирования

// Вставка элементов

i != s2.end(); i++) // Вывод

cout « endl;

// Переменная для хранения результата equal_range;

pair <set_i::iterator. set_i; .-iterator > p;

p = s2.equal_range(2);

cout « *(p.first)« " p = s2.equal_range(5); cout « *(p.first)« " return 0;

« *(p.second) « endl; « *(p.second) « endl;

}

Результат работы программы:

1. 2 4 6 10

2. 4 6 6

Как и для словаря, элементы в множестве хранятся отсортированными. Повторяющиеся элементы в множество не заносятся.

Для работы с множествами в стандартной библиотеке определены алгоритмы, описанные на с. 364.