李建聪的博客
0%

Posted on Edited on In

本文深入探讨了C++并发编程中的关键技巧，包括使用std::lock和std::lock_guard避免死锁、通过固定顺序获取锁防止死锁、利用std::unique_lock实现灵活的锁管理，以及使用std::call_once实现线程安全的延迟初始化。文章还介绍了如何通过std::condition_variable实现线程间的数据等待与通知机制，展示了线程安全队列的实现。这些技巧为C++开发者提供了高效处理并发问题的实用工具，帮助编写更安全、更高效的多线程程序。

Read more »

Posted on Edited on In

本文介绍了最近最少使用缓存（LRU）的简单实现。LRU缓存通过键值对存储数据，并在达到容量上限时删除最近最少使用的项目。文章详细展示了如何使用C++实现LRU缓存，包括get和put操作的核心逻辑。通过std::list和std::unordered_map的结合，实现了高效的数据访问和更新。本文为开发者提供了LRU缓存的实用实现方法，适合需要高效缓存管理的场景。

Read more »

Posted on Edited on In

本文介绍了跳表（Skiplist）的简单实现，跳表是一种高效的数据结构，支持快速查找、插入和删除操作。文章详细展示了跳表的C++实现代码，包括节点结构定义、搜索、添加和删除操作的逻辑。通过随机层级生成和多层链表结构，跳表在保持简单性的同时，提供了接近平衡树的性能。本文为C++开发者提供了跳表的实用实现方法，适合需要高效数据管理的场景。

Read more »

Posted on Edited on In

C++ 回调函数示例

简单示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <functional>
#include <iostream>

void print() { std::cout << "print()" << std::endl; }

void callback(std::function<void()> func) {
  std::cout << "Enter: callback()" << std::endl;
  func();
  std::cout << "Leave: callback()" << std::endl;
}

int main() {
  callback(print);
  system("pause");
}

输出：

Enter: callback()

print()

Leave: callback()

接下来我们把这两个函数放入类中实现，在调用的时候绑定函数名和其对应实例就可以按以上例子方法调用。

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
#include <functional>
#include <iostream>

class operation {
public:
void print() { std::cout << "print()" << std::endl; }
};

class controller {
public:
void callback(std::function<void()> func) {
  std::cout << "Enter: callback()" << std::endl;
  func();
  std::cout << "Leave: callback()" << std::endl;
}
};

int main() {
  controller control;
  operation op;
  /// 绑定实例和对应的操作函数
  auto f = std::bind(&operation::print, &op);
  control.callback(f);
  system("pause");
}

现在我们把绑定函数对象的过程封装起来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <functional>
#include <iostream>

class operation {
 public:
  auto get_print_function() { return std::bind(&operation::print, this); }
  void print() { std::cout << "print()" << std::endl; }
};

class controller {
 public:
  void callback(std::function<void()> func) {
    std::cout << "Enter: callback()" << std::endl;
    func();
    std::cout << "Leave: callback()" << std::endl;
  }
};

int main() {
  controller control;
  operation op;
  control.callback(op.get_print_function());
  system("pause");
}

Posted on Edited on In

数据结构

字符串

字符串是不可变字节(byte)序列，其本身是一个符合结构.

1
2
3
4
type stringStruct struct {
  str unsafe.Pointer
  len int
}

头部指针指向字节数组，但没有NULL结尾。默认以UTF-8编码存储Unicode字符，字面量里允许使用十六进制、八进制和UTF编码格式。

内置函数len返回字节数组长度，cap不接受字符串类型参数。

字符串默认值不是nil, 而是"".

使用for遍历字符串是，分byte和rune两种方式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func main () {	// byte
	s:="李建聪"
	for i := 0; i < len(s); i++ {
		fmt.Printf("%d: [%c]\n", i, s[i])
	}


	for i, c := range s {	// rune: 返回数组索引号，以及Unicode字符
		fmt.Printf("%d: [%c]\n", i, c)
	}
}
///0: [æ]
///1: [
///2: []
///3: [å]
///4: [»]
///5: [º]
///6: [è]
///7: []
///8: [ª]
///0: [李]
///3: [建]
///6: [聪]

要修改字符串，须将其转换为可变类型([]rune或[]byte), 待完成后再转换回来。但不管怎么转换，都须重新分配内存，并复制数据。

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
func pp(format string, ptr interface{}) {
	p := reflect.ValueOf(ptr).Pointer()
	h := (*uintptr)(unsafe.Pointer(p))
	fmt.Printf(format, *h)
}

func main () {	// byte
	s:="hello, world!"
	pp("s: %x\n", &s)

	bs := []byte(s)
	s2 := string(bs)

	pp("string to []byte, bs:%x\n", &bs)
	pp("[]byte to string, s2:%x\n", &s2)

	rs := []rune(s)
	s3 := string(rs)

	pp("string to []byte, rs:%x\n", &rs)
	pp("[]byte to string, s3:%x\n", &s3)
}
/// 输出：
/// s: 2bcc91
/// string to []byte, bs:c0000a20a0
/// []byte to string, s2:c0000a20b0
/// string to []byte, rs:c0000b80c0
/// []byte to string, s3:c0000a20d0

编译器会为了某些场合进行专门优化，避免额外分配和复制操作：

  • 将[]byte转换为string key, 去map[string]查询的时候。
  • 将string转换为[]byte, 进行for range迭代时，直接取字节赋值给局部变量。

