Д. Стефенс - C++. Сборник рецептов

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

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

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

#include

#include

#include

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 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::const_iterator p =

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

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

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

}

}

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

Рецепт 6.7.

Требуется сохранить ключи и значения, обеспечив постоянное время доступа к элементам, и не требуется хранения элементов в упорядоченном виде.

Используйте один из связанных с хешами контейнеров — hash_mapили hash_set. Однако помните, что они не входят в число стандартных контейнеров, определяемых стандартом С++, а представляют собой расширения, включаемые большинством реализаций стандартной библиотеки. Пример 6.8 показывает, как использовать hash_set.

Пример 6.8. Хранение строк в hash_set

#include

#include

#include

int main() {

hash_set hsString;

string s = "bravo";

hsString.insert(s);

s = "alpha";

hsString.insert(s);

s = "charlie";

hsString.insert(s);

for (hash set::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 hsString; // hash_set строк

string s = "bravo";

hsString.insert(s); // Вставка копии s

Использование hash_mapаналогично, за исключением того, что требуется, как минимум, указать типы данных используемых ключей и значений. Это аналогично map.

hash_map

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

Value, // Тип значения,

// связанного с ключом

HashFun = hash, // Используемая хеш-функция

EqualKey = equal_to // Функция, используемая для

// проверки равенства ключей

Alloc = alloc>; // Используемый распределитель памяти

hash_set

HashFun = hash, // Используемая хеш-функция