Запись итератора для нескольких списков

Question

Я пытаюсь написать итератор, который выполняет итерации в нескольких (отсортированных) списках. У меня есть тот, который работает, но я бы хотел его улучшить.

Вот что у меня на данный момент.

#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__) */ 

Вот вопросы, я размышлял:

1. Что должен ++ итераторы C делать, когда он доходит до конца (пытаясь выглядеть STDLIB). Выбросить исключение?

2. Я не считаю, что мой список итераторов «концов» изящный. Я также не могу найти, все ли итераторы заканчиваются в next(). У кого-нибудь есть более чистое решение?

3. В настоящее время next() работает в линейном времени и вызывается для операторов * и ++. Я думаю, что могу сохранить текущий итератор и заставить оператор * работать в постоянное время. Кроме того, если я сортирую свой список каждый раз, когда я вызываю ++, будет ли работать в nlog (n)? Я слышал, что это можно сделать в log (n) времени, и я не могу найти способ сделать это. Каковы ваши мысли о сложности и оптимизации для этого?

Answer 1

То, что вы пытаетесь сделать, довольно хорошо покрывается итераторами zip - библиотека Boost.Iterator предоставляет один. Проверьте их реализацию.

Вы должны также проверить это обсуждение, если вам нужно, чтобы иметь возможность добавлять контейнеры динамически:

Zip Several Iterators in C++

Answer 2

Что должен C++ итераторы делать, когда он доходит до конца (пытаясь выглядеть STDLIB). Выбросить исключение?

Должно быть исключительное; то есть он должен оставаться способным сравниваться с другими итераторами из одной и той же последовательности, но не обязательно должен быть разборчивым. В частности, он должен сравниваться с другим итератором прошлого и не равен никакому неособым итерам.

Это, безусловно, не должно вызывать исключения.