Совет 19. Помните о различиях между равенством и эквивалентностью

Совет 20. Определите тип сравнения для ассоциативного контейнера, содержащего указатели

Совет 21. Следите за тем, чтобы функции сравнения возвращали false в случае равенства

Совет 22. Избегайте изменения ключа «на месте» в контейнерах set и multiset

Совет 23. Рассмотрите возможность замены ассоциативных контейнеров сортированными векторами

Совет 24. Тщательно выбирайте между map::operator[] и map::insert

Совет 25. Изучите нестандартные хэшированные контейнеры

Ассоциативные контейнеры

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

set

map

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

map

multimap

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

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

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

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

find

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

set::insert

должна проверить, не существует ли данное значение в контейнере.

Совет 19. Помните о различиях между равенством и эквивалентностью

Алгоритм

find

и функция

set::insert

являются типичными представителями семейства функций, проверяющих совпадение двух величин, однако делают это они по-разному. Для

find

совпадением считается равенство двух величин, проверяемое оператором

==

. Функция

set::insert

проверяет отношение эквивалентности, обычно основанное на операторе

<

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

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

==

. Если результат выражения

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

, а пользовательский предикат (см. совет 39). Каждый стандартный ассоциативный контейнер предоставляет свой предикат сортировки через функцию

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>

, в котором функция сравнения игнорирует регистр символов в строках. С точки зрения такой функции строки «STL» и «stL» эквивалентны. Пример реализации функции

ciStringCompare

, игнорирующей регистр символов, приведен в совете 35, однако

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")

). Приведенный пример поясняет одну из причин, по которой в соответствии с советом 44 рекомендуется использовать функции контейнеров (

set::find

) вместо их внешних аналогов (

find

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

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

less

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

equal_to

, но интересно заметить, что функция

equal_to

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

==

. В частности, именно так поступает внешний алгоритм

find

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

set2CF

, построенный по

образцу

set — «set с двумя функциями сравнения». Первая функция сравнения определяет порядок сортировки элементов множества, а вторая используется для проверки равенства. А теперь рассмотрим следующее объявление:

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

Контейнер

s

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

s

вставляются два варианта написания строки «Persephone»:

s.insert("Persephone");

s.insert("persephone");

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

"Persephone" != "persephone"

, и вставит обе строки в

s

, в каком порядке они должны следовать?

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

multiset

multimap

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

multiset

) или ключей (

multimap

). Или нам следует настоять на детерминированном порядке содержимого

s

и проигнорировать вторую попытку вставки (для строки «persephone»)? А если будет выбран этот вариант, что произойдет при выполнении следующей команды:

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

Функция

find

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

insert

для сохранения детерминированного порядка элементов

s

, проверка даст отрицательный результат — хотя строка «persephone» была отвергнута как дубликат!

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

find

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

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

Совет 20. Определите тип сравнения для ассоциативного контейнера, содержащего указатели

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

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

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

copy

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

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

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

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

copy

не компилируется. Итератор

ostream_iterator

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

string

и типом объекта, хранящегося в

ssp(string*)

, он выдает ошибку. Еще один довод в пользу сильной типизации…

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

*i

в цикле на

**i

, возможно, вы получите нужный результат — но скорее всего, этого не произойдет. Да, строки будут выведены, но вероятность их следования в алфавитном порядке равна всего 1/24. Контейнер

ssp

хранит свои элементы в отсортированном виде, однако он содержит указатели, поэтому сортироваться будут значения указателей, а не строки. Существует 24 возможных перестановки для четырех указателей, то есть 24 разных последовательности, из которых лишь одна отсортирована в алфавитном порядке[2].

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

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

Совет 21. Следите за тем, чтобы функции сравнения возвращали false в случае равенства

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

set

с типом сравнения

less_equal

и вставьте в него число 10:

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

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

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

s.insert(10);

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

insert

контейнер должен выяснить, присутствует ли в нем число 10. Мы знаем, что такое число уже есть, но контейнер глуп как пробка и все проверяет лично. Чтобы вам было проще понять, что при этом происходит, назовем первоначально вставленный экземпляр 10_A, а новый экземпляр — 10_B.

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

