Writing an iterator for multiple lists

Question

I'm trying to write an iterator that iterates on multiple (sorted) lists. I have one that works but I'd like to improve it.

Here's what I have for now.

#ifndef __multi_iterator__
#define __multi_iterator__

#include <list>

template <typename T>
class multi_iterator
{
private:
    typedef typename std::list<T>::const_iterator iterator;
    typedef std::list<iterator> iterator_list;

public:
    multi_iterator();
    multi_iterator(const multi_iterator<T>& other);
    multi_iterator& operator = (const multi_iterator<T>& other);

    virtual ~multi_iterator();

    void add_list(const std::list<T>& it);

    const T& operator * ();
    multi_iterator<T>& operator ++ ();
    multi_iterator<T> operator ++ (int unused);
    bool operator == (const multi_iterator<T>& other);
    bool operator != (const multi_iterator<T>& other);


protected:
    iterator_list _it_list;
    iterator_list _end_list;

private:
    iterator& next();
};

template <typename T>
multi_iterator<T>::multi_iterator()
: _it_list()
{
}

template <typename T>
multi_iterator<T>::multi_iterator(const multi_iterator<T>& other)
: _it_list(other._it_list)
{
}

template <typename T>
multi_iterator<T>& multi_iterator<T>::operator = (const multi_iterator<T>& other)
{
    _it_list = other._it_list;
}

template <typename T>
multi_iterator<T>::~multi_iterator<T>()
{
}


template <typename T>
void multi_iterator<T>::add_list(const std::list<T>& l)
{
    _it_list.push_back(l.begin());
    _end_list.push_back(l.end());
}

template <typename T>
const T& multi_iterator<T>::operator * ()
{
    return *(next());
}

template <typename T>
multi_iterator<T>& multi_iterator<T>::operator ++ ()
{

    ++(next());

    return *this;
}

template <typename T>
typename multi_iterator<T>::iterator& multi_iterator<T>::next()
{
    typename iterator_list::iterator it = _it_list.begin();
    typename iterator_list::iterator end_it = _end_list.begin();
    typename iterator_list::iterator cur_it = _it_list.end();
    for (; it != _it_list.end(); ++it)
    {
        if (*it != *end_it)
        {
            if ((cur_it == _it_list.end()) || (**it < **cur_it))
            {
                cur_it = it;
            }
        }
        ++end_it;
    }

    return *cur_it;
}

template <typename T>
multi_iterator<T> multi_iterator<T>::operator ++ (int unused)
{
    return ++(*this);
}

template <typename T>
bool multi_iterator<T>::operator == (const multi_iterator<T>& other)
{
    return _it_list == other._it_list;
}

template <typename T>
bool multi_iterator<T>::operator != (const multi_iterator<T>& other)
{
    return !(*this == other);
}


#endif /* defined(__multi_iterator__) */

Here are the questions I've been pondering:

What should a C++ iterator do when it reaches the end (trying to look like stdlib). Throw an exception?
I don't think my keeping the list of iterator "ends" is elegant. Neither is my way to find if all iterators are at the end in next(). Does anyone have a cleaner solution?
Currently next() runs in linear time and is called for both * and ++ operators. I'm thinking I could save the current iterator and get the * operator to run in constant time. Also, If I sort my list each time I call ++, would ++ run in nlog(n)? I heard that this can be done in log(n) time and I can't really find a way to do that. What are your thoughts on complexity and optimization for this?

Good read: http://stackoverflow.com/questions/228783/what-are-the-rules-about-using-an-underscore-in-a-c-identifier — chris, May 20 '13 at 15:37
This is an intersting idea, but I don't see the application. Can you give us a use-case? — John Dibling, May 20 '13 at 15:40
There honestly isn't. I just picked up a list of "tough interview questions" I've been working on for the fun of it. — LodeRunner, May 20 '13 at 15:42
If you are interested in the requirements for creating iterators that conform to the C++ standard library you should take a look at [this page](http://en.cppreference.com/w/cpp/iterator) — Captain Obvlious, May 20 '13 at 15:42
Off-topic, but you shouldn't use [reserved names](http://stackoverflow.com/questions/228783) for your include guards. — Mike Seymour, May 20 '13 at 15:45
What exactly is this supposed to do? Interleave sorted lists by the total order of all elements? — Xeo, May 20 '13 at 16:09
@Xeo yes, I forgot to explain. I'll edit the question so it says that. — LodeRunner, May 20 '13 at 16:32

score 5 · Accepted Answer · edited May 23 '17 at 12:05

5

What you're trying to do is pretty well covered by zip iterators -- the Boost.Iterator library provides one. Check out their implementation.

You should also check out this discussion if you need to be able to add containers dynamically:

Zip Several Iterators in C++

edited May 23 '17 at 12:05

Community

1
1

answered May 20 '13 at 15:43

Nathan Monteleone

5,430
29
43

1

I don't think zip-iterators fit here. OP's iterator returns a single value on dereference, while zip iterators yield N values (in a tuple, normally), where N is the number of zipped ranged. – Xeo May 20 '13 at 16:18
@Xeo You are right, it's a little different. I think there are some aspects of zip iterator that are germane but I need to mod my answer... – Nathan Monteleone May 20 '13 at 16:25
@Xeo ... waiting on OP to see if it's supposed to be interleaved or sequential... – Nathan Monteleone May 20 '13 at 16:52

score 3 · Answer 2 · answered May 20 '13 at 15:55

3

What should a C++ iterator do when it reaches the end (trying to look like stdlib). Throw an exception?

It should become singular; that is, it must remain able to be compared with other iterators from the same sequence, but does not need to be dereferencable. Specifically, it must compare equal to another past-the-end iterator, and not equal to any non-singular iterator.

It certainly shouldn't throw an exception.

answered May 20 '13 at 15:55

Mike Seymour

249,747
28
448
644

So there is no defined behaviour for past-the-end iterators? What do STL past-the-end iterators do exactly, though? Specifically when dereferenced and incremented? – LodeRunner May 20 '13 at 15:59
1

@LodeRunner Past-the-end iterators cannot be dereferenced nor incremented, according to the standard. So iterator implementers need not care about this case (usually, they just fail and your program will eventually crash somehow). – Gorpik May 20 '13 at 16:07
So if checking for past-the-end iterators is done by comparison (using operator== against another past-the-end iterator), what's a good interface to get a reference past-the-end iterator? – LodeRunner May 20 '13 at 16:14
@LodeRunner: One possibility is to use a default-constructed iterator to represent the past-the-end point of any sequence. That's what standard stream iterators do, for example. – Mike Seymour May 20 '13 at 16:29

Writing an iterator for multiple lists

2 Answers2