Ассоциативные контейнеры

1.

Ассоциативные контейнеры

2.

Ассоциативные контейнеры
Ассоциативные контейнеры обеспечивают быстрый
доступ к данным за счет того, что они, как правило,
построены на основе сбалансированных деревьев
поиска (стандартом регламентируется только интерфейс
контейнеров, а не их реализация). Существует пять типов
ассоциативных контейнеров:
словари (mар),
словари с дубликатами (multimap),
множества (set),
множества с дубликатами (multiset) и
битовые множества (bitset).

3.

Словари часто называют также ассоциативными массивами или
отображениями. Словарь построен на основе пар значений,
первое из которых представляет собой ключ для идентификации
элемента, а второе — собственно элемент. Можно сказать, что
ключ ассоциирован с элементом, откуда и произошло название
этих контейнеров.
Например, в англо-русском словаре ключом является английское
слово, а элементом — русское. Обычный массив тоже можно
рассматривать как словарь, ключом в котором служит номер
элемента. В словарях, описанных в STL, в качестве ключа может
использоваться значение произвольного типа. Ассоциативные
контейнеры описаны в заголовочных файлах <map> и <set>.

4.

5.

Для хранения пары «ключ—элемент» используется
шаблон pair, описанный в за головочном файле <utility>:
template <class T1, class T2> struct pair{
typedef Tl first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair(const T1& x, const T2& y);
template <class U, class V>pair(const pair
V>&p);
};
<U,

6.

Шаблон pair имеет два параметра, представляющих
собой типы элементов пары. Первый элемент имеет
имя first, второй — second. Определено два
конструктора:
один должен получать два значения для
инициализации элементов,
второй (конструктор копирования) — ссылку на другую
пару.
Конструктора по умолчанию у пары нет, то есть при
создании объекта ему требуется присвоить значение
явным образом.

7.

Для пары определены проверка на равенство и операция
сравнения на меньше (все остальные операции
отношения генерируются в STL автоматически на основе
этих двух операций).
Пара р1 меньше пары р2. если
р1.first < р2.first или
р1.first == р2.first && р1.second < р2.second.

8.

Для присваивания значения паре можно использовать
функцию make_pair:
template <class T1, class T2>
pair <T1, T2> make_pair(const T1& x, const T2& y);

9.

Пример формирования пар:
#include <iostream>
#include <utility>
using namespace std;
int main()
{
pair <int, double> p1(10, 12.3), p2(p1);
p2 = make_pair(20, 12.3);/* Эквивалентно
p2 = pair <int, double> (20, 12.3)*/
cout << "p1: " << p1.first << " " << p1.second <<endl; cout <<
"p2: " << p2.first << " " << p2.second<< endl; p2.first -= 10;
if (p1 == p2) cout << "p1 == p2\n“;
p1.second -= 1;
if (p2 > p1) cout << "p2 > p1\n“;
}

10.

Результат работы программы:
p1: 10 12.3
p2: 20 12.3
p1 == p2
p2 > p1

11.

На данный момент существует отличный контейнер map, который позволяет
ассоциировать элементы с чем угодно. Например, у вас есть список продуктов
для покупки (список книг в библиотеке). Вам необходимо хранить сколько и чего
нужно купить (название и количество книг в библиотеке). Контейнер <map>
позволяет нам хранить эти данные в виде ключ-значение (книга-количество,
продукт-вес\объем...). Контейнер <map> является отсортированным массивом.
Сортировка произведена по ключу.
Для использования <map> необходимо сначала его подключить:
#include <map>
Для создание контейнера достаточно написать:
map <key type, data type> map_name;
Например map<string, int> books; Содержит связку название книги / количество
или
map<string, CObject*> objects; Содержит связку название объекта / указатель
на объект
Для доступа (или записи) в массив нужно писать:
map_name[key];

12.

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

13.

begin() - итератор на первый элемент;
end() - итератор на элемент идущий после последнего;
rbegin() - итератор на последний элемент (для обратных
алгоритмов);
rend() - итератор на позицию перед первым элементом
(для обратных алгоритмов).
размер отображения
empty() - возвращает истину, если размер отображения 0;
size() - возвращает число элементов;
max_size() - максимально возможный размер
отображения.
count(key) - число элементов соответствующих указанному
ключу. Для класса map значения 1 или 0;

14.

find(key) - итератор на первый элемент с указанным ключом;
lower_bound(key) - итератор на первый элемент, чей ключ
больше или равен указанному ключу;
upper_bound(key) - итератор на первый элемент, чей ключ
больше указанного ключа;
equal_range(key) - диапазон элементов, чей ключ равен
указанному ключу;
[] - операция индексации по ключу.
swap(map& m) - обмен значениями с другим отображением;
insert(el) - вставка элемента, возвращается его позиция;
insert(beg,end) - вставка элементов из указанного диапазона;
erase(key) - удалить указанный элемент;
erase(it), erase(start,end) - удаляет элемент с заданным
итератором или между заданными
clear() - удалить все элементы.

15.

Для обращения к элементу в строках и векторах
достаточно было перед именем контейнера поставить *,
но в map так не получится, т.к. в каждом элементе
хранится 2 значения (ключ и данные). Поэтому надо
писать так:
(*iter).first - для обращения к ключу и
(*iter).second -для обращения к данным,
где iter - итератор элемента

