В этой книге известный автор Скотт Мейерс раскрывает секреты настоящих мастеров, позволяющие добиться максимальной эффективности при работе с библиотекой STL. Во многих книгах описываются возможности STL, но только в этой рассказано о том, как работать с этой библиотекой. Каждый из 50 советов книги подкреплен анализом и убедительными примерами, поэтому читатель узнает не только, как решать ту или иную задачу, но и когда следует выбирать то или иное решение — и почему именно такое.
Содержание
Предисловие
Благодарности
Введение
Определение, использование и расширение STL
Ссылки
STL и Стандарты
Подсчет ссылок
string и wstring
Терминология
Примеры
Вопросы эффективности
Рекомендации
Глава 1 Контейнеры
Совет 1. Внимательно подходите к выбору контейнера
Совет 2. Остерегайтесь иллюзий контейнерно-независимого кода
Совет 3. Реализуйте быстрое и корректное копирование объектов в контейнерах
Совет 4. Вызывайте empty вместо сравнения size() с нулем
Совет 5. Используйте интервальные функции вместо одноэлементных
Совет 6. Остерегайтесь странностей лексического разбора C++
Совет 7. При использовании контейнеров указателей, для которых вызывался оператор new, не забудьте вызвать delete для указателей перед уничтожением контейнера
Совет 8. Никогда не создавайте контейнеры, содержащие auto_ptr
Совет 9. Тщательно выбирайте операцию удаления
Совет 10. Помните о правилах и ограничениях распределителей памяти
Совет 11. Учитывайте область применения пользовательских распределителей памяти
Совет 12. Разумно оценивайте потоковую безопасность контейнеров STL
Глава 2 Контейнеры vector и string
Совет 13. Используйте vector и string вместо динамических массивов
Совет 14. Используйте reserve для предотвращения лишних операций перераспределения памяти
Совет 15. Помните о различиях в реализации string
Совет 16. Научитесь передавать данные vector и string функциям унаследованного интерфейса
Совет 17. Используйте "фокус с перестановкой" для уменьшения емкости
Совет 18. Избегайте vector
Глава 3 Ассоциативные контейнеры
Совет 19. Помните о различиях между равенством и эквивалентностью
Совет 20. Определите тип сравнения для ассоциативного контейнера, содержащего указатели
Совет 21. Следите за тем, чтобы функции сравнения возвращали false в случае равенства
Совет 22. Избегайте изменения ключа "на месте" в контейнерах set и multiset
Совет 23. Рассмотрите возможность замены ассоциативных контейнеров сортированными векторами
Совет 24. Тщательно выбирайте между map::operator[] и map::insert
Совет 25. Изучите нестандартные хэшированные контейнеры
Глава 4 Итераторы
Совет 26. Старайтесь использовать iterator вместо const_iterator, reverse_iterator и const_reverse_iterator
Совет 27. Используйте distance и advance для преобразования const_iterator в iterator
Совет 28. Научитесь использовать функцию base
Совет 29. Рассмотрите возможность использования istreambuf_iterator при посимвольном вводе
Глава 5 Алгоритмы
Совет 30. Следите за тем, чтобы приемный интервал имел достаточный размер
Совет 31. Помните о существовании разных средств сортировки
Совет 32. Сопровождайте вызовы remove-подобных алгоритмов вызовом erase
Совет 33. Будьте внимательны при использовании remove-подобных алгоритмов с контейнерами указателей
Совет 34. Помните о том, какие алгоритмы получают сортированные интервалы
Совет 35. Реализуйте простые сравнения строк без учета регистра символов с использованием mismatch или lexicographical_compare
Совет 36. Правильно реализуйте copy_if Совет 37. Используйте accumulate или for_each для обобщения интервальных данных
Глава 6 Функции, функторы и классы функций
Совет 38. Проектируйте классы функторов для передачи по значению
Совет 39. Реализуйте предикаты в виде "чистых" функций
Совет 40. Классы функторов должны быть адаптируемыми
Совет 41. Разберитесь, для чего нужны ptr_fun, mem_fun и mem_fun_ref
Совет 42. Следите за тем, чтобы конструкция less означала operator<
Глава 7 Программирование в STL
Совет 43. Используйте алгоритмы вместо циклов
Совет 44. Используйте функции контейнеров вместо одноименных алгоритмов
Совет 45. Различайте алгоритмы count, find, binary_search, lower_bound, upper_bound и equal_range
Совет 46. Передавайте алгоритмам объекты функций вместо функций
Совет 47. Избегайте "нечитаемого" кода
Совет 48. Всегда включайте нужные заголовки
Совет 49. Научитесь читать сообщения компилятора
Совет 50. Помните о web-сайтах, посвященных STL
Сайт SGI STL
Сайт STLport
Сайт Boost
Литература
Книги, написанные мной
Книги, написанные другими авторами
Ошибки и опечатки
Приложение А. Локальные контексты
Сравнение строк без учета регистра символов
Первая попытка
Локальный контекст
Локальные контексты в C++
Фасет collate
Сравнение строк без учета регистра
Приложение Б. Замечания по поводу платформ STL от Microsoft
Шаблоны функций классов в STL
MSVC версий 4-6
Обходное решение для MSVC4-5
Обходное решение для MSVC6
Алфавитный указатель
ОТРЫВОК
Введение
Вы уже знакомы с STL. Вы умеете создавать контейнеры, перебирать их содержимое, добавлять и удалять элементы, а также использовать общие алгоритмы - такие, как find и sort. Но вы никак не можете отделаться от впечатления, что используете лишь малую часть возможностей STL. Задачи, которые должны решаться просто, решаются сложно; операции, которые должны выполняться просто и прямолинейно, приводят к утечке ресурсов или ведут себя непредсказуемо. Процедуры, которые должны работать с максимальной эффективностью, поглощают больше времени или памяти, чем положено. Да,
вы умеете использовать библиотеку STL, но не уверены в том, что используете ее эффективно.
Я написал эту книгу для вас.
В ней я покажу, как организовать взаимодействие между компонентами STL с тем, чтобы в полной мере использовать архитектуру библиотеки. Вы научитесь разрабатывать простые решения для простых задач и проектировать элегантные решения для более сложных ситуаций. В книге описаны стандартные ошибки использования STL и приведены рекомендации относительно того, как их избежать. Это поможет ликвидировать утечку ресурсов, предотвратить появление непереносимого кода и непредсказуемое поведение программ. Различные приемы оптимизации кода заставят библиотеку STL
работать быстро и эффективно, как и было задумано при ее проектировании.
Прочитав эту книгу, вы будете лучше программировать в STL. Программирование станет более продуктивным и интересным занятием. Работать с STL интересно, но эффективная работа с библиотекой - занятие чрезвычайно захватывающее, от которого просто невозможно оторваться. Даже при беглом взгляде на STL становится ясно, что это замечательная библиотека, но ее достоинства гораздо шире и глубже, чем можно себе представить. Я занимаюсь программированием около 30 лет, но я еще никогда не встречал ничего похожего на STL.
Определение, использование и расширение STL
У STL не существует официального определения, и разные авторы вкладывают в этот термин разный смысл. В этой книге термин "STL" относится к компонентам стандартной библиотеки C++, работающим с итераторами. К этой категории относятся стандартные контейнеры (включая string), части библиотеки потоков ввода-вывода, объекты функций и алгоритмы. В нее не входят адаптеры стандартных контейнеров (stack, queue и priority_queue), контейнеры bitset и valarray, не поддерживающие итераторы, а также массивы. Хотя массивы поддерживают итераторы в форме указателей, они являются частью языка C++, а не
библиотеки.
С технической точки зрения в мое определение STL не входят расширения стандартной библиотеки C++, в том числе хэшированные контейнеры, односвязные списки, контейнеры rope и различные нестандартные объекты функций. Несмотря на это, программистам STL следует помнить о существовании этих расширений, поэтому я упоминаю о них там, где это уместно. В совете 25 приведен обзор нестандартных хэшированных контейнеров. В настоящее время эти контейнеры не входят в STL, но их аналоги почти наверняка будут включены в следующую версию стандартной библиотеки C++.
Возможность расширения была заложена в библиотеку STL во время проектирования. Тем не менее, в этой книге основное внимание уделяется использованию STL, а не разработке новых компонентов. Так, в книге почти ничего не сказано о написании собственных алгоритмов, контейнеров и итераторов. На мой взгляд, сначала необходимо в совершенстве освоить существующие возможности STL. Этой теме и посвящена данная книга. Если вы решите заняться созданием STL-подобных компонентов, необходимую информацию можно будет найти в книгах Джосаттиса "The С++ Standard Library" [3] и Остерна "Generic
Programming and the STL" [4]. В этой книге упоминается лишь один аспект расширения STL - написание объектов функций. Эффективное использование STL невозможно без объектов функций, поэтому этой теме в книге посвящена вся глава 6.
Ссылки
Ссылки на книги Джосаттиса и Остерна в предыдущем абзаце дают представление о том, как в этой книге оформляются библиографические ссылки. Как правило, я стараюсь включить в ссылку достаточно информации, чтобы ее узнали люди, уже знакомые с этим трудом. Если вы уже читали книги этих авторов, вам не придется обращаться к разделу "Литература" и выяснять, что скрывается за ссылками [3] и [4]. Конечно, в списке литературы приведены полные данные.
Три публикации упоминаются так часто, что номер ссылки обычно не указывается. Первая из них, Международный cтандарт C++ [5], в книге именуется просто "Стандартом". Две другие - мои предыдущие книги о C++, "Effective C++" [1] и "More Effective C++" [2].
STL и Стандарты
В книге я часто ссылаюсь на Стандарт C++, потому что основное внимание уделяется переносимой, стандартной версии C++. Теоретически все примеры, приведенные в книге, должны работать во всех реализациях C++. К сожалению, на практике это не так. Вследствие недоработок в компиляторах и реализациях STL даже правильный код иногда не компилируется или работает не так, как положено. В самых типичных случаях описывается суть проблемы и предлагаются обходные решения.
Иногда самый простой выход заключается в переходе на другую реализацию STL (пример приведен в приложении Б). Чем больше вы работаете с STL, тем важнее отличать компилятор от реализации библиотеки. Когда у программиста возникают проблемы с компиляцией правильного кода, он обычно винит во всем компилятор. Однако при работе с STL компилятор может быть в полном порядке, а проблемы оказываются связанными с ошибками в реализации. Чтобы подчеркнуть зависимость программ как от компилятора, так и от реализации библиотеки, я использую термин "платформа STL", под которым
понимается комбинация конкретного компилятора с конкретной реализацией STL. Если в книге говорится о проблеме компилятора, значит, виноват именно компилятор. Но если речь идет о проблеме платформы STL, это следует понимать так: "виноват то ли компилятор, то ли библиотека, а может, и то и другое".
Обычно я говорю о компиляторах во множественном числе. Я искренне убежден в том, что проверка работоспособности программы на нескольких компиляторах улучшает ее качество (и особенно переносимость). Более того, использование нескольких компиляторов помогает распутать гордиев узел сообщений об ошибках, выданных при неправильном применении STL (рекомендации по расшифровке этих сообщений приводятся в совете 49).
Уделяя особое внимание тому, чтобы код соответствовал стандартам, я также стремлюсь избежать конструкций с непредсказуемым поведением. Последствия выполнения таких конструкций на стадии работы программы могут быть любыми. К сожалению, иногда эти конструкции могут делать именно то, что требуется, а это создает вредные иллюзии. Слишком многие программисты считают, что непредсказуемое поведение всегда ведет к очевидным проблемам, то есть сбоям обращений к сегментам или другим катастрофическим последствиям. Результаты могут быть гораздо более тонкими
(например, искажение данных, редко используемых в программе); кроме того, разные запуски программы могут приводить к разным результатам. У непредсказуемого поведения есть хорошее неформальное определение: "Работает у меня, работает у тебя, работает во время тестирования, но не работает у самого важного клиента". Непредсказуемого поведения следует избегать, поэтому я особо выделяю некоторые стандартные случаи в книге. Будьте начеку и учитесь распознавать ситуации, чреватые непредсказуемым поведением.
Подсчет ссылок
При описании STL практически невозможно обойти стороной подсчет ссылок. Как будет показано в советах 7 и 33, любая архитектура, основанная на контейнерах указателей, практически всегда основана на подсчете ссылок. Кроме того, подсчет ссылок используется во многих внутренних реализациях string, причем, как показано в совете 15, это обстоятельство иногда приходится учитывать при программировании. Предполагается, что читатель знаком с основными принципами работы механизма подсчета ссылок, а если не знаком - необходимую информацию можно найти в любом учебнике C+
+ среднего или высокого уровня. Например, в книге "More Effective C++" соответствующий материал приведен в советах 28 и 29. Но даже если вы не знаете, что такое подсчет ссылок, и не горите желанием поскорее узнать, не беспокойтесь. Материал книги в целом все равно останется вполне доступным.
string и wstring
Все, что говорится о контейнере string, в равной степени относится и к wstring, его аналогу с расширенной кодировкой символов. Соответственно, любые упоминания о связи между string и char или char* относятся и к связи между 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.
Итераторы произвольного доступа обладают всеми возможностями двусторонних итераторов, но они также позволяют переходить в прямом или обратном направлении на произвольное расстояние за один шаг. Итераторы произвольного доступа поддерживаются контейнерами vector, string и deque. В массивах функциональность итераторов произвольного доступа обеспечивается указателями.
Любой класс, перегружающий оператор вызова функции (то есть operator()), является классом функтора. Объекты, созданные на основе таких классов, называются объектами функций, или функторами. Как правило, в STL объекты функций могут свободно заменяться "обычными" функциями, поэтому под термином "объекты функций" часто объединяются как функции C++, так и функторы.
Функции bind1st и bind2nd называются функциями привязки (binders).
Революционным новшеством STL являются гарантии сложности, то есть ограничения объема работы, выполняемой любыми операциями STL. Таким образом, программист может сравнить относительную эффективность нескольких решений в зависимости от платформы STL. Гарантии сложности выражаются в виде функции от количества элементов в контейнере или интервале (n).
Операция с постоянной сложностью выполняется за время, не зависящее от n. Например, вставка элемента в список выполняется с постоянной сложностью. Сколько бы элементов ни содержал список, один или миллион, вставка будет занимать практически одинаковое время.
Термин "постоянная сложность" не стоит воспринимать буквально. Он означает не то, что время выполнения операции остается строго постоянной величиной, а лишь то, что оно не зависит от n. Например, на двух разных платформах STL время выполнения операции "с постоянной сложностью" может заметно отличаться. Такое бывает, когда одна библиотека использует более совершенную реализацию алгоритма или один компилятор выполняет более активную оптимизацию.
Операции с логарифмической сложностью с ростом n выполняются за время, пропорциональное логарифму n. Например, операция с миллионом элементов будет выполняться только в три раза дольше операции с сотней элементов, поскольку log n3 = 3log n. Многие операции поиска в ассоциативных контейнерах (например, set::find) обладают логарифмической сложностью.
Время, необходимое для выполнения операций с линейной сложностью, возрастает пропорционально n. Стандартный алгоритм count работает с линейной сложностью, поскольку он должен просмотреть каждый элемент в заданном интервале. Если интервал увеличивается в три раза, объем работы тоже увеличивается втрое, поэтому операция занимает в три раза больше времени.
Как правило, операции с постоянной сложностью выполняются быстрее, чем операции с логарифмической сложностью, а последние выполняются быстрее операций с линейной сложностью. Этот принцип особенно четко выполняется для больших значений n, но при относительно малых n операции, которые теоретически должны занимать больше времени, в отдельных случаях выполняются быстрее. За дополнительной информацией о гарантиях сложности в STL обращайтесь к книге Джосаттиса "The C++ Standard Library" [3].
И последнее замечание по поводу терминологии: вспомните, что каждый элемент контейнеров map и multimap состоит из двух компонентов. Я обычно называю первый компонент ключом, а второй - ассоциированным значением. Например, в контейнере
map m;
ключ относится к типу string, а ассоциированное значение - к типу double.
Примеры
Книга содержит множество примеров. Все примеры комментируются по мере их приведения, и все же кое-что следует пояснить заранее.
Из приведенного выше примера с map видно, что я обычно опускаю директивы #include и игнорирую тот факт, что компоненты STL принадлежат пространству имен std. Полное определение m должно было выглядеть так:
#include |