template<class Container>
struct combine
{
    typedef typename Container::iterator CIt;
    struct It : CIt
    {
        CIt end1_, begin2_;
        bool withinC2_;
        It(const CIt& it, const CIt& end1, const CIt& begin2, bool withinC2)
            : CIt(it), end1_(end1), begin2_(begin2), withinC2_(withinC2) {}
        It& operator++()
        {
            CIt::operator++();
            if (!withinC2_ && static_cast<const CIt&>(*this) == end1_)
            {
                CIt::operator=(begin2_);
                withinC2_=true;
            }
            return *this;
        }
        bool operator==(const It& rhs) const { return withinC2_ == rhs.withinC2_ && static_cast<const CIt&>(*this) == rhs; }
        bool operator!=(const It& rhs) const { return withinC2_ != rhs.withinC2_ || static_cast<const CIt&>(*this) != rhs; }
    private:
        It operator++(int); // undefined
    };
    typedef It iterator;

    Container &c1_, &c2_;
    combine(Container& c1, Container& c2) : c1_(c1), c2_(c2) {}
    It begin()
    {
        if (c1_.empty())
            return It(c2_.begin(), c1_.end(), c2_.begin(), true);
        return It(c1_.begin(), c1_.end(), c2_.begin(), false);
    }
    It end() { return It(c2_.end(), c1_.end(), c2_.begin(), true); }
};

// some performance measurement
int main()
{
    list<int> l(10000000), l2(10000000);
    long before, after;
    
    before = clock();
    for(auto it = l.begin(), e = l.end(); it != e; ++it)
        *it = rand();
    for(auto it = l2.begin(), e = l2.end(); it != e; ++it)
        *it = rand();
    after = clock();
    cout << after-before << endl;

    before = clock();
    combine<list<int>> c(l,l2);
    for(auto it = c.begin(), e = c.end(); it != e; ++it)
        *it = rand();
    after = clock();
    cout << after - before << endl;
}