状态机的C++代码

Question

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

编写自动售货机的代码:从一个简单的代码开始,它只是出售一种类型的商品.所以两个状态变量:金钱和库存,都可以.

我的答案:

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

下一个问题:

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

我当时无法回答这个问题.但后来想到,我可能:

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

我的问题是:

• 在大规模软件系统环境中,关于可伸缩性的switch-case语句有什么问题？
• 如果是这样,我的解决方案(目前我觉得比使用长线性代码更模块化)将解决问题？

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

Answer 1

我正在考虑更多OO方法,使用State Pattern:

机器:

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

美国:

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

我不习惯用C++编程,但是这段代码很好地编译了GCC 4.8.2并且valgrind显示没有泄漏,所以我猜它没关系.我不算钱,但我不需要这个来向你展示这个想法.

测试它:

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

输出是:

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孩子.也许你还需要添加一个broken属性Machine.

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

Answer 2

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

这很好地扩展,因为您不必更改表处理功能; 只需在表格中添加另一行.

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

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

编辑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];
}  

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

我不知道这是否会让你通过采访,但我个人不会手工编写任何状态机,特别是如果它是在专业环境中.状态机是一个研究得很好的问题,并且存在经过良好测试的开源工具,这些工具通常可以为您自己手工生成的代码生成优质代码,并且它们还可以帮助您通过例如诊断状态机的问题.能够自动生成状态图.

我对这类问题的转到工具是:

• Ragel
• SMC