std:: set_union

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

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

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

Параметры

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

Итератор за концом построенного диапазона.

Сложность

Пусть \(\scriptsize N_1\) N 1 равно std:: distance ( first1, last1 ) и \(\scriptsize N_2\) N 2 равно std:: distance ( first2, last2 ) :

Исключения

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

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

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

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)
            // Завершен диапазон 2, включаем оставшуюся часть диапазона 1:
            return std::copy(first1, last1, d_first);
        if (comp(*first2, *first1))
            *d_first = *first2++;
        else
        {
            *d_first = *first1;
            if (!comp(*first1, *first2)) // Эквивалентны => не нужно включать *first2.
                ++first2;
            ++first1;
        }
    }
    // Завершен диапазон 1, включаем оставшуюся часть диапазона 2:
    return std::copy(first2, last2, d_first);
}

Примечания

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

Пример

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
void println(const std::vector<int>& 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++.

Смотрите также