Также табл 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.
6.7. Использование хеш-контейнеров
Проблема
Требуется сохранить ключи и значения, обеспечив постоянное время доступа к элементам, и не требуется хранения элементов в упорядоченном виде.
Решение
Используйте один из связанных с хешами контейнеров — hash_map или hash_set. Однако помните, что они не входят в число стандартных контейнеров, определяемых стандартом С++, а представляют собой расширения, включаемые большинством реализаций стандартной библиотеки. Пример 6.8 показывает, как использовать hash_set.
Пример 6.8. Хранение строк в hash_set
#include <iostream>
#include <string>
#include <hash_set>
int main() {
hash_set<std::string> hsString;
string s = "bravo";
hsString.insert(s);
s = "alpha";
hsString.insert(s);
s = "charlie";
hsString.insert(s);
for (hash set<string>::const_iterator p = hsString.begin();
p != hsString.end(); ++p)
cout << *p << endl; // заметьте, что здесь не гарантируется хранение
// в упорядоченном виде
}
Обсуждение
Контейнеры, основанные на хешах, — это популярные во всех языках структуры данных, и прискорбно, что стандарт C++ не требует их реализации. Однако если требуется использовать хеш-контейнер, то не все потеряно: высока вероятность, что используемая вами реализация стандартной библиотеки содержит hash_map и hash_set, но тот факт, что они не стандартизованы, означает, что их интерфейсы могут отличаться от одной реализации стандартной библиотеки к другой. Я опишу хеш-контейнеры, которые поставляются в составе реализации стандартной библиотеки STLPort.
STLPort — это свободно распространяемая переносимая реализация стандартной библиотеки, существующая уже довольно длительное время и предоставляющая хеш-контейнеры. При использовании другой библиотеки интерфейс может быть другим, но общая идея будет той же самой.
Главной особенностью хеш-контейнеров (называемых во многих книгах по ассоциативными хеш-контейнерами) является то, что они в общем случае предоставляют постоянное время поиска, вставки и удаления элементов, а в худшем случае эти операции имеют линейное время. Ценой постоянного времени выполнения этих операций является то, что в хеш-контейнере они хранятся в неупорядоченном виде, как в map.
Посмотрите на пример 6.8. Использование хеш-контейнера (в данном случае hash_set) довольно просто — объявите его как большинство других контейнеров и начните вставлять в него элементы.
hash_set<string> hsString; // hash_set строк
string s = "bravo";
hsString.insert(s); // Вставка копии s
Использование hash_map аналогично, за исключением того, что требуется, как минимум, указать типы данных используемых ключей и значений. Это аналогично map.
hash_map<string, string>
hmStrings; // Отображение строк на строки
string key = "key";
string val = "val";
hmStrings[key] = val;
Это только основы использования хеш-контейнеров. Также имеется набор параметров шаблона, которые позволяют указать используемую хеш-функцию, функцию, проверяющую ключи на эквивалентность, и объект, используемый для распределения памяти. Я опишу их немного позже.
В большинстве библиотек есть четыре хеш-контейнера, и они похожи на другие ассоциативные контейнеры стандартной библиотеки (т.е. map и set). Это hash_map, hash_multimap, hash_set и hash_multiset. хеш-контейнеры реализуются с помощью хеш- таблицы. Хеш-таблица — это структура данных, которая обеспечивает постоянное время доступа к элементам, используя для этого хеш-функцию перехода к месту, близкому к хранению искомого объекта, а не проход по древовидной структуре. Разница между hash_map и hash_set состоит в том, как данные хранятся в хеш-таблице.
Объявления контейнеров, использующих хеш-таблицу, в STLPort выглядят так.
hash_map<Key, // Тип ключа
Value, // Тип значения,
// связанного с ключом
HashFun = hash<Key>, // Используемая хеш-функция
EqualKey = equal_to<Key> // Функция, используемая для
// проверки равенства ключей
Alloc = alloc>; // Используемый распределитель памяти
hash_set<Key, // Тип ключа
HashFun = hash<Key>, // Используемая хеш-функция
EqualKey = equal_to<Key>, // Функция, используемая для
// проверки равенства ключей
