boost::range::join for multiple ranges

Question

I want to do the following:

std::vector<int> a = {1,2,3}, b = {4,5,6}, c = {7,8,9};

for(auto&& i : join(a,b,c)) {
  i += 1
  std::cout << i;  // -> 2345678910
}

I tried using boost::range::join, this works fine:

auto r = boost::join(a,b);
for(auto&& i : boost::join(r,c)) {
  i += 1;
  std::cout << i;  // -> 2345678910
}

Chaining joins, reading operations work:

for(auto&& i : boost::join(boost::join(a,b),c))
  std::cout << i;  // -> 123456789

However, writing doesn't work:

for(auto&& i : boost::join(boost::join(a,b),c)) {
  i += 1; // Fails  :(
  std::cout << i;  
}

My variadic join has the same problem, i.e. works for reading but not for writing:

template<class C> C&& join(C&& c) { return c; }

template<class C, class D, class... Args>
auto join(C&& c, D&& d, Args&&... args)
-> decltype(boost::join(boost::join(std::forward<C>(c), std::forward<D>(d)),
                     join(std::forward<Args>(args)...))) {
return boost::join(boost::join(std::forward<C>(c), std::forward<D>(d)),
                     join(std::forward<Args>(args)...));
}

Mehrdad gave the solution in the comments

template<class C>
auto join(C&& c)
-> decltype(boost::make_iterator_range(std::begin(c),std::end(c))) {
return boost::make_iterator_range(std::begin(c),std::end(c));
}

template<class C, class D, class... Args>
auto join(C&& c, D&& d, Args&&... args)
-> decltype(boost::join(boost::join(boost::make_iterator_range(std::begin(c),std::end(c)),
                                 boost::make_iterator_range(std::begin(d),std::end(d))),
                     join(std::forward<Args>(args)...))) {
  return boost::join(boost::join(boost::make_iterator_range(std::begin(c),std::end(c)),
                                 boost::make_iterator_range(std::begin(d),std::end(d))),
                     join(std::forward<Args>(args)...));
}

Contributor

This might work (but credits go to jrok, since he explains the reason behind the problem): boost::join(boost::join(boost::make_iterator_range(a.begin(), a.end()), boost::make_iterator_range(b.begin(), b.end())), boost::make_iterator_range(c.begin(), c.end())) – Keldon

@Mehrdad Thanks, it works! I'll update the question with the solution. Could you explain why it works? boost::make_iterator_range also returns an lvalue so the const ref overload of join should be selected, right? – Contributor

Yes. It's because of the fact that the range a is the container itself, and a const container like vector propagates its const-ness onto its elements. On the other hand, an iterator range isn't a container -- it's just a pair of iterators. And the const-ness of an iterator is completely unrelated to the const-ness of what the iterators point to. On another note, while I'm not sure about this, I think replacing boost::make_iterator_range(a.begin(), a.end()) with boost::make_iterator_range(a) might also work. – Keldon

Just for the the record - your join template works too if you use only lvalues (after you rename it, the call with two arguments is ambiguous with boost::join). – Uredium

@Uredium Do you mean the wrapper marked as the solution or the previous one? (the previous one has the same initial problem) – Contributor

The previous one - it works with the same workaround as in my answer. – Uredium

@Mehrdad Thanks! And yes, boost::make_iterator_range(a) works (see solution). – Contributor

Complete solution here: https://mcmap.net/q/746137/-boost-range-join-many-ranges-in-one-custom-call/1077444 – Parliament

Answer 1

There are two overloads of boost::join

template<typename SinglePassRange1, typename SinglePassRange2>
joined_range<const SinglePassRange1, const SinglePassRange2>
join(const SinglePassRange1& rng1, const SinglePassRange2& rng2)

template<typename SinglePassRange1, typename SinglePassRange2>
joined_range<SinglePassRange1, SinglePassRange2>
join(SinglePassRange1& rng1, SinglePassRange2& rng2);

When you do this

for(auto&& i : boost::join(boost::join(a,b), c)) {
           //  ^^^^        ^^^^ temporary here
           //   ||
           //  calls the const ref overload

You get a temporary joined_range and as those can only bind to const references, the first overload is selected which returns a range that doesn't allow modifying.

You can work around this if you avoid temporaries:

#include <boost/range.hpp>
#include <boost/range/join.hpp>

int main()
{
    std::vector<int> a = {1,2,3}, b = {4,5,6}, c = {7,8,9};
    auto range = boost::join(a,b);

    for(int& i : boost::join(range,c)) {
        i += 1;
        std::cout << i;
    }
}

Live demo.

I haven't looked into your variadic functions, but the problem is likely similar.

Uredium

it is the same problem for the variadic ranges. The imo best solution would be to make a patch to boost.range, providing overload for rvalue references. – Dymphia

Thanks! Agreed, when chaining two boost::join's the function call produces a temporary that binds to a const lvalue reference (there is no boost::join overload for rvalue references). 'Our' workaround works. However, inside the variadic wrapper recursion would produce only temporaries, making it harder to achieve. – Contributor

Answer 2

Here's a complete solution, which works correctly on GCC 12. For GCC 10 & 11, the subranges function can be used to obtain an array of subranges, which can then be used as the lhs argument to | std::views::join.

EDIT: These functions only return on ranges that have a common iterator type. If you don't have a common iterator type, one option is to create a new container from the ranges (which is probably not what you want), or to create a custom type with different sub-ranges (which can't be used with std::views::join).

#include <ranges>
#include <vector>
#include <iostream>
#include <tuple>
#include <array>
#include <algorithm>

