c++ - 如何实现 'square list' 迭代器

Question

我正在使用 C++ 实现一个方形列表，它是双向链表的双向链表。列表已排序，想法是在插入和删除元素时结构保持正方形的形状。如果列表总共有四个元素，则该正方形将为 2x2 形状。

看起来像这样:

我对链表做了一些研究，了解到一般的想法是创建节点来保存每个数据元素，以及指向和来自周围元素的指针，但让我失望的一件事是我会如何(或可以)实现一个迭代器来遍历方形列表。

这是我第一次尝试构建数据结构，所以这个过程总体上对我来说很陌生。任何提示表示赞赏!

Answer 1

您需要做出一些设计决策，例如整个迭代依次耗尽每个“内部”列表是否重要，或者是否应该返回所有内部列表的第一个元素，然后是第二个等等。

作为对如何实现这个的尝试:

#include <iostream>
#include <list>

template <typename T>
struct Iterator
{
    typedef typename std::list<std::list<T> >::iterator outer_iterator;
    typedef typename std::list<T>::iterator inner_iterator;

    outer_iterator outer_;
    bool inner_initialised_;
    inner_iterator inner_;

    Iterator(outer_iterator begin)
      : outer_(begin), inner_initialised_(false)
    { }

    T& operator*()
    {
        if (!inner_initialised_)
        {
            inner_ = outer_->begin();
            inner_initialised_ = true;
        }
        return *inner_;
    }

    T& operator->() { return operator*(); }

    Iterator& operator++()
    {
        if (++inner_ == outer_->end())
        {
            ++outer_;
            inner_initialised_ = false;
        }
        return *this;
    }

    bool operator!=(outer_iterator i) const { return outer_ != i; }
};

int main()
{
    std::list<std::list<int>> lli;
    std::list<int> li;
    li.push_back(42);
    li.push_back(13);
    lli.push_back(li);
    li.push_back(999);
    lli.push_back(li);
    for (Iterator<int> i = lli.begin(); i != lli.end(); ++i)
        std::cout << *i << ' ';
    std::cout << '\n';
}

输出:

42 13 42 13 999

注意 bool inner_initialised_变量 - 它确保不会尝试调用 ->begin()在等于 end() 的外部迭代器值上.

您可能想用 operator== 充实一下, ++(int) , -- , 一个 const const_iterator 的版本s 等更一般的用法。我通常会使自定义迭代器类成为自定义容器类的成员，提供 begin()和 end()产生自定义迭代器对象，但我不确定您是否打算拥有一个实际的“方形列表”类或只使用 list<list<T>>到处。