Min c какая библиотека

Функции <algorithm>

Поиск двух соседних элементов, которые либо равны, либо удовлетворяют указанному условию.

Параметры

exec
Используемая политика выполнения.

first
Итератор вперед в позиции первого элемента в диапазоне для поиска.

last
Впереди итератор в позиции, за последним элементом в диапазоне для поиска.

pred
Двоичный предикат, задающий условие, которому должны удовлетворять значения соседних элементов в диапазоне, по которому выполняется поиск.

Возвращаемое значение

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

Алгоритм adjacent_find не изменяет последовательность. Диапазон для поиска должен быть допустимым. Все указатели должны быть разыменовываемыми, а последняя позиция должна быть доступной от первой путем приращения. Временная сложность алгоритма линейно зависит от количества элементов в диапазоне.

operator== , используемый для определения совпадения между элементами, налагает отношение эквивалентности между своими операндами.

Пример

all_of

Возвращает значение true , если условие выполняется каждым элементом заданного диапазона.

Параметры

exec
Используемая политика выполнения.

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

last
Входной итератор, указывающий конец диапазона элементов для проверки условия.

pred
Условие для проверки. pred — это определяемый пользователем объект функции предиката, определяющий условие, которое должно быть удовлетворено проверяемым элементом. Унарный предикат принимает один аргумент и возвращает true или false .

Возвращаемое значение

Возвращает значение true , если условие обнаруживается в каждом элементе указанного диапазона или если диапазон пуст и false в противном случае.

Пример

any_of

Возвращает значение true , если условие выполняется хотя бы один раз в указанном диапазоне элементов.

Параметры

exec
Используемая политика выполнения.

first
Входной итератор, указывающий, откуда должна начинаться проверка диапазона элементов на соответствие условию.

last
Входной итератор, указывающий конец диапазона элементов для проверки условия.

pred
Условие для проверки. Этот тест предоставляется пользовательским объектом функции предиката. Предикат задает условие, которому должен соответствовать проверяемый элемент. Унарный предикат принимает один аргумент и возвращает true или false .

Возвращаемое значение

Возвращает значение true , если хотя бы один элемент в указанном диапазоне соответствует условию, и значение false , если ни один элемент не соответствует условию.

Пример

binary_search

Проверяет, существует ли элемент в отсортированный диапазон, равный указанному значению или эквивалентный ему, в некотором смысле, заданном двоичным предикатом.

Параметры

first
Прямой итератор, адресующий положение первого элемента в диапазоне для поиска.

last
Прямой итератор, адресующий положение на единицу после последнего элемента в диапазоне для поиска.

value
Значение должно соответствовать значению элемента или удовлетворять условию со значением элемента, заданному двоичным предикатом.

pred
Определяемый пользователем объект функции предиката, задающий условие, когда один элемент меньше другого. Бинарный предикат принимает два аргумента и возвращает true в случае соответствия и false в случае несоответствия.

Возвращаемое значение

Значение true , если в диапазоне обнаруживается элемент, равный или эквивалентный указанному значению; в противном случае — значение false .

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

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

Исходные диапазоны не изменяются . binary_search

Типы значений вперед итераторов должны быть меньше, чем сопоставимые для упорядочения. То есть, учитывая два элемента, можно определить, что один меньше другого или что они эквивалентны. (Здесь эквивалент означает, что ни меньше, чем другая.) Это сравнение приводит к упорядочению между элементами nonequivalent.

Сложность алгоритма является логарифмической для итераторов произвольного доступа и линейным в противном случае с количеством шагов, пропорциональным ( last — first ).

Пример

clamp

Сравнивает значение с верхней и нижней границами и возвращает ссылку на значение, если оно находится между границами, или ссылку на верхнюю или нижнюю границу, если значение выше или ниже их соответственно.

Параметры

value
Значение, сравняемое с upper и lower .

lower
Нижняя граница значений для закрепления value .

upper
Верхняя граница значений для закрепления value .

pred
Предикат, используемый для сравнения value или upper lower . Предикат сравнения принимает два аргумента и возвращает, true если первый находится в некотором смысле меньше второго, а в противном случае false .

Возвращаемое значение

Возвращает ссылку на lower значение if value < lower или ссылку на upper if upper < value . В противном случае возвращается ссылка на value .

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

Параметры

exec
Используемая политика выполнения.

first
Итератор ввода, обращающийся к позиции первого элемента в исходном диапазоне.

last
Итератор ввода, обращающийся к позиции, которая на единицу превышает позицию завершающего элемента в исходном диапазоне.

destBeg
Итератор вывода указывает на позицию первого элемента в диапазоне назначения.

Возвращаемое значение

Выходной итератор, указывающий на позицию, которая находится за последним элементом в диапазоне назначения, то есть адрес result итератора + ( last — first ).

Так как алгоритм копирует исходные элементы в порядке, начиная с первого элемента, диапазон назначения может перекрываться с исходным диапазоном, если last позиция исходного диапазона не содержится в диапазоне назначения. copy можно использовать для перемещения элементов влево, но не вправо, если между исходными и целевыми диапазонами нет перекрытия. Чтобы перейти вправо на любое количество позиций, используйте copy_backward алгоритм.

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

Пример

copy_backward

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

Параметры

first
Двунаправленный итератор, обращающийся к положению первого элемента в исходном диапазоне.

last
Двунаправленный итератор, обращающийся к позиции, которая на единицу превышает позицию завершающего элемента в исходном диапазоне.

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

Возвращаемое значение

Выходной итератор, указывающий на позицию, которая находится за последним элементом в диапазоне назначения, то есть адрес destEnd — (last — first) итератора.

Алгоритмы copy_backward и move_backward алгоритмы — это единственные алгоритмы стандартной библиотеки C++, обозначающие выходной диапазон с итератором, указывающим на конец диапазона назначения.

Так как алгоритм копирует исходные элементы в порядке, начиная с последнего элемента, диапазон назначения может перекрываться с исходным диапазоном, предоставленным first положением исходного диапазона, не содержится в диапазоне назначения. copy_backward можно использовать для перемещения элементов вправо, но не влево, если между исходным и целевым диапазонами нет перекрытия. Чтобы перейти влево на любое количество позиций, используйте copy алгоритм.

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

Пример

copy_if

Копирует из диапазона элементов те элементы, проверка которых на соответствие заданному условию дает значение true .

Параметры

exec
Используемая политика выполнения.

first
Входной итератор, указывающий начало диапазона для проверки условия.

last
Входной итератор, указывающий конец диапазона.

dest
Выходной итератор, указывающий место назначения для скопированных элементов.

pred
Условие, на соответствие которому проверяется каждый элемент в диапазоне. Это условие предоставляется определенным пользователем объектом функции предиката. Унарный предикат принимает один аргумент и возвращает true или false .

Возвращаемое значение

Выходной итератор, который увеличивает dest на единицу после каждого элемента, удовлетворяющего условию. Другими словами, возвращаемое значение минус dest равно количеству скопированных элементов.

один раз для каждого N в диапазоне [0, last — first) строго на увеличение значений N , начиная с наименьшего значения. Если dest и first назначьте области хранения, dest не должны находиться в диапазоне [ first, last ) .

Пример

copy_n

Копирует указанное количество элементов.

Параметры

exec
Используемая политика выполнения.

first
Входной итератор, указывающий, откуда копировать элементы.

count
Целое число со знаком или без знака, указывающее количество копируемых элементов.

dest
Выходной итератор, указывающий, куда копировать элементы.

Возвращаемое значение

Возвращает выходной итератор, куда были скопированы элементы. Это то же самое, что и возвращаемое значение dest параметра.

Функция шаблона проверяет *(dest + N) = *(first + N)) один раз для каждого N в диапазоне [0, count) строго на увеличение значений N начиная с наименьшего значения. Затем оно возвращает значение dest + N . Если dest и first назначьте области хранения, dest не должны находиться в диапазоне [first, last) .

Пример

count

Возвращает количество элементов в диапазоне, значения которых соответствуют заданному значению.

Параметры

exec
Используемая политика выполнения.

first
Входной итератор, адресующий положение первого элемента в диапазоне для прохода.

last
Входной итератор, указывающий позицию, следующую за последним элементом в диапазоне для прохода.

value
Значение элементов для подсчета.

Возвращаемое значение

Тип InputIterator разницы, который подсчитывает количество элементов в диапазоне [ first , last ) с значением value .

Пример

count_if

Возвращает количество элементов в диапазоне, значения которых соответствуют заданному условию.

Параметры

exec
Используемая политика выполнения.

first
Входной итератор, адресующий положение первого элемента в диапазоне для поиска.

last
Входной итератор, адресующий положение на единицу после последнего элемента в диапазоне для поиска.

pred
Определенный пользователем объект функции предиката, задающий условие, которое должно удовлетворяться, чтобы элемент был подсчитан. Унарный предикат принимает один аргумент и возвращает true или false .

Возвращаемое значение

Количество элементов, которые удовлетворяют условию, заданному предикатом.

Пример

equal

Сравнивает два диапазона поэлементно на признак равенства или равноценности в смысле, заданном бинарным предикатом.

