c++ - 为多个列表编写迭代器

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++