Вы уже знакомы с STL. Вы умеете создавать контейнеры, перебирать их содержимое, добавлять и удалять элементы, а также использовать общие алгоритмы — такие, как find и sort. Но вы никак не можете отделаться от впечатления, что используете лишь малую часть возможностей STL. Задачи, которые должны решаться просто, решаются сложно; операции, которые должны выполняться просто и прямолинейно, приводят к утечке ресурсов или ведут себя непредсказуемо. Процедуры, которые должны работать с максимальной эффективностью, поглощают больше времени или памяти, чем положено. Да, вы умеете использовать библиотеку STL, но не уверены в том, что используете ее эффективно. Я написал эту книгу для вас.
В ней я покажу, как организовать взаимодействие между компонентами STL с тем, чтобы в полной мере использовать архитектуру библиотеки. Вы научитесь разрабатывать простые решения для простых задач и проектировать элегантные решения для более сложных ситуаций. В книге описаны стандартные ошибки использования STL и приведены рекомендации относительно того, как их избежать. Это поможет ликвидировать утечку ресурсов, предотвратить появление непереносимого кода и непредсказуемое поведение программ. Различные приемы оптимизации кода заставят библиотеку STL работать быстро и эффективно, как и было задумано при ее проектировании.
Прочитав эту книгу, вы будете лучше программировать в STL. Программирование станет более продуктивным и интересным занятием. Работать с STL интересно, но эффективная работа с библиотекой — занятие чрезвычайно захватывающее, от которого просто невозможно оторваться. Даже при беглом взгляде на STL становится ясно, что это замечательная библиотека, но ее достоинства гораздо шире и глубже, чем можно себе представить. Я занимаюсь программированием около 30 лет, но я еще никогда не встречал ничего похожего на STL.
Определение, использование и расширение STL
У STL не существует официального определения, и разные авторы вкладывают в этот термин разный смысл. В этой книге термин «STL» относится к компонентам стандартной библиотеки С++, работающим с итераторами. К этой категории относятся стандартные контейнеры (включая string), части библиотеки потоков ввода-вывода, объекты функций и алгоритмы. В нее не входят адаптеры стандартных контейнеров (stack, queue и priorityqueue), контейнеры bitset и valarray, не поддерживающие итераторы, а также массивы. Хотя массивы поддерживают итераторы в форме указателей, они являются частью языка С++, а не библиотеки.
С технической точки зрения в мое определение STL не входят расширения стандартной библиотеки С++, в том числе хэшированные контейнеры, односвязные списки, контейнеры rope и различные нестандартные объекты функций. Несмотря на это, программистам STL следует помнить о существовании этих расширений, поэтому я упоминаю о них там, где это уместно. В совете 25 приведен обзор нестандартных хэшированных контейнеров. В настоящее время эти контейнеры не входят в STL, но их аналоги почти наверняка будут включены в следующую версию стандартной библиотеки С++.
Возможность расширения была заложена в библиотеку STL во время проектирования. Тем не менее, в этой книге основное внимание уделяется использованию STL, а не разработке новых компонентов. Так, в книге почти ничего не сказано о написании собственных алгоритмов, контейнеров и итераторов. На мой взгляд, сначала необходимо в совершенстве освоить существующие возможности STL. Этой теме и посвящена данная книга. Если вы решите заняться созданием STL-подобных компонентов, необходимую информацию можно будет найти в книгах Джосаттиса «The С++ Standard Library» [3] и Остерна «Generic Programming and the STL» [4]. В этой книге упоминается лишь один аспект расширения STL — написание объектов функций. Эффективное использование STL невозможно без объектов функций, поэтому этой теме в книге посвящена вся глава 6.
Ссылки
Ссылки на книги Джосаттиса и Остерна в предыдущем абзаце дают представление о том, как в этой книге оформляются библиографические ссылки. Как правило, я стараюсь включить в ссылку достаточно информации, чтобы ее узнали люди, уже знакомые с этим трудом. Если вы уже читали книги этих авторов, вам не придется обращаться к разделу «Литература» и выяснять, что скрывается за ссылками [3] и [4]. Конечно, в списке литературы приведены полные данные.
Три публикации упоминаются так часто, что номер ссылки обычно не указывается. Первая из них, Международный стандарт С++ [5], в книге именуется просто «Стандартом». Две другие — мои предыдущие книги о С++, «Effective С++» [1] и «More Effective С++» [2].
STL и Стандарты
В книге я часто ссылаюсь на Стандарт С++, потому что основное внимание уделяется переносимой, стандартной версии С++. Теоретически все примеры, приведенные в книге, должны работать во всех реализациях С++. К сожалению, на практике это не так. Вследствие недоработок в компиляторах и реализациях STL даже правильный код иногда не компилируется или работает не так, как положено. В самых типичных случаях описывается суть проблемы и предлагаются обходные решения.
Иногда самый простой выход заключается в переходе на другую реализацию STL (пример приведен в приложении Б). Чем больше вы работаете с STL, тем важнее отличать компилятор от реализации библиотеки. Когда у программиста возникают проблемы с компиляцией правильного кода, он обычно винит во всем компилятор. Однако при работе с STL компилятор может быть в полном порядке, а проблемы оказываются связанными с ошибками в реализации. Чтобы подчеркнуть зависимость программ как от компилятора, так и от реализации библиотеки, я использую термин «платформа STL», под которым понимается комбинация конкретного компилятора с конкретной реализацией STL. Если в книге говорится о проблеме компилятора, значит, виноват именно компилятор. Но если речь идет о проблеме платформы STL, это следует понимать так: «виноват то ли компилятор, то ли библиотека, а может, и то и другое».
Обычно я говорю о компиляторах во множественном числе. Я искренне убежден в том, что проверка работоспособности программы на нескольких компиляторах улучшает ее качество (и особенно переносимость). Более того, использование нескольких компиляторов помогает распутать гордиев узел сообщений об ошибках, выданных при неправильном применении STL (рекомендации по расшифровке этих сообщений приводятся в совете 49).
Уделяя особое внимание тому, чтобы код соответствовал стандартам, я также стремлюсь избежать конструкций с непредсказуемым поведением. Последствия выполнения таких конструкций на стадии работы программы могут быть любыми. К сожалению, иногда эти конструкции могут делать именно то, что требуется, а это создает вредные иллюзии. Слишком многие программисты считают, что непредсказуемое поведение всегда ведет к очевидным проблемам, то есть сбоям обращений к сегментам или другим катастрофическим последствиям. Результаты могут быть гораздо более тонкими (например, искажение данных, редко используемых в программе); кроме того, разные запуски программы могут приводить к разным результатам. У непредсказуемого поведения есть хорошее неформальное определение: «Работает у меня, работает у тебя, работает во время тестирования, но не работает у самого важного клиента». Непредсказуемого поведения следует избегать, поэтому я особо выделяю некоторые стандартные случаи в книге. Будьте начеку и учитесь распознавать ситуации, чреватые непредсказуемым поведением.
Подсчет ссылок
При описании STL практически невозможно обойти стороной подсчет ссылок. Как будет показано в советах 7 и 33, любая архитектура, основанная на контейнерах указателей, практически всегда основана на подсчете ссылок. Кроме того, подсчет ссылок используется во многих внутренних реализациях string, причем, как показано в совете 15, это обстоятельство иногда приходится учитывать при программировании. Предполагается, что читатель знаком с основными принципами работы механизма подсчета ссылок, а если не знаком — необходимую информацию можно найти в любом учебнике С++ среднего или высокого уровня. Например, в книге «More Effective С++» соответствующий материал приведен в советах 28 и 29. Но даже если вы не знаете, что такое подсчет ссылок, и не горите желанием поскорее узнать, не беспокойтесь. Материал книги в целом все равно останется вполне доступным.
string
и
wstring
Все, что говорится о контейнере string, в равной степени относится и к wstring, его аналогу с расширенной кодировкой символов. Соответственно, любые упоминания о связи между string и char или cha r* относятся и к связи между wstring и wchar_t или wchar_t*. Иначе говоря, отсутствие специальных упоминаний о строках с расширенной кодировкой символов не означает, что в STL они не поддерживаются. Контейнеры string и wstring являются специализациями одного шаблона basic_string.
Терминология
Данная книга не является учебником начального уровня по STL. Предполагается, что читатель уже владеет основными материалом. Тем не менее следующие термины настолько важны, что я счел необходимым особо выделить их.
•Контейнеры vector, string, deque и list относятся к категории стандартных последовательных контейнеров. К категории стандартных ассоциативных контейнеров относятся контейнеры set, multiset, map и multimap.
•Итераторы делятся на пять категорий в соответствии с поддерживаемыми операциями. Итераторы ввода обеспечивают доступ только для чтения и позволяют прочитать каждую позицию только один раз. Итераторы вывода обеспечивают доступ только для записи и позволяют записать данные в каждую позицию только один раз. Итераторы ввода и вывода построены по образцу операций чтения-записи в потоках ввода-вывода (например, в файлах), поэтому неудивительно, что самыми распространенными представителями итераторов ввода и вывода являются istream_iterator и ostream_iterator соответственно.
Прямые итераторы обладают свойствами итераторов ввода и вывода, но они позволяют многократно производить чтение или запись в любой позиции. Оператор — ими не поддерживается, поэтому они позволяют производить передвижение только в прямом направлении с некоторой степенью эффективности. Все стандартные контейнеры STL поддерживают итераторы, превосходящие эту категорию итераторов по своим возможностям, но, как будет показано в совете 25, одна из архитектур хэшированных контейнеров основана на использовании прямых итераторов. Контейнеры односвязных списков (см. совет 50) также поддерживают прямые итераторы.
Двусторонние итераторы похожи на прямые итераторы, однако они позволяют перемещаться не только в прямом, но и в обратном направлении. Они поддерживаются всеми стандартными ассоциативными контейнерами, а также контейнером list.
Итераторы произвольного доступа обладают всеми возможностями двусторонних итераторов, но они также позволяют переходить в прямом или обратном направлении на произвольное расстояние за один шаг. Итераторы произвольного доступа поддерживаются контейнерами vecto r , string и deque. В массивах функциональность итераторов произвольного доступа обеспечивается указателями.
•Любой класс, перегружающий оператор вызова функции (то есть operator () ), является классом функтора. Объекты, созданные на основе таких классов, называются объектами функций, или функторами. Как правило, в STL объекты функций могут свободно заменяться «обычными» функциями, поэтому под термином «объекты функций» часто объединяются как функции С++, так и функторы.
•Функции bind1st и bind2nd называются функциями привязки (binders).
Революционным новшеством STL являются гарантии сложности, то есть ограничения объема работы, выполняемой любыми операциями STL. Таким образом, программист может сравнить относительную эффективность нескольких решений в зависимости от платформы STL. Гарантии сложности выражаются в виде функции от количества элементов в контейнере или интервале (п).
•Операция с постоянной сложностью выполняется за время, не зависящее от п. Например, вставка элемента в список выполняется с постоянной сложностью. Сколько бы элементов ни содержал список, один или миллион, вставка будет занимать практически одинаковое время.
Термин «постоянная сложность» не стоит воспринимать буквально. Он означает не то, что время выполнения операции остается строго постоянной величиной, а лишь то, что оно не зависит от п. Например, на двух разных платформах STL время выполнения операции «с постоянной сложностью» может заметно отличаться. Такое бывает, когда одна библиотека использует более совершенную реализацию алгоритма или один компилятор выполняет более активную оптимизацию.
•Операции с логарифмической сложностью с ростом n выполняются за время, пропорциональное логарифму п. Например, операция с миллионом элементов будет выполняться только в три раза дольше операции с сотней элементов, поскольку log n3 = 3 log n. Многие операции поиска в ассоциативных контейнерах (например, set::find) обладают логарифмической сложностью.
•Время, необходимое для выполнения операций с линейной сложностью, возрастает пропорционально п. Стандартный алгоритм count работает с линейной сложностью, поскольку он должен просмотреть каждый элемент в заданном интервале. Если интервал увеличивается в три раза, объем работы тоже увеличивается втрое, поэтому операция занимает в три раза больше времени.
Как правило, операции с постоянной сложностью выполняются быстрее, чем операции с логарифмической сложностью, а последние выполняются быстрее операций с линейной сложностью. Этот принцип особенно четко выполняется для больших значений п, но при относительно малых n операции, которые теоретически должны занимать больше времени, в отдельных случаях выполняются быстрее. За дополнительной информацией о гарантиях сложности в STL обращайтесь к книге Джосаттиса «The С++ Standard Library» [3].
И последнее замечание по поводу терминологии: вспомните, что каждый элемент контейнеров map и multimap состоит из двух компонентов. Я обычно называю первый компонент ключом, а второй — ассоциированным значением. Например, в контейнере
map
ключ относится к типу string, а ассоциированное значение — к типу double.
Примеры
Книга содержит множество примеров. Все примеры комментируются по мере их приведения, и все же кое-что следует пояснить заранее.
Из приведенного выше примера с map видно, что я обычно опускаю директивы #include и игнорирую тот факт, что компоненты STL принадлежат пространству имен std. Полное определение m должно было выглядеть так:
#include
#include
using std::map;
using std::string;
map
Но я предпочитаю оставить в примере лишь самое существенное. При объявлении формального параметра-типа шаблона вместо class используется ключевое слово typename . Иначе говоря, вместо конструкции вида
template
class Widget{...};
я использую конструкцию
template
class Widget{...};
В данном контексте ключевые слова class и typename эквивалентны, но мне кажется, что слово typename более четко выражает важную мысль: подходит любой тип, Т не обязательно является классом. Если вы предпочитаете объявлять параметры с ключевым словом class — пожалуйста. Выбор между typename и class в этом контексте зависит только от стиля.
Однако в других контекстах стиль не является единственным фактором. Во избежание потенциальных неоднозначностей лексического анализа (я избавлю вас от подробностей) имена типов, зависящие от формальных параметров шаблона, должны предваряться ключевым словом typename. Такие типы называются зависимыми типами. Небольшой пример поможет вам лучше понять, о чем идет речь. Предположим, вы пишете шаблон функции, которая получает контейнер STL и возвращает результат проверки условия «последний элемент контейнера больше первого». Одно из возможных решений выглядит так:
template
bool latGreaterThanFirst(const С& container)
{
if(container.empty()) return false:
typename C::const_iterator begin(container.begin());
typename C::const_iterator end(container.end());
return *--end > *begin;
}
В этом примере локальные переменные begin и end относятся к типу С::const_iterator, зависящему от формального параметра С. Поскольку тип С:: const_iterator является зависимым, перед ним должно стоять ключевое слово typename. Некоторые компиляторы принимают код без typename, но такой код не переносится на другие платформы.
Надеюсь, вы обратили внимание на жирный шрифт в приведенных примерах. Выделение должно привлечь ваше внимание к особенно важным фрагментам кода. Нередко таким образом подчеркиваются различия между похожими примерами, как, например, при демонстрации двух разных способов объявления параметра Т в примере Widget. Аналогичным образом помечаются и важные блоки на рисунках. Например, на диаграмме из совета 5 таким образом помечаются два указателя, изменяемые при вставке нового элемента в список.
В книге часто встречаются параметры lhs и rhs. Эти сокращения означают «left-hand side» («левая сторона») и «right-hand side» («правая сторона») соответственно, они особенно удобны при объявлении операторов. Пример из совета 19:
class Widget {...}:
bool operator==(const Widget& lhs . const Widgets rhs):
При вызове этой функции в контексте
if (х==у) // Предполагается, что х и у
// относятся к классу Widget
Объекту х, находящемуся слева от оператора =, в объявлении operator-= соответствует параметр Ihs, а объекту у соответствует параметр rhs.
Что касается имени класса Widget, то оно не имеет никакого отношения к графическим интерфейсам или инструментариям. Этим именем я привык обозначать «некий класс, который что-то делает». Иногда (как, например, на с. 20) имя Widget относится к шаблону класса, а не к классу. В таких случаях я продолжаю говорить о Widget как о классе несмотря на то, что в действительности это шаблон. Столь неформальное отношение к различиям между классами и шаблонами классов, структурами и шаблонами структур, функциями и шаблонами функций безвредно (при условии, что оно не приводит к возникновению неоднозначности в рассматриваемой теме). Если возможны какие-либо недоразумения, я провожу четкие различия между шаблонами и сгенерированными на их основе классами, структурами и функциями.
Вопросы эффективности
Сначала я хотел включить в книгу отдельную главу, посвященную вопросам эффективности, но в итоге решил, что лучше оставить привычное деление на советы. Тем не менее многие советы посвящены минимизации затрат памяти и ресурсов на стадии исполнения. Для удобства ниже приводится краткое содержание «виртуальной главы», посвященной эффективности.
Совет 4.Вызывайте empty вместо сравнения size() с нулем
Совет 5.Используйте интервальные функции вместо одноэлементных
Совет 14.Используйте reserve для предотвращения лишних операций перераспределения памяти
Совет 15.Помните о различиях в реализации string
Совет 23.Рассмотрите возможность замены ассоциативных контейнеров сортированными векторами
Совет 24.Тщательно выбирайте между map::operator[] и map::insert
Совет 25.Изучите нестандартные хэшированные контейнеры
Совет 29.Рассмотрите возможность использования istreambuf_iterator при посимвольном вводе
Совет 31.Помните о существовании разных средств сортировки
Совет 44.Используйте функции контейнеров вместо одноименных алгоритмов
Совет 46.Передавайте алгоритмам объекты функций вместо функций
Рекомендации
Рекомендации, составляющие 50 советов этой книги, основаны на мнениях и наблюдениях опытнейших программистов STL. Они в краткой форме подводят итог всему, что практически всегда следует (или наоборот, не следует) делать для успешного использования библиотеки STL. С другой стороны, это всего лишь рекомендации, и в некоторых ситуациях их нарушения вполне оправданны. Например, в заголовке совета 7 говорится о необходимости вызова delete для указателей перед уничтожением контейнера. Но из текста совета становится ясно, что это правило действует лишь в тех случаях, когда объекты, на которые ссылаются указатели, должны уничтожаться раньше самого контейнера. Обычно это действительно так, но не всегда. Приведу другой пример — в заголовке совета 35 предлагается использовать алгоритмы STL для выполнения простых сравнений строк без учета регистра, но из текста совета следует, что в некоторых случаях лучше использовать функцию не только внешнюю по отношению к STL, но даже не входящую в стандарт С++!
Только хорошее знание специфики программы и условий ее работы позволит определить, стоит ли нарушать представленные рекомендации. Обычно этого лучше не делать, но в отдельных случаях возможны исключения. Как рабская покорность, так и безрассудное легкомыслие одинаково вредны. Прежде чем сходить с проторенной дороги, убедитесь в том, что для этого есть достаточно веские причины.