Используйте std::equal при сравнении элементов в разных типах контейнеров (например vector , и list ) или при сравнении различных типов элементов или при сравнении подрангов контейнеров. При сравнении элементов одного типа в контейнерах одного типа используйте оператор operator== , предоставляемый для каждого контейнера.

Используйте перегрузки с двумя диапазонами в коде C++14, так как перегрузки, которые принимают только один итератор для второго диапазона, не будут обнаруживать различия, если второй диапазон длиннее первого диапазона. Эти перегрузки приведут к неопределенному поведению, если второй диапазон короче первого диапазона.

Параметры

exec
Используемая политика выполнения.

first1
Входной итератор, указывающий на положение первого элемента в первом диапазоне для тестирования.

last1
Входной итератор, указывающий на положение, следующее за последним элементом, в первом диапазоне для тестирования.

first2
Входной итератор, указывающий на положение первого элемента во втором диапазоне для тестирования.

last2
Входной итератор, указывающий на положение, следующее за последним элементом, во втором диапазоне для тестирования.

pred
Заданный пользователем объект функции предиката, определяющий условие, которое должно выполняться, чтобы два элемента считались эквивалентными друг другу. Бинарный предикат принимает два аргумента и возвращает true в случае соответствия и false в случае несоответствия.

Возвращаемое значение

true Значение , если диапазоны идентичны или эквивалентны двоичному предикату при сравнении элемента по элементу; false в противном случае .

Диапазон, по которому ведется поиск, должен быть допустимым. Все итераторы должны поддерживать сброс ссылок и должна быть возможность достижения последнего положения, начиная от первого, путем приращения.

Если два диапазона имеют одинаковую длину, то временная сложность алгоритма линейно зависит от числа элементов в диапазоне. В противном случае функция немедленно возвращает значение false .

Для введения симметричного, рефлексивного и транзитивного отношения между операндами не требуется operator== или определяемый пользователем предикат.

Пример

equal_range

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

Параметры

first
Прямой итератор, адресующий положение первого элемента в диапазоне для поиска.

last
Прямой итератор, адресующий положение на единицу после последнего элемента в диапазоне для поиска.

value
Значение для поиска в упорядоченном диапазоне.

pred
Определяемый пользователем объект функции предиката, задающий условие, когда один элемент меньше другого. Предикат сравнения принимает два аргумента и возвращается true , когда они удовлетворены и false когда они не удовлетворены.

Возвращаемое значение

Пара прямых итераторов, задающих поддиапазон в искомом диапазоне, в котором все элементы эквивалентны value в смысле, заданном используемым двоичным предикатом ( pred или по умолчанию «меньше чем»).

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

Диапазон должен быть упорядочен согласно предикату, предоставленному в equal_range . Например, если вы собираетесь использовать предикат больше, чем предикат, диапазон должен быть отсортирован в порядке убывания.

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

Сложность алгоритма является логарифмической для итераторов произвольного доступа и линейным в противном случае с количеством шагов, пропорциональным ( last — first ).

Пример

Присваивает одно и то же новое значение каждому элементу в заданном диапазоне.

Параметры

exec
Используемая политика выполнения.

first
Прямой итератор, указывающий на позицию первого элемента в диапазоне для прохода.

last
Прямой итератор, указывающий на позицию, следующую за последним элементом в диапазоне для прохода.

value
Значение, присваиваемое элементам в диапазоне [ first , last ).

Целевой диапазон должен быть допустимым; все указатели должны поддерживать сброс ссылок; должна быть возможность достижения последнего положения с первого путем приращения. Сложность линейная по отношению к размеру диапазона.

Пример

fill_n

Назначает новое значение указанному количеству элементов в диапазоне, начиная с определенного элемента.

Параметры

exec
Используемая политика выполнения.

first
Выходной итератор, указывающий позицию первого элемента в диапазоне, в котором должны назначаться значения value .

count
Целое число со знаком или без знака, указывающее количество элементов, которым следует назначить значение.

value
Значение, присваиваемое элементам в диапазоне [ first , first + count ).

Возвращаемое значение

Итератор элемента, который следует за последним элементом, заполненным, если count > нуль, в противном случае — первый элемент.

Пример

Находит позицию первого вхождения элемента с заданным значением в диапазон.

Параметры

exec
Используемая политика выполнения.

first
Входной итератор, адресующий положение первого элемента в диапазоне для поиска заданного значения.

last
Входной итератор, адресующий положение после последнего элемента в диапазоне для поиска заданного значения.

value
Значение, которое нужно найти.

Возвращаемое значение

Входной итератор, адресующий первое вхождение заданного значения в диапазоне, в котором выполняется поиск. Если не найдено ни одного элемента с эквивалентным значением, возвращается last .

find_end

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

Параметры

first1
Прямой итератор, адресующий положение первого элемента в диапазоне для поиска.

last1
Прямой итератор, указывающий на положение, следующее за последним элементом в диапазоне для поиска.

first2
Прямой итератор, указывающий на положение первого элемента в диапазоне для поиска.

last2
Прямой итератор, указывающий на положение, следующее за последним элементом в диапазоне для поиска.

Возвращаемое значение

Переадресация итератора, адресующего позицию первого элемента последней подсевенности в [first1, last1), которая соответствует указанной последовательности [first2, last2).

Пример

find_first_of

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

Параметры

first1
Прямой итератор, адресующий положение первого элемента в диапазоне для поиска.

last1
Прямой итератор, адресующий положение на единицу после последнего элемента в диапазоне для поиска.

first2
Прямой итератор, адресующий положение первого элемента в диапазоне для сравнения.

last2
Прямой итератор, адресующий положение на единицу после последнего элемента в диапазоне для сравнения.

Возвращаемое значение

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

Пример

find_if

Находит позицию первого вхождения элемента, удовлетворяющего определенному условию, в диапазон.

Параметры

first
Входной итератор, адресующий положение первого элемента в диапазоне для поиска.

last
Входной итератор, адресующий положение на единицу после последнего элемента в диапазоне для поиска.

pred
Определенный пользователем объект функции предиката или лямбда-выражение, определяющее условие, которому должен соответствовать искомый элемент. Унарный предикат принимает один аргумент и возвращается true в случае удовлетворения или false если он не удовлетворяется. Подпись pred должна быть bool pred(const T& arg); , где T — тип, к которому можно явным образом привести InputIterator при сбросе ссылки. Ключевое const слово показано только для иллюстрации того, что объект функции или лямбда-выражение не должны изменять аргумент.

Возвращаемое значение

Входной итератор, ссылающийся на первый элемент в диапазоне, удовлетворяющий условию, заданному предикатом (результат предиката true ). Если не найдено ни одного элемента, удовлетворяющего условию предиката, возвращается last .

Эта функция-шаблон представляет собой обобщение алгоритма find , заменяя предикат «равно определенному значению» любым предикатом. Для логической противоположности (найдите первый элемент, который не удовлетворяет предикату), см. в разделе find_if_not .

Пример

find_if_not

Возвращает первый элемент в указанном диапазоне, который не удовлетворяет условию.

Параметры

first
Входной итератор, адресующий положение первого элемента в диапазоне для поиска.

last
Входной итератор, адресующий положение на единицу после последнего элемента в диапазоне для поиска.

pred
Определенный пользователем объект функции предиката или лямбда-выражение, определяющее условие, которому не должен соответствовать искомый элемент. Унарный предикат принимает один аргумент и возвращается true в случае удовлетворения или false если он не удовлетворяется. Подпись pred должна быть bool pred(const T& arg); , где T — тип, к которому можно явным образом привести InputIterator при сбросе ссылки. Ключевое const слово показано только для иллюстрации того, что объект функции или лямбда-выражение не должны изменять аргумент.

Возвращаемое значение

Входной итератор, ссылающийся на первый элемент в диапазоне, который не удовлетворяет условию, заданному предикатом (результат false предиката). Если все элементы удовлетворяют условию предиката (результат предиката true для всех элементов), возвращает last .

Эта функция-шаблон представляет собой обобщение алгоритма find , заменяя предикат «равно определенному значению» любым предикатом. Для логической противоположности (найдите первый элемент, удовлетворяющий предикату), см. раздел find_if .

Пример кода, который легко адаптируется к find_if_not() , см. в разделе find_if .

for_each

Применяет заданный объект функции к каждому элементу в прямом порядке в пределах диапазона и возвращает объект функции.

Параметры

first
Входной итератор, адресующий положение первого элемента в диапазоне для работы.

last
Итератор ввода содержит положение элемента, стоящего за последним рассматриваемым элементом в нужном диапазоне.

func
Определенный пользователем объект функции, который применяется к каждому элементу в диапазоне.

Возвращаемое значение

Копия объекта функции после того, как он будет применён ко всем элементам в диапазоне.

Алгоритм for_each является гибким, что позволяет изменять каждый элемент в диапазоне различными пользовательскими способами. Шаблонизируемые функции могут использоваться многократно в измененной форме путем передачи разных параметров. Определяемые пользователем функции могут накапливать сведения во внутреннем состоянии, которое может возвращать алгоритм после обработки всех элементов в диапазоне.

