Structured bindings and tuple of references

Question

I'm encountering a problem in the design of a simple zip function, that would be called this way:

for (auto [x, y] : zip(std::vector{1,2,3}, std:vector{-1, -2, -3}) {
    // ...
}

So zip would return an object of type zip_range, itself exposing begin and end functions returning a zip_iterator.

Now, a zip_iterator, as I implemented it, uses a std::tuple<Iterators> -where Iterators are the types of the zipped containers' iterators- to keep tracks of its position in the zipped containers. When I dereference a zip_iterator, I obtain a tuple of references to the zipped containers' elements. The problem is it doesn't fit well with the structured bindings syntax:

std::vector a{1,2,3}, b{-1, -2, -3};
for (auto [x, y] : zip(a, b)) { // syntax suggests by value
    std::cout << ++x << ", " << --y << '\n'; // but this affects a's and b's content
}

for (auto& [x, y] : zip(a, b)) { // syntax suggests by reference
    // fails to compile: binding lvalue ref to temporary
}

So my question is: can you see a way to reconcile this reference-tuple's actual type (temporary value) with its semantics (lvalue, allows to modify the content it's refering to)?

I hope my question isn't too broad. Here's a working example, to compile with clang++ prog.cc -Wall -Wextra -std=gnu++2a (it won't work with gcc due to a bug in the way gcc handles deduction guides):

#include <tuple>
#include <iterator>
#include <iostream>
#include <vector>
#include <list>
#include <functional>


template <typename Fn, typename Argument, std::size_t... Ns>
auto tuple_map_impl(Fn&& fn, Argument&& argument, std::index_sequence<Ns...>) {
    if constexpr (sizeof...(Ns) == 0) return std::tuple<>(); // empty tuple
    else if constexpr (std::is_same_v<decltype(fn(std::get<0>(argument))), void>) {
        [[maybe_unused]]
        auto _ = {(fn(std::get<Ns>(argument)), 0)...}; // no return value expected
        return;
    }
    // then dispatch lvalue, rvalue ref, temporary
    else if constexpr (std::is_lvalue_reference_v<decltype(fn(std::get<0>(argument)))>) {
        return std::tie(fn(std::get<Ns>(argument))...);
    }
    else if constexpr (std::is_rvalue_reference_v<decltype(fn(std::get<0>(argument)))>) {
        return std::forward_as_tuple(fn(std::get<Ns>(argument))...);
    }
    else {
        return std::tuple(fn(std::get<Ns>(argument))...);
    }
}

template <typename T>
constexpr bool is_tuple_impl_v = false;

template <typename... Ts>
constexpr bool is_tuple_impl_v<std::tuple<Ts...>> = true;

template <typename T>
constexpr bool is_tuple_v = is_tuple_impl_v<std::decay_t<T>>;


template <typename Fn, typename Tuple>
auto tuple_map(Fn&& fn, Tuple&& tuple) {
    static_assert(is_tuple_v<Tuple>, "tuple_map implemented only for tuples");
    return tuple_map_impl(std::forward<Fn>(fn), std::forward<Tuple>(tuple),
                          std::make_index_sequence<std::tuple_size<std::decay_t<Tuple>>::value>());
}

template <typename... Iterators>
class zip_iterator {
    public:
    using value_type = std::tuple<typename std::decay_t<Iterators>::value_type...>;
    using difference_type = std::size_t;
    using pointer = value_type*;
    using reference = value_type&;
    using iterator_category = std::forward_iterator_tag;

    public:
    zip_iterator(Iterators... iterators) : iters(iterators...) {}
    zip_iterator(const std::tuple<Iterators...>& iter_tuple) : iters(iter_tuple) {}
    zip_iterator(const zip_iterator&) = default;
    zip_iterator(zip_iterator&&) = default;

    zip_iterator& operator=(const zip_iterator&) = default;
    zip_iterator& operator=(zip_iterator&&) = default;

    bool operator != (const zip_iterator& other) const { return iters != other.iters; }

    zip_iterator& operator++() { 
        tuple_map([](auto& iter) { ++iter; }, iters);
        return *this;
    }
    zip_iterator operator++(int) {
        auto tmp = *this;
        ++(*this);
        return tmp;
    }
    auto operator*() {
        return tuple_map([](auto i) -> decltype(auto) { return *i; }, iters);  
    }    
    auto operator*() const {
        return tuple_map([](auto i) -> decltype(auto) { return *i; }, iters);
    }
    private:
    std::tuple<Iterators...> iters;
};

template <typename... Containers>
struct zip {
    using iterator = zip_iterator<decltype(std::remove_reference_t<Containers>().begin())...>;
    template <typename... Container_types>
    zip(Container_types&&... containers) : containers_(containers...) {}
    auto begin() { return iterator(tuple_map([](auto&& i) { return std::begin(i); }, containers_)); }
    auto end()   { return iterator(tuple_map([](auto&& i) { return std::end(i); },   containers_)); }
    std::tuple<Containers...> containers_;
};

template <typename... Container_types>
zip(Container_types&&... containers) -> zip<std::conditional_t<std::is_lvalue_reference_v<Container_types>,
                                                             Container_types,
                                                             std::remove_reference_t<Container_types>>...>;

int main() {

    std::vector a{1,2,3}, b{-1, -2, -3};

    for (auto [x, y] : zip(a, b)) { // syntax suggests by value
        std::cout << x++ << ", " << y-- << '\n'; // but this affects a's and b's content
    }
    for (auto [x, y] : zip(a, b)) { 
        std::cout << x << ", " << y << '\n'; // new content
    }
    //for (auto& [x, y] : zip(a, b)) { // syntax suggests by reference
        // fails to compile: binding lvalue ref to temporary
    //}

}

Answer 1

Technically, this is less a structured bindings issue than it is a reference-semantic type issue. auto x = y does look like it's copying and then acting on an independent type, which is decidedly not the case for types like tuple<T&...> (and reference_wrapper<T> and string_view and span<T> and others).

However, as T.C. suggests in the comments, there are some horrible things you can do to make this work. Mind you, don't actually do them. I think your implementation is correct. But just for completeness. And general interest.

First, the wording for structured bindings indicates a difference in how get() is invoked based on the value category of the underlying object. If it's an lvalue reference (i.e. auto& or auto const&), get() is invoked on an lvalue. Otherwise, it's invoked on an xvalue. We need to take advantage of this by making:

for (auto [x, y] : zip(a, b)) { ... }

do one thing, and

for (auto& [x, y] : zip(a, b)) { ... }

do something else. That something else needs to be, first and foremost, actually compiling. To do that, your zip_iterator::operator* needs to return an lvalue. To do that, it actually needs to store within it a tuple<T&...>. The easiest way (in my opinion) to do that is to store an optional<tuple<T&...>> and have operator* do an emplace() on it and return its value(). That is:

template <typename... Iterators>
class zip_iterator {
    // ...
    auto& operator*() {
        value.emplace(tuple_map([](auto i) -> decltype(auto) { return *i; }, iters));
        return *value;
    }

    // no more operator*() const. You didn't need it anyway?

private:
    std::tuple<Iterators...> iters;

    using deref_types = std::tuple<decltype(*std::declval<Iterators>())...>;
    std::optional<deref_types> value;
};

But that still gets us the problem of wanting different get()s. To address that issue, we need our own tuple type - which provides its own get()s, such that when invoked an an lvalue it yields lvalues, but when invoked on an xvalue it yields prvalues.

Which I think is something like this:

template <typename... Ts>
struct zip_tuple : std::tuple<Ts...> {
    using base = std::tuple<Ts...>;
    using base::base;

    template <typename... Us,
         std::enable_if_t<(std::is_constructible_v<Ts, Us&&> && ...), int> = 0>
    zip_tuple(std::tuple<Us...>&& rhs)
         : base(std::move(rhs))
    { }

    template <size_t I>
    auto& get() & {
        return std::get<I>(*this);
    };

    template <size_t I>
    auto& get() const& {
        return std::get<I>(*this);
    };

    template <size_t I>
    auto get() && {
        return std::get<I>(*this);
    };

    template <size_t I>
    auto get() const&& {
        return std::get<I>(*this);
    };
};

namespace std {
    template <typename... Ts>
    struct tuple_size<zip_tuple<Ts...>>
        : tuple_size<tuple<Ts...>>
    { };

    template <size_t I, typename... Ts>
    struct tuple_element<I, zip_tuple<Ts...>>
        : tuple_element<I, tuple<remove_reference_t<Ts>...>>
    { };
}

In the non-lvalue-reference case, this means we bind a bunch of rvalue references to temporaries, which is fine - they get lifetime extended.

Now change just the deref_types alias to be a zip_tuple instead of a std::tuple and you have your desired behavior.

---

Two unrelated notes.

1) Your deduction guide can be reduced to just:

template <typename... Container_types>
zip(Container_types&&... containers) -> zip<Container_types...>;

If Container_types isn't an lvalue reference type, then it simply isn't a reference type, and remove_reference_t<Container_types> is Container_types.

2) gcc has a bug with regards to the way you're trying to construct zip<>. So to make it compile with both, prefer:

template <typename... Containers>
struct zip {
    zip(Containers... containers) : containers_(std::forward<Containers>(containers)...) { }
};

You're intended usage is to go through the deduction guide anyway, so this shouldn't cost you anything in favor of having it working on multiple compilers.

Answer 2

You can trivially “advertise” the reference semantics with

for (auto&& [x, y] : zip(a, b)) {

No expert will “fall for it”, but hopefully they understand that, even with auto [x, y], the valueness applies to the composite (which must be a prvalue for obvious reasons), not to the decomposed names, which are never copies of anything (unless a customized get makes them such).