除了类型转换外，动态构建字符串也容易造成性能问题。
用加法操作符拼接字符串时，每次都须重新分配内存。如此，在构建超大字符串时，性能就显得极差。
改进思路时预分配i足够大的空间。常用方法是用string.Join函数，他会统计所有参数长度，并一次性完成内存分配操作。
另外
utf8.ValidString(s) 返回s是不是一个有效的字符串
utf8.RuneCountInString(s) 替代len返回unicode的字符数量

Posted on Edited on In

方法

方法是与对象实例绑定的特殊函数。
方法是面向对象编程的基本概念，用于维护和展示对象的自身状态。对象是内敛的，每个实例都有各自不同的独立特征，以属性和方法来暴露对外通信接口。普通函数则专注于算法流程，通过接收参数来完成特定逻辑运算，并返回最终结果。换句话说，方法是有关联的而函数通常没有。
方法和函数定义语法区别，在于前者有前置实例接收参数，编译器以此确定方法所数类型。
可以为当前包，以及除接口和指针以外的任何类型定义方法。

1
2
3
4
5
6
7
8
9
10
11
type N int
func (n N) toString() string {
  return fmt.Sprintf("%#x", n)
}

func main() {
  var a N = 25
  println(a.toString())
}
/// 输出：
/// 0x19

方法同样不支持重载(overload)。receiver参数名没有限制，按惯例会选用简短有意义的名称。如方法内部并不引用实例，可省略参数名，仅保留类型。

1
2
3
4
5
type N int

func (N) test() {
  println("hi~")
}

方法可看作特殊的函数，那么receiver的类型自然可以是基础类型或指针类型。这会关系到调用时对象实例是否被赋值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
type N int
func (n N) value() {
  n++
  fmt.Printf("v: %p, %v\n", &n, n)
}

func (n *N) pointer() {
  (*n)++
  fmt.Printf("p: %p, %v\n", n, *n)
}

func main() {
  var a N = 25
  a.value()
  a.pointer()

  fmt.Printf("a: %p, %v\n", &a, a)
}

/// 输出：
/// v: 0xc8200741c8, 26 /// receiver 被复制
/// p: 0xc8200741c0, 26
/// a: 0xc8200741c0, 26

可使用实例值或指针调用方法，编译器会根据方法receiver类型自动在基础类型和指针类型间转换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func main() {
  var a N = 25
  p := &a
  a.value()
  a.pointer()
  p.value()
  p.pointer()

  /// p2 := &p   错误
}
/// 输出：
/// v: 0xc82999a2c0, 26
/// p: 0xc82999a298, 26
/// v: 0xc82000a2f0, 27
/// v: 0xc82000a298, 27

指针类型的receiver必须时合法指针(包括nil), 或能获取实例地址。

1
2
3
4
5
6
7
8
9
10
11
type X struct {}

func (x *X) test() {
  println("hi!", x)
}

func main() {
  var a *X
  a.test()  ///相当于test(nil)
  X{}.test()  /// 错误无法获取地址
}

如何选择方法的receiver类型：

  • 要修改实例状态，用*T
  • 无需修改状态的小对象或固定值，建议用T
  • 大对象建议用*T, 以减少复制成本。
  • 引用类型、字符串、函数等指针包装对象，直接用T。
  • 若包含Mutex等同步字段，用*T,避免因复制造成锁操作无效
  • 其他无法确定的情况，都用*T

匿名字段

可以访问匿名字段成员那样调用其方法，有编译器负责查找。

1
2
3
4
5
6
7
8
9
10
type data struct {
  sync.Mutex
  buf [1024]byte
}

func main() {
  d := data()
  d.Lock()  /// 编译器会处理为 sync.(*Mutex).Lock()调用
  defer d.Unlock()
}

方法也会有同名遮蔽问题。但利用这一特性可实现类似(override)操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
type user struct {}
type manager struct {
  user
}

fun (user) toString() string {
  return "user"
}

func (m manager) toString() string {
  return m.user.toString() + "; manager"
}

func main() {
  var m manager
  println(m.toString())
  println(m.user.toString())
}
/// 输出：
/// user; manager
/// user

尽可能直接访问匿名字段的成员和方法，但他们依然不属于继承关系。

方法集

类型有一个与之相关的方法集，这决定了它是否实现某个接口。

  • 类型T方法集包含所有receiver T方法。
  • 类型*T方法集包含所有recever T + *T方法。
  • 匿名嵌入S, T方法集包含所有receiver S方法。
  • 匿名嵌入*S, T方法集包含所有receiver S+*S方法。
  • 匿名嵌入S或*S, *T方法集包含所有receiver S+*S方法。

可利用反射测试这些规则。

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
type S struct{}
type T struct{
  S // 匿名嵌入字段
}
func (S) sVal() {}
func (*S) sPtr() {}
func (T) tVal() {}
func (*T) tPtr() {}

func methodSet(a interface{}) {
  t := reflect.TypeOf(a)
  for i, n := 0, t.NumMethod(); i < n; i++ {
    m := t.Method(i)
    fmt.Println(m.Name, m.Type)
  }
}