Сложность является линейной с не более чем ( last — first ) сравнениями.

Пример

for_each_n

Применяет указанный объект функции к указанному числу элементов в диапазоне, начиная с определенного элемента.

Параметры

exec
Используемая политика выполнения.

first
Входной итератор в позиции первого элемента в диапазоне для работы.

count
Количество элементов для работы.

func
Определяемый пользователем объект функции, применяемый к каждому элементу диапазона [ first , first + count ).

Возвращаемое значение

Итератор элемента, который следует последнему обработанному элементу, если count > нуль, в противном случае — первый элемент.

Пример

В этом примере определяется класс объекта функции. Рабочий lambda код часто используется для достижения того же результата с меньшим количеством кода.

generate

Присваивает значения, создаваемые объектом функции, каждому элементу в диапазоне.

Параметры

first
Переадресация итератора в позиции первого элемента в диапазоне, к которому должны быть назначены значения.

last
Переадресация итератора в позиции, которая за последним элементом в диапазоне, к которому должны быть назначены значения.

gen
Объект функции, вызываемый без аргументов для создания значений, назначенных каждому элементу в диапазоне.

Объект функции вызывается для каждого элемента в диапазоне и не должен возвращать одно и то же значение при каждом вызове. Например, он может читать данные из файла или ссылаться на локальное состояние и изменять его. Тип результата генератора должен быть преобразован в тип значения прямого итератора для диапазона.

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

Сложность является линейной, с точными last — first вызовами генератора.

Пример

generate_n

Присваивает значения, созданные объектом функции, указанному числу элементов в диапазоне. Возвращает позицию за последним назначенным значением.

Параметры

exec
Используемая политика выполнения.

first
Выходной итератор, обращающийся к позиции первого элемента в диапазоне, которому назначаются значения.

count
Целочисленный тип со знаком или без знака, указывающий количество элементов, которым функция генератора назначит значение.

gen
Объект функции, который вызывается без аргументов и используется для формирования значений, которые необходимо назначить каждому из элементов в диапазоне.

Объект функции вызывается для каждого элемента в диапазоне и не должен возвращать одно и то же значение при каждом вызове. Например, он может читать данные из файла или ссылаться на локальное состояние и изменять его. Тип результата должен поддерживать преобразование в тип значения прямых итераторов диапазона.

Отношение сложности линейное, требуется ровно count вызовов генератора.

Пример

includes

Проверяет, содержит ли один отсортированный диапазон все элементы, содержащиеся во втором отсортированном диапазоне, где порядок сортировки или критерий эквивалентности элементов можно задать бинарным предикатом.

Параметры

exec
Используемая политика выполнения.

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

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

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

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

Возвращаемое значение

true Значение , если первый отсортированный диапазон содержит все элементы во втором отсортированный диапазон; false в противном случае .

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

В качестве предусловия для применения алгоритма includes отсортированные исходные диапазоны должны быть упорядочены с тем же упорядочением, который используется алгоритмом для сортировки объединенных диапазонов.

Исходные диапазоны не изменяются алгоритмом merge .

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

Сложность алгоритма является линейной с наибольшим 2 * ((last1 — first1) + (last2 — first2)) — 1 числом сравнений для непустых исходных диапазонов.

Пример

inplace_merge

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

Параметры

exec
Используемая политика выполнения.

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

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

last
Двунаправленный итератор, указывающий позицию, следующую за последним элементом во втором из двух последовательных упорядоченных диапазонов, которые следует объединить и упорядочить в один диапазон.

pred
Определяемый пользователем объект функции предиката, задающий условие, когда один элемент меньше другого. Предикат сравнения принимает два аргумента и должен возвращать, true если первый элемент меньше второго элемента и в false противном случае.

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

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

Сложность зависит от объема доступной памяти, так как алгоритм выделяет память для временного буфера. Если доступно достаточно памяти, лучше всего использовать линейную линию с (last — first) — 1 сравнениями; если нет вспомогательной памяти, то в худшем случае — N log(N) где = N last — first .

Пример

is_heap

Возвращает значение true , если элементы в указанном диапазоне образуют кучу.

Параметры

exec
Используемая политика выполнения.

first
Итератор произвольного доступа, указывающий начало диапазона для проверки кучи.

last
Итератор произвольного доступа, указывающий конец диапазона.

pred
Условие для проверки порядка элементов. Предикат сравнения принимает два аргумента и возвращает true или false .

Возвращаемое значение

Возвращает значение true , если элементы в указанном диапазоне образуют кучу, false если они нет.

is_heap_until

Возвращает итератор, расположенный в первом элементе диапазона [ first , ), last который не удовлетворяет условию упорядочения кучи или end если диапазон формирует кучу.

Параметры

exec
Используемая политика выполнения.

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

last
Итератор произвольного доступа, который задает конец диапазона для проверки кучи.

pred
Двухместный предикат, который задает условие строгого слабого упорядочения, определяющее кучу. Предикат по умолчанию не std::less<> pred указан.

Возвращаемое значение

Возвращает last , если указанный диапазон формирует кучу или содержит один элемент либо менее. В противном случае возвращает итератор для первого найденного элемента, который не удовлетворяет условию кучи.

Первая функция шаблона возвращает последний итератор next в [first, last) , где [first, next) — это куча, упорядоченная по объекту функции std::less<> . Если расстояние last — first меньше 2, функция возвращается last .

Вторая функция-шаблон работает так же, как первая, но использует в качестве условия упорядочения кучи предикат pred вместо std::less<> .

is_partitioned

Возвращает значение true , если все элементы в заданном диапазоне, возвращающие true для какого-либо условия, расположены перед всеми элементами, возвращающими false .

Параметры

exec
Используемая политика выполнения.

first
Входной итератор, указывающий, где начинается диапазон для проверки условия.

last
Входной итератор, указывающий конец диапазона.

pred
Условие для проверки. Этот тест предоставляется определяемым пользователем объектом функции предиката, который определяет условие, которое должно быть удовлетворено элементом, для которых выполняется поиск. Унарный предикат принимает один аргумент и возвращает true или false .

Возвращаемое значение

Возвращает значение true , когда все элементы в заданном диапазоне, которые проверяют true условие, приходят до всех элементов, которые проверяют false , и в противном случае возвращается false .

Функция шаблона возвращает true , только если все элементы в [first, last) секционированы по pred , то есть все элементы X в [first, last) , для которых pred (X) имеет значение true, находятся перед всеми элементами Y , для которых pred (Y) — false .

is_permutation

Возвращает значение true , если оба диапазона содержат одни и те же элементы, независимо от того, находятся ли элементы в одном порядке. Используйте перегрузки с двумя диапазонами в коде C++14, так как перегрузки, которые принимают только один итератор для второго диапазона, не будут обнаруживать различия, если второй диапазон длиннее первого диапазона. Эти перегрузки приведут к неопределенному поведению, если второй диапазон короче первого диапазона.

Параметры

first1
Прямой итератор, указывающий на первый элемент диапазона.

last1
Прямой итератор, указывающий на место, следующее за последним элементом диапазона.

first2
Прямой итератор, указывающий на первый элемент второго диапазона, используемый для сравнения.

last2
Прямой итератор, указывающий на место, следующее за последним элементом второго диапазона, используемым для сравнения.

pred
Предикат, который проверяет равенство и возвращает bool .

Возвращаемое значение

true , когда диапазоны можно переупорядочить так, чтобы они стали совпадающими в соответствии с предикатом сравнения. В противном случае — false .

В первой функции шаблона предполагается, что в диапазоне есть столько элементов, сколько в диапазоне first2 , заданном [first1, last1) . Если в втором диапазоне есть больше элементов, они игнорируются; Если меньше, произойдет неопределенное поведение. Третья функция шаблона (C++14 и более поздних версий) не делает это предположение. Оба значения возвращаются true только в том случае, если для каждого элемента X в диапазоне, заданном Y [first1, last1) в том же диапазоне X == Y , что и в диапазоне, начиная first2 с или [first2, last2) . operator== Здесь необходимо выполнить попарное сравнение операндов.

Вторая и четвертая функции шаблона действуют одинаково, за исключением того, что они заменяют operator==(X, Y) на Pred(X, Y) . Для правильного поведения предикат должен быть симметричным, рефлексивным и транзитивным.

Пример

В следующем примере показано использование is_permutation .

is_sorted

Возвращает значение true , если элементы в указанном диапазоне расположены в порядке сортировки.

Параметры

exec
Используемая политика выполнения.

first
Прямой итератор, указывающий, где начинается диапазон для проверки.

last
Прямой итератор, указывающий конец диапазона.

pred
Условие теста для определения порядка между двумя элементами. Предикат сравнения принимает два аргумента и возвращает true или false . Этот предикат выполняет ту же задачу, что и operator< .

is_sorted_until

Возвращает ForwardIterator , установленный в последний элемент в порядке сортировки из указанного диапазона.

Вторая версия позволяет предоставить объект функции сравнения, возвращающий, true когда два заданных элемента находятся в порядке сортировки и в false противном случае.

