Lizq的个人博客

发表于 更新于 本文字数： 1.1k 阅读时长 ≈ 4 分钟

1 迭代器模式

  • 在软件构建过程中，集合对象内部结构常常变化各异。但对于这些集合对象，我们希望在不暴露其内部结构的同时，可以让外部客户代码透明地访问其中包含的元素;同时这种“诱明遍历”也为“同一种算法在多种集合对象上进行操作”提供了可能。
  • 提供一种方法顺序访问一个聚合对象中的各个元素，而又不暴露（稳定）该对象的内部表示
  • 访问一个聚合对象的内容而无需暴露其内部实现；支持对聚合对象的多种遍历；为遍历不同的聚合结构提供统一的接口；健壮性考虑：遍历的同时更改迭代器所在聚合结构，会导致问题
  • 该篇介绍的是基于面向对象的迭代器实现，但是C++泛型编程迭代器已经淘汰掉面向对象的迭代器，然而思想一样，技术更新而已

2 迭代器v1

迭代器模式

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
/*
C++现在都是基于模板的迭代器，模板又称为编译时多态，速度肯定比虚函数的运行时多态要好很多
但是java、C#、PHP、Swift还是这种基于虚函数的迭代器（因为不支持编译时的模板机制）
*/
template<typename T>
class Iterator{
public:
    virtual void first() = 0;
    virtual void next() = 0;
    virtual bool isDone() const = 0;
    virtual T& current() = 0;
};

template<typename T>
class MyCollection{
public:
    Iterator<T>* GetIterator(){
        // ...
    }
};

template<typename T>
class CollectionIterator : public Iterator<T>{
    MyCollection<T> mc;
public:
    CollectionIterator(const MyCollection<T>& c): mc(c){ }
    
    void first() override {
        // ...
    }
    void next() override {
        // ...
    }
    bool isDone() const override{
        // ...
    }
    T& current() override{
        // ...
    }
};

void MyAlgorithm(){
    MyCollection<int> mc;
    Iterator<int>* iter = mc.GetIterator();
    for (iter->first(); !iter->isDone(); iter->next()){ // 多态
        cout << iter->current() << endl; // 多态
    }
}
阅读全文 »

发表于 更新于 本文字数： 699 阅读时长 ≈ 3 分钟

1 抽象工厂模式

  • 在软件系统中，经常面临着“一系列相互依赖的对象”的创建工作；同时，由于需求的变化，往往存在更多系列对象的创建工作。
  • 如何应对这种变化？如何绕过常规的对象创建方法(new)，提供一种“封装机制”来避免客户程序和这种“多系列具体对象创建工作”的紧耦合？
  • 提供一个接口，让该接口负责创建一系列“相关或者相互依赖的对象”，无需指定它们具体的类。

2 问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class EmployeeDAO{
public:
    vector<EmployeeDO> GetEmployees(){
        SqlConnection* connection = new SqlConnection(); // 耦合
        connection->ConnectionString("...");

        SqlCommand* command = new SqlCommand(); // 耦合
        command->CommandText("...");
        command->SetConnection(connection);

        SqlDataReader* reader = command->ExecuteReader();
        while (reader->Read()){
            // ...
        }
    }
};

3 尝试简单工厂模式

阅读全文 »

发表于 更新于 本文字数： 664 阅读时长 ≈ 2 分钟

1 工厂模式

  • 父类决定实例的生成方式，但并不决定所要生成具体的类，具体处理全部交给子类处理。 将生成实例的框架与具体的实例类解耦。
  • 在软件系统中，经常面临创建对象的工作，由于需求的变化，需要创建的对象的具体类型经常变化
  • 如何应对这种变化？如何绕过常规的对象创建方法(new)，提供一种“封装机制”来避免客户程序和这种“具体对象创建工作”的紧耦合？

2 问题

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
// FileSplitter.cpp
class ISplitter{
public:
    virtual void split()=0;
    virtual ~ISplitter(){}
};

// 多个具体的文件分割器
class BinarySplitter : public ISplitter{
    virtual void split(){
        // ...
    }
};

class TxtSplitter: public ISplitter{
    virtual void split(){
        // ...
    }
};

class PictureSplitter: public ISplitter{
    virtual void split(){
        // ...
    }
};

