C++. Сборник рецептов

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

Смотри также

Рецепт 6.1.

6.6. Отображение строк на другие объекты

Проблема

Имеются объекты, которые требуется сохранить в памяти, и вы хотите хранить их по ключам типа string. Требуется иметь возможность быстро добавлять, удалять и получать элементы (с, как максимум, логарифмической сложностью).

Решение

Для отображения ключей (string) на значения (любой тип, который подчиняется семантике значений) используйте стандартный контейнер map, объявленный в <map>. Пример 6.6 показывает, как это делается.

Пример 6.6. Создание отображения строк

#include <iostream>
#include <map>
#include <string>

using namespace std;

int main {
 map<string, string> strMap;
 strMap["Monday"] = "Montag";
 strMap["Tuesday"] = "Dienstag";
 strMap["Wednesday"] = "Mittwoch";
 strMap["Thursday"] = "Donnerstag";
 strMap["Friday"] = "Freitag";
 strMap["Saturday"] = "Samstag";
 // strMap.insert(make_pair("Sunday", "Sonntag"));
 strMap.insert(pair<string, string>("Sunday", "Sonntag"));
 for(map<string, string>::iterator p = strMap.begin;
 p != strMap.end; ++p) {
 cout << "English: " << p->first
 << German: " << p->second << endl;
 }
 cout << endl;
 strMap.erase(strMap.find("Tuesday"));
 for (map<string, string>::iterator p = strMap.begin;
 p ! = strMap.end; ++p) {
 cout << "English: " << p->first
 << ", German: " << p->second << endl;
 }
}

Обсуждение

map — это ассоциативный контейнер, который отображает ключи на значения, предоставляет логарифмическую сложность вставки и поиска и постоянную сложность удаления одного элемента. Обычно разработчики используют отображение для хранения объектов по их ключам типа string. Именно это делает пример 6.6. В этом случае отображаемый тип является строкой, но он может быть почти чем угодно.

Отображение объявляется вот так.

map<typename Key, // Тип ключа
 typename Value, // Тип значения
 typename LessThanFun = std::less<Key>, // Функция/функтор,
 // используемые для сортировки
 typename Alloc = std::allocator<Key> > // Распределитель памяти

Key и Value — это типы ключа и связанного значения, которые хранятся в отображении. LessThanFun — это функция или функтор, который принимает два аргумента и возвращает истину, если первый меньше, чем второй. По умолчанию используется стандартный функтор less. Alloc — это распределитель памяти, и по умолчанию используется стандартный.

Использование map довольно просто. Объявите тип ключа и значения вот так.

map<string, string> strMan;

В результате будет создан map, в котором и ключ, и значение имеют тип string. С помощью operator[] поместите в отображение объекты, что интуитивно и легко читаемо.

strMap["Monday"] = Montag";
strMap["Tuesday"] = "Dienstag";
strMap["Wednesday"] = "Mittwoch"; // ...

В результате в map будут вставлены элементы с индексом (например, "Monday") в качестве ключа и правым операндом в качестве значения. Они хранятся в порядке, определяемом параметром шаблона LessThanFun, и если он не указан, то map использует std::less<Key>.

Чтобы получить значения из map, используйте operator[] в правой части присвоения, как здесь.

wedInGerman = strMap["Wednesday"];

В манере всех стандартных контейнеров значение, связанное с ключом "Wednesday", с помощью operator= копируется в объект wedInGerman.

operator[] — это удобный способ вставки или обновления элементов или получения значений из map, но он имеет побочный эффект, который может оказаться неожиданным. Строго говоря, operator[k] возвращает ссылку на значение, ассоциированное с k — независимо от того, существует ли k в map или нет. Если k уже находится в map, то возвращается ассоциированное с ним значение. Если нет, то k вставляется, а затем используется конструктор по умолчанию, который создает объект значения для этого ключа. Чтобы сделать это более понятным, рассмотрим, что делает следующий код.

map<string, string> mapZipCodes; // Сейчас здесь ноль элементов
string myZip = mapZipCodes["Tempe"]; // В map пока что нет элементов,
 // но чему теперь равно count?

Что находится в myZip и сколько теперь элементов в mapZipCodes? Так как operator[] вставляет указанный ключ, если он не существует, myZip содержит пустую строку, а в mapZipCodes содержится один элемент. Это может оказаться нежелательно, но независимо от вашего желания помните, что operator[] не является const– методом: всегда есть вероятность того, что он изменит состояние map, добавив узел.

Метод insert предоставляет альтернативный метод добавления пар в отображение, insert выполняет строгую вставку, а не вставку/обновление, как operator[]. При использовании map (но не multimap, который может содержать дублирующиеся ключи) insert, если ключ уже существует, не делает ничего. По сравнению с ним operator[], если ключ уже существует, заменяет значение объекта для этого ключа на новое.

Но синтаксис вставки требует несколько большей работы, чем operator[], и он связан с тем, как map хранит данные. Рассмотрим строку из примера 6.6.