Все контейнеры STL по-своему полезны, однако большинство программистов С++ работает с vector и string чаще, чем с их собратьями, и это вполне понятно. Ведь контейнеры vector и string разрабатывались как замена массивов, а массивы настолько полезны и удобны, что встречаются во всех коммерческих языках программирования от COBOL до Java.

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

Совет 13. Используйте vector и string вместо динамических массивов

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

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

2.Освобождение должно выполняться соответствующей формой оператора delete. Одиночный объект освобождается простым вызовом delete, а для массивов требуется форма delete []. Ошибка в выборе формы delete приводит к непредсказуемым последствиям. На одних платформах программа «зависает» во время выполнения, а на других она продолжает работать с ошибками, приводящими к утечке ресурсов и порче содержимого памяти.

3. Оператор delete для освобождаемого объекта должен вызываться ровно один раз. Повторное освобождение памяти также приводит к непредсказуемым последствиям.

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

Каждый раз, когда вы готовы прибегнуть к динамическому выделению памяти под массив (то есть собираетесь включить в программу строку вида «new T[...]»), подумайте, нельзя ли вместо этого воспользоваться vector или string. Как правило, string используется в том случае, если Т является символьным типом, а vector — во всех остальных случаях. Впрочем, позднее мы рассмотрим ситуацию, когда выбор vector выгладит вполне разумно. Контейнеры vector и string избавляют программиста от хлопот, о которых говорилось выше, поскольку они самостоятельно управляют своей памятью. Занимаемая ими память расширяется по мере добавления новых элементов, а при уничтожении vector или string деструктор автоматически уничтожает элементы контейнера и освобождает память, в которой они находятся.

Кроме того, vector и string входят в семейство последовательных контейнеров STL, поэтому в вашем распоряжении оказывается весь арсенал алгоритмов STL, работающих с этими контейнерами. Впрочем, алгоритмы STL могут использоваться и с массивами, однако у массивов отсутствуют удобные функции begin, end, size и т. п., а также вложенные определения типов (iterator , reverse_iterator , value_type и т. д.), а указатели char* вряд ли могут сравниться со специализированными функциями контейнера string. Чем больше работаешь с STL, тем меньше энтузиазма вызывают встроенные массивы.

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

Честно говоря, мне приходит в голову лишь одна возможная проблема при замене динамических массивов контейнерами vector/string, причем она относится только к string. Многие реализации string основаны на подсчете ссылок (совет 15), что позволяет избавиться от лишних выделений памяти и копирования символов, а также во многих случаях ускоряет работу контейнера. Оптимизация string на основе подсчета ссылок была сочтена настолько важной, что Комитет по стандартизации С++ специально разрешил ее использование.

