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

std::set_union

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

 
 
Алгоритмы
Функции
Немодифицирующие линейные операции
Модифицирующие линейные операции
Разделение
Сортировка (на отсортированных промежутках)
Бинарный поиск (на отсортированных промежутках)
Множества (на отсортированных промежутках)
Куча
Минимум/максимум
Числовые операции
Библиотека 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 Translate.
Вы можете проверить и исправить перевод. Для инструкций кликните сюда.

Содержание

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

first1, last1 -
Первый вход отсортированный диапазон
Оригинал:
the first input sorted range
Текст был переведён автоматически через Google Translate.
Вы можете проверить и исправить перевод. Для инструкций кликните сюда.
first2, last2 -
Второй вход отсортированный диапазон
Оригинал:
the second input sorted range
Текст был переведён автоматически через Google Translate.
Вы можете проверить и исправить перевод. Для инструкций кликните сюда.
comp - comparison function which returns ​true if the first argument is less than the second.

The signature of the comparison function should be equivalent to the following:

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

The signature does not need to have const &, but the function must not modify the objects passed to it.
Типы Type1 и Type2 должны быть таковы, что объекты типов InputIt1 и InputIt2 могут быть разыменованы и затем неявно преобразованы в Type1 и Type2 соответственно. ​

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

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

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

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

В большинстве сравнений 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 Translate.
Вы можете проверить и исправить перевод. Для инструкций кликните сюда.

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

Первый вариант
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);
}

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

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

возвращает истину, если один набор является подмножеством другого
Оригинал:
returns true if one set is a subset of another
Текст был переведён автоматически через Google Translate.
Вы можете проверить и исправить перевод. Для инструкций кликните сюда.

(шаблон функции) [edit]
вычисляет разницу между двумя наборами
Оригинал:
computes the difference between two sets
Текст был переведён автоматически через Google Translate.
Вы можете проверить и исправить перевод. Для инструкций кликните сюда.

(шаблон функции) [edit]
вычисляет пересечение двух множеств
Оригинал:
computes the intersection of two sets
Текст был переведён автоматически через Google Translate.
Вы можете проверить и исправить перевод. Для инструкций кликните сюда.

(шаблон функции) [edit]
вычисляет симметрическая разность между двумя наборами
Оригинал:
computes the symmetric difference between two sets
Текст был переведён автоматически через Google Translate.
Вы можете проверить и исправить перевод. Для инструкций кликните сюда.

(шаблон функции) [edit]