Параметры

exec
Используемая политика выполнения.

first
Прямой итератор, указывающий, где начинается диапазон для проверки.

last
Прямой итератор, указывающий конец диапазона.

pred
Условие теста для определения порядка между двумя элементами. Предикат сравнения принимает два аргумента и возвращает true или false .

Возвращаемое значение

Возвращает ForwardIterator , установленный в последний элемент в порядке сортировки. Отсортированная последовательность начинается с first .

Первая функция-шаблон возвращает последний итератор next в [first, last] , так что [first, next) — это последовательность, упорядоченная по operator< . Если distance() значение меньше 2, функция возвращается last .

Вторая функция шаблона работает так же, за исключением того, что она заменяет operator<(X, Y) на pred(X, Y) .

iter_swap

Меняет местами два значения, указанные парой определенных итераторов.

Параметры

left
Один из прямых итераторов, значение которого должно быть изменено.

right
Второй из прямых итераторов, значение которого должно быть изменено.

swap следует использовать в предпочтениях iter_swap, которая была включена в стандарт C++ для обратной совместимости. Если Fit1 и Fit2 являются итераторами пересылки, то iter_swap( Fit1, Fit2 ) эквивалентен swap( *Fit1, *Fit2 ) .

Типы значений входных прямых итераторов должны иметь одно и то же значение.

Пример

lexicographical_compare

Сравнивает две последовательности поэлементно для определения того, какой элемент из двух меньше.

Параметры

exec
Используемая политика выполнения.

first1
Входной итератор, указывающий на положение первого элемента в первом диапазоне для сравнения.

last1
Входной итератор, указывающий на положение, следующее за последним элементом в первом диапазоне для сравнения.

first2
Входной итератор, указывающий на положение первого элемента во втором диапазоне для сравнения.

last2
Входной итератор, указывающий на положение, следующее за последним элементом во втором диапазоне для сравнения.

Возвращаемое значение

true Значение , если первый диапазон лексикографически меньше второго диапазона; в противном случае false .

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

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

Пример

lower_bound

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

Параметры

first
Прямой итератор, адресующий положение первого элемента в диапазоне для поиска.

last
Прямой итератор, адресующий положение на единицу после последнего элемента в диапазоне для поиска.

value
Значение, чья первая позиция или возможная первая позиция ищется в упорядоченном диапазоне.

Возвращаемое значение

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

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

Предварительным условием для использования lower_bound является упорядоченный диапазон, порядок в котором тот же, что и заданный двоичным предикатом.

Диапазон не изменяется алгоритмом lower_bound .

Типы значений вперед итераторов должны быть меньше, чем сравнимые для упорядочения. То есть, учитывая два элемента, можно определить, что одно меньше другого или что они эквивалентны. (Здесь эквивалент означает, что ни меньше другого.) Это сравнение приводит к упорядочению между элементами nonequivalent.

Сложность алгоритма — логарифмическая для итераторов произвольного доступа и линейного иначе с количеством шагов, пропорциональным ( last — first ).

Пример

make_heap

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

Параметры

first
Итератор произвольного доступа, обращающийся к позиции первого элемента в диапазоне, подлежащем преобразованию в кучу.

last
Итератор произвольного доступа, обращающийся к позиции, следующей за последним элементом в диапазоне, подлежащем преобразованию в кучу.

Пример

Сравнивает два объекта и возвращает больший из них, где критерий упорядочивания может быть указан бинарным предикатом.

Параметры

left
Первый из сравниваемых объектов.

right
Второй из сравниваемых объектов.

pred
Двоичный предикат, используемый для сравнения двух объектов.

inlist
Список initializer с объектами, которые необходимо сравнить.

Возвращаемое значение

Больший из двух объектов, если ни один из них не больше — в этом случае возвращается первый из двух объектов. При указании initializer_list он возвращает наибольшее количество объектов в списке.

При использовании алгоритма max очень редко объекты передаются как параметры. Большинство алгоритмов библиотеки стандартных программ C++ работают в диапазоне элементов, позиция которых задается итераторами, передаваемыми в качестве параметров. Если вам нужна функция, которая работает с диапазоном элементов, используйте max_element вместо этого. Visual Studio 2017 включает constexpr перегрузки, которые принимают initializer_list .

Пример

max_element

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

Параметры

exec
Используемая политика выполнения.

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

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

Возвращаемое значение

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

Пример

merge

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

Параметры

exec
Используемая политика выполнения.

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

last1
Входной итератор, обращающийся к позиции, следующей за последним элементом в первом из двух упорядоченных исходных диапазонов, которые следует объединить и упорядочить в один диапазон.

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

last2
Входной итератор, обращающийся к позиции, следующей за последним элементом во втором из двух последовательных упорядоченных исходных диапазонов, которые следует объединить и упорядочить в один диапазон.

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

Возвращаемое значение

Выходной итератор, указывающий на позицию, следующую за последним элементом, в упорядоченном диапазоне назначения.

Каждый упорядоченный исходный диапазон должны быть упорядочен в качестве предусловия для применения алгоритма merge в соответствии с теми же правилами, чтобы использоваться алгоритмом для упорядочения объединенных диапазонов.

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

Типы значений входных итераторов должны быть меньше, чем сравнимые для упорядочения. То есть, учитывая два элемента, можно определить, что одно меньше другого или что они эквивалентны. (Здесь эквивалент означает, что ни меньше другого.) Это сравнение приводит к упорядочению между элементами nonequivalent. Если эквивалентные элементы имеются в обоих исходных диапазонах, в диапазоне назначения элементы из первого диапазона будут предшествовать элементам из второго исходного диапазона.

Сложность алгоритма является линейной с наибольшим (last1 — first1) — (last2 — first2) — 1 количеством сравнений.

Класс list предоставляет функцию-член merge для слияния элементов двух списков.

Пример

Сравнивает два объекта и возвращает меньший из них, где критерий упорядочивания может быть указан бинарным предикатом.

Параметры

left
Первый из сравниваемых объектов.

right
Второй из сравниваемых объектов.

pred
Двоичный предикат, используемый для сравнения двух объектов.

inlist
Объект initializer_list , содержащий элементы для сравнения.

Возвращаемое значение

Меньший из двух объектов; если ни один из них не меньше, то возвращается первый из двух объектов. initializer_list Если указан объект, он возвращает наименьшее количество объектов в списке.

При использовании алгоритма min очень редко объекты передаются как параметры. Большинство алгоритмов библиотеки стандартных программ C++ работают в диапазоне элементов, позиция которых задается итераторами, передаваемыми в качестве параметров. Если вам нужна функция, использующая диапазон элементов, используйте min_element . constexpr в Visual Studio 2017 г. включена initializer_list перегрузка.

Пример

min_element

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

Параметры

exec
Используемая политика выполнения.

first
Прямой итератор, указывающий положение первого элемента в диапазоне для поиска наименьшего элемента.

last
Прямой итератор, указывающий положение, следующее за последним элементом в диапазоне для поиска наименьшего элемента.

pred
Определяемый пользователем объект функции предиката, задающий условие, когда один элемент меньше другого. Предикат сравнения принимает два аргумента и должен возвращать true , если первый элемент меньше второго элемента и false в противном случае.

Возвращаемое значение

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

Пример

minmax_element

Выполняет работу, которую делают min_element и max_element , в одном вызове.

Параметры

exec
Используемая политика выполнения.

first
Прямой итератор, указывающий начало диапазона.

last
Прямой итератор, указывающий конец диапазона.

pred
Определяемый пользователем объект функции предиката, определяющий смысл, в котором один элемент меньше другого. Предикат сравнения принимает два аргумента и должен возвращать true значение, если первое меньше второго и false в противном случае.

Возвращаемое значение

pair<ForwardIterator, ForwardIterator>( min_element(first, last), max_element(first, last)) .

minmax

Сравнивает два входных параметра и возвращает их в виде пары, в порядке от меньшего к большему.

Параметры

left
Первый из сравниваемых объектов.

right
Второй из сравниваемых объектов.

pred
Двоичный предикат, используемый для сравнения двух объектов.

inlist
Объект initializer_list , содержащий элементы для сравнения.

mismatch

Сравнивает поэлементно два диапазона и находит первую позицию, где элементы отличаются.

Используйте перегрузки с двумя диапазонами в коде C++14, так как перегрузки, которые принимают только один итератор для второго диапазона, не обнаруживают различий, если второй диапазон длиннее первого диапазона. Эти перегрузки приведут к неопределенному поведению, если второй диапазон короче первого диапазона.

Параметры

exec
Используемая политика выполнения.

first1
Входной итератор, указывающий на положение первого элемента в первом диапазоне для тестирования.

first2
Входной итератор, указывающий на положение первого элемента во втором диапазоне для тестирования.

pred
Определяемый пользователем объект функции предиката, который сравнивает текущие элементы в каждом диапазоне и определяет, эквивалентен ли он. Он возвращается true , когда оно удовлетворено и false если оно не удовлетворено.

Возвращаемое значение

