У всех операций [alg.sorting] есть две версии: одна использует объект функции типа, Compare а другая - объект operator<.
Compare это а function object type. Возвращаемое значение операции вызова функции, примененной к объекту типа Comparewhen contextually converted to bool, дает результат, true если первый аргумент вызова меньше второго, и в false противном случае. Compare comp везде используется для алгоритмов, предполагающих отношение порядка. Предполагается, что comp через разыменованный итератор не будет применяться какая-либо непостоянная функция.
Для всех используемых алгоритмов Compareсуществует версия, которая использует operator< вместо них. То есть по comp(*i, *j) != false умолчанию *i < *j != false. Для алгоритмов, отличных от описанных в [alg.binary.search], comp должен вызывать строгий слабый порядок значений.
Этот термин strict относится к требованию иррефлексивного отношения (!comp(x, x) для всех x), а термин - weak к требованиям, которые не такие строгие, как требования для полного упорядочения, но более сильные, чем требования для частичного упорядочения. Если мы определяем equiv(a, b) как !comp(a, b) && !comp(b, a), то требования таковы, comp и equiv оба должны быть транзитивными отношениями:
comp(a, b) && comp(b, c) подразумевает comp(a, c)
equiv(a, b) && equiv(b, c) подразумевает equiv(a, c)
[ Note: В этих условиях можно показать, что
equiv является отношением эквивалентности
comp индуцирует корректно определенное отношение на классах эквивалентности, определяемых equiv
Индуцированное отношение - это строгий тотальный порядок.
— end note ]
Последовательность является ,sorted with respect to a comparator comp если для каждого итератора ,i указывающей последовательность , и каждый неотрицательное целое число n такое , что i + n является действительным итератора , указывающий на элемент последовательности, comp(*(i + n), *i) == false.
Последовательность [start, finish) - partitioned with respect to это выражение, f(e) если существует такое целое число n , что для всех 0 <= i < (finish - start), f(*(start + i)) есть true тогда и только тогда, когда i < n.
В описаниях функций, которые имеют дело с отношениями упорядочения, мы часто используем понятие эквивалентности для описания таких понятий, как стабильность. Эквивалентность, о которой мы говорим, не обязательно является operator==отношением эквивалентности, индуцированным строгим слабым порядком. То есть два элемента a и b считаются эквивалентными тогда и только тогда, когда !(a < b) && !(b < a).
template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
template<class ExecutionPolicy, class RandomAccessIterator>
void sort(ExecutionPolicy&& exec,
RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
void sort(ExecutionPolicy&& exec,
RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
Requires: RandomAccessIterator должны удовлетворять требованиям ValueSwappable. Тип *first должен удовлетворять требованиям MoveConstructible и MoveAssignable.
template<class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
template<class ExecutionPolicy, class RandomAccessIterator>
void stable_sort(ExecutionPolicy&& exec,
RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
void stable_sort(ExecutionPolicy&& exec,
RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
Requires: RandomAccessIterator должны удовлетворять требованиям ValueSwappable. Тип *first должен удовлетворять требованиям MoveConstructible и MoveAssignable.
Complexity: Максимум Nlog2(N) сравнений, где N=last - first, но только NlogN сравнения, если достаточно дополнительной памяти.
template<class RandomAccessIterator>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last);
template<class ExecutionPolicy, class RandomAccessIterator>
void partial_sort(ExecutionPolicy&& exec,
RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last,
Compare comp);
template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
void partial_sort(ExecutionPolicy&& exec,
RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last,
Compare comp);
Requires: RandomAccessIterator должны удовлетворять требованиям ValueSwappable. Тип *first должен удовлетворять требованиям MoveConstructible и MoveAssignable.
template<class InputIterator, class RandomAccessIterator>
RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last);
template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterator>
RandomAccessIterator
partial_sort_copy(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last);
template<class InputIterator, class RandomAccessIterator,
class Compare>
RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last,
Compare comp);
template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterator,
class Compare>
RandomAccessIterator
partial_sort_copy(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last,
Compare comp);
Requires: RandomAccessIterator должны удовлетворять требованиям ValueSwappable. Тип *result_first должен удовлетворять требованиям MoveConstructible и MoveAssignable.
Effects: Помещает первые min(last - first, result_last - result_first) отсортированные элементы в диапазон [result_first, result_first + min(last - first, result_last - result_first)).
template<class ForwardIterator>
bool is_sorted(ForwardIterator first, ForwardIterator last);
template<class ExecutionPolicy, class ForwardIterator>
bool is_sorted(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
bool is_sorted(ForwardIterator first, ForwardIterator last,
Compare comp);
template<class ExecutionPolicy, class ForwardIterator, class Compare>
bool is_sorted(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
Compare comp);
template<class ForwardIterator>
ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last);
template<class ExecutionPolicy, class ForwardIterator>
ForwardIterator is_sorted_until(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last,
Compare comp);
template<class ExecutionPolicy, class ForwardIterator, class Compare>
ForwardIterator is_sorted_until(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
Compare comp);
Returns: Если (last - first) < 2, вернется last. В противном случае, возвращает последний итератор i в [first, last] течение которого диапазон [first, i) сортируется.
template<class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last);
template<class ExecutionPolicy, class RandomAccessIterator>
void nth_element(ExecutionPolicy&& exec,
RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last, Compare comp);
template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
void nth_element(ExecutionPolicy&& exec,
RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last, Compare comp);
Requires: RandomAccessIterator должны удовлетворять требованиям ValueSwappable. Тип *first должен удовлетворять требованиям MoveConstructible и MoveAssignable.
Effects: После nth_element элемента в позиции, на которую указывает, nth находится элемент, который был бы в этой позиции, если бы весь диапазон был отсортирован, если только nth == last. Также для каждого итератора i в диапазоне [first, nth) и каждого итератора j в диапазоне [nth, last) он содержит: !(*j < *i) или comp(*j, *i) == false.
Все алгоритмы в этом разделе являются версиями двоичного поиска и предполагают, что просматриваемая последовательность разделена по отношению к выражению, сформированному путем привязки ключа поиска к аргументу неявной или явной функции сравнения. Они работают с итераторами с неслучайным доступом, сводя к минимуму количество сравнений, которое будет логарифмическим для всех типов итераторов. Они особенно подходят для итераторов с произвольным доступом, поскольку эти алгоритмы выполняют логарифмическое количество шагов через структуру данных. Для итераторов с неслучайным доступом они выполняют линейное количество шагов.
template<class ForwardIterator, class T>
ForwardIterator
lower_bound(ForwardIterator first, ForwardIterator last,
const T& value);
template<class ForwardIterator, class T, class Compare>
ForwardIterator
lower_bound(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);
Requires: Элементы e из [first, last) должны быть разделены по отношению к экспрессии e < value или comp(e, value).
Returns: Самыйi дальний итератор в диапазоне, [first, last] такой, что для каждого итератора j в диапазоне [first, i) выполняются следующие соответствующие условия: *j < value или comp(*j, value) != false.
template<class ForwardIterator, class T>
ForwardIterator
upper_bound(ForwardIterator first, ForwardIterator last,
const T& value);
template<class ForwardIterator, class T, class Compare>
ForwardIterator
upper_bound(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);
Requires: Элементы e из [first, last) должны быть разделены по отношению к экспрессии !(value < e) или !comp(value, e).
Returns: Самыйi дальний итератор в диапазоне, [first, last] такой, что для каждого итератора j в диапазоне [first, i) выполняются следующие соответствующие условия: !(value < *j) или comp(value, *j) == false.
template<class ForwardIterator, class T>
pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first,
ForwardIterator last, const T& value);
template<class ForwardIterator, class T, class Compare>
pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first,
ForwardIterator last, const T& value,
Compare comp);
Requires: Элементы e из [first, last) должны быть разделены относительно выражений e < value и !(value < e) или comp(e, value) и !comp(value, e). Кроме того , для всех элементов e из [first, last), e < value влечет !(value < e) или comp(e, value) влечет !comp(value, e).
Returns:
make_pair(lower_bound(first, last, value),
upper_bound(first, last, value))или
make_pair(lower_bound(first, last, value, comp),
upper_bound(first, last, value, comp))template<class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last,
const T& value);
template<class ForwardIterator, class T, class Compare>
bool binary_search(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);
Requires: Элементы e из [first, last) разделены относительно выражений e < value и !(value < e) или comp(e, value) и !comp(value, e). Кроме того , для всех элементов e из [first, last), e < value предполагает !(value < e) или comp(e, value) подразумевает !comp(value, e).
Returns: true еслиi в диапазоне есть итератор [first, last) , удовлетворяющий соответствующим условиям: !(*i < value) && !(value < *i) или comp(*i, value) == false && comp(value, *i) == false.
template <class InputIterator, class Predicate>
bool is_partitioned(InputIterator first, InputIterator last, Predicate pred);
template <class ExecutionPolicy, class ForwardIterator, class Predicate>
bool is_partitioned(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last, Predicate pred);
Requires: Для перегрузки с нет ExecutionPolicy, InputIterator«s тип значения должен быть конвертирован в Predicate» S типа аргумента. Для перегрузки с ExecutionPolicy, ForwardIterator«с типом значения должны быть конвертированы в Predicate» S типа аргумента.
Returns: true if [first, last) пуст или если [first, last) разделен на pred, то есть если все элементы, удовлетворяющие условиям, pred появляются перед теми, которые этого не делают.
template<class ForwardIterator, class Predicate>
ForwardIterator
partition(ForwardIterator first, ForwardIterator last, Predicate pred);
template<class ExecutionPolicy, class ForwardIterator, class Predicate>
ForwardIterator
partition(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last, Predicate pred);
Requires: ForwardIterator должны удовлетворять требованиям ValueSwappable.
Effects: Помещает все элементы в диапазоне, [first, last) которые удовлетворяют, pred перед всеми элементами, которые ему не удовлетворяют.
Returns: Итератора i таким образом, что для каждого итератора j в диапазоне [first, i) pred(*j) != false, и для каждого итератора k в диапазоне [i, last), pred(*k) == false.
Complexity: Пусть N=last - first:
Для перегрузки без ExecutionPolicy, как раз N применения предиката. В большинстве N/2 случаев меняет местами, если ForwardIterator соответствует BidirectionalIterator требованиям, и не больше, в N противном случае.
Для перегрузки с ExecutionPolicy, O(NlogN) свопами и O(N) приложениями предиката.
template<class BidirectionalIterator, class Predicate>
BidirectionalIterator
stable_partition(BidirectionalIterator first, BidirectionalIterator last,
Predicate pred);
template<class ExecutionPolicy, class BidirectionalIterator, class Predicate>
BidirectionalIterator
stable_partition(ExecutionPolicy&& exec,
BidirectionalIterator first, BidirectionalIterator last,
Predicate pred);
Requires: BidirectionalIterator должны удовлетворять требованиям ValueSwappable. Тип *first должен удовлетворять требованиям MoveConstructible и MoveAssignable.
Effects: Помещает все элементы в диапазоне, [first, last) которые удовлетворяют, pred перед всеми элементами, которые ему не удовлетворяют.
Returns: Итератора i таким образом, что для каждого итератора j в диапазоне [first, i), pred(*j) != falseи для каждого итератора k в диапазоне [i, last), pred(*k) == false. Относительный порядок элементов в обеих группах сохраняется.
Complexity: Пусть N = last - first:
Для перегрузки без подкачки, ExecutionPolicyсамое большее NlogN подкачки, но только O(N) подкачки, если достаточно дополнительной памяти. Собственно N применения сказуемого.
Для перегрузки с ExecutionPolicy, O(NlogN) свопами и O(N) приложениями предиката.
template <class InputIterator, class OutputIterator1,
class OutputIterator2, class Predicate>
pair<OutputIterator1, OutputIterator2>
partition_copy(InputIterator first, InputIterator last,
OutputIterator1 out_true, OutputIterator2 out_false,
Predicate pred);
template <class ExecutionPolicy, class ForwardIterator, class ForwardIterator1,
class ForwardIterator2, class Predicate>
pair<ForwardIterator1, ForwardIterator2>
partition_copy(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
ForwardIterator1 out_true, ForwardIterator2 out_false,
Predicate pred);
Requires:
Для перегрузки без каких - либо ExecutionPolicy, InputIterator«с типом значение должно быть CopyAssignable (таблица 26), и должны быть доступны для записи ([iterator.requirements.general]) к out_true и out_false OutputIteratorс, и должны быть конвертированы в Predicate» с аргументом типа.
Для перегрузки с ExecutionPolicy, ForwardIterator«с типом значения должны быть CopyAssignable, и должны быть доступны для записи на out_true и out_false ForwardIteratorс, и должны быть конвертированы в Predicate» с аргументом типа. [ Note: Если ForwardIteratorтип значения не является типом значения, это может повлиять на производительностьCopyConstructible. ] — end note
Для обеих перегрузок входной диапазон не должен перекрываться ни с одним из выходных диапазонов.
Effects: Для каждого итератора i в [first, last)копии *i в начале диапазона выходной мощности с , out_true если pred(*i) это true, или в диапазоне , начиная с выхода в out_false противном случае.
Returns: Такая пара p , которая p.first является концом выходного диапазона, начинающегося с, out_true и p.second является концом выходного диапазона, начинающегося с out_false.
template<class ForwardIterator, class Predicate>
ForwardIterator partition_point(ForwardIterator first,
ForwardIterator last,
Predicate pred);
Requires: ForwardIteratorТип значения должен быть преобразован в Predicateтип аргумента. [first, last) должны быть разделены на pred, т. е. все элементы, которые удовлетворяют, pred должны появляться перед теми, которые не удовлетворяют .
Returns: Итератор mid такой, что all_of(first, mid, pred) и none_of(mid, last, pred) есть оба true.
template<class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator
merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator>
ForwardIterator
merge(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result);
template<class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator
merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator, class Compare>
ForwardIterator
merge(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result, Compare comp);
Requires: Диапазоны [first1, last1) и [first2, last2) должны быть отсортированы относительно operator< или comp. Результирующий диапазон не должен перекрываться ни с одним из исходных диапазонов.
Effects: Копирует все элементы двух диапазонов [first1, last1) и [first2, last2) в диапазон [result, result_last), где result_last есть result + (last1 - first1) + (last2 - first2), так что результирующий диапазон удовлетворяет is_sorted(result, result_last) или is_sorted(result, result_last, comp), соответственно.
template<class BidirectionalIterator>
void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last);
template<class ExecutionPolicy, class BidirectionalIterator>
void inplace_merge(ExecutionPolicy&& exec,
BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last, Compare comp);
template<class ExecutionPolicy, class BidirectionalIterator, class Compare>
void inplace_merge(ExecutionPolicy&& exec,
BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last, Compare comp);
Requires: Диапазоны [first, middle) и [middle, last) должны быть отсортированы относительно operator< или comp. BidirectionalIterator должны удовлетворять требованиям ValueSwappable. Тип *first должен удовлетворять требованиям MoveConstructible и MoveAssignable.
Effects: Объединяет два отсортированных последовательных диапазона [first, middle) и [middle, last), помещая результат слияния в диапазон [first, last). Результирующий диапазон будет в порядке неубывания; то есть, для каждого итератора i в [first, last) другом чем first, состояние *i < *(i - 1) или, соответственно, comp(*i, *(i - 1)) будет false.
Complexity: Пусть N=last - first:
Для перегрузок с отсутствием ExecutionPolicy, если доступно достаточно дополнительной памяти, именно N−1 сравнения.
Для перегрузок с нет, ExecutionPolicy если дополнительная память недоступна, O(NlogN) сравнения.
Для перегрузок ExecutionPolicy, O(NlogN) сравнений.
В этом разделе определены все основные операции над сортированными структурами. Они также работают с multisets несколькими копиями эквивалентных элементов. Семантика заданных операций обобщается на multisets стандартным способом, определяя set_union() максимальное количество вхождений каждого элемента, set_intersection() минимальное и т. Д.
template<class InputIterator1, class InputIterator2>
bool includes(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
bool includes(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
template<class InputIterator1, class InputIterator2, class Compare>
bool includes(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
Compare comp);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class Compare>
bool includes(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
Compare comp);
Returns: true если [first2, last2) пусто или если каждый элемент в диапазоне [first2, last2) содержится в диапазоне [first1, last1). Вfalse противном случае возвращается .
template<class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator
set_union(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator>
ForwardIterator
set_union(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result);
template<class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator
set_union(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator, class Compare>
ForwardIterator
set_union(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result, Compare comp);
Effects: Создает отсортированное объединение элементов из двух диапазонов; то есть набор элементов, которые присутствуют в одном или обоих диапазонах.
Remarks: Если [first1, last1) содержит m элементы, которые эквивалентны друг другу , и [first2, last2) содержит n элементы, которые эквивалентны их, то все m элементы из первого диапазона должны быть скопированы в выходном диапазоне, в порядке, а затем max(n−m,0) элементы из второго диапазона должны быть скопированы в выходном диапазоне , чтобы.
template<class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator
set_intersection(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator>
ForwardIterator
set_intersection(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result);
template<class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator
set_intersection(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator, class Compare>
ForwardIterator
set_intersection(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result, Compare comp);
Effects: Создает отсортированное пересечение элементов из двух диапазонов; то есть набор элементов, которые присутствуют в обоих диапазонах.
template<class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator
set_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator>
ForwardIterator
set_difference(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result);
template<class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator
set_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator, class Compare>
ForwardIterator
set_difference(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result, Compare comp);
Effects: Копирует элементы диапазона [first1, last1) , отсутствующие в диапазоне, [first2, last2) в диапазон, начинающийся с result. Элементы в построенном диапазоне сортируются.
template<class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator
set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator>
ForwardIterator
set_symmetric_difference(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result);
template<class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator
set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator, class Compare>
ForwardIterator
set_symmetric_difference(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result, Compare comp);
Effects: Копирует элементы диапазона [first1, last1) , отсутствующие в диапазоне [first2, last2), и элементы диапазона [first2, last2) , отсутствующие в диапазоне, [first1, last1) в диапазон, начинающийся с result. Элементы в построенном диапазоне сортируются.
Remarks: Если [first1, last1) содержит m элементы, которые эквивалентны друг другу и [first2, last2) содержит n элементы, которые приравненных к ним, то |m−n| из этих элементов должны быть скопированы в выходной диапазон: последний m−n из этих элементов от [first1, last1) если m>n, и последний n−m из этих элементов , [first2, last2) если m<n.
A heap - это особая организация элементов в диапазоне между двумя итераторами произвольного доступа, [a, b) такая что:
С N = b - a, для всех i, 0<i<N, comp(a[⌊i−12⌋], a[i]) есть false.
*a может быть удалено pop_heap(), или новый элемент добавляет push_heap()в O(logN) время.
make_heap() преобразует диапазон в кучу и sort_heap() превращает кучу в отсортированную последовательность.
template<class RandomAccessIterator>
void push_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void push_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
Requires: Диапазон [first, last - 1) должен быть допустимой кучей. Тип *first должен удовлетворять MoveConstructible requirements и MoveAssignable requirements.
template<class RandomAccessIterator>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
Requires: Диапазон [first, last) должен быть действительной непустой кучей. RandomAccessIterator должны удовлетворять требованиям ValueSwappable. Тип *first должен удовлетворять требованиям MoveConstructible и MoveAssignable.
Effects: Меняет местами значение в местоположении first со значением в местоположении last - 1 и превращается [first, last - 1) в кучу.
template<class RandomAccessIterator>
void make_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void make_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
Requires: Тип *first должен удовлетворять MoveConstructible requirements и MoveAssignable requirements.
template<class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
Requires: Диапазон [first, last) должен быть допустимой кучей. RandomAccessIterator должны удовлетворять требованиям ValueSwappable. Тип *first должен удовлетворять требованиям MoveConstructible и MoveAssignable.
template<class RandomAccessIterator>
bool is_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class ExecutionPolicy, class RandomAccessIterator>
bool is_heap(ExecutionPolicy&& exec,
RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
bool is_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
bool is_heap(ExecutionPolicy&& exec,
RandomAccessIterator first, RandomAccessIterator last, Compare comp);
template<class RandomAccessIterator>
RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last);
template<class ExecutionPolicy, class RandomAccessIterator>
RandomAccessIterator is_heap_until(ExecutionPolicy&& exec,
RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
RandomAccessIterator is_heap_until(ExecutionPolicy&& exec,
RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
Returns: Если (last - first) < 2, вернется last. В противном случае, возвращает последний итератор i в [first, last] течение которого диапазон [first, i) является пирамидой.
template<class T> constexpr const T& min(const T& a, const T& b);
template<class T, class Compare>
constexpr const T& min(const T& a, const T& b, Compare comp);
Requires: Для первой формы тип T должен быть LessThanComparable.
template<class T>
constexpr T min(initializer_list<T> t);
template<class T, class Compare>
constexpr T min(initializer_list<T> t, Compare comp);
Requires: T должно быть CopyConstructible и t.size() > 0. Для первой формы тип T должен быть LessThanComparable.
Remarks: Возвращает копию самого левого аргумента, если несколько аргументов эквивалентны наименьшему.
template<class T> constexpr const T& max(const T& a, const T& b);
template<class T, class Compare>
constexpr const T& max(const T& a, const T& b, Compare comp);
Requires: Для первой формы тип T должен быть LessThanComparable.
template<class T>
constexpr T max(initializer_list<T> t);
template<class T, class Compare>
constexpr T max(initializer_list<T> t, Compare comp);
Requires: T должно быть CopyConstructible и t.size() > 0. Для первой формы тип T должен быть LessThanComparable.
Remarks: Возвращает копию самого левого аргумента, если несколько аргументов эквивалентны самому большому.
template<class T> constexpr pair<const T&, const T&> minmax(const T& a, const T& b);
template<class T, class Compare>
constexpr pair<const T&, const T&> minmax(const T& a, const T& b, Compare comp);
Requires: Для первой формы тип T должен быть LessThanComparable.
Returns: pair<const T&, const T&>(b, a) если b меньше a, и в pair<const T&, const T&>(a, b) противном случае.
template<class T>
constexpr pair<T, T> minmax(initializer_list<T> t);
template<class T, class Compare>
constexpr pair<T, T> minmax(initializer_list<T> t, Compare comp);
Requires: T должно быть CopyConstructible и t.size() > 0. Для первой формы тип T должен быть LessThanComparable.
Returns: pair<T, T>(x, y), где x имеет наименьшее и y наибольшее значение в списке инициализаторов.
Remarks: x является копией самого левого аргумента, когда несколько аргументов эквивалентны наименьшему. y является копией самого правого аргумента, когда несколько аргументов эквивалентны самому большому.
template<class ForwardIterator>
constexpr ForwardIterator min_element(ForwardIterator first, ForwardIterator last);
template<class ExecutionPolicy, class ForwardIterator>
ForwardIterator min_element(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
constexpr ForwardIterator min_element(ForwardIterator first, ForwardIterator last,
Compare comp);
template<class ExecutionPolicy, class ForwardIterator, class Compare>
ForwardIterator min_element(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
Compare comp);
Returns: Первый итератор i в диапазоне, [first, last) такой, что для каждого итератора j в диапазоне [first, last) выполняются следующие соответствующие условия: !(*j < *i) или comp(*j, *i) == false. Возвращает, last если first == last.
template<class ForwardIterator>
constexpr ForwardIterator max_element(ForwardIterator first, ForwardIterator last);
template<class ExecutionPolicy, class ForwardIterator>
ForwardIterator max_element(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
constexpr ForwardIterator max_element(ForwardIterator first, ForwardIterator last,
Compare comp);
template<class ExecutionPolicy, class ForwardIterator, class Compare>
ForwardIterator max_element(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
Compare comp);
Returns: Первый итератор i в диапазоне, [first, last) такой, что для каждого итератора j в диапазоне [first, last) выполняются следующие соответствующие условия: !(*i < *j) или comp(*i, *j) == false. Возвращает, last если first == last.
template<class ForwardIterator>
constexpr pair<ForwardIterator, ForwardIterator>
minmax_element(ForwardIterator first, ForwardIterator last);
template<class ExecutionPolicy, class ForwardIterator>
pair<ForwardIterator, ForwardIterator>
minmax_element(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
constexpr pair<ForwardIterator, ForwardIterator>
minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);
template<class ExecutionPolicy, class ForwardIterator, class Compare>
pair<ForwardIterator, ForwardIterator>
minmax_element(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last, Compare comp);
Returns: make_pair(first, first) если [first, last) пусто, в противном случае make_pair(m, M)где m - первый итератор в [first, last) таком, что ни один итератор в диапазоне не ссылается на меньший элемент, а где M - последний итератор266 в [first, last) таком, что ни один итератор в диапазоне не ссылается на больший элемент.
Complexity: В большинстве max(⌊32(N−1)⌋,0) случаев применения соответствующего предиката, где N есть last - first.
Это поведение намеренно отличается от max_element().
template<class T>
constexpr const T& clamp(const T& v, const T& lo, const T& hi);
template<class T, class Compare>
constexpr const T& clamp(const T& v, const T& lo, const T& hi, Compare comp);
Requires: Значение lo не должно быть больше hi. Для первой формы тип T должен быть LessThanComparable.
template<class InputIterator1, class InputIterator2>
bool
lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
bool
lexicographical_compare(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
template<class InputIterator1, class InputIterator2, class Compare>
bool
lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
Compare comp);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class Compare>
bool
lexicographical_compare(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
Compare comp);
Returns: true если последовательность элементов, определенная диапазоном [first1, last1) , лексикографически меньше, чем последовательность элементов, определенных диапазоном, [first2, last2) и в false противном случае.
Complexity: По большинству 2min(last1 - first1, last2 - first2) приложений соответствующее сравнение.
Remarks: Если две последовательности имеют одинаковое количество элементов и их соответствующие элементы (если есть) эквивалентны, то ни одна из последовательностей не является лексикографически меньшей, чем другая. Если одна последовательность является префиксом другой, то более короткая последовательность лексикографически меньше, чем более длинная последовательность. В противном случае лексикографическое сравнение последовательностей дает тот же результат, что и сравнение первой соответствующей пары неэквивалентных элементов.
[ Example: Следующий пример реализации удовлетворяет этим требованиям:
for ( ; first1 != last1 && first2 != last2 ; ++first1, (void) ++first2) {
if (*first1 < *first2) return true;
if (*first2 < *first1) return false;
}
return first1 == last1 && first2 != last2;— end example ]
template<class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first,
BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
bool next_permutation(BidirectionalIterator first,
BidirectionalIterator last, Compare comp);
Requires: BidirectionalIterator должны удовлетворять требованиям ValueSwappable.
Effects: Принимает последовательность, определенную диапазоном, [first, last) и преобразует ее в следующую перестановку. Следующая перестановка находится в предположении, что множество всех перестановок лексикографически отсортировано относительно operator< или comp.
Returns: true если такая перестановка существует. В противном случае он преобразует последовательность в наименьшую перестановку, то есть в сортированную по возрастанию, и возвращает false.
template<class BidirectionalIterator>
bool prev_permutation(BidirectionalIterator first,
BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
bool prev_permutation(BidirectionalIterator first,
BidirectionalIterator last, Compare comp);
Requires: BidirectionalIterator должны удовлетворять требованиям ValueSwappable.
Effects: Принимает последовательность, определенную диапазоном, [first, last) и преобразует ее в предыдущую перестановку. Предыдущая перестановка находится в предположении, что набор всех перестановок лексикографически отсортирован относительно operator< или comp.
Returns: true если такая перестановка существует. В противном случае он преобразует последовательность в наибольшую перестановку, то есть отсортированную по убыванию, и возвращает false.