c++ - 状态机的 C++ 代码

Question

这是一个用 C++ 编写的面试问题：

为自动售货机编写代码：从一个仅售卖一种商品的简单机器开始。所以两个状态变量：金钱和库存，就可以了。

我的答案：

我会使用具有大约 3-4 个状态的状态机。使用枚举变量来指示状态并使用 switch case 语句，其中每个 case 都有对应于每个状态的操作，并停留在循环中以从一个状态移动到另一个状态。

下一个问题：

但是对于添加更多状态和修改状态中的现有操作，使用 switch case 语句并不能“很好地扩展”。你将如何处理这个问题？

我当时无法回答这个问题。但后来想，我大概可以：

• 对不同的状态有不同的功能（每个功能对应一个状态）
• 有一个std::mapfrom (string, function) 其中 string 表示状态以调用相应的状态函数。
• 主函数有一个字符串变量（从初始状态开始），并在循环中调用与该变量对应的函数。每个函数执行所需的操作并将新状态返回给主函数。

我的问题是：

• 在大规模软件系统的上下文中，关于可伸缩性的 switch-case 语句有什么问题？
• 如果是这样，我的解决方案（目前我觉得它比长线性代码更模块化）会解决问题吗？

面试问题是期待来自大型软件系统的 C++ 习语和设计模式的答案。

Answer 1

我正在考虑一种更面向对象的方法，使用State Pattern：

机器：

// machine.h
#pragma once

#include "MachineStates.h"

class AbstractState;

class Machine {
  friend class AbstractState;

public:
  Machine(unsigned int _stock);
  void sell(unsigned int quantity);
  void refill(unsigned int quantity);
  unsigned int getStock();
  ~Machine();

private:
  unsigned int stock;
  AbstractState *state;
};


// --------

// machine.cpp
#include "Machine.h"
#include "MachineStates.h"

Machine::Machine(unsigned int _stock) {
  stock = _stock;
  state = _stock > 0 ? static_cast<AbstractState *>(new Normal())
                    : static_cast<AbstractState *>(new SoldOut());
}

Machine::~Machine() { delete state; }

void Machine::sell(unsigned int quantity) { state->sell(*this, quantity); }

void Machine::refill(unsigned int quantity) { state->refill(*this, quantity); }

unsigned int Machine::getStock() { return stock; }

美国：

// MachineStates.h
#pragma once

#include "Machine.h"
#include <exception>
#include <stdexcept>

class Machine;

class AbstractState {
public:
  virtual void sell(Machine &machine, unsigned int quantity) = 0;
  virtual void refill(Machine &machine, unsigned int quantity) = 0;
  virtual ~AbstractState();

protected:
  void setState(Machine &machine, AbstractState *st);
  void updateStock(Machine &machine, unsigned int quantity);
};

class Normal : public AbstractState {
public:
  virtual void sell(Machine &machine, unsigned int quantity);
  virtual void refill(Machine &machine, unsigned int quantity);
  virtual ~Normal();
};

class SoldOut : public AbstractState {
public:
  virtual void sell(Machine &machine, unsigned int quantity);
  virtual void refill(Machine &machine, unsigned int quantity);
  virtual ~SoldOut();
};

// --------

// MachineStates.cpp
#include "MachineStates.h"

AbstractState::~AbstractState() {}

void AbstractState::setState(Machine &machine, AbstractState *state) {
  AbstractState *aux = machine.state;
  machine.state = state;
  delete aux;
}

void AbstractState::updateStock(Machine &machine, unsigned int quantity) {
  machine.stock = quantity;
}

Normal::~Normal() {}

void Normal::sell(Machine &machine, unsigned int quantity) {
  unsigned int currStock = machine.getStock();
  if (currStock < quantity) {
    throw std::runtime_error("Not enough stock");
  }

  updateStock(machine, currStock - quantity);

  if (machine.getStock() == 0) {
    setState(machine, new SoldOut());
  }
}

