C++状态机代码

Question

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

为自动售货机编写代码：从简单的开始，只出售一种物品。所以两个状态变量：money（钱）和inventory（库存）就足够了。

我的答案：

我会使用一个具有3-4个状态的状态机。使用枚举变量表示状态，并使用switch case语句，在每个状态下执行相应的操作，然后在循环中从一个状态转移到另一个状态。

接下来问到：

但是，使用switch case语句无法很好地扩展到添加更多状态和修改现有状态的操作。你打算如何解决这个问题？

当时我无法回答这个问题。但后来想到：

• 针对不同的状态拥有不同的函数（每个函数对应一个状态）
• 使用std::map将（字符串、函数）进行映射，其中字符串表示调用相应状态函数。
• 主函数有一个字符串变量（从初始状态开始），并在循环中调用与该变量相应的函数。每个函数执行所需的操作并返回新状态到主函数。

我的问题是：

• 在大型软件系统的背景下，switch-case语句在可扩展性方面存在什么问题？
• 如果有问题，我目前的解决方案（我认为比具有长线性代码更加模块化）是否能够解决该问题？

该面试题期望从C++惯用语和设计模式的角度回答。

- Romonov

---

我认为他们期望你使用状态设计模式... - Henrique Barcelos

Answer 1

我在思考更加面向对象的方法，使用状态模式：

这台机器：

// 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;
 }

为了添加更多的产品，你需要有一个包含产品及其库存数量等信息的产品地图...

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

- Henrique Barcelos

---

机器应该根据数量初始化为“正常”或“售罄”状态，而不是默认始终为“正常”。 - zar

值得注意的是，如果你尝试在 Visual Studio 2017 中使用 C++17 编译此代码，它会产生一个错误 C2446：“:”：无法将 'SoldOut*' 转换为 'Normal*'。 如果你在Machine的构造函数中删除三元运算符，并简单地在构造函数体中初始化 mState 变量（或在Machine的头文件中初始化它），那么就没问题了。 - micka190

@micka190 嗯，这看起来很奇怪。虽然我不是专业的 C++ 程序员，但据我所知，由于 mState 是 AbstractState 类型，而 Normal 和 SoldOut 都继承了它，所以不应该有问题。关于你在头文件中初始化的建议，如果你能给我一个代码片段，我很乐意更新答案。 - Henrique Barcelos

@HenriqueBarcelos，我只是在猜测（因为这可能只是MSVC的问题），但我认为三元运算符要求两个结果都是相同类型的（无论左侧变量是否与两者兼容）。您必须在构造函数中使用“if”语句来正确初始化它。至于头文件初始化，那只允许我们将其显式地初始化为“nullptr”，“Normal”或“SoldOut”（没有三元运算符和“if”语句，因此基本上给它一个默认状态）。 - micka190

我更新了答案，现在代码应该可以无错误编译。看起来在我写下初始答案后编译器很快就被更新了，现在需要使用三元运算符进行显式转换。 - Henrique Barcelos

Answer 2

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

这种方法的可扩展性很好，因为您不需要改变表格处理函数；只需向表格添加一行即可。

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

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

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

table.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

table.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];
}  

状态机.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";
         }
    }
}

- Thomas Matthews

---

请问您能否提供更多关于如何在单独的文件中使用访问器函数编写此表格的细节？如果可能的话，可以通过一个小的状态机示例来说明：3个状态（A、B、C）；A()、B()、C()是每个状态需要执行的操作所在的函数。 - Romonov

这是一个使用I/O流的C状态机，而不是C++状态机。 - user1171983

为什么不用 C++？我承认这个程序并不是完全面向对象的，但是它可以与 C 和 C++ 兼容。难道是因为我没有使用函数对象或 std::map 结构吗？我之所以使用表格，是因为表格可以编译为静态数据，而无需像 std::map 一样进行初始化。 - Thomas Matthews

我花了很多时间尝试各种类型的状态机，但是转换表在我遇到的几乎所有问题中都表现最好。对于那里真的很棒的代码，点个赞！ - Zimano

如果一个符合标准的编译器可以编译通过，那么我不认同“这不是C ++”这样的说法。至此为止。你可以说它不是面向对象的，但是C++的美妙之处在于它并不会强制任何范式。 - chili

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; }
));

- leemes

Answer 4

我不知道这是否能帮助你通过面试，但我个人建议在专业环境下避免手写任何状态机，尤其是涉及编程方面。状态机是一个经过深入研究的问题，存在着经过充分测试的开源工具，通常会比你手写的代码产生更优秀的结果，并且它们还可以通过自动生成状态图来帮助你诊断状态机中的问题。

我推荐使用以下工具：

- Ragel - SMC

- unthought

---

你也试过stateforge吗？它现在是开源的。免责声明，我是作者。 - Frederic Heem

SMC的上面链接应该是https://sourceforge.net/projects/smc/。 - HiTechHiTouch

对不起，当我点击原始答案的 SMC 链接时，它似乎已经失效了。现在可以访问。 - HiTechHiTouch

SMC链接已损坏 - b264

Answer 5

我使用这些方法编写了很多状态机。但是，当我为 Nexus 7000 编写 Cisco 的 Transceiver Library（一款价值 $117,000 的交换机）时，我使用了一种在80年代发明的方法。那就是使用宏，使状态机看起来更像是多任务阻塞代码。这些宏是用 C 写的，但我在为 DELL 工作时稍加修改后也用于 C++。您可以在此处阅读更多信息：https://www.codeproject.com/Articles/37037/Macros-to-simulate-multi-tasking-blocking-code-at。

- eddyq

Answer 6

#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;
}

- himanshu mishra