class VideoSplitter: public ISplitter{
    virtual void split(){
        // ...
    }
};
1
2
3
4
5
6
7
8
9
// MainForm.cpp
class MainForm : public Form{
public:
	void Button1_Click(){
		// 抽象依赖* ptr = new 具体依赖(); 违背依赖倒置原则，这样肯定不行的！
		ISplitter * splitter = new BinarySplitter(); //依赖具体类
        splitter->split();
	}
};
阅读全文 »

发表于 更新于 本文字数： 907 阅读时长 ≈ 3 分钟

1 策略模式

  • 定义一系列算法，把它们一个个封装起来，并且使它们可互相替换（变化）。该模式使得算法可独立于使用它的客户程序（稳定）而变化（扩展，子类化）。
  • 将算法与其它部分分离开，只定义与算法相关的接口，然后在程序中以委托的方式来使用。使用委托这种弱关联关系可以很方便地整体替换算法。程序运行过程中也可以替换算法
  • 策略模式是一种行为设计模式， 它能让你定义一系列算法， 并将每种算法分别放入独立的类中， 以使算法的对象能够相互替换。

2 问题

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
enum TaxBase {
	CN_Tax,
	US_Tax,
	DE_Tax,
	FR_Tax //更改：新添加
};

class SalesOrder{
    TaxBase tax;
public:
    double CalculateTax(){
        //...
        
        if (tax == CN_Tax){
            //CN***********
        }
        else if (tax == US_Tax){
            //US***********
        }
        else if (tax == DE_Tax){
            //DE***********
        }
		else if (tax == FR_Tax){  //更改
			//...
		}
        //....
     }
};

3 策略v1

阅读全文 »

发表于 更新于 本文字数： 403 阅读时长 ≈ 1 分钟

并查集

  • 一般用于快速判断两个元素是否同属于一个集合
  • 数组形式表示树结构
  • 插入元素会被映射到从0开始的顺序整数中

实现技巧

  • 路径压缩：在find时，通过递归并返回找到的祖宗节点并赋值，可以达成find后降低树高的功效
  • 按秩归并：在unite时，其中一方会挂在另一方的门下，所以希望“小的挂到大的上面”，以此来产生结果高度更小的树，有两种方式：
    • 高度：树高：S[Root]=-树高，代码多一步判断：即：两个树相同高度时，增加树高
    • 数目（推荐）：S[Root]=-元素个数。子孙节点数目，可以通过利用根节点来达成，根节点之前是-1，现在改为-n，其中n是包含根节点的整个树的节点数目

LC.990

阅读全文 »

发表于 更新于 本文字数： 1.4k 阅读时长 ≈ 5 分钟

1. 缓存雪崩：

布隆过滤器(1970)、分布式锁

比如说双十一某宝，redis缓存中key大面积失效，导致某宝直接和数据库进行沟通，把请求直接打到数据库
解决方法：

  1. 随机初始化缓存失效时间，让其不要在同一时间失效
  2. redis一般都是集群部署，我们把热点key放到不同的节点上去，让热点的缓存平均的分布在不同的redis节点上
  3. 最暴力的方法：不设置缓存的失效时间，让它永远不失效，或者跑定时任务，让它定时刷这个缓存让其不失效

2. 缓存穿透：

阅读全文 »

发表于 更新于 本文字数： 1.2k 阅读时长 ≈ 5 分钟

1 观察者模式

  • 在软件构建过程中，我们需要为某些对象建立一种“通知依赖关系” ——一个对象（目标对象）的状态发生改变，所有的依赖对象（观察者对象）都将得到通知。如果这样的依赖关系过于紧密，将使软件不能很好地抵御变化。
  • 定义对象间的一种一对多（变化）的依赖关系，以便当一个对象(Subject)的状态发生改变时，所有依赖于它的对象都得到通知并自动更新。
  • 观察对象的状态发生变化时，通知给观察者。 观察者模式适用于根据对象状态进行相应处理的场景。

2 问题

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
// FileSplitter.cpp
class FileSplitter{
	string m_filePath;
	int m_fileNumber;
	ProgressBar* m_progressBar; // 不能应对变化，和具体某个平台的进度条绑死：例如UI进度条、无界面的Shell进度条等等

public:
	FileSplitter(const string& filePath, int fileNumber, ProgressBar* progressBar) :
		m_filePath(filePath), 
		m_fileNumber(fileNumber),
		m_progressBar(progressBar){
	}

