24
\$\begingroup\$

My goal was to get the following code to work:

#include<iostream>
#include<vector>
#include<list>
#include<algorithm>
#include<array>
#include"functional.hpp"

int main( )
{
    std::vector<double> a{1.0, 2.0, 3.0, 4.0};
    std::list<char> b;
    b.push_back('a');
    b.push_back('b');
    b.push_back('c');
    b.push_back('d');
    std::array<int,5> c{5,4,3,2,1};

    auto d = zip(a, b, c);

    for (auto i : zip(a, b, c) )
    {
        std::cout << std::get<0>(i) << ", " << std::get<1>(i) << ", " << std::get<2>(i) << std::endl;
    }

    for (auto i : d)
    {
        std::cout << std::get<0>(i) << ", " << std::get<1>(i) << ", " << std::get<2>(i) << std::endl;
        std::get<0>(i) = 5.0;
        //std::cout << i1 << ", " << i2 << ", " << i3 << std::endl;
    }
    for (auto i : d)
    {
        std::cout << std::get<0>(i) << ", " << std::get<1>(i) << ", " << std::get<2>(i) << std::endl;
        //std::cout << i1 << ", " << i2 << ", " << i3 << std::endl;
    }
}

With the output:

1, a, 5
2, b, 4
3, c, 3
4, d, 2
5, a, 5
5, b, 4
5, c, 3
5, d, 2

The source for "functional.hpp" is:

#pragma once
#include<tuple>
#include<iterator>
#include<utility>

/***************************
// helper for tuple_subset and tuple_tail (from http://stackoverflow.com/questions/8569567/get-part-of-stdtuple)
***************************/
template <size_t... n>
struct ct_integers_list {
    template <size_t m>
    struct push_back
    {
        typedef ct_integers_list<n..., m> type;
    };
};

template <size_t max>
struct ct_iota_1
{
    typedef typename ct_iota_1<max-1>::type::template push_back<max>::type type;
};

template <>
struct ct_iota_1<0>
{
    typedef ct_integers_list<> type;
};

/***************************
// return a subset of a tuple
***************************/
template <size_t... indices, typename Tuple>
auto tuple_subset(const Tuple& tpl, ct_integers_list<indices...>)
    -> decltype(std::make_tuple(std::get<indices>(tpl)...))
{
    return std::make_tuple(std::get<indices>(tpl)...);
    // this means:
    //   make_tuple(get<indices[0]>(tpl), get<indices[1]>(tpl), ...)
}

/***************************
// return the tail of a tuple
***************************/
template <typename Head, typename... Tail>
inline std::tuple<Tail...> tuple_tail(const std::tuple<Head, Tail...>& tpl)
{
    return tuple_subset(tpl, typename ct_iota_1<sizeof...(Tail)>::type());
    // this means:
    //   tuple_subset<1, 2, 3, ..., sizeof...(Tail)-1>(tpl, ..)
}

/***************************
// increment every element in a tuple (that is referenced)
***************************/
template<std::size_t I = 0, typename... Tp>
inline typename std::enable_if<I == sizeof...(Tp), void>::type
increment(std::tuple<Tp...>& t)
{ }

template<std::size_t I = 0, typename... Tp>
inline typename std::enable_if<(I < sizeof...(Tp)), void>::type
increment(std::tuple<Tp...>& t)
{
    std::get<I>(t)++ ;
    increment<I + 1, Tp...>(t);
}

/**************************** 
// check equality of a tuple
****************************/
template<typename T1>
inline bool not_equal_tuples( const std::tuple<T1>& t1,  const std::tuple<T1>& t2 )
{
    return (std::get<0>(t1) != std::get<0>(t2));
}

template<typename T1, typename... Ts>
inline bool not_equal_tuples( const std::tuple<T1, Ts...>& t1,  const std::tuple<T1, Ts...>& t2 )
{
    return (std::get<0>(t1) != std::get<0>(t2)) && not_equal_tuples( tuple_tail(t1), tuple_tail(t2) );
}

