状态机的 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.
相关文章