C++17 zip iterator compatible with std::sort

Question

Here are ~100 lines of code implementing three classes (ZipRef, ZipIter, Zip) which should satisfy the zip iterator pattern in a STL-compatible way. This means that, unlike boost::zip_iterator, ZipIter can be safely (I hope!) used in various algorithms like std::rotate and std::sort. I tried to embrace the power of C++17, aiming at writing much more readable (variadic) template code compared to what allowed by C++11.

Note: maintained on GitHub (includes a usage example and some extra notes), the code in this post is not going to be edited.

//
// C++17 implementation of ZipIterator by Dario Pellegrini <pellegrini.dario@gmail.com>
// Still unsure about the licence, but something in the line of just providing attribution
// October 2019
//

#include <tuple>

template <typename ...T>
class ZipRef {
  std::tuple<T*...> ptr;
public:
  ZipRef() = delete;
  ZipRef(const ZipRef& z) = default;
  ZipRef(ZipRef&& z) = default;
  ZipRef(T* const... p): ptr(p...) {}

  ZipRef& operator=(const ZipRef& z)             { return copy_assign( z); }
  ZipRef& operator=(const std::tuple<T...>& val) { return val_assign(val); }

  template <size_t I = 0>
  ZipRef& copy_assign(const ZipRef& z) {
    *(std::get<I>(ptr)) = *(std::get<I>(z.ptr));
    if constexpr( I+1 < sizeof...(T) ) return copy_assign<I+1>(z);
    return *this;
  }
  template <size_t I = 0>
  ZipRef& val_assign(const std::tuple<T...>& t) {
    *(std::get<I>(ptr)) = std::get<I>(t);
    if constexpr( I+1 < sizeof...(T) ) return val_assign<I+1>(t);
    return *this;
  }

  std::tuple<T...> val() const {return std::apply([](auto&&...args){ return std::tuple((*args)...); }, ptr);}
  operator std::tuple<T...>() const { return val(); }

  template <size_t I = 0>
  void swap(const ZipRef& o) const {
    std::swap(*(std::get<I>(ptr)), *(std::get<I>(o.ptr)));
    if constexpr( I+1 < sizeof...(T) ) swap<I+1>(o);
  }

  #define OPERATOR(OP) \
    bool operator OP(const ZipRef & o) const { return val() OP o.val(); } \
    inline friend bool operator OP(const ZipRef& r, const std::tuple<T...>& t) { return r.val() OP t; } \
    inline friend bool operator OP(const std::tuple<T...>& t, const ZipRef& r) { return t OP r.val(); }

    OPERATOR(==) OPERATOR(<=) OPERATOR(>=)
    OPERATOR(!=) OPERATOR(<)  OPERATOR(>)
  #undef OPERATOR

};

template<typename ...IT>
class ZipIter {
  std::tuple<IT...> it;

  template<int N, typename... T> using NthTypeOf =
    typename std::tuple_element<N, std::tuple<T...>>::type;
  template<typename... T> using FirstTypeOf = NthTypeOf<0, T...>;

public:
  using iterator_category = typename std::iterator_traits<FirstTypeOf<IT...>>::iterator_category;
  using difference_type   = typename std::iterator_traits<FirstTypeOf<IT...>>::difference_type;
  using value_type        = std::tuple<typename std::iterator_traits<IT>::value_type ...>;
  using pointer           = std::tuple<typename std::iterator_traits<IT>::pointer ...>;
  using reference         = ZipRef<typename std::iterator_traits<IT>::value_type ...>;

  ZipIter() = default;
  ZipIter(const ZipIter &rhs) = default;
  ZipIter(ZipIter&& rhs) = default;
  ZipIter(const IT&... rhs): it(rhs...) {}

  ZipIter& operator=(const ZipIter& rhs) = default;
  ZipIter& operator=(ZipIter&& rhs) = default;

  ZipIter& operator+=(const difference_type d) { 
    std::apply([&d](auto&&...args){((std::advance(args,d)),...);}, it); return *this;
  }
  ZipIter& operator-=(const difference_type d) { return operator+=(-d); }