namespace detail {

template<std::size_t N, typename... Ts>
struct has_common_type_helper {
    using T1 = std::decay_t<std::tuple_element_t<N-1, std::tuple<Ts...>>>;
    using T2 = std::decay_t<std::tuple_element_t<N-2, std::tuple<Ts...>>>;
    static constexpr bool value = std::same_as<T1, T2> && has_common_type_helper<N-1, Ts...>::value;
};

template<typename... Ts>
struct has_common_type_helper<0, Ts...> : std::false_type {
    static_assert(std::is_void_v<Ts...>, "Undefined for an empty parameter pack");
};

template<typename... Ts>
struct has_common_type_helper<1, Ts...> : std::true_type {};

template<typename T> struct iterator_types;

template<std::ranges::range... Ts>
struct iterator_types<std::tuple<Ts...>> {
  using type = std::tuple<std::ranges::iterator_t<Ts>...>;
};

}

template<typename T>
struct has_common_type;

template<typename T1, typename T2>
struct has_common_type<std::pair<T1,T2>> {
    static constexpr bool value = std::same_as<std::decay_t<T1>, std::decay_t<T2>>;
};

template <typename... Ts>
struct has_common_type<std::tuple<Ts...>> : detail::has_common_type_helper<sizeof...(Ts), Ts...> {};

template <typename T>
inline constexpr bool has_common_type_v = has_common_type<T>::value;

template<std::size_t I = 0, typename Array, typename... Ts, typename Func> requires (I == sizeof...(Ts))
void init_array_from_tuple(Array& a, const std::tuple<Ts...>& t, Func fn)
{
}

template<std::size_t I = 0, typename Array, typename... Ts, typename Func> requires (I < sizeof...(Ts))
void init_array_from_tuple(Array& a, const std::tuple<Ts...>& t, Func fn)
{
    a[I] = fn(std::get<I>(t));
    init_array_from_tuple<I+1>(a, t, fn);
}

template<std::ranges::range... Ranges>
auto subranges(Ranges&&... rngs)
{
    using IteratorTypes = detail::iterator_types<std::tuple<Ranges...>>::type;
    static_assert(has_common_type_v<IteratorTypes>);
    using SubrangeT = std::ranges::subrange<std::tuple_element_t<0, IteratorTypes>>;
    auto subrngs = std::array<SubrangeT, sizeof...(Ranges)>{};
    auto t = std::tuple<Ranges&&...>{std::forward<Ranges>(rngs)...};
    auto fn = [](auto&& rng) {
        return std::ranges::subrange{rng.begin(), rng.end()};
    };
    init_array_from_tuple(subrngs, t, fn);
    return subrngs;
}

#if __GNUC__ >= 12
template<std::ranges::range... Ranges>
auto join(Ranges&&... rngs)
{
    return std::ranges::owning_view{subranges(std::forward<Ranges>(rngs)...) | std::views::join};
}
#endif

int main()
{
    std::vector<int> v1{1,2,3};
    std::vector<int> v2{4};
    std::vector<int> v3{5,6};

#if __GNUC__ >= 12
    std::ranges::copy(join(v1,v2,v3,v1), std::ostream_iterator<int>(std::cout, " "));
#else
    auto subrngs = subranges(v1,v2,v3,v1);
    std::ranges::copy(subrngs | std::views::join, std::ostream_iterator<int>(std::cout, " "));
#endif
    std::cout << '\n';
    return 0;
}

Guinea

Answer 3

Here's an implementation that works for two different ranges with a common reference type. You can extend it to 3 ranges using a brute-force approach.

#include <ranges>
#include <vector>
#include <list>
#include <iostream>
#include <algorithm>

template<std::ranges::range Range1, std::ranges::range Range2>
auto join2(Range1&& rng1, Range2&& rng2)
{
    using Ref1 = std::ranges::range_reference_t<Range1>;
    using Ref2 = std::ranges::range_reference_t<Range2>;
    using Ref = std::common_reference_t<Ref1, Ref2>;

    class Iter {
    public:
        using value_type = std::remove_cv_t<std::remove_reference_t<Ref>>;
        using difference_type = std::ptrdiff_t;

        Iter() = default;

        Iter(Range1&& rng1_, Range2&& rng2_, bool begin)
            : m_it1{begin ? rng1_.begin() : rng1_.end()}
            , m_it2{begin ? rng2_.begin() : rng2_.end()}
            , m_e1{rng1_.end()} {}

        bool operator==(const Iter& rhs) const {
            return m_it1 == rhs.m_it1 && m_it2 == rhs.m_it2;
        }

        Ref operator*() const {
            return m_it1 != m_e1 ? *m_it1 : *m_it2;
        }
        Iter& operator++() {
            (m_it1 != m_e1) ? (void)++m_it1 : (void)++m_it2;
            return *this;
        }
        Iter operator++(int) {
            Iter ret = *this;
            ++(*this);
            return ret;
        }

    private:
        std::ranges::iterator_t<Range1> m_it1;
        std::ranges::iterator_t<Range2> m_it2;
        std::ranges::iterator_t<Range1> m_e1;
    };
    static_assert(std::forward_iterator<Iter>);
    auto b = Iter{std::forward<Range1>(rng1), std::forward<Range2>(rng2), true};
    auto e = Iter{std::forward<Range1>(rng1), std::forward<Range2>(rng2), false};
    return std::ranges::subrange<Iter>{b, e};
}

int main()
{
    std::vector<int> v{1,2,3};
    std::list<int> l{4,5,6};
    std::ranges::copy(join2(v,l), std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
    return 0;
}

P.S. I am not optimistic about a variadic implementation, although I'm sure someone smarter than me would be able to figure it out.

Guinea