/**************************** 
// dereference a subset of elements of a tuple (dereferencing the iterators)
****************************/
template <size_t... indices, typename Tuple>
auto dereference_subset(const Tuple& tpl, ct_integers_list<indices...>)
    -> decltype(std::tie(*std::get<indices-1>(tpl)...))
{
    return std::tie(*std::get<indices-1>(tpl)...);
}

/**************************** 
// dereference every element of a tuple (applying operator* to each element, and returning the tuple)
****************************/
template<typename... Ts>
inline auto
  dereference_tuple(std::tuple<Ts...>& t1) -> decltype( dereference_subset( std::tuple<Ts...>(), typename ct_iota_1<sizeof...(Ts)>::type()))
  {
    return dereference_subset( t1, typename ct_iota_1<sizeof...(Ts)>::type());
  }


template< typename T1, typename... Ts >
class zipper
{
    public:

    class iterator : std::iterator<std::forward_iterator_tag, std::tuple<typename T1::value_type, typename Ts::value_type...> >
    {
        protected:
            std::tuple<typename T1::iterator, typename Ts::iterator...> current;
        public:

        explicit iterator(  typename T1::iterator s1, typename Ts::iterator... s2 ) : 
            current(s1, s2...) {};

        iterator( const iterator& rhs ) :  current(rhs.current) {};

        iterator& operator++() {
            increment(current);
            return *this;
        }

        iterator operator++(int) {
            auto a = *this;
            increment(current);
            return a;
        }

        bool operator!=( const iterator& rhs ) {
            return not_equal_tuples(current, rhs.current);
        }

        typename iterator::value_type operator*() {
            return dereference_tuple(current);
        }
    };


    explicit zipper( T1& a, Ts&... b):
                        begin_( a.begin(), (b.begin())...), 
                        end_( a.end(), (b.end())...) {};

    zipper(const zipper<T1, Ts...>& a) :
                        begin_(  a.begin_ ), 
                        end_( a.end_ ) {};

    template<typename U1, typename... Us>
    zipper<U1, Us...>& operator=( zipper<U1, Us...>& rhs) {
        begin_ = rhs.begin_;
        end_ = rhs.end_;
        return *this;
    }

    zipper<T1, Ts...>::iterator& begin() {
        return begin_;
    }

    zipper<T1, Ts...>::iterator& end() {
        return end_;
    }

    zipper<T1, Ts...>::iterator begin_;
    zipper<T1, Ts...>::iterator end_;
};



//from cppreference.com: 
template <class T>
  struct special_decay
  {
     using type = typename std::decay<T>::type;
  };

//allows the use of references:
template <class T>
 struct special_decay<std::reference_wrapper<T>>
 {
   using type = T&;
 };

template <class T>
 using special_decay_t = typename special_decay<T>::type;

//allows template type deduction for zipper:
template <class... Types>
 zipper<special_decay_t<Types>...> zip(Types&&... args)
 {
   return zipper<special_decay_t<Types>...>(std::forward<Types>(args)...);
 }

I'm asking for a few things:

  • References and performance: Theoretically, the only things that (I believe) should be copied are iterators, but I'm not sure how to confirm this. I'm hoping that this has very little overhead (A couple of pointer dereferences maybe?), but I'm not sure how to check something like this.

  • Correctness: Are there any hidden bugs that aren't showing up in my use case? Technically, the code isn't really working as "expected" (it should spit out copies of the values for "auto i", and only allow modification of the original containers values with "auto& i", and there should be a version that allows you to look, but not touch: "const auto& i"), but I'm not sure how to fix that. I expect I need to create a const version for the const auto& i mode, but I'm not sure how to make a copy for the auto i version.

  • Code Cleanliness, Best practices: My code is pretty much never read by another human being, so any recommendations of best practices or commenting would be appreciated. I'm also not sure what to do about the move constructors: should I be deleting them, or ignoring them?

