c++ - 这是利用尾调用递归遍历链表的最佳方式吗？

Question

基本上我正在创建一个基类，该基类将用于存储为链表的类，这些类按照返回 bool 值的虚拟 update() 函数的指示进行遍历和删除。

我想知道这是否是最有效的情况(我特别喜欢它可以是单链表这一事实):

class Traversable
{
    public:
        Traversable();
        virtual ~Traversable();
        void traverse(Traversable** prevNext);
        virtual bool update()=0;
    protected:
    private:
        Traversable* next;
};


void Traversable::traverse(Traversable** prevNext)
{
    if (!update()) /// Virtual function that returns a death flag
    { /// Death
        if (next)
        {
            Traversable* localNext = next;
            delete this;
            localNext->traverse(prevNext);
        }
        else
        {
            *prevNext = NULL;
            delete this;
        }
    }
    else
    { /// This node stays alive, for now
        *prevNext = this;
        if (next)
        {
            next->traverse(&next);
        }
    }
}

注意链表以 NULL 终止。

我认为在调用下一个遍历函数后小心地缺少对局部变量的赋值操作将确保使用尾调用使用该函数。谁能发现我做错了什么，或者建议一种稍微不那么复杂的方法:p

Answer 1

您故意混淆代码以“引诱”编译器创建特定结果；这种情况是否发生很可能更多地取决于所使用的编译器、有效的优化标志，甚至是使用上述编译器编译的代码。下面是更简洁的代码:

void Traversable::traverse(Traversable** prevNext)
{
    bool doUpdate = update();

    *prevNext = doUpdate ? this : next ? *prevNext : NULL;

    Traversable **argNext = doUpdate ? &next : prevNext;
    Traversable *localNext = next;

    do_the_traversal_action();     // not spec'ed ...

    if (!doUpdate)
        delete this;
    if (localNext)
        localNext->traverse(argNext);
}

并且仍然以单个尾部返回点结束函数。这使用条件的唯一原因是因为您要在其中更改 prevNext。

编辑:我想说的是，无论您如何编写代码，最终都由编译器决定是否要对函数进行尾部优化。对于现代优化编译器，通常有开关(GCC 中的 -fconserve-stack 或 -foptimize-sibling-calls)比源代码本身对此有更直接的影响.

编辑 2: 是的，如果可以非递归地编写此函数；最后，它只是一种访问者类型模式。所以实际的事件最终是这样的:

static void Traversable::traverse(Traversable *start)
{
    Traversable *cur, *next;

    for (cur = start; cur; cur = next) {
        next = cur->next;

        cur->do_the_traversal_action();     // not spec'ed ...

        if (cur->update())
            continue;                       // not supposed to remove this

        if (next)
            next->prevNext = cur->prevNext; // remove cur from list
        delete cur;
    }
}

尽管如此，当您这样编写代码时，下一个明显的问题是为什么不为 Traversable 实现简单的迭代器类型并使用 std::remove_copy_if()条件访问和删除任务。或者使用 STL 列表作为开始。