  reference operator* () const {return std::apply([](auto&&...args){return reference(&(*(args))...);}, it);}
  pointer   operator->() const {return std::apply([](auto&&...args){return pointer  (&(*(args))...);}, it);}
  reference operator[](difference_type rhs) const {return *(operator+(rhs));}

  ZipIter& operator++() { return operator+=( 1); }
  ZipIter& operator--() { return operator+=(-1); }
  ZipIter operator++(int) {ZipIter tmp(*this); operator++(); return tmp;}
  ZipIter operator--(int) {ZipIter tmp(*this); operator--(); return tmp;}

  difference_type operator-(const ZipIter& rhs) const {return std::get<0>(it)-std::get<0>(rhs.it);}
  ZipIter operator+(const difference_type d) const {ZipIter tmp(*this); tmp += d; return tmp;}
  ZipIter operator-(const difference_type d) const {ZipIter tmp(*this); tmp -= d; return tmp;}
  inline friend ZipIter operator+(const difference_type d, const ZipIter& z) {return z+d;}
  inline friend ZipIter operator-(const difference_type d, const ZipIter& z) {return z-d;}

  #define OPERATOR(OP) \
    bool operator OP(const ZipIter& rhs) const {return it OP rhs.it;}
    OPERATOR(==) OPERATOR(<=) OPERATOR(>=)
    OPERATOR(!=) OPERATOR(<)  OPERATOR(>)
  #undef OPERATOR
};

template<typename ...Container>
class Zip {
  std::tuple<Container&...> zip;

public:
  Zip() = delete;
  Zip(const Zip& z) = default;
  Zip(Zip&& z) = default;
  Zip(Container&... z): zip(z...) {}

  #define HELPER(OP) \
    auto OP(){return std::apply([](auto&&... args){ return ZipIter((args.OP())...);}, zip);}
    HELPER( begin) HELPER( end)
    HELPER(rbegin) HELPER(rend)
  #undef HELPER
};

#include <utility>
using std::swap;
template<typename ...T> void swap(const ZipRef<T...>& a, const ZipRef<T...>& b) { a.swap(b); }

#include <sstream>
template< class Ch, class Tr, class...IT, typename std::enable_if<(sizeof...(IT)>0), int>::type = 0>
auto& operator<<(std::basic_ostream<Ch, Tr>& os, const ZipRef<IT...>& t) {
  std::basic_stringstream<Ch, Tr> ss;
  ss << "[ ";
  std::apply([&ss](auto&&... args) {((ss << args << ", "), ...);}, t.val());
  ss.seekp(-2, ss.cur);
  ss << " ]";
  return os << ss.str();
}

Usage example from the README:

Consider this minimal example:

#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include "ZipIterator.hpp" //Header only ;)

int main() {
  std::vector<int> a{3,1,4,2};
  std::vector<std::string> b{"Alice","Bob","Charles","David"};

  auto zip = Zip(a,b);

  for (const auto & z: zip) std::cout << z << std::endl;
  std::cout << std::endl;

  std::sort(zip.begin(), zip.end());

  for (const auto & z: zip) std::cout << z << std::endl;
  return 0;
}

It can be compiled by simply enabling the c++17 (or more recent) standard and the produced output is:

$ g++ -std=c++17 main.cpp -o main.out && ./main.out
[ 3, Alice ]
[ 1, Bob ]
[ 4, Charles ]
[ 2, David ]

[ 1, Bob ]
[ 2, David ]
[ 3, Alice ]
[ 4, Charles ]

Behind the curtain the permutations (either by swapping or copying) applied by std::sort to the elements of vector a have been simultaneously applied to vector b as well.

Note that it would have been possible to zip a third (and more) vector as well, as the implementation leverages on variadic templates.