Возвращает пару итераторов, указывающих на позиции несоответствия в двух диапазонах. Первый итератор компонента указывает на позицию в первом диапазоне. Второй итератор компонента указывает на позицию во втором диапазоне. Если нет разницы между элементами в сравниваемых диапазонах или если двоичный предикат во второй версии удовлетворяется всеми парами элементов из двух диапазонов, то первый итератор компонента указывает на позицию, последнюю позицию в первом диапазоне, а второй итератор компонента указывает на позицию, последнюю позицию, протестированную во втором диапазоне.

При выполнении первой функции шаблона предполагается, что в диапазоне, начинающемся с first2, имеется столько же элементов, сколько в диапазоне, указанном аргументами [first1, last1). Если в втором диапазоне больше, они игнорируются; Если их меньше, то результатом неопределенного поведения будет.

Временная сложность алгоритма линейно зависит от количества элементов в более коротком диапазоне.

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

Пример

В следующем примере демонстрируется использование несовпадения. Перегрузка C++ 03 показана только с целью демонстрации того, как она может привести к непредвиденному результату.

<alg> move

Перемещает элементы, связанные с заданным диапазоном.

Параметры

exec
Используемая политика выполнения.

first
Входной итератор, указывающий, откуда начинается диапазон элементов для перемещения.

last
Входной итератор, указывающий конец диапазона элементов для перемещения.

dest
Выходной итератор, который должен содержать перемещенные элементы.

Функция шаблона проверяет *(dest + N) = move(*(first + N)) один раз для каждого N в диапазоне [0, last — first) строго на увеличение значений N начиная с наименьшего значения. Затем оно возвращает значение dest + N . Если dest и first указать области хранения, dest не должно находиться в диапазоне [first, last) .

move_backward

Перемещает элементы одного итератора в другой. Перемещение начинается с последнего элементом в указанном диапазоне и завершается первым элементом в этом диапазоне.

Параметры

first
Итератор, указывающий начало диапазона, из которого должны перемещаться элементы.

last
Итератор, указывающий конец диапазона, из которого должны перемещаться элементы. Этот элемент не перемещается.

Функция шаблона проверяет *(destEnd — N — 1) = move(*(last — N — 1)) один раз для каждого N в диапазоне [0, last — first) строго на увеличение значений N начиная с наименьшего значения. Затем оно возвращает значение destEnd — (last — first) . Если destEnd и first указать области хранения, destEnd не должно находиться в диапазоне [first, last) .

move и move_backward — функциональный эквивалент использованию copy и copy_backward с итератором перемещения.

next_permutation

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

Параметры

first
Двунаправленный итератор, указывающий позицию первого элемента в диапазоне, в котором переставляются элементы.

last
Двунаправленный итератор, указывающий позицию, следующую за последним элементом в диапазоне, в котором переставляются элементы.

pred
Определяемый пользователем объект функции предиката, задающий критерий сравнения, который должен соблюдаться идущими подряд элементами при упорядочении. Бинарный предикат принимает два аргумента и возвращает true в случае соответствия и false в случае несоответствия.

Возвращаемое значение

true Значение , если лексикографическо следующая перестановка существует и заменила исходное упорядочение диапазона; в противном случае false порядок преобразуется в лексикографическо наименьшую перестановку.

Пример

nth_element

Секционирует диапазон элементов, правильно размещая n-йэлемент последовательности в диапазоне, который соответствует этим критериям: все элементы перед ним меньше или равны ему, а все последующие элементы больше или равны ему.

Параметры

exec
Используемая политика выполнения.

first
Итератор произвольного доступа, указывающий позицию первого элемента в разделяемом диапазоне.

nth
Итератор произвольного доступа, указывающий позицию элемента для правильного упорядочивания на границе раздела.

last
Итератор произвольного доступа, обращающийся к позиции, следующей за последним элементом в разделяемом диапазоне.

pred
Определяемый пользователем объект функции предиката, задающий критерий сравнения, который должен соблюдаться идущими подряд элементами при упорядочении. Предикат сравнения принимает два аргумента и возвращается true при удовлетворении и false в случае, если он не удовлетворяется.

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

Если ни один из элементов не меньше другого, то эти элементы эквивалентны, но не обязательно равны.

Средняя сложность сортировки является линейной относительно last — first .

Пример

none_of

Возвращает значение true , если условие не выполняется ни одним элементом заданного диапазона.

Параметры

exec
Используемая политика выполнения.

last
Входной итератор, указывающий конец диапазона элементов.

pred
Условие для проверки. Этот тест предоставляется определяемым пользователем объектом функции предиката, который определяет условие. Унарный предикат принимает один аргумент и возвращает true или false .

Возвращаемое значение

Возвращает значение true , если условие не обнаружено хотя бы один раз в указанном диапазоне и false если условие обнаружено.

partial_sort

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

Параметры

exec
Используемая политика выполнения.

first
Итератор произвольного доступа, обращающийся к позиции первого элемента в сортируемом диапазоне.

sortEnd
Итератор произвольного доступа, обращающийся к позиции, следующей за последним элементом в сортируемом поддиапазоне.

last
Итератор произвольного доступа, обращающийся к позиции, следующей за последним элементом в диапазоне для частичной сортировки.

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

Средняя сложность частичной сортировки — журнал O(( last — first ) ( sortEnd — first )).

Пример

partial_sort_copy

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

Параметры

exec
Используемая политика выполнения.

first1
Итератор ввода, обращающийся к позиции первого элемента в исходном диапазоне.

last1
Входной итератор, указывающий позицию, следующую за последним элементом в исходном диапазоне.

first2
Итератор произвольного доступа, указывающий позицию первого элемента в сортируемом диапазоне назначения.

last2
Итератор произвольного доступа, указывающий позицию, следующую за последним элементом в сортируемом диапазоне назначения.

Возвращаемое значение

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

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

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

Пример

partition

Классифицирует элементы в диапазоне на два несвязанных набора, при этом эти элементы удовлетворяют унарному предикату, предшествующему тем, которые не удовлетворяют его.

Параметры

exec
Используемая политика выполнения.

first
Двунаправленный итератор адресует позицию первого элемента в разделяемом диапазоне.

last
Двунаправленный итератор, указывающий позицию, следующую за последним элементом в разделяемом диапазоне.

pred
Определенный пользователем объект функции предиката, задающий условие, которое должно удовлетворяться, чтобы элемент был классифицирован. Унарный предикат принимает один аргумент и возвращает true или false .

Возвращаемое значение

Двунаправленный итератор указывает позицию первого элемента в диапазоне, не соответствующего условию предиката.

Элементы a и b эквивалентны, но не обязательно равны, если оба pred( a, b ) значения имеют значение false и pred( b, a ) false, где pred указан предикат, указанный параметром. Алгоритм partition не является стабильным и не гарантирует, что будет сохранено относительное упорядочение эквивалентных элементов. Алгоритм stable_partition сохраняет этот исходный порядок.

Сложность является линейной: есть (last — first) приложения pred и не более (last — first)/2 чем переключения.

Пример

partition_copy

Копирует элементы, возвращающие true для какого-либо условия, в одно место назначения, а возвращающие false — в другое. Эти элементы должны поступать из указанного диапазона.

Параметры

exec
Используемая политика выполнения.

first
Входной итератор, указывающий начало диапазона для проверки условия.

last
Входной итератор, указывающий конец диапазона.

dest1
Выходной итератор, используемый для копирования элементов, которые возвращают значение true при проверке на соответствие условию с использованием pred .

dest2
Выходной итератор, используемый для копирования элементов, которые возвращают значение false при проверке на соответствие условию с использованием pred .

pred
Условие для проверки. Тест предоставляется определяемым пользователем объектом функции предиката, который определяет условие для тестирования. Унарный предикат принимает один аргумент и возвращает true или false .

partition_point

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

Параметры

first
ForwardIterator , указывающий начало диапазона для проверки условия.

last
ForwardIterator , указывающий конец диапазона.

pred
Условие для проверки. Тест предоставляется определяемым пользователем объектом функции предиката, который определяет условие для удовлетворения элементом, который выполняет поиск. Унарный предикат принимает один аргумент и возвращает true или false .

Возвращаемое значение

Возвращает объект ForwardIterator , ссылающийся на первый элемент, который не соответствует условию, тестируемого на pred , или возвращается last , если он не найден.

pop_heap

Удаляет наибольший элемент из начала кучи до позиции, следующей за последней, в диапазоне, а затем формирует новую кучу из оставшихся элементов.

Параметры

first
Итератор произвольного доступа, обращающийся к позиции первого элемента в куче.

last
Итератор произвольного доступа, обращающийся к позиции, следующей за последним элементом в куче.

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

Кучи имеют два следующих свойства.

Первый элемент — всегда наибольший.

Элементы могут добавляться и удаляться в логарифмическое время.

Диапазон, исключая только что добавленный в конце элемент, должен быть кучей.

Сложность логарифмическая, требующая большинства log (last — first) сравнений.

Пример

prev_permutation

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

Параметры

Возвращаемое значение

Значение true , если лексикографически предыдущая перестановка существует и заменила исходный порядок в диапазоне; в противном случае — значение false , указывающее, что порядок преобразуется в лексикографически наибольшую перестановку.

