#include <iostream>
#include <vector>
#include <deque>
using namespace std;

class nested_deque_iterator 
{
    vector<deque<int>::const_iterator>            iterators;
    vector<deque<int>::const_iterator>            ends;
    vector<deque<int>::const_iterator>::iterator  current;
    bool                                          at_end = false;
    
public:
    nested_deque_iterator(vector<deque<int>::const_iterator> iterators,
                          vector<deque<int>::const_iterator> ends) :
		iterators(iterators),
		ends(ends)
    {
    	update_current();
    }

    int operator *() const {
	    return **current;
	}
	nested_deque_iterator& operator++() {
	    if (!at_end) {
	    	++(*current);
	        update_current();
	    }
	    return *this;
	}
	nested_deque_iterator operator++(int) {
	    nested_deque_iterator old(*this);
	    ++(*this);
	    return old;
	}
	bool operator==(const nested_deque_iterator &o) const {
		// If either iterator is at the end, don't dereference current!
		if (at_end || o.at_end)
			return at_end == o.at_end;
	    return *current == *(o.current);
	}
	bool operator!=(const nested_deque_iterator &o) const {
	    return !(*this == o);
	}
    
private:
    void update_current() {
	    if (!at_end && iterators.size() > 0) {
	        // At the beginning, we assume that we didn't find any
	        // new "next smaller element" in any deque.
	        at_end = true;
	
	        // Iterate through the deques (with two iterators in parallel)
	        for (auto i = iterators.begin(), e = ends.begin();
	             i != iterators.end() && e != ends.end();
	             ++i, ++e)
	        {
	            // We ignore deques which are already at their end
	            if (*i != *e) {
	                // If we found a smaller next element (or the first try)...
	                if (at_end || **i < **current) {
	                    // ... then replace the current iterator with it:
	                    at_end = false;
	                    current = i;
	                }
	            }
	        }
	    }
	}
};

//-----------------------------------------------------------------------------

nested_deque_iterator nested_deque_begin(const deque<deque<int>> & deques) {
    vector<deque<int>::const_iterator>   iterators;
    vector<deque<int>::const_iterator>   ends;
    for (const auto & d : deques) {
        iterators.push_back(d.begin());
        ends.push_back(d.end());
    }
    return { iterators, ends };
}

nested_deque_iterator nested_deque_end(const deque<deque<int>> & deques) {
    vector<deque<int>::const_iterator>   ends;
    for (const auto & d : deques) {
        ends.push_back(d.end());
    }
    return { ends, ends };
}

//-----------------------------------------------------------------------------

struct nested_deque {
    deque<deque<int>> deques;
};

nested_deque_iterator begin(const nested_deque & nd) {
    return nested_deque_begin(nd.deques);
}
nested_deque_iterator end(const nested_deque & nd) {
    return nested_deque_end(nd.deques);
}

//-----------------------------------------------------------------------------

int main() {
    deque<deque<int>> deques;
    // until 40, here we have the powers of two:
	deques.push_back(deque<int>{1,2,4,8,16,32});
	// ..and the prime numbers:
	deques.push_back(deque<int>{2,3,5,7,11,13,17,19,23,29,31,37});
	
	// Here we make use of the adaptor which overloads begin() and end():
	for (int i : nested_deque{deques})
	    cout << i << ' ';
	
	return 0;
}