std::merge

template< class InputIt1, class InputIt2, class OutputIt >
OutputIt merge( InputIt1 first1, InputIt1 last1,
                InputIt2 first2, InputIt2 last2,
                OutputIt d_first );

template< class ExecutionPolicy,
          class ForwardIt1, class ForwardIt2, class ForwardIt3 >
ForwardIt3 merge( ExecutionPolicy&& policy,
                  ForwardIt1 first1, ForwardIt1 last1,
                  ForwardIt2 first2, ForwardIt2 last2,
                  ForwardIt3 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 );

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 );

Объединяет два отсортированных диапазона [first1, last1) и [first2, last2) в один отсортированный диапазон, начинающийся с d_first.

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

Если выходной диапазон перекрывается с [first1, last1) или [first2, last2), поведение не определено.

Параметры

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

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

Сложность

Пусть \(\scriptsize N_1\)N₁ — это std::distance(first1, last1), а \(\scriptsize N_2\)N₂ — это std::distance(first2, last2):

Исключения

Перегрузки с параметром шаблона с именем ExecutionPolicy сообщают об ошибках следующим образом:

• Если выполнение функции, вызванной в рамках алгоритма, выбрасывает исключение и ExecutionPolicy является одной из стандартных политик, вызывается std::terminate. Для любого другого ExecutionPolicy поведение определяется реализацией.
• Если алгоритму не удаётся выделить память, выбрасывается std::bad_alloc.

Возможная реализация

См. также реализации в 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);
}

Примечания

Этот алгоритм выполняет задачу, похожую на задачу 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 может вывести меньше.

Пример

#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <random>
#include <vector>

auto print = [](const auto rem, const auto& v)
{
    std::cout << rem;
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
};

int main()
{
    // fill the vectors with random numbers
    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)));
    
    print("Originally:\nv1: ", v1);
    print("v2: ", v2);
    
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());
    
    print("After sorting:\nv1: ", v1);
    print("v2: ", v2);
    
    // merge
    std::vector<int> dst;
    std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(dst));
    
    print("After merging:\ndst: ", dst);
}

Originally:
v1: 2 6 5 7 4 2 2 6 7 0
v2: 8 3 2 5 0 1 9 6 5 0
After sorting:
v1: 0 2 2 2 4 5 6 6 7 7
v2: 0 0 1 2 3 5 5 6 8 9
After merging:
dst: 0 0 0 1 2 2 2 2 3 4 5 5 5 6 6 6 7 7 8 9

Отчёты об ошибках

Следующие отчёты об ошибках, изменяющие поведение, были применены задним числом к ранее опубликованным стандартам C++.

См. также