set

; в нашем примере это функция

operator<=

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

less_equal

, a

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

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

set

появляются два экземпляра значения 10, а это означает утрату одного из важнейших свойств

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

? Раз эти контейнеры могут содержать дубликаты, так ли важно, что два объекта с одинаковыми значениями окажутся не эквивалентными? Сохраним оба, для этого и нужны mult-контейнеры. Верно?»

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

multiset

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

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

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

Теперь

s

содержит два экземпляра числа 10, и было бы логично предположить, что при вызове

equal_range

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

equal_range

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

s

говорит, что 10_A и 10_B не эквивалентны, поэтому они не могут оказаться в интервале, определяемом функцией

equal_range

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

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

sort

(см. совет 31). Если вас заинтересуют подробности того, что понимается под строгой квазиупорядоченностью, информацию можно найти во многих серьезных руководствах по STL, в том числе «The C++ Standard Library» [3], «Generic Programming аnd the STL» [4] и на web-сайте SGI, посвященном STL [21]. Особых откровений не ждите, но одно из требований строгой квазиупорядоченности относится непосредственно к данному совету. Требование заключается в следующем: функция, определяющая строгую квазиупорядоченность, должна возвращать

false

при получении двух копий одного значения.

Совет 22. Избегайте изменения ключа «на месте» в контейнерах set и multiset

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

set/multiset

, как и все стандартные ассоциативные контейнеры, хранят свои элементы в отсортированном порядке, и правильное поведение этих контейнеров зависит от сохранения этого порядка. Если изменить значение элемента в ассоциативном контейнере (например заменить 10 на 1000), новое значение окажется в неправильной позиции, что нарушит порядок сортировки элементов в контейнере.

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

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

и mu

l

tiset можно изменять в любое время, и преобразование

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

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

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

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

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

map

multimap

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

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

set

multiset

map

или

multimap

состоит из пяти простых шагов.

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

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

map/multimap

первый компонент копии не должен объявляться константным — ведь именно его мы и собираемся изменить!

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

erase

(см. совет 9).

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

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

insert

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

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

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

Совет 23. Рассмотрите возможность замены ассоциативных контейнеров сортированными векторами

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

multiset , map и multimap

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

set

map

и их

multi

-аналогов.

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

vector

. Чтобы эффективно использовать STL, необходимо понимать, в каких случаях

vector

превосходит стандартные ассоциативные контейнеры по скорости поиска.

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

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

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

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

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

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

vector

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

vector

не совсем произволен — подходят только сортированныеконтейнеры

vector

, поскольку лишь они правильно работают с алгоритмами

binary_search

lower_bound

equal_range

и т. д. (совет 34). Но почему бинарный поиск через вектор (может быть, отсортированный) обеспечивает лучшее быстродействие, чем бинарный поиск через двоичное дерево? Прежде всего из-за банального принципа «размер имеет значение». Существуют и другие причины, не столь банальные, но не менее истинные, и одна из них — локализованность ссылок.

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

Widget

. Скорость поиска является важным фактором, поэтому рассматриваются два основных кандидата: ассоциативный контейнер объектов

Widget

и сортированный

vector<Widget>

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

Widget

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

Widget

в ассоциативном контейнере должны храниться минимум три указателя.

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

Widget

в контейнере

vector

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

vector

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

int

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

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

vector

требуется меньше страниц, чем для ассоциативного контейнера. Это объясняется тем, что в

vector

объект

Widget

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

Widget

прилагаются три указателя. Предположим, вы работаете в системе, где объект

Widget

занимает 12 байт, указатели — 4 байт, а страница памяти содержит 4096 байт. Если не обращать внимания на служебную память контейнера,

vector

позволяет разместить на одной странице 341 объект

Widget

, но в ассоциативном контейнере это количество уменьшается до 170. Следовательно, по эффективности расходования памяти

vector

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

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

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

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

vector

