String и wstring

Все, что говорится о контейнере stri ng, в равной степени относится и к wstri ng, его аналогу с расширенной кодировкой символов. Соответственно, любые упоминания о связи между string и char или char* относятся и к связи между wstring и wchar t или wchar t*. Иначе говоря, отсутствие специальных упоминаний о строках с расширенной кодировкой символов не означает, что в STL они не поддерживаются. Контейнеры string и wstring являются специализациями одного шаблона basic string.

Терминология

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

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

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

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

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

Моге Effective С++ соответствующий материал приведен в советах 28 и 29. Но даже если вы не знаете, что такое подсчет ссылок, и не горите желанием поскорее узнать, не беспокойтесь. Материал книги в целом все равно останется вполне доступным.

Терминология 19

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

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

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

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

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

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

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

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

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

Примеры

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

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

finclude <map> iinclude <string>

using std::map: using std:istring:

map<string. double> m:

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

template <class Т> class Widget{...}:

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

template <typenaine Т> class Widget{...}:

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

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

template <typename С>

bool latGreaterThanFirstCconst С& container) {

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

map<string,clouble> m;

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