Является ли это наилучшим способом использования рекурсии хвостового вызова, пересекающей связанный список?

Question

В основном я создаю базовый класс, который будет использоваться для классов, хранящихся в виде связанного списка, которые просматриваются и удаляются в соответствии с виртуальной функцией update (), которая возвращает bool.

Мне интересноесли это наиболее эффективный случай (мне нравится тот факт, что это может быть, в частности, односвязный список):

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 там.

Edit: , что я пытаюсь сказать, это то, что независимо от того, как вы его кодируете, вВ конце концов, это зависит от компилятора, который решает, хочет ли он оптимизировать функцию или нет.Для современных оптимизирующих компиляторов часто есть переключатели (-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 для начала.