SOLID Principle

  • Single Responsibility Principle (SRP) 日记例子,一个类只做一件事

  • Open-Closed Principle (OCP)

    根据颜色大小排序, Specification类,为扩展开发,为修改关闭

  • Liskov Substitution Principle (LSP)

    父类定义的方法意义,子类不能相违背,矩形和正方形的set_size()

  • Interface Segregation Principle (ISP)

    打印机传真机扫描仪封为machine,不如打印,传真,扫描封为抽象功能组合

  • Dependency Inversion Principle (DIP)

    其他类依赖本类的高级抽象而非具体实现,类间的依赖原则

Creational Patterns

创建型模式

一些概念

  • 栈分配
  • 堆分配
  • 智能指针

Builder

创建模式

Simple Builder

HtmlBuilder

Fluent Builder

使用流式操作

1builder.add_child("li", "hello").add_child("li", "world");
2builder->add_child("li", "hello")->add_child("li", "world");

为了强制让人使用Builder而不是构造函数, 可以把构造函数设为protected类型

类的隐式转换

 1#include <cstdio>
 2
 3class Html
 4{
 5public:
 6    void str()
 7    {
 8        printf("str");
 9    }
10
11protected:
12    Html() = default;
13    friend class HtmlBuilder;
14};
15
16class HtmlBuilder
17{
18    Html html;
19
20public:
21    operator Html() const
22    {
23        return html;
24    }
25};
26
27int main()
28{
29    HtmlBuilder builder;
30    Html root = builder;
31    root.str();
32}

Groovy-Style Builder

Tag抽象类, 包含了所有的数据存储, 构造函数protected

P, IMG等继承, 构造函数public, 初始化一些值

总结: 通过派生类特定构造来实现多样化的对象生成

 1import groovy.transform.builder.Builder
 2
 3@Builder(builderMethodName = 'initiator', buildMethodName = 'create')
 4class Message {
 5    String from, to, subject, body
 6}
 7
 8def message = Message.initiator()
 9        .from('mrhaki@mrhaki.com')
10        .body('Groovy rocks!')
11        .create()
12
13assert message.body == 'Groovy rocks!'
14assert message.from == 'mrhaki@mrhaki.com'

mini-DSL

例如下面Swift中的VStackTextButton都是SwiftUI嵌入在Swift中的DSL

1var body: some View {
2    VStack {
3        Text("Hello, World!")
4            .font(.largeTitle)
5        Button("Tap me!") {
6            print("Button was tapped")
7        }
8    }
9}

Composite Builder

Person静态函数create()生成PersonBuilder, PersonBuilder利用.at(), .with_post_code(), .as_a()等fluent builder快速构建对象, 然后利用operator Person转化为Person对象

Factories

工厂模式

Factory Method

类的方法替代构造函数创建类

Point, 笛卡尔坐标, 极坐标, 静态NewCartesian, NewPolar方法, 构造函数protected类型

Factory

隔离的类创建对象, 即使只是提供函数来创建类而不是直接创建

把静态NewCartesian, NewPolar方法放到PointFactory里面, Point友元类为工厂类, Point构造函数去掉

Inner Factory

把工厂类设置为Point的内置类, 可以访问Point私有成员而不需要友元, 然后声明一个静态的工厂类对象在Point类中

Abstract Factory

能被实际工厂函数继承

要创建的对象继承关系多种类复杂, 比如drink, hotdrink, tea, coffee, 工厂函数也要有相应的继承关系

和Builder的区别, Builder是一点数据一点数据添加, Factory是一次性生成

Prototype

原型模式, 对象模型能够直接拷贝, 然后通过修改参数生成新的对象

Object Constrution

构造两个类似的对象通常需要花费更多操作, 拷贝则简单许多

Ordinary Duplication

直接用等于号复制, 会带来浅拷贝的问题

Duplication via Copy Construction

用拷贝构造函数来拷贝对象或者用=操作符拷贝对象, 或者继承自Clonable类用clone方法, 用CRTP

Serialization

使用Boost的Serialization, 侵入式, 非侵入式, 原理是使用序列化和反序列化来传递数据生成新的对象

Prototype Factory

预设几个全局的模板, 用工厂方法生成对应的

Singleton

单例模式

Singleton as Global Object

静态变量返回

Classic Implementation

构造函数加计数器, 禁用各种构造函数, 删除拷贝构造, 赋值操作符

Thread Safety

加锁防止同时调用初始化函数造成问题

The Trouble with Singleton

单例模式写死后测试需要用假的类, 比如database, 需要改动就有很复杂的依赖, 尝试依赖单例对象的抽象接口类而不是依赖单例类

Singletons and Inversion of Control

使用IoC模式减少单例模式中单例对象的依赖性, 用依赖注入DI

Monostate

单态

是个普通的类但是表现为单例, 可以进行继承实现多态

Structural Patterns

结构型模式

几种结构:

  • Inheritance: 继承
  • Composition: 包含(拥有对象)
  • Aggregation: 聚集(拥有对象指针)

Adapter

适配器模式,STL中的容器适配器和迭代器适配器就是适配器模式的应用之一

Adapter

画点函数需要画所有线的点, 包括线组成的对象, 需要把线转成点集然后绘制

Adapter Temporaries

上述操作每次都要进行一次转换, 消耗计算资源, 利用哈希存储转换后的数据可以只转换不存在的点

类适配器模式

类适配器模式是适配器模式的一种,其定义为将一个类的接口转换成客户端所期望的另一个接口,使得原本由于接口不兼容而不能一起工作的那些类可以一起工作。在类适配器模式中,适配器与适配者之间是继承关系。

 1// 接口
 2class Target {
 3public:
 4    virtual void request() = 0;
 5};
 6
 7// 与接口不兼容的类
 8class Adaptee {
 9public:
10    void specificRequest() {
11        std::cout << "Adaptee::specificRequest()" << std::endl;
12    }
13};
14
15// 通过多继承的方式实现
16class Adapter : public Adaptee, public Target {
17public:
18    void request() override {
19        specificRequest();
20    }
21};
22
23int main() {
24    Target* target = new Adapter();
25    target->request();
26
27    delete target;
28    return 0;
29}

对象适配器模式

相对于类适配器模式,对象适配器模式使用组合的方式,而不是继承的方式来实现适配器

 1class Target {
 2public:
 3    virtual void request() = 0;
 4};
 5
 6class Adaptee {
 7public:
 8    void specificRequest() {
 9        std::cout << "Adaptee::specificRequest()" << std::endl;
10    }
11};
12
13class Adapter : public Target {
14public:
15    Adapter(Adaptee* adaptee) : m_adaptee(adaptee) {}
16
17    void request() override {
18        m_adaptee->specificRequest();
19    }
20
21private:
22    Adaptee* m_adaptee;
23};
24
25int main() {
26    Adaptee* adaptee = new Adaptee();
27    Target* target = new Adapter(adaptee);
28    target->request();
29
30    delete target;
31    delete adaptee;
32    return 0;
33}

接口适配器

接口适配器模式用于解决一个接口有多个方法,而客户端只需要使用其中的部分方法的情况。在接口适配器模式中,适配器通过实现一个或多个接口来适配适配者与客户端之间的接口

 1class Target {
 2public:
 3    virtual void request() = 0;
 4};
 5
 6class Adaptee {
 7public:
 8    void method1() {
 9        std::cout << "Adaptee::method1()" << std::endl;
10    }
11
12    void method2() {
13        std::cout << "Adaptee::method2()" << std::endl;
14    }
15
16    void method3() {
17        std::cout << "Adaptee::method3()" << std::endl;
18    }
19};
20
21// 使用Adapter类只实现method1接口
22class Adapter : public Target, public Adaptee {
23public:
24    void request() override {
25        method1();
26    }
27};
28
29int main() {
30    Target* target = new Adapter();
31    target->request();
32
33    delete target;
34    return 0;
35}

Bridge

桥接模式,用于将抽象部分与它的实现部分分离,使它们都可以独立地变化

The Pimpl Idiom

Pimpl的好处:

  • 只暴露public接口
  • 修改私有类的时候由于是指针存在公有类中, 不会对公有类的二进制结构造成影响, 比如size或者函数相对偏移地址等
  • 减少相互包含更多的头文件, 私有类的包含可以放到cpp文件里面去, 头文件不需要改不会让其他包含该头文件的文件重新编译

Example

