东风草堂博客

栈在表达式求值中的应用

实际上，编译器就是通过两个栈来实现的。其中一个保存操作数的栈，另一个是保存运算符的栈。我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较。

如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。

栈在括号匹配中的应用

什么是完美转发？网上资料很多，简单总结一下，就是通过函数参数传递给函数里面的另外一个函数时，参数的属性不能变化，原来是左值的还得是左值，原来是右值的还得是右值。

左值比较简单，默认就是，关键是这右值，当一个右值当作参数传递给另外一个函数时，这个右值便有了自己的名字，于是变成了左值，这才是问题所在。

1
2
3
4
5
6
7

funtion(左值) {
    forward(左值)
}

funtion(右值) {
    forward(右值)
}

我们要让它进入转发的目标函数参数时也是右值才行，这里需要用到特殊引用和std::forward来解决问题，另外需要了解什么是引用折叠。

异常处理

就一个连接池而已，为什么要采用装饰者模式，听着咋感觉那么高深？

所谓连接池，也就是连接先不close，放入池中，等待下次需要用的时候，直接从池中取出即可用，省去了tcp握手的时间，所以这个可以看作是一个长连接，知道连接池清除空闲连接把多余的连接清除掉才会释放。

而普通的连接，用完后如果生命周期内不再使用了，就会销毁掉。

所以基于普通的连接，要定义出线程池的那种用完放回线程池的连接，就需要把close的方法进行重写，所以可以采用继承的方法实现，相当于产生了两个子类，一个是普通连接类，一个是线程池化的连接类。

这个设计模式的功能就是实现订阅与发布的功能，一旦有消息更新，即可将最新的消息同步给所有的订阅者，无需订阅者主动来询问，如果订阅者无需这些消息了，只需要取消订阅即可，后续有新的消息就不会再次打扰。

适用于对于相同的数据需要表现为不同的行为的功能，比如，得知爸爸要回来了，儿子就会立马停止玩游戏，妈妈立马开始准备晚餐。也有可能是很多人都想订阅这些数据，比如求职者先将要找工作的需求交给猎头，猎头那里有很多这样的需求，一旦有公司有需求，猎头那里就会立马通知所有的要找这份工作的求职者，让他们分别去面试，公司选择优秀的人才入职。

生活中有很多类似的场景，都可以用观察者模式来解释，所以设计模式的灵感也来源于生活。另外一方面，也实现了逻辑与应用的分离，从上面的例子也可以看出，底层数据只有一份，但是可以用在几个不同的场景，如果新的场景，也就相当于多了一个订阅者而已。

基于模板实现的观察者模式

网上面有很多实现了的观察者模式，用的都是普通类，但由于模型应用场景，比如订阅的消息类型各式各样，有string、int或者自定义class，那就需要改用模板类了。

最近有很多朋友在问这个问题，那我就写篇短文集中回答一下，七夕我都不过了，有问题随时私聊我，捂脸。

什么是公众号迁移？

公众号不支持直接变更主体。公众平台推出帐号迁移功能，通过此功能可将A账号的粉丝、文章素材（可选）、微信号（可选）、违规记录迁移至B帐号。

有人之前问，我的公众号是个人类型的号，可不可以升级为企业类型的号，所以答案是不可以直接升级，但可以通过迁移来改变你的主体。

具体做法是，先注册一个企业类型的订阅号，再将你之前的个人订阅号迁移过来，之后你使用企业号发文就好了，之前个人号上的文章和粉丝都可以迁移过来，间接的升级了你的个人号为企业号。

简简单单说两个事。

公众号留言功能开通说明

现在是2021年了，留言功能还是很多公号作者的一大难题，没有留言功能，自己写的文章感觉得不到半点的反馈，也不知道有没有赞赏或者批评，非常难受，导致本来就是写写文章看看的小伙伴更加难以坚持下去了。

其实从2018年3月份开始，官方就关闭了对于新开的微信个人公众号的留言功能，原因其实也简单，由于微信体量越来越大，所以在监管这一块就需要担起更大的责任了，上面也会给他们更大的压力，这个大家应该都能理解。

