4

我正在尝试编写一个迭代多个（排序）列表的迭代器。我有一个可以工作，但我想改进它。

这就是我现在所拥有的。

#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) 时间内完成，但我真的找不到办法做到这一点。您对此的复杂性和优化有何看法？

4

2 回答 2

5

zip 迭代器很好地涵盖了您想要做的事情——Boost.Iterator 库提供了一个。查看他们的实现。

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

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

于 2013-05-20T15:43:52.650 回答
3

当 C++ 迭代器到达末尾时应该做什么（试图看起来像 stdlib）。抛出异常？

它应该变成单数；也就是说，它必须保持能够与来自同一序列的其他迭代器进行比较，但不需要是可解引用的。具体来说，它必须与另一个过去的迭代器进行比较，并且不等于任何非奇异迭代器。

它当然不应该抛出异常。

于 2013-05-20T15:55:24.050 回答