Эффективное использование STL - [6]

Шрифт
Интервал

) обладают логарифмической сложностью.

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

Как правило, операции с постоянной сложностью выполняются быстрее, чем операции с логарифмической сложностью, а последние выполняются быстрее операций с линейной сложностью. Этот принцип особенно четко выполняется для больших значений п, но при относительно малых n операции, которые теоретически должны занимать больше времени, в отдельных случаях выполняются быстрее. За дополнительной информацией о гарантиях сложности в STL обращайтесь к книге Джосаттиса «The C++ 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 T>

>class Widget{...};

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

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

>template

>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 как о классе несмотря на то, что в действительности это шаблон. Столь неформальное отношение к различиям между классами и шаблонами классов, структурами и шаблонами структур, функциями и шаблонами функций безвредно (при условии, что оно не приводит к возникновению неоднозначности в рассматриваемой теме). Если возможны какие-либо недоразумения, я провожу четкие различия между шаблонами и сгенерированными на их основе классами, структурами и функциями.


Еще от автора Скотт Мейерс
Эффективный и современный С++. 42 рекомендации по использованию С++11 и С++14

Эффективный и современный С++Освоение С++11 и С++14 — это больше, чем просто ознакомление с вводимыми этими стандартами возможностями (например, объявлениями типов auto, семантикой перемещения, лямбда-выражениями или поддержкой многопоточности). Вопрос в том, как использовать их эффективно, чтобы создаваемые программы были корректны, эффективны и переносимы, а также чтобы их легко можно было сопровождать. Именно этим вопросам и посвящена данная книга, описывающая создание по-настоящему хорошего программного обеспечения с использованием C++11 и С++14 — т.е.


Как функции, не являющиеся методами, улучшают инкапсуляцию

Когда приходится инкапсулировать, то иногда лучше меньше, чем большеЯ начну со следующего утверждения: Если вы пишете функцию, которая может быть выполнена или как метод класса, или быть внешней по отношению к классу, Вы должны предпочесть ее реализацию без использования метода. Такое решение увеличивает инкапсуляцию класса. Когда Вы думаете об использовании инкапсуляции, Вы должны думать том, чтобы не использовать методы.Удивлены? Читайте дальше.


Рекомендуем почитать
Графика DirectX в Delphi

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


Вторая жизнь старых компьютеров

Сейчас во многих школах, институтах и других учебных заведениях можно встретить компьютеры старого парка, уже отслужившие свое как морально, так и физически. На таких компьютерах можно изучать разве что Dos, что далеко от реалий сегодняшнего дня. К тому же у большинства, как правило, жесткий диск уже в нерабочем состоянии. Но и выбросить жалко, а новых никто не дает. Различные спонсоры, меценаты, бывает, подарят компьютер (один) и радуются, как дети. Спасибо, конечно, большое, но проблемы, как вы понимаете, этот компьютер в общем не решает, даже наоборот, усугубляет, работать на старых уже как-то не хочется, теперь просто есть с чем сравнивать.


DirectX 8. Начинаем работу с DirectX Graphics

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


Симуляция частичной специализации

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


Обработка событий в С++

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


Питон — модули, пакеты, классы, экземпляры

Python - объектно-ориентированный язык сверхвысокого уровня. Python, в отличии от Java, не требует исключительно объектной ориентированности, но классы в Python так просто изучить и так удобно использовать, что даже новые и неискушенные пользователи быстро переходят на ОО-подход.


SQL: быстрое погружение

Что общего между самыми востребованными профессиями и стремительным увеличением количества информации в мире? Ответ: язык структурированных запросов (SQL). SQL — рабочая лошадка среди языков программирования, основа основ для современного анализа и управления данными. Книга «SQL: быстрое погружение» идеальна для всех, кто ищет новые перспективы карьерного роста; для разработчиков, которые хотят расширить свои навыки и знания в программировании; для любого человека, даже без опыта, кто хочет воспользоваться возможностями будущего, в котором будут править данные.


Чистый код. Создание, анализ и рефакторинг

Даже плохой программный код может работать. Однако если код не является «чистым», это всегда будет мешать развитию проекта и компании-разработчика, отнимая значительные ресурсы на его поддержку и «укрощение». Эта книга посвящена хорошему программированию. Она полна реальных примеров кода. Мы будем рассматривать код с различных направлений: сверху вниз, снизу вверх и даже изнутри. Прочитав книгу, вы узнаете много нового о коде. Более того, вы научитесь отличать хороший код от плохого. Вы узнаете, как писать хороший код и как преобразовать плохой код в хороший. Книга состоит из трех частей.


Изучаем Python

Книга "Изучаем Python" - это ускоренный курс, который позволит вам сэкономить время и сразу начать писать работоспособные программы (игры, визуализации данных, веб-приложения и многое другое). Хотите стать программистом? В первой части книги вам предстоит узнать о базовых принципах программирования, познакомиться со списками, словарями, классами и циклами, вы научитесь создавать программы и тестировать код. Во второй части книги вы начнете использовать знания на практике, работая над тремя крупными проектами: создадите собственную "стрелялку" с нарастающей сложностью уровней, займетесь работой с большими наборами данных и освоите их визуализацию, и, наконец, создадите полноценное веб-приложение на базе Django, гарантирующее конфиденциальность пользовательской информации. Если вы решились разобраться в том что такое программирование, не нужно ждать.


Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих

Алгоритмы - это всего лишь пошаговые алгоритмы решения задач, и большинство таких задач уже были кем-то решены, протестированы и проверены. Можно, конечно, погрузится в глубокую философию гениального Кнута, изучить многостраничные фолианты с доказательствами и обоснованиями, но хотите ли вы тратить на это свое время? Откройте великолепно иллюстрированную книгу и вы сразу поймете, что алгоритмы - это просто. А грокать алгоритмы - это веселое и увлекательное занятие.