C++ Logo


Advanced search

ranges::set_intersection and ranges::set_difference requirements are too strict

From: Alexander Bessonov <alexbav_at_[hidden]>
Date: Wed, 10 Mar 2021 10:54:42 +0300
Hello Everyone,

ranges::set_intersection and ranges::set_difference algorithms (among other set_* algorithms and ranges::merge) explicitly require its parameters to satisfy std::mergeable concept:



Part of this concept requires that elements of the _second_ range must be copyable to the destination:

std::indirectly_copyable<I2, Out>

However, by definition of both these algorithms, they only ever copy elements of the first range. This prohibits useful scenarios like the one shown below:

#include <vector>
#include <ranges>
#include <algorithm>
#include <cassert>

struct comp
    bool operator()(int p1, const std::pair<int, int> &p2) const
        return p1 < p2.first;

    bool operator()(const std::pair<int, int> &p1, int p2) const
        return p1.first < p2;

int main()
    std::vector<std::pair<int, int>> v1, v3;
    std::vector<int> v2;


    // The following line gives compilation error:
    std::ranges::set_intersection(v1, v2, std::back_inserter(v3), std::less{}, [](const auto &p) { return p.first; });

    // The following line also gives compilation error (for the same reason):
    std::ranges::set_intersection(v1, v2, std::back_inserter(v3), comp{});
    // This one compiles:
    std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(v3), comp{});

It looks like the requirements for these two algorithms are too strict. Maybe the new concept, let’s call it “half_mergeable” has to be added for these two algorithms?

template< class I1, class I2, class Out, class R = ranges::less, class P1 = std::identity, class P2 = std::identity >
concept half_mergeable =
    std::input_iterator<I1> &&
    std::input_iterator<I2> &&
    std::weakly_incrementable<Out> &&
    std::indirectly_copyable<I1, Out> &&
    // std::indirectly_copyable<I2, Out> && <-- this line removed
    std::indirect_strict_weak_order<R, std::projected<I1, P1>, std::projected<I2, P2>>;

What do you think?

Alexander Bessonov
HHD Software Ltd.

Received on 2021-03-10 01:54:49