func main() {
  var t T
  methodSet(t)  ///< 显示T方法集
  println("-------")
  methodSet(&t) ///< 显示*T方法集
}
/// 输出：
/// sVal func(main.T)
/// tVal func(main.T)
/// ---------
/// sPtr func(*main.T)
/// sVal func(*main.T)
/// tPtr func(*main.T)
/// tVal func(*main.T)

方法集影响接口实现和方法表达式转换，于通过实例或实例指针调用方法无关。实例并不使用方法集，而是直接调用(或通过隐式字段名).
很显然，匿名字段就是为方法准备的。否则，完全没必要为少写个字段名而大费周折。
面向对象的三大特征"封装",“继承"和"多态”, Go仅仅实现了部分特征，它更倾向于”组合优于继承“这种思想。将模块分解成相互独立的更小单元，分别处理不同方面的需求，最后以匿名嵌入方式组合到一起，共同实现对外接口。而且其简短一致的调用方式，更是隐藏了内部实现细节。

组合没有父子依赖，不会破坏封装。且整体和局部松耦合，可任意增加来实现实现扩展。各单元持有单一职责，互无关联，实现和维护更加简单。

表达式

方法和函数一样，除直接调用外还可以赋值给变量，或作为参数传递。依照具体引用方式不同，可分为expression和value两种状态。
通过类型引用Method expression会被还原为普通函数央视，receiver是第一参数，调用时须显示传参。至于类型，可以是T或*T, 只要目标方法集中即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
type N int
func (n N) test() {
  fmt.Printf("test.n: %p, %d", &n, n)
}
func main() {
  var n N = 25
  fmt.Printf("main.n: %p, %d\n", &n, n)
  f1 := N.test  ///< func(n N)
  f1(n)
  f2 := (*N).test ///< func(n *N)
  f2(&n)  ///< 按方法集中的签名传递正确类型的参数
}
/// 输出：
/// main.n: 0xc82000a140, 25
/// test.n: 0xc82000a158, 25
/// test.n: 0xc82000a168, 25

当然，也可直接以表达式方式调用。

1
2
3
4
5
func main(){
  var n N = 25
  N.test(n)
  (*N).test(&n) ///< 注意： *N 须使用括号，以免语法解析错误。
}

基于实例或指针引用的method value, 参数签名不会改变，依旧按正常方式调用。
但当method value被赋值给变量或作为参数传递时，会立即计算并复制该方法执行所需的receiver对象，与其绑定，以便在稍后执行时，能隐式传入receiver参数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
type N int
func (n N) test() {
  fmt.Printf("test.n: %p, %v\n", &n, n)
}
func main() {
  var n N = 100
  p := &n
  n++
  f1 := n.test  //< 因为test方法的reveiver是类型,所以复制n, 等于101

  n++
  f2 := p.test  ///< 复制*p, 等于102
  n++
  fmt.Printf("main.n: %p, %v\n", p, n)
  f1()
  f2()
}
/// 输出：
/// main.n: 0xc829976028, 103
/// test.n: 0xc820076060, 101
/// test.n: 0xc820076060, 102

编译器会为method value生成一个包装函数，实现间接调用。至于receiver复制，和闭包的实现方法基本相同，打包成funcval, 经由DX寄存器传递。

当method value作为参数是，会复制含receiver在内的整个method value。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func call(m func()) {
  m()
}
func main(){
  var n N = 100
  p := &n
  fmt.Printf("main.h: %p, %v", p, n)
  n++
  call(n.test)
  n++
  call(p.test)
}
/// 输出：
/// main.n 0x82000a288, 100
/// test.n 0x82000a2c0, 101
/// main.n 0x82000a2d0, 102

当然，如果目标方法的receiver是指针类型，那么被复制的仅是指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
type N int
func (n *N) test() {
  fmt.Printf("test.n: %p, %v\n", n, *n)
}
func main() {
  var n N = 100
  p := &n
  n++
  f1 := n.test  ///< 因为test方法的receiver是*N类型, 所以复制&n
  n++
  f2 := p.test  ///< 复制p指针
  n++
  fmt.Printf("main.n: %p, %v\n", p, n)
  f1()  ///< 延迟调用，n == 103
  f2()
}
/// 输出：
/// main.n: 0xc82000a298, 103
/// test.n: 0xc82000a298, 103
/// test.n: 0xc82000a298, 103

只要receiver参数类型正确，使用nil同样可以执行。

1
2
3
4
5
6
7
8
9
10
11
type N int
func (N) value() {}
func (*N) pointer() {}

func main(){
  var p *N
  p.pointer() // method value
  (*N)(nil).pointer() // method value
  (*N).pointer(nil) // method expression
  /// p.value() 错误： invalid memory address or nil pointer dereference
}

Posted on Edited on In

前序遍历：

遍历的顺序是：根节点-左节点-右节点

递归代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
      std::vector<int> res;
      std::function<void(TreeNode*)> order = [&](TreeNode* node){
        if(node == nullptr) return;
        res.push_back(node->val);
        order(node->left);
        order(node->right);
      };
      order(root);
      return res;
    }
};

迭代代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
      std::vector<int> res;
      std::stack<TreeNode*> s;
      s.push(root);
      while(!s.empty()) {
        root = s.top();
        s.pop();
        if(root == nullptr) continue;
        res.push_back(root->val);
        s.push(root->right);
        s.push(root->left);
      }
      return res;
    }
};

中序遍历：

遍历的顺序是：左节点-根节点-右节点

