状态机的 C++ 代码

C++ code for state machine

提问by Romonov

This was an interview question to be coded in C++:

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

Write code for a vending machine: Start with a simple one where it just vends one type of item. So two state variables: money and inventory, would do.

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

My answer:

我的答案：

I would use a state machine which has about 3-4 states. Use an enum variable to indicate the state and use a switch case statement, where each case has the operations to be done corresponding to each state and stay in a loop to move from one state to another.

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

The next question:

下一个问题：

But using a switch case statement does not "scale well" for more states being added and modifying existing operations in a state. How are you going to deal with that problem?

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

I couldn't answer this question at that time. But later thought, I can probably:

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

• have different functions for different states (each function corresponding to a state)
• have an std::mapfrom (string, function) where string indicates state to call the corresponding state function.
• The main function has a string variable (starting in initial state), and calls the function corresponding to that variable in a loop. Each function does the operations needed and returns the new state to the main function.

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

My questions are:

我的问题是：

• What is the problem with switch-case statements with respect to scalability in the context of large scale software systems?
• If so is my solution (which currently I feel is a bit more modular than having long linear code) going to resolve the problem?

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

The interview question is expecting answers from C++ idioms and design patterns for large scale software systems.

面试问题期待 C++ 习惯用法和大型软件系统设计模式的答案。

回答by Henrique Barcelos

I was thinking in a more OO approach, using the State Pattern:

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

The Machine:

机器：

// machine.h
#pragma once

#include "MachineStates.h"

class AbstractState;
class Machine {
    friend class AbstractState;
    public:
        Machine(unsigned int inStockQuantity);
        void sell(unsigned int quantity);
        void refill(unsigned int quantity);
        unsigned int getCurrentStock();
        ~Machine();
    private:
        unsigned int mStockQuantity;
        AbstractState* mState;
};

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

Machine::Machine(unsigned int inStockQuantity) :
    mStockQuantity(inStockQuantity), 
    mState(inStockQuantity > 0 ? new Normal() : new SoldOut()) {
}

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

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

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

unsigned int Machine::getCurrentStock() {
    return mStockQuantity;
}

The States:

美国：

// 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.mState;
    machine.mState = state; 
    delete aux;
}

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

Normal::~Normal() {
}

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

    updateStock(machine, currStock - quantity);

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

void Normal::refill(Machine& machine, unsigned int quantity) {
    int currStock = machine.getCurrentStock();
    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());
}

I'm not used to program in C++, but this code aparently compiles against GCC 4.8.2 and valgrind shows no leaks, so I guess it's fine. I'm not computing money, but I don't need this to show you the idea.

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

To test it:

要测试它：

#include <iostream>
#include <stdexcept>
#include "Machine.h"
#include "MachineStates.h"

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.getCurrentStock() << " items" << std::endl;

    m.sell(5);
    std::cout << "m: " << "Sold 5 items" << std::endl;
    std::cout << "m: " << "Remaining " << m.getCurrentStock() << " 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;
}

Output is:

输出是：

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

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

Now, if you want to add a Brokenstate, all you need is another AbstractStatechild. Maybe you'll need to add a brokenproperty on Machinealso.

现在，如果你想添加一个Broken状态，你只需要另一个AbstractState孩子。也许您还需要添加一个broken属性Machine。

To add more products, you must have a map of products and its respective in-stock quantity and so on...

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

回答by Thomas Matthews

Consider using tables instead of switchstatements. One column could be the transition criteria and another column is the destination state.

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

This scales nicely because you don't have to change the table processing function; just add another row to the table.

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

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

In my code at work, we use a column of function pointers rather than the "Next state ID". The table is a separate file with accessor functions defined. There is one or more include statements to resolve each function pointer.

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

Edit 1: Example of separate table files.

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

table.h

表.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:

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

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

回答by leemes

I once wrote a state machine in C++, where I needed the same transition for a lot of state pairs (source → target pairs). I want to illustrate an example:

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

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

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

What I came up with was a set of (transition criteria + next state + "action" function to be called). To keep things general, both the transition criteria and the next state were written as functors (lambda functions):

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

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

This solution is nice if you have a lot of transitions which apply for a lot of different states as in the example above. However, for each "step", this method requires to linearly scan the list of all different transitions.

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

For the examples above, there would be two such transitions:

对于上面的例子，会有两个这样的转换：

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

回答by unthought

I don't know whether that would have gotten you through the interview, but I'd personally refrain from coding any state machine by hand, especially if it's in a professional setting. State machines are a well researched problem, and there exist well tested open source tools which often produce superior code to what you will produce yourself by hand, and they also help you with diagnosing problems with your state machine by eg. being able to generate state diagrams automatically.

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

My goto tools for this kind of problem are:

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

• Ragel
• SMC

• 雷格尔
• SMC

回答by eddyq

I've written plenty of state machines using these methods. But when I wrote Cisco's Transceiver Library for the Nexus 7000 (a $117,000 switch) I used a method I invented in the 80's. That was to use a macro which makes the state machine look more like multi-tasking blocking code. The macros are written for C but I have used them with small modifications for C++ when I worked for DELL. You can read more about it here: https://www.codeproject.com/Articles/37037/Macros-to-simulate-multi-tasking-blocking-code-at

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

回答by himanshu mishra

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