void Normal::refill(Machine &machine, unsigned int quantity) {
  int currStock = machine.getStock();
  updateStock(machine, currStock + quantity);
}

SoldOut::~SoldOut() {}

void SoldOut::sell(Machine &machine, unsigned int quantity) {
  throw std::runtime_error("Sold out!");
}

void SoldOut::refill(Machine &machine, unsigned int quantity) {
  updateStock(machine, quantity);
  setState(machine, new Normal());
}

我不习惯用 C++ 编程，但这段代码显然是针对GCC 4.8.2 clang @编译的，11.0.0而且 Valgrind 没有显示任何泄漏，所以我想这很好。我不是在计算金钱，但我不需要这个来向你展示这个想法。

要测试它：

// main.cpp
#include "Machine.h"
#include "MachineStates.h"
#include <iostream>
#include <stdexcept>

int main() {
  Machine m(10), m2(0);

  m.sell(10);
  std::cout << "m: "
            << "Sold 10 items" << std::endl;

  try {
    m.sell(1);
  } catch (std::exception &e) {
    std::cerr << "m: " << e.what() << std::endl;
  }

  m.refill(20);
  std::cout << "m: "
            << "Refilled 20 items" << std::endl;

  m.sell(10);
  std::cout << "m: "
            << "Sold 10 items" << std::endl;
  std::cout << "m: "
            << "Remaining " << m.getStock() << " items" << std::endl;

  m.sell(5);
  std::cout << "m: "
            << "Sold 5 items" << std::endl;
  std::cout << "m: "
            << "Remaining " << m.getStock() << " items" << std::endl;

  try {
    m.sell(10);
  } catch (std::exception &e) {
    std::cerr << "m: " << e.what() << std::endl;
  }

  try {
    m2.sell(1);
  } catch (std::exception &e) {
    std::cerr << "m2: " << e.what() << std::endl;
  }

  return 0;
}

一点点Makefile：

CC = clang++
CFLAGS = -g -Wall -std=c++17

main: main.o Machine.o MachineStates.o
    $(CC) $(CFLAGS) -o main main.o Machine.o MachineStates.o

main.o: main.cpp Machine.h MachineStates.h
    $(CC) $(CFLAGS) -c main.cpp

Machine.o: Machine.h MachineStates.h

MachineStates.o: Machine.h MachineStates.h

clean:
    $(RM) main

然后运行：

make main
./main

输出是：

m: Sold 10 items
m: Sold out!
m: Refilled 20 items
m: Sold 10 items
m: Remaining 10 items
m: Sold 5 items
m: Remaining 5 items
m: Not enough stock
m2: Not enough stock

现在，如果你想添加一个Broken状态，你只需要另一个AbstractState孩子：

diff --git a/Machine.cpp b/Machine.cpp
index 935d654..6c1f421 100644
--- a/Machine.cpp
+++ b/Machine.cpp
@@ -13,4 +13,8 @@ void Machine::sell(unsigned int quantity) { state->sell(*this, quantity); }
 
 void Machine::refill(unsigned int quantity) { state->refill(*this, quantity); }
 
+void Machine::damage() { state->damage(*this); }
+
+void Machine::fix() { state->fix(*this); }
+
 unsigned int Machine::getStock() { return stock; }
diff --git a/Machine.h b/Machine.h
index aa983d0..706dde2 100644
--- a/Machine.h
+++ b/Machine.h
@@ -12,6 +12,8 @@ public:
   Machine(unsigned int _stock);
   void sell(unsigned int quantity);
   void refill(unsigned int quantity);
+  void damage();
+  void fix();
   unsigned int getStock();
   ~Machine();
 
diff --git a/MachineStates.cpp b/MachineStates.cpp
index 9656783..d35a53d 100644
--- a/MachineStates.cpp
+++ b/MachineStates.cpp
@@ -13,6 +13,16 @@ void AbstractState::updateStock(Machine &machine, unsigned int quantity) {
   machine.stock = quantity;
 }
 
