Скотт Мейерс - Эффективное использование STL

Здесь есть возможность читать онлайн «Скотт Мейерс - Эффективное использование STL» весь текст электронной книги совершенно бесплатно (целиком полную версию без сокращений). В некоторых случаях можно слушать аудио, скачать через торрент в формате fb2 и присутствует краткое содержание. Город: СПб., Год выпуска: 2002, ISBN: 2002, Издательство: Питер, Жанр: Программирование, на русском языке. Описание произведения, (предисловие) а так же отзывы посетителей доступны на портале библиотеки ЛибКат.

Эффективное использование STL: краткое содержание, описание и аннотация

Предлагаем к чтению аннотацию, описание, краткое содержание или предисловие (зависит от того, что написал сам автор книги «Эффективное использование STL»). Если вы не нашли необходимую информацию о книге — напишите в комментариях, мы постараемся отыскать её.

В этой книге известный автор Скотт Мейерс раскрывает секреты настоящих мастеров, позволяющие добиться максимальной эффективности при работе с библиотекой STL.
Во многих книгах описываются возможности STL, но только в этой рассказано о том, как работать с этой библиотекой. Каждый из 50 советов книги подкреплен анализом и убедительными примерами, поэтому читатель не только узнает, как решать ту или иную задачу, но и когда следует выбирать то или иное решение — и почему именно такое.

Эффективное использование STL — читать онлайн бесплатно полную книгу (весь текст) целиком

Ниже представлен текст книги, разбитый по страницам. Система сохранения места последней прочитанной страницы, позволяет с удобством читать онлайн бесплатно книгу «Эффективное использование STL», без необходимости каждый раз заново искать на чём Вы остановились. Поставьте закладку, и сможете в любой момент перейти на страницу, на которой закончили чтение.

Тёмная тема
Сбросить

Интервал:

Закладка:

Сделать

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

Четверка алгоритмов set_unon, set_inesection, set_diffeenceи set_symmetric_differenceпредназначена для выполнения со множествами операций с линейным временем. Почему этим алгоритмам нужны сортированные интервалы? Потому что в противном случае они не справятся со своей задачей за линейное время. Начинает прослеживаться некая закономерность — алгоритмы требуют передачи сортированных интервалов для того, чтобы обеспечить лучшее быстродействие, невозможное при работе с несортированными интервалами. В дальнейшем мы лишь найдем подтверждение этой закономерности.

Алгоритмы mergeи inplace_mergeвыполняют однопроходное слияние с сортировкой: они читают два сортированных интервала и строят новый сортированный интервал, содержащий все элементы обоих исходных интервалов. Эти алгоритмы работают с линейным временем, что было бы невозможно без предварительной сортировки исходных интервалов.

Перечень алгоритмов, работающих с сортированными интервалами, завершает алгоритм includes. Он проверяет, входят ли все объекты одного интервала в другой интервал. Поскольку includesрассчитывает на сортировку обоих интервалов, он обеспечивает линейное время. Без этого он в общем случае работает медленнее.

В отличие от перечисленных алгоритмов, uniqueи unique_copyспособны работать и с несортированными интервалами. Но давайте взглянем на описание uniqueв Стандарте (курсив мой): «…Удаляет из каждой смежной группы равных элементов все элементы, кроме первого».

Иначе говоря, если вы хотите, чтобы алгоритм uniqueудалил из интервала все дубликаты (то есть обеспечил «уникальность» значений в интервале), сначала необходимо позаботиться о группировке всех дубликатов. Как нетрудно догадаться, именно эта задача и решается в процессе сортировки. На практике алгоритм uniqueобычно применяется для исключения всех дубликатов из интервала, поэтому интервал, передаваемый при вызове unique(или unique_copy), должен быть отсортирован. Программисты Unix могут обратить внимание на поразительное сходство между алгоритмом STL uniqueи командой Unix uniq— подозреваю, что совпадение отнюдь не случайное.

Следует помнить, что uniqueисключает элементы из интервала по тому же принципу, что и remove, то есть ограничивается «логическим» удалением. Если вы не совсем уверены в том, что означает этот термин, немедленно обратитесь к советам 32 и 33. Трудно выразить, сколь важно доскональное понимание принципов работы removeи remove-подобных алгоритмов. Общих представлений о происходящем недостаточно. Если вы не знаете, как работают эти алгоритмы, у вас будут неприятности.

Давайте посмотрим, что же означает само понятие «сортированный интервал». Поскольку STL позволяет задать функцию сравнения, используемую в процессе сортировки, разные интервалы могут сортироваться по разным критериям. Например, интервал intможно отсортировать как стандартным образом (то есть по возрастанию), так и с использованием greater, то есть по убыванию. Интервал объектов Widgetможет сортироваться как по цене, так и по дате. При таком изобилии способов сортировки очень важно, чтобы данные сортировки, находящиеся в распоряжении контейнера STL, была логически согласованы. При передаче сортированного интервала алгоритму, который также получает функцию сравнения, проследите за тем, чтобы переданная функция сравнения вела себя так же, как функция, применявшаяся при сортировке интервала.

Рассмотрим пример неправильного подхода:

vector v; // Создать вектор, заполнить

… // данными, отсортировать

sort(v.begin(), v.end(), greater()); // по убыванию.

… // Операции с вектором

// (не изменяющие содержимого).

bool a5Exists = // Поиск числа 5 в векторе.

binary_search(v.begin(), v.end(), 5); // Предполагается, что вектор

Читать дальше
Тёмная тема
Сбросить

Интервал:

Закладка:

Сделать

Похожие книги на «Эффективное использование STL»

Представляем Вашему вниманию похожие книги на «Эффективное использование STL» списком для выбора. Мы отобрали схожую по названию и смыслу литературу в надежде предоставить читателям больше вариантов отыскать новые, интересные, ещё непрочитанные произведения.


Отзывы о книге «Эффективное использование STL»

Обсуждение, отзывы о книге «Эффективное использование STL» и просто собственные мнения читателей. Оставьте ваши комментарии, напишите, что Вы думаете о произведении, его смысле или главных героях. Укажите что конкретно понравилось, а что нет, и почему Вы так считаете.

x