Shape的自绘, Renderer的种类, Circle继承自形状, 传入Renderer引用存储

 1// 定义 Shape 类,作为抽象化角色。它持有一个 Renderer 类型的指针,并在 draw 函数中调用 Renderer 的 renderCircle 函数。
 2class Renderer {
 3public:
 4    virtual void renderCircle(float x, float y, float radius) = 0;
 5};
 6
 7class Shape {
 8protected:
 9    Renderer* renderer;
10
11public:
12    Shape(Renderer* renderer) : renderer(renderer) {}
13
14    virtual void draw() = 0;
15    virtual void resize(float factor) = 0;
16};
17
18// 定义 Circle 类,作为改善后的抽象化角色。它继承自 Shape 类,增加了一个 radius 成员变量,并在 draw 函数中调用 Renderer 的 renderCircle 函数。
19class Circle : public Shape {
20private:
21    float x, y, radius;
22
23public:
24    Circle(Renderer* renderer, float x, float y, float radius)
25        : Shape(renderer), x(x), y(y), radius(radius) {}
26
27    void draw() override {
28        renderer->renderCircle(x, y, radius);
29    }
30
31    void resize(float factor) override {
32        radius *= factor;
33    }
34};
35
36// 定义 Renderer 类及其两个具体实现类 RedCircle 和 GreenCircle,作为实现者角色。它们都实现了 renderCircle 函数,用于渲染圆形。
37class Renderer {
38public:
39    virtual void renderCircle(float x, float y, float radius) = 0;
40};
41
42class RedCircle : public Renderer {
43public:
44    void renderCircle(float x, float y, float radius) override {
45        cout << "Drawing red circle at (" << x << ", " << y << ") with radius " << radius << endl;
46    }
47};
48
49class GreenCircle : public Renderer {
50public:
51    void renderCircle(float x, float y, float radius) override {
52        cout << "Drawing green circle at (" << x << ", " << y << ") with radius " << radius << endl;
53    }
54};
55
56// 绘制
57int main() {
58    Renderer* renderer = new RedCircle();
59    Shape* circle = new Circle(renderer, 5, 5, 10);
60    circle->draw();
61
62    circle->resize(2);
63    circle->draw();
64
65    delete circle;
66    delete renderer;
67
68    renderer = new GreenCircle();
69    circle = new Circle(renderer, 10, 10, 20);
70    circle->draw();
71
72    delete circle;
73    delete renderer;
74
75    return 0;
76}

使用桥接模式可以将抽象和实现部分分离,从而使得它们可以独立变化。这样,我们就可以轻松地实现不同形状和不同颜色之间的组合,并且可以在运行时动态地改变它们之间的关系

Composite

组合模式使得用户对单个对象和组合对象的使用具有一致性

给单一的多个对象或者一组对象同一的接口, 比如begin/end, 单个的Graph对象有draw, 多个Graph组成的对象组同样有draw

ArcGIS Qt SDK里面的Geometry也是类似的设计方式, 包括了Point, Polyline, Polygon, Multipart等等

Array Backed Properties

Creature有一些值比如力量, 敏捷和智力, 要统计这些数据的共性, 与其定义几个不同的变量不如用数组和枚举记录在一起, 用迭代器求均值最大最小值

Grouping Graphic Objects

针对相同接口的对象进行编组, 用虚函数调用

Neural Networks

派生自模板接口

 1template <typename Self>
 2struct SomeNeurons
 3{
 4    template <typename T> void connect_to(T& other)
 5    {
 6        for (Neuron& from : *static_cast<Self*>(this))
 7        {
 8            for (Neuron& to : other)
 9            {
10                from.out.push_back(&to);
11                to.in.push_back(&from);
12            }
13        }
14    }
15};
16
17struct Neuron
18{
19    vector<Neuron*> in, out;
20    unsigned int id;
21
22    Neuron()
23    {
24        static int id = 1;
25        this->id = id++;
26    }
27}
28
29struct SingleNeuron : Neuron,
30                      SomeNeurons<SingleNeuron>
31{
32
33}
34
35
36struct NeuronLayer : Neuron,
37                     vector<Neuron>,
38                     SomeNeurons<NeuronLayer>
39{
40
41}

Decorator

装饰模式

在不改变原有类的情况下增强类的功能并且把增强的东西隔离开

实现方法:

  • 动态的组合允许在运行时组合, 拥有最大的弹性
  • 静态的组合对象的增强是在编译时使用模板, 所以在编译时就需要知道所有可能的增强

Dynamic Decorator

通过子类传入父类的引用或者指针来增加功能, 多个功能通过构造函数嵌套实现多种功能, 通过多态

 1struct ColoredShape : Shape
 2{
 3    Shape& shape;
 4    string color;
 5    ColoredShape(Shape& shape, const string& color) :
 6            shape{shape}, color{color} {}
 7};
 8
 9
10struct TransparentShape : Shape
11{
12    Shape& shape;
13    uint8_t transparency;
14    TransparentShape(Shape& shape, uint8_t transparency) :
15            shape{shape}, transparency{transparency} {}
16};
17
18
19// 多个功能的, 使用多态实现功能的叠加
20TransparentShape s{ColoredShape{Circle{1.2}, "red"}, 100};

Static Decorator

使用Mixin方式继承模板类, 添加功能增强类和子类

 1template <typename... Mixins>
 2class Point : public Mixins... {
 3public:
 4    double x, y;
 5    Point() : Mixins()..., x(0.0), y(0.0) {}
 6    Point(double x, double y) : Mixins()..., x(x), y(y) {}
 7};
 8class Label {
 9public:
10    std::string label;
11    Label() : label("") {}
12};
13class Color {
14public:
15    unsigned char red = 0, green = 0, blue = 0;
16};
17using MyPoint = Point<Label, Color>;

该例子实现了带颜色和标签的点,功能组合了

Function Decorator

使用函数模板为入参, 在函数开始前和结束后进行附加操作, 增强函数的功能, 比如记录函数运行时间和运行状态的Logger类, 重载()运算符

例如python的函数装饰器

 1import logging
 2import time
 3
 4def logger(func):
 5    logging.basicConfig(filename='example.log', level=logging.INFO)
 6
 7    def wrapper(*args, **kwargs):
 8        start_time = time.time()
 9        result = func(*args, **kwargs)
10        end_time = time.time()
11        run_time = end_time - start_time
12        logging.info("Function {}() ran in {} seconds with result: {}".format(
13            func.__name__, run_time, result))
14        return result
15
16    return wrapper
17
18@logger
19def add(x, y):
20    return x + y
21
22print(add(2, 3))  # 输出 5,同时将日志写入 example.log 文件中

Façade

外观模式, 终端就是外观, 实际的内部形式是buffer, 把简单接口放在复杂的子系统前面, 比如终端很多的buffer和viewport, 最后抽象成API。UE5里面的MeadiaPlayer也用到了外观模式。

外观模式的优点在于它能够简化客户端代码,降低客户端与子系统之间的耦合度。同时,外观模式还能够提高代码的可维护性和可扩展性,因为它将子系统的复杂性封装在一个单独的类中,使得对子系统的修改和扩展更加容易

 1#include <iostream>
 2
 3// 子系统类A
 4class SubsystemA {
 5public:
 6    void operationA() {
 7        std::cout << "Subsystem A operation" << std::endl;
 8    }
 9};
10
11// 子系统类B
12class SubsystemB {
13public:
14    void operationB() {
15        std::cout << "Subsystem B operation" << std::endl;
16    }
17};
18
19// 外观类
20class Facade {
21private:
22    SubsystemA* subsystemA;
23    SubsystemB* subsystemB;
24public:
25    Facade() {
26        subsystemA = new SubsystemA();
27        subsystemB = new SubsystemB();
28    }
29    ~Facade() {
30        delete subsystemA;
31        delete subsystemB;
32    }
33    // 对外提供的简单接口
34    void operation() {
35        subsystemA->operationA();
36        subsystemB->operationB();
37    }
38};
39
40// 客户端代码
41int main() {
42    Facade* facade = new Facade();
43    facade->operation();
44    delete facade;
45    return 0;
46}

Flyweight

享元模式

(flyweight token or cookie) 通常是一个临时组件, 比如智能指针, 通常有大量相同的对象, 需要最小化使用内存存储。例如字符串表哈希等。

User Names

大型服务器相同名字的用户每个用户都存储一份字符串会消耗大量的字节

用int代表key, 去bitmap中查找名称, bitmap可用双向查找

Boost.Flyweight

boost::flyweight<string>直接可用变成享元

String Ranges

std::string::substring()返回的是额外的字符串空间, 而不是共享内存只改变下标的字符串

string_view则是共享单元

Naïve Approach

建立一个bool数组对应string每个字符, bool为true代表要把对应字符串大写, 这样一个字符串既存储了原始字符串也存储了大写后的字符串

vector<bool>是优化存储过的, 用位

Flyweight Implementation

格式化字符串, 用和上面一样的方式存储多个TextRange类, TextRange里面标记起始和结束, 代表一个格式

享元模式没有确定的形式, 有时候是API token, 有时候是隐式的, 藏在幕布后面, 客户端并不知道是否使用享元模式

Proxy

装饰模式是不同方式增强对象的功能, 代理模式相似, 但是目标是在提供增强功能时尽可能保持正在使用的API