обладает серьезным недостатком — он должен постоянно сохранять порядок сортировки! При вставке нового элемента все последующие элементы сдвигаются на одну позицию. Операция сдвига обходится довольно дорого и становится еще дороже при перераспределении памяти (см. совет 14), поскольку после этого обычно приходится копировать всеэлементы вектора. С другой стороны, при удалении элемента из вектора все последующие элементы сдвигаются на одну позицию к началу. Операции вставки-удаления дорого обходятся для контейнеров

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

и т. д.), но в этом вам поможет совет 45.

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

map/multimap

к контейнеру

vector

ситуация становится более интересной, поскольку

vector

должен содержать объекты

pair

, входящие в

map/multimap

. Но при объявлении объекта типа

map<K, V>

(или его

multimap

-аналога) элементы, хранящиеся в контейнере, в действительности относятся к типу

pair<const K, V>

. Чтобы эмулировать

map

или

multimap

на базе

vector

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

map<K, V>

на базе vector данные, хранящиеся в векторе, должны относиться к типу

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()

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

Контейнер

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

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

Совет 24. Тщательно выбирайте между map::operator[] и map::insert

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

Widget

с конструктором по умолчанию, а также конструктором и оператором присваивания с операндом типа double:

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

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

operator[]

. Но при отсутствии ключа

k

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

operator[]

возвращает ссылку на созданный объект.

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

map<int, Widget> m;

m[1]=1.50;

Выражение

m[1]

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

m.operator[](1)

, поэтому во второй строке присутствует вызов

map::operator[]

. Функция должна вернуть ссылку на ассоциированный объект

Widget

. В данном примере

m

еще не содержит ни одного элемента, поэтому элемент с ключом 1 не существует. Конструктор по умолчанию создает объект

Widget

, ассоциируемый с ключом 1, и возвращает ссылку на этот объект. Наконец, созданному объекту

Widget

присваивается значение 1.50.

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

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

— совет 25) тип элемента всегда представляет собой некую разновидность

pair

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

operator[]

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

operator[]

. При обновлении, то есть при наличии эквивалентного ключа (см. совет 19) в контейнере

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

(совет 45). Чтобы определить, обнаружила ли функция

lower_bound

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

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

уже содержит элемент с ключом 10. В этом случае приведенный ранее шаблон заключает, что

ValueArgType

является

double

, и в теле функции число 1.5 в формате

double

напрямую присваивается объекту

Widget

, ассоциированному с ключом 10. Присваивание осуществляется вызовом

Widget::operator=(double)

. Если бы третий параметр

efficientAddOrUpdate

относился к типу

МарТуре::mapped_type

, то число 1.5 в момент вызова было бы преобразовано в

Widget

, что привело бы к лишним затратам на конструирование (и последующее уничтожение) объекта

Widget

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

efficientAddOrUpdate

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

map::operator[]

map::insert

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

map

рекомендуется использовать оператор

[]

, но при создании нового элемента предпочтение отдается

insert

Совет 25. Изучите нестандартные хэшированные контейнеры

После первого знакомства с 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

в реализации SGI выглядит следующим образом (слегка исправлено для удобства чтения):

template<typename T,

typename HashFunction = hash<T>,

typename CompareFunction = equal_to<T>,

typename Allocator = allocator<T> >

class hash_set;

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

equal_to

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

less

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

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

hash_compare

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

HashingInfo

шаблона контейнера.

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

hash_set

(также отформатированное для наглядности) в реализации Dinkumware выглядит следующим образом:

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

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

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

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()

(в данном случае для реализации функций хэширования и сравнения) используется гораздо чаще, чем можно представить. Другое применение этой концепции продемонстрировано в совете 23.

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

hash_compare

(возможно, объявленный производным от

hash_compare

). Если этот класс будет определять

bucket_size

min_buckets

, две функции

operator()

(с одним и с двумя аргументами) и еще несколько мелочей, не упомянутых выше, он может использоваться для управления конфигурацией и поведением контейнеров Dinkumware

hash_set

hash_multiset

. Управление конфигурацией

hash_map

hash_multimap

осуществляется аналогичным образом.

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

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

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

int

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

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

rbegin

или

rend

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

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

Примечания:

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

Оглавление

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

Все материалы представлены для ознакомления и принадлежат их авторам.