+void AbstractState::damage(Machine &machine) {
+  setState(machine, new Broken());
+};
+
+void AbstractState::fix(Machine &machine) {
+  setState(machine, machine.stock > 0
+                        ? static_cast<AbstractState *>(new Normal())
+                        : static_cast<AbstractState *>(new SoldOut()));
+};
+
 Normal::~Normal() {}
 
 void Normal::sell(Machine &machine, unsigned int quantity) {
@@ -33,6 +43,10 @@ void Normal::refill(Machine &machine, unsigned int quantity) {
   updateStock(machine, currStock + quantity);
 }
 
+void Normal::fix(Machine &machine) {
+  throw std::runtime_error("If it ain't broke, don't fix it!");
+};
+
 SoldOut::~SoldOut() {}
 
 void SoldOut::sell(Machine &machine, unsigned int quantity) {
@@ -43,3 +57,17 @@ void SoldOut::refill(Machine &machine, unsigned int quantity) {
   updateStock(machine, quantity);
   setState(machine, new Normal());
 }
+
+void SoldOut::fix(Machine &machine) {
+  throw std::runtime_error("If it ain't broke, don't fix it!");
+};
+
+Broken::~Broken() {}
+
+void Broken::sell(Machine &machine, unsigned int quantity) {
+  throw std::runtime_error("Machine is broken! Fix it before sell");
+}
+
+void Broken::refill(Machine &machine, unsigned int quantity) {
+  throw std::runtime_error("Machine is broken! Fix it before refill");
+}
diff --git a/MachineStates.h b/MachineStates.h
index b117d3c..3921d35 100644
--- a/MachineStates.h
+++ b/MachineStates.h
@@ -11,6 +11,8 @@ class AbstractState {
 public:
   virtual void sell(Machine &machine, unsigned int quantity) = 0;
   virtual void refill(Machine &machine, unsigned int quantity) = 0;
+  virtual void damage(Machine &machine);
+  virtual void fix(Machine &machine);
   virtual ~AbstractState();
 
 protected:
@@ -22,6 +24,7 @@ class Normal : public AbstractState {
 public:
   virtual void sell(Machine &machine, unsigned int quantity);
   virtual void refill(Machine &machine, unsigned int quantity);
+  virtual void fix(Machine &machine);
   virtual ~Normal();
 };
 
@@ -29,5 +32,13 @@ class SoldOut : public AbstractState {
 public:
   virtual void sell(Machine &machine, unsigned int quantity);
   virtual void refill(Machine &machine, unsigned int quantity);
+  virtual void fix(Machine &machine);
   virtual ~SoldOut();
 };
+
+class Broken : public AbstractState {
+public:
+  virtual void sell(Machine &machine, unsigned int quantity);
+  virtual void refill(Machine &machine, unsigned int quantity);
+  virtual ~Broken();
+};
diff --git a/main b/main
index 26915c2..de2c3e5 100755
Binary files a/main and b/main differ
diff --git a/main.cpp b/main.cpp
index 8c57fed..82ea0bf 100644
--- a/main.cpp
+++ b/main.cpp
@@ -39,11 +39,34 @@ int main() {
     std::cerr << "m: " << e.what() << std::endl;
   }
 
+  m.damage();
+  std::cout << "m: "
+            << "Machine is broken" << std::endl;
+  m.fix();
+  std::cout << "m: "
+            << "Fixed! In stock: " << m.getStock() << " items" << std::endl;
+
   try {
     m2.sell(1);
   } catch (std::exception &e) {
     std::cerr << "m2: " << e.what() << std::endl;
   }
 
+  try {
+    m2.fix();
+  } catch (std::exception &e) {
+    std::cerr << "m2: " << e.what() << std::endl;
+  }
+
+  m2.damage();
+  std::cout << "m2: "
+            << "Machine is broken" << std::endl;
+
+  try {
+    m2.refill(10);
+  } catch (std::exception &e) {
+    std::cerr << "m2: " << e.what() << std::endl;
+  }
+
   return 0;
 }

要添加更多产品，您必须拥有产品地图及其各自的库存数量等等......

最终代码可以在这个 repo中找到。

Answer 2

考虑使用表而不是switch语句。一列可以是转换标准，另一列是目标状态。

这可以很好地扩展，因为您不必更改表处理功能；只需在表格中添加另一行。

+------------------+---------------------+---------------+
| Current state ID | transition criteria | Next state ID |
+------------------+---------------------+---------------+
|                  |                     |               |
+------------------+---------------------+---------------+

在我的工作代码中，我们使用一列函数指针而不是“下一个状态 ID”。该表是一个单独的文件，其中定义了访问器函数。有一个或多个包含语句来解析每个函数指针。

编辑 1：单独表格文件的示例。

表.h

#ifndef TABLE_H
#define TABLE_H

struct Table_Entry
{
    unsigned int  current_state_id;
    unsigned char transition_letter;
    unsigned int  next_state_id;
};

Table_Entry const *    table_begin(void);
Table_Entry const *    table_end(void);

#endif // TABLE_H

表.cpp：

#include "table.h"

static const Table_Entry    my_table[] =
{
    //  Current   Transition     Next
    //  State ID    Letter     State ID
    {    0,          'A',        1}, // From 0 goto 1 if letter is 'A'.
    {    0,          'B',        2}, // From 0 goto 2 if letter is 'B'.
    {    0,          'C',        3}, // From 0 goto 3 if letter is 'C'.
    {    1,          'A',        1}, // From 1 goto 1 if letter is 'A'.
    {    1,          'B',        3}, // From 1 goto 3 if letter is 'B'.
    {    1,          'C',        0}, // From 1 goto 0 if letter is 'C'.
};

static const unsigned int  TABLE_SIZE =  
    sizeof(my_table) / sizeof(my_table[0]);


Table_Entry const *
table_begin(void)
{
    return &my_table[0];
}


Table_Entry const *
table_end(void)
{
    return &my_table[TABLE_SIZE];
}  

state_machine.cpp

#include "table.h"
#include <iostream>

using namespace std;  // Because I'm lazy.

void
Execute_State_Machine(void)
{
    unsigned int current_state = 0;
    while (1)
    {
        char transition_letter;
        cout << "Current state: " << current_state << "\n";
        cout << "Enter transition letter: ";
        cin >> transition_letter;
        cin.ignore(1000, '\n'); /* Eat up the '\n' still in the input stream */
        Table_Entry const *  p_entry = table_begin();
        Table_Entry const * const  p_table_end =  table_end();
        bool state_found = false;
        while ((!state_found) && (p_entry != p_table_end))
        {
            if (p_entry->current_state_id == current_state)
            {
                if (p_entry->transition_letter == transition_letter)
                {
                    cout << "State found, transitioning"
                         << " from state " << current_state
                         << ", to state " << p_entry->next_state_id
                         << "\n";
                    current_state = p_entry->next_state_id;
                    state_found = true;
                    break;
                }
             }
             ++p_entry;
         }
         if (!state_found)
         {
             cerr << "Transition letter not found, current state not changed.\n";
         }
    }
}

Answer 3

我曾经用 C++ 编写过一个状态机，我需要对很多状态对（源→目标对）进行相同的转换。我想举例说明：

4 -> 8   \
5 -> 9    \_ action1()
6 -> 10   /
7 -> 11  /

8 -> 4   \
9 -> 5    \_ action2()
10 -> 6   /
11 -> 7  /

我想出的是一组（转换标准+下一个状态+要调用的“动作”函数）。为了保持一般性，转换标准和下一个状态都写成函子（lambda 函数）：

typedef std::function<bool(int)> TransitionCriteria;
typedef std::function<int(int)>  TransitionNewState;
typedef std::function<void(int)> TransitionAction;   // gets passed the old state

如果您有很多适用于许多不同状态的转换，如上例所示，则此解决方案很好。但是，对于每个“步骤”，此方法需要线性扫描所有不同转换的列表。

对于上面的示例，将有两个这样的转换：

struct Transition {
    TransitionCriteria criteria;
    TransitionNewState newState;
    TransitionAction action;

    Transition(TransitionCriteria c, TransitionNewState n, TransitionAction a)
        : criteria(c), newState(n), action(a) {}
};
std::vector<Transition> transitions;

transitions.push_back(Transition(
    [](int oldState){ return oldState >= 4 && oldState < 8; },
    [](int oldState){ return oldState + 4; },
    [](int oldState){ std::cout << "action1" << std::endl; }
));
transitions.push_back(Transition(
    [](int oldState){ return oldState >= 8 && oldState < 12; },
    [](int oldState){ return oldState - 4; },
    [](int oldState){ std::cout << "action2" << std::endl; }
));

Answer 4

我不知道这是否能让你通过面试，但我个人会避免手动编写任何状态机，尤其是在专业环境中。状态机是一个经过充分研究的问题，并且存在经过良好测试的开源工具，这些工具通常可以生成比您自己手动生成的代码更好的代码，它们还可以帮助您诊断状态机的问题，例如。能够自动生成状态图。

我针对此类问题的 goto 工具是：

• 拉格尔
• SMC

Answer 5

#include <stdio.h>
#include <iostream>

using namespace std;
class State;

enum state{ON=0,OFF};
class Switch {
    private:
        State* offState;
        State* onState;
        State* currState;
    public:
        ~Switch();
        Switch();
        void SetState(int st);
        void on();
        void off();
};
class State{
    public:
        State(){}
        virtual void on(Switch* op){}
        virtual void off(Switch* op){} 
};
class OnState : public State{
    public:
    OnState(){
        cout << "OnState State Initialized" << endl;
    }
    void on(Switch* op);
    void off(Switch* op);
};
class OffState : public State{
    public:
    OffState(){
        cout << "OffState State Initialized" << endl;
    }
    void on(Switch* op);
    void off(Switch* op);
};
Switch::Switch(){
    offState = new OffState();
    onState = new OnState();
    currState=offState;
}
Switch::~Switch(){
    if(offState != NULL)
        delete offState;
    if(onState != NULL)
        delete onState;
}
void Switch::SetState(int newState){
    if(newState == ON)
    {
        currState = onState;
    }
    else if(newState == OFF)
    {
        currState = offState;
    }
}
void Switch::on(){
    currState->on(this);
}
void Switch::off(){
    currState->off(this);
}
void OffState::on(Switch* op){
    cout << "State transition from OFF to ON" << endl;
    op->SetState(ON);
}
void OffState::off(Switch* op){
    cout << "Already in OFF state" << endl;
}
void OnState::on(Switch* op){
    cout << "Already in ON state" << endl;
}
void OnState::off(Switch* op){
    cout << "State transition from ON to OFF" << endl;
    op->SetState(OFF);
}
int main(){
    Switch* swObj = new Switch();
    int ch;
    do{
        switch(ch){
            case 1:     swObj->on();
                    break;
            case 0:     swObj->off();
                    break;
            default :   cout << "Invalid choice"<<endl;
                    break;
        }
        cout << "Enter 0/1: ";
        cin >> ch;  
    }while(true);`enter code here`
    delete swObj;
    return 0;
}

Answer 6

我已经使用这些方法编写了很多状态机。但是当我为 Nexus 7000（价值 117,000 美元的交换机）编写 Cisco 的收发器库时，我使用了我在 80 年代发明的方法。那是使用一个使状态机看起来更像多任务阻塞代码的宏。这些宏是为 C 编写的，但当我为 DELL 工作时，我对 C++ 做了一些小的修改。您可以在此处阅读更多相关信息：https ://www.codeproject.com/Articles/37037/Macros-to-simulate-multi-tasking-blocking-code-at