std::set_symmetric_difference

Определено в заголовочном файле `<algorithm>`
	(1)
template< class InputIt1, class InputIt2, class OutputIt > OutputIt set_symmetric_difference( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first );		(до C++20)
template< class InputIt1, class InputIt2, class OutputIt > constexpr OutputIt set_symmetric_difference( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first );		(с C++20)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class ForwardIt3 > ForwardIt3 set_symmetric_difference( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, ForwardIt3 d_first );	(2)	(с C++17)
	(3)
template< class InputIt1, class InputIt2, class OutputIt, class Compare > OutputIt set_symmetric_difference( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp );		(до C++20)
template< class InputIt1, class InputIt2, class OutputIt, class Compare > constexpr OutputIt set_symmetric_difference( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp );		(с C++20)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class ForwardIt3, class Compare > ForwardIt3 set_symmetric_difference( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, ForwardIt3 d_first, Compare comp );	(4)	(с C++17)

Вычисляет симметрическую разность двух отсортированных диапазонов: элементы, которые находятся в любом из диапазонов, но не в обоих, копируются в диапазон, начинающийся с d_first. Диапазон вывода также отсортирован.

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

если m > n, то конечные m - n этих элементов из [first1, last1).
если m < n, то конечные n - m этих элементов из [first2, last2).

1) Элементы сравниваются с использованием operator< и диапазоны должны быть отсортированы по отношению к этому.

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

2,4) То же, что и (1,3), но выполняется согласно policy. Эти перегрузки не участвуют в разрешении перегрузки, если

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>` является `true`.	(до C++20)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>` является `true`.	(с C++20)

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

Параметры

first1, last1	-	первый отсортированный диапазон элементов
first2, last2	-	второй отсортированный диапазон элементов
d_first	-	начало диапазона вывода
policy	-	политика выполнения, которая должна использоваться. См. политика выполнения для получения подробной информации.
comp	-	объект функции сравнения (т.е. объект, удовлетворяющий требованиям Compare), который возвращает `true`, если первый аргумент меньше (т.е. отсортирован раньше) второго. Подпись функции сравнения должна быть эквивалентна следующей: `bool cmp(const Type1& a, const Type2& b);` Хотя подпись не обязательно должна содержать const&, функция не должна изменять переданные ей объекты и должна быть способна принимать все значения типа (возможно, const) `Type1` и `Type2` независимо от категории значения (поэтому `Type1&` недопустимо, также недопустимо `Type1` за исключением случаев, когда для `Type1` перемещение эквивалентно копированию(с C++11)). Типы Type1 и Type2 должны быть такими, чтобы объекты типов InputIt1 и InputIt2 можно было декореферировать и затем неявно преобразовать в оба типа Type1 и Type2.
Требования к типу
-`InputIt1, InputIt2` должен удовлетворять требованиям LegacyInputIterator.
-`OutputIt` должен удовлетворять требованиям LegacyOutputIterator.
-`ForwardIt1, ForwardIt2, ForwardIt3` должен удовлетворять требованиям LegacyForwardIterator.

Значение результата

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

Сложность

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

1,2) не более 2·(M + N) - 1 сравнений с использованием operator<.

3,4) не более 2·(M + N) - 1 применений предиката p.

Исключения

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

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

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

set_symmetric_difference (1)
template<class InputIt1, class InputIt2, class OutputIt> OutputIt set_symmetric_difference(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first) { while (first1 != last1) { if (first2 == last2) return std::copy(first1, last1, d_first); if (first1 < first2) d_first++ = first1++; else { if (first2 < first1) d_first++ = first2; else ++first1; ++first2; } } return std::copy(first2, last2, d_first); }
set_symmetric_difference (3)
template<class InputIt1, class InputIt2, class OutputIt, class Compare> OutputIt set_symmetric_difference(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp) { while (first1 != last1) { if (first2 == last2) return std::copy(first1, last1, d_first); if (comp(first1, first2)) d_first++ = first1++; else { if (comp(first2, first1)) d_first++ = first2; else ++first1; ++first2; } } return std::copy(first2, last2, d_first); }

set_symmetric_difference (1)

template<class InputIt1, class InputIt2, class OutputIt>
OutputIt set_symmetric_difference(InputIt1 first1, InputIt1 last1,
                                  InputIt2 first2, InputIt2 last2, OutputIt d_first)
{
    while (first1 != last1)
    {
        if (first2 == last2)
            return std::copy(first1, last1, d_first);
 
        if (*first1 < *first2)
            *d_first++ = *first1++;
        else
        {
            if (*first2 < *first1)
                *d_first++ = *first2;
            else
                ++first1;
            ++first2;
        }
    }
    return std::copy(first2, last2, d_first);
}

set_symmetric_difference (3)

template<class InputIt1, class InputIt2, class OutputIt, class Compare>
OutputIt set_symmetric_difference(InputIt1 first1, InputIt1 last1,
                                  InputIt2 first2, InputIt2 last2,
                                  OutputIt d_first, Compare comp)
{
    while (first1 != last1)
    {
        if (first2 == last2)
            return std::copy(first1, last1, d_first);
 
        if (comp(*first1, *first2))
            *d_first++ = *first1++;
        else
        {
            if (comp(*first2, *first1))
                *d_first++ = *first2;
            else
                ++first1;
            ++first2;
        }
    }
    return std::copy(first2, last2, d_first);
}

Пример

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
 
int main()
{
    std::vector<int> v1{1, 2, 3, 4, 5, 6, 7, 8};
    std::vector<int> v2{5, 7, 9, 10};
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());
 
    std::vector<int> v_symDifference;
 
    std::set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(),
                                  std::back_inserter(v_symDifference));
 
    for (int n : v_symDifference)
        std::cout << n << ' ';
    std::cout << '\n';
}

Вывод:

1 2 3 4 6 8 9 10

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

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

DR	Применён к	Поведение, как опубликовано	Правильное поведение
LWG 291	C++98	не было указано, как обрабатывать эквивалентные элементы в входных диапазонах	указано

См. также

includes	возвращает `true`, если одна последовательность является подпоследовательностью другой (шаблон функции)
set_difference	вычисляет разность двух множеств (шаблон функции)
set_union	вычисляет объединение двух множеств (шаблон функции)
set_intersection	вычисляет пересечение двух множеств (шаблон функции)
ranges::set_symmetric_difference (C++20)	вычисляет симметрическую разность двух множеств (niebloid)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/w/cpp/algorithm/set_symmetric_difference