std::ranges::set_difference, std::ranges::set_difference_result

Определено в заголовке `<algorithm>`
Подпись вызова
template< std::input_iterator I1, std::sentinel_for<I1> S1, std::input_iterator I2, std::sentinel_for<I2> S2, std::weakly_incrementable O, class Comp = ranges::less, class Proj1 = std::identity, class Proj2 = std::identity > requires std::mergeable<I1, I2, O, Comp, Proj1, Proj2> constexpr set_difference_result<I1, O> set_difference( I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );	(1)	(с C++20)
template< ranges::input_range R1, ranges::input_range R2, std::weakly_incrementable O, class Comp = ranges::less, class Proj1 = std::identity, class Proj2 = std::identity > requires std::mergeable<ranges::iterator_t<R1>, ranges::iterator_t<R2>, O, Comp, Proj1, Proj2> constexpr set_difference_result<ranges::borrowed_iterator_t<R1>, O> set_difference( R1&& r1, R2&& r2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );	(2)	(с C++20)
Вспомогательные типы
template< class I, class O > using set_difference_result = ranges::in_out_result<I, O>;	(3)	(с C++20)

Копирует элементы из упорядоченного входного диапазона [first1, last1), которые не найдены в упорядоченном входном диапазоне [first2, last2), в выходной диапазон, начинающийся с result.

Поведение не определено, если

входные диапазоны не упорядочены относительно comp и proj1 или proj2, соответственно, или
результирующий диапазон перекрывается с любым из входных диапазонов.

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

2) То же, что и (1), но использует r1 в качестве первого диапазона и r2 в качестве второго диапазона, как если бы использовался ranges::begin(r1) как first1, ranges::end(r1) как last1, ranges::begin(r2) как first2, и ranges::end(r2) как last2.

Функциональные сущности, описанные на этой странице, являются niebloids, то есть:

Явные списки аргументов шаблона не могут быть указаны при вызове любого из них.
Ни один из них не виден для поиска зависимых от аргументов.
Когда любой из них найден обычным поиском без квалификаторов как имя слева от оператора вызова функции, поиск зависимых от аргументов запрещен.

На практике они могут быть реализованы как объекты функций или с помощью специальных расширений компилятора.

Параметры

first1, last1	-	пара итераторов-пределов, обозначающая первый упорядоченный входной диапазон
first2, last2	-	пара итераторов-пределов, обозначающая второй упорядоченный входной диапазон
r1	-	первый упорядоченный входной диапазон
r2	-	второй упорядоченный входной диапазон
result	-	начало выходного диапазона
comp	-	компаратор для применения к спроецированным элементам
proj1	-	проекция для применения к элементам в первом диапазоне
proj2	-	проекция для применения к элементам во втором диапазоне

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

{last1, result_last}, где result_last — конец построенного диапазона.

Сложность

Максимум \(\scriptsize 2\cdot(N_1+N_2)-1\)2·(N₁+N₂)-1 сравнений и применений каждой проекции, где \(\scriptsize N_1\)N₁ и \(\scriptsize N_2\)N₂ соответственно ranges::distance(first1, last1) и ranges::distance(first2, last2).

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

struct set_difference_fn
{
    template<std::input_iterator I1, std::sentinel_for<I1> S1,
             std::input_iterator I2, std::sentinel_for<I2> S2,
             std::weakly_incrementable O, class Comp = ranges::less,
             class Proj1 = std::identity, class Proj2 = std::identity>
    requires std::mergeable<I1, I2, O, Comp, Proj1, Proj2>
    constexpr ranges::set_difference_result<I1, O>
        operator()(I1 first1, S1 last1, I2 first2, S2 last2,
                   O result, Comp comp = {},
                   Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        while (!(first1 == last1 or first2 == last2))
        {
            if (std::invoke(comp, std::invoke(proj1, *first1), std::invoke(proj2, *first2)))
            {
                *result = *first1;
                ++first1;
                ++result;
            }
            else if (std::invoke(comp, std::invoke(proj2, *first2),
                                 std::invoke(proj1, *first1)))
                ++first2;
            else
            {
                ++first1;
                ++first2;
            }
        }
        return ranges::copy(std::move(first1), std::move(last1), std::move(result));
    }
 
    template<ranges::input_range R1, ranges::input_range R2,
             std::weakly_incrementable O, class Comp = ranges::less,
             class Proj1 = std::identity, class Proj2 = std::identity>
    requires std::mergeable<ranges::iterator_t<R1>, ranges::iterator_t<R2>,
                            O, Comp, Proj1, Proj2>
    constexpr ranges::set_difference_result<ranges::borrowed_iterator_t<R1>, O>
        operator()(R1&& r1, R2&& r2, O result, Comp comp = {},
                   Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        return (*this)(ranges::begin(r1), ranges::end(r1),
                       ranges::begin(r2), ranges::end(r2),
                       std::move(result), std::move(comp),
                       std::move(proj1), std::move(proj2));
    }
};
 
inline constexpr set_difference_fn set_difference {};

Пример

#include <algorithm>
#include <cassert>
#include <iostream>
#include <iterator>
#include <string_view>
#include <vector>
 
auto print = [](const auto& v, std::string_view end = "")
{
    std::cout << "{ ";
    for (auto n{v.size()}; auto i : v)
        std::cout << i << (--n ? ", " : " ");
    std::cout << "} " << end;
};
 
struct Order // a struct with some very interesting data
{
    int order_id{};
 
    friend std::ostream& operator<<(std::ostream& os, const Order& ord)
    {
        return os << '{' << ord.order_id << '}';
    }
};
 
int main()
{
    const auto v1 = {1, 2, 5, 5, 5, 9};
    const auto v2 = {2, 5, 7};
    std::vector<int> diff{};
 
    std::ranges::set_difference(v1, v2, std::back_inserter(diff));
    print(v1, "∖ ");
    print(v2, "= ");
    print(diff, "\n\n");
 
    // We want to know which orders "cut" between old and new states:
    const std::vector<Order> old_orders{{1}, {2}, {5}, {9}};
    const std::vector<Order> new_orders{{2}, {5}, {7}};
    std::vector<Order> cut_orders(old_orders.size() + new_orders.size());
 
    auto [old_orders_end, cut_orders_last] =
        std::ranges::set_difference(old_orders, new_orders,
                                    cut_orders.begin(), {},
                                    &Order::order_id, &Order::order_id);
    assert(old_orders_end == old_orders.end());
 
    std::cout << "old orders = ";
    print(old_orders, "\n");
    std::cout << "new orders = ";
    print(new_orders, "\n");
    std::cout << "cut orders = ";
    print(cut_orders, "\n");
    cut_orders.erase(cut_orders_last, end(cut_orders));
    std::cout << "cut orders = ";
    print(cut_orders, "\n");
}

Вывод:

{ 1, 2, 5, 5, 5, 9 } ∖ { 2, 5, 7 } = { 1, 5, 5, 9 } 
 
old orders = { {1}, {2}, {5}, {9} } 
new orders = { {2}, {5}, {7} } 
cut orders = { {1}, {9}, {0}, {0}, {0}, {0}, {0} } 
cut orders = { {1}, {9} }

См. также

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

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