How to make an iterator over several sorted lists?

Question

Ok, so this is an interview question that I got, and only performed mediocre on at the time. I am wondering what the optimal solution is and how it is best implemented.

You are given multiple sorted lists, construct something that allows us to iterate over all these lists from the smallest to the largest element.

Example:

{ -2, 5, 10}
{ 2, 9, 11}
{ -5, 9}


-> -5, -2, 2, 5, 9, 9, 10, 11

Update:

With a bit of help from the SO chat #c-questions-and-answers and @Nican in particular, I've gotten this ship to fly somehow. I have posted my working code as an answer to allow for other solutions as well.

The answer I have posted below is still messy, and in particular I have not implemented == and != correctly. I still need help on those.

Justification for this question

Finding clean and minimalistic custom iterator implementations online is not that common. And I believe this question may serve as a good starting point for others to enhance their understanding of iterators and best practices.

Answer 1

I think that SortedListsIter::iterator should contain a copy of all the items, rather than reference, so that you can be ForwardIterator instead of InputIterator. You also avoid the dangling reference in the end iterator (which can be a default constructed iterator, as iterator::iterator(std::vector<SortedListIterItem<Iter> > _items = {}) : m_items(_items){};)

Two heaps may differ in order of elements, so we use std::is_permutation to determine equality

bool SortedListsIter::iterator::operator==(iterator other) 
{ return std::is_permutation(m_items.begin(), m_items.end(), other.m_items.begin(), other.m_items.end()); } 

C++11 alternative (4 iterator version that checks distance isn't available):

bool SortedListsIter::iterator::operator==(iterator other) 
{ return (std::distance(m_items.begin(), m_items.end()) == std::distance(other.m_items.begin(), other.m_items.end())) 
      && std::is_permutation(m_items.begin(), m_items.end(), other.m_items.begin()); } 

Item equality is simple:

bool SortedListIterItem::operator==(SortedListIterItem other) 
{ return (it_beg == other.it_beg) && (it_end == other.it_end); }