2

基本的に、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

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またはGCC）がよくあります。-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リストを使用して開始します。

于 2011-06-24T09:05:23.123 に答える