Революционным новшеством STL являются гарантии сложности, то есть ограничения объема работы, выполняемой любыми операциями STL. Таким образом, программист может сравнить относительную эффективность нескольких решений в зависимости от платформы STL. Гарантии сложности выражаются в виде функции от количества элементов в контейнере или интервале (п).
• Операция с постоянной сложностью выполняется за время, не зависящее от п. Например, вставка элемента в список выполняется с постоянной сложностью. Сколько бы элементов ни содержал список, один или миллион, вставка будет занимать практически одинаковое время.
Термин
«постоянная сложность» не стоит воспринимать буквально. Он означает не то, что время выполнения операции остается строго постоянной величиной, а лишь то, что оно не зависит от п. Например, на двух разных платформах STL время выполнения операции «с постоянной сложностью» может заметно отличаться. Такое бывает, когда одна библиотека использует более совершенную реализацию алгоритма или один компилятор выполняет более активную оптимизацию.
• Операции с логарифмической сложностью с ростом n выполняются за время, пропорциональное логарифму п. Например, операция с миллионом элементов будет выполняться только в три раза дольше операции с сотней элементов, поскольку log n^3 = 3 log n. Многие операции поиска в ассоциативных контейнерах (например,
set::find
) обладают логарифмической сложностью.
• Время, необходимое для выполнения операций с линейной сложностью, возрастает пропорционально п. Стандартный алгоритм
count
работает с линейной сложностью, поскольку он должен просмотреть каждый элемент в заданном интервале. Если интервал увеличивается в три раза, объем работы тоже увеличивается втрое, поэтому операция занимает в три раза больше времени.
Как правило, операции с постоянной сложностью выполняются быстрее, чем операции с логарифмической сложностью, а последние выполняются быстрее операций с линейной сложностью. Этот принцип особенно четко выполняется для больших значений п, но при относительно малых n операции, которые теоретически должны занимать больше времени, в отдельных случаях выполняются быстрее. За дополнительной информацией о гарантиях сложности в STL обращайтесь к книге Джосаттиса «The C++ Standard Library» [3].
И последнее замечание по поводу терминологии: вспомните, что каждый элемент контейнеров
map
и
multimap
состоит из двух компонентов. Я обычно называю первый компонент ключом, а второй — ассоциированным значением. Например, в контейнере
map<string,double> m;
ключ относится к типу
string
, а ассоциированное значение — к типу
double
.
Примеры
Книга содержит множество примеров. Все примеры комментируются по мере их приведения, и все же кое-что следует пояснить заранее.
Из приведенного выше примера с
map
видно, что я обычно опускаю директивы
#include
и игнорирую тот факт, что компоненты STL принадлежат пространству имен std. Полное определение m должно было выглядеть так:
#include <map>
#include <string>
using std::map;
using std::string;
map<string. double> m;
Но я предпочитаю оставить в примере лишь самое существенное. При объявлении формального параметра-типа шаблона вместо
class
используется ключевое слово
typename
.
Иначе говоря, вместо конструкции вида
template <class T>
class Widget{...};
я использую конструкцию
template <typename T>
class Widget{...};
В данном контексте ключевые слова
class
и
typename
эквивалентны, но мне кажется, что слово
typename
более четко выражает важную мысль: подходит любой тип, T не обязательно является классом. Если вы предпочитаете объявлять параметры с ключевым словом
class
— пожалуйста. Выбор между
typename
и
class
в этом контексте зависит только от стиля.
Однако в других контекстах стиль не является единственным фактором. Во избежание потенциальных неоднозначностей лексического анализа (я избавлю вас от подробностей) имена типов, зависящие от формальных параметров шаблона, должны предваряться ключевым словом
typename
. Такие типы называются зависимыми типами. Небольшой пример поможет вам лучше понять, о чем идет речь. Предположим, вы пишете шаблон функции, которая получает контейнер STL и возвращает результат проверки условия «последний элемент контейнера больше первого». Одно из возможных решений выглядит так:
, зависящему от формального параметра C. Поскольку тип
C::const_iterator
является зависимым, перед ним должно стоять ключевое слово
typename
. Некоторые компиляторы принимают код без
typename
, но такой код не переносится на другие платформы.
Надеюсь, вы обратили внимание на жирный шрифт в приведенных примерах. Выделение должно привлечь ваше внимание к особенно важным фрагментам кода. Нередко таким образом подчеркиваются различия между похожими примерами, как, например, при демонстрации двух разных способов объявления параметра T в примере
Widget
. Аналогичным образом помечаются и важные блоки на рисунках. Например, на диаграмме из совета 5 таким образом помечаются два указателя, изменяемые при вставке нового элемента в список.
В книге часто встречаются параметры
lhs
и
rhs
. Эти сокращения означают «left-hand side» («левая сторона») и «right-hand side» («правая сторона») соответственно, они особенно удобны при объявлении операторов. Пример из совета 19: