std::merge

Объединяет два отсортированных диапазона [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.

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

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

[править] Параметры

[править] Возвращаемое значение

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

[править] Сложность

[править] Исключения

Перегрузки с параметром шаблона по имени 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