Пример

push_heap

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

Параметры

first
Итератор произвольного доступа, обращающийся к позиции первого элемента в куче.

Пример

random_shuffle

Функция std::random_shuffle() является нерекомендуемой, заменена std::shuffle . Пример кода и дополнительные сведения см. в записи <random> Stack Overflow Why are std::random_shuffle methods are deprecated in C++14?.

remove

Устраняет указанное значение из заданного диапазона без нарушения порядка оставшихся элементов. Возвращает конец нового диапазона, свободного от указанного значения.

Параметры

exec
Используемая политика выполнения.

first
Прямой итератор, обращающийся к положению первого элемента в диапазоне, в котором удаляются элементы.

last
Прямой итератор, обращающийся к положению за последним элементом в диапазоне, в котором удаляются элементы.

value
Значение, которое необходимо удалить из диапазона.

Возвращаемое значение

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

Пример

remove_copy

Копирует элементы из исходного диапазона в диапазон назначения, за исключением того, что элементы указанного значения не копируются, не нарушая порядок оставшихся элементов. Возвращает конец нового диапазона назначения.

Параметры

exec
Используемая политика выполнения.

first
Входной итератор, указывающий на позицию первого элемента в диапазоне, в котором удаляются элементы.

last
Входной итератор, указывающий на позицию, следующую за последним элементом в диапазоне, в котором удаляются элементы.

result
Выходной итератор, указывающий на позицию первого элемента в диапазоне назначения, в который удаляются элементы.

value
Значение, которое необходимо удалить из диапазона.

Возвращаемое значение

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

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

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

Порядок неудаляемых элементов не меняется.

Сложность является линейной. Это делает ( last — first ) сравнения для равенства и не более ( last — first ) назначений.

Пример

remove_copy_if

Копирует элементы из исходного диапазона в диапазон назначения, за исключением элементов, удовлетворяющих предикату. Элементы копируются без нарушения порядка оставшихся элементов. Возвращает конец нового диапазона назначения.

Параметры

exec
Используемая политика выполнения.

first
Входной итератор, указывающий на позицию первого элемента в диапазоне, в котором удаляются элементы.

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

Возвращаемое значение

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

Пример

remove_if

Устраняет элементы, удовлетворяющие предикату из заданного диапазона, не нарушая порядок оставшихся элементов. Возвращает конец нового диапазона, свободного от указанного значения.

Параметры

exec
Используемая политика выполнения.

first
Прямой итератор, указывающий на позицию первого элемента в диапазоне, из которого удаляются элементы.

last
Прямой итератор, указывающий на позицию, следующую за последним элементом в диапазоне, из которого удаляются элементы.

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

Возвращаемое значение

Пример

replace

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

Параметры

exec
Используемая политика выполнения.

first
Прямой итератор, указывающий на позицию первого элемента в диапазоне, в котором заменяются элементы.

last
Прямой итератор, указывающий на позицию, следующую за последним элементом в диапазоне, в котором заменяются элементы.

oldVal
Старое значение заменяемых элементов.

newVal
Новое значение, присваиваемое элементам со старым значением.

Пример

replace_copy

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

Параметры

exec
Используемая политика выполнения.

first
Входной итератор, указывающий на позицию первого элемента в диапазоне, в котором заменяются элементы.

last
Входной итератор, указывающий на позицию, следующую за последним элементом в диапазоне, в котором заменяются элементы.

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

oldVal
Старое значение заменяемых элементов.

newVal
Новое значение, присваиваемое элементам со старым значением.

Возвращаемое значение

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

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

Порядок незаменяемых элементов не меняется.

Пример

replace_copy_if

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

Параметры

exec
Используемая политика выполнения.

first
Входной итератор, указывающий на позицию первого элемента в диапазоне, в котором заменяются элементы.

result
Выходной итератор, указывающий на позицию первого элемента в диапазоне назначения, в который копируются элементы.

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

value
Новое значение, присваиваемое элементам, старые значения которых удовлетворяют предикату.

Возвращаемое значение

Пример

replace_if

Проверяет каждый элемент в диапазоне и заменяет его, если он соответствует заданному предикату.

Параметры

exec
Используемая политика выполнения.

first
Прямой итератор, указывающий на позицию первого элемента в диапазоне, в котором заменяются элементы.

last
Итератор, указывающий на позицию, следующую за последним элементом в диапазоне, в котором заменяются элементы.

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

value
Новое значение, присваиваемое элементам, старые значения которых удовлетворяют предикату.

Пример

reverse

Изменяет порядок элементов в диапазоне на обратный.

Параметры

exec
Используемая политика выполнения.

first
Двунаправленный итератор, указывающий на позицию первого элемента в диапазоне, в котором переставляются элементы.

last
Двунаправленный итератор, указывающий на позицию, следующую за последним элементом в диапазоне, в котором переставляются элементы.

Пример

reverse_copy

Изменяет порядок элементов в исходном диапазоне на обратный, одновременно копируя их в диапазон назначения

Параметры

exec
Используемая политика выполнения.

first
Двунаправленный итератор, указывающий на позицию первого элемента в исходном диапазоне, в котором переставляются элементы.

last
Двунаправленный итератор, указывающий на позицию, следующую за последним элементом в исходном диапазоне, в котором переставляются элементы.

Возвращаемое значение

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

Пример

rotate

Меняет местами элементы в двух соседних диапазонах.

Параметры

exec
Используемая политика выполнения.

first
Прямой итератор, указывающий на позицию первого элемента в диапазоне для изменения места.

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

last
Прямой итератор, указывающий на позицию, следующую за последним элементом в диапазоне для изменения места.

Указанные диапазоны должны быть допустимыми. Все указатели должны поддерживать удаление ссылок, а последняя позиция в последовательности должна быть доступна из первой позиции за счет увеличения на один.

Сложность является линейной. Он делает не более ( last — first ) переключения.

Пример

rotate_copy

Меняет местами элементы в двух соседних диапазонах в пределах исходного диапазона и копирует результат в диапазон назначения.

Параметры

exec
Используемая политика выполнения.

first
Прямой итератор, указывающий на позицию первого элемента в диапазоне для изменения места.

result
Итератор вывода указывает на позицию первого элемента в диапазоне назначения.

Возвращаемое значение

Выходной итератор, указывающий на позицию, следующую за последним элементом в диапазоне назначения.

Пример

sample

search

Ищет первое вхождение последовательности в целевом диапазоне, элементы которого равны элементам в заданной последовательности элементов или элементы которых эквивалентны в некотором смысле, заданному двоичным предикатом элементам в данной последовательности.

Параметры

exec
Используемая политика выполнения.

first1
Прямой итератор, адресующий положение первого элемента в диапазоне для поиска.

last1
Прямой итератор, адресующий положение на единицу после последнего элемента в диапазоне для поиска.

first2
Прямой итератор, адресующий положение первого элемента в диапазоне для сравнения.

last2
Прямой итератор, адресующий положение на единицу после последнего элемента в диапазоне для сравнения.

searcher
Средство поиска, инкапсулирующее шаблон для поиска и используемый алгоритм поиска. Дополнительные сведения о поисковых системах см. в разделе default_searcher «Класс», boyer_moore_horspool_searcher «Класс» и boyer_moore_searcher «Класс».

Возвращаемое значение

Средняя сложность является линейной относительно размера поискового диапазона. Наихудшая сложность регистра также является линейной относительно размера искомой последовательности.

Пример

search_n

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

Параметры

exec
Используемая политика выполнения.

first1
Прямой итератор, адресующий положение первого элемента в диапазоне для поиска.

last1
Прямой итератор, адресующий положение на единицу после последнего элемента в диапазоне для поиска.

count
Размер искомой последовательности.

value
Значение элементов в искомой последовательности.

Возвращаемое значение

Пример

set_difference

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

Параметры

exec
Используемая политика выполнения.

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

last1
Входной итератор, указывающий на позицию, следующую за последним элементом в первом из двух упорядоченных исходных диапазонов, которые следует объединить и упорядочить в один диапазон, представляющий разность двух исходных диапазонов.

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

last2
Входной итератор, указывающий на позицию, следующую за последним элементом во втором из двух последовательных упорядоченных исходных диапазонов, которые следует объединить и упорядочить в один диапазон, представляющий разность двух исходных диапазонов.

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

pred
Определяемый пользователем объект функции предиката, задающий условие, когда один элемент меньше другого. Двоичный предикат принимает два аргумента и должен возвращать true , если первый элемент меньше второго и false в противном случае.

Возвращаемое значение

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

Каждый упорядоченный исходный диапазон должны быть упорядочен в качестве предусловия для применения алгоритма set_difference в соответствии с теми же правилами, чтобы использоваться алгоритмом для упорядочения объединенных диапазонов.

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

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

Сложность алгоритма является линейной с наибольшим 2 * ((last1 — first1) + (last2 — first2)) — 1 количеством сравнений для непустых исходных диапазонов.

Пример

set_intersection

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

Параметры

exec
Используемая политика выполнения.

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

