`zip` operator to iterate on multiple container in a sign

Question

I worked out a zip operator similar to Python's, because I didn't find one in std. It allows to use range-based for loops to iterate at once over several equal-length containers (arrays, counters... anything that has an iterator and a static length). It should be safe (never exceed the iterator's capacity), be able to modify the content of the container in-place when possible, and have no run-time overhead compared to manually incrementing the iterators.

Some things still look a bit fishy to me and I also wonder if all my naming/implementation choices adhere the std look-and-feel. Examples of use:

  std::array a = {1,2,3,4};
  std::array b = {4,3,2,1};

  for (auto [i, j, k] : zip(a, b, a)) {
    std::cout << i << " " << j << " " << k << std::endl;
    i = 42; // we can overwrite the values of a
  }

  //// This one doesn't work yet:
  // for (auto [i, j] : zip(a, {4, 3, 2, 1})) {
  //   std::cout << i << " " << j << std::endl;
  // } 

With it comes a simple range class that allows to include counters in the iterations:

  // x takes the value of array a, and i counts from 0 to 3
  for (auto [x, i] : zip(a, range<4>())) {
    std::cout << i << " " << x << std::endl;
  }

Note here that the arguments to zip aren't necessarily l-values.

Here is my implementation:

// inductive case
template<typename T, typename... Ts>
struct zip : public zip<Ts...> {
  static_assert(std::tuple_size<T>::value == std::tuple_size<zip<Ts...>>::value,
                "Cannot zip over structures of different sizes");

  using head_value_type = std::tuple<typename T::value_type&>;
  using tail_value_type = typename zip<Ts...>::value_type;
  using value_type = decltype(std::tuple_cat(std::declval<head_value_type>(),
                                             std::declval<tail_value_type>()));

  zip(T& t, Ts&... ts) : zip<Ts...>(ts...), t_(t) {}
  zip(T& t, Ts&&... ts) : zip<Ts...>(ts...), t_(t) {}
  zip(T&& t, Ts&... ts) : zip<Ts...>(ts...), t_(t) {}
  zip(T&& t, Ts&&... ts) : zip<Ts...>(ts...), t_(t) {}

  struct iterator {
    using head_iterator = typename T::iterator;
    using tail_iterator = typename zip<Ts...>::iterator;

    head_iterator head;
    tail_iterator tail;

    bool operator!=(iterator& that) { return head != that.head; }
    void operator++() { ++head; ++tail; }

    value_type operator*() {
      return std::tuple_cat<head_value_type, tail_value_type>(*head, *tail);
    }

    iterator(head_iterator h, tail_iterator t) : head(h), tail(t) {}
  };

  iterator begin() { return iterator(t_.begin(), zip<Ts...>::begin()); }
  iterator end() { return iterator(t_.end(), zip<Ts...>::end()); }
  T& t_;
};

// base case
template<typename T>
struct zip<T> {
  using value_type = std::tuple<typename T::value_type&>;
  using iterator = typename T::iterator;
  zip(T&& t) : t_(t) {};
  zip(T& t) : t_(t) {};
  iterator begin() { return t_.begin(); }
  iterator end() { return t_.end(); }
private:
  T& t_;
};

// must implement tuple_size to check size equality
template<typename T, typename... Ts>
struct std::tuple_size<zip<T, Ts...>> {
  static constexpr int value = std::tuple_size<T>::value;
};

What looks fishy/over-complicated:

• the constructors to cover all kinds of arguments (l/r-value/references)
• the mangling of tuple types
• bonus: why doesn't my second example compile?

For completeness, here is my implementation of the range class:

template<class T, T BEG, T END, T STEP>
struct Range {
  Range() {};
  using iterator = Range;
  using value_type = T;

  bool operator!=(iterator that) { return this->val_ < that.val_; }
  void operator++() { val_ += STEP; }
  int& operator*() { return val_;}

  iterator begin() { return *this; }
  iterator end() { return Range(END); }
private:
  Range(int val) : val_(val) {}
  T val_ = BEG;
};

template<class T, T BEG, T END, T STEP>
struct std::tuple_size<Range<T, BEG, END, STEP>> {
  static constexpr int value = (END - BEG) / STEP;
};

template<class T, T BEG, T END, T STEP>
static auto range() { return Range<T, BEG, END, STEP>(); };

template<int BEG, int END, int STEP=1>
static auto range() { return Range<int, BEG, END, STEP>(); };

template<int END>
static auto range() { return Range<int, 0, END, 1>(); };

Any feedback will be much appreciated! Thanks in advance.

Answer 1

zip

Right now, your zip uses the tuple protocol. It probably makes more sense to use the range protocol instead, to support cases like this:

std::vector a{1, 2, 3, 4};
std::vector b{5, 6, 7, 8};
for (auto [x, y] : zip(a, b)) {
    std::cout << x << ' ' << y << '\n';
}

These constructors:

zip(T& t, Ts&... ts) : zip<Ts...>(ts...), t_(t) {}
zip(T& t, Ts&&... ts) : zip<Ts...>(ts...), t_(t) {}
zip(T&& t, Ts&... ts) : zip<Ts...>(ts...), t_(t) {}
zip(T&& t, Ts&&... ts) : zip<Ts...>(ts...), t_(t) {}

mandate that all arguments other than the first have the same. You also convert everything to lvalues, because an id-expression that refer to an rvalue reference is an lvalue (!) — this is because the original purpose of rvalue references were to capture rvalues and treat them like normal objects, not to forward rvalues.

The iterator class is also some required operations: associated types (iterator_category, difference_type, etc.), ==, postfix ++, etc. Also consider supporting random access iterator functionalities if the zipped ranges support them. We'll come back to this later.

I would also probably implement the zip without recursion, to reduce the compile-time overhead of nested template class instantiations. So the end result roughly looks like this: (not comprehensively tested, may have bugs; for simplicity, only random access ranges are supported)

#include <exception>
#include <iterator>
#include <tuple>

namespace detail {
    using std::begin, std::end;

    template <typename Range>
    struct range_traits {
        using iterator = decltype(begin(std::declval<Range>()));
        using value_type = typename std::iterator_traits<iterator>::value_type;
        using reference = typename std::iterator_traits<iterator>::reference;
    };

    template <typename... Its>
    class zip_iterator {
    public:
        // technically lying
        using iterator_category = std::common_type_t<
            typename std::iterator_traits<Its>::iterator_category...
        >;
        using difference_type = std::common_type_t<
            typename std::iterator_traits<Its>::difference_type...
        >;
        using value_type = std::tuple<
            typename std::iterator_traits<Its>::value_type...
        >;
        using reference = std::tuple<
            typename std::iterator_traits<Its>::reference...
        >;
        using pointer = std::tuple<
            typename std::iterator_traits<Its>::pointer...
        >;

        constexpr zip_iterator() = default;
        explicit constexpr zip_iterator(Its... its)
            : base_its{its...}
        {
        }

        constexpr reference operator*() const
        {
            return std::apply([](auto&... its) {
                return reference(*its...);
            }, base_its);
        }
        constexpr zip_iterator& operator++()
        {
            std::apply([](auto&... its) {
                (++its, ...);
            }, base_its);
            return *this;
        }
        constexpr zip_iterator operator++(int)
        {
            return std::apply([](auto&... its) {
                return zip_iterator(its++...);
            }, base_its);
        }
        constexpr zip_iterator& operator--()
        {
            std::apply([](auto&... its) {
                (--its, ...);
            }, base_its);
            return *this;
        }
        constexpr zip_iterator operator--(int)
        {
            return std::apply([](auto&... its) {
                return zip_iterator(its--...);
            }, base_its);
        }
        constexpr zip_iterator& operator+=(difference_type n)
        {
            std::apply([=](auto&... its) {
                ((its += n), ...);
            }, base_its);
            return *this;
        }
        constexpr zip_iterator& operator-=(difference_type n)
        {
            std::apply([=](auto&... its) {
                ((its -= n), ...);
            }, base_its);
            return *this;
        }
        friend constexpr zip_iterator operator+(const zip_iterator& it, difference_type n)
        {
            return std::apply([=](auto&... its) {
                return zip_iterator(its + n...);
            }, it.base_its);
        }
        friend constexpr zip_iterator operator+(difference_type n, const zip_iterator& it)
        {
            return std::apply([=](auto&... its) {
                return zip_iterator(n + its...);
            }, it.base_its);
        }
        friend constexpr zip_iterator operator-(const zip_iterator& it, difference_type n)
        {
            return std::apply([=](auto&... its) {
                return zip_iterator(its - n...);
            }, it.base_its);
        }
        constexpr reference operator[](difference_type n) const
        {
            return std::apply([=](auto&... its) {
                return reference(its[n]...);
            }, base_its);
        }

        // the following functions assume usual random access iterator semantics
        friend constexpr bool operator==(const zip_iterator& lhs, const zip_iterator& rhs)
        {
            return std::get<0>(lhs.base_its) == std::get<0>(rhs.base_its);
        }
        friend constexpr bool operator!=(const zip_iterator& lhs, const zip_iterator& rhs)
        {
            return !(lhs == rhs);
        }
        friend constexpr bool operator<(const zip_iterator& lhs, const zip_iterator& rhs)
        {
            return std::get<0>(lhs.base_its) < std::get<0>(rhs.base_its);
        }
        friend constexpr bool operator>(const zip_iterator& lhs, const zip_iterator& rhs)
        {
            return rhs < lhs;
        }
        friend constexpr bool operator<=(const zip_iterator& lhs, const zip_iterator& rhs)
        {
            return !(rhs < lhs);
        }
        friend constexpr bool operator>=(const zip_iterator& lhs, const zip_iterator& rhs)
        {
            return !(lhs < rhs);
        }
     private:
        std::tuple<Its...> base_its;
    };
}

template <typename... Ranges>
class zip {
    static_assert(sizeof...(Ranges) > 0, "Cannot zip zero ranges");
public:
    using iterator = detail::zip_iterator<
        typename detail::range_traits<Ranges>::iterator...
    >;
    using value_type = typename iterator::value_type;
    using reference = typename iterator::reference;

    explicit constexpr zip(Ranges&&... rs)
        : ranges{std::forward<Ranges>(rs)...}
    {
    }
    constexpr iterator begin()
    {
        return std::apply([](auto&... rs) {
            return iterator(rs.begin()...);
        }, ranges);
    }
    constexpr iterator end()
    {
        return std::apply([](auto&... rs) {
            return iterator(rs.end()...);
        }, ranges);
    }
private:
    std::tuple<Ranges...> ranges;
};

// by default, rvalue arguments are moved to prevent dangling references
template <typename... Ranges>
explicit zip(Ranges&&...) -> zip<Ranges...>;

Let's hope that P1858 Generalized pack declaration and usage gets accepted so that we can eliminate the tons of invocations of std::apply ...

range

Similar to zip, range operates on a tuple basis — the parameters are passed as template arguments, and tuple_size is provided. This would limit the usefulness of it, because runtime ranges (e.g., range(vector.size())) are not possible.

You choose to make range its own iterator type, which is not without precedent in the standard library. However, this will cause confusion once you add more functionality to range.

A more sophisticated comparison operator that treats sentinel (end) values specially takes the sign of step into account allows for commutative comparison and negative steps.

So the end result may look like this: (concept verification, overflow checking, etc. are omitted for simplicity)

namespace detail {
    template <typename T>
    class range_iterator {
        T value{0};
        T step{1};
        bool sentinel{false};
    public:
        // lying again
        using iterator_category = std::forward_iterator_tag;
        using difference_type = std::intmax_t;
        using value_type = T;
        using reference = T;
        using pointer = T*;

        constexpr range_iterator() = default;
        // sentinel
        explicit constexpr range_iterator(T v)
            : value{v}, sentinel{true}
        {
        }
        explicit constexpr range_iterator(T v, T s)
            : value{v}, step{s}
        {
        }

        constexpr reference operator*() const
        {
            return value;
        }
        constexpr range_iterator& operator++()
        {
            value += step;
            return *this;
        }
        constexpr range_iterator operator++(int)
        {
            auto copy{*this};
            ++*this;
            return copy;
        }
        friend constexpr bool operator==(const range_iterator& lhs, const range_iterator& rhs)
        {
            if (lhs.sentinel && rhs.sentinel) {
                return true;
            } else if (lhs.sentinel) {
                return rhs == lhs;
            } else if (lhs.step > 0) {
                return lhs.value >= rhs.value;
            } else if (lhs.step < 0) {
                return lhs.value <= rhs.value;
            } else {
                return lhs.value == rhs.value;
            }
            // C++20: return (lhs.value <=> rhs.value) == (step <=> 0); from third branch
        }
        friend constexpr bool operator!=(const range_iterator& lhs, const range_iterator& rhs)
        {
            return !(lhs == rhs);
        }
    };
}

template <typename T>
class range {
    T first{0};
    T last{};
    T step{1};
public:
    using value_type = T;
    using iterator = detail::range_iterator<T>;

    explicit constexpr range(T e)
        : last{e}
    {
    }
    explicit constexpr range(T b, T e, T s = T{1})
        : first{b}, last{e}, step{s}
    {
    }
    constexpr iterator begin() const
    {
        return iterator{first, step};
    }
    constexpr iterator end() const
    {
        return iterator{last};
    }
    constexpr T size() const
    {
        return (last - first) / step;
    }
};

You may also consider implementing enumerate based on Python's, which comes in handy when accessing sequences by index:

// again, rvalue arguments are copied by default
template <typename Sequence>
auto enumerate(Sequence&& seq)
{
    using std::begin, std::end;
    return zip(range(end(seq) - begin(seq)), std::forward<Sequence>(seq));
}