\$\endgroup\$
  • \$\begingroup\$ I like the special_decay trick. \$\endgroup\$ – alfC Feb 23 '18 at 16:21
  • \$\begingroup\$ I don't get the purpose of std::get<0>(i) = 5.0; line. Was it supposed to modify the tuple? My output for the third loop is still 1, a, 5 \n 2, b, 4 \n 3, c, 3 \n 4, d, 2 \$\endgroup\$ – Patrizio Bertoni Sep 28 '18 at 8:23
13
\$\begingroup\$

I have not much to say. Your code reads quite good, which is rather pleasant. Here are a few tidbits though:

typedef

If you are willing to write modern code, you should consider dropping typedef and using using everywhere instead. It helps to be consistent between regular alias and alias template. Moreover, the = symbol help to visually split the new name and the type it refers to. And the syntax is also consistent towards the way you can declare variables:

auto i = 1;
using some_type = int;

Perfect forwarding

It's clear that you already used it. But there are some other places where it would make sense to use it:

template <size_t... indices, typename Tuple>
auto tuple_subset(Tuple&& tpl, ct_integers_list<indices...>)
    -> decltype(std::make_tuple(std::get<indices>(std::forward<Tuple>(tpl))...))
{
    return std::make_tuple(std::get<indices>(std::forward<Tuple>(tpl))...);
    // this means:
    //   make_tuple(get<indices[0]>(tpl), get<indices[1]>(tpl), ...)
}

std::enable_if

While using std::enable_if in the return type of the functions, I find that it tends to make it unreadable. Therefore, you may probably want to move it to the template parameters list instead. Consider your code:

template<std::size_t I = 0, typename... Tp>
inline typename std::enable_if<(I < sizeof...(Tp)), void>::type
increment(std::tuple<Tp...>& t)
{
    std::get<I>(t)++ ;
    increment<I + 1, Tp...>(t);
}

And compare it to this one:

template<std::size_t I = 0, typename... Tp,
        typename = typename std::enable_if<I < sizeof...(Tp), void>::type>
inline void increment(std::tuple<Tp...>& t)
{
    std::get<I>(t)++ ;
    increment<I + 1, Tp...>(t);
}

Pre-increment vs. post-increment

Depending on the type, ++var may be faster than var++. It does not change anything for int but if your container contains large type, remember that the ++ in var++ is generally defined as:

auto operator++(int)
    -> T&
{
    auto res = var;
    ++var;
    return res;
}

As you can see, yet another copy of the incremented variable is made and ++var is called. Therefore, you may want to use ++var instead of var++ in a generic context.

Miscellaneous tidbits

template<typename U1, typename... Us>
zipper<U1, Us...>& operator=(zipper<U1, Us...>& rhs) { ... }

You may want to pass a const zipper<U1, Us...>& instead of a zipper<U1, Us...>&.

zipper<T1, Ts...>::iterator& begin() {
    return begin_;
}

zipper<T1, Ts...>::iterator& end() {
    return end_;
}

You may also want to provide the functions begin() const, end() const, cbegin() const and cend() const if you want this set of functions to be complete and consistent towards the STL. Also, some operator== would be great for zipper::iterator.

Also, I like the new function syntax which IMHO helps to separate the function return type and its name, which is especially useful when the said return type is long. However, I read that some people don't like it, so it's up to your own preferences.

Conclusion

Generally speaking, your code was good and it works, which is even better. I've provided a few tips, but there are probably many other things that you could do to improve it. It will always be up to you when it concerns the readability though, preferences matter in that domain :)

Edit: ok, so apparently yout example worked fine, but @Barry's answer seem to highlight more serious problems. You might want to accept it instead.

\$\endgroup\$
12
\$\begingroup\$

There are a few serious things that haven't been brought up by the other two answers yet.

Dereferencing issues

Let's say I am zipping a vector<T> and a vector<U>. Your iterator's current member will have type std::tuple<std::vector<T>::iterator, std::vector<U>::iterator> and its value_type will be std::tuple<T, U> and its reference type will be std::tuple<T, U>&.