Впрочем, оптимизация нередко оборачивается «пессимизацией». При использовании string с подсчетом ссылок в многопоточной среде время, сэкономленное на выделении памяти и копировании, может оказаться ничтожно малым по сравнению со временем, затраченным на синхронизацию доступа (за подробностями обращайтесь к статье Саттера «Optimizations That Aren't (In a Multithreaded World)» [20]). Таким образом, при использовании string с подсчетом ссылок в многопоточной среде желательно следить за проблемами быстродействия, обусловленными поддержкой потоковой безопасности.

Чтобы узнать, используется ли подсчет ссылок в вашей реализации string, проще всего обратиться к документации библиотеки. Поскольку подсчет ссылок считается оптимизацией, разработчики обычно отмечают его среди положительных особенностей библиотеки. Также можно обратиться к исходным текстам реализации string. Обычно я не рекомендую искать нужную информацию таким способом, но иногда другого выхода просто не остается. Если вы пойдете по этому пути, не забывайте, что string является определением типа для basic_string (а wstring — для basic_string), поэтому искать следует в шаблоне basic_string. Вероятно, проще всего обратиться к копирующему конструктору класса. Посмотрите, увеличивает ли он переменную, которая может оказаться счетчиком ссылок. Если такая переменная будет найдена, string использует подсчет ссылок, а если нет — не использует... или вы просто ошиблись при поиске.

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

Из всего сказанного можно сделать простой вывод — массивы с динамическим выделением памяти часто требуют лишней работы. Чтобы упростить себе жизнь, используйте vector и string.

Совет 14. Используйте reserve для предотвращения лишних операций перераспределения памяти

Одной из самых замечательных особенностей контейнеров STL является автоматическое наращивание памяти в соответствии с объемом внесенных данных (при условии, что при этом не превышается максимальный размер контейнера — его можно узнать при помощи функции max_size). Для контейнеров vector и string дополнительная память выделяется аналогом функции realloc. Процедура состоит из четырех этапов:

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

2.Копирование всех элементов из старой памяти контейнера в новую память.

3.Уничтожение объектов в старой памяти.

4.Освобождение старой памяти.

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

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

•Функция size() возвращает текущее количество элементов в контейнере. Она не сообщает, сколько памяти контейнер выделил для хранящихся в нем элементов.

•Функция capacity() сообщает, сколько элементов поместится в выделенной памяти. Речь идет об общем количестве элементов, а не о том, сколько еще элементов можно разместить без расширения контейнера. Если вас интересует объем свободной памяти vector или string, вычтите size() из capacity(). Если size() и capacity() возвращают одинаковые значения, значит, в контейнере не осталось свободного места, и следующая вставка (insert, push_back и т. д.) вызовет процедуру перераспределения памяти, описанную выше.

•Функция resize(size_t n) изменяет количество элементов, хранящихся в контейнере. После вызова resize функция size вернет значение n. Если n меньше текущего размера, лишние элементы в конце контейнера уничтожаются. Если n больше текущего размера, в конец контейнера добавляются новые элементы, созданные конструктором по умолчанию. Если n больше текущей емкости контейнера, перед созданием новых элементов происходит перераспределение памяти.

•Функция reserve(size_t n) устанавливает минимальную емкость контейнера равной n — при условии, что n не меньше текущего размера. Обычно это приводит к перераспределению памяти вследствие увеличения емкости (если n меньше текущей емкости, vector игнорирует вызов функции и не делает ничего, а string может уменьшить емкость до большей из величин (size(), n)), но размер string при этом заведомо не изменяется. По собственному опыту знаю, что усечение емкости string вызовом reserve обычно менее надежно, чем «фокус с перестановкой», описанный в совете 17.

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

Предположим, вы хотите создать vector с числами из интервала 1-1000. Без использования reserve это делалось бы примерно так:

vector v;

for (int i=l; i<=1000: ++i) v.push_back(i):

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

vector v;

reserve(1000);

for (int i=1;i<=1000: ++i) v.push_back(i);

В этом случае количество расширений будет равно нулю.

Взаимосвязь между size и capacity позволяет узнать, когда вставка в vector или string приведет к расширению контейнера. В свою очередь, это позволяет предсказать, когда вставка приведет к недействительности итераторов, указателей и ссылок в контейнере. Пример:

string s;

if (s.size() < s.capacity()) {

s.push_back('x');

}

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

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

Совет 15. Помните о различиях в реализации string

Бьерн Страуструп однажды написал статью с интригующим названием «Sixteen Ways to Stack a Cat» [27], в которой были представлены разные варианты реализации стеков. Оказывается, по количеству возможных реализаций контейнеры string не уступают стекам. Конечно, нам, опытным и квалифицированным программистам, положено презирать «подробности реализации», но если Эйнштейн был прав, и Бог действительно проявляется в мелочах... Даже если подробности действительно несущественны, в них все же желательно разбираться. Только тогда можно быть полностью уверенным в том, что они действительно несущественны.

Например, сколько памяти занимает объект string? Иначе говоря, чему равен результат sizeof(string)? Ответ на этот вопрос может быть весьма важным, особенно если вы внимательно следите за расходами памяти и думаете о замене низкоуровневого указателя char* объектом string.

Оказывается, результат sizeof (string) неоднозначен — и если вы действительно следите за расходами памяти, вряд ли этот ответ вас устроит. Хотя у некоторых реализаций контейнер string по размеру совпадает с char*, так же часто встречаются реализации, у которой string занимает в семь раз больше памяти. Чем объясняются подобные различия? Чтобы понять это, необходимо знать, какие данные и каким образом будут храниться в объекте string.

Практически каждая реализация string хранит следующую информацию:

•размер строки, то есть количество символов;

•емкость блока памяти, содержащего символы строки (различия между размером и емкостью описаны в совете 14);

•содержимое строки, то есть символы, непосредственно входящие в строку. Кроме того, в контейнере string может храниться:

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

Реализации string, основанные на подсчете ссылок, также содержат:

•счетчик ссылок для текущего содержимого.

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

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

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

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

Блок «Прочее» оказался больше остальных блоков, поскольку я постарался выдержать масштаб изображения. Если один блок вдвое больше другого, значит, он занимает вдвое больше памяти. В реализации В размер данных синхронизации примерно в шесть раз превышает размер указателя.

В реализации С размер объекта string всегда равен размеру указателя, но этот указатель всегда ссылается на динамически выделенный буфер, содержащий все данные строки: размер, емкость, счетчик ссылок и текущее содержимое. Распределители уровня объекта не поддерживаются. В буфере также хранятся данные, описывающие возможности совместного доступа к содержимому; эта тема здесь не рассматривается, поэтому соответствующий блок на рисунке помечен буквой «X» (если вас интересует, зачем может потребоваться ограничение доступа к данным с подсчетом ссылок, обратитесь к совету 29 «More Effective С++»).

В реализации D объекты string занимают в семь раз больше памяти, чем указатель (при использовании стандартного распределителя памяти). В этой реализации подсчет ссылок не используется, но каждый объект string содержит внутренний буфер, в котором могут храниться до 15 символов. Таким образом, небольшие строки хранятся непосредственно в объекте string — данная возможность иногда называется «оптимизацией малых строк». Если емкость строки превышает 15 символов, в начале буфера хранится указатель на динамически выделенный блок памяти, в котором содержатся символы строки.

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

string s("Perse"); // Имя нашей собаки - Персефона, но мы

// обычно зовем ее просто "Перси"

в реализации D обходится без динамического выделения памяти, обходится одним выделением в реализациях А и С и двумя — в реализации В (для объекта, на который ссылается указатель string, и для символьного буфера, на который ссылается указатель в этом объекте). Если для вас существенно количество операций выделения/освобождения или затраты памяти, часто связанные с этими операциями, от реализации В лучше держаться подальше. С другой стороны, наличие специальной поддержки синхронизации доступа в реализации В может привести к тому, что эта реализация подойдет для ваших целей лучше, чем реализации А и С, а количество динамических выделений памяти уйдет на второй план. Реализация D не требует специальной поддержки многопоточности, поскольку в ней не используется подсчет ссылок. За дополнительной информацией о связи между многопоточностью и строками с подсчетом ссылок обращайтесь к совету 13. Типичная поддержка многопоточности в контейнерах STL описана в совете 12.

В архитектуре, основанной на подсчете ссылок, все данные, находящиеся за пределами объекта string, могут совместно использоваться разными объектами string (имеющими одинаковое содержимое), поэтому из приведенных диаграмм также можно сделать вывод, что реализация А обладает меньшими возможностями для совместного использования данных. В частности, реализации В и С допускают совместное использование данных размера и емкости объекта, что приводит к потенциальному уменьшению затрат на хранение этих данных на уровне объекта. Интересно и другое: отсутствие поддержки распределителей уровня объекта в реализации С означает, что это единственная реализация с возможностью использования общих распределителей: все объекты string должны работать с одним распределителем! (За информацией о принципах работы распределителей обращайтесь к совету 10.) Реализация D не позволяет совместно использовать данные в объектах string.

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

string s ("Perse"); // Строка s состоит из 5 символов

В реализации А минимальный размер выделяемого буфера равен 32 символам. Таким образом, хотя размер s во всех реализациях равен 5 символам, емкость этого контейнера в реализации А равна 31 (видимо, 32-й символ зарезервирован для завершающего нуль-символа, упрощающего реализацию функции c_str). В реализации С также установлен минимальный размер буфера, равный 16, при этом место для завершающего нуль-символа не резервируется, поэтому в реализации С емкость s равна 16. Минимальный размер буфера в реализации D также равен 16, но с резервированием места для завершающего нуль-символа. Принципиальное отличие реализации D заключается в том, что содержимое строк емкостью менее 16 символов хранится в самом объекте string. Реализация В не имеет ограничений на минимальный размер выделяемого блока, и в ней емкость s равна 7. (Почему не 6 или 5? Не знаю. Простите, я не настолько внимательно анализировал исходные тексты.)

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

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

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

•Объекты string занимают в 1-7 (по меньшей мере) раз больше памяти, чем указатели char*.

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

•Объекты string могут совместно использовать данные о размере и емкости строки.

•Объекты string могут поддерживать (или не поддерживать) распределители памяти уровня объекта.

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

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

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

Совет 16. Научитесь передавать данные vector и string функциям унаследованного интерфейса

С момента стандартизации С++ в 1998 году элита С++ настойчиво подталкивает программистов к переходу с массивов на vector. Столь же открыто пропагандируется переход от указателей char* к объектам string. В пользу перехода имеются достаточно веские аргументы, в том числе ликвидация распространенных ошибок программирования (совет 13) и возможность полноценного использования всей мощи алгоритмов STL (совет 31).

Но на этом пути остаются некоторые препятствия, из которых едва ли не самым распространенным являются унаследованные интерфейсы языка С, работающие с массивами и указателями char* вместо объектов vector и string. Они существуют с давних времен, и если мы хотим эффективно использовать STL, придется как-то уживаться с этими «пережитками прошлого».

К счастью, задача решается просто. Если у вас имеется vector v и вы хотите получить указатель на данные v, которые интерпретировались бы как массив, воспользуйтесь записью &v[0]. Для string s аналогичная запись имеет вид s.c_str(). Впрочем, это не все — существуют некоторые ограничения (то, о чем в рекламе обычно пишется самым мелким шрифтом).

Рассмотрим следующее объявление:

vector v;

Выражение v[0] дает ссылку на первый элемент вектора, соответственно &v[0] — указатель на первый элемент. В соответствии со Стандартом С++ элементы vector должны храниться в памяти непрерывно, по аналогии с массивом. Допустим, у нас имеется функция С, объявленная следующим образом:

void doSomething(const int* pInts, size_t numlnts):

Передача данных должна происходить так:

doSomething(&v[0],v.size());

Во всяком случае, так должно быть. Остается лишь понять, что произойдет, если вектор v пуст. В этом случае функция v.size() вернет 0, а &v[0] пытается получить указатель на несуществующий блок памяти с непредсказуемыми последствиями. Нехорошо. Более надежный вариант вызова выглядит так:

if (!v.empty()) {

doSomething(&v[0],v.size());

}

Отдельные подозрительные личности утверждают, что &v[0] можно заменить на v.begin(), поскольку begin возвращает итератор, а для vector итератор в действительности представляет собой указатель. Во многих случаях это действительно так, но, как будет показано в совете 50, это правило соблюдается не всегда, и полагаться на него не стоит. Функция begin возвращает итератор, а не указатель, поэтому она никогда не должна использоваться для получения указателя на данные vector. А если уж вам очень приглянулась запись v. begin(), используйте конструкцию &*v.begin() — она вернет тот же указатель, что и &v[0], хотя это увеличивает количество вводимых символов и затрудняет работу людей, пытающихся разобраться в вашей программе. Если знакомые вам советуют использовать v.begin() вместо &v[0] — лучше смените круг общения.

Способ получения указателя на данные контейнера, хорошо работающий для vector, недостаточно надежен для string. Во-первых, контейнер string не гарантирует хранения данных в непрерывном блоке памяти; во-вторых, внутреннее представление строки не обязательно завершается нуль-символом. По этим причинам в контейнере string предусмотрена функция c_str, которая возвращает указатель на содержимое строки в формате С. Таким образом, передача строки s функции

void doSomething(const char *pString);

происходит так:

doSomething(s.c_str());

Данное решение подходит и для строк нулевой длины. В этом случае c_str возвращает указатель на нуль-символ. Кроме того, оно годится и для строк с внутренними нуль-символами, хотя в этом случае doSomething с большой вероятностью интерпретирует первый внутренний нуль-символ как признак конца строки. Присутствие внутренних нуль-символов несущественно для объектов string, но не для функций С, использующих char*

Вернемся к объявлениям doSomething:

void doSomething(const int* pints, size_t numInts);

void doSomething(const char *pString);

В обоих случаях передаются указатели на const Функция С, получающая данные vector или string, читает их, не пытаясь модифицировать. Такой вариант наиболее безопасен. Для string он неизбежен, поскольку не существует гарантии, что c_str вернет указатель на внутреннее представление строковых данных; функция может вернуть указатель на неизменяемую копию данных в формате С (если вас встревожила эффективность этих операций, не волнуйтесь — мне не известна ни одна современная реализация библиотеки, в которой бы использовалась данная возможность).

Vector предоставляет программисту чуть большую свободу действий. Передача v функции С, модифицирующей элементы v, обычно обходится без проблем, но вызванная функция не должна изменять количество элементов в векторе. Например, она не может «создавать» новые элементы в неиспользуемой памяти vector. Такие попытки приведут к нарушению логической целостности контейнера v, поскольку объект не будет знать свой правильный размер, и вызов функции v.size()возвратит неправильные результаты. А если вызванная функция попытается добавить новые данные в вектор, у которого текущий размер совпадает с емкостью (совет 14), произойдет сущий кошмар. Я даже не пытаюсь предугадать последствия, настолько они ужасны.

Вы обратили внимание на формулировку «обычно обходится без проблем» в предыдущем абзаце? Конечно, обратили. Некоторые векторы устанавливают для своих данных дополнительные ограничения, и при передаче вектора функции API, изменяющей его содержимое, вы должны проследить за тем, чтобы эти ограничения не были нарушены. Например, как объясняется в совете 23, сортируемые векторы часто могут рассматриваться в качестве разумной альтернативы для ассоциативных контейнеров, но при этом содержимое таких векторов должно оставаться правильно отсортированным. При передаче сортируемого вектора функции, способной изменить его содержимое, вам придется учитывать, что при возвращении из функции сортировка элементов может быть нарушена.

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

// Функция fillArray получает указатель на массив.

// содержащий не более arraySize чисел типа double.

// и записывает в него данные. Возвращаемое количество записанных

// чисел заведомо не превышает maxNumDoubles.

size_t fillArray(double *pArray, size_t arraySize);

vector vd(maxNumDoubles); // Создать vector, емкость которого

// равна maxNumDoubles

vd.resize(fillArray(&vd[0], vd.size())); // Заполнить vd вызовом

// функции fillArray. после чего // изменить размер по количеству // записанных элементов

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

// Функция получает указатель на массив, содержащий не более

// arraySize символов, и записывает в него данные.

// Возвращаемое количество записанных чисел заведомо не превышает

// maxNumChars

size_t fillString(char *pArray. sizet arraySize);

vector vc(maxNumChars); // Создать vector, емкость которого

// равна maxNumChars

size_t charsWritten = fillString(&vc[0],vc.size());

// Заполнить vc

// вызовом fillString string s(vc.begin().vc.begin()+charsWritten);

// Скопировать данные

// из vc в s интервальным

// конструктором (совет 5)

Собственно, сам принцип сохранения данных функцией API в vector и их последующего копирования в нужный контейнер STL работает всегда:

size_t fillArray(double *pArray. size_t arraySize); // См. ранее

vector vd(maxNumDoubles);// Также см. ранее

vd.resize(fillArray(&vd[0],vd.size());

deque d(vd.begin().vd.end());// Копирование в deque

list l(vd.begin().vd.end());// Копирование в list

set s(vd.begin(),vd.end()):// Копирование в set

Более того, этот фрагмент подсказывает, как организовать передачу данных из других контейнеров STL, кроме vector и string, функциям С. Для этого достаточно скопировать данные контейнера в vector и передать его при вызове:

void doSomething(const int* pints. size_t numlnts); // Функция С (см. ранее)

set intSet:

// Множество, в котором

// хранятся передаваемые

// данные

vector v(intSet.begin(),intSet.end());// Скопировать данные

// из set в vector

if (!v.empty()) doSomething(&v[0],v.size());// Передать данные

// функции С

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

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

Предположим, вы пишете программу для нового телешоу «Бешеные деньги». Информация о потенциальных участниках хранится в векторе:

class Contestant {...};

vector contestants;

При объявлении набора участников заявки сыплются градом, и вектор быстро заполняется элементами. Но по мере отбора перспективных кандидатов относительно небольшое количество элементов перемещается в начало вектора (вероятно, вызовом partial_sort или partition — см. совет 31), а неудачники удаляются из вектора (как правило, при помощи интервальной формы erase — см. совет 5). В результате удаления длина вектора уменьшается, но емкость остается прежней. Если в какой-то момент времени вектор содержал данные о 100 000 кандидатов, то его емкость останется равной 100 000, даже если позднее количество элементов уменьшится до 10.

Чтобы вектор не удерживал ненужную память, необходимы средства, которые бы позволяли сократить емкость от максимальной до используемой в настоящий момент. Подобное сокращение емкости обычно называется «сжатием по размеру». Сжатие по размеру легко программируется, однако код — как бы выразиться поделикатнее? — выглядит недостаточно интуитивно. Давайте разберемся, как он работает.

Усечение лишней емкости в векторе contestants производится следующим образом:

vector(contestants).swap(contestants);

Выражение vector(contestants) создает временный вектор, содержащий копию contestants; основная работа выполняется копирующим конструктором vector. Тем не менее, копирующий конструктор vector выделяет ровно столько памяти, сколько необходимо для хранения копируемых элементов, поэтому временный вектор не содержит лишней емкости. Затем содержимое вектора contestants меняется местами с временным вектором функцией swap. После завершения этой операции в contestants оказывается содержимое временного вектора с усеченной емкостью, а временный вектор содержит «раздутые» данные, ранее находившиеся в contestants. В этот момент (то есть в конце команды) временный вектор уничтожается, освобождая память, ранее занимаемую вектором contestants.

Аналогичный прием применяется и по отношению к строкам:

string s;

// Создать большую строку и удалить из нее // большую часть символов

string(s).swap(s);// Выполнить "сжатие по размеру" с объектом s

Я не могу предоставить стопроцентной гарантии того, что этом прием действительно удалит из контейнера лишнюю емкость. Авторы реализаций при желании могут намеренно выделить в контейнерах vector и string лишнюю память, и иногда они так и поступают. Например, контейнер может обладать минимальной емкостью или же значения емкости vector/string могут ограничиваться степенями 2 (по собственному опыту могу сказать, что подобные аномалии чаще встречаются в реализациях string, нежели в реализациях vector. За примерами обращайтесь к совету 15). Таким образом, «сжатие по размеру» следует понимать не как «приведение к минимальной емкости», а как «приведение к минимальной емкости, допускаемой реализацией для текущего размера контейнера». Впрочем, это лучшее, что вы можете сделать (не считая перехода на другую реализацию STL), поэтому «сжатие по размеру» для контейнеров vector и string фактически эквивалентно «фокусу с перестановкой».

Кстати говоря, одна из разновидностей «фокуса с перестановкой» может использоваться для очистки контейнера с одновременным сокращением емкости до минимальной величины, поддерживаемой вашей реализацией. Для этого в перестановке используется временный объект vector или string, содержимое которого создается конструктором по умолчанию:

vector v;

string s;

// Использовать v и s

vector ().swap(v); // Очистить v с уменьшением емкости

string().swap(s);// Очистить s с уменьшением емкости

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

Совет 18. Избегайте vector<bool>

Vector как контейнер STL обладает лишь двумя недостатками. Во-первых, это вообще не контейнер STL. Во-вторых, он не содержит bool.

Объект не становится контейнером STL только потому, что кто-то назвал его таковым — он становится контейнером STL лишь при соблюдении всех требований, изложенных в разделе 23.1 Стандарта С++. В частности, в этих требованиях говорится, что если с — контейнер объектов типа Т, поддерживающий оператор [], то следующая конструкция должна нормально компилироваться:

Т *р = &с[0];// Инициализировать Т* адресом данных,

// возвращаемых оператором []

Иначе говоря, если оператор [ ] используется для получения одного из объектов Т в Container, то указатель на этот объект можно получить простым взятием его адреса (предполагается, что оператор & типа Т не был перегружен извращенным способом). Следовательно, чтобы vector был контейнером, следующий фрагмент должен компилироваться:

vector v;

bool *pb = &v[0]: // Инициализировать bool* адресом результата.

// возвращаемого оператором vector::operator[]

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

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

Ссылки на отдельные биты тоже запрещены, что представляет определенную проблему для дизайна интерфейса vector, поскольку функция vector::operator[] должна возвращать значение типа Т&. Если бы контейнер vector действительно содержал bool, этой проблемы не существовало бы, но вследствие особенностей внутреннего представления функция vector::operator[] должна вернуть несуществующую ссылку на отдельный бит.

Чтобы справиться с этим затруднением, функция vector::operator[] возвращает объект, который имитирует ссылку на отдельный бит — так называемый промежуточный объект. Для использования STL не обязательно понимать, как работают промежуточные объекты, но вообще это весьма полезная идиома С++. Дополнительная информация о промежуточных объектах приведена в совете 30 «More Effective С++», а также в разделе «Паттерн Ргоху» книги «Приемы объектно-ориентированного проектирования» [6]. На простейшем уровне vector выглядит примерно так:

template

vector {

public:

class reference {…};// Класс, генерирующий промежуточные

// объекты для ссылок на отдельные биты

reference operator[](size_type n); // operator[] возвращает

… // промежуточный объект

};

Теперь понятно, почему следующий фрагмент не компилируется: vector v;

bool *pb=&v[0]; // Ошибка! Выражение в правой части относится к типу

// vector::reference*, а не bool*

А раз фрагмент не компилируется, vector не удовлетворяет требованиям к контейнерам STL. Да, специфика vector особо оговорена в Стандарте; да, этот контейнер почти удовлетворяет требованиям к контейнерам STL, но «почти» не считается. Чем больше вы напишете шаблонов, предназначенных для работы с STL, тем глубже вы осознаете эту истину. Уверяю вас, наступит день, когда написанный вами шаблон будет работать лишь в том случае, если получение адреса элемента контейнера дает указатель на тип элемента; и когда этот день придет, вы наглядно ощутите разницу между контейнером и почти контейнером.

Спрашивается, почему же vector присутствует в Стандарте, если это не контейнер? Отчасти это связано с одним благородным, но неудачным экспериментом, но позвольте мне ненадолго отложить эту тему и заняться более насущным вопросом. Итак, от vector следует держаться подальше, потому что это не контейнер — но что же делать, когда вам действительно понадобится вектор логических величин?

В стандартную библиотеку входят два альтернативных решения, которые подходят практически для любых ситуаций. Первое решение — deque. Контейнер deque обладает практически всеми возможностями vector (за исключением разве что reserve и capacity), но при этом deque является полноценным контейнером STL, содержащим настоящие значения bool. Конечно, внутренняя память deque не образует непрерывный блок, поэтому данные deque не удастся передать функции С, получающей массив bool (см. совет 16), но это не удалось бы сделать и с vector из-за отсутствия переносимого способа получения данных vector. (Прием, продемонстрированный для vector в совете 16, не компилируется для vector, поскольку он зависит от возможности получения на тип элемента, хранящегося в векторе, — как упоминалось выше, vector не содержит bool.)

Второй альтернативой для vector является bitset. Вообще говоря, bitset не является стандартным контейнером STL, но входит в стандартную библиотеку С++. В отличие от контейнеров STL, размер bitset (количество элементов) фиксируется на стадии компиляции, поэтому операции вставки-удаления элементов не поддерживаются. Более того, поскольку bitset не является контейнером STL, в нем отсутствует поддержка итераторов. Тем не менее bitset, как и vector, использует компактное представление каждого элемента одним битом, поддерживает функцию flip контейнера vector и ряд других специальных функций, имеющих смысл в контексте битовых множеств. Если вы переживете без итераторов и динамического изменения размеров, вероятно, bitset хорошо подойдет для ваших целей.

А теперь вернемся к благородному, но неудачному эксперименту, из-за которого появился «псевдоконтейнер» vector. Я уже упоминал о том, что промежуточные объекты часто используются при программировании на С++. Члены Комитета по стандартизации С++ знали об этом, поэтому они решили создать vector как наглядный пример контейнера, доступ к элементам которого производится через промежуточные объекты. Предполагалось, что при наличии такого примера в Стандарте у программистов появится готовый образец для построения собственных аналогов.

В итоге выяснилось, что создать контейнер с промежуточными объектами, удовлетворяющий всем требованиям к контейнеру STL, невозможно. Так или иначе, следы этой неудачной попытки сохранились в Стандарте. Можно долго гадать, почему vector был сохранен, но с практической точки зрения это несущественно. Главное — помните, что vector не удовлетворяет требованиям к контейнерам STL, что им лучше не пользоваться и что существуют альтернативные структуры данных deque и bitset, почти всегда способные заменить vector.

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

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

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

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

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

Алгоритм find и функция set::insert являются типичными представителями семейства функций, проверяющих совпадение двух величин, однако делают это они по-разному. Для find совпадением считается равенство двух величин, проверяемое оператором =. Функция set:: insert проверяет отношение эквивалентности, обычно основанное на операторе < Таким образом, по одному определению два объекта могут иметь одинаковые значения, тогда как по другому определению они будут различаться. Отсюда следует, что для эффективного использования STL необходимо понимать различия между равенством и эквивалентностью.

Формальное определение равенства основано на использовании оператора =. Если результат выражения х=у равен true, значит, х и у имеют одинаковые значения, а если false — разные. В целом определение весьма прямолинейное, хотя следует помнить о том, что из равенства значений не следует равенство всех полей данных. Предположим, класс Widget хранит внутренние данные о времени последнего обращения:

class Widget {

public:

private:

TimeStamp lastAccessed;

};

Для класса Widget можно определить оператор ==, игнорирующий значение этого поля:

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

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

}

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

Эквивалентность основана на относительном порядке значений объектов в отсортированном интервале. Проще всего рассматривать ее в контексте порядка сортировки, являющегося частью любого стандартного ассоциативного контейнера (то есть set, multiset, map и multimap). Два объекта х и у считаются эквивалентными по отношению к порядку сортировки, используемому ассоциативным контейнером с, если ни один из них не предшествует другому в порядке сортировки с. На первый взгляд такая формулировка кажется запутанной, но на практике все просто. Возьмем контейнер set s. Два объекта Widget, w1 и w2, имеют эквивалентные значения по отношению к s, если ни один из них не предшествует другому в порядке сортировки s. Стандартная функция сравнения для set — less — по умолчанию просто вызывает operator< для объектов Widget, поэтому wl и w2 будут иметь значения, эквивалентные по отношению к operator< если истинно следующее выражение:

!(w1

&& // и

!(w2

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

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

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

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

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

Выражение !c.key_comp()(x,y) выглядит устрашающе, но стоит понять, что c.key_comp() возвращает функцию (или объект функции), как все затруднения исчезают. Перед нами простой вызов функции (или объекта функции), возвращаемой key_comp, которой передаются аргументы х и у. Затем вычисляется логическое отрицание результата. Функция с.keycomp ()(х, у) возвращает true лишь в том случае, если х предшествует у в порядке сортировки, поэтому выражение !с.key_comp()(х, у) истинно только в том случае, если х не предшествует у в порядке сортировки с.

Чтобы вы лучше осознали принципиальный характер различий между равенством и эквивалентностью, рассмотрим пример — контейнер set без учета регистра символов, то есть контейнер set, в котором функция сравнения игнорирует регистр символов в строках. С точки зрения такой функции строки «STL» и «stL» эквивалентны. Пример реализации функции ciStringCompare, игнорирующей регистр символов, приведен в совете 35, однако set требуется тип функции сравнения, а не сама функция. Чтобы заполнить этот пробел, мы пишем класс функтора с оператором (), вызывающим ciStringCompare:

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

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

binary_function{ // описание базового класса

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

bool operator() (const string& lhs,

const string& rhs) const

{

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

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

}

};

При наличии CiStringCompare контейнер set, игнорирующий регистр символов, создается очень просто:

set 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 > 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 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::const_iterator i = ssp.begin(); // Предполагаемый

i!=ssp.end();

++i)

cout <<*i << endl;

Однако на практике ничего похожего не происходит. Вместо строк выводятся четыре шестнадцатеричных числа — значения указателей. Поскольку в контейнере set хранятся указатели, *i является не строкой, а указателем на строку. Пусть этот урок напоминает, чтобы вы следовали рекомендациям совета 43 и избегали написания собственных циклов. Использование алгоритма сору:

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

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

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

не только делает программу более компактной, но и помогает быстрее обнаружить ошибку, поскольку вызов сору не компилируется. Итератор ostream_iterator должен знать тип выводимого объекта, поэтому когда компилятор обнаруживает расхождение между заданным в параметре шаблона типом string и типом объекта, хранящегося в ssp (string*), он выдает ошибку. Еще один довод в пользу сильной типизации...

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

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

set ssp;

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

set > ssp;

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

set.allocator > ssp;

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

Если вы хотите сохранить указатели string* в контейнере set так, чтобы их порядок определялся значениями строк, стандартный функтор сравнения less вам не подойдет. Вместо этого необходимо написать собственный функтор сравнения, который получает указатели string* и упорядочивает их по содержимому строк, на которые они ссылаются. Пример:

struct StringPtrLess:

public binary_function

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

bool> {

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

{

return *ps1<*ps2:

}

};.

После этого StringPtrLess используется в качестве типа критерия сравнения ssp:

typedef set StringPtrSet;

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

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

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

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

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

for(StringPtrSet::const _iterator i = ssp.begin();

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

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

cout«**i«endl; // "Pengun". "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:

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

struct Dereference{

template

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

{

return *ptr;

}

};

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

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

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

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

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

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

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

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

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

return *psl<*ps2:

}

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

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

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

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

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

struct DereferenceLess {

template

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

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

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

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

}

};

Данный шаблон снимает необходимость в написании таких классов, как StringPtrLess, поскольку вместо них можно использовать DereferenceLess:

set ssp; // Ведет себя так же. как

// set

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

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

Сейчас я покажу вам нечто любопытное. Создайте контейнер set с типом сравнения less_equal и вставьте в него число 10:

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

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

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

s.insert(10);

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

Контейнер перебирает свои внутренние структуры данных и ищет место для вставки 10в. В итоге ему придется проверить 10А и сравнить его с 10в. Для ассоциативного контейнера «сравнение» сводится к проверке эквивалентности (см. совет 19), поэтому контейнер проверяет эквивалентность объектов 10А и 10в. Естественно, при этой проверке используется функция сравнения контейнера set; в нашем примере это функция operator<=, поскольку мы задали функцию сравнения less_equal, a less_equal означает operator<=. Затем контейнер проверяет истинность следующего выражения:

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

Оба значения, 10А и 10в, равны 10, поэтому условие 10А<=10В заведомо истинно. Аналогично истинно и условие 10В<=10А. Приведенное выше выражение упрощается до !(t rue) &&!(t rue), то есть false && false — результат равен false. Другими словами, контейнер приходит к выводу, что 10А и 10в не эквивалентны, и вставляет 10в в контейнер наряду с 10А. С технической точки зрения эта попытка приводит к непредсказуемым последствиям, но на практике в контейнере set появляются два экземпляра значения 10, а это означает утрату одного из важнейших свойств set. Передача типа сравнения less_equal привела к порче контейнера! Более того, любая функция сравнения, которая возвращает true для равных значений, приведет к тем же последствиям. Равные значения по определению не эквивалентны! Здорово, не правда ли?

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

Например, в совете 20 рассказано о том, как написать функцию сравнения для контейнеров указателей string* обеспечивающую автоматическую сортировку содержимого контейнера по значениям строк, а не указателей. Приведенная функция сравнения сортирует строки по возрастанию, но давайте предположим, что вам понадобилась функция для сортировки по убыванию. Естественно, вы возьмете существующий код и отредактируете его. Но если не проявить достаточной осторожности, у вас может получиться следующий результат (изменения выделены жирным шрифтом):

struct StringPtr Greater :

public binary_function

const string*, // изменения, внесенные в код bool> {// из совета 20.

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

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

bool operator()(const string *psl. const string *ps2) const

{

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

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

};

Идея заключается в том, чтобы изменить порядок сортировки логическим отрицанием условия в функции сравнения. К сожалению, отрицанием операции «<» является не «>», а «>=», а мы выяснили, что операция «>=», возвращающая true для равных значений, не подходит для функции сравнения в ассоциативных контейнерах.

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

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

public binary_function

const string*,

bool> {

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

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

}

}:

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