last1
Входной итератор, указывающий на позицию, следующую за последним элементом в первом из двух упорядоченных исходных диапазонов, которые следует объединить и упорядочить в один диапазон, представляющий пересечение двух исходных диапазонов.

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

last2
Входной итератор, указывающий на позицию, следующую за последним элементом во втором из двух последовательных упорядоченных исходных диапазонов, которые следует объединить и упорядочить в один диапазон, представляющий пересечение двух исходных диапазонов.

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

Возвращаемое значение

Выходной итератор, указывающий на позицию, следующую за последним элементом в упорядоченном диапазоне назначения, представляющем пересечение двух исходных диапазонов.

Каждый упорядоченный исходный диапазон должен быть упорядочен в качестве предусловия для применения алгоритма merge в соответствии с тем же правилами, чтобы использоваться алгоритмом для упорядочения объединенных диапазонов.

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

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

Пример

set_symmetric_difference

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

Параметры

exec
Используемая политика выполнения.

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

last1
Входной итератор, указывающий на позицию, следующую за последним элементом в первом из двух упорядоченных исходных диапазонов, которые следует объединить и упорядочить в один диапазон, представляющий симметрическую разность двух исходных диапазонов.

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

last2
Входной итератор, указывающий на позицию, следующую за последним элементом во втором из двух последовательных упорядоченных исходных диапазонов, которые следует объединить и упорядочить в один диапазон, представляющий симметрическую разность двух исходных диапазонов.

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

Возвращаемое значение

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

Каждый упорядоченный исходный диапазон должны быть упорядочен в качестве предусловия для применения алгоритма merge* в соответствии с теми же правилами, чтобы использоваться алгоритмом для упорядочения объединенных диапазонов.

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

Пример

set_union

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

Параметры

exec
Используемая политика выполнения.

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

last1
Входной итератор, указывающий на позицию, следующую за последним элементом в первом из двух упорядоченных исходных диапазонов, которые следует объединить и упорядочить в один диапазон, представляющий объединение двух исходных диапазонов.

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

last2
Входной итератор, указывающий на позицию, следующую за последним элементом во втором из двух последовательных упорядоченных исходных диапазонов, которые следует объединить и упорядочить в один диапазон, представляющий объединение двух исходных диапазонов.

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

Возвращаемое значение

Выходной итератор, указывающий на позицию, следующую за последним элементом в упорядоченном диапазоне назначения, представляющем объединение двух исходных диапазонов.

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

Сложность алгоритма является линейной с наибольшим 2 * ((last1 — first1) + (last2 — first2)) — 1 количеством сравнений.

Пример

shuffle

Перемешивает (изменяет порядок) элементы в указанном диапазоне, используя генератор случайных чисел.

Параметры

first
Итератор первого элемента в диапазоне, который необходимо перемешать (инклюзивно). Должен соответствовать требованиям RandomAccessIterator и ValueSwappable .

last
Итератор последнего элемента в диапазоне, который необходимо перемешать (эксклюзивно). Должен соответствовать требованиям RandomAccessIterator и ValueSwappable .

gen
Генератор случайных чисел, который будет использовать функция shuffle() . Должен соответствовать требованиям UniformRandomNumberGenerator .

Параметры

exec
Используемая политика выполнения.

first
Итератор произвольного доступа, обращающийся к позиции первого элемента в сортируемом диапазоне.

last
Итератор произвольного доступа, обращающийся к позиции после последнего элемента в сортируемом диапазоне.

pred
Определяемый пользователем объект функции предиката, задающий критерий сравнения, который должен соблюдаться идущими подряд элементами при упорядочении. Этот бинарный предикат принимает два аргумента и возвращает значение true , если эти два аргумента упорядочены, или значение false в противном случае. Эта функция средства сравнения должна задать строгое слабое упорядочение пар элементов последовательности. Дополнительные сведения см. в разделе Алгоритмы.

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

Средняя сложность сортировки — O( N log N ) n = last — first .

Пример

sort_heap

Преобразует кучу в упорядоченный диапазон.

Параметры

first
Итератор произвольного доступа, обращающийся к позиции первого элемента в целевой куче.

last
Итератор произвольного доступа, обращающийся к позиции, следующей за последним элементом в целевой куче.

Пример

stable_partition

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

Параметры

exec
Используемая политика выполнения.

first
Двунаправленный итератор адресует позицию первого элемента в разделяемом диапазоне.

Возвращаемое значение

Элементы a и b эквивалентны, но не обязательно равны, если оба pred( a, b ) значения имеют значение false и pred( b, a ) false, где pred указан предикат, заданный параметром. Алгоритм stable_partition является стабильным и гарантирует сохранение относительного порядка эквивалентных элементов. Алгоритм partition не обязательно сохраняет исходное упорядочение.

Пример

stable_sort

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

Параметры

exec
Используемая политика выполнения.

first
Двунаправленный итератор указывает позицию первого элемента в диапазоне для сортировки.

last
Двунаправленный итератор указывает позицию, следующую за последним элементом в диапазоне для сортировки.

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

Сложность stable_sort времени выполнения зависит от объема доступной памяти, но лучше всего (учитывая достаточную память) O(N log N) и худшим случаем является = last O(N (log N)^2) — first N. Как правило, sort алгоритм быстрее stable_sort .

Пример

Первое переопределение меняет местами значения двух объектов. Второе переопределение меняет местами значения двух массивов объектов.

Параметры

left
Для первого переопределения — первый объект для обмена его содержимого. Для второго переопределения — первый массив для обмена его содержимого.

right
Для первого переопределения — второй объект для обмена его содержимого. Для второго переопределения — второй массив для обмена его содержимого.

Пример

swap_ranges

Меняет местами элементы одного диапазона с элементами другого диапазона такого же размера.

Параметры

exec
Используемая политика выполнения.

first1
Прямой итератор, указывающий первую позицию первого диапазона элементов для обмена.

last1
Прямой итератор, указывающий позицию, следующую за последней позицией первого диапазона элементов для обмена.

first2
Прямой итератор, указывающий первую позицию второго диапазона элементов для обмена.

Возвращаемое значение

Прямой итератор, указывающий позицию, следующую за последней позицией второго диапазона элементов для обмена.

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

Сложность линейной с выполненными переключениями last1 — first1 . Если переставляются элементы из контейнеров одного и того же типа, то должна использоваться функция-член swap из этого контейнера, так как функция-член обычно имеет постоянную сложность.

Пример

transform

Применяет указанный объект функции к каждому элементу в исходном диапазоне или к паре элементов из двух исходных диапазонов. Затем он копирует возвращаемые значения объекта функции в диапазон назначения.

Параметры

exec
Используемая политика выполнения.

first1
Входной итератор, адресующий положение первого элемента в первом исходном диапазоне для работы.

last1
Входной итератор, адресующий позицию, расположенную за последним элементом в первом исходном диапазоне для работы.

first2
Входной итератор, адресующий положение первого элемента во втором исходном диапазоне для работы.

result
Итератор вывода указывает на позицию первого элемента в диапазоне назначения.

func
Определяемый пользователем объект унарной функции, используемый в первой версии алгоритма для применения к каждому элементу в первом исходном диапазоне или определяемом пользователем двоичному объекту-функции, используемому во второй версии алгоритма, применяемого по парной стрелке в порядке переадресации к двум исходным диапазонам.

Возвращаемое значение

Итератор вывода указывает на позицию после последнего элемента в диапазоне назначения, который получает выходные элементы, преобразованные объектом функции.

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

Если результат равен first1 первой версии алгоритма, исходные и целевые диапазоны будут одинаковыми, а последовательность будет изменена. result Но не может адресировать позицию в диапазоне [ first1 + 1, last1 ).

Сложность является линейной. Это делает не более ( last1 — first1 ) сравнения.

Пример

unique

Удаляет повторяющиеся элементы, которые находятся рядом друг с другом в указанном диапазоне.

Параметры

exec
Используемая политика выполнения.

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

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

Возвращаемое значение

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

Указанный диапазон должен быть допустимым. Все указатели должны поддерживать удаление ссылок, а последняя позиция в последовательности должна быть доступна из первой позиции за счет увеличения на один. Количество элементов в последовательности не изменяется алгоритмом unique , а элементы за пределами измененной последовательности разыменовываются, но не указаны.

Сложность является линейной, требующей (last — first) — 1 сравнения.

В классе list имеется более эффективная функция-член unique, которая может работать лучше.

Эти алгоритмы нельзя использовать в ассоциативном контейнере.

Пример

unique_copy

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

Параметры

exec
Используемая политика выполнения.

first
Прямой итератор, указывающий на позицию первого элемента в исходном диапазоне для копирования.

last
Прямой итератор, указывающий на позицию, следующую за последним элементом в исходном диапазоне для копирования.

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

Возвращаемое значение

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

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

Сложность является линейной, требующей ( last — first ) сравнения.

Пример

upper_bound

Находит позицию первого элемента в упорядоченном диапазоне со значением, превышающим указанное значение. Двоичный предикат указывает критерий упорядочения.

Параметры

