Есть ли простой способ поместить переменные в стек для последующего поиска - PullRequest
Новая
       8

Есть ли простой способ поместить переменные в стек для последующего поиска

1 голос
/ 17 декабря 2009

У меня есть функция-член объекта, которая обычно используется итеративно, но иногда рекурсивно. Эта функция в основном следует по пути потока воды под гору, и при определенных условиях поток может расколоться. Чтобы поддержать случайную рекурсию, я должен поместить состояние объекта в стек и вытащить его после слов. В настоящее время я делаю это с использованием локальных переменных, но код выглядит ужасно. Я хотел бы написать члены PushState и PopState, но большинство реализаций, на которые я смотрел, не очень хороши. например использование члена стека в моем объекте, который в конечном итоге использует кучу, которая медленная и приводит к другим проблемам. _alloca не будет работать, так как кадр стека теряется при возврате функции push.

Существуют ли другие разумные способы выталкивания и выталкивания из стека, которые мне не хватает? 

class CMyObject
{   
    enum Direction
    {
      left,right,branch,finished;
    }

    // state variables
    double m_XPos,m_YPos;

    void    Navigate(double x,double y);
    Direction GoLeft();
    Direction GoLeft();
};

void    CMyObject::Navigate(double x,double y)
{
    m_XPos = x; m_YPos = y;

    Direction d = GoLeft(x,y);
    while(d != finished)
    {
        switch(d)
        {
            case left: d = GoLeft(); break;
            case right: d = GoRight(); break;
            case branch:
            {
                // push object state onto the stack
                double temp_x = m_XPos; double temp_y = m_YPos;
                Navigate(m_XPos,m_YPos);
                // pop object state from the stack
                m_XPos = temp_x; m_YPos = temp_x;
                GoRight();
            } break;
        }
    }
}

Ответы [ 3 ]

2 голосов
/ 17 декабря 2009

Полагаю, очевидным способом было бы создать копию всего объекта и выполнить рекурсивный вызов для этого. Таким образом, каждая ветвь имеет свое собственное состояние, и ваш компилятор выполняет управление стеками за вас. По сути, метод должен быть reentrant , чтобы его можно было безопасно использовать в рекурсии. Это не тот случай, поскольку ваши методы основаны на постоянном состоянии. Таким образом, вы должны скопировать это состояние, а это означает копирование объекта.

UPDATE:

Еще несколько ссылок о рекурсии и повторном входе:

К сожалению, Дональд Кнут еще не закончил четвертую часть своего шедевра , но когда он это сделает, прочитайте его, потому что это, безусловно, ясно.

1 голос
/ 17 декабря 2009

Я думаю, что вам могут понадобиться два объекта - один, который поддерживает положение и любое другое состояние, и другой, который выполняет рекурсивную навигацию экземпляра первого объекта по дереву. Таким образом, состояние перемещаемого объекта будет восстановлено после возврата рекурсивных вызовов в навигаторе.

0 голосов
/ 17 декабря 2009

Как насчет этого? 

struct Restore {
    Restore(double& value) : m_value(value), m_initial(value) {}
    ~Restore() {m_value = value;}
    double& m_value;
    double m_initial;
};

и затем: 

{ //scope
    Restore r1(m_XPos), r2(m_YPos);
    Navigate(m_XPos,m_YPos);
} // m_XPos and m_YPos automatically restored when r1 and r2 goes out of scope
...