我前面文章也说过了，目前来看，对于个人号来说，想要再开通微信留言功能的办法只有一个。

队列

循环队列，固定容器大小，实现如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

#include <iostream>

using namespace std;

const int MAX_QUEUE_SIZE = 102;

template<typename T>
class Node {
public:
    T data;
    Node<T>* next;
};

template<typename T>
class CircularQueue {
public:
    CircularQueue(): front(NULL), rear(NULL), size(0) {}
    bool enqueue(T data);
    bool dequeue(T& data);
    bool isFull() { return size == MAX_QUEUE_SIZE; }
    bool isEmpty() { return size == 0; }
    int getSize() { return size; }
    void printQueue();

private:
    Node<T>* front;
    Node<T>* rear;
    int size;
};

template<typename T>
bool CircularQueue<T>::enqueue(T data) {
    if (isFull()) {
        if (front == NULL) {
            return false; // 队列为空的情况
        }
        // 队列已满，直接修改最早插入节点的值
        front->data = data;
        front = front->next; // 移动头指针
        rear = rear->next; // 移动尾指针
    } else {
        Node<T>* newNode = new Node<T>();
        newNode->data = data;
        newNode->next = front;
        if (isEmpty()) {
            front = newNode;
            rear = newNode;
        } else {
            rear->next = newNode;
            rear = newNode;
        }
        size++;
    }
    return true;
}

template<typename T>
bool CircularQueue<T>::dequeue(T& data) {
    if (isEmpty()) {
        return false;
    }
    Node<T>* temp = front;
    data = temp->data;
    front = front->next;
    delete temp;
    size--;
    return true;
}

template<typename T>
void CircularQueue<T>::printQueue() {
    if (isEmpty()) {
        cout << "Queue is empty" << endl;
    } else {
        Node<T>* temp = front;
        while (temp != rear) {
            cout << temp->data << " ";
            temp = temp->next;
        }
        cout << rear->data << " " << endl;
    }
}

int main() {
    CircularQueue<int> q;
    for (int i = 0; i < 100; i++) {
        q.enqueue(i);
    }
    q.printQueue();
    q.enqueue(100);
    q.enqueue(101);
    q.enqueue(102);
    q.enqueue(103);
    q.enqueue(104);
    q.printQueue();
    return 0;
}

在用数组实现的非循环队列中，队满的判断条件是 tail == n，队空的判断条件是 head == tail。那针对循环队列，如何判断队空和队满呢？

队列为空的判断条件仍然是 head == tail。但队列满的判断条件就稍微有点复杂了。

就像我图中画的队满的情况，tail=3，head=4，n=8，所以总结一下规律就是：(3+1)%8=4。多画几张队满的图，你就会发现，当队满时，(tail+1)%n=head。

包完整性

1. 以特殊符号来分界，如每个包都以特定的字符来结尾（如\r\n，http的header就是），当在字节流中读取到该字符时，则表明上一个包到此为止。
2. 固定包头+包体结构，包头一般时一个固定字节长度的结构，并且包头中会有一个特定的字段指定包体的大小。收包时，先接收固定字节数的头部，解出这个包的完整长度，按此长度接收包体。header+body 目前应用最多的一种包格式。
3. 在序列化后的buffer前面增加一个字符流的头部，其中有一个字段存储包总长度，根据特殊字符（比如\n或者\0）判断头部的完整性。这样通常比2麻烦些，http和redis（$6\r\nfoobar\r\n）采用的这种形式，收包的时候，先判断已经收到的数据中是否包含结束符，收到结束符后解析包头，解出这个包完整长度，按此长度接收包体。

协议设计

序列号：tcp只能保证数据到达，不能保证数据是否处理。

type表示协议类型，如xml，json。

版本号尽量放在前面，读取版本号的时候可以少读一些字节，如下nginx。protobuf封装后是放在body里面的。header也是定长的，就不用序列化。body做序列化即可。

http请求头为文本，但是body如果传的是jpeg就是二进制。

xml、json序列化后都是文本，protobuf序列化后就是二进制，这里指的是将对象序列化，对象里面一些变长的字段不进行序列化不方便传输。

