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

При описании STL практически невозможно обойти стороной подсчет ссылок. Как будет показано в советах 7 и 33, любая архитектура, основанная на контейнерах указателей, практически всегда основана на подсчете ссылок. Кроме того, подсчет ссылок используется во многих внутренних реализациях string, причем, как показано в совете 15, это обстоятельство иногда приходится учитывать при программировании. Предполагается, что читатель знаком с основными принципами работы механизма подсчета ссылок, а если не знаком — необходимую информацию можно найти в любом учебнике C++ среднего или высокого уровня. Например, в книге «More Effective C++» соответствующий материал приведен в советах 28 и 29. Но даже если вы не знаете, что такое подсчет ссылок, и не горите желанием поскорее узнать, не беспокойтесь. Материал книги в целом все равно останется вполне доступным.

Все, что говорится о контейнере string, в равной степени относится и к wstring, его аналогу с расширенной кодировкой символов. Соответственно, любые упоминания о связи между stringи charили cha r* относятся и к связи между wstringи wchar_tили wchar_t*. Иначе говоря, отсутствие специальных упоминаний о строках с расширенной кодировкой символов не означает, что в STL они не поддерживаются. Контейнеры stringи wstringявляются специализациями одного шаблона basic_string.

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

• Контейнеры vector, st ring, dequeи listотносятся к категории стандартных последовательных контейнеров. К категории стандартных ассоциативных контейнеров относятся контейнеры set, multiset, mapи multimap.

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

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

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

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

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

• Функции bind1stи bind2ndназываются функциями привязки (binders).

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

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

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

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

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

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