递归代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
      std::vector<int> res;
        std::function<void(TreeNode*)> order = [&](TreeNode* node){
          if(node == nullptr) return;
          order(node->left);
          res.push_back(node->val);
          order(node->right);
        };
        order(root);
        return res;
    }
};

迭代代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
      std::vector<int> res;
      std::stack<TreeNode*> s;
      while(root != nullptr || !s.empty()){
        while(root != nullptr){
          s.push(root);
          root = root->left;
        }
        root = s.top();
        s.pop();
        res.push_back(root->val);
        root = root->right;
      }
      return res;
    }
};

后序遍历：

遍历的顺序是：左节点-右节点-根节点

递归代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        std::vector<int> res;
        std::function<void(TreeNode*)> order = [&](TreeNode* node){
          if(node == nullptr) return;
          order(node->left);
          order(node->right);
          res.push_back(node->val);
        };
        order(root);
        return res;
    }
};

迭代代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
      std::vector<int> res;
      if(root == nullptr) return res;
      std::stack<TreeNode*> s;
      s.push(root);
      while(!s.empty()) {
        root = s.top();
        if(root == nullptr){
          s.pop();
          res.push_back(s.top()->val);
          s.pop();
        } else {
          s.push(nullptr);
          if(root->right) s.push(root->right);
          if(root->left) s.push(root->left);
        }
      }
      return res;
    }
};

Posted on Edited on In

排序操作次数

题目描述:
有一种排序算法定义如下，该排序算法每次把一个元素提到序列的开头，例如2, 1, 3, 4，只需要一次操作把1提到序列起始位置就可以使得原序列从小到大有序。现在给你个乱序的1-n的排列，请你计算最少需要多少次操作才可以使得原序列从小到大有序。
输入描述

输入第一行包含两个正整数n，表示序列的长度。（1 <= n <= 100000）
接下来一行有n个正整数，表示序列中的n个元素，中间用空格隔开。（1 <= a_i <= n）

输出描述

输出仅包含一个整数，表示最少的操作次数。

样例输入
4
2 1 3 4

样例输出
1

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
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>

int get_operation_count(const std::vector<int>& vec) {
  std::vector<int> sorted(vec);
  std::sort(sorted.begin(), sorted.end());
  int p = sorted.size() - 1;
  int q = p;
  while (p >= 0 && q >= 0) {
    if (vec.at(p) == sorted.at(q)) {
      --p;
      --q;
    } else {
      while (p >= 0 && vec.at(p) != sorted.at(q)) {
        --p;
      }
    }
    return q + 1;
  }
}

int main() {
  int n = 0;
  std::cin >> n;
  std::vector<int> vec(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> vec.at(i);
  }
  std::cout << get_operation_count(vec) << std::endl;
  system("pause");
}

Posted on Edited on In

接口

接口代表一种调用契约，是多个方法声明的集合。接口最常见的使用场景，是对包外提供访问，或预留扩展空间。
Go接口的实现机制很简洁，只要目标类型方法集内包含接口声明的全部方法，就被视为实现了该接口，无须做显式声明。当然，目标类型可实现多个接口。
接口：

  • 不能有字段
  • 不能定义自己的方法
  • 只能声明方法，不能实现
  • 可嵌入其他接口类型

接口通常以er作为名称后缀，方法名是声明组成部分，但参数名可不同或省略。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
type tester interface {
  test()
  string() string
}

type data struct {}

func (*data) test() {}
func (data) string() string() {return "";}

func main() {
  var d data

  /// var t tester = d  ///< 错误

  var t tester = &d
  t.test()
  println(t.string())
}

如果接口没有任何声明方法声明，那么就是一个空接口, 他的用途类似面向对象的根类型Object, 可被赋值为任何类型的对象。
接口变量默认值是nil。如果实现接口的类型支持，可做相等运算。

1
2
3
4
5
6
7
8
9
10
11
12
13
func main() {
  var t1, t2 interface{}
  println(t1 == nil, t1 == t2)

  t1, t2 = 100, 100
  println(t1 == t2)
  t1, t2 = map[string]int{}, map[string]int{}
  println(t1 == t2)
}
/// 输出：
/// true true
/// true
/// panic: runtime error: comparing uncomparable type map[string]int

可以像匿名字段一样，嵌入其他接口。目标类型方法集中必须拥有包含嵌入接口方法在内的全部方法才算实现了该接口。
前提是，不能有同名方法, 不能嵌入自身或循环嵌入，那会导致递归错误。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
type stringer interface {
  string() string
}

type tester interface {
  stringer  ///< 嵌入接口
  test()
}

func (*data) test() {}
func (data) string() string{
  return ""
}

func main() {
  var d data
  var t tester = &d
  t.test()
  println(t.string())
}

超集接口变量可隐式转换为子集，反过来不行。

1
2
3
4
5
6
7
8
9
10
11
func pp(a stringer) {
  println(a.string())
}

func main() {
  var d data
  var t tester = &d
  pp(t) ///< 隐式转换为自己接口
  var s stringer = t  ///< 超集转换为子集
  println(s.string())
}

支持匿名接口类型，可直接用于变量定义，或作为结构字段类型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
type data struct{}
func (data) string() string {
  return ""
}
type node struct {
  data interface {  ///< 匿名接口类型
    string() string
  }
}

