• Операции с логарифмической сложностью с ростом n выполняются за время, пропорциональное логарифму п. Например, операция с миллионом элементов будет выполняться только в три раза дольше операции с сотней элементов, поскольку log n³ = 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 и возвращает результат проверки условия «последний элемент контейнера больше первого». Одно из возможных решений выглядит так:
template <typename С>
bool latGreaterThanFirst(const С& container) {
if (container.empty()) return false;
typename C::const_iterator begin(container.begin());
typename C::const_iterator end(container.end());
return *--end > *begin;
}
В этом примере локальные переменные begin и end относятся к типу C::const_iterator, зависящему от формального параметра C. Поскольку тип C::const_iterator является зависимым, перед ним должно стоять ключевое слово typename. Некоторые компиляторы принимают код без typename, но такой код не переносится на другие платформы.
Надеюсь, вы обратили внимание на жирный шрифт в приведенных примерах. Выделение должно привлечь ваше внимание к особенно важным фрагментам кода. Нередко таким образом подчеркиваются различия между похожими примерами, как, например, при демонстрации двух разных способов объявления параметра T в примере Widget. Аналогичным образом помечаются и важные блоки на рисунках. Например, на диаграмме из совета 5 таким образом помечаются два указателя, изменяемые при вставке нового элемента в список.
В книге часто встречаются параметры lhs и rhs. Эти сокращения означают «left-hand side» («левая сторона») и «right-hand side» («правая сторона») соответственно, они особенно удобны при объявлении операторов. Пример из совета 19:
class Widget {...}:
bool operator==(const Widget& lhs, const Widgets rhs);
При вызове этой функции в контексте
if (х==у) // Предполагается, что х и у
// относятся к классу Widget
Объекту х, находящемуся слева от оператора ==, в объявлении operator== соответствует параметр lhs, а объекту у соответствует параметр rhs.
Что касается имени класса Widget, то оно не имеет никакого отношения к графическим интерфейсам или инструментариям. Этим именем я привык обозначать «некий класс, который что-то делает». Иногда (как, например, на с. 20) имя Widget относится к шаблону класса, а не к классу. В таких случаях я продолжаю говорить о Widget как о классе несмотря на то, что в действительности это шаблон. Столь неформальное отношение к различиям между классами и шаблонами классов, структурами и шаблонами структур, функциями и шаблонами функций безвредно (при условии, что оно не приводит к возникновению неоднозначности в рассматриваемой теме). Если возможны какие-либо недоразумения, я провожу четкие различия между шаблонами и сгенерированными на их основе классами, структурами и функциями.
Сначала я хотел включить в книгу отдельную главу, посвященную вопросам эффективности, но в итоге решил, что лучше оставить привычное деление на советы. Тем не менее многие советы посвящены минимизации затрат памяти и ресурсов на стадии исполнения. Для удобства ниже приводится краткое содержание «виртуальной главы», посвященной эффективности.
Совет 4. Вызывайте empty вместо сравнения size() с нулем
Совет 5. Используйте интервальные функции вместо одноэлементных
Совет 14. Используйте reserve для предотвращения лишних операций перераспределения памяти
Совет 15. Помните о различиях в реализации string
Совет 23. Рассмотрите возможность замены ассоциативных контейнеров сортированными векторами
Совет 24. Тщательно выбирайте между map::operator[] и map::insert
Совет 25. Изучите нестандартные хэшированные контейнеры
Совет 29. Рассмотрите возможность использования istreambuf_iterator при посимвольном вводе
Совет 31. Помните о существовании разных средств сортировки
Совет 44. Используйте функции контейнеров вместо одноименных алгоритмов
Совет 46. Передавайте алгоритмам объекты функций вместо функций
Рекомендации, составляющие 50 советов этой книги, основаны на мнениях и наблюдениях опытнейших программистов STL. Они в краткой форме подводят итог всему, что практически всегда следует (или наоборот, не следует) делать для успешного использования библиотеки STL. С другой стороны, это всего лишь рекомендации, и в некоторых ситуациях их нарушения вполне оправданны. Например, в заголовке совета 7 говорится о необходимости вызова delete для указателей перед уничтожением контейнера. Но из текста совета становится ясно, что это правило действует лишь в тех случаях, когда объекты, на которые ссылаются указатели, должны уничтожаться раньше самого контейнера. Обычно это действительно так, но не всегда. Приведу другой пример — в заголовке совета 35 предлагается использовать алгоритмы STL для выполнения простых сравнений строк без учета регистра, но из текста совета следует, что в некоторых случаях лучше использовать функцию не только внешнюю по отношению к STL, но даже не входящую в стандарт C++!
Только хорошее знание специфики программы и условий ее работы позволит определить, стоит ли нарушать представленные рекомендации. Обычно этого лучше не делать, но в отдельных случаях возможны исключения. Как рабская покорность, так и безрассудное легкомыслие одинаково вредны. Прежде чем сходить с проторенной дороги, убедитесь в том, что для этого есть достаточно веские причины.