Proxy不是同质的, 不同类型的人建立方式不同, 服务目标不同

Smart Pointers

智能指针在实现其额外功能时保留了和普通指针一样的特性接口, 比如*运算符和->运算符, 还有bool运算符, 下标运算符, 但是智能指针不能执行delete 操作

Property Proxy

实现了getter, setter和普通的值一样

Virtual Proxy

lazy instantiation(延迟实例化), 仅用到了的时候才对对象构造分配空间, eager(反义词)

LazyBitmap, 只有在调用draw的时候才进行图片加载, 接口一样但是实现的方式不一样

Communication Proxy

本机通信和跨计算机通信共用接口

总结:

不像装饰模式, 代理模式不会通过增加对象成员来扩大功能(除非没办法). 所有对已知功能的增强都是基于已经存在的成员

  • property proxies是替身对象, 替换fields同时在获取值和写入值时进行额外操作
  • virtual proxies提供虚拟的接触基础对象, 然后实现例如lazy loading之类的功能. 这样让你感觉跟和真正的对象接触一样.
  • communication proxies允许改变对象的物理位置, 比如移动到云端, 但是我们只需要使用相同的API
  • logging proxies允许我们在调用基础函数的时候记录日志, 参考Function Decorator. 区别在于用代理模式实现的话两个函数同名

Behavioral Patterns

行为型模式, 没有一个固定的主题, 只有相似的策略, 大多数模式以独特的表现形式解决特定的问题

Chain of Responsibility

职责链模式

Pointer Chain

 1class CreatureModifier
 2{
 3    CreatureModifier* next{nullptr};
 4protected:
 5    Creature& creature; // alternative: pointer or shared_ptr
 6public:
 7    explicit CreatureModifier(Creature& creature):
 8        creature(creature) {}
 9
10    void add(CreatureModifier* cm)
11    {
12        if (next) next->add(cm);
13        else next = cm;
14    }
15
16    virtual void handle()
17    {
18        if (next) next->handle(); // critical!
19    }
20};
 1class DoubleAttackModifier : public CreatureModifier
 2{
 3public:
 4    explicit DoubleAttackModifier(Creature &creature)
 5            : CreatureModifier(creature) {}
 6
 7    void handle() override
 8    {
 9        creature.attack *= 2;
10        CreatureModifier::handle();
11    }
12};

类似的QWidget的paintEvent也是递归调用。组合模式加职责链模式可以实现集合中所有元素遍历操作

Broker Chain

通过一个集中化组件, 该组件保存一个Modifier列表,Broker理解为中间件

Boost.Signals2实现信号槽

Command Query Separation (CQS)

Gang of Four(GoF,Erich Gamma, Richard Helm, Ralph Johnson和John Vlissides)

 1struct Game // mediator
 2{
 3    signal<void(Query & )> queries;
 4};
 5
 6struct Query
 7{
 8    string creature_name;
 9    enum Argument
10    {
11        attack, defense
12    } argument;
13    int result;
14};
15
16class Creature
17{
18    Game &game;
19    int attack, defense;
20public:
21    string name
22
23    Creature(Game &game, ...) : game{game}, ...
24    { ... }
25// other members here
26};
27
28int Creature::get_attack() const
29{
30    Query q{name, Query::Argument::attack, attack};
31    game.queries(q);
32    return q.result;
33}
34
35class CreatureModifier
36{
37    Game &game;
38    Creature &creature;
39public:
40    CreatureModifier(Game &game, Creature &creature)
41            : game(game), creature(creature)
42    {}
43};
44
45class DoubleAttackModifier : public CreatureModifier
46{
47    connection conn;
48public:
49    DoubleAttackModifier(Game &game, Creature &creature)
50            : CreatureModifier(game, creature)
51    {
52        conn = game.queries.connect([&](Query &q) {
53            if (q.creature_name == creature.name &&
54                q.argument == Query::Argument::attack)
55                q.result *= 2;
56        });
57    }
58
59    ~DoubleAttackModifier()
60    { conn.disconnect(); }
61};
62Game game;
63Creature goblin{game, "Strong Goblin", 2, 2};
64cout << goblin << endl;
65// name: Strong Goblin attack: 2 defense: 2
66DoubleAttackModifier dam{game, goblin};
67cout << goblin << endl;
68// name: Strong Goblin attack: 4 defense: 2
69cout << goblin << endl;
70// name: Strong Goblin attack: 2 defense: 2

Command

命令模式是一种行为型设计模式,它将一个请求封装为一个对象,从而允许我们使用不同的请求对客户端进行参数化。请求被包装在对象中,并传递给调用对象,调用对象寻找可以处理该命令的合适对象,并将该命令传递给相应的对象,该对象执行命令。

给一个值赋值, 让其改变, 并不能知道改变记录, 也没办法回滚. 命令模式与其通过API改变对象, 不如发送命令: 指导该怎样做

 1#include <iostream>
 2using namespace std;
 3
 4// 命令接口
 5class Command {
 6public:
 7    virtual void execute() = 0;
 8};
 9
10// 具体命令
11class ConcreteCommand : public Command {
12public:
13    ConcreteCommand() {}
14    ~ConcreteCommand() {}
15
16    void execute() {
17        cout << "执行命令..." << endl;
18    }
19};
20
21// 调用对象
22class Invoker {
23public:
24    Invoker(Command *cmd) {
25        m_cmd = cmd;
26    }
27
28    ~Invoker() {
29        delete m_cmd;
30        m_cmd = nullptr;
31    }
32
33    void invoke() {
34        m_cmd->execute();
35    }
36
37private:
38    Command *m_cmd;
39};
40
41// 客户端
42int main() {
43    Command *cmd = new ConcreteCommand();
44    Invoker *invoker = new Invoker(cmd);
45    invoker->invoke();
46
47    delete invoker;
48    return 0;
49}

Implementing the Command Pattern

定义虚基类Command带纯虚函数call, BankAccountCommand构造函数带BankAccount, Action, amout, 调用call时存钱取钱

Undo Operations

Command添加undo虚函数

 1#include <iostream>
 2#include <vector>
 3using namespace std;
 4
 5// 命令接口
 6class Command {
 7public:
 8    virtual void execute() = 0;
 9    virtual void undo() = 0;
10};
11
12// 具体命令类
13class ConcreteCommand : public Command {
14public:
15    ConcreteCommand(int& value, int delta) : m_value(value), m_delta(delta) {}
16    virtual void execute() override {
17        m_prevValue = m_value;
18        m_value += m_delta;
19    }
20    virtual void undo() override {
21        m_value = m_prevValue;
22    }
23private:
24    int& m_value;
25    int m_delta;
26    int m_prevValue;
27};
28
29// 命令管理类
30class CommandManager {
31public:
32    void execute(Command* cmd) {
33        m_commands.push_back(cmd);
34        cmd->execute();
35    }
36    void undo() {
37        if (!m_commands.empty()) {
38            Command* cmd = m_commands.back();
39            m_commands.pop_back();
40            cmd->undo();
41            delete cmd;
42        }
43    }
44private:
45    vector<Command*> m_commands;
46};
47
48int main() {
49    int value = 0;
50    CommandManager manager;
51    manager.execute(new ConcreteCommand(value, 1)); // value = 1
52    manager.execute(new ConcreteCommand(value, 2)); // value = 3
53    manager.execute(new ConcreteCommand(value, 3)); // value = 6
54    manager.undo(); // value = 3
55    manager.undo(); // value = 1
56    manager.undo(); // value = 0
57    manager.undo(); // do nothing
58    return 0;
59}

Composite Command

组合命令, 转账, 提款后取款, 组合模式

1struct CompositeBankAccountCommand : vector<BankAccountCommand>, Command

组合命令需要全部执行才能算成功, 所以call和undo需要判断, 中间步骤出错也需要把已经做的步骤撤回等等

Command Query Separation

命令查询分开

  • Commands, 指导系统执行一些操作参与状态变化但是没有返回值
  • Queries, 返回值但是不改变状态
 1class Creature
 2{
 3    int strength, agility;
 4public:
 5    Creature(int strength, int agility)
 6            : strength{strength}, agility{agility}
 7    {}
 8
 9    void process_command(const CreatureCommand &cc);
10    int process_query(const CreatureQuery &q) const;
11};

Interpreter

解释器模式

显著的例子:

  • 数字字面量, 需要用二进制存储, 转换函数atof
  • 正则表达式, 能够在字符串中匹配特定的模式, (domain-specific-language)DSL(领域专用语言), 使用之前必须保证正确解释
  • 结构化的数据, 比如csv, xml, json需要先解释后使用
  • 成熟的编程语言, 比如c, python在编译或者解释的时候先要对代码进行解释

Numeric Expression Evaluator

数学表达式求值

Lexing

词法分析, 把字符序列转化为tokens符号, tokens是句法的主要元素, 最后以一串平面序列结束, token可以是以下:

  • 整数
  • 操作符
  • 开闭括号
