• Время, необходимое для выполнения операций с линейной сложностью, возрастает пропорционально п. Стандартный алгоритм

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

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

И последнее замечание по поводу терминологии: вспомните, что каждый элемент контейнеров

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

ключ относится к типу

, а ассоциированное значение — к типу .

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

Из приведенного выше примера с

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

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

используется ключевое слово . Иначе говоря, вместо конструкции вида

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

В данном контексте ключевые слова

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

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

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

В этом примере локальные переменные

и относятся к типу , зависящему от формального параметра C. Поскольку тип является зависимым, перед ним должно стоять ключевое слово . Некоторые компиляторы принимают код без , но такой код не переносится на другие платформы.

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

. Аналогичным образом помечаются и важные блоки на рисунках. Например, на диаграмме из совета 5 таким образом помечаются два указателя, изменяемые при вставке нового элемента в список.

В книге часто встречаются параметры

и . Эти сокращения означают «left-hand side» («левая сторона») и «right-hand side» («правая сторона») соответственно, они особенно удобны при объявлении операторов. Пример из совета 19:

При вызове этой функции в контексте