爲多個列表編寫迭代器

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 ）。拋出異常？

它應該變成單數;也就是說，它必須能夠與來自相同序列的其他迭代器進行比較，但不需要無法引用。具體而言，它必須與另一個過去末端迭代器相比較，並且不等於任何非奇異迭代器。

它當然不應該拋出異常。