The reason for ZipRef over std::tuple is that one needs special constructor, assignment and comparison operators to be able to handle the tuple of pointers with a value-like semantics. One also needs a tuple of pointers because it allows to manipulate the data even if the tuple is constant, so one can extend the lifetime of non-const lvalues references of ZipRef (as the one returned when dereferencing ZipIter) by binding them to const references, while still being able, later, to modify the data being pointed to. Note that the custom swap, quite unusually, takes const references!

Answer 1

Lies, damned lies, ... and iterator_category

This line from ZipIter is a big lie:

    using iterator_category = typename std::iterator_traits<FirstTypeOf<IT...>>::iterator_category;

Why? Because it unequivocally expands the capabilities of the first iterator type to all the other ones.

This has some bad consequences: Some operations (e.g. std::sort) require at least some specific iterator category to work.

Example:

auto a = std::vector<std::string>{ "A", "B", "C", "A" };
auto b = std::forward_list<int>{ 4, 3, 2, 1 };

auto zip = Zip(a, b);
std::sort(zip.begin(), zip.end()); // This cannot succeed

In this case, std::sort requires random access iterators, which std::vector does provide. However, std::forward_list doesn't (it only provides forward iterators). But ZipIter promises that it is a random access iterator, even though random access operations are not supported on some contained iterators.

Ok, ZipIter::iterator_category is a lie, but why is it so damning?

Because iterator_category is an easy to use feature check (with strong constraints mandated by the standard). So many algorithm implementations just check for iterator_category. If you're lucky, they will still fail at compile time, but in some subtler cases you just silently run into undefined behavior.

How to fix this?

Instead of using the first available iterator_category, use the minimal iterator_category of all provided iterators:

    using iterator_category = std::common_type_t<typename std::iterator_traits<IT>::iterator_category...>;
    // this works since more powerful iterator categories inherit from less powerful ones
    // thus the common ancestor tag is supported by all

But wait a moment...

Remember when I said that the standard mandates strong constraints for certain iterator categories?

Well, if an iterator wants to be categorized as forward iterator or above, among other constraints the following must be true:

reference must be either value_type& or const value_type&.