Я знаю, о чем вы думаете. «Конечно, это имеет смысл для set и map, поскольку эти контейнеры не могут содержать дубликатов. А как насчет multiset и multimap? Раз эти контейнеры могут содержать дубликаты, так ли важно, что два объекта с одинаковыми значениями окажутся не эквивалентными? Сохраним оба, для этого и нужны mult-контейнеры. Верно?»

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

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

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

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

Теперь s содержит два экземпляра числа 10, и было бы логично предположить, что при вызове equal _range мы получим пару итераторов, описывающих интервал с обеими копиями. Однако это невозможно. Функция equal_range, несмотря на свое название, определяет интервал не равных, а эквивалентных значений. В нашем примере функция сравнения s говорит, что 10А и 10в не эквивалентны, поэтому они не могут оказаться в интервале, определяемом функцией equal range.

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

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

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

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

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

map m;

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

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

multimap mm;

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

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

Дело в том, что элементы объекта типа map или multimap относятся к типу pair. Ключ относится к типу const К и поэтому не может изменяться. Впрочем, его все же можно изменить с применением const_cast, как показано ниже. Хотите — верьте, хотите — нет, но иногда это даже нужно.

Обратите внимание: в заголовке этого совета ничего не сказано о контейнерах пир и multimap. Для этого есть веские причины. Как показывает предыдущий пример, модификация ключа «на месте» невозможна для map и multimap (без применения преобразования const_cast), но может быть допустима для set и multiset. Для объектов типа set и multiset в контейнере хранятся элементы типа Т, а не const Т. Следовательно, элементы контейнеров set и multiset можно изменять в любое время, и преобразование const_cast для этого не требуется (вообще говоря, дело обстоит не так просто, но не будем забегать вперед).

