Стенли Липпман - Язык программирования C++. Пятое издание

Алгоритмы partial_sort()и nth_element()выполняют частичную сортировку последовательности. Их используют в случае, когда в результате сортировки всей последовательности могут возникнуть проблемы. Поскольку эти операции являются менее трудоемкими, они выполняются быстрее, чем сортировка всего исходного диапазона.

sort(beg, end)

stable_sort(beg, end)

sort(beg, end, comp)

stable_sort(beg, end, comp)

Сортирует весь диапазон.

is_sorted(beg, end)

is_sorted(beg, end, comp)

is_sorted_until(beg, end)

is_sorted_until(beg, end, comp)

Алгоритм is sorted()возвращает логическое значение, указывающее, сортируется ли вся исходная последовательность. Алгоритм is_sorted_until()находит самую длинную изначально отсортированную часть в исходной последовательности и возвращает итератор на позицию сразу после ее конца.

partial_sort(beg, mid, end)

partial_sort(beg, mid, end, comp)

Сортирует набор элементов, количество которых равно mid-beg. То есть если mid-begравно 42, эта функция помещает элементы с самыми низкими значениями, в отсортированном порядке, в первые 42 позиции последовательности. После завершения работы алгоритма partial_sort()окажутся отсортированы элементы в диапазоне от begи далее, но не включая mid. Ни один из элементов в отсортированном диапазоне не больше, чем любой из элементов в диапазоне после mid. Порядок неотсортированных элементов не определен.

partial_sort_copy(beg, end, destBeg, destEnd)

partial_sort_copy(beg, end, destBeg, destEnd, comp)

Сортирует элементы исходного диапазона и помещает их (в отсортированном порядке) в последовательность, указанную итераторами destBegи destEnd. Если получающий диапазон имеет тот же размер или превосходит исходный, в него сохраняется весь исходный диапазон в отсортированном виде, начиная с позиции destBeg. Если размер получающего диапазона меньше, в него будет скопировано столько отсортированных элементов, сколько поместится.

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

nth_element(beg, nth, end)

nth_element(beg, nth, end, comp)

Аргумент nthдолжен быть итератором, указывающим на элемент в исходной последовательности. Обозначенный этим итератором элемент после выполнения алгоритма nth_elementимеет значение, которое находилось бы там после сортировки всей последовательности. Кроме того, элементы контейнера вокруг позиции nthтакже отсортированы: перед ней располагается значение меньше или равное значению в позиции nth, а после нее значение, большее или равное.

Некоторые алгоритмы переупорядочивают элементы исходной последовательности. Первые два, remove()и unique(), переупорядочивают последовательность так, чтобы элементы в первой части удовлетворяли некоему критерию. Они возвращают итератор, отмечающий конец этой подпоследовательности. Другие, например reverse(), rotate()и random_shuffle(), реорганизуют всю последовательность.

Базовые версии этих алгоритмов работают "на месте", т.е. они реорганизуют элементы непосредственно исходной последовательности. Три алгоритма изменения порядка предоставляют копирующие версии. Они записывают переупорядоченные значения в получающую последовательность, а не непосредственно в исходную. Для получающей последовательности этим алгоритмам требуются итераторы вывода .

Эти алгоритмы переупорядочивают исходную последовательность. Им необходимы по крайней мере прямые итераторы .

remove(beg, end, val)

remove_if(beg, end, unaryPred)

remove_copy(beg, end, dest, val)

remove_copy_if(beg, end, dest, unaryPred)

"Удаляет" элементы из последовательности, записывая поверх них те элементы, которые должны быть сохранены. Удаляются те элементы, которые равны значению valили те, для которых предикат unaryPredвернул значение true. Возвращает итератор на следующий элемент после последнего удаленного.

unique(beg, end)

unique(beg, end, binaryPred)

unique_copy(beg, end, dest)

unique_copy_if(beg, end, dest, binaryPred)