First of all, the latter makes no sense. There is no std::tuple<T,U> for you to give a reference to, so you should change that particular typedef to refer to value_type (simply provide all the types for std::iterator instead of using defaults).

Secondly, take a look at this:

typename iterator::value_type operator*() {
    return dereference_tuple(current);
}

dereference_tuple does the right thing here - it gives you all the references, so the type of that expression is std::tuple<T&, U&>. But that isn't what you're returning! So rather than yielding references, you're yielding values. This means you're copying every element on every iteration, and you're not allowing any kind of modification.

But the lack of modification is hidden. Your original example compiles fine:

for (auto i : d) {
    std::get<0>(i) = 5.0;
}

but doesn't actually modify anything in a, which still retains {1.0, 2.0, 3.0, 4.0}. This would be very surprising to your users. You definitely want to make sure that you give back a tuple of references.

Forwarding isn't really supported

Your main function is:

template <class... Types>
zipper<special_decay_t<Types>...> zip(Types&&... args)

but your constructor is:

explicit zipper( T1& a, Ts&... b):
                    begin_( a.begin(), (b.begin())...), 
                    end_( a.end(), (b.end())...) {};

You can't call that with rvalues. If I tried to do zip(foo(), bar()), it wouldn't compile. Which is better than not working! But it'd be great if it could in fact be supported.

If you're not going to support it, you should change the signature to make that obvious:

template <class... Cs>
zipper<special_decay_t<Cs>...> zip(Cs&... containers)

const definitely isn't supported

Currently, a const container cannot be zipped. Say this example:

std::vector<int> v{1, 2, 3};
const std::vector<char> c{'a', 'b', 'c'};
zip(v, c); // error

This will fail to compile, for several reasons. First, you decay the types, so you're constructing a zipper<std::vector<int>, std::vector<char>>, so you can only fail from there - there's no way to ever get the right types. Next, you're using T::iterator when in this case we need const_iterator. And lastly, you're yielding value_type. Firstly, we want to yield reference (see first section), but in this case we need const_reference. So this will all need to be handled.

With C++11, you can use declval to get all of these more directly:

template <typename T>
using iter_t = decltype(std::declval<T&>().begin());

template <typename T>
using ref_t = decltype(*std::declval<iter_t<T>>());

And then current be std::tuple<iter_t<Ts...>> (see later on why I dropped T1), and you can yield std::tuple<ref_t<Ts...>>.

begin() and end() by ref?

This works fine if all you want to do is support iteration in a range-based for expression, but can lead to all sorts of broken code if people start using zipper as a normal container somewhere else. I think it'd be better to return by value.

Default Operations where possible

Your copy constructor does exactly what the default would do, so just make that clear:

zipper(const zipper& rhs) = default;

Your assignment operator is misleading. First, it is not the copy assignment operator (that one will be defaulted by the compiler, since the copy assignment operator is never a template). And why do you want to support assignment from arbitrary other zippers anyway? Is that ever going to be viable? Let's just default it:

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

Simplify the template

You have zipper<T1, Ts...>, but T1 is never special. You just use it to indicate you can't have zipper<>. But if you just make that a static_assert, you can shorten the rest of your code a lot:

template <class... Ts>
class zipper {
    static_assert(sizeof...(Ts) > 0, "!");

public:
    class iterator 
    : std::iterator<std::forward_iterator_tag,
        std::tuple<typename Ts::value_type...>
        >
    {
        ...
    };

    explicit zipper(Ts&... containers)
    : begin_(containers.begin()...)
    , end_(containers.end()...)
    { }

    // etc.
};

Iterator comparison

Your not_equals_tuple makes lots of intermediate objects. This is totally unnecessary. Rather than making a whole new pair of tuples for each element, just chop off the next index:

template <class Tuple>
bool any_equals(Tuple const&, Tuple const&, std::index_sequence<> ) {
    return false;
}