采用proto buffer作为idl语言。
采用http2进行通信，body采用protobuf序列化后的二进制传输，将字段名去掉，以数字代替。

四种模式：一个端口可以对应多个service

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

syntax = "proto3";
package helloworld; // 命名空间
option go_package = "grpc/helloworld/proto";
import "google/protobuf/timestamp.proto";
import "google/protobuf/any.proto"; // go 里面的interface类型

service Greeter {
// simple rpc
rpc GetFeature(Point) returns (Feature) {}

// server-to-client streaming rpc，下载文件
rpc ListFeatures(Rectangle) returns (stream Feature) {}

// client-to-server streaming rpc，上传文件
rpc RecoredRoute(stream Point) returns (RouteSummary) {}

// Bidirectional streaming rpc，开多线程读写实现，问答场景
rpc RouteChat(stream RouteNote) returns (stream RouteNote) {}
}

// 结构体以message开头
message Feature {
    // 1-15 占一个字节
    string name = 1;
    Point location = 2;
    google.protobuf.Timestamp birthday = 9;
    Address address = 10; // 自定义类型
    repeated string hobys = 11; // 多个兴趣
    map<string, google.protobuf.Any> data = 12;
    reserved 3, 4 to 8; // 保留字段
    reserved "phone", "email";
}

enum Gender {
    FEMALE = 0; // 必须0开始
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

// ListFeatures
std::unique_ptr<ClientReader<Feature>> reader(stub_->ListFeatures(&context, rect)); // 通过stub_
while (reader->Read(&feature)) { // 重复接收
    std::cout << "Found feature called " << feature.name() << " at " << feature.location().latitude() / kCoordFactor_ << ", " << feature.location().longitude() / kCoordFactor_ << << std::endl;
}
Status status = reader->Finish();
if (status.ok()) {
    std::cout << "ListFeatures rpc success." << std::endl;
} else {
    std::cout << "ListFeatures rpc failed." << std::endl;
}

// 主线程读
RouteNote server_note;
while (stream->Read(&server_note)) {
    std::cout << "Got message " << server_note.message() << " at " << server_note.location().latitude() << ", " << server_note.location().longitude() << std::endl;
}
writer.join(); // 等待写线程完成

grpc用于微服务所面临的问题：

1. 用户鉴权问题，鉴权方案的具体实现还包括了多种场景下的解决方案，例如：基于 JWT 或 OAuth 认证、基于多种细粒度授权方案进行授权、支持 OIDC 等。开发者需要根据具体的业务需求和安全要求，选择合适的鉴权方案。

docker

1
2
3

docker run -itd --name redis -p 6379:6379 --restart unless-stopped redis
docker exec -ti redis bash
redis-cli

redis

内存数据库、kv数据库、数据结构数据库
对象类型有哪些？底层使用了哪些数据结构

• string
  • int，字符串长度小于等于20且能转成整数，set teacher 1000000，type teacher，object encoding teacher
  • raw，字符串长度大于44
  • embstr，字符串长度小于等于44，cpu缓存中基本单位为cacheline 64字节，sdshdr头为9字节，加上’\0’，buf的最大长度为44，set teacher 1000000a，object encoding teacher
• list
  • quicklist，双向循环链表
  • ziplist，压缩链表
• hash，hmset role:1001 age 30 name mark sex 1, hgetall role:1001, hget role:1001 age，散列表：指针数组+数组长度+hash函数
  • dict/hashtable,节点数量大于512，或字符串长度大于64
  • ziplist，压缩列表，节点数量小于等于512（hash-max-ziplist-entries），且字符串长度小于等于64(hash-max-ziplist-value)
• set，sadd set 1 2 3 4 5,object encoding set,sadd set mark,object encoding set
  • intset，整数数组，元素都为整数，且节点数量小于等于512(set-max-intset-entries)
  • dict/hashtable，字典，元素有一个不为整数或者数量大于512
• zset，有序的结构
  • skiplist，跳表，数量大于128或者有一个字符串长度大于64
  • ziplist，压缩列表，节点数量小于等于128（zset-max-ziplist-entries）且字符串长度小于等于64(zset-max-ziplist-value)