2

基本上，我正在创建一个基类，该基类将用于存储为链表的类，这些类将按照返回布尔值的虚拟 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

4

1 回答 1

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在那里改变。

编辑：我想说的是，无论你如何编码，最终由编译器决定是否要对函数进行尾部优化。对于现代优化编译器，通常有一些开关（-fconserve-stack或-foptimize-sibling-calls在 GCC 中）对此产生的影响比源代码本身更直接。

编辑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 列表开始。

于 2011-06-24T09:05:23.123 回答