为多个列表编写迭代器

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库提供了一个.看看他们的实施.

如果您需要能够动态添加容器,还应该查看此讨论:

在C++中压缩几个迭代器