/ 3 0.2

800 0.3

3 2.9

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

Конструкторы словарей с дубликатами аналогичны конструкторам словарей, поэтому мы не станем их здесь рассматривать, а сосредоточимся на отличиях словарей с дубликатами от словарей. Например, мы не можем заменить строчку

D.insert(mmtype::value type{ Johnson, J. , 12345));

ИЗ программы multimap.cpp в разделе 2.7 на

D[ Johnson, J. ] = 12345; ???

Функции insert и erase для словарей с дубликатами объявлены следующим образом:

iterator insert (const value type&: x) ;

iterator insert(iterator position, const value type&: x); void insert(const value type* first, const value type* last);

void erase(iterator position);

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

void erase(iterator first, iterator last);

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

Обратим внимание на порядок, в котором элементы с одинаковыми ключами добавляются в словарь с дубликатами. Его демонстрирует следующая программа:

mmapins.cpp: Добавление элементов в словарь с дубликатами.

iinclude <iostream> iinclude <map>

using namespace std;

typedef multimap<int, double, less<int> > multimaptype; typedef multimaptype::iterator Iterator;

void Mylnsert(multimaptype Ш, int k, double x) { Iterator i = M.insert(make pair(k, x));

cout << (*i).first (*i).second;

Эквивалентно:

cout << к << x;

cout << inserted\n ;

int main() { multimaptype M;

MyInsert(M, 800, 0.3)

Mylnsert(M, 800, 0.7)

Mylnsert(M, 800, 0.5)

Mylnsert(M, 100, 1.9)

Mylnsert(M, 800, 0.6)

cout << Multimap traversal:\n ;

for (Iterator i = M.begin(); i != M.endO; + + i)

cout << (*i).first << (*i).second << endl;

return 0;

Результат работы программы mmapins.cpp показывает, что порядок элементов с одинаковыми ключами в словаре с дубликатами совпадает с порядком, в котором они были добавлены в указанный контейнер. В противоположность этому разные ключи следуют в возрастающем порядке, вне зависимости от порядка их добавления.

800, 0.3 inserted 800, 0.7 inserted 800, 0.5 inserted 100, 1.9 inserted 800, 0.6 inserted Multimap traversal: 100, 1.9 800, 0.3 800, 0.7 800, 0.5 800, 0.6

Вторая из трех функций erase (с одним аргументом, ключом) удаляет все элементы с заданным ключом и возвращает число удаленных элементов. Например, если мы в программе mmapins.cpp добавим строчки

int п = M.erase(800) ;

cout n elements erased\n ;

непосредственно после пяти вызовов функции Mylnsert, вывод программы будет следующий:

800, 0.3 inserted 800, 0.7 inserted 800, 0.5 inserted 100, 1.9 inserted 800, 0.6 inserted 4 elements erased Multimap traversal: 100, 1.9

4.7. Сводный указатель

в этом разделе мы создадим приложение, использующее концепции словаря и множества наряду с классом string, представленным в разделе 2.12. Это будет программа сводный указатель, берущая в качестве входных данных любой текстовый файл и для каждого слова в файле показывающая номера строк, в которых встречается это слово. Если слово встречается более одного раза на строчке, для этого слова номер строчки появится только один раз; сами слова будут перечислены в алфавитном порядке. Слово определяется как последовательность букв. Заглавные буквы будут заменены строчными. Для примера в качестве входного файла выберем текст первой программы в этой книге из раздела 1.1:

ftempl.cpp: А template function, iinclude <iostream.h>

template <class T> T f(T X)

{ T x2 = 2 * x;

return x2 + (X * X + l)/x2;

int mainO

{ cout f(5.0) << endl f(5) << endl; return 0;

Как мы видим, во входном файле могут встречаться любые символы. Для него наша программа сводный указатель выдаст следующий результат:

Enter name of input file: ftempi.cdd

class 4

cout 11

cpp 1

endl 11

f 5 11