47. Ассоциативные контейнеры — краткий обзор. Множество и отображение.

В то время как последовательные контейнеры хранят свои данные линейно, с сохранением относительных позиций, в которые были вставлены элементы, отсортированные ассоциативные контейнеры обходятся без этого порядка, а вместо этого сосредотачиваются на максимальной скорости выборки на основе ключей, которые хранятся в элементе (или, в некоторых случаях, представляют собой сам элемент). Каждый ключ связан со своим подмножеством при помощи так называемой хеш­функции. Первый подход — отсортированные ассоциативные контейнеры можно реализовать в том числе с использованием сбалансированных бинарных деревьев поиска, а последний — хешированные ассоциативные контейнеры — при помощи любого из множества представлений хеш­таблиц. Отсортированными ассоциативными контейнерами STL являются классы set, multiset, map и multimap. В случае множеств и мультимножеств элементами данных являются сами ключи, причем мультимножество допускает наличие одинаковых ключей, а множество — нет. В отображениях и мультиотображениях элементы данных представляют собой пары, состоящие из ключей и собственно данных некоторого другого типа, причем мультиотображение допускает наличие одинаковых ключей, а отображение — нет. По множествам: в STL есть замечательный контейнер — set, он реализует такие сущности как множество и мультимножество. По сути это контейнеры, которые содержат некоторое количество отсортированных элементов, при добавлении нового элемента в множество он сразу становится на свое место так, чтобы не нарушать порядка сортировки. Пример использования множества в программе:

#include  <iostream>
#include  <set>   //  заголовочный  файл
множеств  и  мультимножеств
#include  <iterator>
using  namespace  std;
int  main()
{ set <char>  mySet;
//  объявили  пустое  множество
   //  добавляем  элементы  в  множество
     mySet.insert('I');
     mySet.insert('n');
     mySet.insert('f');
     mySet.insert('i');
     mySet.insert('n');
     mySet.insert('i');
     mySet.insert('t');
     mySet.insert('y');
copy(  mySet.begin(),  mySet.end(),
ostream_iterator<char>(cout,  "  "));
return  0; }

Чтобы объявить множество, необходимо подключить заголовочный файл <set>. Для объявления множества необходимо воспользоваться классом set. То есть в восьмой строке, мы создали объект — множество с именем mySet, элементы которого имеют тип данных char. Далее в множество добавляются новые элементы, до этого множество было пустое. Чтобы добавить элемент в множество, достаточно воспользоваться методом insert(), которому в параметре передать новый элемент. Ну и в строке 20 как обычно выполняется вывод множества на экран, с помощью функции copy(). Смотрим результат работы программы: I f i n t y Как видно, это не совсем то, что мы вводили. Порядок ввода и реальный порядок элементов в множестве — разный, это связано с тем, что элементы множества автоматически сортируются. Еще одной очень важной деталью является то, что в множество не сохранились дубликаты, хотя дубликаты были при добавлении элементов в множество. Как видно в выводе программы, каждый элемент множества уникален. По отображениям: шаблон map – это ассоциативный массив, запоминающий ключи и ассоциированные с ними значения. Ниже представлен код, который выводит год по заданному имени, используя отображение, и список годов, используя мультиотображение (для следующего билета).

#include  <iostream>
#include  <fstream>
#include  <map>
#include  <string>
using  namespace  std;
int  main  ()
{
fstream  in  ("input_task1.txt");
map<string,int>  mp;
multimap<string,int>  mmp;
/*заполнение  map  и  multimap*/
while  (!in.eof()){
string  name;
in>>name;
int  year;
in>>year;
mp.insert(map<string,int>::value_type(
name,year));
mmp.insert(multimap<string,int>::value
_type(name,year));
}
in.close();
/*вывести по заданному имени год
(map)*/
string  find_name_mp;
cout<<"enter  name  (for  map)  :  ";
cin>>find_name_mp;
cout<<mp[find_name_mp]<<endl;
/*список  годов  (multimap)*/
string  find_name_mmp;
cout<<"enter  name  (for  multimap)  :  ";
cin>>find_name_mmp;
for (multimap<string,int>::iterator
iter = mmp.find (find_name_mmp); iter
!= mmp.end() && iter­>first ==
find_name_mmp  ;  ++iter){
cout<<iter­>second  <<endl;
}
return  0;
}

Содержимое входного файла:

Name1 2000
Name2 2001
Name3 2000
Name4 2004
Name2 2011
Name5 2005
Name6 2006
Name7 2007
Name2 2012
Name8 2000
Name9 2009

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

enter  name  (for  map)  :  Name2
2001
enter  name  (for  multimap)  :  Name2 
2001
2011
2012