C++. Сборник рецептов полностью

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

По хеш-функциям и таблицам написано огромное количество книг. Если вы заинтересовались этим вопросом, поищите в 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 должен обеспечивать конструктор копирования и присвоение, и все.

Пример 6.10 показывает, как использовать set для строк. Использование набора для хранения объектов других типов работает точно так же — объявите набор с именем класса в качестве параметра шаблона.

std::set setMyObjs;

Это все, что требуется сделать для использования набора простейшим образом. Но в большинстве случаев жизнь не будет такой простой. Например, при сохранении в наборе указателей использовать предикат сортировки по умолчанию нельзя, так как он просто отсортирует объекты по их адресам. Чтобы гарантировать, что элементы будут отсортированы правильно, требуется создать собственный предикат, выполняющий сравнение «меньше чем». Пример 6.11 показывает, как это делается.

Пример 6.11. Хранение указателей в set

#include

#include

#include

#include

#include

using namespace std;

// Класс для сравнения строк, переданных через указатели

struct strPtrLess {

 bool operator()(const string* p1,

  const string* p2) {

  assert(p1 && p2);

  return(*p1 < *p2);

 }

 int main() (

  set setStrPtr; // Передаем специальный

                                      // «меньше чем» функтор

 string s1 = "Tom";

 string s2 = "Dick";

 string s3 = "Harry";

 setStrPtr.insert(&s1);

 setStrPtr.insert(&s2);

 setStrPtr.insert(&s3);