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.

StrMap.insert(std::make_pair("Sunday", "Sonntag"));

Ma p хранит пары ключ/значение в объекте pair, pair — это простой вспомогательный шаблон класса (объявленный в <utility> и включенный в <map>), который хранит два значения двух типов. Чтобы объявить pair из двух string, сделайте так.

Pair<string, string> myPair;

Первый и второй элементы в pair доступны по открытым членам first и second. При использовании для доступа к элементам map оператора operator[] обычно работать с pair не приходится, но в случае со многими другими методами это придется делать, так что следует знать, как создавать и использовать объекты pair. Например, итераторы разыменовываются в простые объекты pair, так что при их использовании, как это делается в примере 6.6, следует знать, как получить ключ и его значение.

For (map<string, string> iterator p = strMap.begin();

 p != strMap.end(); ++p).

 cout << "English: " << p->first.

  << ", German: " << p->second << endl;

Ключ хранится в first, а значение хранится в second.

Однако это не объясняет, почему я использовал make_pair. make_pair — это вспомогательный шаблон функции, который создает объект pair на основе двух переданных в него аргументов. Некоторые предпочитают этот подход вызову конструктора pair, так как шаблон класса не может догадаться о типах своих аргументов, в то время как шаблон функции может. Таким образом, эти две строки кода функционально эквивалентны.

StrMap.insert(std::make_pair("Sunday", "Sonntag"));

StrMap.insert(std::pair<string, string>("Sunday", "Sonntag"));

Map не допускает наличия дублирующихся ключей. Если требуется разрешить дублирование ключей, следует использовать multimap, который является map, разрешающим наличие несколько одинаковых ключей. Его интерфейс идентичен map, но поведение методов в необходимых случаях отличается. В табл. 6.1 приведен перечень методов, которые есть в одном, но отсутствуют в другом, и пояснения различий в поведении общих методов, map и multimap содержат несколько typedef, которые описывают различные значения, хранящиеся в них. В табл. 6.1 они используются следующим образом:

Key_type.

Это тип ключа. В string map, объявленном как map<string, MyClass*>, key_type должен быть string.

Mapped_type.

Это тип значения, на которое отображается ключ. В string map, объявленном как map<string, MyClass*>, mapped_type должен быть MyClass*.

Value_type.

Это тип объекта, содержащего ключ и значение, которой, применительно к map и multimap, является pair<const key_type, mapped_type>.

Табл. 6.1. map и multimap.

Метод	map, multimap или оба	Поведение
T& operator[] (const key_type& k)	map	Возвращает ссылку на объект значения, сохраненный с ключом k. Если k в map отсутствует, то он добавляется, а объект значения создается с помощью конструктора по умолчанию
iterator insert(const value_type& v) pair<iterator, bool> insert(const value_type& v)	Оба	Первая версия вставляет v в multimap и возвращает итератор, который указывает на вставленную пару pair. Вторая версия вставляет v и map при условии, что в map еще не содержится ключа, равного v. Возвращаемая pair содержит итератор который указывает на вставленную pair, если произошла вставка, и bool, указывающий, была ли вставка успешной
iterator find(const key_type& k)	Оба	Возвращает итератор или const_iterator, который указывает на mapped_type, соответствующий k. В multimap не гарантируется, что возвращаемый итератор будет указывать на первое значение, соответствующее k. Если ключа, равного k, нет, то возвращаемый итератор равен end()

Также табл 6.1 показывает разницу в поведении между map и multimap.

Если operator[] вам не подходит, т.е. другой способ найти ключ в map. Для этого можно использовать метод find.

Map<string, string>::const_iterator p.

 = strMap.find("Thursday");

If (p != strMap.end()).

 cout << "Thursday = " << p->second << endl;

Но не забудьте, что при использовании multimap не гарантируется, что возвращаемый элемент будет первым элементом с ключом, равным искомому. Если нужен первый элемент, чей ключ не меньше определенного значения или не больше определенного значения, используйте lower_bound или upper_bound. lower_bound возвращает итератор, указывающий на первую пару ключ/значение, равную или большую, чем аргумент key_type. Другими словами, если ваш map содержит дни недели, как в примере 6.6, следующий код вернет итератор, который указывает на пару, содержащую "Friday" и "Freitag".

P = strMap.lower_bound("Foo");

If (p != strMap.end()).

 cout << p->first << " = " << p->second << endl;

Это происходит благодаря тому, что первый ключ больше или равен "Foo". upper_bound работает аналогично, но с противоположным условием.

В начале этого обсуждения я упоминал, что элементы в map хранятся в отсортированном по ключам порядке, так что при переборе от begin до end каждый элемент будет «больше», чем предшествующий (а в multimap — больше или равен ему) Но при использовании более сложных ключей, чем string или числа, может потребоваться указать, как при вставке элементов в отображение следует сравнивать ключи.

По умолчанию ключи хранятся с помощью стандартного функтора less (объявленного в <functional>). less — это двоичная функция (принимает два аргумента одинакового типа), которая возвращает bool, указывающий на то, больше ли первый аргумент, чем второй, или нет. Другими словами, less(a, b) возвращает a < b. Если это не то, что вам требуется, создайте свой собственный функтор и объявите map с его помощью. Например, если в качестве ключа используется объект Person и каждый Person имеет имя и фамилию, то может потребоваться сравнивать фамилии и имена. Пример 6.7 показывает способ сделать это.

Пример 6.7. Использование собственного функтора сортировки.

#include <iostream>

#include <map>

#include <string>

Using namespace std;

Class Person {

 friend class PersonLessThan;

Public:

 Person(const string& first, const string& last) :

  lastName_(last), firstName_(first) {}.

 // ...

 string getFirstName() const {return(firstName_);}.

 string getLastName() const {return(lastName_);}.

Private:

 string lastName_;

 string firstName_;

};

Class PersonLessThan {

Public:

 bool operator()(const Person& per1,

  const Person& per2) const {

  if (per1.lastName_ < per2. lastName_)      // Сравнить фамилии,

   return(true);                             // а затем.

  else if (per1.lastName_ == per2.lastName_) // имена.

   return(per1.firstName_ < per2.firstName_);

  else.

   return(false);

 }

};

Int main() {

 map<Person, string, PersonLessThan> personMap;

 Person per1("Billy", "Silly"),

  per2("Johnny", "Goofball"),

  per3("Frank", "Stank"),

  реr4("Albert", "Goofball");

 personMap[per1] = "cool";

 personMap[per2] = "not cool";

 personMap[per3] = "not cool";

 personMap[per4] = "cool";

 for (map<Person, string, PersonLessThan>::const_iterator p =

  personMap.begin(); p != personMap.end(); ++p) {

  cout << p->first.getFirstName() << " " << p->first.getLastName().

   << " is " << p->second << endl;

 }

}

Map — это прекрасный способ хранить пары ключ/значение. После того как вы поймете поведение его частей, таких как operator[] и хранение данных (в виде объектов pair<Key, Value>), map предоставит простоту в использовании и высокую производительность.

Смотри также.

Рецепт 6.7.