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

This is not a complete answer

I've implemented a partly solution to the point that it works. This is not a complete, nor correct implementation in lines with the requirements of a input_iterator. This illustrates the point, and the remaining legwork is up to whoever feels the call.

--

I just picked this up again from my notes and efforts yesterday. I've gotten some really nice help from Nican.

I'm using a heap to keep the lists inside my structure. (Which has the valid critique that I am reinventing the priority_queue). There are several things still missing here, among other things:

• Copy constructor
• Post-fix ++ operator
• Proper == and != implementation, I'm only comparing size.
• This could easily be a forward_iterator.

I got to the point where I've built my understanding of iterators. And this is as far as I'm going to take it this time around.

#include <algorithm>
#include <forward_list>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>

template <typename Iter>
struct SortedListIterItem {
  Iter it_beg;
  Iter it_end;
  /* Used by the heap to sort ascending */
  bool operator<(const SortedListIterItem<Iter>& other) {
    return *it_beg > *other.it_beg;
  }
  bool operator==(const SortedListIterItem<Iter>& other) {
    return it_beg == other.it_begin && it_end == *other.it_beg;
  }
  SortedListIterItem<Iter>(Iter _begin, Iter _end)
      : it_beg(_begin), it_end(_end){};
};

template <typename Iter>
class SortedListsIter {
  // member typedefs provided through inheriting from std::iterator
  class iterator {
    std::vector<SortedListIterItem<Iter> > m_items;

   public:
    iterator(std::vector<SortedListIterItem<Iter> > _items = {})
        : m_items(_items){};
    iterator& operator++() {
      std::pop_heap(m_items.begin(), m_items.end());
      SortedListIterItem<Iter>& largest = m_items.back();

      if (++largest.it_beg == largest.it_end) {
        m_items.pop_back();
      } else {
        std::push_heap(m_items.begin(), m_items.end());
      }
      return *this;
    }
    // iterator traits
    using value_type = typename Iter::value_type;
    using pointer = typename Iter::pointer;
    using reference = typename Iter::reference;
    using iterator_category = std::input_iterator_tag;
    /** A simplified comparator, which is not a correct implementation.
     *  While it does work for regular for loops. */
    bool operator!=(iterator other) { 
      return (m_items.size() != other.m_items.size());
    }
    value_type operator*() const { 
      return *(m_items.front().it_beg); 
    };
  };
  std::vector<SortedListIterItem<Iter> > m_items;

 public:
  void add_list(Iter it_begin, Iter it_end) {
    if (it_begin != it_end) {
      m_items.push_back(SortedListIterItem<Iter>(it_begin, it_end));
      std::push_heap(m_items.begin(), m_items.end());
    }
    // Ignore empty lists.
  }
  iterator begin() { return iterator(m_items); };
  iterator end() {
    std::vector<SortedListIterItem<Iter> > _items;
    return iterator(_items);
  };
};

int main(int argc, char** argv) {
  std::forward_list<std::string> animals = {"Cat", "Dog", "Horse"};
  std::forward_list<std::string> fish = {"Dolphin", "Mermaid", "Shark"};
  std::forward_list<std::string> birds = {"Crow", "Duck", "Eagle"};
  SortedListsIter<std::forward_list<std::string>::iterator> my_string_iter;
  my_string_iter.add_list(fish.begin(), fish.end());
  my_string_iter.add_list(animals.begin(), animals.end());
  my_string_iter.add_list(birds.begin(), birds.end());

  for (auto i : my_string_iter) {
    std::cout << " " << i << ",";
  }
  std::cout << std::endl;
  for (auto i : my_string_iter) {
    std::cout << " " << i << ",";
  }
  std::cout << std::endl;

  std::vector<int> l4 = {1, 2, 99};
  std::vector<int> l5 = {-11, -4, 3};
  std::vector<int> l6 = {-5, 1};

  SortedListsIter<std::vector<int>::iterator> my_iter2;
  my_iter2.add_list(l4.begin(), l4.end());
  my_iter2.add_list(l5.begin(), l5.end());
  my_iter2.add_list(l6.begin(), l6.end());

  for (auto i : my_iter2) {
    std::cout << " " << i << ",";
  }
  std::cout << std::endl;

  return 0;
}

Answer 2

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); }