template <class Tuple, std::size_t I, std::size_t Is...>
bool any_equals(Tuple const& lhs, Tuple const& rhs, std::index_sequence<I, Is...> ) {

    return std::get<I>(lhs) == std::get<I>(rhs) ||          // this one
        any_equals(lhs, rhs, std::index_sequence<Is...>{}); // rest of them
}

bool operator==(iterator const& rhs) {
    return any_equals(current, rhs.current, std::index_sequence_for<Ts...>{});
}

bool operator!=(iterator const& rhs) { return !(*this == rhs); }

The Expander Trick

First of all, ct_integers_list and ct_iota_1 is reinventing the wheel. We have std::integer_sequence. If you don't have a C++14 compiler, just copy an implement of it from the web somewhere. It's super useful in all things metaprogramming, so it's helpful if everybody's using the same terms.

Next, you can write all sorts of "iterating-over-a-sequence" functions without having them be recursive. Take for instance increment:

template <class... Ts, std::size_t... Is>
void increment(std::tuple<Ts...>& tpl, std::index_sequence<Is...> ) {
    using expander = int[];
    expander{0,
        (void(
            ++std::get<Is>(tpl)
        ), 0)...
    };
}

template <class... Ts>
void increment(std::tuple<Ts...>& tpl) {
    increment(tpl, std::index_sequence_for<Ts...>{});
}

It takes a while to get used to, but once you do, everything is in the same place, and no enable_if necessary.

\$\endgroup\$
3
\$\begingroup\$

Some of your metaprogramming machinery is a bit over-complicated for C++11.

Compare:

template <size_t... n>
struct ct_integers_list {
    template <size_t m>
    struct push_back
    {
        typedef ct_integers_list<n..., m> type;
    };
};

template <size_t max>
struct ct_iota_1
{
    typedef typename ct_iota_1<max-1>::type::template push_back<max>::type type;
};

template <>
struct ct_iota_1<0>
{
    typedef ct_integers_list<> type;
};
template<std::size_t I = 0, typename... Tp>
inline typename std::enable_if<I == sizeof...(Tp), void>::type
increment(std::tuple<Tp...>& t)
{ }

template<std::size_t I = 0, typename... Tp>
inline typename std::enable_if<(I < sizeof...(Tp)), void>::type
increment(std::tuple<Tp...>& t)
{
    std::get<I>(t)++ ;
    increment<I + 1, Tp...>(t);
}

Versus:

template<size_t... n> struct ct_integers_list {};

template<size_t... acc> struct ct_iota_1;
template<size_t max, size_t... acc> struct ct_iota_1 : ct_iota_1<max-1, max-1, acc...> {};
template<size_t... acc> struct ct_iota_1<0, acc...> : ct_integers_list<acc...> {};

template<size_t... Indices, typename Tuple>
inline void increment_helper(Tuple& t, ct_integers_list<Indices...>)
{
    std::initializer_list<int>{
        [&]{ ++std::get<Indices>(t); return 0; }()...
    };
}

template<typename... Tp>
inline void increment(std::tuple<Tp...>& t)
{
    increment_helper(t, ct_iota_1<sizeof...(Tp)>());
}

The idea is to let parameter-pack expansion do for you all the things that in C++03 you had to do via foo<T>::type typedefs and std::enable_if and so on.

Basically, you can replace a lot of recursion with iteration (as in my increment_helper); and for the stuff that has to remain recursion, you can make it look a bit neater and avoid the proliferation of entities (à la Occam's Razor). If you don't need all those intermediate ct_iota_1<...>::type entities, get rid of them!

However, if you want a production-quality ct_integers_list, you should be using C++14's predefined std::integer_sequence, or at least an efficient implementation such as this one by Xeo. Compilers often limit template recursion to something like 256 levels; both your version and mine will quickly run into this limit, whereas Xeo's will work fine, because its recursion is O(log max) rather than O(max).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.