Книги
чёрным по белому
Главное меню
Главная О нас Добавить материал Поиск по сайту Карта книг Карта сайта
Книги
Археология Архитектура Бизнес Биология Ветеринария Военная промышленность География Геология Гороскоп Дизайн Журналы Инженерия Информационные ресурсы Искусство История Компьютерная литература Криптология Кулинария Культура Лингвистика Математика Медицина Менеджмент Металлургия Минералогия Музыка Научная литература Нумизматика Образование Охота Педагогика Политика Промышленные производства Психология Путеводители Религия Рыбалка Садоводство Саморазвитие Семиотика Социология Спорт Столярное дело Строительство Техника Туризм Фантастика Физика Футурология Химия Художественная литература Экология Экономика Электроника Энергетика Этика Юриспруденция
Новые книги
Цуканов Б.И. "Время в психике человека" (Медицина)

Суворов С. "Танк Т-64. Первенец танков 2-го поколения " (Военная промышленность)

Нестеров В.А. "Основы проэктирования ракет класса воздух- воздух и авиационных катапульных установок для них" (Военная промышленность)

Фогль Б. "101 вопрос, который задала бы ваша кошка своему ветеринару если бы умела говорить" (Ветеринария)

Яблоков Н.П. "Криминалистика" (Юриспруденция)
Реклама

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

Мейерс С. Эффективное использование STL. Библиотека программиста — Спб.: Питер , 2002. — 224 c.
ISBN 5-94723-382-7
Скачать (прямая ссылка): effektivnoeispolzovaniestlbibliote2002.djvu
Предыдущая << 1 .. 65 66 67 68 69 70 < 71 > 72 73 74 75 76 77 .. 114 >> Следующая

перемещения между позициями интервала, в котором производится поиск.
Четверка алгоритмов set_union, set_iintersection, set_di fference и
set_symmetriс_ di fference предназначена для выполнения со множествами
операций с линейным временем. Почему этим алгоритмам нужны сортированные
интервалы? Потому что в противном случае они не справятся со своей
задачей за линейное время. Начинает прослеживаться некая закономерность -
алгоритмы требуют передачи сортированных интервалов для того, чтобы
обеспечить лучшее быстродействие, невозможное при работе с
несортированными интервалами. В дальнейшем мы лишь найдем подтверждение
этой закономерности.
Алгоритмы merge и i npl acejnerge выполняют однопроходное слияние с
сортировкой: они читают два сортированных интервала и строят новый
сортированный интервал, содержащий все элементы обоих исходных
интервалов. Эти алгоритмы работают с линейным временем, что было бы
невозможно без предварительной сортировки исходных интервалов.
Перечень алгоритмов, работающих с сортированными интервалами, завершает
алгоритм i ncl udes. Он проверяет, входят ли все объекты одного интервала
в другой интервал. Поскольку i ncl udes рассчитывает на сортировку обоих
интервалов, он обеспечивает линейное время. Без этого он в общем случае
работает медленнее.
В отличие от перечисленных алгоритмов, unique и uniquecopy способны
работать и с несортированными интервалами. Но давайте взглянем на
описание unique в Стандарте (курсив мой): "...Удаляет из каждой смежной
группы равных элементов все элементы, кроме первого".
Иначе говоря, если вы хотите, чтобы алгоритм unique удалил из интервала
все дубликаты (то есть обеспечил "уникальность" значений в интервале),
сначала необходимо позаботиться о группировке всех дубликатов. Как
нетрудно догадаться, именно эта задача и решается в процессе сортировки.
На практике алгоритм uni que обычно применяется для исключения всех
дубликатов из интервала, поэтому интервал, передаваемый при вызове unique
(или unique copy), должен быть отсортирован. Программисты Unix могут
обратить внимание на поразительное сходство
140 Глава 5 • Алгоритмы
между алгоритмом STL unique и командой Unix uniq - подозреваю, что
совпадение отнюдь не случайное.
Следует помнить, что unique исключает элементы из интервала по тому же
принципу, что и remove, то есть ограничивается "логическим" удалением.
Если вы не совсем уверены в том, что означает этот термин, немедленно
обратитесь к советам 32 и 33. Трудно выразить, сколь важно доскональное
понимание принципов работы remove и remove-подобных алгоритмов. Общих
представлений о происходящем недостаточно. Если вы не знаете, как
работают эти алгоритмы, у вас будут неприятности.
Давайте посмотрим, что же означает само понятие "сортированный интервал".
Поскольку STL позволяет задать функцию сравнения, используемую в процессе
сортировки, разные интервалы могут сортироваться по разным критериям.
Например, интервал int можно отсортировать как стандартным образом (то
есть по возрастанию), так и с использованием greater<int>, то есть по
убыванию. Интервал объектов Widget может сортироваться как по цене, так и
по дате. При таком изобилии способов сортировки очень важно, чтобы данные
сортировки, находящиеся в распоряжении контейнера STL, была логически
согласованы. При передаче сортированного интервала алгоритму, который
также получает функцию сравнения, проследите за тем, чтобы переданная
функция сравнения вела себя так же, как функция, применявшаяся при
сортировке интервала.
Рассмотрим пример неправильного подхода:
vector'dnt> v: // Создать вектор, заполнить
// данными, отсортировать
sort(v.begin().v.end(),greater<int>0): // по убыванию.
// Операции с вектором
// (не изменяющие содержимого).
bool a5Exists = // Поиск числа 5 в векторе.
binary_search(v.begin().v.endO,5): // Предполагается, что вектор
// отсортирован по возрастанию!
По умолчанию bi nary search предполагает, что интервал, в котором
производится поиск, отсортирован оператором < (то есть по возрастанию),
но в приведенном примере вектор сортируется по убыванию. Как нетрудно
догадаться, вызов binary_search (или lower_bound и т. д.) для интервала,
порядок сортировки которого отличен от ожидаемого, приводит к
непредсказуемым последствиям.
Чтобы программа работала правильно, алгоритм binary search должен
использовать ту же функцию сравнения, которая использовалась при вызове
sort:
bool a5Exi sts = bi na ry_sea rch(v.beg i n 0,v.end 0,5,greater<i nt>()):
Все алгоритмы, работающие только с сортированными интервалами (то есть
все алгоритмы, упоминавшиеся в данном совете, кроме unique и uniquecopy),
проверяют совпадение по критерию эквивалентности, как и стандартные
ассоциативные контейнеры (которые также сортируются). С другой стороны,
unique и unique copy по умолчанию проверяют совпадение по критерию
равенства, хотя при вызове этим алгоритмам может передаваться предикат,
определяющий альтернативный смысл "совпадения". За подробной информацией
Предыдущая << 1 .. 65 66 67 68 69 70 < 71 > 72 73 74 75 76 77 .. 114 >> Следующая