Конечный автомат в C ++ через синглтон?

Question

Я думаю, что хорошим способом реализации конечного автомата является использование шаблона синглтона.Например, это может выглядеть так:

class A
{

private:
    friend class State;
    State* _state;
    void change_state(State* state) { _state = state; }
};

class State
{
    virtual void action(A *a) = 0;
private:
    void change_state(A *a, State *state) { a->change_state(state); }
};

class StateA : public State
{
public:
    static State* get_instance()
    {
        static State *state = new StateA;
        return state;
    }
    virtual void action(A *a) { change_state(a, StateB::get_instance(); }
};

class StateB : public State
{
public:
    ...
    virtual void action(A *a) { change_state(a, StateA::get_instance(); }
};

Мой вопрос таков: я прочитал много статей о том, что шаблон синглтона настолько злой.Реализуя это без одноэлементного шаблона, вы должны вызывать новый каждый раз, когда вы меняете состояние, так что для тех, кто не любит одноэлементный, как бы вы реализовали шаблон конечного автомата?

Answer 1

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

Учитывая это, я не согласен с тем, что синглтон - лучший путь для вашего конечного автомата. Если вы реализуете его как синглтон, вы говорите, что это всегда ровно одна копия этого конечного автомата. Но что, если я хочу, чтобы два конечных автомата работали параллельно? Или нет конечных автоматов вообще? Что делать, если мне нужен собственный локальный конечный автомат, чтобы я мог поэкспериментировать с ним, чтобы увидеть, что с ним происходит? Если ваш конечный автомат одноэлементный, я не могу ничего из этого сделать, потому что на самом деле во всей программе используется только один конечный автомат.

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

Что касается того, как реализовать конечный автомат без единого тона, вы можете захотеть заставить объект конечного автомата выделять свою собственную копию каждого состояния и создавать таблицу переходов (если вам нужны явные объекты состояний), или просто иметь гигантский оператор switch и единственное перечисляемое значение, управляющее состоянием, в котором вы находитесь. Если у вас есть один экземпляр конечного автомата, это не менее эффективно, чем в текущей версии, и если у вас есть несколько экземпляров, это позволяет хранить локальную информацию в каждое состояние без загрязнения глобальной копии состояний, которые могут быть прочитаны другими частями программы.

Answer 2

Ваши классы StateA, StateB не имеют элементов данных. Предположительно, другие состояния также не будут иметь изменяемых элементов данных, поскольку, если бы они имели их, то это состояние было бы странным образом распределено между различными экземплярами A, то есть разными конечными автоматами, работающими одновременно.

Таким образом, ваши синглтоны избежали половины проблемы с шаблоном (глобальное изменяемое состояние). Фактически, с небольшими изменениями в вашем дизайне, вы можете заменить классы состояний на функции; замените указатели на их экземпляры указателями на функции; и замените виртуальный вызов на action вызовом через указатель текущей функции. Если кто-то доставляет вам много хлопот за использование синглетонов, но вы уверены, что ваш дизайн верен, вы можете внести это незначительное изменение и посмотреть, заметят ли они, что их «исправление» вообще не имело существенного значения для дизайна.

Другая половина проблемы с синглетонами все еще не будет решена, хотя это фиксированные зависимости. С вашими одиночками невозможно смоделировать StateB, чтобы протестировать StateA изолированно, или ввести гибкость, когда вы хотите ввести в вашу библиотеку новый конечный автомат, который совпадает с текущим, за исключением того, что StateA вместо этого переходит к StateC государстваB. Вы можете или не можете считать это проблемой. Если вы это сделаете, то вместо того, чтобы делать каждое состояние единичным, вам нужно сделать его более настраиваемым.

Например, вы могли бы дать каждому состоянию некоторый идентификатор (строку или, возможно, член перечисления), и для каждого идентификатора зарегистрировать State* где-нибудь в классе А. Затем, вместо того, чтобы переключаться на одноэлементный экземпляр StateB, StateA может перейти к любому объекту состояния, используемому для представления «состояния B» в этом автомате . Это может быть испытательным макетом для определенных случаев. Вы по-прежнему вызываете new один раз для каждого состояния для каждой машины, но не один раз для каждого изменения состояния.

По сути, это все еще шаблон стратегии для класса A, как и в вашем проекте. Но вместо того, чтобы иметь единую стратегию для продвижения конечного автомата и его постоянной замены по мере изменения состояния, у нас есть одна стратегия для каждого состояния, через которое проходит машина, все с одним и тем же интерфейсом. Другой вариант в C ++, который будет работать для некоторых целей, но не для других, - это использовать (форму) основанного на политике проектирования вместо стратегий. Затем каждое состояние обрабатывается классом (предоставляется в качестве аргумента шаблона), а не объектом (устанавливается во время выполнения). Поведение вашего конечного автомата, таким образом, фиксируется во время компиляции (как в вашем текущем проекте), но может быть настроено путем изменения аргументов шаблона, а не каким-либо образом изменяя или заменяя класс StateB. Тогда вам вообще не нужно вызывать new - создайте отдельный экземпляр каждого состояния в конечном автомате в качестве члена данных, используйте указатель на один из них для представления текущего состояния и сделайте виртуальный вызов это как раньше. При разработке на основе политик обычно не нужны виртуальные вызовы, поскольку обычно отдельные политики полностью независимы, тогда как здесь они реализуют общий интерфейс, и мы выбираем между ними во время выполнения.

Все это предполагает, что A знает о конечном множестве состояний. Это может быть нереально (например, A может представлять собой универсальный программируемый конечный автомат, который должен принимать произвольное количество произвольных состояний). В этом случае вам нужен способ создания ваших состояний: сначала создайте экземпляр StateA и экземпляр StateB. Поскольку каждое состояние имеет один выходной путь, каждый объект состояния должен иметь один элемент данных, который является указателем на новое состояние. Таким образом, создав состояния, установите для экземпляров StateA «следующее состояние» для экземпляра StateB и наоборот. Наконец, установите элемент данных текущего состояния A для экземпляра StateA и запустите его. Обратите внимание, что когда вы делаете это, вы создаете циклический график зависимостей, поэтому, чтобы избежать утечек памяти, вам, возможно, придется принять специальные меры по обработке ресурсов помимо подсчета ссылок.

Answer 3

Подход к проектированию, который я рассматриваю, заключается в создании фабрики состояний, которая является одноэлементной, чтобы более чем один конечный автомат мог использовать объекты состояния, созданные фабрикой.

Но эта мысль привела меня к идее реализации моей фабрики состояний с шаблоном навесного веса, и на этом я остановился.

По сути, мне нужно исследовать преимущества реализации объектов состояния в качестве навесных весов, а затем преимущества шаблона проектирования с наименьшим весом.

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

Во всяком случае, я проводил некоторые исследования и наткнулся на этот пост. Просто думал, что поделюсь ...

Answer 4

Один подход, который предполагает, что все объекты состояния живут вдоль StateMachine, может быть таким:

enum StateID
{
   STATE_A,
   STATE_B,
   ...
};

// state changes are triggered by events 
enum EventID
{
   EVENT_1,
   EVENT_2,
   ...
};

// state manager (state machine)
class StateMachine
{
   friend StateA;
   friend StateB;
   ...

public: 
   StateMachine();
   ~StateMachine();
   // state machine receives events from external environment
   void Action(EventID eventID);
private:
   // current state
   State* m_pState;

