Скотт Мейерс - Эффективное использование STL
list<int>::iterator 11,12; // Передача двусторонних итераторов
sort(11.2);// алгоритму, которому необходимы итераторы
// произвольного доступа
•Если вы используете стандартный компонент STL (например, контейнер vector или string, алгоритм for_each), а компилятор утверждает, что он понятия не имеет, что имеется в виду, скорее всего, вы забыли включить необходимый заголовочный файл директивой #include. Как объясняется в совете 48, эта проблема может нарушить работоспособность кода, успешно компилировавшегося в течение некоторого времени, при переносе его на другую платформу.
Совет 50. Помните о web-сайтах, посвященных STL
Интернет богат информацией об STL. Если ввести в любой поисковой системе запрос «STL», вы получите сотни ссылок, часть из которых даже будет содержать полезную информацию. Впрочем, большинство программистов STL в поисках не нуждается и хорошо знает следующие сайты:
•сайт SGI STL, http://www.sgi.com/tech/stl;
•сайт STLport, http://stlport.org;
•сайт Boost, http://www.boost.org.
Ниже я постараюсь объяснить, почему эти сайты заслуживают вашего внимания.
Сайт SGI STL
Web-сайт SGI STL не случайно находится в начале списка. На нем имеется подробная документация по всем компонентам STL. Многие программисты рассматривают его как основной источник электронной документации незав4исимо от используемой платформы STL. Документацию собрал Мэтт Остерн (Matt Austern), который позднее дополнил ее и представил в книге «Generic Programming and the STL» [4]. Материал не сводится к простому описанию компонентов STL. Например, описание потоковой безопасности контейнеров STL (см. совет 12) основано на материалах сайта SGI STL.
На сайте SGI программисту предлагается свободно распространяемая реализация STL. Она была адаптирована лишь для ограниченного круга компиляторов, но поставка STL легла в основу распространенной поставки STLport, описанной ниже. Более того, в реализацию STL от SGI входят некоторые нестандартные компоненты, делающие программирование в STL не только более мощным и гибким, но и более интересным. Некоторые из них стоит выделить.
•Хэшированные ассоциативные контейнеры hash_set, hash_multiset, hash_map и hash_multimap. За дополнительной информацией об этих контейнерах обращайтесь к совету 25.
•Односвязный список slist. Контейнер slist реализован наиболее стандартным образом, а итераторы указывают на те узлы списка, на которые они и должны указывать. К сожалению, этот факт оборачивается дополнительными затратами при реализации функций insert и erase, поскольку обе функции должны модифицировать указатель на следующий узел списка в узле, предшествующем тому, на который указывает итератор. В двусвязном списке (например, в стандартном контейнере list) это не вызывает проблем, но в односвязном списке возврат к предыдущему узлу является операцией с линейной сложностью. В контейнере slist из реализации SGI функции insert и erase выполняются с линейной сложностью вместо постоянной, что является существенным недостатком. В реализации SGI эта проблема решается при помощи нестандартных (но зато работающих с постоянной сложностью) функций insert_after и erase_after. В сопроводительной документации говорится:
«...Если окажется, что функции insert_after и erase_after плохо подходят для ваших целей, и вам часто приходится вызывать функции insert и erase в середине списка, вероятно, вместо slist лучше воспользоваться контейнером list».
В реализацию Dinkumware также входит односвязный список slist, но в нем используется другая архитектура итераторов, сохраняющая постоянную сложность при вызовах insert и erase. За дополнительной информацией о Dimkumware обращайтесь к приложению Б.
•Контейнер rope, аналог string для очень больших строк. В документации SGI контейнер rope описывается так:
«Контейнер rope представляет собой масштабированную разновидность string: он предназначен для эффективного выполнения операций со строками в целом. Затраты времени на такие операции, как присваивание, конкатенация и выделение подстроки, практически не зависят от длины строки. В отличие от строк С, контейнер rope обеспечивает разумное представление для очень длинных строк (например, содержимого буфера текстового редактора или сообщений электронной почты)».
Во внутреннем представлении контейнер rope реализуется в виде дерева подстрок с подсчетом ссылок, при этом каждая строка хранится в виде массива char. Одна из интересных особенностей интерфейса rope заключается в том, что функции begin и end всегда возвращают тип const_iterator. Это сделано для предотвращения операций, изменяющих отдельные символы. Такие операции обходятся слишком дорого. Контейнер rope оптимизирован для операций с текстом в целом или большими фрагментами (присваивание, конкатенация и выделение подстроки); операции с отдельными символами выполняются неэффективно.
•Различные нестандартные объекты функций и адаптеры. Некоторые классы функторов из исходной реализации HP STL не вошли в Стандарт С++. Опытным мастерам старой школы больше всего не хватает функторов select1st и select2nd, чрезвычайно удобных при работе с контейнерами map и multimap. Функтор select1st возвращает первый компонент объекта pair, а функтор select2nd возвращает второй компонент объекта pair. Пример использования этих нестандартных шаблонов классов функторов:
map<int,string> m;
// Вывод всех ключей map в cout
transform(m.begin(),m.end(),
ostream_iterator<int>(cout,"n"),
select1st<map<int,string>::value_type>());
// Создать вектор и скопировать в него
// все ассоциированные значения из map
vector<string> v:
transforms.begin(),m.end() ,back_inserter(v),
select2nd<map<int,string>::value_type>());
Как видите, функторы select1st и select2nd упрощают использование алгоритмов в ситуациях, где обычно приходится писать собственные циклы (см. совет 43). С другой стороны, вследствие нестандартности функторов вас могут обвинить в написании непереносимого и вдобавок плохо сопровождаемого кода (см. совет 47).
Настоящих фанатов STL это нисколько не волнует. Они считают, что отсутствие select1st и select2nd в Стандарте само по себе является вопиющей несправедливостью.
К числу нестандартных объектов функций, входящих в реализацию STL, также принадлежат объекты identity, project1st, project2nd, compose1 и compose2. Информацию о них можно найти на сайте, хотя пример использования compose2 приводился на с. 172 настоящей книги. Надеюсь, я убедил вас в том, что посещение web-сайта SGI принесет несомненную пользу.
Реализация библиотеки от SGI выходит за рамки STL. Первоначально ставилась цель разработки полной реализации стандартной библиотеки С++ за исключением компонентов, унаследованных из С (предполагается, что у вас в распоряжении уже имеется стандартная библиотека С). По этой причине с сайта SGI также стоит получить реализацию библиотеки потоков ввода-вывода С++. Как следует ожидать, эта реализация хорошо интегрируется с реализацией STL от SGI, но при этом по быстродействию она превосходит многие аналогичные реализации, поставляемые с компиляторами С++.
Сайт STLport
Главная отличительная особенность STLport заключается в том, что эта модифицированная версия реализации STL от SGI (включая потоки ввода-вывода и т. д.) была перенесена более чем на 20 компиляторов. STLport, как и библиотека SGI, распространяется бесплатно. Если ваш код должен работать сразу на нескольких платформах, вы избавите себя от множества хлопот, если возьмете за основу унифицированную реализацию STLport и будете использовать ее со всеми компиляторами.
Большинство изменений кода SGI в реализации STLport связано с улучшением переносимости, однако STLport является единственной известной мне реализацией, в которой предусмотрен «отладочный режим» для диагностики случаев неправильного использования STL — компилируемых, но приводящих к непредсказуемым последствиям во время работы программы. Например, в совете 30 распространенная ошибка записи за концом контейнера поясняется следующим примером:
int transmogrify(int х); // Функция вычисляет некое новое значение
// по переданному параметру х
vector<int> values;
// Заполнение вектора values данными
vector<int> results;
transform(values.begin(), // Попытка записи за концом results! values.end(),
results.end,
transmogrify);
Этот фрагмент компилируется, но во время выполнения работает непредсказуемо. Если вам повезет, проблемы возникнут при вызове transform, и отладка будет относительно элементарной. Гораздо хуже, если вызов transform испортит данные где-то в другом месте адресного пространства, но это обнаружится лишь позднее. В этом случае определение причины порчи данных становится задачей — как бы выразиться? — весьма нетривиальной.
Отладочный режим STLport значительно упрощает эту задачу. При выполнении приведенного выше вызова transform выдается следующее сообщение (предполагается, что реализация STLport установлена в каталоге C:STLport):