Parsing

语法分析, 把tokens序列转换为有意义的, 结构化的, 面向对象的数据

完整代码:

  1#include <string>
  2#include <utility>
  3#include <iostream>
  4#include <ostream>
  5#include <sstream>
  6#include <vector>
  7
  8using namespace std;
  9
 10struct Token
 11{
 12    enum Type
 13    {
 14        t_integer,
 15        t_plus,
 16        t_minus,
 17        t_lparen,
 18        t_rparen,
 19    };
 20
 21    Type type;
 22    string text;
 23
 24    explicit Token(Type type, string text) :
 25            type(type), text(std::move(text))
 26    {}
 27
 28    friend ostream &operator<<(ostream &os, const Token &obj)
 29    {
 30        return os << "`" << obj.text << "`";
 31    }
 32};
 33
 34vector<Token> lex(const string &input)
 35{
 36    vector<Token> result;
 37    ostringstream buffer;
 38    auto add_integer = [&] {
 39        if (buffer.precision()) {
 40            result.emplace_back(Token{Token::t_integer, buffer.str()});
 41            buffer.str("");
 42        }
 43    };
 44    for (char c : input) {
 45        switch (c) {
 46            case '+':
 47                add_integer();
 48                result.emplace_back(Token{Token::t_plus, "+"});
 49                break;
 50            case '-':
 51                add_integer();
 52                result.emplace_back(Token{Token::t_minus, "-"});
 53                break;
 54            case '(':
 55                add_integer();
 56                result.emplace_back(Token{Token::t_lparen, "("});
 57                break;
 58            case ')':
 59                add_integer();
 60                result.emplace_back(Token{Token::t_rparen, ")"});
 61                break;
 62            case '0':
 63            case '1':
 64            case '2':
 65            case '3':
 66            case '4':
 67            case '5':
 68            case '6':
 69            case '7':
 70            case '8':
 71            case '9':
 72                buffer << c;
 73                break;
 74            default:
 75                break;
 76        }
 77    }
 78    add_integer();
 79    return result;
 80}
 81
 82struct Element
 83{
 84    virtual int eval() const = 0;
 85};
 86
 87struct Integer : Element
 88{
 89    int value;
 90
 91    explicit Integer(const int value) :
 92            value(value)
 93    {}
 94
 95    int eval() const override
 96    { return value; }
 97};
 98
 99struct BinaryOperation : Element
100{
101    enum Type
102    {
103        t_addition,
104        t_subtraction,
105    };
106
107    Type type;
108    shared_ptr<Element> lhs, rhs;
109
110    int eval() const override
111    {
112        if (type == t_addition) {
113            return lhs->eval() + rhs->eval();
114        } else {
115            return lhs->eval() - rhs->eval();
116        }
117    }
118};
119
120shared_ptr<Element> parse(const vector<Token> &tokens)
121{
122    auto result = make_unique<BinaryOperation>();
123    bool have_lhs = false;
124    for (int i = 0; i < tokens.size(); ++i) {
125        auto token = tokens[i];
126        switch (token.type) {
127            case Token::t_integer: {
128                int value = stoi(token.text);
129                auto integer = make_shared<Integer>(value);
130                if (!have_lhs) {
131                    result->lhs = integer;
132                    have_lhs = true;
133                } else {
134                    result->rhs = integer;
135                }
136            }
137            case Token::t_plus:
138                result->type = BinaryOperation::t_addition;
139                break;
140            case Token::t_minus:
141                result->type = BinaryOperation::t_subtraction;
142                break;
143            case Token::t_lparen: {
144                int j = i;
145                for (; j < tokens.size(); ++j) {
146                    if (tokens[j].type == Token::t_rparen) {
147                        break;
148                    }
149                }
150                vector<Token> subexpression(&tokens[i + 1], &tokens[j]);
151                auto element = parse(subexpression);
152                if (!have_lhs) {
153                    result->lhs = element;
154                    have_lhs = true;
155                } else {
156                    result->rhs = element;
157                    i = j;
158                }
159            }
160            case Token::t_rparen:
161                break;
162        }
163    }
164    return result;
165}
166
167template<typename T>
168ostream &operator<<(ostream &os, vector<T> vec)
169{
170    for (auto &e : vec) {
171        os << e;
172    }
173    return os;
174}
175
176int main()
177{
178    auto tokens = lex("4+(13+2)");
179    cout << tokens << endl;
180    auto parsed = parse(tokens);
181    cout << parsed->eval() << endl;
182}

Parsing with Boost.Spirit

Boost.Spirit提供简明的API来创建parser, 没有明显区分lexing和parsing步骤, 允许自己定义文本的结构怎样映射成对象类型

Abstract Syntax Tree

抽象语法树

Parser

BNF语法

Printer

Iterator

迭代器模式, 很多数据结构都涉及到遍历

Iterators in the Standard Library

注: range-based for循环需要在类里面实现迭代器, 原生实现方式

 1template<typename T, int N>
 2class rray
 3{
 4public:
 5    using iterator = T *;
 6
 7    iterator begin()
 8    {
 9        return &data[0];
10    }
11
12    iterator end()
13    {
14        return &data[N];
15    }
16
17    T &operator[](int index)
18    {
19        return data[index];
20    }
21
22private:
23    T data[N];
24};
25
26int main(int argc, char *argv[])
27{
28    Aray<int, 10> a{};
29    for (auto &it : a) {
30        it = 1;
31    }
32}

vector里面的迭代器样式: iterator, const_iterator, 函数begin(), cbegin(), rbegin(), crbegin() c代表const, r代表reserved, reserved能够遍历vector中没写数据的部分

Traversing a Binary Tree

pre-oder

遍历二叉树, 前序中序后序

Iteration with Coroutines

post-oder, 用递归的方式

Mediator

中间者模式, 大多数类和类的通信关系都是通过指针引用进行, 也有设计需要两个对象互相不知道对方存在

中间者模式目的是减轻组件之间的通信

 1#include <iostream>
 2#include <string>
 3#include <vector>
 4
 5using namespace std;
 6
 7class Colleague;
 8
 9// 抽象中介者
10class Mediator {
11public:
12    virtual void send(string message, Colleague* colleague) = 0;
13};
14
15// 具体中介者
16class ConcreteMediator : public Mediator {
17public:
18    void setColleague(vector<Colleague*> colleagues) {
19        this->colleagues = colleagues;
20    }
21
22    void send(string message, Colleague* colleague) {
23        for (auto c : colleagues) {
24            if (c != colleague) {
25                c->receive(message);
26            }
27        }
28    }
29
30private:
31    vector<Colleague*> colleagues;
32};
33
34// 抽象同事类
35class Colleague {
36public:
37    Colleague(Mediator* mediator) : mediator(mediator) {}
38
39    virtual void send(string message) = 0;
40    virtual void receive(string message) = 0;
41
42protected:
43    Mediator* mediator;
44};
45
46// 具体同事类
47class ConcreteColleagueA : public Colleague {
48public:
49    ConcreteColleagueA(Mediator* mediator) : Colleague(mediator) {}
50
51    void send(string message) {
52        mediator->send(message, this);
53    }
54
55    void receive(string message) {
56        cout << "ConcreteColleagueA received message: " << message << endl;
57    }
58};
59
60class ConcreteColleagueB : public Colleague {
61public:
62    ConcreteColleagueB(Mediator* mediator) : Colleague(mediator) {}
63
64    void send(string message) {
65        mediator->send(message, this);
66    }
67
68    void receive(string message) {
69        cout << "ConcreteColleagueB received message: " << message << endl;
70    }
71};
72
73int main() {
74    ConcreteMediator* mediator = new ConcreteMediator();
75    ConcreteColleagueA* colleagueA = new ConcreteColleagueA(mediator);
76    ConcreteColleagueB* colleagueB = new ConcreteColleagueB(mediator);
77    vector<Colleague*> colleagues = {colleagueA, colleagueB};
78    mediator->setColleague(colleagues);
79
80    colleagueA->send("Hello, colleagueB!");
81    colleagueB->send("Hi, colleagueA!");
82
83    delete colleagueA;
84    delete colleagueB;
85    delete mediator;
86
87    return 0;
88}

Chat Room

Person接收发送广播, ChatRoom加入人,发送广播, 转发信息给人

Mediator with Events

简单的用类实现类似Observer观察者模式, 另一种办法是用事件, 参与者订阅事件来接收通知, 也可以通过发送消息来触发事件