   // all states
   StateA* m_pStateA;
   StateB* m_pStateB;
   ... 

   void SetState(StateID stateID);       
};

StateMachine::StateMachine()
{
   // create all states
   m_pStateA = new StateA(this, STATE_A);
   m_pStateB = new StateB(this, STATE_B);
   ...

   // set initial state
   m_pState = m_pStateA; 
}

StateMachine::~StateMachine()
{
   delete m_pStateA;
   delete m_pStateB;
   ...
}

void StateMachine::SetState(StateID stateID)
{
   switch(stateID)
   {
   case STATE_A:
      m_pState = m_pStateA;
      break;
   case STATE_B:
      m_pState = m_pStateA;
      break;
   ...
   }
}

void StateMachine::Action(EventID eventID)
{
   // received event is dispatched to current state for processing
   m_pState->Action(eventID);
}

// abstract class
class State
{
public:
   State(StateMachine* pStateMachine, StateID stateID);
   virtual ~State();
   virtual void Action(EventID eventID) = 0;
private:
   StateMachine* m_pStateMachine;
   StateID m_stateID;       
};

class StateA : public State
{
public: 
   StateA(StateMachine* pStateMachine, StateID stateID);    
   void Action(EventID eventID);
};

StateA::StateA(StateMachine* pStateMachine, StateID stateID) : 
   State(pStateMachine, stateID) {...}

void StateA::Action(EventID eventID)
{
   switch(eventID)
   {
   case EVENT_1:
      m_pStateMachine->SetState(STATE_B);
      break;
   case EVENT_2:
      m_pStateMachine->SetState(STATE_C);
      break;
   ...
   }
}

void StateB::Action(EventID eventID)
{
   switch(eventID)
   {
   ...
   case EVENT_2:
      m_pStateMachine->SetState(STATE_A);
      break;
   ...
   }
}

int main()
{
   StateMachine sm;
   // state machine is now in STATE_A

   sm.Action(EVENT_1);
   // state machine is now in STATE_B

   sm.Action(EVENT_2);
   // state machine is now in STATE_A

   return 0;
}

В более сложном решении StateMachine будет иметь очередь событий и цикл событий, который будет ожидать события из очереди и отправлять их в текущее состояние. Все трудоемкие операции в StateX::Action(...) должны выполняться в отдельном (рабочем) потоке, чтобы предотвратить блокировку цикла событий.

Answer 5

В вашем коде вы не связываете состояние с конечным автоматом, которому принадлежит состояние (при условии, что класс A является конечным автоматом). Эта информация передается в метод действия. Таким образом, если у вас есть два экземпляра класса A (то есть два конечных автомата), вы можете в конечном итоге обновить состояние неверного конечного автомата.

Если вы делаете это, чтобы избежать повторных вызовов new и удаления в целях ускорения, то это, вероятно, преждевременная оптимизация. Лучшее решение, если вы можете показать, что использование new и delete слишком медленное / вызывает другие проблемы (например, фрагментация памяти), - это определить оператор new / delete в базовом классе State, который выделяется из его собственного пула памяти.

Вот несколько псевдокодов о том, как работает конечный автомат, которым я сейчас пользуюсь:

class StateMachine
{
public:
   SetState (State state) { next_state = state; }
   ProcessMessage (Message message)
   {
     current_state->ProcessMessage (message);
     if (next_state)
     {
       delete current_state;
       current_state = next_state;
       next_state = 0;
     }
   }
private:
   State current_state, next_state;
}

class State
{
public:
   State (StateMachine owner) { m_owner = owner; }
   virtual ProcessMessage (Message message) = 0;
   void *operator new (size_t size) // allocator
   {
     return memory from local memory pool
   }
   void operator delete (void *memory) // deallocator
   {
     put memory back into memory pool
   }
protected:
   StateMachine m_owner;
};

class StateA : State
{
public:
  StateA (StateMachine owner) : State (owner) {}
  ProcessMessage (Message message)
  {
    m_owner->SetState (new StateB (m_owner));
  }
}

Пул памяти может представлять собой массив кусков памяти, каждый из которых достаточно большой, чтобы вместить любое состояние, с парой списков, один для выделенных блоков и один для нераспределенных блоков. Выделение блока затем становится процессом удаления блока из нераспределенного списка и добавления его в выделенный список. Освобождение - это обратный процесс. Я думаю, что термин «свободный список» для этого типа стратегии распределения. Это очень быстро, но немного потерянной памяти.