基于范围的for循环用于链表

Question

我有一个操作嵌套链表的函数。该函数如下：

void DoLiana(void) {

    PlotPointer plot;
    TreePointer tree;

        plot = FirstPlot;
        while (plot != nullptr) {
            tree = plot->FirstTree;
            while (tree != nullptr) {
                if (tree->isLiana) {
                    if (tree->attachedTree == nullptr && TestForLianaAttach(plot, tree))
                    DoLianaAttachement(plot, tree);
                }
                tree = tree->next;
            }
            plot = plot->next;
        }    
}

因为这种迭代在我的代码中发生了多次，所以我正在寻找一种使迭代更加紧凑和表达的方法。我读到在C++11中有基于范围的for循环可用于遍历集合。这个结构是否适用于这种情况？或者还有其他可能的方法来执行这些迭代吗？

- Manfredo

---

基于范围的for循环主要是语法糖，需要您拥有begin/end（更多细节请参见此处）。因此，您只需要以某种方式提供所需的接口即可。 - Borgleader

range-for循环可以迭代任何提供一对迭代器的东西。因此，请使您的类支持迭代。或者，只需使用std::list或std::slist来满足您的链表需求 - 这些类已经提供了必要的脚手架。 - Igor Tandetnik

没问题。您需要为容器提供 begin 和 end 方法，该方法将返回具有定义了 operator++() 和 operator== 的对象。我认为一个简单的指针就可以胜任。@IgorTandetnik 我认为 begin/end 返回的类型甚至不需要正式成为迭代器。 - luk32

但是你可以立即在这里使用基本循环：for (PlotPointer plot = FirstPlot; plot != nullptr; plot=plot.next) { for (TreePointer tree = plot->FirstTree, tree!= nullptr; tree=tree->next) { ... }}。 - Serge Ballesta

@luk32 我不确定一个“简单指针”是否适合这个任务：https://codereview.stackexchange.com/questions/74609/custom-iterator-for-a-linked-list-class - Bob__

@Bob__ 哦，是的。我犯了个错误。链表的存储很可能不是连续的，所以指针上的 ++ 不起作用。这就为实现一个迭代器提供了一个非常好的练习机会。 - luk32

Answer 1

是的，您可以为此定义适当的函数。

由于您提供的细节非常少，让我们做一些假设。

struct Tree
{
    bool  isLiana;
    void* attachedTree;
    Tree* next;
};

using TreePointer = Tree*;

struct Plot
{
    TreePointer FirstTree;
    Plot*       next;
};

using PlotPointer = Plot*;

bool TestForLianaAttach(PlotPointer, TreePointer);
void DoLianaAttachement(PlotPointer, TreePointer);

PlotPointer FirstPlot;

为了让指针正常工作，您需要为指针定义适当的begin()和end()方法。

NextIterator<Plot> begin(PlotPointer ptr)  {return make_NextIterator(ptr);}
NextIterator<Plot> end(PlotPointer)        {return make_NextIterator<Plot>();}

NextIterator<Tree> begin(TreePointer ptr)  {return make_NextIterator(ptr);}
NextIterator<Tree> end(TreePointer)        {return make_NextIterator<Tree>();}

基于范围的 for 循环会寻找能够与您的类型一起使用的 begin() 和 end() 函数。现在，标准库有默认的std::begin()和std::end()函数，它们会调用对象的begin()和end()方法。但是，您可以自己提供（如上所述）以针对您的类型/指针执行特殊操作。

现在，由于您的指针使用p = p->next;来推进，因此我们需要一个迭代器对象来完成这部分工作。在上面的代码中，我称其为NextIterator。定义它相对容易。

template<typename T>
struct NextIterator
{
    T* p;

    NextIterator():       p(nullptr) {}
    NextIterator(T* ptr): p(ptr)     {}

    NextIterator& operator++(){p = p->next;return *this;}

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

    bool operator==(NextIterator const& rhs) const {return p == rhs.p;}
    bool operator!=(NextIterator const& rhs) const {return p != rhs.p;}
};
template<typename T>
NextIterator<T> make_NextIterator(T* val)   {return NextIterator<T>(val);}
template<typename T>
NextIterator<T> make_NextIterator()         {return NextIterator<T>{};}

现在我们可以使用基于范围的for循环重写您的循环。

void DoLianaRange(void) {

        for(auto& plot: FirstPlot) {
            for(auto& tree: plot.FirstTree) {
                if (tree.isLiana) {
                    if (tree.attachedTree == nullptr && TestForLianaAttach(&plot, &tree))
                    DoLianaAttachement(&plot, &tree);
                }
            }
        }
}