Сначала выясним, почему элементы set и multiset не имеют атрибута const. Допустим, у нас имеется класс Emplоуее:

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 с объектами Emplоуее было бы вполне разумно упорядочить его по кодам работников:

struct IDNumberLess:

public binary_function { // См. совет 40

bool operator() (const Employees Ihs,

const Employees rhs) const

{

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

}

}

typedef set EmplIDSet;

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

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

// по коду

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

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

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

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

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

}

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

Спрашивается, почему нельзя применить ту же логику к ключам контейнеров map и multimap? Почему бы не создать контейнер map, ассоциирующий работников со страной, в которой они живут; контейнер с функцией сравнения IDNumberLess, как в предыдущем примере? И почему бы в таком контейнере не изменить должность без изменения кода работника, как в предыдущем примере?

Откровенно говоря, мне это кажется вполне логичным, однако мое личное мнение в данном случае несущественно. Важно то, что Комитет по стандартизации решил, что ключи map/multimap должны быть неизменными (const), а значения set/ multiset — не должны.

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

Впрочем, не все так просто. Хотя элементы set/multiset и не являются неизменными, реализации могут предотвратить их возможную модификацию. Например, оператор* для set: iterator может возвращать const Т&, то есть результат разыменования итератора 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(*i) .setTitle("Corporate Deity"); // константность *i

}