基础的C++不支持事件, Boost.Signal2提供需要的功能. 其中的术语: signals代表生成通知的对象, slots处理通知的函数

 1#include <string>
 2#include <iostream>
 3#include <boost/signals2.hpp>
 4
 5using namespace std;
 6using namespace boost;
 7
 8struct EventData
 9{
10    virtual ~EventData() = default;
11    virtual void print() const = 0;
12};
13
14struct PlayerScoreData : EventData
15{
16    string player_name;
17    int goals_scored_so_far;
18
19    PlayerScoreData(string player_name, const int goals_scored_so_far) :
20            player_name(std::move(player_name)), goals_scored_so_far(goals_scored_so_far)
21    {}
22
23    void print() const override
24    {
25        cout << player_name << "has scored! (their "
26             << goals_scored_so_far << "goal)" << "\n";
27    }
28};
29
30struct Game
31{
32    signals2::signal<void(EventData *)> events;
33};
34
35struct Player
36{
37    string name;
38    int goals_scored = 0;
39    Game &game;
40
41    Player(string name, Game &game) :
42            name(std::move(name)), game(game)
43    {}
44
45    void score()
46    {
47        goals_scored++;
48        PlayerScoreData ps{name, goals_scored};
49        game.events(&ps);
50    }
51};
52
53struct Coach
54{
55    Game &game;
56
57    explicit Coach(Game &game) : game(game)
58    {
59        game.events.connect([](EventData *e) {
60            auto *ps = dynamic_cast<PlayerScoreData *>(e);
61            if (ps && ps->goals_scored_so_far < 3) {
62                cout << "coach says: well done, " << ps->player_name << "\n";
63            }
64        });
65    }
66};
67
68int main()
69{
70    Game game;
71    Player player{"helywin", game};
72    Coach coach{game};
73    player.score();
74    player.score();
75    return 0;
76}

中间者模式通过绑定触发事件和接收者来隔离两者之间的互相引用和依赖, 同时能够一对多多对一的进行通信

更高明的中间者实现使用事件允许参与者订阅和取消订阅系统中发生的事件. 组件和组件之间发送的消息可以视为events.

Memento

备忘录模式, 命令模式记录的变更允许回滚到系统任何时间点, 但有时候并不关心回放到系统的状态, 但是需要关心能回到之前的状态.

命令模式的存储的是修改过程, 备忘录模式存储的是修改后的状态

Bank Account

 1Memento deposit(int amount)
 2{
 3    balance += amount;
 4    return { balance };
 5}
 6
 7class Memento
 8{
 9    int balance;
10}
11
12BankAccount ba{ 100 };
13auto m1 = ba.deposit(50);
14auto m2 = ba.deposit(25);
15cout << ba << "\n"; // Balance: 175
16
17// undo to m1
18ba.restore(m1);
19cout << ba << "\n"; // Balance: 150
20
21// redo
22ba.restore(m2);
23cout << ba << "\n"; // Balance: 175

Undo and Redo

单个账号状态备份, 用shared_ptr存储Memento

总结:

每个Memento对象都存储一个完整的数据能够把当前系统恢复到对应的状态

Null Object

纯抽象类用来做基类指针时, 比如Logger, 当并不需要类记录日志时, 没有适用的Logger类让其不记录日志

Null Object

这时需要一个NullLogger实现Logger中的函数并是个空函数

shared_ptr is not a Null Object

共享指针不是空对象

1shared_ptr<int> n;
2int x = *n + 1;

Design Improvements

提升BankAccount的使用性

  • 在所有的地方检查指针
  • 设置默认值
  • 适用可选类型std::optional

Implicit Null Object

 1#include <memory>
 2#include <string>
 3#include <iostream>
 4
 5using namespace std;
 6
 7struct Logger
 8{
 9    virtual ~Logger() = default;
10    virtual void info(const string &s) = 0;
11    virtual void warn(const string &s) = 0;
12};
13
14struct ConsoleLogger : Logger
15{
16    void info(const string &s) override
17    {
18        cout << "Info: " << s << endl;
19    }
20
21    void warn(const string &s) override
22    {
23        cout << "Warn: " << s << endl;
24    }
25};
26
27struct NullLogger : Logger
28{
29    void info(const string &s)
30    {};
31
32    void warn(const string &s)
33    {};
34};
35
36struct OptionalLogger : Logger
37{
38    shared_ptr<Logger> impl;
39    static shared_ptr<Logger> no_logging;
40
41    explicit OptionalLogger(const shared_ptr<Logger> &logger) : impl{logger}
42    {}
43
44    virtual void info(const string &s) override
45    {
46        if (impl) impl->info(s);
47    }
48
49    virtual void warn(const string &s) override
50    {
51        if (impl) impl->warn(s);
52    }
53};
54
55shared_ptr<Logger> OptionalLogger::no_logging{};
56
57struct User
58{
59    string name;
60    shared_ptr<OptionalLogger> logger;
61
62    explicit User(string name, const shared_ptr<Logger> &logger = OptionalLogger::no_logging) :
63            name(std::move(name)),
64            logger{make_shared<OptionalLogger>(logger)}
65    {}
66
67    void log()
68    {
69        logger->info(name);
70    }
71
72};
73
74int main()
75{
76    User u1("u1");
77    u1.log();
78    shared_ptr<ConsoleLogger> logger = make_shared<ConsoleLogger>();
79    User u2("u2", logger);
80    u2.log();
81    return 0;
82}

std::optional的用法

std::optional为容器的变量可以具有bool操作符运算来判断值是否有效, 比如返回值是optional<string>, 可以之接用if判断而不用调用值然后判断empty, 对于接口来说相对统一

Observer

C#等语言有开箱即用的, C++需要自己实现

观察者模式是一种行为型设计模式,它的作用是当一个对象的状态发生变化时,能够自动通知其他关联对象,自动刷新对象状态。观察者模式完美的将观察者和被观察的对象分离开

 1#include <iostream>
 2#include <vector>
 3using namespace std;
 4
 5class Observer {
 6public:
 7    virtual void update(int data) = 0;
 8};
 9
10class Subject {
11public:
12    void attach(Observer* observer) {
13        observers.push_back(observer);
14    }
15    void detach(Observer* observer) {
16        for (auto it = observers.begin(); it != observers.end(); ++it) {
17            if (*it == observer) {
18                observers.erase(it);
19                return;
20            }
21        }
22    }
23    void notify(int data) {
24        for (auto observer : observers) {
25            observer->update(data);
26        }
27    }
28private:
29    vector<Observer*> observers;
30};
31
32class ConcreteObserver : public Observer {
33public:
34    ConcreteObserver(string name) : name(name) {}
35    void update(int data) override {
36        cout << "Observer " << name << " received data: " << data << endl;
37    }
38private:
39    string name;
40};
41
42class ConcreteSubject : public Subject {
43public:
44    void setData(int data) {
45        this->data = data;
46        notify(data);
47    }
48private:
49    int data;
50};
51
52int main() {
53    ConcreteSubject subject;
54    ConcreteObserver observer1("Observer 1");
55    ConcreteObserver observer2("Observer 2");
56    subject.attach(&observer1);
57    subject.attach(&observer2);
58    subject.setData(10);
59    subject.detach(&observer1);
60    subject.setData(20);
61    return 0;
62}

Property Observers

C++17 Property

 1#include <cstdio>
 2
 3class Person
 4{
 5    int age_ = 0;
 6
 7public:
 8    int get_age() const { return age_; }
 9    void set_age(int age) { age_ = age; }
10    __declspec(property(get=get_age, put=set_age)) int age;
11    void print() { printf("%d\n", age_); }
12};
13
14Person person;
15person.age = 10;

其中set_age()可以通知值的改变

Observer<T>

1struct PersonListener
2{
3    virtual void person_changed(Person &p, const string &property_name, const any new_value) = 0;
4};

更好的解决办法, 不光针对Person类型

 1template<typename T>
 2struct Observer
 3{
 4    virtual void field_changed(T &source, const string &field_name) = 0;
 5};
 6
 7struct ConsolePersonObserver : Observer<Person>
 8{
 9    void field_changed(Person& source, const string &field_name) override
10    {
11        cout << "Person's" << field_name << " has changed to " << source.get_age() << ".\n";
12    }
13};

这样做的好处可以同时观察好几个类

1struct ConsolePersonObserver : Observer<Person>, Observer<Creature>;

还可以用std::any绑定任意类型, 比如类似void *

Observable<T>

当Person成为可被观察的类时, 需要实现以下职责:

  • 用一个列表存储所有对Person类变化感兴趣的观察者们
  • 允许观察者订阅和取消订阅(subscribe()/unsubscribe())
  • 当发生改变并发出notify()时通知所有观察者

原型如下:

 1template <typename T>
 2struct Observable
 3{
 4    void notify(T &source, const string &name)
 5    {
 6        for (auto obs : observers)
 7        {
 8            obs->field_changed(source, name);
 9        }
10    }
11    void subscribe(Observer<T>* f) { observers.push_back(f); }
12    void unsubscribe(Observer<T> *f) {...}
13private:
14    vector<Observer<T> *> observers;
15};

notify函数在调用set_age函数时使用, 但是要判断值是否真的改变了

