Рисунок 4.2. Отображение ключей на значения

При доступе по индексу к обычному массиву мы используем последовательные значения индекса 0,1,2 и т. д., которые нет необходимости сохранять где-либо, поскольку элементы массива размещаются непрерывно друг за другом. В противоположность этому как ключи, так и соответствующие значения словарей хранятся в сбалансированном двоичном дереве поиска (см. пример на рис. 4.3). В двоичных деревьях поиска удобно искать ключи (на рисунке 4.3 они подчеркнуты) из-за принципа построения таких деревьев: для каждого узла все ключи в левом поддереве меньше ключа в этом узле, а в правом поддереве все ключи больше.

Рисунок 4.3. Сбалансированное двоичное дерево поиска, служащее для представления словаря

Функции-члены insert для словарей

Вместо доступа по индексу мы можем добавлять элементы словарей с помощью трех функций-членов insert, объявленных как:

pair<iterator, bool> insert(const value type&: x); interator insert(iterator position, const value type&: x); void insert(const value type* first, const value type* last);

Они похожи на функции insert для множеств, о которых говорилось в разделе 4.2, но в этом объявлении тип value type более сложный, потому что каждый элемент является парой (ключ, значение). Как видно из программы

mapcstr.cpp в предыдущем разделе, мы можем использовать конструктор класса pair<int, double> для создания такой пары. Например, вместо

МВ[800] = 0.3;

можно написать

МБ.insert(pair<int, double>(800, 0.3));

не используя значение, возвращаемое функцией insert. Однако добавления с помощью этой функции не происходит, если ключ уже присутствует в словаре.

Следующая программа показывает, как можно использовать возвращаемое этой функцией значение. Она создает словарь, содержащий только один элемент (800, 0.3). Попытка заменить этот элемент на элемент (800, 0.7) не приводит к успеху, потому что их ключи совпадают:

mapins.cpp: Значение, возвращаемое функцией insert класса тар.

iinclude <iostream> iinclude <map> using namespace std;

typedef map<int, double, less<int> > maptype; typedef maptype::iterator Iterator;

void MyInsert(maptype &M, int k, double x) { pair<Iterator, bool>

P = M.insert(make pair(k, x));

Iterator i = P.first;

bool b = P.second;

cout << After attempt to insert ( << к << , << x

), returning P = (i, b):\n ; cout (*i).first = << (*i).first << endl; cout << (*i).second = << (*i).second << endl; cout << b = << b endl << endl;

int mainO { maptype M;

MyInsert(M, 800, 0.3);

MyInsert(M, 800, 0.7);

return 0;

Вывод этой программы выглядит следующим образом:

After attempt to insert (800, 0.3), returning P = (i, b):

(*i).first = 800

(*i).second = 0.3 b = 1

After attempt to insert (800, 0.7), returning P = (i, b):

{*i).first = 800

{*i).second = 0.3 b = 0

Каждая операция вставки в этой программе возвращает пару (г, Ь), где i -итератор, ссылающийся на вставленный элемент, а Ь - значение типа bool, показывающее, успешно ли прошла операция. Две последние строчки приведенного выше вывода программы показывают, что элемент (800, 0.7) не был добавлен в словарь: значение second по-прежнему 0.3, а не 0.7, а b равно О (=false). Если мы хотим добавить элемент (k, х), заменив элемент с тем же значением k, при наличии такого в словаре, просто напишем

М[к] = х;

В функции My Insert мы могли бы заменить выражение

pair<int, double>{k, х)

maptype::value type(к, х) Стоит отметить, что мы не использовали запись

i->first вместо

{*i).first

Эта упрощенная запись оказалась бы допустимой, если переменная i была бы указателем, однако она является итератором, для которого не определен оператор ->.

Для удаления элементов словаря мы можем использовать три функции erase, объявленные следующим образом:

void erase(iterator position);

size type erase (const key type&: x);

void erase(iterator first, iterator last);

Эти функции аналогичны соответствующим функциям множеств, поэтому мы не станем их подробно обсуждать. То же относится к функциям find, count, lowerJjound и upperjbound.

4.6. Словари с дубликатами

Как стало ясно из раздела 2.7, словари с дубликатами отличаются от просто словарей тем, что они допускают два и более элементов с одинаковыми ключами. Рисунок 4.4 показывает возможное представление словаря с дубликатами. Это дерево не может служить представлением словаря, потому что существуют два элемента с одним и тем же ключом, равным 3.