itmo.ru aco.ifmo.ru c-visionlab.ru
вернуться в оглавление предыдущая глава предыдущий параграф следующий параграф следующая глава


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