Chaining function for range-based for loop

Question

Motivation: I'm relatively new to C++. I'm writing a function meant to be used with range-based for loops. The goal is to be able to iterate over multiple containers at once, each in turn (essentially Python's itertools.chain), with as littler overhead as possible (e.g. no copying containers).

Usage:

vector<int> a = {1, 2, 3, 4};
vector<int> b = {5, 6, 7, 8};
list<int> c = {9, 9, 4};
for (auto& i : chain_it(a, b, a, b, c)) { 
    cout << i << " "; 
}

This should print out:

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 9 4 

Implementation:

Working example also available at ideone.

#include <memory>
#include <iterator>
#include <type_traits>

template <typename T>
struct ref_or_copy
{
    ref_or_copy(T&& rval) 
        : storage(new T(std::move(rval)))
        , val(*storage) { }
    ref_or_copy(T& lval) : val(lval) { }

    std::unique_ptr<T> storage;
    T& val;
};

template <typename C1, typename C2>
struct chain_obj_struct {
  ref_or_copy<std::remove_reference_t<C1>> c1;
  ref_or_copy<std::remove_reference_t<C2>> c2;
  struct iterator {
    decltype(std::begin(c1.val)) it1;
    decltype(std::begin(c1.val)) it1_end;
    decltype(std::begin(c2.val)) it2;
    bool in_first;

    iterator& operator++() {
      if (in_first) {
        ++it1;
        if (it1 == it1_end) {
          in_first = false;
        }
      } else { 
        ++it2;
      }
      return *this;
    }

    typename std::conditional<
        std::is_const<std::remove_reference_t<decltype(*it1)>>::value,
        decltype(*it1), decltype(*it2)>::type
    operator*() 
    {
      if (in_first) return *it1;
      return *it2;
    }

    bool operator==(const iterator& i2) { 
      if (in_first != i2.in_first) return false;
      if (in_first)
        return it1 == i2.it1;
      else
        return it2 == i2.it2;
    }
    bool operator!=(const iterator& i2) {
        return !this->operator==(i2);
    }
  };

  iterator begin() {
    return iterator{std::begin(c1.val), std::end(c1.val), std::begin(c2.val), true};
  }

  iterator end() {
    return iterator{std::end(c1.val), std::end(c1.val), std::end(c2.val), false};
  }
};

template <typename C1, typename C2>
chain_obj_struct<C1, C2> chain_obj(C1&& c1, C2&& c2) {
    return chain_obj_struct<C1, C2>{std::forward<C1>(c1), std::forward<C2>(c2)};
}

template <typename C>
auto chain_it(C&& c) { return std::forward<C>(c); }

template <typename C1, typename C2, typename... Cs>
auto chain_it(C1&& c1, C2&& c2)
{
    return chain_obj(std::forward<C1>(c1), std::forward<C2>(c2));
}

template <typename C1, typename... Cs>
auto chain_it(C1&& c1, Cs&&... cs)
{
    return chain_obj(std::forward<C1>(c1), chain_it(std::forward<Cs>(cs)...));
}

Explanation:

chain_obj_struct is a basic container which implements just what is needed for the range-based for loop to work. It implements begin() and end() which return the iterators that end up iterating across both ranges.

Most of the logic is in chain_obj_struct::iterator which implements preincrement, unary *, and equality/inequality. This code is pretty straightforward, except for the return type of unary *, which picks the more consty return type.

chain_obj is the helper function to create chain_obj_structs without having to specify types.

I ran into a difficulty when chaining chain objects, that is, when trying something like this:

for (auto& i : chain_obj(a, chain_obj(b, a)) { ... }

Initially chain_obj just took references of its parameters. It appeared that the temporary chain_obj_struct returned by chain_obj(b, a) would get destructed and the code would segfault. However, I absolutely did not want to make a copy of the container being iterated over until absolutely necessary. But I wasn't sure how to take a reference if I could, but copy the object if I had to.

My solution was the ref_or_copy helper struct which keeps a reference if it can (ref_or_copy(T& lval) constructor) or stores a local copy if it must (ref_or_copy(T&& rval) constructor). With the former constructor the only overhead is for a null std::unique_ptr. chain_obj_struct thus keeps ref_or_copys around which do the best they can.

The rest is just the chain_it variadic template implementation which does perfect forwarding as necessary.

Questions:

• Was the ref_or_copy a good/necessary approach (i.e. is there a better way to do that)?
• Does this code follow best practices in general?
• Any other comments in particular?

Answer 1

Starting from the top.

ref_or_copy

Firstly, it's an odd name, since we're never copying. We're either referring or moving. But secondly, it's bigger than it needs to be, and incurs allocation overhead. We can hugely simplify this changing:

template <typename T>
struct ref_or_copy
{ ... };

ref_or_copy<std::remove_reference_t<C1>> c1;
ref_or_copy<std::remove_reference_t<C2>> c2;

into:

C1 c1;
C2 c2;

Wait what? Consider the usage like:

template <typename T>
T wrapped(T&& val) { return T{std::forward<T>(val)}; }

In the lvalue case, T will be some type U&, so we're referring to the passed in val. In the rvalue case, T will be some type V, so we'll be move-constructed from val. Everything checks out.

What about non-member begin?

This is definitely the Forgot About Dre of C++11 container programming:

struct Foo {
    int arr[2]{10, 11};
};

int* begin(Foo& f) { return f.arr; }
int* end(Foo& f) { return f.arr + 2; }

Foo d;
for (auto i : chain_it(d, d)) { // error: no matching function call to 'begin'
}

Where you use std::begin and std::end, you'll have to make unqualified calls with the std:: functions in scope in order to do the right thing.

Chain of one

If try to do:

std::vector<int> a = {1, 2, 3, 4};
for (int& i : chain_it(a)) { ++i; }

I would be quite surprised when a[0] was still 1 at the end. I'd also be surprised that this doesn't compile:

int d[] = {10, 11};
for (int& i : chain_it(d)) { ... }

Since the last container always gets chain_it()-ed as one, this is a serious issue. Both have the same root cause. The overload of chain_it that takes a single argument has the wrong return type:

template <typename C>
auto chain_it(C&& c) { return std::forward<C>(c); }

For the vector, we're copying it. And for the array, we're decaying it and ending up with a pointer. We want to return an lvalue reference for lvalue references, and a value for rvalue references. That is, trivially:

template <typename C>
C chain_it(C&& c) { return std::forward<C>(c); }