Пространства имён
Варианты
Действия

set_union

Материал из cppreference.com
< cpp‎ | algorithm

 
 
Библиотека алгоритмов
Ограниченные алгоритмы и алгоритмы над диапазонами (C++20)
Ограниченные алгоритмы, например ranges::copy, ranges::sort, ...
Политики исполнения (C++17)
Немодифицирующие операции над последовательностями
(C++11)(C++11)(C++11)
(C++17)
Модифицирующие операции над последовательностями
Операции разбиения
Операции сортировки
(C++11)
Операции двоичного поиска
Операции с наборами (в отсортированных диапазонах)
Операции с кучей
(C++11)
Операций минимума/максимума
(C++11)
(C++17)

Операции перестановки
Числовые операции
Операции с неинициализированной памятью
(C++17)
(C++17)
(C++17)
Библиотека C
 
Определено в заголовочном файле <algorithm>
template< class InputIt1, class InputIt2, class OutputIt >

OutputIt set_union( InputIt1 first1, InputIt1 last1,
                    InputIt2 first2, InputIt2 last2,

                    OutputIt d_first );
(1)
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 );
(2)
Создает отсортированный диапазон начало в d_first, состоящий из всех элементов, присутствующих в одном или обоих диапазонах отсортированы [first1, last1) и [first2, last2). Первая версия ожидает, что обе входные диапазоны должны быть отсортированы с operator<, вторая версия ожидает, что они должны быть отсортированы с данной comp функцию сравнения. Если некоторый элемент не найден m раз в [first1, last1) и n раз в [first2, last2), то все m элементы будут скопированы из [first1, last1) в d_first, сохраняя порядок, и тогда точно std::max(n-m, 0) элементы будут скопированы из [first2, last2) в d_first, а также сохранение порядка. В результате диапазон не должен пересекаться с любым из входных диапазонов.
Оригинал:
Constructs a sorted range beginning at d_first consisting of all elements present in one or both sorted ranges [first1, last1) and [first2, last2). The first version expects both input ranges to be sorted with operator<, the second version expects them to be sorted with the given comparison function comp. If some element is found m times in [first1, last1) and n times in [first2, last2), then all m elements will be copied from [first1, last1) to d_first, preserving order, and then exactly std::max(n-m, 0) elements will be copied from [first2, last2) to d_first, also preserving order. The resulting range cannot overlap with either of the input ranges.
Текст был переведён автоматически используя Переводчик Google.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.

Содержание

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

first1, last1
Первый вход отсортированный диапазон
Оригинал:
the first input sorted range
Текст был переведён автоматически используя Переводчик Google.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.
first2, last2
Второй вход отсортированный диапазон
Оригинал:
the second input sorted range
Текст был переведён автоматически используя Переводчик Google.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.
comp функция сравнения, возвращающая ​true если первый аргумент меньше второго.

Сигнатура функции сравнения должна быть эквивалентна следующей:

 bool cmp(const Type1 &a, const Type2 &b);

Сигнатура на обязана содержать const &, однако, функция не может изменять переданные объекты.
Типы Type1 и Type2 должны быть таковы, что объекты типов InputIt1 и InputIt2 могут быть разыменованы и затем неявно преобразованы в Type1 и Type2 соответственно. ​

Требования к типам
-
InputIt1 должен соответствовать требованиям InputIterator.
-
InputIt2 должен соответствовать требованиям InputIterator.
-
OutputIt должен соответствовать требованиям OutputIterator.

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

Iterator в конце прошлого построен диапазон.
Оригинал:
Iterator past the end of the constructed range.
Текст был переведён автоматически используя Переводчик Google.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.

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

В большинстве сравнений 2·(N1+N2-1), где N1 = std::distance(first1, last1) и N2 = std::distance(first2, last2).
Оригинал:
At most 2·(N1+N2-1) comparisons, where N1 = std::distance(first1, last1) and N2 = std::distance(first2, last2).
Текст был переведён автоматически используя Переводчик Google.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.

[править] Возможная реализация

Первый вариант
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)
            return std::copy(first1, last1, d_first);
        if (comp(*first2, *first1)) {
            *d_first = *first2++;
        } else {
            *d_first = *first1;
            if (!comp(*first1, *first2))
                ++first2;
            ++first1;
        }
    }
    return std::copy(first2, last2, d_first);
}

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

[править] См. также

возвращает true, если одна последовательность является подпоследовательностью другой
(шаблон функции) [править]
вычисляет разницу между двумя наборами
(шаблон функции) [править]
вычисляет пересечение двух множеств
(шаблон функции) [править]
вычисляет симметричную разницу между двумя наборами
(шаблон функции) [править]