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

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

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

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

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

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

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

qsort, но после прочтения совета 46 они раскаиваются и возвращаются к
мыслям о sort).
Действительно, sort - превосходный алгоритм, однако полноценная
сортировка требуется далеко не всегда. Например, если у вас имеется
вектор объектов Widget и вы хотите отобрать 20 "лучших" объектов с
максимальным рангом, можно ограничиться сортировкой, позволяющей выявить
20 нужных объектов и оставить остальные объекты несортированными. Задача
называется частичной сортировкой, и для ее решения существует специальный
алгоритм parti al_sort:
bool qualityCompare(const Widgets lhs. const Widgets rhs)
{
// Вернуть признак сравнения атрибутов quality // объектов lhs и rhs
}
partia1_sort(widgets.begin(). // Разместить 20 элементов
widgets.begin0+20. // с максимальным рангом widgets.endO. // в начале
вектора widgets qua1i tyCompa re):
// Использование widgets
После вызова parti alsort первые 20 элементов wi dgets находятся в начале
контейнера и располагаются по порядку, то есть wi dgets [0] содержит Wi
dget с наибольшим рангом, затем следует widgets[l] и т. д.
Если вы хотите выделить 20 объектов Widget и передать их 20 клиентам, но
при этом вас не интересует, какой объект будет передан тому или иному
клиенту, даже алгоритм partial_sort превышает реальные потребности. В
описанной ситуации требуется выделить 20 "лучших" объектов Widget в
произвольном порядке. В STL имеется алгоритм, который решает именно эту
задачу, однако его имя выглядит несколько неожиданно - он называется nth
el ement.
Алгоритм nth_el ement сортирует интервал таким образом, что в заданной
вами позиции п оказывается именно тот элемент, который оказался бы в ней
при полной сортировке контейнера. Кроме того, при выходе из nth_el ement
ни один из элементов в позициях до п не находится в порядке сортировки
после элемента, находящегося в позиции п, а ни один из элементов в
позициях после п не предшествует элементу, находящемуся в позиции п. Если
такая формулировка кажется слишком сложной, это объясняется лишь тем, что
мне приходилось тщательно подбирать слова. Вскоре я объясню причины, но
сначала мы рассмотрим пример использования nth_element для перемещения 20
"лучших" объектов Widget в начало контейнера widgets:
nth_e1ement(widgets.begin(). // Переместить 20 "лучших" элементов
widgets.begin()+20. // в начало widgets
widgets.endO, // в произвольном порядке
qualityCompare):
128 Глава 5 • Алгоритмы
Как видите, вызов nth_element практически не отличается от вызова parti
al_ sort. Единственное различие заключается в том, что partial_sort
сортирует элементы в позициях 1-20, a nth el ement этого не делает.
Впрочем, оба алгоритма перемещают 20 объектов Wi dget с максимальными
значениями ранга в начало вектора.
Возникает важный вопрос - что делают эти алгоритмы для элементов с
одинаковыми значениями атрибута? Предположим, вектор содержит 12
элементов с рангом 1 и 15 элементов с рангом 2. В этом случае выборка 20
"лучших" объектов Widget будет состоять из 12 объектов с рангом 1 и 8 из
15 объектов с рангом 2. Но как алгоритмы parti al sort и nth el ement
определяют, какие из 15 объектов следует отобрать в "верхнюю двадцатку"?
И как алгоритм sort выбирает относительный порядок размещения элементов
при совпадении рангов?
Алгоритмы partial sort и nthel ement упорядочивают эквивалентные элементы
по своему усмотрению, и сделать с этим ничего нельзя (понятие
эквивалентности рассматривается в совете 19). Когда в приведенном примере
возникает задача заполнения объектами Widget с рангом 2 восьми последних
позиций в "верхней двадцатке", алгоритм выберет такие объекты, какие
сочтет нужным. Впрочем, такое поведение вполне разумно. Если вы
запрашиваете 20 "лучших" объектов Widget, а некоторых объекты равны, то в
результате возвращенные объекты будут по крайней мере "не хуже" тех,
которые возвращены не были.
Полноценная сортировка обладает несколько большими возможностями.
Некоторые алгоритмы сортировки стабильны. При стабильной сортировке два
эквивалентных элемента в интервале сохраняют свои относительные позиции
после сортировки. Таким образом, если Widget А предшествует Widget В в
несортированном векторе widgets и при этом ранги двух объектов совпадают,
стабильный алгоритм сортировки гарантирует, что после сортировки Widget А
по-прежнему будет предшествовать Widget В. Нестабильный алгоритм такой
гарантии не дает.
Алгоритм parti al sort, как и алгоритм nth_el ement, стабильным не
является. Алгоритм sort также не обладает свойством стабильности, но
существует специальный алгоритм stable_sort, который, как следует из его
названия, является стабильным. При необходимости выполнить стабильную
сортировку, вероятно, следует воспользоваться stab! e sort. В STL не
входят стабильные версии parti al_sort и nth_el ement.
Следует заметить, что алгоритм nth_el ement чрезвычайно универсален.
Помимо выделения п верхних элементов в интервале, он также может
использоваться для вычисления медианы по интервалу и поиска значения
Предыдущая << 1 .. 59 60 61 62 63 64 < 65 > 66 67 68 69 70 71 .. 114 >> Следующая