Стандарты программирования на С++. 101 правило и рекомендация

nth_element, partial_sort (и его вариант partial_sort_copy), sort и stable_sort. Используйте наименее дорогой из алгоритмов, которые выполняют необходимую вам работу; применение излишне мощного алгоритма — расточительство.

Время работы алгоритмов partition, stable_partition и nth_element — линейное, что является очень хорошим показателем.

Алгоритмы nth_element, partial_sort, sort и stable_sort требуют итераторы произвольного доступа. Вы не можете использовать их при наличии только двунаправленных итераторов (например, list<T>::iterator). Если вам нужны данные алгоритмы, но у вас нет итераторов произвольного доступа, вы можете воспользоваться идиомой индексного контейнера: создайте контейнер, поддерживающий итераторы произвольного доступа (например, vector), в котором будут храниться итераторы, указывающие на элементы интересующего вас диапазона, и затем примените к нему более мощный алгоритм с использованием разыменовывающей версии вашего предиката (в которой перед обычным сравнением выполняется разыменование итераторов).

Версии stable_… следует применять только тогда, когда вам необходимо сохранить относительный порядок одинаковых элементов. Заметим, что алгоритмы partial_sort и nth_element не являются устойчивыми (т.е. они не оставляют одинаковые элементы в том же относительном порядке, в котором они находились до сортировки), и у них нет стандартизированных устойчивых версий. Если вам все же требуется сохранение относительной упорядоченности элементов, вероятно, вам надо использовать stable_sort.

Само собой разумеется, не следует прибегать ни к каким алгоритмам сортировки, если вы можете обойтись без них. Если вы пользуетесь стандартным ассоциативным контейнером (set/multiset или map/multimap) или адаптером priority_queue, и вам требуется только один порядок сортировки, то не забывайте, что элементы в этих контейнерах всегда находятся в отсортированном виде.

Примеры

Пример 1. partition. Если вам надо разделить весь диапазон на две группы (группа элементов, удовлетворяющих предикату, за которыми следует группа элементов, предикату не удовлетворяющих), то для этого достаточно воспользоваться алгоритмом partition. Это все, что вам надо, чтобы ответить на вопросы наподобие приведенных далее.

• Кто из студентов имеет средний бал не ниже 4.5? Для ответа на этот вопрос можно воспользоваться вызовом partition(students.begin(), students.end(), GradeAtLeast (4.5));, который вернет итератор, указывающий на первого студента, чей средний балл ниже 4.5.

• Какие из товаров имеют вес менее 10 кг? Вызов partition (products.begin(), products.end(), WeightUnder(10)); вернет итератор, указывающий на первый товар, вес которого не ниже 10 кг.

Пример 2. nth_element. Алгоритм nth_element можно использовать для того, чтобы получить один элемент в корректной n-й позиции, в которой он бы находился при полной сортировке всего диапазона, при этом все прочие элементы корректно располагаются до или после этого n-го элемента. Этого достаточно, чтобы ответить на вопросы наподобие следующих.

• Перечислите 20 лучших покупателей. Вызов nth_element(s.begin(), s.begin()+19, s.end(), SalesRating); помещает 20 наилучших покупателей в начало контейнера.

• Какое изделие имеет медианное значение качества в данном наборе? Искомый элемент находится в средней позиции отсортированного диапазона. Для его поиска достаточно вызова nth_element(run.begin(), run.begin() + run.size()/2, run.end(), itemQuality);.

• У какого изделия уровень качества находится на 75-м перцентиле? Искомый элемент находится в позиции, отстоящей на 25% от начала отсортированного диапазона. Для его поиска достаточно вызова nth_element(run.begin(), run.begin()+run.size()*.25, run.end(), ItemQuality);.

Пример 3. partial_sort. Алгоритм partial_sort выполняет те же действия, что и nth_element, но кроме того обеспечивает корректное отсортированное размещение всех элементов до n-го. Алгоритм partial_sort используется для ответов на вопросы, аналогичные вопросам для nth_element, но в которых требуется, чтобы все интересующие элементы были корректно отсортированы. Этот алгоритм — все, что вам надо для ответа, например, на вопрос: 'Кто из участников занял первое, второе и третье места?' Ответ можно получить при помощи вызова partial_sort (contestants.begin(), contestants.begin()+3, contestants.end(), ScoreCompare);, после которого участники, занявшие три первые места, окажутся в корректном порядке в трех первых элементах контейнера, и не более того.

Исключения

Хотя обычно алгоритм partial_sort быстрее полной сортировки (так как должен выполнять меньшее количество работы), если вам надо отсортировать почти весь (или весь) диапазон, то в этой ситуации алгоритм sort может оказаться быстрее.

Ссылки

[Austern99] §13.1 • [Bentley00] §11 • [Josuttis99] §9.2.2 • [Meyers01] §31 • [Musser01] §5.4, §22.26 • [Stroustrup00] §17.1.4.1, §18.7

87. Делайте предикаты чистыми функциями

Резюме

Предикат представляет собой функциональный объект, который возвращает ответ да/нет, обычно в виде значения типа bool. Функция является 'чистой' в математическом смысле, если ее результат зависит только от ее аргументов (обратите внимание — в данном случае термин 'чистая' не имеет никакого отношения к чисто виртуальным функциям).

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

Обсуждение

Алгоритмы создают неизвестное количество копий предикатов в неизвестные моменты времени и в неизвестном порядке, так что приходится полагаться на то, что все копии эквивалентны.

Именно поэтому вы отвечаете за то, чтобы все копии предикатов были эквивалентны; это означает, что все они должны быть чистыми функциями, результат работы которых полностью и однозначно определяется аргументами, передаваемыми оператору operator() и не зависит ни от каких иных факторов. При передаче одних и тех же аргументов предикат всегда должен возвращать одно и то же значение.

Предикаты с состояниями могут показаться полезными, но они явно не очень полезны при использовании с алгоритмами стандартной библиотеки С++, и это сделано преднамеренно. В частности, предикаты с состояниями могут быть полезны только при выполнении ряда условий.

• Предикат не копируется. Стандартные алгоритмы не дают такой гарантии;