•Время, необходимое для выполнения операций с линейной сложностью, возрастает пропорционально п. Стандартный алгоритм >count работает с линейной сложностью, поскольку он должен просмотреть каждый элемент в заданном интервале. Если интервал увеличивается в три раза, объем работы тоже увеличивается втрое, поэтому операция занимает в три раза больше времени.
Как правило, операции с постоянной сложностью выполняются быстрее, чем операции с логарифмической сложностью, а последние выполняются быстрее операций с линейной сложностью. Этот принцип особенно четко выполняется для больших значений п, но при относительно малых n операции, которые теоретически должны занимать больше времени, в отдельных случаях выполняются быстрее. За дополнительной информацией о гарантиях сложности в STL обращайтесь к книге Джосаттиса «The С++ 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 Т>
>class Widget{...};
В данном контексте ключевые слова >class и >typename эквивалентны, но мне кажется, что слово >typename более четко выражает важную мысль: подходит любой тип, Т не обязательно является классом. Если вы предпочитаете объявлять параметры с ключевым словом >class — пожалуйста. Выбор между >typename и >class в этом контексте зависит только от стиля.
Однако в других контекстах стиль не является единственным фактором. Во избежание потенциальных неоднозначностей лексического анализа (я избавлю вас от подробностей) имена типов, зависящие от формальных параметров шаблона, должны предваряться ключевым словом
