状态机的 C++ 代码

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

<块引用>

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

我的回答:

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

下一个问题:

<块引用>

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

当时我无法回答这个问题.不过后来想想,我大概可以:

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

我的问题是:

  • 在大规模软件系统的上下文中,switch-case 语句在可扩展性方面有什么问题?
  • 如果是这样的话,我的解决方案(目前我觉得它比长线性代码更模块化)能解决问题吗?

这个面试问题期待从 C++ 习语和大型软件系统的设计模式中得到答案.

解决方案

我正在考虑采用更面向对象的方法,使用 状态模式:

机器:

//machine.h#pragma once#include "MachineStates.h";类抽象状态;类机器{朋友类 AbstractState;上市:机器(无符号整数_stock);无效出售(无符号整数数量);void refill(无符号整数数量);无符号整数 getStock();~机器();私人的:无符号整数股票;抽象状态 *状态;};//--------//机器.cpp#include "Machine.h";#include "MachineStates.h";机器::机器(无符号整数_stock){股票 = _stock;状态 = _stock >0 ?static_cast(new Normal()): static_cast(new SoldOut());}机器::~机器(){ 删除状态;}void Machine::sell(unsigned intquantity) { state->sell(*this,quantity);}void Machine::refill(unsigned intquantity) { state->refill(*this,quantity);}unsigned int Machine::getStock() { 返回库存;}

美国:

//MachineStates.h#pragma once#include "Machine.h";#include <例外>#include 类机;类抽象状态{上市:虚拟无效销售(机器和机器,无符号整数数量)= 0;virtual void refill(Machine &machine, unsigned int 数量) = 0;虚拟 ~AbstractState();受保护:void setState(Machine &machine, AbstractState *st);void updateStock(Machine &machine, unsigned int 数量);};类正常:公共抽象状态{上市:虚拟无效销售(机器和机器,无符号整数数量);virtual void refill(Machine &machine, unsigned int 数量);虚拟 ~Normal();};类已售完:公共抽象状态{上市:虚拟无效销售(机器和机器,无符号整数数量);virtual void refill(Machine &machine, unsigned int 数量);虚拟 ~SoldOut();};//--------//机器状态.cpp#include "MachineStates.h";AbstractState::~AbstractState() {}void AbstractState::setState(Machine &machine, AbstractState *state) {AbstractState *aux = machine.state;machine.state = 状态;删除辅助;}void AbstractState::updateStock(Machine &machine, unsigned int 数量) {machine.stock = 数量;}正常::~正常() {}void Normal::sell(Machine &machine, unsigned int 数量) {无符号整数 currStock = machine.getStock();如果(currStock <数量){throw std::runtime_error(库存不足");}updateStock(machine, currStock - 数量);如果(machine.getStock()== 0){setState(machine, new SoldOut());}}void Normal::refill(Machine &machine, unsigned int 数量) {int currStock = machine.getStock();updateStock(machine, currStock + 数量);}售罄::~售罄() {}void SoldOut::sell(机器和机器,无符号整数数量){throw std::runtime_error(售罄!");}void SoldOut::refill(Machine &machine, unsigned int 数量) {更新库存(机器,数量);setState(machine, new Normal());}

我不习惯用 C++ 编程,但这段代码显然是针对 GCC 4.8.2 clang@11.0.0 和Valgrind 显示没有泄漏,所以我想这很好.我不是在计算钱,但我不需要这个来向你展示这个想法.

测试:

//main.cpp#include "Machine.h";#include "MachineStates.h";#include #include int main() {机器 m(10), m2(0);m.sell(10);std::cout <<"米:"<<售出 10 件"<<std::endl;尝试 {m.sell(1);} catch (std::exception &e) {std::cerr <<"米:"<<e.what() <<std::endl;}m.refill(20);std::cout <<"米:"<<重新装满 20 件物品"<<std::endl;m.sell(10);std::cout <<"米:"<<售出 10 件"<<std::endl;std::cout <<"米:"<<《剩余》<<m.getStock() <<"项目"<<std::endl;m.sell(5);std::cout <<"米:"<<已售出 5 件"<<std::endl;std::cout <<"米:"<<《剩余》<<m.getStock() <<"项目"<<std::endl;尝试 {m.sell(10);} catch (std::exception &e) {std::cerr <<"米:"<<e.what() <<std::endl;}尝试 {m2.sell(1);} catch (std::exception &e) {std::cerr <<"平方米:"<<e.what() <<std::endl;}返回0;}

一点Makefile:

CC = clang++CFLAGS = -g -Wall -std=c++17main: main.o Machine.o MachineStates.o$(CC) $(CFLAGS) -o main main.o Machine.o MachineStates.omain.o: main.cpp Machine.h MachineStates.h$(CC) $(CFLAGS) -c main.cppMachine.o: Machine.h MachineStates.hMachineStates.o: Machine.h MachineStates.h干净的:$(RM) 主

然后运行:

make main./主要的

输出为:

<块引用>

m: 售出 10 件商品米:售罄!m:重新填充 20 项m:售出 10 件商品m: 剩余 10 项m: 售出 5 件商品m: 剩余 5 项m:库存不足m2:库存不足

现在,如果你想添加一个 Broken 状态,你只需要另一个 AbstractState 子:

diff --git a/Machine.cpp b/Machine.cpp索引 935d654..6c1f421 100644--- a/Machine.cpp+++ b/Machine.cpp@@ -13,4 +13,8 @@ void Machine::sell(unsigned intquantity) { state->sell(*this,quantity);}void Machine::refill(unsigned intquantity) { state->refill(*this,quantity);}+void Machine::damage() { state->damage(*this);}++void Machine::fix() { state->fix(*this);}+unsigned int Machine::getStock() { 返回库存;}diff --git a/Machine.h b/Machine.h索引 aa983d0..706dde2 100644--- a/Machine.h+++ b/Machine.h@@ -12,6 +12,8 @@ 公众:机器(无符号整数_stock);无效出售(无符号整数数量);void refill(无符号整数数量);+ 无效伤害();+ 无效修复();无符号整数 getStock();~机器();diff --git a/MachineStates.cpp b/MachineStates.cpp索引 9656783..d35a53d 100644--- a/MachineStates.cpp+++ b/MachineStates.cpp@@ -13,6 +13,16 @@ void AbstractState::updateStock(Machine &machine, unsigned int 数量) {machine.stock = 数量;}+void AbstractState::damage(Machine &machine) {+ setState(machine, new Broken());+};++void AbstractState::fix(Machine &machine) {+ setState(machine, machine.stock > 0+ ?static_cast(new Normal())+ : static_cast(new SoldOut()));+};+正常::~正常() {}void Normal::sell(Machine &machine, unsigned int 数量) {@@ -33,6 +43,10 @@ void Normal::refill(Machine &machine, unsigned int 数量) {updateStock(machine, currStock + 数量);}+void Normal::fix(Machine &machine) {+ throw std::runtime_error(如果它没有坏,就不要修复它!");+};+售罄::~售罄() {}void SoldOut::sell(机器和机器,无符号整数数量){@@ -43,3 +57,17 @@ void SoldOut::refill(Machine &machine, unsigned int 数量) {更新库存(机器,数量);setState(machine, new Normal());}++void SoldOut::fix(Machine &machine) {+ throw std::runtime_error(如果它没有坏,就不要修复它!");+};++Broken::~Broken() {}++void Broken::sell(机器和机器,无符号整数数量){+ throw std::runtime_error(机器坏了!卖前修好");+}++void Broken::refill(Machine &machine, unsigned int 数量) {+ throw std::runtime_error(机器坏了!在重新填充之前修复它");+}diff --git a/MachineStates.h b/MachineStates.h索引 b117d3c..3921d35 100644--- a/MachineStates.h+++ b/MachineStates.h@@ -11,6 +11,8 @@ class AbstractState {上市:虚拟无效销售(机器和机器,无符号整数数量)= 0;virtual void refill(Machine &machine, unsigned int 数量) = 0;+ 虚拟虚空损坏(机器和机器);+ 虚拟无效修复(机器和机器);虚拟 ~AbstractState();受保护:@@ -22,6 +24,7 @@ 类普通:public AbstractState {上市:虚拟无效销售(机器和机器,无符号整数数量);virtual void refill(Machine &machine, unsigned int 数量);+ 虚拟无效修复(机器和机器);虚拟 ~Normal();};@@ -29,5 +32,13 @@ class SoldOut : public AbstractState {上市:虚拟无效销售(机器和机器,无符号整数数量);virtual void refill(Machine &machine, unsigned int 数量);+ 虚拟无效修复(机器和机器);虚拟 ~SoldOut();};++class Broken : public AbstractState {+公众:+ 虚拟无效销售(机器和机器,无符号整数数量);+ 虚拟空填充(机器和机器,无符号整数数量);+ 虚拟 ~Broken();+};diff --git a/main b/main索引 26915c2..de2c3e5 100755二进制文件 a/main 和 b/main 不同差异 --git a/main.cpp b/main.cpp索引 8c57fed..82ea0bf 100644--- a/main.cpp+++ b/main.cpp@@ -39,11 +39,34 @@ int main() {std::cerr <<"米:"<<e.what() <<std::endl;}+ m.damage();+ std::cout <<"米:"+ <<机器坏了"<<std::endl;+ m.fix();+ std::cout <<"米:"+ <<“固定!有货:"<<m.getStock() <<"项目"<<std::endl;+尝试 {m2.sell(1);} catch (std::exception &e) {std::cerr <<"平方米:"<<e.what() <<std::endl;}+ 试试 {+ m2.fix();+ } catch (std::exception &e) {+ std::cerr <<"平方米:"<<e.what() <<std::endl;+ }++ m2.damage();+ std::cout <<"平方米:"+ <<机器坏了"<<std::endl;++ 试试 {+ m2.refill(10);+ } catch (std::exception &e) {+ std::cerr <<"平方米:"<<e.what() <<std::endl;+ }+返回0;}

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

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

This was an interview question to be coded in 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.

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?

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::map from (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.

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?

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

解决方案

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

The Machine:

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

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

I'm not used to program in C++, but this code apparently compiles against GCC 4.8.2 clang@11.0.0 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.

To test it:

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

A little bit of 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

Then run:

make main
./main

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

Now, if you want to add a Broken state, all you need is another AbstractState child:

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

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

The final code can be found in this repo.

相关文章