first
Позиция первого элемента в диапазоне для поиска.

last
Позиция, следующая за последним элементом в диапазоне для поиска.

value
Значение в упорядоченном диапазоне, которое должно превышаться значением элемента, указанного возвращенным итератором.

pred
Определяемый пользователем объект функции предиката сравнения, определяющий смысл, в котором один элемент меньше другого. Предикат сравнения принимает два аргумента и возвращается true при удовлетворении и false в случае, если он не удовлетворяется.

Возвращаемое значение

Прямой итератор, указывающий позицию первого элемента со значением, превышающим указанное значение.

MIN and MAX in C

Where are MIN and MAX defined in C, if at all?

What is the best way to implement these, as generically and type safe as possible (compiler extensions/builtins for mainstream compilers preferred).

As functions. I wouldn’t use macros like #define MIN(X, Y) (((X) < (Y)) ? (X) : (Y)) , especially if you plan to deploy your code. Either write your own, use something like standard fmax or fmin , or fix the macro using GCC’s typeof (you get typesafety bonus too) in a GCC statement expression:

Everyone says «oh I know about double evaluation, it’s no problem» and a few months down the road, you’ll be debugging the silliest problems for hours on end.

Note the use of __typeof__ instead of typeof :

If you are writing a header file that must work when included in ISO C programs, write __typeof__ instead of typeof .

It’s also provided in the GNU libc (Linux) and FreeBSD versions of sys/param.h , and has the definition provided by dreamlax.

The source repositories are here:

There’s a std::min and std::max in C++, but AFAIK, there’s no equivalent in the C standard library. You can define them yourself with macros like

But this causes problems if you write something like MAX(++a, ++b) .

Avoid non-standard compiler extensions and implement it as a completely type-safe macro in pure standard C (ISO 9899:2011).

Solution

Usage

Explanation

The macro MAX creates another macro based on the type parameter. This control macro, if implemented for the given type, is used to check that both parameters are of the correct type. If the type is not supported, there will be a compiler error.

If either x or y is not of the correct type, there will be a compiler error in the ENSURE_ macros. More such macros can be added if more types are supported. I’ve assumed that only arithmetic types (integers, floats, pointers etc) will be used and not structs or arrays etc.

If all types are correct, the GENERIC_MAX macro will be called. Extra parenthesis are needed around each macro parameter, as the usual standard precaution when writing C macros.

Then there’s the usual problems with implicit type promotions in C. The ?: operator balances the 2nd and 3rd operand against each other. For example, the result of GENERIC_MAX(my_char1, my_char2) would be an int . To prevent the macro from doing such potentially dangerous type promotions, a final type cast to the intended type was used.

Rationale

We want both parameters to the macro to be of the same type. If one of them is of a different type, the macro is no longer type safe, because an operator like ?: will yield implicit type promotions. And because it does, we also always need to cast the final result back to the intended type as explained above.

A macro with just one parameter could have been written in a much simpler way. But with 2 or more parameters, there is a need to include an extra type parameter. Because something like this is unfortunately impossible:

The problem is that if the above macro is called as MAX(1, 2) with two int , it will still try to macro-expand all possible scenarios of the _Generic association list. So the ENSURE_float macro will get expanded too, even though it isn’t relevant for int . And since that macro intentionally only contains the float type, the code won’t compile.

To solve this, I created the macro name during the pre-processor phase instead, with the ## operator, so that no macro gets accidentally expanded.

Examples

@David Titarenco nailed it here, but let me at least clean it up a bit to make it look nice, and show both min() and max() together to make copying and pasting from here easier. 🙂

Update 25 Apr. 2020: I’ve also added a Section 3 to show how this would be done with C++ templates too, as a valuable comparison for those learning both C and C++, or transitioning from one to the other. I’ve done my best to be thorough and factual and correct to make this answer a canonical reference I can come back to again and again, and I hope you find it as useful as I do.

1. The old C macro way:

This technique is commonly used, well-respected by those who know how to use it properly, the "de facto" way of doing things, and fine to use if used properly, but buggy (think: double-evaluation side effect) if you ever pass expressions including variable assignment in to compare:

2. The new and improved gcc "statement expression" way:

This technique avoids the above "double-evaluation" side effects and bugs, and is therefore considered the superior, safer, and "more modern" GCC C way to do this. Expect it to work with both the gcc and clang compilers, since clang is, by design, gcc-compatible (see the clang note at the bottom of this answer).

BUT: DO watch out for "variable shadowing" effects still, as statement expressions are apparently inlined and therefore do NOT have their own local variable scope!

Note that in gcc statement expressions, the last expression in the code block is what is "returned" from the expression, as though it was returned from a function. GCC’s documentation says it this way:

The last thing in the compound statement should be an expression followed by a semicolon; the value of this subexpression serves as the value of the entire construct. (If you use some other kind of statement last within the braces, the construct has type void, and thus effectively no value.)

3. [C++ only] The C++ template way:

C++ Note: if using C++, templates are probably recommended for this type of construct instead, but I personally dislike templates and would probably use one of the above constructs in C++ anyway, as I frequently use and prefer C styles in embedded C++ as well.

This section added 25 Apr. 2020:

I’ve been doing a ton of C++ the past few months, and the pressure to prefer templates over macros, where able, in the C++ community is quite strong. As a result, I’ve been getting better at using templates, and want to put in the C++ template versions here for completeness and to make this a more canonical and thorough answer.

Here’s what basic function template versions of max() and min() might look like in C++:

Do additional reading about C++ templates here: Wikipedia: Template (C++).

However, both max() and min() are already part of the C++ standard library, in the <algorithm> header ( #include <algorithm> ). In the C++ standard library they are defined slightly differently than I have them above. The default prototypes for std::max<>() and std::min<>() , for instance, in C++14, looking at their prototypes in the cplusplus.com links just above, are:

Note that the keyword typename is an alias to class (so their usage is identical whether you say <typename T> or <class T> ), since it was later acknowledged after the invention of C++ templates, that the template type might be a regular type ( int , float , etc.) instead of only a class type.

Here you can see that both of the input types, as well as the return type, are const T& , which means "constant reference to type T ". This means the input parameters and return value are passed by reference instead of passed by value. This is like passing by pointers, and is more efficient for large types, such as class objects. The constexpr part of the function modifies the function itself and indicates that the function must be capable of being evaluated at compile-time (at least if provided constexpr input parameters), but if it cannot be evaluated at compile-time, then it defaults back to a run-time evaluation, like any other normal function.

The compile-time aspect of a constexpr C++ function makes it kind-of C-macro-like, in that if compile-time evaluation is possible for a constexpr function, it will be done at compile-time, same as a MIN() or MAX() macro substitution could possibly be fully evaluated at compile-time in C or C++ too. For additional references for this C++ template info, see below.

4. [C++ only] C++ std::max()

If using C++, I’d like to add that the built-in std::max() function in the <algorithm> header file has a variety of forms. See the "Possible implementation" section on the documentation page at the cppreference.com community wiki (https://en.cppreference.com/w/cpp/algorithm/max) for 4 possible implementations for the 4 forms of std::max() .

Normal usages include:

. but if you’d like to compare many numbers at once, you can use the 4th form, which accepts a std::initializer_list<T> , like this:

References:

Clang note from Wikipedia:

[Clang] is designed to act as a drop-in replacement for the GNU Compiler Collection (GCC), supporting most of its compilation flags and unofficial language extensions.

C++ std::vector Find max and min Element and Respective Index in a Vector

To find the largest or smallest element stored in a vector, you can use the methods std::max_element and std::min_element , respectively. These methods are defined in <algorithm> header. If several elements are equivalent to the greatest (smallest) element, the methods return the iterator to the first such element. Return v.end() for empty vectors.

maxElementIndex:3, maxElement:10
minElementIndex:1, minElement:2

The minimum and maximum element in a vector can be retrieved at the same time by using the method std::minmax_element , which is also defined in <algorithm> header:

Min c какая библиотека

Функции <algorithm>

Параметры

Возвращаемое значение

Комментарии

Пример

all_of

Параметры

Возвращаемое значение

Комментарии

Пример

any_of

Параметры

Возвращаемое значение

Комментарии

Пример

binary_search

Параметры

Возвращаемое значение

Комментарии

Пример

clamp

Параметры

Возвращаемое значение

Комментарии

Параметры

Возвращаемое значение

Комментарии

Пример

copy_backward

Параметры

Возвращаемое значение

Комментарии

Пример

copy_if

Параметры

Возвращаемое значение

Комментарии

Пример

copy_n

Параметры

Возвращаемое значение

Комментарии

Пример

count

Параметры

Возвращаемое значение

Комментарии

Пример

count_if

Параметры

Возвращаемое значение

Комментарии

Пример

equal

Параметры

Возвращаемое значение

Комментарии

Пример

equal_range

Параметры

Возвращаемое значение

Комментарии

Пример

Параметры

Комментарии

Пример

fill_n

Параметры

Возвращаемое значение

Комментарии

Пример

Параметры

Возвращаемое значение

Комментарии

find_end

Параметры

Возвращаемое значение

Комментарии

Пример