	void split(){
		//1.读取大文件
		// ...

		//2.分批次向小文件中写入
		for (int i = 0; i < m_fileNumber; i++){
			//...
			float progressValue = m_fileNumber;
			progressValue = (i + 1) / progressValue;
			m_progressBar->setValue(progressValue);
		}
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// MainForm.cpp
class MainForm : public Form{
	TextBox* txtFilePath;
	TextBox* txtFileNumber;
	ProgressBar* progressBar;

public:
	void Button1_Click(){
		string filePath = txtFilePath->getText();
		int number = atoi(txtFileNumber->getText().c_str());
		FileSplitter splitter(filePath, number, progressBar);
		splitter.split();
	}
};
阅读全文 »

发表于 更新于 本文字数： 602 阅读时长 ≈ 2 分钟

函数介绍

  • lock_guard：锁定互斥锁后，生命周期结束后会自动释放，不需要手动解锁，也无法手动解锁
  • unique_lock：多数情况与上面一个可以相互替代，但是其更具功能性（付出一些代价）。unique_lock可以进行unlock操作，因此可以和条件变量搭配使用

多线程输出数字

多个线程互斥输出: 0 1 2 3 4 5 6 ...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <vector>
#include <thread>
#include <mutex>
using namespace std;
int idx = 0;
mutex _mutex;
void func(int n) {
	while (idx < n) { // 改成true一样的
		lock_guard<mutex> tmp(_mutex);
		if (idx >= n) break; // 必须，否则多输出几个数才停
		cout << idx++ << " ";
	}
}
int main() {
	vector<thread> arr;
	for (int i = 0; i < 10; ++i)
		arr.push_back(thread(func, 1000));
	for (auto& e : arr)
		e.join();
	return 0;
}
阅读全文 »

发表于 更新于 本文字数： 2k 阅读时长 ≈ 7 分钟

问题

  1. 临时对象非必要的昂贵的拷贝操作
  2. 在模板函数中如何按照参数的实际类型进行转发
  • 关键字：右值、纯右值、将亡值、universal references、引用折叠、移动语义、move语义、完美转发
  • 以下用四条代码来阐述C++的右值引用及其思想

1. 第一行代码

1
int i = getVal();
阅读全文 »

发表于 更新于 本文字数： 1.1k 阅读时长 ≈ 4 分钟

辅助代码（全局变量）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef pair<int, int> node;
vector<vector<int>> G = {
    {1,1,1,1,1,1,1,1,1,1,1},
    {1,1,1,1,1,1,1,1,1,1,1},
    {1,1,1,1,1,2,1,1,1,1,1},
    {1,1,1,1,2,3,2,1,1,1,1},
    {1,1,1,2,3,4,3,2,1,1,1},
    {1,1,2,3,4,5,4,3,2,1,1},
    {1,1,1,2,3,4,3,2,1,1,1},
    {1,1,1,1,2,3,2,1,1,1,1},
    {1,1,1,1,1,2,1,1,1,1,1},
    {1,1,1,1,1,1,1,1,1,1,1},
    {1,1,1,1,1,1,1,1,1,1,1}
};
int row = (int)G.size();
int col = (int)G[0].size();
node S = { 5,0 };
node E = { 5,10 };
int dir[] = { -1, 0, 1, 0, -1 };

DFS

  • DFS是无法找到最优路径的（理论上可以，但是复杂度巨高，如果是四个方向搜索的话，那么就是四叉树，高度是图中结点数，也就是说如果是10x10的图，那就是大约4^100复杂度）
  • 下面代码只表示找到任意一条路后直接返回
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<vector<bool>> visited(row, vector<bool>(col, false));
vector<node> path;
bool END = false;
void dfs(node cur) {
    if (cur == E) 
        END = true;
    visited[cur.first][cur.second] = true;
    path.push_back(cur);
    for (int i = 0; i < 4 && !END; ++i) {
        int ix = cur.first + dir[i];
        int iy = cur.second + dir[i + 1];
        if (ix < 0 || ix >= row || iy < 0 || iy >= col || visited[ix][iy]) continue;
        dfs({ ix, iy });
    }
    if (END) return; // 保留路径
    path.pop_back();
    visited[cur.first][cur.second] = false;
}
阅读全文 »
0%