Мы берем объект, на который ссылается i, и сообщаем компилятору, что результат должен интерпретироваться как ссылка на (неконстантный) объект Employee, после чего вызываем setTitle для полученной ссылки. Я не буду тратить время на долгие объяснения и лучше покажу, почему альтернативное решение работает совсем не так, как можно было бы ожидать.

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

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

static_cast(*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 и multimap содержат элементы типа pair. Объявление const означает, что первый компонент пары определяется как константа, а из этого следует, что любые попытки устранить его константность приводят к непредсказуемому результату. Теоретически реализация STL может записывать такие данные в область памяти, доступную только для чтения (например, в страницу виртуальной памяти, которая после исходной записи защищается вызовом системной функции), и попытки устранить их константность в лучшем случае ни к чему не приведут. Я никогда не слышал о реализациях, которые бы поступали подобным образом, но если вы стремитесь придерживаться правил, установленных в Стандарте, — никогда не пытайтесь устранять константность ключей в контейнерах map и multimap.

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

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

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

2.Создайте копию изменяемого элемента. Помните, что для контейнеров map/ multimap первый компонент копии не должен объявляться константным — ведь именно его мы и собираемся изменить!

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

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

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

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

if (i!=se.end()) { Employee e(*i);

se.erase(i++):

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

//Этап 2: копирование элемента

//Этап 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 в контейнере 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 vw;// Альтернатива для set

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

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

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

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

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

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

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

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

// binary_search

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

if (i!=vw.end() && !(*i

// !(*i

pair::iterator.

vector::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 (или его multimap-аналога) элементы, хранящиеся в контейнере, в действительности относятся к типу pair . Чтобы эмулировать map или multimap на базе vector, признак константности необходимо устранить, поскольку в процессе сортировки элементы вектора перемещаются посредством присваивания, а это означает, что оба компонента пары должны допускать присваивание. Следовательно, при эмуляции map на базе vector данные, хранящиеся в векторе, должны относиться к типу pair, а не pair.

Содержимое map/multimap хранится в отсортированном виде, но при сортировке учитывается только ключевая составляющая элемента (первый компонент пары), поэтому при сортировке vector должно происходить то же самое. Нам придется написать собственную функцию сравнения для пар, поскольку оператор < типа pair сравнивает обе составляющие пары.

Интересно заметить, что для выполнения поиска требуется вторая функция сравнения. Функция сравнения, используемая при сортировке, получает два объекта pair, но поиск выполняется только по значению ключа. С другой стороны, функция сравнения, используемая при поиске, должна получать два разнотипных объекта — объект с типом ключа (искомое значение) и pair (одна из пар, хранящихся в векторе). Но это еще не все: мы не знаем, что передается в первом аргументе — ключ или pair, поэтому в действительности для поиска необходимы две функции: одна получает ключ, а другая — объект pair. В следующем примере объединено все сказанное ранее:

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

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

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

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

{

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

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

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

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& kl.// сравнения

const Data::first_type& k2) const

{

return kl < k2;

}

}

В данном примере предполагается, что сортированный вектор эмулирует map. Перед нами практически буквальное переложение комментариев, приведенных ранее, если не считать присутствия функции keyLess, предназначенной для согласования функций operator(). Каждая функция просто сравнивает два ключа, поэтому, чтобы не программировать одни и те же действия дважды, мы производим проверку в keyLess, а функция operator() возвращает полученный результат. Конечно, этот прием упрощает сопровождение DataCompare, однако у него есть один недостаток: наличие функций operator() с разными типами параметров исключает адаптацию объектов функций (см. совет 40). С этим ничего не поделаешь.

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

vector vd;// Альтернатива для map

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

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

// (при эмуляции multiset можно // воспользоваться алгоритмом // stable_sort - см. совет 31)

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

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

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

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

vector::iterator i = 1ower_bound(vd.begin(),vd.end().s, DataCompareO): if (i!=vd.end() && !(i ->first

//Поиск с применением

//lower_bound: конструкция

//!(i->first

//в совете 45

pair::iterator.

vector::iterator> range = equal_range(vd.begin() .vd.end() ,s. DataCompareO): 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 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 m команда m[k]=v; проверяет, присутствует и ключ к в контейнере. Если ключ отсутствует, он добавляется вместе с ассоциированным значением v. Если ключ уже присутствует, ассоциированное с ним значение заменяется на v.

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

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

map 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 intWidgetMap: // Вспомогательное определение типа

pair 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; // Значение, ассоциируемое

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

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

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

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

При вызове insert передается аргумент типа inWidgetMap::value_type (то есть pair), потому при вызове insert необходимо сконструировать и уничтожить объект данного типа. Следовательно, при вызове insert будут вызваны конструктор и деструктор pair, что в свою очередь приведет к вызову конструктора и деструктора Widget, поскольку pair содержит объект Widget. При вызове operator[] объект pair не используется, что позволяет избежать затрат на конструирование и уничтожение pair и Widget.

Следовательно, при вставке элемента в map по соображениям эффективности желательно использовать insert вместо operator[], а при обновлении существующих элементов предпочтение отдается operator[], что объясняется как эффективностью, так и эстетическими соображениями.

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

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

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

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

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

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

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

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

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

template

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

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

typename МарТуре::iterator

efficientAddOrUpdate(MapType& m.

const KeyArgType& k.

const ValueArgType& v)

{

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

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

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

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

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

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

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::кеуcomp. В результате проверки эквивалентности мы узнаем, какая операция выполняется — создание или обновление.

Обновление реализовано весьма прямолинейно. С созданием дело обстоит поинтереснее, поскольку в нем используется «рекомендательная» форма insert. Конструкция m.insert(lb.MVT(k, v)) «рекомендует» lb как правильную точку вставки для нового элемента с ключом, эквивалентным к, а Стандарт гарантирует, что в случае правильности рекомендации вставка будет выполнена за постоянное время (вместо логарифмического). В efficentAddOrUpdate мы знаем, что lb определяет правильную позицию вставки, поэтому insert всегда выполняется с постоянным временем.

У данной реализации есть одна интересная особенность — KeyArgType и ValueArgType не обязаны быть типами, хранящимися в контейнере, а всего лишь должны приводиться к этим типам. Существует и другое возможное решение — удалить параметры-типы KeyArgType/ValueArgType и заменить их на МарТуре::key_type и МарТуре::mapped_type. Но в этом случае вызов может сопровождаться лишними преобразованиями типов. Возьмем определение контейнера map, встречавшееся в примерах:

map m;// См. ранее

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

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

public:

Widget& operator=(double weight);

};

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

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

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

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

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

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

template

typename HashFunction,

typename CompareFunction,

typename Allocator = allocator >

class hash _контейнер ;

Полученное объявление весьма близко к объявлению хэшированных контейнеров в реализации SGI. Главное различие между ними заключается в том, что в реализации SGI для типов HashFunction и CompareFunction предусмотрены значения по умолчанию. Объявление hash_set в реализации SGI выглядит следующим образом (слегка исправлено для удобства чтения):

template

typename HashFunction = hash,

typename CompareFunction = equal_to,

typename Allocator = allocator >

class hash_set;

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

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

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

template

class hash_compare;

template

typename Hashinglnfo = hash_compare>,

typename Allocator = allocator>

class hash_set;

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

После небольшого форматирования объявление hash_compare (значение по умолчанию для HashingInfo) выглядит примерно так:

template>

class hash_compare{

public:

enum{

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

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

}

size_t operator()(const Т&) 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_mnap и hash_ multimap осуществляется аналогичным образом.

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

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

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

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

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

На первый взгляд итераторы представляются предметом весьма простым. Но стоит присмотреться повнимательнее, и вы заметите, что стандартные контейнеры STL поддерживают четыре разных типа итераторов: iterator, const_iterator, reverse_iterator и const_reverse_iterator. Проходит совсем немного времени, и выясняется, что в некоторых формах insert и erase только один из этих четырех типов принимается контейнером. И здесь начинаются вопросы. Зачем нужны четыре типа итераторов? Существует ли между ними какая-либо связь? Можно ли преобразовать итератор от одного типа к другому? Можно ли смешивать разные типы итераторов при вызове алгоритмов и вспомогательных функций STL? Как эти типы связаны с контейнерами и их функциями?

В настоящей главе вы найдете ответы на эти вопросы, а также поближе познакомитесь с разновидностью итераторов, которой обычно не уделяют должного внимания: isreambuf_iterator. Если вам нравится STL, но не устраивает быстродействие istream_iterator при чтении символьных потоков, возможно, isreambuf_ iterator поможет справиться с затруднениями.

Совет 26. Старайтесь использовать iterator вместо const_iterator, reverse_iterator и const_reverse_iterator

Как известно, каждый стандартный контейнер поддерживает четыре типа итераторов. Для контейнера container тип iterator работает как Т* тогда как const_iterator работает как const Т* (также встречается запись Т const*). При увеличении iterator или const_iterator происходит переход к следующему элементу контейнера в прямом порядке перебора (от начала к концу контейнера). Итераторы reverse_iterator и const_reverse_iterator также работают как Т* и const Т* соответственно, но при увеличении эти итераторы переходят к следующему элементу в обратном порядке перебора (от конца к началу).

Рассмотрим несколько сигнатур insert и erase в контейнере vector:

iterator insert(iterator position, const T& x);

iterator erase (iterator position);

iterator erase ( iterator rangeBegin, iterator rangeEnd);

Аналогичные функции имеются у всех стандартных контейнеров, но тип возвращаемого значения определяется типом контейнера. Обратите внимание: перечисленные функции требуют передачу параметров типа iterator. Не const_iterator , не reverse_iterator и не const_reverse_iterator — только iterator. Хотя контейнеры поддерживают четыре типа итераторов, один из этих типов обладает привилегиями, отсутствующими у других типов. Тип iterator занимает особое место.

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

Из рисунка следует, что iterator преобразуется в const_iterator и reverse_ iterator, а reverse_iterator — в const_reverse_iterator. Кроме того, reverse_iterator преобразуется в iterator при помощи функции base типа reverse_iterator, a const_ reverse_iterator аналогичным образом преобразуется в const_iterator. Однако из рисунка не видно, что итераторы, полученные при вызове base, могут оказаться не теми, которые вам нужны. За подробностями обращайтесь к совету 28.

Обратите внимание: не существует пути от const_iterator к iterator или от const_reverse_iterator к reverse_iterator. Из этого важного обстоятельства следует, что const_iterator и const_reverse_iterator могут вызвать затруднения с некоторыми функциями контейнеров. Таким функциям необходим тип iterator, а из-за отсутствия обратного перехода от const-итераторов к iterator первые становятся в целом бесполезными, если вы хотите использовать их для определения позиции вставки или удаления элементов.

Однако не стоит поспешно заключать, что const-итераторы вообще бесполезны. Это не так. Они прекрасно работают с алгоритмами, поскольку для алгоритмов обычно подходят все типы итераторов, относящиеся к нужной категории. Кроме того, const-итераторы подходят для многих функций контейнеров. Проблемы возникают лишь с некоторыми формами insert и erase.

Обратите внимание на формулировку: const-итераторы становятся в целом бесполезными, если вы хотите использовать их для определения позиции вставки или удаления элементов. Называть их полностью бесполезными было бы неправильно. Const-итераторы могут принести пользу, если вы найдете способ получения iterator для const_iterator или const_reverse_iterator. Такое возможно часто, но далеко не всегда, причем даже в благоприятном случае решение не очевидно, да и эффективным его не назовешь. В двух словах этот вопрос не изложить, если вас заинтересуют подробности — обращайтесь к совету 27. А пока имеющаяся информация позволяет понять, почему типу iterator отдается предпочтение перед его const- и reverse-аналогами.

•Некоторым версиям insert и erase при вызове должен передаваться тип iterator. Const- и reverse-итераторы им не подходят.

•Автоматическое преобразование const-итератора в iterator невозможно, а методика получения iterator на основании const_iterator (совет 27) применима не всегда, да и эффективность ее не гарантируется.

•Преобразование reverse_iterator в iterator может требовать дополнительной регулировки итератора. В совете 28 рассказано, когда и почему возникает такая необходимость.

Из сказанного следует однозначный вывод: если вы хотите работать с контейнерами просто и эффективно и по возможности застраховаться от нетривиальных ошибок, выбирайте iterator вместо его const- и reverse-аналогов.

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

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

typedef deque IntDeque;// Определения типов

typedef IntDeque:iterator Iter;// упрощают работу

typedef IntDeque::const_iterator Constlter; // с контейнерами STL

// и типами итераторов

iter i;

Constlter ci:

// i и ci указывают на элементы // одного контейнера

if (i=ci)...// Сравнить iterator

//c const_iterator

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

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

if (c=i)...// Обходное решение для тех случаев,

// когда приведенное выше сравнение не работает

Подобные проблемы возникают не только при сравнении, но и вообще при смешанном использовании iterator и const_iterator (или reverse_iterator и const_ reverse_iterator) в одном выражении. например, при попытке вычесть один итератор произвольного доступа из другого:

if (i-ci>=3)... // Если i находится минимум в трех позициях после ci...

ваш (правильный) код будет несправедливо отвергнут компилятором, если итераторы относятся к разным типам. Обходное решение остается прежним (перестановка i и ci), но в этом случае приходится учитывать, что i-ci не заменяется на ci-i:

if (c+3<=i)... // Обходное решение на случай, если

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

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

Совет 27. Используйте distance и advance для преобразования const_iterator в iterator

Как было сказано в совете 26, некоторые функции контейнеров, вызываемые с параметрами-итераторами, ограничиваются типом iterator; const_iterator им не подходит. Что же делать, если имеется const_iterator и вы хотите вставить новый элемент в позицию контейнера, обозначенную этим итератором? Const_iterator необходимо каким-то образом преобразовать в iterator, и вы должны принять в этом активное участие, поскольку, как было показано в совете 26, автоматического преобразования const_iterator в iterator не существует.

Я знаю, о чем вы думаете. «Если ничего не помогает, берем кувалду», не так ля? В мире С++ это может означать лишь одно: преобразование типа. Стыдитесь. И где вы набрались таких мыслей?

Давайте разберемся с вредным заблуждением относительно преобразования типа. Посмотрим, что происходит при преобразовании const_iterator в iterator:

typedef deque IntDeque:// Вспомогательные определения типов

typedef IntDeque::iterator Iter;

typedef IntDeque::const_iterator Constlter;

Constlter ci

// ci - const iterator

Iter i(ci);// Ошибка! He существует автоматического

// преобразования const_iterator // в iterator

Iter i(const_cast(ci)): // Ошибка! Преобразование const_iterator

// в iterator невозможно!

В приведенном примере используется контейнер deque, но аналогичный результат будет получен и для list, set, muliset, mulimap и хэшированных контейнеров, упоминавшихся в совете 25. Возможно, строка с преобразованием будет откомпилирована для vector и string, но это особые случаи, которые будут рассмотрены ниже.

Почему же для этих типов контейнеров преобразование не компилируется? Потому что iterator и const_iterator относятся к разным классам, и сходства между ними не больше, чем между string и complex. Попытка преобразования одного типа в другой абсолютно бессмысленна, поэтому вызов const_cast будет отвергнут. Попытки использования static_cast, reintepreter_cast и преобразования в стиле С приведут к тому же результату.

Впрочем, некомпилируемое преобразование все же может откомпилироваться, если итераторы относятся к контейнеру vector или string. Это объясняется тем, что в реализациях данных контейнеров в качестве итераторов обычно используются указатели. В этих реализациях vector::iterator является определением типа для Т*, vector:: const_iterator — для const Т*, string::iterator — для char*, а string:: const_iterator — для const char*. В реализациях данных контейнеров преобразование const_iterator в iterator вызовом const_cast компилируется и даже правильно работает, поскольку оно преобразует const Т* в Т*. Впрочем, даже в этих реализациях reverse_iterator и const_reverse_iterator являются полноценными классами, поэтому const_cast не позволяет преобразовать const_reverse_iterator в reverse_iterator. Кроме того, как объясняется в совете 50, даже реализации, в которых итераторы контейнеров vector и string представлены указателями, могут использовать это представление лишь при компиляции окончательной (release) версии. Все перечисленные факторы приводят к мысли, что преобразование const-итераторов в итераторы не рекомендуется и для контейнеров vector и string, поскольку переносимость такого решения будет сомнительной.

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

typedef deque IntDeque;//См. ранее

typedef IntDeque::iterator Iter;

typedef IntDeque::const_iterator ConstIter;

IntDeque d;

Constlter ci;

// Присвоить ci ссылку на d

Iter i(d.begin());// Инициализировать i значением d.begin()

advance(i,distance(i,ci)); // Переместить i в позицию ci

Решение выглядит настолько простым и прямолинейным, что это невольно вызывает подозрения. Чтобы получить iterator, указывающий на тот же элемент контейнера, что и const_iterator, мы создаем новый iterator в начале контейнера и перемещаем его вперед до тех пор, пока он не удалится на то же расстояние, что и const_iterator! Задачу упрощают шаблоны функций advance и distance, объявленные в . Distance возвращает расстояние между двумя итераторами в одном контейнере, a advance перемещает итератор на заданное расстояние. Когда итераторы i и ci относятся к одному контейнеру, выражение advance( i, distance(i, ci)) переводит их в одну позицию контейнера.

Все хорошо, если бы этот вариант компилировался... но этого не происходит. Чтобы понять причины, рассмотрим объявление distance:

template

typename iterator_traits::difference_type

distance(InputIterator first, InputIterator last);

Не обращайте внимания на то, что тип возвращаемого значения состоит из 56 символов и содержит упоминания зависимых типов (таких как differenceype). Вместо этого проанализируем использование параметра-типа InputIterator:

template

typename iterator_traits::difference_type

distance(InputIterator first,InputIterator last);

При вызове distance компилятор должен определить тип, представленный InputIterator, для чего он анализирует аргументы, переданные при вызове. Еще раз посмотрим на вызов distance в приведенном выше коде:

advance(i,.distance(i,ci)); // Переместить i в позицию ci

При вызове передаются два параметра, i и ci. Параметр i относится к типу iter, который представляет собой определение типа для deque:: iterator. Для компилятора это означает, что InputIterator при вызове distance( соответствует типу deque: iterator. Однако ci относится к типу ConstIter, который представляет собой определение типа для deque::const_iterator. Из этого следует, что InputIterator соответствует типу deque::const_iterator. InputIterator никак не может соответствовать двум типам одновременно, поэтому вызов distance завершается неудачей и каким-нибудь запутанным сообщением об ошибке, из которого можно (или нельзя) понять, что компилятор не смог определить тип InputIterator.

Чтобы вызов нормально компилировался, необходимо ликвидировать неоднозначность. Для этого проще всего явно задать параметр-тип, используемый distance, и избавить компилятор от необходимости определять его самостоятельно:

advanced.distance(i,ci)): // Вычислить расстояние между

// i и ci (как двумя const_iterator)

// и переместить i на это расстояние

Итак, теперь вы знаете, как при помощи advance и distance получить iterator, соответствующий заданному const_iterator, но до настоящего момента совершенно не рассматривался вопрос, представляющий большой практический интерес: насколько эффективна данная методика? Ответ прост: она эффективна настолько, насколько это позволяют итераторы. Для итераторов произвольного доступа, поддерживаемых контейнерами vector, string, deque и т. д., эта операция выполняется с постоянным временем. Для двусторонних итераторов (к этой категории относятся итераторы других стандартных контейнеров, а также некоторых реализаций хэшированных контейнеров — см. совет 25) эта операция выполняется с линейным временем.

Поскольку получение iterator, эквивалентного const_iterator, может потребовать линейного времени, и поскольку это вообще невозможно сделать при недоступности контейнера, к которому относится const_iterator, проанализируйте архитектурные решения, вследствие которых возникла необходимость получения iterator по const_iterator. Результат такого анализа станет дополнительным доводом в пользу совета 26, рекомендующего отдавать предпочтение iterator перед const- и reverse-итераторами.

Совет 28. Научитесь использовать функцию base

При вызове функции base для итератора reverse_iterator будет получен «соответствующий» iterator, однако из сказанного совершенно не ясно, что же при этом происходит. В качестве примера рассмотрим следующий фрагмент, который заносит в вектор числа 1-5, устанавливает reverse_iterator на элемент 3 и инициализирует iterator функцией base:

vector v;

v.reserve(5);

//См. совет 14

for (int i=1;i<=5; ++i){

v.push_back(i);

// Занести в вектор числа 1-5

vector::reverse_iterator ri=

find(v.rbegin(),v.rend(),3);

vector:: iterator i ( ri.base());

// Установить ri на элемент 3

// Присвоить i результат вызова base

// для итератора ri

После выполнения этого фрагмента ситуация выглядит примерно так:

На рисунке видно характерное смещение reverse_iterator и соответствующего базового итератора, воспроизводящего смещение begin() и end() по отношению к begin() и end(), но найти на нем ответы на некоторые вопросы не удается. В частности, рисунок не объясняет, как использовать i для выполнения операций, которые должны были выполняться с ri.

Как упоминалось в совете 26, некоторые функции контейнеров принимают в качестве параметров-итераторов только iterator. Поэтому если вы, допустим, захотите вставить новый элемент в позицию, определяемую итератором п, сделать это напрямую не удастся; функция insert контейнера vector не принимает reverse_ iterator. Аналогичная проблема возникает при удалении элемента, определяемого итератором г . Функции erase не соглашаются на reverse_iterator и принимают только iterator. Чтобы выполнить удаление или вставку, необходимо преобразовать reverse_iterator в iterator при помощи base, а затем воспользоваться iterator для выполнения нужной операции.

Допустим, потребовалось вставить в v новый элемент в позиции, определяемой итератором n. Для определенности будем считать, что вставляется число 99. Учитывая, что n на предыдущем рисунке используется для перебора справа налево, а новый элемент вставляется перед позицией итератора, определяющего позицию вставки, можно ожидать, что число 99 окажется перед числом 3 в обратном порядке перебора. Таким образом, после вставки вектор v будет выглядеть так:

Конечно, мы не можем использовать n для обозначения позиции вставки, поскольку это не iterator. Вместо этого необходимо использовать i. Как упоминалось выше, когда n указывает на элемент 3, i (то есть r. base()) указывает на элемент 4. Именно на эту позицию должен указывать итератор i, чтобы вставленный элемент оказался в той позиции, в которой он бы находился, если бы для вставки можно было использовать итератор r.

Заключение:

• чтобы эмулировать вставку в позицию, заданную итератором ri типа reverse_ iterator, выполните вставку в позицию r.base(). По отношению к операции вставки ri и r.base() эквивалентны, но r.base() в действительности представляет собой iterator, соответствующий ri.

Рассмотрим операцию удаления элемента. Вернемся к взаимосвязи между ri и исходным вектором (по состоянию на момент, предшествующий вставке значения 99):

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

Заключение:

• чтобы эмулировать удаление в позиции, заданной итератором ri типа reverse_ iterator, выполните удаление в позиции, предшествующей ri .base(). По отношению к операции удаления ri и ri .base() не эквивалентны, a ri .base() не является объектом iterator, соответствующим ri.

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

vector v;

… // См. ранее. В вектор v заносятся // числа 1-5

vector::reverse_iterator ri = // Установить ri на элемент 3

find(v.rbegin(),v.rend(),3);

v.erase(--ri .base());// Попытка стирания в позиции.

// предшествующей ri-base():

// для вектора обычно

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

Решение выглядит вполне нормально. Выражение --ri.base() правильно определяет элемент, предшествующий удаляемому. Более того, приведенный фрагмент будет нормально работать для всех стандартных контейнеров, за исключением vector и string. Наверное, он бы мог работать и для этих контейнеров, но во многих реализациях vector и string он не будет компилироваться. В таких реализациях типы iterator (и const_iterator) реализованы в виде встроенных указателей, поэтому результатом вызова i.base() является указатель. В соответствии с требованиями как С, так и С++ указатели, возвращаемые функциями, не могут модифицироваться, поэтому на таких платформах STL выражения типа --i.base() не компилируются. Чтобы удалить элемент в позиции, заданной итератором reverse_iterator, и при этом сохранить переносимость, необходимо избегать модификации возвращаемого значения base. Впрочем, это несложно. Если мы не можем уменьшить результат вызова base, значит, нужно увеличить reverse_iterator и после этого вызвать base!

//См. ранее

v.erase((++ri).base()); // Удалить элемент, на который указывает ri;

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

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

Вероятно, вы уже поняли: говорить о том, что функция base класса reverse_ iterator возвращает «соответствующий» iterator, не совсем правильно. В отношении вставки это действительно так, а в отношении удаления — нет. При преобразовании reverse_iterator в iterator важно знать, какие операции будут выполняться с полученным объектом iterator. Только в этом случае вы сможете определить, подойдет ли он для ваших целей.

Совет 29. Рассмотрите возможность использования istreambuf_iterator при посимвольном вводе

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

ifstream inputFile("interestringData.txt");

string fileData(istream_iterator(inputFile)), // Прочитать inputFile istream iterator0);// в fileData

Но вскоре выясняется, что приведенный синтаксис не копирует в строку пропуски (whitespace), входящие в файл. Это объясняется тем, что isream_iterator производит непосредственное чтение функциями operator<<, а эти функции по умолчанию не читают пропуски.

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

ifstream inputFile("interestingData.txt"):

inputFle.unset(ios::skipws);// Включить режим

// чтения пропусков

// в inputFile

string fileData(istream_iterator(inputFile)), // Прочитать inputFile istream_iterator0);// в fileData.

Теперь все символы InputFile копируются в fileData.

Кроме того, может выясниться, что копирование происходит не так быстро, как вам хотелось бы. Функции operator<<, от которых зависит работа stream_iterator, производят форматный ввод, а это означает, что каждый вызов сопровождается многочисленными служебными операциями. Они должны создать и уничтожить объекты sentry (специальные объекты потоков ввода-вывода, выполняющие начальные и завершающие операции при каждом вызове operator<<); они должны проверить состояние флагов, влияющих на их работу (таких, как skpws); они должны выполнить доскональную проверку ошибок чтения, а в случае обнаружения каких-либо проблем — проанализировать маску исключений потока и определить, нужно ли инициировать исключение. Все перечисленные операции действительно важны при форматном вводе, но если ваши потребности ограничиваются чтением следующего символа из входного потока, без них можно обойтись.

Более эффективное решение основано на использовании неприметного итератора istreambuf_iterator. Итераторы istreambuf_iterator работают аналогично istream_iterator, но если объекты istream_iterator читают отдельные символы из входного потока оператором <<, то объекты streambuf_iterator обращаются прямо к буферу потока и непосредственно читают следующий символ (выражаясь точнее, объект streambuf_iterator читает следующий символ из входного потока s вызовом s.rdbuf ()->sgetc()).

Перейти на использование istreambuf_iiterator при чтении файла так просто, что даже программист Visual Basic сделает это со второй попытки:

ifstream inputFile("interestingData.txt");

string fileData(istreambuf_iterator(inputFile)). istreambuf_iterator0);

На этот раз сбрасывать флаг skpws не нужно, итераторы streambuf_iterator никогда не пропускают символы при вводе и просто возвращают следующий символ из буфера.

По сравнению с istream_iterator это происходит относительно быстро. В проведенных мною простейших тестах выигрыш по скорости достигал 40%, хотя в вашем случае цифры могут быть другими. Не удивляйтесь, если быстродействие будет расти со временем; итераторы istreambuf_iterator населяют один из заброшенных уголков STL, и авторы реализаций еще недостаточно позаботились об их оптимизации. Например, в моих примитивных тестах итераторы istreambuf_iterator одной из реализаций работали всего на 5% быстрее, чем istream_iterator. В таких реализациях остается широкий простор для оптимизации i streambuf_iterator.

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

Раз уж речь зашла о буферизованных итераторах, следует упомянуть и об использовании osreambuf_iterator при неформатном посимвольном выводе. По сравнению с ostream_iterator итераторы ostream_bufiterator обладают меньшими затратами (при меньших возможностях), поэтому обычно они превосходят их по эффективности.

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

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

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

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

Совет 30. Следите за тем, чтобы приемный интервал имел достаточный размер

Контейнеры STL автоматически увеличиваются с добавлением новых объектов (функциями insert, push_front, push_back и т. д.). Автоматическое изменение размеров чрезвычайно удобно, и у многих программистов создается ложное впечатление, что контейнер сам обо всем позаботится и им никогда не придется следить за наличием свободного места. Если бы так!

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

int transmogrify(int х); // Функция вычисляет некое новое значение

// по переданному параметру х

vector values;

… // Заполнение вектора values данными

vector results;// Применить transmogrify к каждому объекту

transform(values.begin(), // вектора values и присоединить возвращаемые

values.end(). // значения к results.

results.end. // Фрагмент содержит ошибку!

transmogrify);

В приведенном примере алгоритм transform получает информацию о том, что приемный интервал начинается с results.end. С этой позиции он и начинает вывод значений, полученных в результате вызова transmogrify для каждого элемента values. Как и все алгоритмы, использующие приемный интервал, transform записывает свои результаты, присваивая значения элементам заданного интервала. Таким образом, transform вызовет transmogrify для values[0] и присвоит результат *results.end(). Затем функция transmogrify вызывается для values[l] с присваиванием результата *(results.end()+1). Происходит катастрофа, поскольку в позиции *results.end() (и тем более в *(results.end()+1) ) не существует объекта! Вызов transform некорректен из-за попытки присвоить значение несуществующему объекту (в совете 50 объясняется, как отладочная реализация STL позволит обнаружить эту проблему на стадии выполнения).

Допуская подобную ошибку, программист почти всегда рассчитывает на то, что результаты вызова алгоритма будут вставлены в приемный контейнер вызовом insert. Если вы хотите, чтобы это произошло, так и скажите. В конце концов, STL — всего лишь библиотека, и читать мысли ей не положено. В нашем примере задача решается построением итератора, определяющего начало приемного интервала, вызовом back_inserter:

vector values:

transform(values.begin(),// Применить transmogrify к каждому

values.end(),// объекту вектора values

back_inserter(results), // и дописать значения в конец results

transmogrify);

При использовании итератора, возвращаемого при вызове back_inserter, вызывается push_back, поэтому back_inserter может использоваться со всеми контейнерами, поддерживающими push_back (то есть со всеми стандартными последовательными контейнерами: vector, string, deque и list). Если вы предпочитаете, чтобы алгоритм вставлял элементы в начало контейнера, Воспользуйтесь front_inserter. Во внутренней реализации front_inserter используется push_front, поэтому front_inserter работает только с контейнерами, поддерживающими эту функцию (то есть deque и list).

… //См. ранее

list results;//Теперь используется