func main() {
  var t interface { ///< 定义匿名接口变量
    string() string
  } = data{}

  n := node{
    data: t,
  }
  println(n.data.string())
}

执行机制

接口执行一个名为itab的结构存储运行期所需的相关类型信息。

1
2
3
4
5
6
7
8
9
type iface struct {
  tab *itab ///< 类型信息
  data unsafe.Pointer ///< 实际对象指针
}
type itab struct {
  inter *interfacetype  ///< 接口类型
  _type *_type  ///< 实际对象类型
  fun [1]uintptr  ///< 实际对象方法地址
}

相关类型信息里保存了接口和实际对象的元数据。同时itab还用fun数组（不定长结构）保存了实际方法地址，从而实现在运行期对目标方法的动态调用。
除此之外，接口还有一个重要特征：将对象赋值给接口变量时，会复制该对象。我们甚至无法修改结构存储的复制品，因为它也是unaddressable的。

1
2
3
4
5
6
func main() {
  d := data{100}
  vat t interface{} = d
  p := &t.(data)  ///< 错误
  t.(data).x = 200  ///< 错误
}

即便将其复制出来，用本地变量修改后，依然无法对iface.data赋值。解决方法就是将对象指针赋值给接口，那么接口内存存储的就是指针的复制品。
只有当接口变量内部的两个指针(itab, data)都为nil时, 接口才等于nil.

类型转换

类型推断可将接口变量还原为原始类型，或用来判断是否实现了某个更具体地接口类型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
type data int
func (d data) String() string() {
  return fmt.Sprintf("data:%d", d)
}

func main() {
  var d data = 15
  var x interface{} = d

  if n, ok := x.(fmt.Stringer); ok {  ///< 转换为更具体地接口类型
    fmt.Println(n)
  }

  if d2, ok := x.(data); ok { ///< 转换回原始类型
    fmt.Println(d2)
  }

  e := x.(error)  ///< 错误： main.data is not error
  fmt.Println(e)
}

使用ok-idiom模式，即便转换失败也不会引发panic。还可用switch语句在多种类型间做出推断匹配，这样空接口就有更多发挥空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func main() {
  var x interface{} = func(x int) string {
    return fmt.Sprintf("d:%d", x)
  }
  switch v := x(type) {
    case nil:
      println("nil")
    case *int:
      println(*v)
    case func(int) string:
      println(v(100))
    case fmt.Stringer:
      fmt.Println(v)
    default:
      println("unknown")
  }
}
/// 输出：
/// d: 100

提示： type switch不支持fallthrought

技巧

让编译器检查，确保类型实现了指定接口

1
2
3
4
type x int
func init() { ///< 包初始函数
  var _ fmt.Stringer = x(0)
}

定义函数类型，让相同签名地函数自动实现某个接口

1
2
3
4
5
6
7
8
9
10
11
12
type FuncString func() string

func (f FuncString) String() string {
  return f()
}

func main() {
  var t fmt.Stringer = FuncString(func() string {
  return "hello, world!"
})
fmt. Println(t)
}

Posted on Edited on In

并发

  • 并发： 逻辑上具备同时处理多个任务的能力。
  • 并行： 物理上在同一时刻执行多个并发任务。
    多线程或多进程时并行的基本条件，但单线程也可用协程做到并发。尽管协程在单个线程上通过主动切换来实现多任务并发，它也有自己的优势。除了将因阻塞而浪费的时间找回来以外，还免去了线程切换的开销。协程上运行的多个任务本质上是依旧串行的，加上可控自主，所以并不需要做同步处理。
    通常情况下，用多进程来实现分布式和负载平衡，减轻单进程垃圾回收压力；用多线程抢夺更多的处理器资源。用协程来提高处理器时间片利用率。

简单将goroutine归纳为协程并不合适。运行时创建多个线程来执行并发任务，且任务单元可被调度到其他线程并行执行。这更像是多线程和协程的综合体，能最大限度提升执行效率，发挥多核处理能力。
只须在函数调用前添加go关键字即可创建并发任务。

1
2
3
4
5
go println("hello, world!")

go func(s string) {
  println(s)
} ("hello, world!")

关键字go并非执行并发操作，而是创建一个并发任务单元。新建任务被放置在系统队列中，等待调度器安排合适系统线程去获取执行权。当前流程不会阻塞，不会等待该任务启动，且运行时也不保证并发任务的执行次序。

每个任务单元除保存函数指针、调用参数外，还会分配执行所需的栈内存空间。相比系统默认MB级别的线程栈，goroutinue自定义栈初始仅须2 KB，所以才能创建成千上万的并发任务。自定义栈采取按需分配策略，在需要时进行扩容，最大能到GB规模。
与defer一样，gorountine也会因"延迟执行"而立即计算并复制执行参数。

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
package main

import (
	"time"
)

var c int

func counter() int {
	c++
	return c
}

func main() {
	a := 100
	go func(x, y int) {
		time.Sleep(time.Second)
		println("go:", x, y)
	}(a, counter())
	a += 100
	println("main:", a, counter())

	time.Sleep(time.Second * 3)	// 等待 `goroutine` 结束
}
/// 输出：
/// main: 200 2
/// go: 100 1

Wait