请见以下内容，供参考对比。

void DoLiana(void) {

    PlotPointer plot;
    TreePointer tree;

        plot = FirstPlot;
        while (plot != nullptr) {
            tree = plot->FirstTree;
            while (tree != nullptr) {
                if (tree->isLiana) {
                    if (tree->attachedTree == nullptr && TestForLianaAttach(plot, tree))
                    DoLianaAttachement(plot, tree);
                }
                tree = tree->next;
            }
            plot = plot->next;
        }
}

或者您可以简单地使用标准的for循环！

void DoLianaForLoop(void) {

        for (PlotPointer plot = FirstPlot; plot != nullptr; plot = plot->next) {
            for (TreePointer tree= plot->FirstTree; tree != nullptr; tree = tree->next) {
                if (tree->isLiana) {
                    if (tree->attachedTree == nullptr && TestForLianaAttach(plot, tree))
                    DoLianaAttachement(plot, tree);
                }
            }
        }
}

将所有代码放在一个地方（按正确顺序编译）。

struct Tree
{
    bool  isLiana;
    void* attachedTree;
    Tree* next;
};

using TreePointer = Tree*;

struct Plot
{
    TreePointer FirstTree;
    Plot*       next;
};

using PlotPointer = Plot*;

template<typename T>
struct NextIterator
{
    T* p;

    NextIterator():       p(nullptr) {}
    NextIterator(T* ptr): p(ptr)     {}

    NextIterator& operator++(){p = p->next;return *this;}

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

    bool operator==(NextIterator const& rhs) const {return p == rhs.p;}
    bool operator!=(NextIterator const& rhs) const {return p != rhs.p;}
};

template<typename T>
NextIterator<T> make_NextIterator(T* val)   {return NextIterator<T>(val);}
template<typename T>
NextIterator<T> make_NextIterator()         {return NextIterator<T>{};}

NextIterator<Plot> begin(PlotPointer ptr)  {return make_NextIterator(ptr);}
NextIterator<Plot> end(PlotPointer)        {return make_NextIterator<Plot>();}

NextIterator<Tree> begin(TreePointer ptr)  {return make_NextIterator(ptr);}
NextIterator<Tree> end(TreePointer)        {return make_NextIterator<Tree>();}

bool TestForLianaAttach(PlotPointer, TreePointer);
void DoLianaAttachement(PlotPointer, TreePointer);

PlotPointer FirstPlot;

void DoLianaRange(void) {

        for(auto& plot: FirstPlot) {
            for(auto& tree: plot.FirstTree) {
                if (tree.isLiana) {
                    if (tree.attachedTree == nullptr && TestForLianaAttach(&plot, &tree))
                    DoLianaAttachement(&plot, &tree);
                }
            }
        }
}
void DoLiana(void) {

    PlotPointer plot;
    TreePointer tree;

        plot = FirstPlot;
        while (plot != nullptr) {
            tree = plot->FirstTree;
            while (tree != nullptr) {
                if (tree->isLiana) {
                    if (tree->attachedTree == nullptr && TestForLianaAttach(plot, tree))
                    DoLianaAttachement(plot, tree);
                }
                tree = tree->next;
            }
            plot = plot->next;
        }
}

- Martin York

---

@Caleth：如果你想让NextIterator符合迭代器的概念。基于范围的for循环并不要求类型是迭代器。 - Martin York

实际上，“make_NextIterator”似乎比它值得的麻烦多了。NextIterator<Plot> begin(PlotPointer ptr) {return ptr;}和NextIterator<Plot> end(PlotPointer ) {return nullptr;}更好。 - Caleth

@Caleth 但它符合一个很好的模式（由标准开始）。所以，是的，初始编写代码有点繁琐，但它提供了思维线索，并增加了对预期内容的文档说明。 - Martin York

它符合提供参数推导的模式（在shared_ptr的情况下，还可以优化分配）。你在这里不是在推断参数。 - Caleth

看看 make_pair()，make_tuple() 它们是相同的模式。 - Martin York

Answer 2

针对Serge Ballesta的评论，您可以立即在此处使用原始的for循环，以替换while循环。因此，您的示例代码将变为：

void DoLiana(void) {

    for (PlotPointer plot = FirstPlot; plot; plot = plot->next) { 
        for (TreePointer tree = plot->FirstTree; tree; tree = tree->next) {
            if (tree->isLiana && !tree->attachedTree && TestForLianaAttach(plot, tree)) {
                DoLianaAttachement(plot, tree);
            }
        }
    }
}

这样可以缩短代码，并增加隔离性和可读性。如果这是一个优势，它还可以保持与C的兼容性。

- Joseph Quinsey