Скотт Мейерс - Эффективное использование STL

Эффективное использование STL

Предисловие

«...На нем не было ленточки! Не было ярлыка! Не было коробки и не было мешка!»

Я впервые написал о STL (Standard Template Library) в 1995 году. Моя книга «More Effective С++» завершалась кратким обзором библиотеки. Но этого оказалось недостаточно, и вскоре я начал получать сообщения с вопросом, когда будет написана книга «Effective STL».

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

Затем я заметил нечто удивительное. Несмотря на все проблемы с переносом и скверное качество документации, несмотря на сообщения компилятора, напоминавшие бессмысленное нагромождение символов, многие из моих клиентов все равно работали с STL. Более того, они не просто экспериментировали с библиотекой, а использовали ее в коммерческих версиях своих программ! Для меня это

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

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

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

Скотт Дуглас Мейерс Стаффорд, Орегон Апрель 2001 г.

Благодарности

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

Другим выдающимся источником информации были конференции Usenet; посвященные языку С++, особенно comp.lang.c++.moderated («clcm»), comp.std.c++ и microsoft.public.vc.stl. Свыше десяти лет участники этих и других конференций отвечали на мои вопросы и ставили задачи, над которыми мне приходилось думать. Я глубоко благодарен сообществу Usenet за помощь в работе над этой книгой и моими предыдущими публикациями по С++.

Мое понимание STL формировалось под влиянием ряда публикаций, самые важные из которых перечислены в конце книги. Особенно много полезного я почерпнул из труда Джосаттиса «The С++ Standard Library» [3].

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

В совете 1 замечание о том, что узловые контейнеры обеспечивают лучшую поддержку транзакционной семантики, позаимствовано из раздела 5.11.2 «The С++ Standard Library» [3]. Пример использования typedef при изменении типа распределителя памяти из совета 2 был предложен Марком Роджерсом. Совет 5 вдохновлен статьeй Ривса (Reeves) «STL Gotchas» [17]. В основу совета 8 заложен совет 37 книги Саттера «Exceptional С++» [8], а Кевлин Хенни (Kevlin Henney) предоставил важную информацию о проблемах, возникающих при использовании контейнеров auto_ptr. В конференциях Usenet Мэтт Остерн (Matt Austem) предоставил примеры использования распределителей памяти, включенные мной в совет 11. Совет 12 основан на материалах сайта SGI STL [21], посвященных потоковой безопасности. Информация о подсчете ссылок в многопоточной среде из совета 13 почерпнута из статьи Саттера [20]. Идея совета 15 была подсказана статьей Ривса «Using Standard string in the Real World, Part 2» [18]. Методика непосредственной записи данных в vector, продемонстрированная в совете 16, была предложена Марком Роджерсом. В совет 17 была включена информация из Usenet, авторы — Симел Наран (Siemel Naran) и Карл Баррон (Carl Barron). Совет 18 был позаимствован из статьи Саттера «When Is a Container Not a Container?» [12]. Для совета 20 Марк Роджерс предложил идею преобразования указателя в объект посредством разыменования, а Скотт Левандовски (Scott Lewandowski) разработал представленную версию DereferenceLess. Совет 21 основан на сообщении Дуга Харрисона (Doug Harrison) в конференцию microsoft.public.vc.stl, но решение о том, чтобы ограничить рамки этого совета проблемой равенства, принял я сам. Совет 22 основан на статье Саттера «Standard Library News: sets and maps» [13]. Совет 23 был подсказан статьей Остерна «Why You Shouldn't Use set — and What to Use Instead» [15]; Дэвид Смоллберг (David Smallberg) усовершенствовал мою реализацию DataCompare. Описание хэшированных контейнеров Dinkumware основано на статье Плаугера (Plauger) «Hash Tables» [16]. Марк Роджерс не согласен с выводами совета 26, но первоначально этот совет был подсказан его замечанием относительно того, что некоторые функции контейнеров принимают только аргументы типа iterator. Работа над советом 29 вдохновлялась дискуссиями в Usenet с участием Мэтта Остерна и Джеймса Канце (James Kanze); на меня также повлияла статья Клауса Крефта (Klaus Kreft) и Анжелики Лангер (Angelika Langer) «А Sophisticated Implementation of User-Defined Inserters and Extractors» [25]. Совет 30 основан на материалак раздела 5.4.2 книги Джосаттиса «The С++ Standard Library» [3]. В совете 31 Марко Далла Гасперина (Marco Dalla Gasperina) предложил пример использования nth_element для вычисления медианы, а использование этого алгоритма для поиска процентилей взято прямо из раздела 18.7.1 книги Страуструпа (Stroustrup) «The С++ Programming Language*. Совет 32 был вдохновлен материалами раздела 5.6.1 книги Джосаттиса «The С++ Standard Library*. Совет 35 появился под влиянием статьи Остерна «How to Do Case-Insensitive String Comparison» [11], а сообщения Джеймса Канце и Джона Потте-ра (John Potter) помогли мне лучше разобраться в сути происходящего. Реализация copy_if, приведенная в совете 36, позаимствована из раздела 18.6.1 книги Страуструпа «The С++ Programming Language» [7]. В основу совета 39 заложены публикации Джосаттиса, который впервые упомянул о «предикатах с состоянием» в своей книге «The С++ Standard Library» [3] и в статье «Predicates vs. Function Objects» [14]. В своей книге я использую его пример и рекомевдую предложенное им решение, хотя термин «чистая функция» принадлежит мне. В совете 41 Мeтт Остерн подтвердил мои подозрения относительно происхождения имен mem_fun и mem_fun_ref. Совет 42 берет свое начало из лекции, прочитанной мне Марком Роджерсом, когда я нарушил рекомендацию этого совета. Марку Роджерсу также принадлежит приведенное в совете 44 замечание о том, что при внешнем поиске в контейнерах map и multimap анализируются оба компонента пары, тогда как при поиске функциями контейнера учитывается только первый компонент (ключ). В совете 45 использована информация от разных участников clem, среди которых Джон Поттер, Марсин Касперски (Marcin Kasperski), Pete Becker (Пит Бекер), Деннис Йель (Dennis Yelle) и Дэвид Абрахаме (David Abrahams). Дэвид Смолл-берг подсказал мне идею применения equal_range для поиска на базе эквивалентности и подсчета результатов в сортированных последовательных контейнерах. Андрей Александреску (Andrei Alexandrescu) помог разобраться в условиях возникновения проблемы «ссылки на ссылку», упоминаемой в совете 50; приведенный в книге пример основан на аналогичном примере Марка Роджерса, взятом с сайта Boost [22].