, но кроме того обеспечивает корректное отсортированное размещение всех элементов до n-го. Алгоритм
partial_sort
используется для ответов на вопросы, аналогичные вопросам для
nth_element
, но в которых требуется, чтобы все интересующие элементы были корректно отсортированы. Этот алгоритм — все, что вам надо для ответа, например, на вопрос: "Кто из участников
занял первое, второе и третье места?" Ответ можно получить при помощи вызова
, после которого участники, занявшие три первые места, окажутся в корректном порядке в трех первых элементах контейнера, и не более того.
Исключения
Хотя обычно алгоритм
partial_sort
быстрее полной сортировки (так как должен выполнять меньшее количество работы), если вам надо отсортировать почти весь (или весь) диапазон, то в этой ситуации алгоритм
Предикат представляет собой функциональный объект, который возвращает ответ да/нет, обычно в виде значения типа
bool
. Функция является "чистой" в математическом смысле, если ее результат зависит только от ее аргументов (обратите внимание — в данном случае термин "чистая" не имеет никакого отношения к чисто виртуальным функциям).
Не позволяйте предикатам сохранять или обращаться к состоянию так, чтобы это могло влиять на результат работы оператора
operator
; при этом понятие состояния включает как данные-члены, так и глобальные состояния. Для предикатов желательно делать оператор
operator
константной функцией-членом (см. рекомендацию 15).
Обсуждение
Алгоритмы создают неизвестное количество копий предикатов в неизвестные моменты времени и в неизвестном порядке, так что приходится полагаться на то, что все копии эквивалентны.
Именно поэтому вы отвечаете за то, чтобы все копии предикатов были эквивалентны; это означает, что все они должны быть чистыми функциями, результат работы которых полностью и однозначно определяется аргументами, передаваемыми оператору
operator
и не зависит ни от каких иных факторов. При передаче одних и тех же аргументов предикат всегда должен возвращать одно и то же значение.
Предикаты с состояниями могут показаться полезными, но они явно не очень полезны при использовании с алгоритмами стандартной библиотеки С++, и это сделано преднамеренно. В частности, предикаты с состояниями могут быть полезны только при выполнении ряда условий.
• Предикат не копируется. Стандартные алгоритмы не дают такой гарантии; в действительности алгоритмы, напротив, предполагают, что предикаты могут безопасно копироваться.
• Предикаты используются в предопределенном документированном порядке. В общем случае стандартные алгоритмы не дают никакой гарантии относительно порядка применения предикатов к элементам диапазона. При отсутствии гарантий по поводу порядка обработки элементов, операция наподобие "пометить третий элемент" (см. примеры) имеет
мало смысла, поскольку не определено, какой именно элемент будет обработан третьим.
Первое условие можно обойти, написав предикат с использованием счетчика ссылок. Этот метод решает проблему копирования предикатов, поскольку в таком случае предикаты могут безопасно копироваться без изменения их семантики при применении к объектам (см. [Sutter02]). Однако обойти второе условие оказывается невозможно.
Всегда объявляйте оператор предиката
operator
как константную функцию-член, чтобы компилятор мог помочь вам избежать неприятностей, выводя сообщение об ошибке при попытках изменить любые данные-члены, которые могут быть у предиката. Это не позволяет пресечь все злоупотребления, например, доступ к глобальным данным, но, по крайней мере, поможет избежать наиболее распространенных ошибок.
Примеры
Пример.
FlagNth
. Перед вами классический пример из [Sutter02], в котором выполняется попытка удалить третий элемент из контейнера
v
.
class FlagNth {
public:
FlagNth(size_t n) : current_(0), n_(n) { }
// Возвращаем значение true только при третьем вызове
template<typename T>
bool operator(const T&) // Плохо: неконстантная
{ return ++current_ == n_; } // функция
private:
size_t current_, n_;
};
// ... позже ...
v.erase(remove_if(v.begin, v.end, FlagNth(3)));
Увы, нет никакой гарантии, что будет удален именно третий элемент В большинстве реальных реализаций STL приведенный код наряду с третьим удалит и шестой элемент. Почему? Потому что
remove_if
обычно реализуется с использованием
find_if
и
remove_copy_if
, и копия предиката передается каждой из этих функций.
Концептуально этот пример неверен, поскольку алгоритм
remove_if
гарантирует только то, что он удалит все элементы, удовлетворяющие некоторому критерию. Он не документирует порядок, в котором совершается обход или удаление элементов из обрабатываемого диапазона, так что приведенный код использует предположение, которое не документировано и, более того, не выполняется.
Корректный способ удаления третьего элемента — выполнить итерации для его поиска и вызвать функцию
88. В качестве аргументов алгоритмов и компараторов лучше использовать функциональные объекты, а не функции
Резюме
Предпочтительно передавать алгоритмам функциональные объекты, а не функции, а компараторы ассоциативных контейнеров просто должны быть функциональными объектами. Функциональные объекты адаптируемы и, вопреки ожиданиям, обычно дают более быстрый по сравнению с функциями код.