Based on this constraint, the most powerful legal iterator_category for this iterator is actually std::input_iterator_tag. (Which in turn means that std::sort won't work at all, as it requires random access iterators.)

There are arguments to be made why the standard is overly restrictive with this clause, but as of C++17 these are the given requirements and shall not be violated. This is why boost::zip_iterator cannot be used with algorithms like std::sort: There is no legally possible way to meet all requirements under all circumstances.

Fun fact: std::vector<bool>::iterator has the same issue.

Constant pain

There are some issues with regard to constness.

auto a = std::vector<int>{ 1, 2, 3, 4 };
auto b = std::vector<std::string>{ "A", "B", "C", "D" };
const auto c = b;

auto zip_one = Zip(a, b);
auto zip_two = Zip(a, c);

for(auto&& value : zip_one) std::cout << value << "\n"; // this works
for(auto&& value : zip_two) std::cout << value << "\n"; // this fails to compile

What happened? c is an exact copy of b - the only difference being a small const. But the consequences are dire: Compilation failure!

What changed? Since c is constant, c.begin() and c.end() only return const_iterators, since elements within should also not change.

How to fix? The culprit in this case is the definition for ZipIter::reference:

    using reference         = ZipRef<typename std::iterator_traits<IT>::value_type ...>;

Using a different definition that takes into account the actual iterator reference fixes this:

    using reference         = ZipRef<std::remove_reference_t<typename std::iterator_traits<IT>::reference>...>;

But the trouble with const doesn't end here: Once any type of the template type parameters of ZipRef is const, some operations of ZipRef won't work anymore: assignment fails (const values cannot be reassigned) and swap fails (same reason). And there is no easy fix for this!

To the end of the universe... and beyond!

auto a = std::vector<std::string>(10, "A");
auto b = std::vector<std::string>(2, "C");

auto zip = Zip(a, b);
std::distance(zip.begin(), zip.end()); // uh oh

How many zipped elements should zip contain?

Logically, there should at most be two, as there aren't any values in b to continue any further.

Instead, the current implementation gives undefined behavior:

auto endReached = std::next(zip.begin(), 2);
assert(endReached != zip.end());

endReached is the ZipIter pointing just at b.end(), i.e. where the iteration should stop. But the check against zip.end() fails, since not all iterators have yet reached their corresponding end iterator.

And this is where undefined behavior happens: ++endReached advances a past-the-end-iterator, and after that nothing can be trusted anymore.

How can this be fixed?

The most common approach is to use a sentinel value as end iterator so that any ZipIter compares true if any (instead of all) of its contained iterators matches the corresponding end iterator.

Licensed trouble (or freedom?)

// Still unsure about the licence, but something in the line of just providing attribution

When posting the code on this site, you have already released it under the CC-BY-SA 4.0 license. You can of course release it under another license model (you're free to do so as the license holder).

Other issues

I won't repeat much of Toby Speight's answer, but some additional notes:

• ZipRef::swap is modelled on std::iter_swap, not std::swap. Maybe the name should be adjusted to reflect this?
• ZipIter::difference_type has the same issue as ZipIter::reference: It only uses the difference_type of the first iterator. (Usually not much of a deal, since most iterators use std::ptrdiff_t. Still, beware of the edge case!)
• ZipRefs operator std::tuple<T...>() is unlikely to work in generic context as intended (conversions are excluded when matching templated arguments, e.g. std::get<1>(zipRef) doesn't work). It works in specialized contexts (void f(std::tuple<std::string, int>); f(zipRef);, but this might cause unexpected issues.

Answer 2

A constant Zip can't easily be iterated:

  auto const zip = Zip(a,b);

  for (const auto & z: zip) std::cout << z << std::endl;

All that's necessary for that to work is to add some const operators:

  #define HELPER(OP) \
    auto OP() const {return std::apply([](auto&&... args){ return ZipIter((args.OP())...);}, zip);}
    HELPER( begin) HELPER( end)
    HELPER(rbegin) HELPER(rend)
    HELPER( cbegin) HELPER( cend)
    HELPER(crbegin) HELPER(crend)
  #undef HELPER

There's still more to do here, as it's surprising that a const Zip returns mutable iterators. Unfortunately, I haven't yet come up with a solution to that problem. The nearest I got was to separate out the const (r){begin,end} like this:

#define HELPER(OP)                                                      \
    auto OP() const {return std::apply([](auto&&... args) { return ZipIter((args.c##OP())...);}, zip);}
    HELPER(begin) HELPER(end)
    HELPER(rbegin) HELPER(rend)
#undef HELPER

but it fails because ZipIter::reference is based on IT::value_type, which doesn't carry the constness with it. I think I'd need to define a parallel const_ZipIter to support that.

---

From C++20 onwards, we can implement operator <=> instead of all the relational operators in ZipIter.

---

std::size_t is misspelt (and is missing its header), where it's used as a non-type template argument.

We're also missing an include of <utility>, for std::swap used in ZipRef.

---

I think we should be allowing argument-dependent lookup of swap here:

  template <size_t I = 0>
  void swap(const ZipRef& o) const {
    std::swap(*(std::get<I>(ptr)), *(std::get<I>(o.ptr)));
    if constexpr( I+1 < sizeof...(T) ) swap<I+1>(o);
  }

I suggest:

    void swap(const ZipRef& o) const {
        swap_impl<0>(o);
    }

private:
    template <std::size_t I>
    void swap_impl(const ZipRef& o) const {
        using std::swap;
        swap(*std::get<I>(ptr), *std::get<I>(o.ptr));
        if constexpr(I+1 < sizeof...(T)) swap_impl<I+1>(o);
    }

I guess that reversing the order might make for simpler code, but could fail the strong exception guarantee if an element's swap() might throw.

Also with swap(), I think that this being const is sufficiently weird to justify a decent explanatory comment in the code. It might save you trying to "fix" this "bug" later!

---

Just before our non-member swap, we have a using declaration:

using std::swap;

Not only do we not need this, it's also poor practice to inflict this on users of the header.

---

Misuse can give hard-to-detect problems. For example, the program crashed when I tried passing inputs of different length. We could add some error checking to the Zip constructor:

#include <algorithm>
#include <functional>

    Zip(Container&... z)
        : zip{z...}
    {
        auto const len = {(zip.size())...,};
        if (std::adjacent_find(len.begin(), len.end(), std::not_equal_to()) != len.end())
            throw std::invalid_argument("array lengths differ");
    }

A little further work should be able to add the actual lengths to the exception message to improve its value to the programmer.

---

Modified code

This is with my changes; I'm sure there's more improvements that could be made.

#include <cstdint>
#include <algorithm>
#include <functional>
#include <tuple>
#include <utility>

template <typename ...T>
class ZipRef {
    std::tuple<T*...> ptr;
public:
    ZipRef() = delete;
    ZipRef(const ZipRef& z) = default;
    ZipRef(ZipRef&& z) = default;
    ZipRef(T* const... p): ptr(p...) {}

    ZipRef& operator=(const ZipRef& z)             { return copy_assign(z); }
    ZipRef& operator=(const std::tuple<T...>& val) { return val_assign(val); }

    template <std::size_t I = 0>
    ZipRef& copy_assign(const ZipRef& z) {
        *(std::get<I>(ptr)) = *(std::get<I>(z.ptr));
        if constexpr(I+1 < sizeof...(T)) return copy_assign<I+1>(z);
        return *this;
    }
    template <std::size_t I = 0>
    ZipRef& val_assign(const std::tuple<T...>& t) {
        *(std::get<I>(ptr)) = std::get<I>(t);
        if constexpr(I+1 < sizeof...(T)) return val_assign<I+1>(t);
        return *this;
    }

    std::tuple<T...> val() const {return std::apply([](auto&&...args) { return std::tuple((*args)...); }, ptr);}
    operator std::tuple<T...>() const { return val(); }

    void swap(const ZipRef& o) const {
        swap_impl<sizeof...(T)-1>(o);
    }

private:
    template <std::size_t I>
    void swap_impl(const ZipRef& o) const {
        using std::swap;
        swap(*std::get<I>(ptr), *std::get<I>(o.ptr));
        if constexpr(I) swap_impl<I-1>(o);
    }

public:
#define OPERATOR(OP)                                                    \
    bool operator OP(const ZipRef & o) const { return val() OP o.val(); } \
    inline friend bool operator OP(const ZipRef& r, const std::tuple<T...>& t) { return r.val() OP t; } \
    inline friend bool operator OP(const std::tuple<T...>& t, const ZipRef& r) { return t OP r.val(); }

    OPERATOR(==) OPERATOR(<=) OPERATOR(>=)
    OPERATOR(!=) OPERATOR(<)  OPERATOR(>)
#undef OPERATOR

};

template<typename ...IT>
class ZipIter {
    std::tuple<IT...> it;

    template<int N, typename... T> using NthTypeOf =
        typename std::tuple_element<N, std::tuple<T...>>::type;
    template<typename... T> using FirstTypeOf = NthTypeOf<0, T...>;

public:
    using iterator_category = typename std::iterator_traits<FirstTypeOf<IT...>>::iterator_category;
    using difference_type   = typename std::iterator_traits<FirstTypeOf<IT...>>::difference_type;
    using value_type        = std::tuple<typename std::iterator_traits<IT>::value_type ...>;
    using pointer           = std::tuple<typename std::iterator_traits<IT>::pointer ...>;
    using reference         = ZipRef<typename std::iterator_traits<IT>::value_type ...>;

    ZipIter() = default;
    ZipIter(const ZipIter &rhs) = default;
    ZipIter(ZipIter&& rhs) = default;
    ZipIter(IT... rhs): it(std::move(rhs)...) {}

    ZipIter& operator=(const ZipIter& rhs) = default;
    ZipIter& operator=(ZipIter&& rhs) = default;

    ZipIter& operator+=(const difference_type d) {
        std::apply([&d](auto&&...args) {((std::advance(args,d)),...);}, it); return *this;
    }
    ZipIter& operator-=(const difference_type d) { return operator+=(-d); }

    reference operator* () const {return std::apply([](auto&&...args) {return reference(&(*(args))...);}, it);}
    pointer   operator->() const {return std::apply([](auto&&...args) {return pointer(&(*(args))...);}, it);}
    reference operator[](difference_type rhs) const {return *(operator+(rhs));}

    ZipIter& operator++() { return operator+=(1); }
    ZipIter& operator--() { return operator+=(-1); }
    ZipIter operator++(int) {ZipIter tmp(*this); operator++(); return tmp;}
    ZipIter operator--(int) {ZipIter tmp(*this); operator--(); return tmp;}

    difference_type operator-(const ZipIter& rhs) const {return std::get<0>(it)-std::get<0>(rhs.it);}
    ZipIter operator+(const difference_type d) const {ZipIter tmp(*this); tmp += d; return tmp;}
    ZipIter operator-(const difference_type d) const {ZipIter tmp(*this); tmp -= d; return tmp;}
    inline friend ZipIter operator+(const difference_type d, const ZipIter& z) {return z+d;}
    inline friend ZipIter operator-(const difference_type d, const ZipIter& z) {return z-d;}

#define OPERATOR(OP)                                                    \
    bool operator OP(const ZipIter& rhs) const {return it OP rhs.it;}
    OPERATOR(==) OPERATOR(<=) OPERATOR(>=)
    OPERATOR(!=) OPERATOR(<)  OPERATOR(>)
#undef OPERATOR
};

template<typename ...Container>
class Zip {
    std::tuple<Container&...> zip;

public:
    Zip() = delete;
    Zip(const Zip& z) = default;
    Zip(Zip&& z) = default;
    Zip(Container&... z)
        : zip {z...}
    {
        auto const len = {(z.size())...,};
        if (std::adjacent_find(len.begin(), len.end(), std::not_equal_to()) != len.end())
            throw std::invalid_argument("array lengths differ");
    }

#define HELPER(OP)                                                      \
    auto OP() {return std::apply([](auto&&... args) { return ZipIter((args.OP())...);}, zip);}
    HELPER(begin) HELPER(end)
    HELPER(rbegin) HELPER(rend)
#undef HELPER

#define HELPER(OP)                                                      \
    auto OP() const {return std::apply([](auto&&... args) { return ZipIter((args.OP())...);}, zip);}
    HELPER(begin) HELPER(end)
    HELPER(rbegin) HELPER(rend)
    HELPER(cbegin) HELPER(cend)
    HELPER(crbegin) HELPER(crend)
#undef HELPER
};

#include <utility>
using std::swap;
template<typename ...T> void swap(const ZipRef<T...>& a, const ZipRef<T...>& b) { a.swap(b); }

#include <sstream>
template< class Ch, class Tr, class...IT, typename std::enable_if<(sizeof...(IT)>0), int>::type = 0>
auto& operator<<(std::basic_ostream<Ch, Tr>& os, const ZipRef<IT...>& t) {
    std::basic_stringstream<Ch, Tr> ss;
    ss << "[ ";
    std::apply([&ss](auto&&... args) {((ss << args << ", "), ...);}, t.val());
    ss.seekp(-2, ss.cur);
    ss << " ]";
    return os << ss.str();
}


#include <vector>
#include <string>
#include <algorithm>
#include <iostream>

int main() {
    std::vector<int> a {3,1,4,2};
    std::vector<std::string> b {"Alice","Bob","Charles","David"};

    auto const zip = Zip(a,b);

    for (const auto & z: zip) std::cout << z << std::endl;

    std::cout << std::endl;
    std::sort(zip.begin(), zip.end());
    for (const auto & z: zip) std::cout << z << std::endl;
}