После вызова

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

Если вы хотите выделить 20 объектов

и передать их 20 клиентам, но при этом вас не интересует, какой объект будет передан тому или иному клиенту, даже алгоритм превышает реальные потребности. В описанной ситуации требуется выделить 20 «лучших» объектов в произвольном порядке. В STL имеется алгоритм, который решает именно эту задачу, однако его имя выглядит несколько неожиданно — он называется .

Алгоритм

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

Как видите, вызов

практически не отличается от вызова . Единственное различие заключается в том, что сортирует элементы в позициях 1-20, a этого не делает. Впрочем, оба алгоритма перемещают 20 объектов с максимальными значениями ранга в начало вектора.

Возникает важный вопрос — что делают эти алгоритмы для элементов с одинаковыми значениями атрибута? Предположим, вектор содержит 12 элементов с рангом 1 и 15 элементов с рангом 2. В этом случае выборка 20 «лучших» объектов

будет состоять из 12 объектов с рангом 1 и 8 из 15 объектов с рангом 2. Но как алгоритмы и определяют, какие из 15 объектов следует отобрать в «верхнюю двадцатку»? И как алгоритм выбирает относительный порядок размещения элементов при совпадении рангов?

Алгоритмы

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

Полноценная сортировка обладает несколько большими возможностями. Некоторые алгоритмы сортировки стабильны. При стабильной сортировке два эквивалентных элемента в интервале сохраняют свои относительные позиции после сортировки. Таким образом, если

 A предшествует  B в несортированном векторе и при этом ранги двух объектов совпадают, стабильный алгоритм сортировки гарантирует, что после сортировки  A по-прежнему будет предшествовать B. Нестабильный алгоритм такой гарантии не дает.

Алгоритм

, как и алгоритм , стабильным не является. Алгоритм также не обладает свойством стабильности, но существует специальный алгоритм , который, как следует из его названия, является стабильным. При необходимости выполнить стабильную сортировку, вероятно, следует воспользоваться . В STL не входят стабильные версии и .

Следует заметить, что алгоритм nth_element чрезвычайно универсален. Помимо выделения

верхних элементов в интервале, он также может использоваться для вычисления медианы по интервалу и поиска значения конкретного процентиля [3] :