std::merge
| Определено в заголовочном файле <algorithm>
|
||
| (1) | ||
template< class InputIt1, class InputIt2, class OutputIt > OutputIt merge( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first ); |
(до C++20) | |
template< class InputIt1, class InputIt2, class OutputIt > constexpr OutputIt merge( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first ); |
(начиная с C++20) | |
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class ForwardIt3 > ForwardIt3 merge( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, ForwardIt3 d_first ); |
(2) | (начиная с C++17) |
| (3) | ||
template< class InputIt1, class InputIt2, class OutputIt, class Compare> OutputIt merge( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp ); |
(до C++20) | |
template< class InputIt1, class InputIt2, class OutputIt, class Compare> constexpr OutputIt merge( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp ); |
(начиная с C++20) | |
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class ForwardIt3, class Compare> ForwardIt3 merge( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, ForwardIt3 d_first, Compare comp ); |
(4) | (начиная с C++17) |
Объединяет два отсортированных диапазона [first1, last1) и [first2, last2), записывая элементы в новый диапазон начиная с d_first. На выходе получается диапазон [d_first, d_last), где d_last совпадает с d_first + (last1 - first1) + (last2 - first2). Новый диапазон удовлетворяет условиям std::is_sorted(d_first, d_last) и std::is_sorted(d_first, d_last, comp), соответственно.
О диапазоне можно говорить как об отсортированном в соответствии с функцией сравнения comp, если для каждого итератора it, указывающего на элемент последовательности, и любого неотрицательного целого числа n, такого, что it + n - это валидный итератор, указывающий на элемент последовательности, значение comp(*(it + n), *it) будет равно false.
operator<.comp.policy. std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> имеет значение true std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> is true Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.
Эта функция объединения является "устойчивой" (stable), то есть обеспечивает на выходе такое расположение элементов из обоих исходных множеств, что элементы первого исходного множества предшествуют эквивалентным элементам из второго. Относительный порядок элементов сохраняется.
Поведение не определено если выходной диапазон пересекается с любым из входных диапазонов (входные диапазоны могут пересекаться).
Параметры
| first1, last1 | — | первый диапазон элементов для объединения |
| first2, last2 | — | второй диапазон элементов для объединения |
| d_first | — | начало выходного диапазона |
| policy | — | политика исполнения, которую следует использовать (см. execution policy) |
| comp | — | объект функции сравнения (т.е. объект, удовлетворяющий требованиям Compare), который возвращает true, если первый аргумент "меньше", чем второй.Определение сравнения должно быть эквивалентно:
Использование |
| Требования к типам | ||
-InputIt1, InputIt2 должен соответствовать требованиям InputIterator.
| ||
-ForwardIt1, ForwardIt2, ForwardIt3 должен соответствовать требованиям ForwardIterator.
| ||
-OutputIt должен соответствовать требованиям OutputIterator.
| ||
Возвращаемое значение
OutputIt, указывающий на позицию вслед за последним скопированным элементом.
Сложность
std::distance(first1, last1) + std::distance(first2, last2) - 1 сравнений.O(std::distance(first1, last1) + std::distance(first2, last2))Исключения
Перегрузки с параметром шаблона по имени ExecutionPolicy сообщают об ошибках следующим образом:
- Если выполнение функции, вызванной как часть алгоритма, вызывает исключение и
ExecutionPolicyявляется одной из стандартных политик, вызывается std::terminate. Для любой другойExecutionPolicyповедение определяется реализацией. - Если алгоритму не удаётся выделить память, генерируется std::bad_alloc.
Примечания
Работа данного алгоритма схожа с работой std::set_union: оба алгоритма принимают на вход два отсортированных диапазона, и формируют на выходе отсортированный диапазон из элементов обоих входных. Разница между ними в том, как они работают с элементами, оцениваемыми как эквивалентные при сравнении (см. LessThanComparable). Если любые эквивалентные значения появляются n раз в первом множестве, и m раз во втором, std::merge выдаст на выходе все n+m элементов, в отличие от std::set_union, который оставит максимум std::max(n, m). То есть std::merge оставляет ровно std::distance(first1, last1) + std::distance(first2, last2) элементов, а std::set_union может оставить меньше.
Возможная реализация
См. так же реализации в libstdc++ и libc++.
| Первый вариант |
|---|
template<class InputIt1, class InputIt2, class OutputIt>
OutputIt merge(InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
OutputIt d_first)
{
for (; first1 != last1; ++d_first) {
if (first2 == last2) {
return std::copy(first1, last1, d_first);
}
if (*first2 < *first1) {
*d_first = *first2;
++first2;
} else {
*d_first = *first1;
++first1;
}
}
return std::copy(first2, last2, d_first);
}
|
| Второй вариант |
template<class InputIt1, class InputIt2,
class OutputIt, class Compare>
OutputIt merge(InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
OutputIt d_first, Compare comp)
{
for (; first1 != last1; ++d_first) {
if (first2 == last2) {
return std::copy(first1, last1, d_first);
}
if (comp(*first2, *first1)) {
*d_first = *first2;
++first2;
} else {
*d_first = *first1;
++first1;
}
}
return std::copy(first2, last2, d_first);
}
|
Example
#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <random>
#include <functional>
int main()
{
// заполнить вектора случайными числами
std::random_device rd;
std::mt19937 mt(rd());
std::uniform_int_distribution<> dis(0, 9);
std::vector<int> v1(10), v2(10);
std::generate(v1.begin(), v1.end(), std::bind(dis, std::ref(mt)));
std::generate(v2.begin(), v2.end(), std::bind(dis, std::ref(mt)));
// отсортировать
std::sort(v1.begin(), v1.end());
std::sort(v2.begin(), v2.end());
// вывести v1
std::cout << "v1 : ";
std::copy(v1.begin(), v1.end(), std::ostream_iterator<int>(std::cout, " "));
std::cout << '\n';
// вывести v2
std::cout << "v2 : ";
std::copy(v2.begin(), v2.end(), std::ostream_iterator<int>(std::cout, " "));
std::cout << '\n';
// объединить
std::vector<int> dst;
std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(dst));
// вывести результат объединения
std::cout << "dst: ";
std::copy(dst.begin(), dst.end(), std::ostream_iterator<int>(std::cout, " "));
std::cout << '\n';
}
Возможный вывод:
v1 : 0 1 3 4 4 5 5 8 8 9
v2 : 0 2 2 3 6 6 8 8 8 9
dst: 0 0 1 2 2 3 3 4 4 5 5 6 6 8 8 8 8 8 9 9
See also
| объединяет два упорядоченных диапазона на месте (шаблон функции) | |
(C++11) |
проверяет, отсортирован ли диапазон по возрастанию (шаблон функции) |
| вычисляет объединение двух множеств (шаблон функции) | |
| сортирует диапазон в порядке возрастания (шаблон функции) | |
| сортирует диапазон элементов, сохраняя порядок между равными элементами (шаблон функции) |
