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

Когсуэлл Джефф

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

#include <iostream>

#include <string>

#include <hash_map>

using namespace std;

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

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

typedef hash_map<string, Session*> 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.

6.8. Хранение объектов в упорядоченном виде

Проблема

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

Решение

Используйте ассоциативный контейнер

set

, объявленный в

<set>

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

less

(который для своих аргументов вызывает

operator<

), а можно передать в него собственный предикат сортировки. Пример 6.10 показывает, как сохранить строки в

set

.

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

#include <iostream>

#include <set>

#include <string>

using namespace std;

int main {

 set<string> setStr;

 string s = "Bill";

 setStr.insert(s);

 s = "Steve";

 setStr.insert(s);

 s = "Randy";

 setStr.insert(s);

 s = "Howard";

 setStr.insert(s);

 for (set<string>::const_iterator p = setStr.begin;

p != setStr.end; ++p)

cout << *p << endl;

}

Так

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

Bill

Howard

Randy

Steve

Обсуждение

set

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

set

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

multiset

,

set

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

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

find

или перебрать элементы с помощью

set<T>::iterator

или

set<T>::const_iterator

. Объявление набора имеет знакомый вид.

set<typename Key, // Тип элемента

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

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

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

Указывать

Key

требуется всегда, иногда требуется предоставить собственную

LessThanFun

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

Параметр шаблона

Key

— это, как и в случае с другими стандартными контейнерами, тип сохраняемых элементов. Для

set

он определяется через

typedef

как

set<Key>::key_type

, так что доступ к нему есть при выполнении программы. Класс

Key

должен обеспечивать конструктор копирования и присвоение, и все.