16.

#include <iostream>
#include <string>
#include <map>
#include <fstream>
using namespace std;
int main() {
map <string,int> words;
ifstream in;
in.open("in.txt");
string word;
while (in>>word)
{ words[word]++; }

17.

ofstream out;
out.open("out.txt");
int count = 0;
map <string,int>::iterator cur;
out<<"Words count:"<<endl;
for (cur=words.begin();cur!=words.end();cur++) {
out<<(*cur).first<<":"<<(*cur).second<<endl;
count+=(*cur).second; }
out<<"Words percenc:"<<endl;
for (cur=words.begin();cur!=words.end();cur++) {
out<<(*cur).first<<":"<<
(float)((float)(*cur).second/(float)count)*100<<"%"<<endl; }
return 0; }

18.

Для поиска элементов в словаре определены следующие
функции:
iterator find(const key_type& х);
const_iterator find(const key_type& x) const;
iterator lower_bound(const key_type& x);
const_iterator lower_bound(const key__type& x) const;
iterator upper_bound(const key_type& x);
const_iterator upper_bound(const key_type &x) const;
size_type count (const key_type& x) const;

19.

include <iostream>
#include <map>
#
using namespace std;
int main ()
{
multimap<char,float> mymultimap;
map<char,float> mymap;
///заполняем multimap
mymultimap.insert( pair<char,float>('a',0.1) );
mymultimap.insert( pair<char,float>('b',0.2) );
mymultimap.insert( pair<char,float>('d',0.4) );
mymultimap.insert( pair<char,float>('e',0.5) );
///заполняем map
mymap.insert( pair<char,float>('f',5.3) );
mymap.insert( pair<char,float>('g',4.32) );
mymap.insert( pair<char,float>('i',23.41) );
mymap.insert( pair<char,float>('r',6.5) );

20.

///вставляем элементы в multimap
mymultimap.emplace('c',0.3);
mymultimap.emplace('b',9.9);
cout << "mymultimap have:" << endl;
for (auto it = mymultimap.begin(); it !=
mymultimap.end(); ++it)
{
cout << it->first << " : " << it->second << endl;
}
auto lowerMap=mymap.lower_bound('g');/// нижняя
граница map
auto upperMap=mymap.upper_bound('i');///верхняя
граница map
auto lowerMultimap=mymultimap.lower_bound('b');///
нижняя граница multimap
auto upperMultimap=mymultimap.upper_bound('d');
//верхняя граница multimap
mymultimap.erase(lowerMultimap,upperMultimap);

21.

mymap.erase(lowerMap,upperMap);
auto itMultimap = mymultimap.begin();
auto itMap = mymap.begin();
cout << "\nmymultimap have: \t mymap have:"
<< endl;
for (itMultimap,itMap; itMultimap !=
mymultimap.end(); ++itMultimap,++itMap)
{
cout << itMultimap->first << " : " <<
itMultimap->second << "\t\t " << itMap>first << " : " << itMap->second << endl;
}
return 0;
}

22.

хеш отображения
В дополнение к стандарту stl многие компиляторы
реализовали дополнительные классы hash_map
и hash_multimap. В нем элементы не сортируются. А для
быстрого доступа к элементу по ключу используется
специальная хеш-функция.
Включаемый файл зависит от компилятора. Так в MinGw
это
#include <ext/hash_map>
В других компиляторах это может быть
#include <hash_map>

23.

Для использования этого класса в MinGw необходимо
использовать пространство имен __gnu_cxx.
Часто типом для ключа является строка. А в MinGw
определена хеш-функция только для С строк, но не
для класса string. Решается эта проблема специализацией
шаблона хеш-функции для класса string. Этот код можно
вынести во включаемый файл или вставлять его перед
объявлением первой переменной такого типа.
В остальном классы аналогичны map и multimap.

24.

... #include <ext/hash_map>
... using namespace __gnu_cxx; //
специализация шаблона хешфункции для класса string
namespace __gnu_cxx{
template<> struct hash<std::string>
{ size_t operator()(const std::string& s) const { return
__stl_hash_string(s.c_str());
}
};
}
... hash_map<string,fdu> funcs; ...

25.

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

26.

Множества с дубликатами (multiset)
Во множествах с дубликатами ключи могут повторяться,
поэтому операция вставки элемента всегда выполняется
успешно, и функция insert возвращает итератор на
вставленный элемент. Элементы с одинаковыми ключами
хранятся в словаре в порядке их занесения. Функция find
возвращает итератор на первый найденный элемент или
end(), если ни одного элемента с заданным ключом не
найдено. При работе с одинаковыми ключами в multiset
часто пользуются функциями count, lower_bound,
upper_bound и equal_range, имеющими тот же смысл, что
и для словарей с дубликатами.

27.

Битовые множества (bitset)
Битовое множество представляет собой шаблон для
представления и обработки длинных
последовательностей битов. Фактически bitset — это
битовый массив, для которого обеспечиваются операции
произвольного доступа, изменения от дельных битов и
всего массива. Биты нумеруются справа налево, начиная с
0.