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

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

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

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

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

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

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

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

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

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

И последнее замечание по поводу терминологии: вспомните, что каждый элемент контейнеров map и multimap состоит из двух компонентов. Я обычно называю первый компонент ключом, а второй — ассоциированным значением. Например, в контейнере

map m;

ключ относится к типу string, а ассоциированное значение — к типу double.

Примеры

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

Из приведенного выше примера с map видно, что я обычно опускаю директивы #include и игнорирую тот факт, что компоненты STL принадлежат пространству имен std. Полное определение m должно было выглядеть так:

#include

#include

using std::map;

using std::string;

map m;

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

template

class Widget{...};

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

template T>

class Widget{...};

В данном контексте ключевые слова class и typename эквивалентны, но мне кажется, что слово typename более четко выражает важную мысль: подходит любой тип, T не обязательно является классом. Если вы предпочитаете объявлять параметры с ключевым словом class — пожалуйста. Выбор между typename и class в этом контексте зависит только от стиля.