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

При помещении элемента в хеш-таблицу она определяет, какому участку принадлежит элемент, используя оператор взятия остатка от деления и число участков, т.е. hashFun(key) % bucket_count(). Это быстрый оператор, который указывает непосредственно на индекс в главном векторе, по которому начинается участок.

Хеш-контейнер можно использовать как обычный ассоциативный контейнер, используя для добавления элементов в, скажем, hash_mapоператор operator[]. Разница заключается в том, что вы знаете, что вставка и поиск займут постоянное время, а не логарифмическое. Рассмотрим пример 6.9, который содержит простой класс, отображающий имена логинов на объекты Session. Он использует некоторые из возможностей хеш-контейнеров, описываемых в этом рецепте.

Пример 6.9. Простой менеджер сессий

#include

#include

#include

using namespace std;

class Session { /* ... */ };

// Облегчение читаемости с помощью typedef

typedef hash_map SessionHashMap;

class SessionManager {

public:

SessionManager() : sessionMap_(500) {} // Инициализация хеш-таблицы

// 500-ми участками

~SessionManager() {

for (SessionHashMap::iterator p = sessionMap_.begin();

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

delete (*p).second; // Удаление объекта Session

}

Session* addSession(const string& login) {

Session* p = NULL;

if (!(p = getSession(login))) {

p = new Session();

sessionMap_[login] = d; // Присвоение новой сессии с помощью

} // operator[]

return(p);

}

Session* getSession(const string& login) {

return(sessionMap_[login]);

}

// ...

private:

SessionHashMap sessionMap_;

};

Каждый ключ отображается на единственный участок, а в участке может храниться несколько ключей. Участок это обычно одно- или двухсвязный список.

По хеш-функциям и таблицам написано огромное количество книг. Если вы заинтересовались этим вопросом, поищите в Google «C++ hash function».

Рецепт 6.6.

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

Используйте ассоциативный контейнер set, объявленный в , который хранит элементы в упорядоченном виде. По умолчанию он использует стандартный шаблон класса less(который для своих аргументов вызывает operator<), а можно передать в него собственный предикат сортировки. Пример 6.10 показывает, как сохранить строки в set.

Пример 6.10. Хранение строк в set

#include

#include

#include

using namespace std;

int main() {

set setStr;

string s = "Bill";

setStr.insert(s);

s = "Steve";

setStr.insert(s);

s = "Randy";

setStr.insert(s);

s = "Howard";

setStr.insert(s);

for (set::const_iterator p = setStr.begin();

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

cout << *p << endl;

}

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

Bill

Howard

Randy

Steve

set(набор) — это ассоциативный контейнер, который предоставляет логарифмическую сложность вставки и поиска и постоянную сложность удаления элементов (если требуется удалить найденный элемент), set— это уникальный ассоциативный контейнер, что означает, что никакие два элемента не могут быть равны, однако если требуется хранить несколько экземпляров одинаковых элементов, используйте multiset, setможно представить как набор в математическом смысле, т.е. коллекцию элементов, в дополнение обеспечивающую поддержание определенного порядка элементов.

Поддерживаются вставка и поиск элементов, но, как и список, набор не позволяет производить произвольный доступ к элементам. Если требуется получить что-то из набора, то можно найти элемент с помощью метода findили перебрать элементы с помощью set::iteratorили set::const_iterator. Объявление набора имеет знакомый вид.

set

typename LessThanFun = std::less, // Функция/Функтор

// используемый для сортировки

typename Alloc = std::allocator > // Распределитель памяти

Указывать Keyтребуется всегда, иногда требуется предоставить собственную LessThanFun, а указывать собственный распределитель требуется очень редко (так что я не буду здесь его описывать).

Параметр шаблона Key— это, как и в случае с другими стандартными контейнерами, тип сохраняемых элементов. Для setон определяется через typedefкак set::key_type, так что доступ к нему есть при выполнении программы. Класс Keyдолжен обеспечивать конструктор копирования и присвоение, и все.