Connecting Observers and Observables

所有代码的实现

 1#include <string>
 2#include <iostream>
 3#include <vector>
 4#include <algorithm>
 5
 6using namespace std;
 7
 8struct Person;
 9
10template<typename T>
11struct Observer
12{
13    virtual void field_changed(T &source, const string &field_name) = 0;
14};
15
16template<typename T>
17struct Observable
18{
19    void notify(T &source, const string &name)
20    {
21        for (auto obs : observers) {
22            obs->field_changed(source, name);
23        }
24    }
25
26    void subscribe(Observer<T> *f)
27    { observers.push_back(f); }
28
29    void unsubscribe(Observer<T> *f)
30    {
31        observers.erase(remove(observers.begin(), observers.end(), observer),
32                        observers.end());
33    }
34
35private:
36    vector<Observer<T> *> observers;
37};
38
39struct Person : Observable<Person>
40{
41    int get_age() const
42    { return age_; }
43
44    void set_age(int age)
45    {
46        if (age_ == age) return;
47        age_ = age;
48        notify(*this, "age");
49    }
50
51    string get_name() const
52    { return name_; }
53
54    void set_name(const string &name)
55    {
56        if (name_ == name) return;
57        name_ = name;
58        notify(*this, "name");
59    }
60
61private:
62    int age_;
63    string name_;
64};
65
66struct ConsolePersonObserver : Observer<Person>
67{
68    void field_changed(Person &source, const string &field_name) override
69    {
70        // source.get_name写死有问题, 需要重载一个根据名称查找值的get_property(), 用std::variant
71        cout << "Person's " << field_name
72             << " has changed to " << source.get_name() << ".\n";
73    }
74};
75
76int main()
77{
78    Person p;
79    ConsolePersonObserver cpo;
80    p.subscribe(&cpo);
81    p.set_name("Wang");
82    return 0;
83}

Dependency Problems

当有一个值是依赖另一个值改变的时候, 代码就会很冗长, 比如can_vote这个值实际不存在, get的时候只是取age>18, 设置age时这个值改变也要判断是否改变并发送通知, 这个问题很难得到解决

Unsubscription and Thread Safety

由于std::vector是非线程安全的, 订阅和取消订阅不在一个线程中执行会出现问题, 解决办法是

  • 在通知, 订阅, 取消订阅时加上锁
  • 使用并发的vector, concurrent_vector

Reentrancy

函数可重入性, 当Person年龄大于17就自动取消订阅, 在field_changed函数里面取消订阅, 调用链:

notify() --> field_changed() --> unsubscribe()

这在调用时由于加锁会导致无法取消订阅, notify和unsubscribe都加锁了, 解决办法有两种

  • 避免出现这种情况
  • 取消订阅不加锁, 只是把观察者设为空指针, 通知时也不加锁, 判断当前是否为空指针, 因为数组的增加和遍历是不会出现线程安全问题
 1void unsubscribe(Observer<T>* o)
 2{
 3    auto it = find(observers.begin(), observers.end(), o);
 4    if (it != observers.end())
 5    *it = nullptr; // cannot do this for a set
 6}
 7//And, subsequently, when you notify(), you just need an extra check:
 8void notify(T& source, const string& name)
 9{
10    for (auto obs : observers)
11        if (obs)
12            obs->field_changed(source, name);
13}

这样解决了notify和unsubscribe的锁竞争(contention), 但是同时订阅和取消订阅仍然会出问题

另外一种办法是通知的时候取一份列表的拷贝

 1void notify(T& source, const string& name)
 2{
 3    vector<Observer<T>*> observers_copy;
 4    {
 5        lock_guard<mutex_t> lock{ mtx };
 6        observers_copy = observers;
 7    }
 8    for (auto obs : observers_copy)
 9        if (obs)
10            obs->field_changed(source, name);
11}

还可以用recursive_mutex替代mutex, 但是很多开发者都讨厌使用, 会丢失性能, 而且通过改变代码结构能避免

还有一些问题:

  • 如果观察者添加两次
  • 如果能重复添加观察者, 那么取消订阅呢
  • 如果改变容器, 使用std::set, std::unordered_set, 怎样实现
  • 观察者有优先级

Observer via Boost.Signals2

使用Boost::Signal2的方案

 1template <typename T>
 2struct Observable
 3{
 4    signal<void(T&, const string&)> property_changed;
 5};
 6
 7struct Person : Observable<Person>
 8{
 9    ...
10    void set_age(const int age)
11    {
12        if (this->age == age) return;
13        this->age = age;
14        property_changed(*this, "age");
15    }
16};
17
18// 使用
19
20Person p{123};
21auto conn = p.property_changed.connect([](Person&, const string& prop_name)
22{
23    cout << prop_name << " has been changed" << endl;
24});
25p.set_age(20); // name has been changed
26
27// later, optionally
28conn.disconnect();

Summary

实现观察者模式的决定

  • 决定要观察的信息
  • 观察者的类是
  • 是否每个观察者单独实现还是有一堆虚函数
  • 是否需要处理取消订阅
    • 如果不需要支持取消订阅,会节省很多时间, 因为不需要进行函数可重入性处理
    • 如果要支持显式的取消订阅函数, 不能直接erase-remove掉, 而是标记元素待移除然后再去移除
    • 如不希望直接使用指针,考虑使用weak_ptr
  • 如果Observer<T>会被多个线程调用, 考虑保护下标数组
    • 在每个相关的函数放上scoped_lock
    • 使用线程安全的集合比如TBB/PPL concurrent_vector. 你会失去排序保证
  • 如果允许多个下标代表同一来源, 那么不能使用std::set

很遗憾没有理想的观察者模式实现对应所有情况, 所以需要按照自己期望的来实现

State

状态模式, 状态是可以改变的, 重要的是谁触发了状态的改变, 有以下两种情况:

  • 状态是带行为的类
  • 状态和转移只是枚举. 我们用状态机来表述这些状态和过程

State-Driven State Transitions

简单的开关

要点:

  • 状态并不是抽象的

  • 其次状态允许从一个切换到另一个, 而且状态允许开关从一个状态到另一个状态而不是开关改变状态

  • 最令人困惑的是, 默认的on/off状态表示我们已经在这个状态

state.hp

 1class LightSwitch;
 2
 3struct State
 4{
 5    virtual void on(LightSwitch *ls)
 6    { cout << "Light is already on\n"; }
 7
 8    virtual void off(LightSwitch *ls)
 9    { cout << "Light is already off\n"; }
10};
11
12struct OnState : State
13{
14    OnState()
15    { cout << "Light turned on\n"; }
16
17    void off(LightSwitch *ls) override;
18};
19
20struct OffState : State
21{
22    OffState()
23    { cout << "Light turned off\n"; }
24
25    void on(LightSwitch *ls) override;
26};
27
28class LightSwitch
29{
30    State *state;
31public:
32    LightSwitch()
33    { state = new OffState(); }
34
35    void set_state(State *s)
36    { this->state = s; }
37
38    void on()
39    { state->on(this); }
40
41    void off()
42    { state->off(this); }
43};

state.cpp

 1#include <iostream>
 2
 3using namespace std;
 4
 5#include "state.hpp"
 6
 7void OnState::off(LightSwitch *ls)
 8{
 9    cout << "Switching light off...\n";
10    ls->set_state(new OffState);
11    delete this;
12}
13
14void OffState::on(LightSwitch *ls)
15{
16    cout << "Switching light on...\n";
17    ls->set_state(new OnState);
18    delete this;
19}
20
21int main()
22{
23    LightSwitch ls;
24    ls.on();
25    ls.off();
26    ls.off();
27}

state diagram

stateDiagram-v2
    on : Switch on
    off : Switch off
    on --> off: Turn off
    off --> on: Turn on
    on --> on: Already on
    off --> off: Already off
  

Handmade State Machine

利用枚举和数据结构进行状态机的状态转移(不完全)

 1enum class State
 2{
 3    off_hook,
 4    connecting,
 5    connected,
 6    on_hold,
 7    on_hook,
 8};
 9
10enum class Trigger
11{
12    call_dialed,
13    hung_up,
14    call_connected,
15    placed_on_hold,
16    taken_off_hold,
17    left_message,
18    stop_using_phone,
19};
20// 包括了当前状态和可能出现的触发条件和触发条件后的结果
21map<State, vector<pair<Trigger, State>>> rules;
22
23
24rules[State::off_hook] = {
25            {Trigger::call_dialed, State::connecting},
26            {Trigger::stop_using_phone, State::on_hook}
27    };
stateDiagram-v2

off_hook
connecting
connected
on_hold
on_hook

off_hook-->connecting: call_dialed
off_hook-->on_hook: stop_using_phone
connecting-->off_hook: hung_up
connecting-->connected: call_connected
connected-->on_hold: placed_on_hold
connected-->off_hook: hung_up
on_hold-->off_hook: hung_up
  

