#include <iterator>
#include <stdexcept>

template <class Range> class MultiRangeIterator;
template <class Iterator, class SubRange>
struct MultiRange;

template <class E> struct EmptyRange 
{ 
  typedef MultiRangeIterator<EmptyRange<E>> iterator;
  iterator begin();
  iterator end(); 

  template <class NewIter>
  struct Append
  {
    typedef MultiRange<NewIter, EmptyRange<E>> type;
  };

  template <class NewIter>
  typename Append<NewIter>::type append(NewIter first, NewIter last) const;
};

template <class Iterator, class SubRange = EmptyRange<typename Iterator::value_type>>
struct MultiRange
{
  Iterator first;
  Iterator last;
  SubRange deeper;

  template <class NewIter>
  struct Append {
    typedef MultiRange<Iterator, typename SubRange::template Append<NewIter>::type> type;
  };
 
  typedef MultiRangeIterator<MultiRange> iterator;
  MultiRange(Iterator a, Iterator b, SubRange s = SubRange())
    : first(a), last(b), deeper(s) {}

  iterator begin();
  iterator end();

  template <class NewIter>
  typename Append<NewIter>::type operator()(NewIter newFirst, NewIter newLast) const
  { return this->append(newFirst, newLast); }

  template <class NewIter>
  typename Append<NewIter>::type append(NewIter newFirst, NewIter newLast) const
  { 
    typedef typename Append<NewIter>::type NewMultiRange;
    return NewMultiRange(first, last, deeper.append(newFirst, newLast));
  }
};

template <class E>
  template <class NewIter>
typename EmptyRange<E>::template Append<NewIter>::type EmptyRange<E>::append(NewIter first, NewIter last) const
{
  return MultiRange<NewIter,EmptyRange<E>>(first, last);
}

template <class Iterator>
MultiRange<Iterator> makeRange(Iterator first, Iterator last)
{ return MultiRange<Iterator> (first, last); }

template <class E>
struct MultiRangeIterator<EmptyRange<E>>
{
  E& operator*() const { throw std::out_of_range("past the end!"); }
  MultiRangeIterator& operator++() { return *this; }
};

template <class Iterator, class SubRange>
struct MultiRangeIterator<MultiRange<Iterator, SubRange>>
{
  MultiRange<Iterator, SubRange> const& myRange;
  Iterator myIter;
  MultiRangeIterator<SubRange> deeperIter;

  typedef typename std::iterator_traits<Iterator>::reference reference;

  MultiRangeIterator(MultiRange<Iterator, SubRange> const& r, Iterator it, MultiRangeIterator<SubRange> d )
    : myRange(r), myIter(it), deeperIter(d) {}

  bool pastEndOfRange() const
  { return myIter == myRange.last; }
   
  reference operator*() const 
  { return pastEndOfRange() ? 
      *deeperIter : 
      *myIter; }

  MultiRangeIterator& operator++() 
  { 
    if (!pastEndOfRange())
      ++myIter;
    else
      ++deeperIter;
    return *this;
  }
}; 

namespace std {
  template <class Iterator, class SubRange>
  struct iterator_traits<MultiRangeIterator<MultiRange<Iterator, SubRange>>>
    : std::iterator_traits<Iterator>
  {};
};

template <class Iterator, class SubRange>
bool operator== (MultiRangeIterator<MultiRange<Iterator, SubRange>> const& lhs,
  MultiRangeIterator<MultiRange<Iterator, SubRange>> const& rhs)
{ return lhs.myIter == rhs.myIter && lhs.deeperIter == rhs.deeperIter; }

template <class E>
bool operator == (MultiRangeIterator<EmptyRange<E>> const& lhs,
  MultiRangeIterator<EmptyRange<E>> const& rhs)
{ return true; }

template <class Range>
bool operator != (MultiRangeIterator<Range> const& lhs, MultiRangeIterator<Range> const& rhs)
{ return !(lhs==rhs); }

template <class Iterator, class SubRange>
typename MultiRange<Iterator, SubRange>::iterator
MultiRange<Iterator, SubRange>::begin()
{ return iterator(*this, first, deeper.begin()); }

template <class Iterator, class SubRange>
typename MultiRange<Iterator, SubRange>::iterator
MultiRange<Iterator, SubRange>::end()
{ return iterator(*this, last, deeper.end()); }

template <class E>
typename EmptyRange<E>::iterator
EmptyRange<E>::begin()
{ return iterator(); } 
template <class E>
typename EmptyRange<E>::iterator
EmptyRange<E>::end()
{ return iterator(); } 


#include <vector>
#include <list>
#include <set>
#include <iostream>
#include <string>
#include <sstream>
#include <iterator>

/* nur zu Testzwecken...
template <class E>
char const* debug(MultiRangeIterator<EmptyRange<E>>) {return "()";}

template <class Iterator, class SubRange>
std::string debug(MultiRangeIterator<MultiRange<Iterator, SubRange>> const& mri)
{ 
  std::ostringstream out;
  out << '(' << std::distance(mri.myRange.first, mri.myIter);
  if (mri.pastEndOfRange()) out << "=end";
  out << debug(mri.deeperIter) << ')';
  return out.str();
} */

using namespace std;

int main()
{
  vector<int> vi = {1,2,3,4};
  list<int> li = {5,6,7,8};
  list<int> li2 = {9,10};
 
  auto myRange = makeRange(vi.begin(), vi.end())
       (li.begin(), li.end());

  auto newRange = myRange.append(myRange.begin(), myRange.end())
       (li2.begin(), li2.end());

  for(auto it = newRange.begin(); it != newRange.end(); ++it)
  { 
    //    cout << debug(it) << ": "; 
    cout << *it << ','; 
  }
}