3.6.
Ассоциативные
контейнеры
Все рассмотренные нами контейнеры эффективны для хранения элементов, включения
и удаления элементов, преобразования порядка следования. Но они не эффективны
для поиска. Для поиска нужного элемента следует перебрать все элементы хранящиеся
в нем. Чтобы этого избежать нужно хранить элементы в контейнеры упорядочено.
Ассоциативный массив - это один из самых полезных и универсальных
контейнеров, который используется для хранения связанных пар "ключ-значение" ("key-value").
Таким образом, ассоциативный массив - это массив, в котором индекс может
быть любого, не только целочисленного типа. Ассоциативный массив называют
часто отображением или картой (map), или словарем (dictionary). В библиотеке
STL реализованы следующие ассоциативные контейнеры:
- map - ассоциативный массив, по ключу в контейнере хранится
одно значение
- multimap - ассоциативный массив с повторяющимися ключами
- set - массив уникальных ключей без значений
- multiset - массив с повторяющимися ключами без значений
3.6.1. Контейнер map (пример 3.7)
Ассоциативные контейнеры организуются как сбалансированное дерево узлов,
значение которого представляет собой пару значений pair<const
key, mapped_type>.
Первый (first) элемент пары является ключом, а второй (second) - значением.
Например:
map<string, int> book;
map<string, int>::iterator it;
for(it=book.begin(); it!=book.end(); ++it)
{
cout<<it->first<<" "<<it->second<<endl;
}
Доступ к элементам ассоциативного массива, так же как и для других контейнеров,
осуществляется с использованием итератора, но при разыменовании итератора
получаем экземпляр объекта pair. Но более типичная работа со значениями,
хранящимися в ассоциативном массиве - это доступ к элементам по ключу. При
этом используется привычный оператор [].
- Если оператор индикации находится справа от знака равенства, то выполняется
поиск по ключу, заданному в качестве индекса, и возвращается соответствующее
ключу значение. Если ключ не найден, то в ассоциативный массив вставляется
элемент с этим ключом и значением по умолчанию (для встроенных типов 0).
- Если оператор индикации находится слева от знака равенства, то выполняется
поиск по ключу, заданному в качестве индекса, и наденному элементу контейнера
присваивается новое значение. Если ключ не найден, то в ассоциативный массив
вставляется элемент с этим ключом и значением заданным слева от знака равенства.
Элементы в ассоциативном массиве хранятся упорядоченно (отсортировано).
Элементы массива будут выведены в лексикографическом порядке, так как обход
по дереву совершается от элемента с меньшим ключом к элементу с большим ключом.
/////////////////////////////////////////////////////////////////////////////
// Программирование на языке высокого уровня. Основы языка С++
// Пример 3.7. Пример работы с контейнером map
//
// http://aco.ifmo.ru/el_books/programming
// Университет ИТМО
/////////////////////////////////////////////////////////////////////////////
#include <iostream> // подключение библиотеки ввода-вывода
#include <map> // подключение описания map
#include <string> // подключение описание строк
using namespace std; // подключение стандартного пространства имен для использования библиотек
/////////////////////////////////////////////////////////////////////////////
void main()
{
map<string, double> glass; // объявление контейнера. Строка - ключ, число - значение
map<string, double>::iterator it; // объявление итератора
// поиск значения по ключу
double n=glass["K8"];
cout<<"K8="<<n<<endl<<endl;
// вставляется элемент с заданным значением
glass["K8"]=1.5;
glass["TK14"]=1.51;
glass["F12"]=1.49;
// вывод всех элементов контейнера
for(it=glass.begin(); it!=glass.end(); it++)
{
cout<<it->first<<" "<<it->second<<endl; // first - ключ, second - значение
}
cout<<endl<<endl;
// изменяется элемент с ключом K8
glass["K8"]=1.55555;
// вывод всех элементов контейнера
for(it=glass.begin(); it!=glass.end(); it++)
{
cout<<it->first<<" "<<it->second<<endl;
}
cout<<endl<<endl;
// поиск по ключу
n=glass["K8"];
cout<<"K8="<<n<<endl;
}
/////////////////////////////////////////////////////////////////////////////
3.6.2. Контейнер set (пример 3.8)
Контейнер set хранит только массив уникальных ключей без значений. Этот
контейнер используется, если нужно из большого количества повторяющихся данных
получить массив уникальных значений.
/////////////////////////////////////////////////////////////////////////////
// Программирование на языке высокого уровня. Основы языка С++
// Пример 3.8. Пример работы с контейнером set
//
// http://aco.ifmo.ru/el_books/programming
// Университет ИТМО
/////////////////////////////////////////////////////////////////////////////
#include <iostream> // подключение библиотеки ввода-вывода
#include <set> // подключение описания set
#include <string> // подключение описание строк
using namespace std; // подключение стандартного пространства имен для использования библиотек
/////////////////////////////////////////////////////////////////////////////
void main()
{
set<string> glass_name; // объявление контейнера
set<string>::iterator it; // объявление итератора
// добавление в контейнер новых значений
glass_name.insert("air");
glass_name.insert("K8");
glass_name.insert("TK14");
glass_name.insert("air");
glass_name.insert("F12");
glass_name.insert("air");
glass_name.insert("TK14");
glass_name.insert("K8");
glass_name.insert("air");
// вывод всех элементов контейнера
for(it=glass_name.begin(); it!=glass_name.end(); it++)
{
cout<<*it<<endl;
}
}
///////////////////////////////////////////////////////////////////////////////
В результате выполнения программы на экран будет выведено:
F12
K8
TK14
air
|