State Machines with Boost.MSM

Meta State Machine, 使用CRTP实现, boost库的MSM库和Statechart库

Summary

  • 除了Boost.MSM和Boost.Statechart还有许多其他的状态机实现方法, 比如QStateMachine,QP等

  • 除了状态机许多还支持Hierarchical State Machine(层级状态机)HSM, 例如MATLAB里面的StateFlow, 比如生病是一种状态, 生病这种状态包含了生不同的病的子状态

  • 值得思考现代状态机和状态模式之间的差距, 不要为了实现形式上的接口设计很多笨重不直观的东西

Strategy

策略模式, 把实现一件事不同的步骤封装到不同的接口里面, 然后封装到通用不变的算法或方法里面, 在动态和静态典范里面存在着。

策略模式是一种行为型设计模式,它定义了一族算法,将每个算法都封装起来,并且使它们之间可以互换。这个模式使得算法的变化可以独立于使用它的客户端。C++提供了多态性来实现这个模式

Dynamic Strategy

比如一段文本要以markdown或者html方式输出, 类似的代码如下

 1// 抽象的处理方法
 2struct ListStrategy
 3{
 4    virtual void start(ostringstream &oss) {}
 5    virtual void add_list_item(ostringstream &oss, const string &item) {}
 6    virtual void end(ostringstream &oss) {}
 7};
 8
 9// 输出列表的通用方法抽象
10struct TextProcessor
11{
12    void append_list(const vector<string> &items)
13    {
14        list_strategy->start(oss);
15        for (const auto &item : items) {
16            list_strategy->add_list_item(oss, item);
17        }
18        list_strategy->end(oss);
19    }
20private:
21    ostringstream oss;
22    unique_ptr<ListStrategy> list_strategy;
23};
24
25struct HtmlListStrategy : ListStrategy {...};
26struct MarkdownListStrategy : ListStrategy {...};

动态策略通过类的多态实现

Static Strategy

静态策略通过模板实现

 1template <typename LS>
 2struct TextProcessor
 3{
 4private:
 5    ostringstream oss;
 6    LS list_strategy;
 7}
 8
 9// 使用
10TextProcessor<MarkdownListStragegy> tpm;
11tpm.append_list(...);

采用静态还是动态看需要

Template Method

模板方法模式, 加上策略模式和工厂模式很相似. 策略模式和模板方法模式不同的地方在于策略模式使用组合(不管动态还是静态), 而模板方法模式使用继承. 核心的原则是在一个地方定义算法的骨架在另外的地方实现剩余的细节, 符合开闭原则

Game Simulation

Chess有initialize, startPlay, endPlay等函数, ChineseChess继承自Chess, run会调用这三个函数进行游戏, 而Chess需要做的只是继承前面三个函数而不用去管游戏怎么运行的, 相当于玩法流程骨架是Chess, 而实现算法的细节在实现具体的Chess类型

 1class Chess {
 2public:
 3    void play() {
 4        // 初始化游戏
 5        initialize();
 6
 7        // 开始游戏
 8        startPlay();
 9
10        // 结束游戏
11        endPlay();
12    }
13
14protected:
15    virtual void initialize() = 0;
16    virtual void startPlay() = 0;
17    virtual void endPlay() {};
18
19};
20
21class ChineseChess : public Chess {
22protected:
23    void initialize() {
24        cout << "初始化中国象棋游戏" << endl;
25    }
26
27    void startPlay() {
28        cout << "开始中国象棋游戏" << endl;
29    }
30};
31
32class InternationalChess : public Chess {
33protected:
34    void initialize() {
35        cout << "初始化国际象棋游戏" << endl;
36    }
37
38    void startPlay() {
39        cout << "开始国际象棋游戏" << endl;
40    }
41
42    void endPlay() {
43        cout << "国际象棋游戏结束" << endl;
44    }
45};
46
47int main() {
48    Chess *chineseChess = new ChineseChess();
49    chineseChess->play();
50
51    Chess *internationalChess = new InternationalChess();
52    internationalChess->play();
53
54    return 0;
55}

模板方法模式和策略模式都属于行为型设计模式,但它们有一些区别。以下是它们的区别:

  • 在模板方法模式中,抽象类定义了一个算法的框架,但是一些步骤的实现由具体子类决定。这种模式的实现是在编译时发生的。而在策略模式中,不同的算法是在运行时选择的,通过将算法封装在独立的类中,使得它们可以相互替换。策略模式的实现是在运行时发生的。
  • 模板方法模式中,抽象类是算法的核心,它定义了算法的骨架,具体实现由子类完成。而策略模式中,算法是核心,它被封装在独立的类中,并且可以在运行时选择。
  • 模板方法模式通常只针对一套算法,注重对同一个算法的不同细节进行抽象提供不同的实现。相比之下,策略模式注重多套算法多套实现,算法之间不应该有交集,因此算法和实现是分开的。

Visitor

访问者模式, 当你获取了一个类型层次, 除非能够接触到源代码否则不可能在结构里面添加函数

表达式类

 1struct Expression {};
 2
 3struct DoubleExpression : Expression
 4{
 5    double value;
 6    explicit DoubleExpression(const double value) : value{value} {};
 7};
 8
 9struct AdditionExpression : Expression
10{
11    Expression *left, *right;
12    AdditionExpression(Expression *const left, Expression *const right) : left{left}, right{right}{};
13};

Instrusive Visitor

侵入式的访问者, 违反开闭原则, 直接修改代码, 要实现打印直接在Expression里面添加虚函数print

Reflective Printer

构造一个ExpressionPrinter, 传入Expression指针, 利用dynamic_cast判断当前指针类的具体子类类型, 使用此方法不需要在基类中增加接口也能实现特定功能的增加

 1#include <sstream>
 2#include <iostream>
 3
 4using namespace std;
 5
 6struct Expression
 7{
 8    // dynamic_cast 需要析构函数为虚函数
 9    virtual ~Expression() = default;
10};
11
12struct DoubleExpression : Expression
13{
14    double value;
15    explicit DoubleExpression(const double value) : value{value} {};
16};
17
18struct AdditionExpression : Expression
19{
20    Expression *left, *right;
21    AdditionExpression(Expression *const left, Expression *const right) : left{left}, right{right} {};
22};
23
24struct ExpressionPrinter
25{
26    void print(Expression *e);
27    void print(DoubleExpression *de);
28    void print(AdditionExpression *ae);
29    string str() const { return oss.str(); }
30private:
31    ostringstream oss;
32};
33
34// dynamic_cast的正确用法
35void ExpressionPrinter::print(Expression *e)
36{
37    if (auto de = dynamic_cast<DoubleExpression *>(e)) {
38        print(de);
39    } else if (auto ae = dynamic_cast<AdditionExpression *>(e)) {
40        print(ae);
41    }
42}
43
44void ExpressionPrinter::print(DoubleExpression *de)
45{
46    oss << de->value;
47}
48
49void ExpressionPrinter::print(AdditionExpression *ae)
50{
51    oss << "(";
52    print(ae->left);
53    oss << "+";
54    print(ae->right);
55    oss << ")";
56}
57
58int main()
59{
60    auto ae = new AdditionExpression(new DoubleExpression(1.0), new DoubleExpression(2.0));
61    auto ae1 = new AdditionExpression(ae, new DoubleExpression(3));
62    ExpressionPrinter printer;
63    printer.print(ae1);
64    cout << printer.str();
65    return 0;
66}

WTH is Dispatch

dispatch(分派)的问题是找出需要调用哪一个函数, 特定的, 为了调用需要多少信息

举例子就是通过基类指针外部调用函数怎样映射到子类函数去

1struct Pet {}
2struct Cat : Pet {}
3struct Dog : Pet {}
4
5void func(Cat *cat) {}
6void func(Dog *dog) {}
7
8Pet *pet = new Dog;
9func(pet);

这样造成的问题就是func不知道用哪个函数去实现, 所以只能通过dynamic_cast去判断, 另一种办法是用多态, 它能被正确的分派到必要的组件, 能够调用必要的重载. 也叫double dispatch(双分派), 因为:

  • 在实际的对象上做了多态调用
  • 在多态调用里面, 在调用重载. 在对象内, this指针是有一个精确的类型, 所以正确的重载也被调用
 1struct Pet {
 2    virtual void call() = 0;
 3}
 4struct Cat : Pet {
 5    void call() override { func(this); }
 6}
 7struct Dog : Pet {
 8    void call() override { func(this); }
 9}
10
11void func(Cat *cat) {}
12void func(Dog *dog) {}
13
14Pet *pet = new Dog;
15pet->call();

在调用重载后的函数call之后会根据vtable自动定位到Dog::call, 从而this的类型也就清楚了

Classic Visitor

典型的访问者模式使用的是双分派, 约定的函数叫法:

  • 访问者的成员函数叫visit()
  • 贯穿层次成员函数实现叫accept()

