std::set_union

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

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

template< class ExecutionPolicy, class ForwardIt1,
          class ForwardIt2, class ForwardIt3 >
ForwardIt3 set_union( ExecutionPolicy&& policy,
                      ForwardIt1 first1, ForwardIt1 last1,
                      ForwardIt2 first2, ForwardIt2 last2, ForwardIt3 d_first );

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

template< class InputIt1, class InputIt2, class OutputIt, class Compare >
constexpr OutputIt set_union( 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 set_union( ExecutionPolicy&& policy,
                      ForwardIt1 first1, ForwardIt1 last1,
                      ForwardIt2 first2, ForwardIt2 last2,
                      ForwardIt3 d_first, Compare comp );

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

Если [first1, last1) содержит m элементов, которые эквивалентны друг другу, и [first2, last2) содержит n элементов, эквивалентных им, то все m элементы будут скопированы из [first1, last1) в выходной диапазон, сохраняя порядок, а затем конечные std::max(n - m, 0) элементы будут скопированы из [first2, last2) в выходной диапазон, также сохраняя порядок.

Если любой из входных диапазонов не отсортирован (используя operator< или comp соответственно) или перекрывается с выходным диапазоном, поведение является неопределённым.

Параметры

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

Итератор, прошедший конец сконструированного диапазона.

Сложность

Учитывая M и N как std::distance(first1, last1) и std::distance(first2, last2) соответственно:

Исключения

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

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

Примечания

Этот алгоритм выполняет задачу, аналогичную той, которую выполняет std::merge. Оба потребляют два отсортированных входных диапазона и генерируют отсортированный выходной диапазон с элементами из обоих входных диапазонов. Разница между этими двумя алгоритмами заключается в обработке значений из обоих входных диапазонов, которые сравниваются как эквивалентные (см. примечания в 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 может генерировать меньше.

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

template<class InputIt1, class InputIt2, class OutputIt>
OutputIt set_union(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++;
        else
        {
            *d_first = *first1;
            if (!(*first1 < *first2))
                ++first2;
            ++first1;
        }
    }
    return std::copy(first2, last2, d_first);
}

template<class InputIt1, class InputIt2, class OutputIt, class Compare>
OutputIt set_union(InputIt1 first1, InputIt1 last1,
                   InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp)
{
    for (; first1 != last1; ++d_first)
    {
        if (first2 == last2)
            // Finished range 2, include the rest of range 1:
            return std::copy(first1, last1, d_first);
 
        if (comp(*first2, *first1))
            *d_first = *first2++;
        else
        {
            *d_first = *first1;
            if (!comp(*first1, *first2)) // Equivalent => don't need to include *first2.
                ++first2;
            ++first1;
        }
    }
    // Finished range 1, include the rest of range 2:
    return std::copy(first2, last2, d_first);
}

Пример

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
 
void println(std::vector<int> const& v)
{
    for (int i : v)
        std::cout << i << ' ';
    std::cout << '\n';
}
 
int main()
{
    std::vector<int> v1, v2, dest;
 
    v1 = {1, 2, 3, 4, 5};
    v2 = {3, 4, 5, 6, 7};
 
    std::set_union(v1.cbegin(), v1.cend(),
                   v2.cbegin(), v2.cend(),
                   std::back_inserter(dest));
    println(dest);
 
    dest.clear();
 
    v1 = {1, 2, 3, 4, 5, 5, 5};
    v2 = {3, 4, 5, 6, 7};
 
    std::set_union(v1.cbegin(), v1.cend(),
                   v2.cbegin(), v2.cend(),
                   std::back_inserter(dest));
    println(dest);
}

1 2 3 4 5 6 7 
1 2 3 4 5 5 5 6 7

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

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

См. также