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

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

find

sort

Я написал эту книгу для вас.

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

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

У STL не существует официального определения, и разные авторы вкладывают в этот термин разный смысл. В этой книге термин «STL» относится к компонентам стандартной библиотеки C++, работающим с итераторами. К этой категории относятся стандартные контейнеры (включая string), части библиотеки потоков ввода-вывода, объекты функций и алгоритмы. В нее не входят адаптеры стандартных контейнеров (

stack, queue

priorityqueue

bitset

valarray

С технической точки зрения в мое определение STL не входят расширения стандартной библиотеки C++, в том числе хэшированные контейнеры, односвязные списки, контейнеры

rope

Возможность расширения была заложена в библиотеку STL во время проектирования. Тем не менее, в этой книге основное внимание уделяется использованию STL, а не разработке новых компонентов. Так, в книге почти ничего не сказано о написании собственных алгоритмов, контейнеров и итераторов. На мой взгляд, сначала необходимо в совершенстве освоить существующие возможности STL. Этой теме и посвящена данная книга. Если вы решите заняться созданием STL-подобных компонентов, необходимую информацию можно будет найти в книгах Джосаттиса «The C++ Standard Library» [3] и Остерна «Generic Programming and the STL» [4]. В этой книге упоминается лишь один аспект расширения STL — написание объектов функций. Эффективное использование STL невозможно без объектов функций, поэтому этой теме в книге посвящена вся глава 6.

Ссылки на книги Джосаттиса и Остерна в предыдущем абзаце дают представление о том, как в этой книге оформляются библиографические ссылки. Как правило, я стараюсь включить в ссылку достаточно информации, чтобы ее узнали люди, уже знакомые с этим трудом. Если вы уже читали книги этих авторов, вам не придется обращаться к разделу «Литература» и выяснять, что скрывается за ссылками [3] и [4]. Конечно, в списке литературы приведены полные данные.

Три публикации упоминаются так часто, что номер ссылки обычно не указывается. Первая из них, Международный стандарт C++ [5], в книге именуется просто «Стандартом». Две другие — мои предыдущие книги о C++, «Effective C++» [1] и «More Effective C++» [2].

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

Иногда самый простой выход заключается в переходе на другую реализацию STL (пример приведен в приложении Б). Чем больше вы работаете с STL, тем важнее отличать компилятор от реализации библиотеки. Когда у программиста возникают проблемы с компиляцией правильного кода, он обычно винит во всем компилятор. Однако при работе с STL компилятор может быть в полном порядке, а проблемы оказываются связанными с ошибками в реализации. Чтобы подчеркнуть зависимость программ как от компилятора, так и от реализации библиотеки, я использую термин «платформа STL», под которым понимается комбинация конкретного компилятора с конкретной реализацией STL. Если в книге говорится о проблеме компилятора, значит, виноват именно компилятор. Но если речь идет о проблеме платформы STL, это следует понимать так: «виноват то ли компилятор, то ли библиотека, а может, и то и другое».

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

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

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

string

Все, что говорится о контейнере

string

wstring

string

char

char*

wstring

wchar_t

wchar_t*

string

wstring

basic_string

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

• Контейнеры

vector

r

deque

list

set

multiset

map

multimap

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

istream_iterator

ostream_iterator

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

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

list

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

vector

string

deque

• Любой класс, перегружающий оператор вызова функции (то есть

operator()

• Функции

bind1st

bind2nd

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

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

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

• Операции с логарифмической сложностью с ростом n выполняются за время, пропорциональное логарифму п. Например, операция с миллионом элементов будет выполняться только в три раза дольше операции с сотней элементов, поскольку log n? = 3 log n. Многие операции поиска в ассоциативных контейнерах (например,

set::find

• Время, необходимое для выполнения операций с линейной сложностью, возрастает пропорционально п. Стандартный алгоритм

count

Как правило, операции с постоянной сложностью выполняются быстрее, чем операции с логарифмической сложностью, а последние выполняются быстрее операций с линейной сложностью. Этот принцип особенно четко выполняется для больших значений п, но при относительно малых n операции, которые теоретически должны занимать больше времени, в отдельных случаях выполняются быстрее. За дополнительной информацией о гарантиях сложности в STL обращайтесь к книге Джосаттиса «The C++ Standard Library» [3].

И последнее замечание по поводу терминологии: вспомните, что каждый элемент контейнеров

map

multimap

map<string,double> m;

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

string

double

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

Из приведенного выше примера с

map

#include

#include <map>

#include <string>

using std::map;

using std::string;

map<string. double> m;

Но я предпочитаю оставить в примере лишь самое существенное. При объявлении формального параметра-типа шаблона вместо

class

typename

template <class T>

class Widget{...};

я использую конструкцию

template <typename T>

class Widget{...};

В данном контексте ключевые слова

class

typename

typename

class

typename

class

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

typename

template <typename С>

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

C::const_iterator

C::const_iterator

typename

typename

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

Widget

В книге часто встречаются параметры

lhs

rhs

class Widget {...}:

bool operator==(const Widget& lhs, const Widgets rhs);

При вызове этой функции в контексте

if (х==у) // Предполагается, что х и у

// относятся к классу Widget

Объекту х, находящемуся слева от оператора

==

operator==

lhs

rhs

Что касается имени класса

Widget

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

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