表达式例子:

 1struct Expression
 2{
 3    virtual void accept(ExpressionVisitor *visitor) = 0;
 4};
 5
 6// 继承了Expression的类要实现accept
 7void accept(ExpressionVisitor *visitor)
 8{
 9    visitor->visit(this);
10}
11
12struct ExpressionVisitor
13{
14    virtual void visit(DoubleExpression *de) = 0;
15    virtual void visit(AdditionExpression *ae) = 0;
16};

Implementing an Additional Visitor

好处就是只需要在层次(hierarchy)中实现一遍accept(), 你永远不需要再次接触层次的成员, 比如计算表达式。

 1class ElementA;
 2class ElementB;
 3
 4class Element {
 5public:
 6    virtual void accept(Visitor& visitor) = 0;
 7    virtual void operation() = 0;
 8};
 9
10class ElementA : public Element {
11public:
12    void accept(Visitor& visitor) override;
13    void operation() override { cout << "ElementA::operation()" << endl; }
14};
15
16class ElementB : public Element {
17public:
18    void accept(Visitor& visitor) override;
19    void operation() override { cout << "ElementB::operation()" << endl; }
20};
21
22class Visitor {
23public:
24    virtual void visit(ElementA& element) = 0;
25    virtual void visit(ElementB& element) = 0;
26};
27
28class ConcreteVisitor : public Visitor {
29public:
30    void visit(ElementA& element) override { cout << "ConcreteVisitor::visit(ElementA&)" << endl; }
31    void visit(ElementB& element) override { cout << "ConcreteVisitor::visit(ElementB&)" << endl; }
32};
33
34int main() {
35    ElementA elementA;
36    ElementB elementB;
37    ConcreteVisitor visitor;
38
39    elementA.accept(visitor); // ConcreteVisitor::visit(ElementA&)
40    elementB.accept(visitor); // ConcreteVisitor::visit(ElementB&)
41
42    return 0;
43}

Acyclic Visitor

Acyclic Visitor, 基于RTTI(Run-Time Type Information), 优点是不存在访问层次的限制, 但是牵涉性能问题

Acyclic Visitor模式是Cyclic Visitor模式的一种变体,它允许访问者访问对象的所有成员,但不包括继承来的成员。这种模式比较简单,只需要一次访问对象

Acyclic Visitor代码示例:

 1#include <iostream>
 2#include <sstream>
 3
 4using namespace std;
 5
 6template<typename Visitable>
 7struct Visitor
 8{
 9    virtual void visit(Visitable &obj) = 0;
10};
11
12// 需要所有的数据模型都能接受visitor, 但是所有的特化都是唯一的, 需要引进marker interface, 带虚析构函数的空类
13struct VisitorBase
14{
15    virtual ~VisitorBase() = default;
16};
17
18struct Expression
19{
20    virtual ~Expression() = default;
21
22    virtual void accept(VisitorBase &obj)
23    {
24        using EV = Visitor<Expression>;
25        // Expression类不执行
26        if (auto ev = dynamic_cast<EV *>(&obj))
27            ev->visit(*this);
28    }
29};
30
31struct DoubleExpression : Expression
32{
33    double value;
34    explicit DoubleExpression(const double value) : value{value} {};
35    void accept(VisitorBase &obj) override
36    {
37        using EV = Visitor<DoubleExpression>;
38        if (auto ev = dynamic_cast<EV *>(&obj))
39            ev->visit(*this);
40    }
41};
42
43struct AdditionExpression : Expression
44{
45    Expression *left, *right;
46    AdditionExpression(Expression *const left, Expression *const right) : left{left}, right{right} {};
47    void accept(VisitorBase &obj) override
48    {
49        using EV = Visitor<AdditionExpression>;
50        if (auto ev = dynamic_cast<EV *>(&obj))
51            ev->visit(*this);
52    }
53};
54
55struct ExpressionPrinter : VisitorBase,
56                           Visitor<DoubleExpression>,
57                           Visitor<AdditionExpression>
58{
59    void visit(DoubleExpression &obj) override;
60    void visit(AdditionExpression &obj) override;
61    string str() const { return oss.str(); }
62private:
63    ostringstream oss;
64};
65
66void ExpressionPrinter::visit(DoubleExpression &obj)
67{
68    oss << obj.value;
69}
70
71void ExpressionPrinter::visit(AdditionExpression &obj)
72{
73    oss << "(";
74    obj.left->accept(*this);
75    oss << "+";
76    obj.right->accept(*this);
77    oss << ")";
78}
79
80int main()
81{
82    auto ae = new AdditionExpression(new DoubleExpression(1.0), new DoubleExpression(2.0));
83    Expression *ae1 = new AdditionExpression(ae, new DoubleExpression(3));
84    auto printer = new ExpressionPrinter;
85    ae1->accept(*printer);
86    cout << printer->str();
87    return 0;
88}

Variants and std::visit

std::visit是标准库里面的模板, 配合std::variant可以存储不同的值, 类似于联合体

1variant<string, int> house;
2house = 221;
3house = "Castle";

完整例子

 1#include <variant>
 2#include <string>
 3#include <iostream>
 4#include <type_traits>
 5
 6using namespace std;
 7
 8struct AddressPrinter
 9{
10    void operator()(const string &house_name) const
11    {
12        cout << "A house called " << house_name << endl;
13    }
14
15    void operator()(const int house_number) const
16    {
17        cout << "House number " << house_number << endl;
18    }
19};
20
21int main()
22{
23    using House = variant<string, int>;
24    House house{123};
25    AddressPrinter ap;
26    // 用visitor类
27    std::visit(ap, house);
28    // 用匿名表达式
29    std::visit([](auto &arg) {
30        // 当T是引用类型,decay<T>::type返回T引用的元素类型;当T是非引用类型,decay<T>::type返回T的类型
31        using T = decay_t<decltype(arg)>;
32        if constexpr (is_same_v<T, string>) {
33            cout << "A house called " << arg.c_str() << endl;
34        } else {
35            cout << "House number" << arg << endl;
36        }
37    }, house);
38    return 0;
39}

可以参考[C++函数式编程]({% post_path ‘Cpp函数式编程’ %}#用模式匹配更好地处理代数数据类型)中使用overload模式利用模板和匿名函数构建访问者

可以配合``

Summary

访问者模式允许对任何层次的元素添加相同的方法, 实现包括

  • Intrusive: 直接对基类添加虚函数, 每个类实现这个虚函数, 破坏了OCP原则
  • Reflective: 增加visitor类, 用dynamic_cast实时派发
  • Classic: (双派发), 整个层次需要更改, 但是只需要更改一次并且是通用的方法. 每个层次都需要学会accept() visitor. 然后子类化visitor保证所有层次的功能都能实现

访问者模式在串联的解释器模式中很常见: 解释了输入转化为对象, 渲染抽象的语法树就需要用ostringstream和所有的对象类型打交道

Appendix A: Functional Design Patterns

可以参考[C++函数式编程]({% post_path ‘Cpp函数式编程’ %})

单子(monad,也译单体)是函数式编程中的一种抽象数据类型,其特别之处在于,它是用来表示计算而不是数据的。在以函数式风格编写的进程中,单子可以用来组织包含有序操作的过程,或者用来定义任意的控制流(比如处理并发、异常、延续)

单子的构造包括定义两个操作bind和return,还有一个必须满足若干性质的类型构造器M

Maybe Monad

C++有很多方式表示不存在的值:

  • 使用nullptr
  • 使用智能指针, 可以测试是否缺少值
  • std::optional<T>可以存储std::nullopt如果没有值

使用空指针需要每次使用时判断是否为空, Maybe的实现(编译不能通过)

 1#include <string>
 2#include <iostream>
 3
 4using namespace std;
 5
 6struct Address
 7{
 8    string *house_name = nullptr;
 9};
10
11struct Person
12{
13    Address *address = nullptr;
14};
15
16template<typename T>
17struct Maybe
18{
19    T *context;
20
21    Maybe(T *context) : context(context) {}
22
23    template<typename Func>
24    auto With(Func evaluator)
25    {
26        context != nullptr ? maybe(evaluator(context)) : nullptr;
27    }
28
29    template<typename TFunc>
30    auto Do(TFunc action)
31    {
32        if (context != nullptr) action(context);
33        return *this;
34    }
35};
36
37template<typename T>
38auto maybe(T *context)
39{
40    return Maybe<T>(context);
41}
42
43void print_house_name(Person *p)
44{
45    auto maybe1 = maybe(p)
46            .With([](Person *x) { return x->address; })
47            .With([](Address *x) { return x->house_name; })
48            .Do([](auto x) { cout << *x << endl; });
49}
50
51int main()
52{
53    auto a = new Address;
54    auto p = new Person;
55    p->address = a;
56    a->house_name = new string("hello");
57    return 0;
58}