• Главная
• Контакты
• Нашёл ошибку
• Прислать материал
• Добавить в избранное

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

set

map

map

multimap

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

В STL отсутствуют контейнеры на базе хэш-таблиц, поэтому глава завершается примерами двух распространенных (хотя и нестандартных) реализаций. Несмотря на отсутствие хэш-таблиц в STL, вам не придется реализовывать их самостоятельно или обходиться другими контейнерами. Существует немало готовых качественных реализаций.

Задача сравнения объектов возникает в STL очень часто. Например, если функция

find

set::insert

Алгоритм

find

set::insert

find

==

set::insert

<

Формальное определение равенства основано на использовании оператора

==

x==y

true

x

y

false

Widget

class Widget {

public:

 …

private:

 TimeStamp lastAccessed;

};

Для класса

Widget

==

bool operator==(const Widgets lhs, const Widgets rhs) {

 // Поле lastAccessed игнорируется

}

В этом случае два объекта

Widget

lastAccessed

Эквивалентность основана на относительном порядке значений объектов в отсортированном интервале. Проще всего рассматривать ее в контексте порядка сортировки, являющегося частью любого стандартного ассоциативного контейнера (то есть

set

multiset

map

multimap

x

y

c

c

set<Widget> s

Widget

w1

w2

s

s

set<Widget>

less<Widget>

operator<

Widget

w1

w2

operator<

!(w1<w2) // Условие w1 < w2 ложно

&&       // и

!(w2<w1)// Условие w2 < w1 ложно

Все вполне логично: два значения эквивалентны (по отношению к некоторому критерию упорядочения), если ни одно из них не предшествует другому в соответствии с данным критерием.

В общем случае функцией сравнения для ассоциативного контейнера является не оператор

<

less

key_comp

x

y

c

!c.key_comp()(x, y) && !c.key_comp()(y, x) // х не предшествует у

// в порядке сортировки с,

// а у не предшествует х

Выражение

!c.key_comp()(x,y)

c.key_comp()

key_comp

x

y

с.keycomp()(х, у)

true

x

y

!с.key_comp()(х, у)

x

y

c

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

set<string>

set<string>

ciStringCompare

set

()

ciStringCompare

struct CiStringCompare:                // Класс сравнения строк

public                                 // без учета регистра символов;

binary_function<string, string, bool>{ // описание базового класса

                                       // приведено в совете 40

bool operator() (const string& lhs, const string& rhs) const {

 return ciStringCompare(lhs, rhs); // Реализация ciStringCompare

                                   // приведена в совете 35

 }

};

При наличии

CiStringCompare

set<string>

set<string, CIStringCompare> ciss;

Теперь при вставке строк «Persephone» и «persephone» в множество будет включена только первая строка, поскольку вторая считается эквивалентной:

ciss.insert("Persephone"); // В множество включается новый элемент

ciss.insert("persephone"); // Эквивалентный элемент не включается

Если теперь провести поиск строки «persephone» функцией

set::find

if(ciss.find("persephone")!=ciss.end())... // Элемент найден

Но если воспользоваться внешним алгоритмом

find

if (find(ciss.begin(), ciss.end(),

 "persephone")!=ciss.end())… // Элемент отсутствует

Дело в том, что строка «persephone» эквивалентна«Persephone» (по отношению к функтору сравнения

CIStringCompare

string("persephone") !=string("Persephone")

set::find

find

Возникает вопрос — почему же в работе стандартных ассоциативных контейнеров используется понятие эквивалентности, а не равенства? Ведь большинству программистов равенство кажется интуитивно более понятным, чем эквивалентность (в противном случае данный совет был бы лишним). На первый взгляд ответ кажется простым, но чем дольше размышляешь над этим вопросом, тем менее очевидным он становится.

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

less

equal_to

equal_to

==

find

Допустим, у нас имеется контейнер

set2CF

образцу

set2CF<string, CIStringCompare, equal_to<string> > s;

Контейнер

s

s

s.insert("Persephone");

s.insert("persephone");

Как поступить в этом случае? Если контейнер поймет, что

"Persephone" != "persephone"

s

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

multiset

multimap

multiset

multimap

s

if (s.find("persephone") != s.end())… // Каким будет результат проверки?

Функция

find

insert

s

Мораль: используя одну функцию сравнения и принимая решение о «совпадении» двух значений на основании их эквивалентности, мы избегаем многочисленных затруднений, возникающих при использовании двух функций сравнения. Поначалу такой подход выглядит несколько странно (особенно когда вы видите, что внутренняя и внешняя версии

find

Но стоит отойти от сортированных ассоциативных контейнеров, как ситуация изменяется, и проблему равенства и эквивалентности приходится решать заново. Существуют две общепринятые реализации для нестандартных (но широко распространенных) ассоциативных контейнеров на базе хэш-таблиц. Одна реализация основана на равенстве, а другая — на эквивалентности. В совете 25 приводится дополнительная информация об этих контейнерах и тех принципак, на которых они основаны.

Предположим, у нас имеется контейнер

set

string*

set<string*> ssp; // ssp = "set of string ptrs"

ssp.insert(new string("Anteater"));

ssp.insert(new string("Wombat"));

ssp.insert(new string("Lemur"));

ssp.insert(new string("Penguin"));

Следующий фрагмент выводит содержимое

set

set

for (set<string*>::const_iterator i = ssp.begin(); // Предполагаемый

 i!=ssp.end();                                     // порядок вывода:

 ++i)                                              // "Anteater", "Lemur"

 cout << *i << endl;                               // "Penguin", "Wombat"

Однако на практике ничего похожего не происходит. Вместо строк выводятся четыре шестнадцатеричных числа — значения указателей. Поскольку в контейнере

set

*i

copy

copy(ssp.begin(), ssp.end(),           // Скопировать строки.

 ostream_iterator<string>(cout,"\n")); //содержащиеся в ssp, в cout

                                       //(не компилируется!)

не только делает программу более компактной, но и помогает быстрее обнаружить ошибку, поскольку вызов

copy

ostream_iterator

string

ssp(string*)

Если заменить

*i

**i

ssp

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

set<string*> ssp;

представляет собой сокращенную запись для объявления

set<string*, less<string*> > ssp;

Строго говоря, это сокращенная запись для объявления

set<string*, less<string*>, allocator<string*> > ssp;

но в контексте данного совета распределители памяти несущественны.

Если вы хотите сохранить указатели

string*

set

less<string*>

string*

struct StringPtrLess:

 public binary_function<const string*, // Базовый класс

 const string*,                        // описан в совете 40

 bool> {

 bool operator() (const string *ps1, const string *ps2) const {

  return *ps1 < *ps2:

 }

};

После этого

StringPtrLess

ssp

typedef set<string*, StringPtrLess> StringPtrSet;

StringPtrSet ssp; // Создать множество с объектами string

                  // и порядком сортировки, определяемым

                  // критерием StringPtrLess

                  // Вставить те же четыре строки

Теперь приведенный выше цикл будет работать именно так, как предполагалось (при условии, что ошибка была исправлена и вместо

*i

**i

for (StringPtrSet::const_iterator i = ssp.begin();

 i != ssp.end();      // Порядок вывода:

 ++i)                 // "Anteater", "Lemur",

 cout << **i << endl; // "Penguin", "Wombat"

Если вы предпочитаете использовать алгоритм, напишите функцию, которая разыменовывает указатели

string*

for_each

void print(const string *ps) // Вывести в cout объект,

{                            // на который ссылается ps

 cout << *ps << endl;

}

for_each(ssp.begin(), ssp.end(), print); // Вызвать print для каждого

                                         // элемента ssp

Существует более изощренное решение — обобщенный функтор разыменования, используемый с

transform

ostream_iterator

// Функтор получает T* и возвращает const T&

struct Dereference {

 template<typename T>

 const T& operator()(const T* ptr) const {

  return *ptr;

 }

};

transform(ssp.begin(), ssp.end(),      // "Преобразовать" каждый

 ostream.iterator<string>(cout, "\n"), // элемент ssp посредством

 Dereference());                       // разыменования и записать

                                       // результаты в cout

Впрочем, замена циклов алгоритмами будет подробно рассматриваться позднее, в совете 43. А сейчас речь идет о том, что при создании стандартного ассоциативного контейнера указателей следует помнить: содержимое контейнера будет сортироваться по значениям указателей. Вряд ли такой порядок сортировки вас устроит, поэтому почти всегда определяются классы-функторы, используемые в качестве типов сравнения.

Обратите внимание на термин «тип сравнения». Возможно, вас интересует, зачем возиться с созданием функтора вместо того, чтобы просто написать функцию сравнения для контейнера

set

bool stringPtrLess(const string* ps1, // Предполагаемая функция сравнения

 const string* ps2)                   // для указателей string*,

{                                     // сортируемых по содержимому строки

 return *ps1 < *ps2;

}

set<string, stringPtrLess> ssp; // Попытка использования stringPtrLess

                                // в качестве функции сравнения ssp.

// Не компилируется!!!

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

set

stringPtrLess

stringPtrLess

set

set

Каждый раз, когда вы создаете ассоциативный контейнер указателей, помните о том, что вам, возможно, придется задать тип сравнения контейнера. В большинстве случаев тип сравнения сводится к разыменованию указателя и сравнению объектов, как это сделано в приведенном выше примере

StringPtrLess

struct DereferenceLess {

 template <typename PtrType>

 bool operator()(PtrType pT1, // Параметры передаются по значению.

  PtrType рТ2) const          // поскольку они должны быть

 {                            // указателями (или по крайней мере

  return *рТ1 < *рТ2;         // вести себя, как указатели)

 }

};

Данный шаблон снимает необходимость в написании таких классов, как

StringPtrLess

DereferenceLess

set<string*, DereferenceLess> ssp; // Ведет себя так же, как

                                   // set<string*, stringPtrLess>

И последнее замечание. Данный совет посвящен ассоциативным контейнерам указателей, но он в равной степени относится и к контейнерам объектов, которые ведут себя как указатели (например, умные указатели и итераторы). Если у вас имеется ассоциативный контейнер умных указателей или итераторов, подумайте, не стоит ли задать тип сравнения и для него. К счастью, решение, приведенное для указателей, работает и для объектов-аналогов. Если определение

DereferenceLess

T*

T

Сейчас я покажу вам нечто любопытное. Создайте контейнер

set

less_equal

set<int, less_equal<int> > s; // Контейнер s сортируется по критерию "<="

s.insert(10); // Вставка числа 10

Теперь попробуйте вставить число 10 повторно:

s.insert(10);

При этом вызове

insert

Контейнер перебирает свои внутренние структуры данных и ищет место для вставки 10_B. В итоге ему придется проверить 10_A и сравнить его с 10_B. Для ассоциативного контейнера «сравнение» сводится к проверке эквивалентности (см. совет 19), поэтому контейнер проверяет эквивалентность объектов 10_A и 10_B. Естественно, при этой проверке используется функция сравнения контейнера

set

operator<=

less_equal

less_equal

operator<=

!(10a<=10b)&&!(10b<=10a) // Проверка эквивалентности 10_A и 10_B

Оба значения, 10_A и 10_B, равны 10, поэтому условие 10_A<=10_B заведомо истинно. Аналогично истинно и условие 10_B<=10_A. Приведенное выше выражение упрощается до

!(true)&&!(true)

false&&false

false

set

set

less_equal

true

Мораль: всегда следите за тем, чтобы функции сравнения для ассоциативных контейнеров возвращали

false

Например, в совете 20 рассказано о том, как написать функцию сравнения для контейнеров указателей

string*

struct StringPtrGreater:

 public binary_function<const string*, // Жирным шрифтом выделены

 const string*,                        // изменения, внесенные в код

 bool> {                               // из совета 20.

                                       // Внимание - приведенное решение

                                       // не работает!

 bool operator()(const string *ps1, const string *ps2) const {

  return !(*ps1 < *ps2); // Простое логическое отрицание

 }                       // старого условия не работает!

};

Идея заключается в том, чтобы изменить порядок сортировки логическим отрицанием условия в функции сравнения. К сожалению, отрицанием операции «

<

>

>=

>=

true

Правильный тип сравнения должен выглядеть так:

struct StringPtrGreater:               // Правильный тип сравнения

 public binary_function<const string*, // для ассоциативных контейнеров

 const string*, bool> {

 bool operator() (const string *ps1, const string *ps2) const {

  return *ps2<*ps1;// Поменять местами операнды

 }

};

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

false

Я знаю, о чем вы думаете. «Конечно, это имеет смысл для

set

map

multiset

multimap

Нет, неверно. Давайте вернемся к исходному примеру, но на этот раз воспользуемся контейнером

multiset

multiset<int, less_equal<int> > s; // s сортируется по критерию "<="

s.insert(10);// Вставка числа 10_A

s.insert(10);// Вставка числа 10_B

Теперь

s

equal_range

equal_range

s

equal_range

Ну что, убедились? Функция сравнения всегда должна возвращать false для равных величин, в противном случае нарушается работа всех стандартных ассоциативных контейнеров (независимо от того, могут они содержать дубликаты или нет).

Строго говоря, функции сравнения, используемые для сортировки ассоциативных контейнеров, должны определять для сравниваемых объектов порядок строгой квазиупорядоченности (strict weak ordering); аналогичное ограничение действует и для функций сравнения, передаваемых алгоритмам, — таким, как

sort

false

Понять смысл этого совета нетрудно. Контейнеры

set/multiset

Сказанное прежде всего касается контейнеров

map

multimap

map<int, string> m;

…

m.begin()->first = 10; // Ошибка! Изменение ключей

                       // в контейнере map запрещено

multimap<int, string> mm;

mm.begin()->first = 20; // Ошибка! Изменение ключей

                        // в контейнере multimap запрещено

Дело в том, что элементы объекта типа

map<K, V>

multimap<K, V>

pair<const K, V>

const K

const_cast

Обратите внимание: в заголовке этого совета ничего не сказано о контейнерах 

map

multimap

map

multimap

const_cast

set

multiset

set<T>

multiset<T>

T

const T

set

l

const_cast

Сначала выясним, почему элементы

set

multiset

const

Employee

class Employee {

public:

 …

 const string& name() const; // Возвращает имя работника

 void setName(const string& name); // Задает имя работника

 const string& title() const; // Возвращает должность

 void setTitle(const string& title); // Задает должность

 int idNumber() const; // Возвращает код работника

 …

}

Объект содержит разнообразные сведения о работнике. Каждому работнику назначается уникальный код, возвращаемый функцией

idNumber

set

Employee

struct IDNumberLess:

 public binary_function<Employee, Employee, bool> { // См. совет 40

 bool operator() (const Employees lhs, const Employees rhs) const {

  return lhs.idNumber() < rhs. IdNumber();

 }

}

typedef set<Employee, IDNumberLess> EmplIDSet;

EmplIDSet se; // Контейнер set объектов

              // Employee, упорядоченных

              // по коду

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

Employee selectedID; // Объект работника с заданным кодом

…

EmpIDSet::iterator = se.find(selectedID);

if (i!=se.end()) {

 i->setTitle("Corporate Deity"); // Изменить должность

}

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

Спрашивается, почему нельзя применить ту же логику к ключам контейнеров

map

multimap

map

IDNumberLess

Откровенно говоря, мне это кажется вполне логичным, однако мое личное мнение в данном случае несущественно. Важно то, что Комитет по стандартизации решил, что ключи

map/multimap

const

set/multiset

Значения в контейнерах

set/multiset

set/multiset

Впрочем, не все так просто. Хотя элементы

set/multiset

*

set<T>::iterator

const T&

set

const

set

multiset

const

Законны ли такие реализации? Может, да, а может — нет. По этому вопросу Стандарт высказывается недостаточно четко, и в соответствии с законом Мерфи разные авторы интерпретируют его по-разному. В результате достаточно часто встречаются реализации STL, в которых следующий фрагмент компилироваться не будет (хотя ранее говорилось о том, что он успешно компилируется):

EmplIDSet se; // Контейнер set объектов

              // Employee, упорядоченных

              // по коду

Employee selectedID; // Объект работника с заданным кодом

…

EmpIDSet::iterator = se.find(selectedID);

if (i!=se.end()) {

 i->setTitle("Corporate Deity"); // Некоторые реализации STL

};                               // выдают ошибку в этой строке

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

set

multiset

Что из этого следует? К счастью, ничего особенно сложного:

• если переносимость вас не интересует, если вы хотите изменить значение элемента в контейнере

set/multiset

• если программа должна быть переносимой, элементы контейнеров

set/multiset

const_cast

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

set/multiset

setTitle

EmpIDSet::iterator i = se.find(selectedID);

if (i != se.end()) {

 i->setTitle("Corporate Deity"); // Некоторые реализации STL

}                                // выдают ошибку в этой строке,

                                 // поскольку *i имеет атрибут const

Чтобы этот фрагмент нормально компилировался и работал, необходимо устранить константность

*i

if (i != se.end()){                                     // Устранить

 const_cast<Empioyee&>(*i).setTitle("Corporate Deity"); // константность *i

}

Мы берем объект, на который ссылается

i

Employee

setTitle

Многие программисты пытаются воспользоваться следующим кодом:

if (i != se.end()){                                     // Преобразовать *i

 static_cast<Employee>(*i).setTitle("Corporate Deity"); // к Employee

}

Приведенный фрагмент эквивалентен следующему:

if (i != se.end()){                            // То же самое,

 ((Employee)(*i)).setTitle("Corporate Deity"); // но с использованием

}                                              // синтаксиса С

Оба фрагмента компилируются, но вследствие эквивалентности работают неправильно. На стадии выполнения объект

*i

*i

setTitle

*i

if (i != se.end()) {

 Employee tempCopy(*i);                // Скопировать *i в tempCopy

 tempCopy.setTitle("Corporate Deity"); // Изменить tempCopy

}

Становится понятно, почему преобразование должно приводить именно к ссылке — тем самым мы избегаем создания нового объекта. Вместо этого результат преобразования представляет собой ссылку на существующийобъект, на который указывает

i

setTitle

*i

Все сказанное хорошо подходит для контейнеров set и multiset, но при переходе к map/multimap ситуация усложняется. Вспомните, что

map<K, V>

multimap<K, V>

pair<const K, V>

const

map

multimap

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

Многие преобразования (включая только что рассмотренные) не являются абсолютно необходимыми. Самый безопасный и универсальный способ модификации элементов контейнера

set

multiset

map

multimap

1. Найдите элемент, который требуется изменить. Если вы не уверены в том, как сделать это оптимальным образом, обратитесь к рекомендациям по поводу поиска в совете 45.

2. Создайте копию изменяемого элемента. Помните, что для контейнеров

map/multimap

3. Удалите элемент из контейнера. Обычно для этого используется функция

erase

4. Измените копию и присвойте значение, которое должно находиться в контейнере.

5. Вставьте новое значение в контейнер. Если новый элемент в порадке сортировки контейнера находится в позиции удаленного элемента или в соседней позиции, воспользуйтесь «рекомендательной» формой

insert

EmpIDSet se; // Контейнер set объектов Employee, упорядоченных по коду

Employee SelectedID; // Объект работника с заданным кодом

…

EmpIDSet::iterator i = // Этап 1: поиск изменяемого элемента

 se.find(selectedID);

if (i != se.end()) {

 Employee e(*i); //Этап 2: копирование элемента

 se.erase(i++); // Этап 3: удаление элемента.

                // Увеличение итератора

                // сохраняет его

                // действительным (см. совет 9)

 e.setTitle("Corporate Deity"); // Этап 4: модификация копии

 se.insert(i, е); // Этап 5: вставка нового значения.

                  // Рекомендуемая позиция совпадает

                  // с позицией исходного элемента

}

Итак, при изменении «на месте» элементов контейнеров

set

multiset

Многие программисты STL, столкнувшись с необходимостью структуры данных с быстрым поиском, немедленно выбирают стандартные ассоциативные контейнеры set ,

multiset , map и multimap

set

map

multi

Даже если гарантированное логарифмическое время поиска вас устраивает, стандартные ассоциативные контейнеры не всегда являются лучшим выбором. Как ни странно, стандартные ассоциативные контейнеры по быстродействию нередко уступают банальному контейнеру

vector

vector

Стандартные ассоциативные контейнеры обычно реализуются в виде сбалансированных бинарных деревьев. Сбалансированное бинарное дерево представляет собой структуру данных, оптимизированную для комбинированных операций вставки, удаления и поиска. Другими словами, оно предназначено для приложений, которые вставляют в контейнер несколько элементов, затем производят поиск, потом вставляют еще несколько элементов, затем что-то удаляют, снова возвращаются к удалению или вставке и т. д. Главной особенностью этой последовательности событий является чередование операций вставки, удаления и поиска. В общем случае невозможно предсказать следующую операцию, выполняемую с деревом.

Во многих приложениях структуры данных используются не столь непредсказуемо. Операции со структурами данных делятся на три раздельные фазы.

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

2. Поиск. Выборка нужных данных из структуры. В этой фазе выполняются только операции поиска. Вставка и удаление выполняются редко или полностью отсутствуют.

3. Реорганизация. Модификация содержимого структуры данных (возможно, со стиранием всего текущего содержимого и вставкой новых элементов). По составу выполняемых операций данная фаза эквивалентна фазе 1. После ее завершения приложение возвращается к фазе 2.

В приложениях, использующих эту схему работы со структурами данных, контейнер

vector

vector

vector

binary_search

lower_bound

equal_range

Начнем с размера. Допустим, нам нужен контейнер для хранения объектов

Widget

Widget

vector<Widget>

Widget

Widget

С другой стороны, при сохранении

Widget

vector

vector

int

Большие структуры данных разбиваются на несколько страниц памяти, однако для хранения

vector

vector

Widget

Widget

Widget

vector

Widget

vector

В действительности я несколько оптимистично подошел к ассоциативным контейнерам — приведенное описание предполагает, что узлы бинарных деревьев сгруппированы в относительно малом наборе страниц памяти. В большинстве реализаций STL подобная группировка достигается при помощи нестандартных диспетчеров памяти, работающих поверх распределителей памяти контейнеров (см. советы 10 и И), но если реализация не следит за локализованностью ссылок, узлы могут оказаться разбросанными по всему адресному пространству. Это приведет к росту числа подгрузок страниц. Даже при использовании группирующих диспетчеров памяти в ассоциативных контейнерах обычно чаще возникают проблемы с подгрузкой страниц, поскольку узловым контейнерам, в отличие от блоковых (таких как vector), труднее обеспечить близкое расположение соседних элементов контейнера в физической памяти. Однако именно эта организация памяти сводит к минимуму подгрузку страниц при выполнении бинарного поиска.

Мораль: данные, хранящиеся в сортированном векторе, обычно занимают меньше памяти, чем те же данные в стандартном ассоциативном контейнере; бинарный поиск в сортированном векторе обычно происходит быстрее, чем поиск в стандартном ассоциативном контейнере (с учетом подгрузки страниц).

Конечно, сортированный

vector

vector

vector

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

vector

set

vector<Widget> vw; // Альтернатива для set<Widget>

…                  // Подготовительная фаза: много вставок,

                   // мало операций поиска

sort(vw.begin(), vw.end()); // Конец подготовительной фазы (при эмуляции

                            // multiset можно воспользоваться

                            // алгоритмом stable_sort - см. совет 31).

Widget w;// Объект с искомым значением

…        // Начало фазы поиска

if (binary_search(vw.begin(), vw.end(), w))… // Поиск с применением

                                             // binary_search

vector<Widget>::iterator i =

 lower_bound(vw.begin(), vw.end(), w); // Поиск с применением

if (i != vw.end() && !(*i < w))…       // lower_bound: конструкция

                                       // !(*i<w)) описана в совете 45

pair<vector<Widget>::iterator, vector<Widget>::iterator> range =

 equal_range(vw.begin(), vw.end(), w); // Поиск с применением

if (range.first != range.second)…      // equal_range

… // Конец фазы поиска,

  // начало фазы реорганизации

sort(vw.begin(), vw.end()); // Начало новой фазы поиска…

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

binary_search

lower_bound

При переходе от

map/multimap

vector

vector

pair

map/multimap

map<K, V>

multimap

pair<const K, V>

map

multimap

vector

map<K, V>

pair<K, V>

pair<const K, V>

Содержимое

map/multimap

vector

<

pair

Интересно заметить, что для выполнения поиска требуется вторая функция сравнения. Функция сравнения, используемая при сортировке, получает два объекта

pair

pair

pair

pair

typedef pair<string, int> Data; // Тип, хранимый в "map" в данном примере

class DataCompare{ // Класс для функций сравнения

public:

 bool operator()(constData& lhs, // Функция сравнения

  constData& rhs) const          // для сортировки

 {

  return keyLess(lhs.first, rhs.first); // Определение keyLess

 }                                      // приведено ниже

 bool operator()(const Data& lhs,  // Функция сравнения

  const Data::first_type& k) const // для поиска (форма 1)

 {

  return keyLess(lhs.first, rhs.first);

 }

 bool operator()(const Data::first_type& k, // Функция сравнения

  const Data& rhs) const;                   // для поиска (форма 2)

 {

  return keyLess(k.rhs.first);

 }

private:                                  // "Настоящая" функция

 bool keyLess(const Data::first_type& k1, // сравнения

  const Data::first_type& k2) const {

  return k1 < k2;

 }

}

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

map<string, int>

keyLess

operator()

keyLess

operator()

DataCompare

operator()

Контейнер

map

set

DataCompare

vector<Widget> vd; // Альтернатива для map<string, int>

…                  // Подготовительная фаза: много вставок,

                   // мало операций поиска

sort(vd.begin(), vd.end(), DataCompare()); // Конец подготовительной фазы

                                           // (при эмуляции multiset можно

                                           // воспользоваться алгоритмом

                                           // stable_sort - см. совет 31)

string s; // Объект с искомым значением

… // Начало фазы поиска

if (binary_search(vd.begin(), vd.end(), s, DataCompare()))… // Поиск

                                                            // с применением binary_search

vector<Data>::iterator i = lower_bound(vd.begin(), vd.end().s,

 DataCompare());                       // Поиск с применением

if (i != vd.end() && !(i->first < s))… // lower_bound: конструкция

                                       //!(i->first<s)) описана

                                       //в совете 45

pair<vector<Data>::iterator, vector<Data>::iterator> range =

 equal_range(vd.begin(), vd.end(), s, DataCompare()); //  Поиск с применением

if (range.first != range.second)…                     // equal_range

… // Конец фазы поиска,

  // начало фазы реорганизации

sort(vd.begin(), vd.end(), DataCompare()); //Начало новой фазы поиска…

Как видите, после написания

DataCompare

map

Допустим, у нас имеется класс

Widget

class Widget {

public:

 Widget();

 Widget(double weight);

 Widget& operator=(double weight);

 …

};

Предположим, мы хотим создать контейнер

map

int

Widget

map<int, Widget> m;

m[1]=1.50;

m[2]=3.67;

m[3]=10.5;

m[4]=45.8;

m[5]=0.0003;

Настолько просто, что легко упустить, что же здесь, собственно, происходит. А это очень плохо, потому что в действительности происходящее может заметно ухудшить быстродействие программы.

Функция

operator[]

map

operator[]

vector

deque

string

[]

map::operator[]

map<K, V> m

m[k]=v;

k

v

v

Для этого

operator[]

k

operator[]

k

operator[]

Вернемся к началу исходного примера:

map<int, Widget> m;

m[1]=1.50;

Выражение

m[1]

m.operator[](1)

map::operator[]

Widget

m

Widget

Widget

Иначе говоря, команда

m[1]=1.50:

функционально эквивалентна следующему фрагменту:

typedef map<int, Widget> intWidgetMap; // Вспомогательное определение типа

pair<intWidgetMap::iterator, bool> result =       // Создание нового

 m.insert(intWidgetMap::value_type(1, Widget())); // элемента с ключом 1

                                                  // и ассоциированным объектом, созданным

                                                  // конструктором по умолчанию; комментарии

                                                  // по поводу value_type

                                                  // приведены далее

result.first->second = 1.50; // Присваивание значения

                             // созданному объекту

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

Widget

Widget

Widget

operator[]

insert

m.insert(intWidgetMap::value_type(1, 1.50));

С функциональной точки зрения эта конструкция эквивалентна фрагменту, приведенному выше, но она позволяет сэкономить три вызова функций: создание временного объекта

Widget

Widget

map::insert

map::operator[]

В приведенном выше фрагменте используется определение типа

value_type

map

multimap

hash_map

hash_multimap

pair

Я уже упоминал о том, что

operator[]

operator[]

map

m[k] = v; // Значение, ассоциируемое

          // с ключом k, заменяется на v при помощи оператора []

m.insert(intWidgetMap::value_type(k, v)).first->second = v; // Значение, ассоциируемое

                                                            // с ключом k, заменяется

                                                            // на v при помощи insert

Вероятно, один внешний вид этих команд заставит вас выбрать

operator[]

При вызове

insert

inWidgetMap::value_type

pair<int, Widget>

insert

insert

pair

Widget

pair<int, Widget>

Widget

operator[]

pair

pair

Widget

Следовательно, при вставке элемента в

map

insert

operator[]

operator[]

Конечно, нам хотелось бы видеть в STL функцию, которая бы автоматически выбирала оптимальное решение в синтаксически привлекательном виде. Интерфейс вызова мог бы выглядеть следующим образом:

iterator affectedPair =        // Если ключ к отсутствует в контейнере m,

 efficentAddOrUpdate(m, k, v); // выполнить эффективное добавление

                               // pair(k, v) в m; в противном случае

                               // выполнить эффективное обновление

                               // значения, ассоциированного с ключом k.

                               // Функция возвращает итератор

                               // для добавленной или измененной пары

В STL такая функция отсутствует, но как видно из следующего фрагмента, ее нетрудно написать самостоятельно. В комментариях даются краткие пояснения, а дополнительная информация приведена после листинга.

template<typename МарТуре, // Тип контейнера

 typename KeyArgType,      // Причины для передачи параметров-типов

 typename ValueArgType>    // KeyArgType и ValueArgType

                           // приведены ниже

typename МарТуре::iterator efficientAddOrUpdate(MapType& m,

 const KeyArgType& k, const ValueArgType& v) {

 typename МарТуре:iterator lb = // Определить, где находится

                                // или должен находиться ключ k.

  m.lower_bound(k);             // Ключевое слово typename

                                // рассматривается на с. 20

 if (lb != m.end())&& !(m.key_comp()(k.lb->first))){ // Если lb ссылается на пару,

                                                     // ключ которой эквивалентен k,

  lb->second = v;                                    // …обновить ассоциируемое значение

  return lb;                                         // и вернуть итератор для найденной пары

 } else {

  typedef typename МарТуре::value_type MVT;

  return m.insert(lb.MVT(k, v)); // Включить pair(k, v) в m и вернуть

                                 // итератор для нового элемента

 }

}

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

lower_bound

lower_bound

map::keycomp

Обновление реализовано весьма прямолинейно. С созданием дело обстоит поинтереснее, поскольку в нем используется «рекомендательная» форма

insert

m.insert(lb.MVT(k, v))

lb

k

efficentAddOrUpdate

lb

insert

У данной реализации есть одна интересная особенность —

KeyArgType

ValueArgType

KeyArgType/ValueArgType

МарТуре::key_type

МарТуре::mapped_type

map

map<int, Widget> m; // См. ранее

Также вспомним, что Widget допускает присваивание значений типа

double

class Widget { // См. ранее

public:

 Widget& operator=(double weight);

};

Теперь рассмотрим следующий вызов

efficientAddOrUpdate

effcientAddOrUpdate(m, 10, 15);

Допустим, выполняется операция обновления, то есть

m

ValueArgType

double

double

Widget

Widget::operator=(double)

efficientAddOrUpdate

МарТуре::mapped_type

Widget

Widget

Сколь бы интересными не были тонкости реализации

efficientAddOrUpdate

map::operator[]

map::insert

map

[]

insert

После первого знакомства с STL у большинства программистов неизбежно возникает вопрос: «Векторы, списки, множества… хорошо, но где же хэш-таблицы?» Действительно, хэш-таблицы не входят в стандартную библиотеку C++. Все сходятся на том, что это досадное упущение, но Комитет по стандартизации C++ решил, что усилия, затраченные на их поддержку, привели бы к чрезмерной задержке в работе над стандартом. По всей вероятности, хэш-таблицы появятся в следующей версии Стандарта, но в настоящий момент хеширование не поддерживается в STL.

Программисты, не печальтесь! Вам не придется обходиться без хэш-таблиц или создавать собственные реализации. Существует немало готовых STL-совместимых хэшированных ассоциативных контейнеров с вполне стандартными именами:

hash_set

hash_multiset

hash_map

hash_multimap

Реализации, скрытые за похожими именами… мягко говоря, не похожи друг на друга. Различается все: интерфейсы, возможности, структуры данных и относительная эффективность поддерживаемых операций, Можно написать более или менее переносимый код, использующий хэш-таблицы, но стандартизация хэшированных контейнеров значительно упростила бы эту задачу (теперь понятно, почему стандарты так важны),

Из всех существующих реализаций хэшированных контейнеров наибольшее распространение получили две: от SGI (совет 50) и от Dinkumware (приложение Б), поэтому дальнейшее описание ограничивается устройством хешированных контейнеров от этих разработчиков. STLport (совет 50) также содержит хэшированные контейнеры, но они базируются на реализации SGI. В контексте настоящего примера все сказанное о хэшированных контейнерах SGI относится и к хэшированным контейнерам STLport.

Хэшированные контейнеры относятся к категории ассоциативных, поэтому им, как и всем остальным ассоциативным контейнерам, при объявлении следует задать тип объектов, хранящихся в контейнере, функцию сравнения для этих объектов и распределитель памяти. Кроме того, для работы хэшированному контейнеру необходима хэш-функция. Естественно предположить, что объявление хэшированного контейнера должно выглядеть примерно так:

template<typename T, typename HashFunction, typename CompareFunction,

 typename Allocator = allocator<T> >

class hash_контейнер;

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

HashFunction

CompareFunction

hash_set

template<typename T,

 typename HashFunction = hash<T>,

 typename CompareFunction = equal_to<T>,

 typename Allocator = allocator<T> >

class hash_set;

В реализации SGI следует обратить внимание на использование

equal_to

less

В реализации Dinkumware принят несколько иной подход. Она также позволяет задать тип объектов, хэш-функцию, функцию сравнения и распределитель, но хэш-функция и функция сравнения по умолчанию перемещены в отдельный класс

hash_compare

HashingInfo

Например, объявление

hash_set

template<typename T, typename CompareFunction>

class hash_compare;

template<typename T,

 typename Hashinglnfo = hash_compare<T, less<T>>,

 typename Allocator = allocator<T>>

class hash_set;

В этом интерфейсе внимание стоит обратить на использование параметра

HashingInfo

После небольшого форматирования объявление

hash_compare

HashingInfo

template<typename T ,typename CompareFunction=less<T> >

class hash_compare {

public:

 enum {

  bucket_size = 4, // Максимальное отношение числа элементов к числу гнезд

  min_buckets = 8 // Минимальное количество гнезд

 }

 size_t operator()(const T&) const; // Хэш-функция

 bool operator() (const T&, const T&) const;

 … // Некоторые подробности опущены,

   // включая использование CompareFunction

};

Перегрузка

operator()

Реализация Dinkumware позволяет программисту написать собственный касс-аналог

hash_compare

hash_compare

bucket_size

min_buckets

operator()

hash_set

hash_multiset

hash_map

hash_multimap

Учтите, что в обоих вариантах все принятие решений можно поручить реализации и ограничиться объявлением следующего вида:

hash_set<int> intTable; // Создать хешированное множество int

Чтобы это объявление нормально компилировалось, хэш-таблица должна содержать данные целочисленных типов (например,

int

Принципы внутреннего устройства реализаций SGI и Dinkumware очень сильно различаются. В реализации SGI использована традиционная схема открытого хэширования с массивом указателей на односвязные списки элементов. В реализации Dinkumware используется двусвязный список. Различие достаточно принципиальное, поскольку оно влияет на категории итераторов, поддерживаемых этими реализациями. Хэшированные контейнеры SGI поддерживают прямые итераторы, что исключает возможность обратного перебора; в них отсутствуют такие функции, как

rbegin

rend

Какая из этих реализаций лучше подходит для ваших целей? Понятия не имею. Только вы можете ответить на этот вопрос, однако в этом совете я даже не пытался изложить все необходимое для принятия обоснованного решения. Речь идет о другом — вы должны знать, что несмотря на отсутствие хэшированных контейнеров непосредственно в STL, при необходимости можно легко найти STL-совместимые хэшированные контейнеры (с разными интерфейсами, возможностями и особенностями работы). Более того, в свободно распространяемых реализациях SGI и STLport вам за них даже не придется платить.

Примечания:

2

Строго говоря, не все 24 перестановки равновероятны, так что вероятность 1/24 не совсем точна. Тем не менее, остается бесспорный факт: существуют 24 разные перестановки, и вы можете получить любую из них.