进程退出时不会等待并发任务结束，可用管道(channel)阻塞，然后发出退出信号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func main() {
	exit := make(chan struct{})	///< 创建通道。因为仅是通知，数据并没有实际意义

	go func() {
		time.Sleep(time.Second)
		println("goroutine done.")
		close(exit)	///< 关闭通道
	} ()
	println("main...")
	<-exit	///< 如通道关闭，立即解除阻塞
	println("main exit.")
}
/// 输出：
/// main...
/// goroutine done.
/// main exit.

除关闭通道外，写入数据也可解除阻塞。
如要等待多个任务结束，推荐使用sync.WaitGroup。通过设定计数器，让每个goroutine在退出前递减，直至归零时接触阻塞。

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
func main() {
	var wg sync.WaitGroup

	for i := 0; i < 10; i++ {
		wg.Add(1)	///< 累加计数
		go func(id int) {
			defer wg.Done()	///< 递减计数

			time.Sleep(time.Second)
			println("goroutine", id, "done.")
		} (i)
	}

	println("main...")
	wg.Wait()	///< 阻塞，直到计数为零
	println("main exit.")
}
/// 输出：
/// main...
/// goroutine 2 done.
/// goroutine 3 done.
/// goroutine 7 done.
/// goroutine 9 done.
/// goroutine 6 done.
/// goroutine 0 done.
/// goroutine 8 done.
/// goroutine 4 done.
/// goroutine 1 done.
/// goroutine 5 done.
/// main exit.

尽管WaitGroup.Add实现了原子操作，但建议在goroutine外累加计数器，以免Add尚未执行，Wait已经退出。
可在多处使用Wait阻塞，他们都能接收到通知

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func main() {
	var wg sync.WaitGroup
	wg.Add(1)

	go func() {
		wg.Wait()	///< 等待归零，解除阻塞
		println("wait exit.")
	} ()

	go func() {
		time.Sleep(time.Second)
		println("done.")
		wg.Done()	///< 递减计数
	}()
	wg.Wait()	///< 等待归零
	println("main exit.")

}
/// 输出：
/// done.
/// wait exit.
/// main exit.

GOMAXPROCE

运行时可能会创建很多线程，但任何时候仅有限的几个线程参与并发任务执行。该数量默认与处理器核数相等，可用runtime.GOMAXPROCS函数(或环境变量)修改。

Local Storage

与线程不同，goroutine任务无法设置优先级，无法获取编号，没有局部存储(TLS), 甚至连返回值都会被抛弃。但除优先级外，其他功能都很容易实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func main() {
	var wg sync.WaitGroup
	var gs [5]struct {	///< 用于实现类似TLS功能
		id int	///< 编号
		result int	///< 返回值
	}

	for i := 0; i < len(gs); i++ {
		wg.Add(1)

		go func (id int) {	// 使用参数避免闭包延迟求值
			defer wg.Done()

			gs[id].id = id
			gs[id].result = (id + 1) * 100
		}	(i)
	}

	wg.Wait()
	fmt.Printf("%+v\n", gs)
}
/// 输出：
/// [{id:0 result:100} {id:1 result:200} {id:2 result:300} {id:3 result:400} {id:4 result:500}]

如使用map作为局部存储容器，建议做同步处理，因为运行时会对其做并发读写检查。

Gosched

暂停，释放线程去执行其他任务。当前任务被放回队列，等待下次调度时恢复执行。

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
func main() {
	runtime.GOMAXPROCS(1)
	exit := make(chan struct{})

	go func() {
		defer close(exit)
		go func() {
			println("b")
		}()

		for i := 0; i < 4; i++ {
			println("a:", i)

			if (i == 1) {	/// 让出当前线程，调度执行b
				runtime.Gosched()
			}
		}
	}()
	<-exit
}
/// 输出：
/// a: 0
/// a: 1
/// b
/// a: 2
/// a: 3

Goexit

Goexit立即终止当前任务，运行时确保所有已注册延迟调用被执行。该函数不会影响其他并发任务，不会引发panic, 自然也就无法捕获。

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
func main() {
	exit := make(chan struct{})

	go func () {
		defer close(exit)	///< 执行
		defer println("a")	///< 执行

		func () {
			defer func() {
				println("b", recover() == nil)	///< 执行，recover返回nil
			}()
		func() {	///< 在多层调用中执行Goexit
			println("c")
			runtime.Goexit()	///< 立即终止整个调用堆栈
			println("c done.")
		} ()
		println("b done.")
		}()
		println("a done.")	///< 不会执行
	}()
	<-exit
	println("main exit.")
}
/// 输出：
/// c
/// b true
/// a
/// main exit.

如果在main.main里调用Goexit, 它会等待其他任务结束，然后让进程直接崩溃。
无论身处哪一层，Goexit都能立即终止整个调用堆栈，这与return仅退出当前函数不同。标准库函数os.Exit可终止进程，但不会执行延迟调用。

通道

Go语言并未实现严格的并发安全。
允许全局变量、指针、引用类型这些非安全内存共享操作，就需要开发人员自行维护数据一致和完整性。Go鼓励使用CSP通道，以通信来代替内存共享，实现并发安全。

CSP: Communicating Sequential Process

通过消息来避免竞态的模型除了CSP, 还有Actor。但两者由较大区别
作为CSP核心，通道(channel)是显式的，要求操作双方必须知道数据类型和具体通道，并不关心另一端操作者身份和数量。可如果另一端未准备妥当，或消息未能及时处理时，会阻塞当前端。
相比起来，Actor是透明的，它不在乎数据类型及通道，只要知道接收者信箱即可。默认就是异步方式，发送方对消息是否被接收和处理并不关心。

从底层实现上来说，通道知识一个队列。同步模式下，发送和接受双方配对，然后直接赋值数据给对方。如配对失败，则置入等待队列，直到另一方出现后才被唤醒。异步模式抢夺的则是数据缓冲槽。发送方要求有空槽可供写入，而接收方则要求有缓冲数据可读。需求不符时，同样加入缓冲队列，直到有另一方写入数据或腾出空槽后被唤醒。
除传递消息（数据）外，通道还常被用做事件通知。

1
2
3
4
5
6
7
8
9
10
11
12
13
func main() {
	done := make(chan struct{})
	c := make(chan string)

	go func(){
		s := <-chan	///< 接收消息
		println(s)
		close(done)	///< 关闭通道，作为结束通知
	} ()

	c <- "hi!" 	///< 发送消息
	<-done			///< 阻塞，直到有数据或管道关闭。
}

同步模式必须有配对操作的goroutine出现，否则会一直阻塞。而异步模式在缓冲区未满或数据未读完前，不会阻塞。

1
2
3
4
5
6
7
8
9
10
func main() {
  c := make(chan int, 3)  ///< 创建带3个缓冲槽的异步通道。
  c <- 1  ///< 缓冲区未满，不会阻塞
  c <- 2
  println(<-c)  ///< 缓冲区不会阻塞
  println(<-c)  ///< 缓冲区不会阻塞
}
/// 输出:
/// 1
/// 2

多数时候，异步通道有助于提升性能，减少排队阻塞。
缓冲去大小仅是内部属性，不属于类型组成部分。另外通道变量本身就是指针，可用相等操作符判断是否为同一对象或nil。
内置函数cap和len返回缓冲区大小和当前已缓冲数量；而对于同步通道则都返回0；据此可判断通道时同步还是异步

1
2
3
4
5
6
7
8
9
10
11
12
func main () {
  var a, b := make(chan int), make(chan int, 3)

  b <- 1
  b <- 2

  println("a:", len(a), cap(a))
  println("b:", len(b), cap(b))
}
/// 输出：
/// a: 0 0
/// b: 2 3

收发

除使用简单的发送和接受操作符外，还可用ok-idom或range模式处理数据

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
func main() {
	done := make(chan struct{})
	c := make(chan int)

	go func() {
		defer close(done)		///< 确保发出结束通知

		for {
			x, ok := <-c
			if !ok {	///< 据此判断通道是否被关闭
				return
			}

			println(x)
		}
	} ()

	c <- 1
	c <- 2
	c <- 3
	close(c)	///< 及时使用`close`函数关闭通道引发结束通知，否则可能会导致死锁。
	<-done
}
/// 输出：
/// 1
/// 2
/// 3

一次性事件用close效率更好，没有多余开销。连续或多样性事件，可传递不同数据标志实现。还可使用sync.Cond实现单播或广播事件。

对于closed或nil通道，发送和接收操作都有相应规则：

  • 向已关闭通道发送数据，引发panci
  • 从已关闭接收数据，返回已缓冲数据或零值。
  • 无论收发，nil通道都会阻塞。
1
2
3
4
5
6
7
8
9
10
11
12
func main() {
  c := make(chan int, 3)

  c <- 10
  c <- 20
  close(c)

  for i := 0; i < cap(c)+1; i++ {
    x, ok := <-c
    println(i, ":", ok, x)
  }
}

重复关闭或关闭nil通道都会引发panic错误。

单向

通道默认时双向的，并不区分发送和接收端。
尽管可用make创建单向通道，但那没有任何意义。通常使用类型装欢来获取单向通道，并分别赋予操作双方。

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
func main() {
  var wg sync.WaitGroup
  wg.Add(2)

  c := make(chan int)
  var send chan<- int = c
  var recv <-chan int = c

  go func() {
    defer wg.Done()
    for x := range recv {
      println(x)
    }
  }()

  go func(){
    defer wg.Done()
    defer close(c)

    for i := 0; i < 3; i++ {
      send <- i
    }
  }()

  wg.Wait()
}

不能在单向通道上做逆向操作。

1
2
3
4
5
6
7
8
9
func main(){
  c := make(chan int, 2)

  var send chan<- int = c
  var recv <-chan int = c

  <-send  ///< 无效操作
  recv <- 1 ///< 无效操作
}

同样，close不能用于接收端

1
2
3
4
5
func main() {
  c := make(chan int, 2)
  var recv <- chan int = c
  close(recv) ///< 无效操作
}

无法将单向通道重新转换回去。

1
2
3
4
5
6
7
8
9
func main() {
  var a, b chan int
  a = make(chan int, 2)
  var recv <-chan int = a
  var send chan<- int = a

  b = (chan int)(recv)  /// 错误
  b = (chan int)(send)  /// 错误
}

选择

如要同时处理多个通道，可选用select语句。它会随机选择一个可用通道做收发操作。

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
func main() {
	var wg sync.WaitGroup
	wg.Add(2)

	a, b := make(chan int), make(chan int)

	go func() {	///< 接收端
		defer wg.Done()

		for {
			var (
				name string
				x	int
				ok bool
			)

			select {	///< 随机选择可用 channel 接收数据
			case x, ok = <-a:
				name = "a"
			case x, ok = <-b:
				name = "b"
			}

			if !ok {	///< 如果任一通道关闭，则终止接收
				return
			}

			println(name, x)	///< 输出接收的数据信息
		}
	}()

	go func() {	///< 发送端
		defer wg.Done()
		defer close(a)
		defer close(b)
		for i := 0; i < 10; i++ {
			select {
			case a <- i:
			case b <- i*10:
			}
		}
	}()

	wg.Wait()
}

/// 输出：
/// a 0
/// b 10
/// a 2
/// a 3
/// a 4
/// a 5
/// b 60
/// a 7
/// a 8
/// a 9

如要等全部通道消息处理结束(closed),可将已完成通道设置为nil。这样它就会被阻塞，不再被select选中。
即使是同一通道，也会随机选择case执行。

当所有通道都不可用时，select会执行default语句。如此可避开select阻塞，但须注意处理外层循环，以免陷入空耗。

模式

通常使用工厂方法将goroutine和通道绑定。

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
type receiver struct {
  sync.WaitGroup
  data chan int
}

func newReceiver() * receiver {
  r := &receiver{
    data: make(chan int),
  }
  r.Add(1)
  go func(){
    defer r.Done()
    for x := range r.data{
      println("recv:", x)
    }
  }
}

func main() {
  r := newReceiver()
  r.data <- 1
  r.data <- 2

  close(r.data) ///< 关闭通道，发出结束通知
  r.Wait()  ///< 等待接收者处理结束
}

鉴于通道本身就是一个并发安全的队列，可用作ID generator、Pool等用途。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
type pool chan []byte
func new Pool(cap int) pool {
  return make(chan []byte, cap)
}

func (p pool) get() []byte {
  var v []byte

  select {
    case v = <-p: ///< 获取
    default:  ///< 获取失败，则创建
      v = make([]byte, 10)
  }
  return v
}

func (p pool) put(b []byte) {
  select {
    case p <- b:
    default:  ///< 放回失败，放弃
  }
}

用通道实现信号量(semaphore)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func main() {
  runtime.GOMAXPROCS(4)
  var wg sync.WaitGroup
  sem := make(chan struct{}, 2) ///< 最多允许两个并发同时执行
  for i := 0; i < 5; i++ {
    wg.Add(1)
    go func (id int) {
      defer wg.Done()
      sem <- struct{}{} ///< acquire: 获取信号
      defer func() { <-sem}() ///< release: 释放信号
      time.Sleep(time.Second * 2)
      fmt.Println(id, time.Now())
    }(i)
  }
  wg.Wait()
}

标准库time提供了timeout和tick channel实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func main() {
  go func() {
    for {
      select {
        case <-time.After(time.Second*5):
          fmt.Println("timeout ...")
          os.Exit(0)
      }
    }
  }()

  go func() {
    tick := time.Tick(time.Second)

    for {
      select {
        case <-tick:
          fmt.Println(time.Now())
      }
    }
  }()
  <-(chan struct{})(nil)  // 直接用nil channel阻塞进程
}

捕获INT、TERM信号，顺便实现一个简易的atexit函数。

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
import (
  "os"
  "os/signal"
  "sync"
  "syscall"
)

var exits = &struct {
  sync.RWMutex
  func []func()
  signals chan os.Signal
}{}

func atexit(f func()){
  exits.Lock()
  defer exits.Unlock()
  exits.funcs = append(exits.funcs, f)
}

func waitExit() {
  if exits.signals == nil {
    exits.signals = make(chan os.Signal)
    signal.Notify(exits.signals, syscall.SIGINT, syscall.SIGTERM)
  }
  exits.RLock()
  for _, f := range exits.funcs {
    defer f() ///< 即使某些函数panic,延迟调用也能确保后续函数执行
  }
  exits.RUnlock()
  <-exit.signals
}

func main() {
  atexit(func() {println("exit1 ...")})
  atexit(func() {println("exit2 ...")})
  waitExit()
}

资源泄露

通道可能会引发goroutine leak, 确切的说，是指goroutine处于发送或接收阻塞状态，但一直未被唤醒。垃圾回收器并不收集此类资源，导致他们会在等待队列里长久休眠形成资源泄露。

同步

标准库sync提供了互斥和读写锁，另有原子操作等，可基本满足日常开发需要。Mutex、RWMutex的使用并不复杂，只有几个地方需要注意。
将Mutex作为匿名字段时，相关方法必须实现为pointer-receiver, 否则会因赋值导致锁机制失效。

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
type data struct {
	sync.Mutex
}

func (d data) test(s string) {
	d.Lock()
	defer d.Unlock()

	for i := 0; i < 5; i++ {
		println(s, i)
		time.Sleep(time.Second)
	}
}

func main() {
	var wg sync.WaitGroup
	wg.Add(2)

	var d data
	go func() {
		defer wg.Done()
		d.test("read")
	}	()

	go func() {
		defer wg.Done()
		d.test("write")
	}()
}
  • 锁不支持递归锁。
  • 对性能要求较高时，应避免使用defer Unlock
  • 读写并发时，用RWMutex性能会更好一些
  • 对单个数据读写保护，可尝试用原子操作
  • 执行严格的测试，尽可能打开数据竞争检查