Jiancong Li's Blog
0%

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性能会更好一些
  • 对单个数据读写保护，可尝试用原子操作
  • 执行严格的测试，尽可能打开数据竞争检查

Posted on Edited on In

工作空间

依照规范，工作空间由src、bin、pkg三个目录组成。通常需要将空间路径添加到GOPATH环境变量列表中, 以便相关工具能正常工作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
workspace/
  |
  +-- src/
  |    |
  |    +-- main.go
  |    |
  |    +-- service/
  |          |
  |          +-- user.go
  |
  +-- bin/
  |    |
  |    +-- server
  |
  +-- pkg/
       |
       +-- linux_amd64/
            |
            +-- service.a

在工作空间里，包括子包在内的所有源码文件都保存在src目录下。至于bin、pkg两个目录， 其主要影响 go install/get命令，他们会将编译结果(可执行文件或静态库)安装到这两个目录下，以实现增量编译。

环境变量

编译器等相关工具按GOPATH设置的路径搜索目标。也就是说在导入目标库时，排在列表前面的路径比当前工作空间优先级更高。另外，go get默认将下载的第三方包保存到列表中第一个工作空间内。

环境变量GOPATH用于指示工具链和标准库的存放位置。在生成工具链时，相关路径就已经嵌入到可执行文件内，故无需额外设置。
除通过设置GOROOT环境变量覆盖内部路径外，还可移动目录(改名、符号链接等), 或重新编译工具链来解决。
至于GOBIN, 则是强制替代工作空间的bin目录，作为go install目标保存路径。这可避免将所有工作空间的bin路径添加到PATH环境变量当中。

导入包

使用标准库或第三方包前，须用import导入，参数是工作空间中以src为起始的绝对路径。编译器从标准库开始搜索，然后依次搜索GOPATH列表中的各个工作空间。

1
import "net/http" // 实际路径: /usr/local/go/src/net/http

除使用默认包名外，还可使用别名，以解决同名冲突问题。

1
2
import osx "github.com/apple/osx/lib"
import nix "github.com/linux/lib"

注意: import导入参数是路径，而非包名。尽管习惯将包和目录名保持一致，但这不是强制规定。在代码中引用包成员时，使用包名而非目录名。

有四种不同的导入方式。

1
2
3
4
import    "github.com/Mercy1101/test" // 默认方式: test.A
import X  "github.com/Mercy1101/test" // 别名方式: X.A
import .  "github.com/Mercy1101/test" // 简便方式: A
import _  "github.com/Mercy1101/test" // 初始化方式: 无法引用，仅用来初始化目标包。

不能直接或间接导入自己，不支持任何形式的循环导入。

未使用的导入(不包括初始化方式)会被编译器视为错误。

相对路径

除工作空间和绝对路径外，部分工具还支持相对路径。可在非工作空间目录下，直接运行、编译一些测试代码。
但在设置了GOPATH的工作空间后相对路径会导致编译失败。go run不受影响。

初始化

包内每个源码文件都可定义一到多个初始化函数，但编译器不保证执行次序。
实际上，所有这些初始化函数(包括标准库和导入的第三方包)都由编译器自动生成的一个包装函数进行调用，因此可保证在单一线程上执行，且仅执行一次。

编译器首先确保完成所有全局变量初始化，然后才开始执行初始化函数。直到这些全部结束后，运行时才正式进入main.main入口函数。
可在初始化函数中创建goroutine，或等到它结束执行。

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

  go func(){
    defer close(done)
    fmt.Println("init:", time.Now)
    time.Sleep(time.Second * 2)
  } ()

  <-done
}

func main () {
  fmt.Println("main: ", time.Now())
}

如果在多个初始化函数中引用全局变量，那么最好在变量定义处直接赋值。因无法保证执行次序，所以任何初始化函数中的赋值都有可能”延迟无效”。

内部包

内部包机制相当于增加了新的访问权限控制：所有保存在internal目录下的包(包括自身)仅能被其父目录下的包(包含所有子目录) 访问。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
workspace/
  |
  +-- src/
  |    |
  |    +-- main.go
  |    |
  |    +-- lib/
  |         |
  |         +-- internal/
  |         |       |
  |         |       +-- a/
  |         |       |
  |         |       +-- b/
  |         +-- x/
  |             |
  |             +-- y/
  |

在lib目录外(比如main.go)导入内部包会引发编译错误。

导入内部包必须使用完整路径， 例如： import “lib/internal/a”

依赖管理

如何使用vendor，专门存放第三方包，实现将源码和依赖完整打包分发。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
workspace/
  |
  +-- src/
  |    |
  |    +-- main.go
  |    |
  |    +-- server/
  |         |
  |         +-- vendor/
  |         |       |
  |         |       +-- github.com/
  |         |              |
  |         |              +-- mercy1101/
                                  |
                                  +-- test/
1
2
3
4
5
package main
import "github.com/Mercy1101/test"
func main(){
  test.Hello()
}

在main.go中导入github.com/mercy1101/test时，优先使用vendor/github.com/mercy1101/test

导入vendor中的第三方包，参数是以vendor/为起点的绝对路径。这避免了vendor目录位置带来的麻烦，让导入无论使用vendor,还是GOPATH都能保持一致。

注意：vendor优先级比标准库高

当多个vendor目录嵌套时，匹配规则如下:
从当前源文件所在目录开始，逐级向上构造vendor全路径，直到发现路径匹配的目标为止。匹配失败，则依旧搜索GOPATH

要使用vendor机制，须开启GO15VENDOREXPERIMENT=1环境变量开关(Go 1.6默认开启),且必须设置了GOPATH的工作空间。

使用go get下载第三方包时，依旧使用GOPATH第一个工作空间，而非vendor目录。当前工具链中并没有真正意义上的包依赖管理，好在由不少第三放工具可选。

Posted on Edited on In

反射

反射能让我们能在运行期探知对象的类型信息和内存结构，同时反射还是实现元编程的重要手段。
Go对象头部并没有类型指针，通过自身是无法在运行期获知任何类型相关信息的。反射操作所需的全部信息都源自接口变量。接口变量除自身存储自身类型外，还会保存实际对象的类型数据。

1
2
func TypeOf(i interface{}) Type
func ValueOf(i interface{}) Value

这两个反射入口函数，会将任何传入的对象转换为接口类型。

在面对类型是，需要区分Type和Kind。前者表示真实类型(静态类型), 后者表示器接触接口(底层类型)类别。

1
2
3
4
5
6
7
8
type X int
func main() {
  var a X = 100
  t := reflect.TypeOf(a)

  fmt.Println(t.Name(), t.Kind())
  /// 输出：X int
}
1
2
3
4
5
6
func main() {
  a := reflect.ArrayOf(10, reflect.TypeOf(byte(0)))
  b := reflect.MapOf(reflect.TypeOf(""), reflect.TypeOf(0))
  fmt.Println(a, m)
  /// 输出: [10]uint8 map[string]int
}

方法Elem返回指针、数组、切片、字典值或通道的基类型。

1
2
3
4
5
func main() {
  fmt.Println(reflect.TypeOf(map[string]int{}).Elem())
  fmt.Println(reflect.TypeOf([]int32{}).Elem())
  /// 输出： int int32
}

只有在获取结构体指针的基类型后，才能遍历它的字段。

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

import (
	"fmt"
	"reflect"
)

type user struct {
	name string
	age int
}

type manager struct {
	user
	title string
}

func main() {
	var m manager
	t := reflect.TypeOf(&m)
	if t.Kind() == reflect.Ptr {
		t = t.Elem()
	}

	for i := 0; i < t.NumField(); i++ {
		f := t.Field(i)
		fmt.Println(f.Name, f.Type, f.Offset)
		if f.Anonymous {
			for x := 0; x < f.Type.NumField(); x++ {
				af := f.Type.Field(x)
				fmt.Println("  ", af.Name, af.Type)
			}
		}
	}
}
/// 输出：
/// user main.user 0
///  name string
///   age int
/// title string 24

对于匿名字段，可用多级索引（按定义顺序）直接访问

1
2
3
4
5
6
7
8
9
10
11
12
13
func main() {
	var m manager
	t := reflect.TypeOf(m)
	name, _ := t.FieldByName("name")	///< 按名称查找
	fmt.Println(name.Name, name.Type)

	age := t.FieldByIndex([]int{0, 1})	///< 按多级索引查找
	fmt.Println(age.Name, age.Type)
}

/// 输出:
/// name string
/// age int

FieldByName不支持多级名称，如有同名遮蔽，须通过匿名字段二次获取

反射能探知当前包或外包的非导出结构成员

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

import (
	"fmt"
	"net/http"
	"reflect"
)

func main() {
	var s http.Server
	t := reflect.TypeOf(s)
	for i := 0; i < t.NumField(); i++ {
		fmt.Println(t.Field(i).Name)
	}
}

/// 输出：
/// Addr
/// Handler
/// TLSConfig
/// ReadTimeout
/// ReadHeaderTimeout
/// WriteTimeout
/// IdleTimeout
/// MaxHeaderBytes
/// TLSNextProto
/// ConnState
/// ErrorLog
/// BaseContext
/// ConnContext
/// inShutdown
/// disableKeepAlives
/// nextProtoOnce
/// nextProtoErr
/// mu
/// listeners
/// activeConn
/// doneChan
/// onShutdown

相对reflect而言，当前包和外包都是”外包”

可用反射提取struct tag, 还能自动分解。其常用于ORM映射, 或数据格式验证。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
type user struct {
	name string `field:"name" type:"varchar(50)"`
	age int	`field:"age" type:"int"`
}

func main() {
	var u user
	t := reflect.TypeOf(u)
	for i := 0; i < t.NumField(); i++ {
		f := t.Field(i)
		fmt.Printf("%s: %s %s\n", f.Name, f.Tag.Get("field"), f.Tag.Get("type"))
	}
}

/// 输出：
/// name: name varchar(50)
/// age: age int

辅助判断方法Implements、ConvertibleTo、AssignableTo 都是运行期进行动态调用和赋值所必需的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
type X int

func (X) String() string {
	return ""
}

func main() {
	var a X
	t := reflect.TypeOf(a)

	// Implements 不能直接使用类型作为参数，导致这种用法特别别扭
	st := reflect.TypeOf((*fmt.Stringer)(nil)).Elem()
	fmt.Println(t.Implements(st))

	it := reflect.TypeOf(0)
	fmt.Println(t.ConvertibleTo(it))

	fmt.Println(t.AssignableTo(st), t.AssignableTo(it))
}
/// 输出：
/// true
/// true
/// true false

值

和Type获取类型信息不同， Value专注于对象实例数据读写
接口变量会赋值对象，且时unaddressable的，所以要修改对象就必须使用指针。

1
2
3
4
5
6
7
8
9
10
func main() {
  a := 100
  va, vp := reflect.ValueOf(a), reflect.ValueOf(&a).Elem()

  fmt.Println(va.CanAddr(), va.CanSet())
  fmt.Println(vp.CpnAddr(), va.CanSet())
}
/// 输出:
/// false false
/// true true

就算传入指针，一样需要通过Elem获取目标对象。因为被接口存储的指针本身时不能寻址和进行设置操作的。

注意：不能对非导出字段进行设置操作，无论是当前包还是外包。

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 User struct {
	Name string
	code int
}

func main() {
	p := new(User)
	v := reflect.ValueOf(p).Elem()
	name := v.FieldByName("Name")
	code := v.FieldByName("code")

	fmt.Printf("name: canaddr = %v, canset = %v\n", name.CanAddr(), name.CanSet())
	fmt.Printf("code: canaddr = %v, canset = %v\n", code.CanAddr(), code.CanSet())

	if name.CanSet() {
		name.SetString("Tom")
	}
	if code.CanAddr() {
		*(*int)(unsafe.Pointer(code.UnsafeAddr())) = 100
  }
  fmt.Printf("%+v\n", *p)
}
/// 输出：
/// name: canaddr = true, canset = true
/// code: canaddr = true, canset = false
/// {Name:Tom code:100}

Value.Pointer和Value.Int等方法类似，将Value.data存储的数据转换为指针，目标必须是指针类型。
而UnsafeAddr返回任何CanAddr Value.data地址（相当于&取地址操作）,比如Elem后的Value, 以及字段成员地址。
以结构体里的指针类型字段为例，Pointer返回该字段所保存的地址，而UnsafeAddr返回该字段本身的地址(结构对象地址+偏移量)

可通过Interface方法进行类型推断

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() {
	type user struct {
		Name string
		Age int
	}

	u := user{
		"q.yuhen",
		60,
	}

	v := reflect.ValueOf(&u)
	if !v.CanInterface() {
		println("CanInterface: fail.")
		return
	}

	p, ok := v.Interface().(*user)
	if !ok {
		println("Interface: fail.")
		return
	}

	p.Age++
	fmt.Printf("%+v\n", u)
}
/// 输出：
/// {Name:q.yuhen Age:61}

也可以直接使用Value.Int、Bool等方法进行类型转换，但失败时会引发panic, 且不支持ok-idiom

复合类型对象设置示例：

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

  if v.TrySend(reflect.ValueOf(100)) {
    fmt.Println(v.TryRecv())
  }
}
/// 100 true

接口有两种nil状态，这一致是个潜在麻烦。解决方法是用IsNil判断值是否为nil

1
2
3
4
5
6
7
8
9
10
func main() {
  var a interface{} = nil
  var b interface{} = (*int)(nil)

  fmt.Println(a == nil)
  fmt.Println(b == nil, reflect.ValueOf(b).IsNil())
}
/// 输出：
/// true
/// false true

也可用unsafe转换后直接判断iface.data是否是零值

1
2
3
4
5
6
7
8
func main() {
  var b interface{} = (*int)(nil)
  iface := (*[2]uintptr)(unsafe.Pointer(&b))
  fmt.Println(iface, iface[1] == 0)
}

/// 输出:
/// &[712160 0] true

让人很无奈的是, Value里的某些方法并未实现ok-idom或返回error, 所以得自行判断返回的是否为Zero Value

1
2
3
4
5
6
7
8
func main(){
  v := reflect.ValueOf(struct{name string})
  println(v.FieldByName("name").IsValid())
  println(v.FieldByName("xxx").IsValid())
}
/// 输出：
/// true
/// false

方法

动态调用方法，谈不上有多麻烦。只须按In列表准备好所需参数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
type X struct{}
func (X) Test(x, y int) (int, error) {
  return x + y, fmt.Errorf("err: %d", x+y)
}

func main() {
  var a X
  v := reflect.ValueOf(&a)
  m := MethodByName("Test")

  in := []reflect.Value {
    reflect.ValueOf(1),
    reflect.ValueOf(2),
  }

  out := m.Call(in)
  for _, v := range out {
    fmt.Println(v)
  }
}

/// 输出:
/// 3
/// err: 3

对于变参来书，用CallSlice要更方便一些

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
type X struct {}
 func (X) Format(s string, a ...interface{}) string {
   return fmt.Sprintf(s, a...)
 }

 func main() {
   var a X
   v := reflect.ValueOf(&a)
   m := v.MethodByName("Format")
   out := m.Call([]reflect.Value{
     reflect.ValueOf("%s = %d"),
     reflect.ValueOf("x"),
     reflect.ValueOf("100"),
   })

   fmt.Println(out)

   out = m.CallSlice([]reflect.ValueP{
     reflect.ValueOf("%s = %d"),
     reflect.ValueOf([]interface{}{"x", 100}),
   })

   fmt.Println(out)
 }
/// 输出：
/// [x = 100]
/// [x = 100]

构建

反射库提供了内置函数make和new的对应操作，其中最有意思的就是MakeFunc。可用它实现通用模板，使用不同数据类型。

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
// 通用算法函数
func add(args []reflect.Value) (results []reflect.Value) {
  if len(args) == 0 {
    return nil
  }

  var ret reflect.Value
  switch args[0].Kind() {
  case reflect.Int:
    n := 0
    for _, a := range args {
      n += int(a.Int())
    }

    ret = reflect.ValueOf(n)
  case reflect.String:
    ss := make([]string, 0, len(args))
    for _, s := range args {
      ss = append(ss, s.String())
    }
    ret = reflect.ValueOf(strings.Join(ss, ""))
  }
  results = append(results, ret)
  return
}

/// 将函数指针参数指向通用算法函数
func makeAdd(fptr interface{}){
  fn := reflect.ValueOf(fptr).Elem()
  v := reflect.MakeFunc(fn.Type(), add) // 这是关键
  fn.Set(v) // 指向通用算法函数
}

func main () {
  var intAdd func(s, y int) int
  var strAdd func(a, b string) string

  makeAdd(&intAdd)
  makeAdd(&strAdd)
  println(intAdd(100, 200))
  println(strAdd("hello,", "world!"))
}
/// 输出:
/// 300
/// hello, world!

Posted on Edited on In

11. 测试

标准库自带单元测试框架

  • 测试代码须放在当前包以”_test.go”结尾的文件中
  • 测试函数以Test为名称前缀
  • 测试命令(go test) 忽略以”_” 或 “.” 开头的测试文件
  • 正常编译操作(go build/install)会忽略测试文件
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
package main

import (
	"testing"
	"time"
)

func add(x, y int) int {
	return x + y
}

func TestAdd(t *testing.T) {
	var tests = []struct {
		x	int
		y	int
		expect	int
	} {
		{1, 1, 2},
		{2, 2, 4},
		{3, 2, 5},
	}

	for _, tt := range tests {
		actual := add(tt.x, tt.y)
		if actual != tt.expect {
			t.Errorf("add(%d, %d): expect %d, actual %d", tt.x, tt.y, tt.expect, actual)
		}
	}
}

func TestA(t *testing.T){
	t.Parallel()
	time.Sleep(time.Second * 2)
}

func TestB(t *testing.T){
	t.Parallel()


	time.Sleep(time.Second * 2)
}
参数 说明 示例
-arg 命令行参数
-v 输出详细信息
-parallel 并发执行, 默认执行GOMAXPROCS -parallel 2
-run 指定测试函数，正则表达式 -run “Add”
-timeout 全部测试累计时间超时将引发panic, 默认值为10ms -timeout 1m30s
-count 重复测试次数，默认次数为1

test main

1
2
3
4
5
6
func TestMain(m * testing.M){
	// setup
	code := m.Run()	// 调用测试函数
	// tear down
	os.Exit(code)	// 注意： os.Exit 不会执行defer
}

多测试用例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func TestMain(m * testing.M) {
	match := func(pat, str string) (bool, error) {	// pat: 命令行参数-run 提供的过滤条件
		return true, nil	// str: InternalTest.Name
	}

	tests := []testing.InternalTest {
		{"b", TestB},
		{"a", TestA},
	}

	benchmarks := []testing.InternalBenchmark{}
	examples := []testing.InternalExample{}

	m = testing.MainStart(match, tests, benchmarks, examples)

	os.Exit(m.Run())
}

example

1
2
3
4
5
6
7
8
func ExampleAdd() {
	fmt.Println(add(1, 2))
	fmt.Println(add(2, 2))

	// Output:
	// 3
	// 4
}

注意：如果没有output注释，该示例就不会被执行。另外，不能使用内置函数print/printIn, 因为他们输出到stderr

benchmark

1
2
3
4
5
func BenchmarkAdd(b *testing.B) {
	for i := 0; i < b.N; i++ {
		_ = add(1, 2)
	}
}

go test -bench .

如果希望仅执行性能测试，那么可以用run=NONE忽略所有测试用例。
性能测试默认以并发方式进行测试，但可用cpu参数设定多个并发限制来观察结果。

go test -bench . -cpu 1,2,4

某些耗时的目标，默认循环测试过少，取平均值不足以准确计量性能。可用benchtime设定最小测试时间来增加循环次数，以便返回更准确的结果。

go test -bench . -benchtime 5s

timer

如果在测试函数中要执行一些额外的操作，那么应该临时i组织计时器工作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func BenchmarkAdd(b *testing.B) {
	time.Sleep(time.Second)
	b.ResetTimer()	// 重置

	for i := 0; i < b.N; i++ {
		_ = add(1, 2)
		if i == 1 {
			b.StopTimer()	// 暂停
			time.Sleep(time.Second)
			b.StartTimer()	// 恢复
		}
	}
	for i := 0; i < b.N; i++ {
		_ = add(1, 2)
	}
}

memory

性能测试查看内存情况

1
2
3
4
5
6
7
8
9
func heap() []byte {
	return make([]byte, 1024*10)
}

func BenchmarkHeap(b *testing.B) {
	for i := 0 ; i < b.N; i++ {
		_ = heap()
	}
}

go test -bench . -benchmem -gcflags “-N -l” # 禁止内联和优化， 以便观察结果

也可将测试函数设置为总是输出内存分配信息，无论使用benchmem参数与否

1
2
3
4
5
6
7
func BenchmarkHeap(b *testing.B) {
	b.ReportAllocs()
	b.ReportTimer()
	for i := 0 ; i < b.N; i++ {
		_ = heap()
	}
}

代码覆盖率

go test -cover

为获取更详细信息，可指定covermode 和coverprofile 参数

  • set: 是否执行
  • count: 执行次数
  • atomic: 执行次数，支持并发模式

    go test -cover -covermode count -coverprofile cover.out

还可以在浏览器中查看包括具体的执行次数等信息

go tool cover -html=cover.out

性能监控

引发性能问题的原因无外乎执行时间过长、内存占用过多，以及意外阻塞。通过捕获或监控相关执行状态数据，就可定位引发问题的原因，从而针对性改进算法。

go test -run NONE -bench . -memprofile mem.out -cpuprofile cpu.out net/http

参数 说明 示例
-cpuprofile 保存执行时间采样到指定文件 -cpuprofile cpu.out
-memprofile 保存内存分配采样到指定文件 -memprofile mem.out
-memprofilerate 内存分配采样起始值，默认为512KB -memprofilerate 1
-blockprofile 保存阻塞时间采样到指定文件 -blockprofile block.out
-blockprofilerate 阻塞时间采样起始值，单位为：ns

如果执行性能测试，可能需要设置benchtime参数，以确保有足够的采样时间

可使用交互模式查看，或用命令行直接输出单向结果。

go tool pprof http.test mem.out
(pprof) top5

  • flat: 仅当前函数，不包括它调用的其他函数。
  • sum: 列表前几行所占百分比的总和。
  • cum: 当前函数调用堆栈累计。

top命令可指定排序字段，比如top5 -cum
找出需要进一步查看的目标，使用peek命令列出调用来源
也可用list命令输出源码统计样式，以便更直观的定位
除文字模式以外，还可输出svg图形，将其保存或用浏览器查看

在线采集数据须诸如 http/pprof包

1
2
3
4
5
6
7
8
import (
  "net/http"
  _ "net/http/pprof"
)

func main() {
  http.ListenAndServe(":8080", http.DefaultServeMux)
}

用浏览器访问指定路径，就可看到不同的检测项。

go tool pprof http://localhost:8080/debug/pprof/heap?debug=1

必要时还可抓取数据，进行离线分析。

curl http://localhost:8080/debug/pprof/heap?debug=1 > mem.out
go tool pprof test mem.out

Posted on Edited on In

C++ 迭代器介绍

迭代器概念

Iterator(迭代器)是一种”能够迭代某序列内所有元素”的对象，可通过改变自寻常pointer的一致性接口来完成工作。Iterator奉行一个纯抽象概念：任何东西，只要行为类似iterator，就是一种iterator。然而不同的的iterator具有不同的行进能力。

迭代器种类

迭代器种类 能力 提供者
Output 迭代器 向前写入 Ostream,inserter
Input 迭代器 向前读取一次 Istream
Forward 迭代器 向前读取 Forward list、unordered containers
Bidirectional 迭代器 向前和向后读取 List、set、multiset、map、multimap
Random-access 迭代器 以随机访问方式读取 Array、vector、deque、string、C-style array
迭代器种类

Output迭代器

Output迭代器允许一步一步前行并搭配write动作。因此你可以一个一个元素地赋值，不能使用output迭代器对同一区间迭代两次。事实上，甚至不保证你可以将一个value复制两次而其迭代器不累进。我们的目标是将一个value以下列形式写入一个黑洞。

1
2
3
4
while(...) {
  *pos = ...;
  ++pos;
}

Output 迭代器无需比较操作。你无法检验output迭代器是否有效，或写入是否成功。你唯一可做的就是写入。通常，一批写入动作是以一个”额外条件定义出”的”特定output迭代器”作为结束。
见下表Output迭代器操作

表达式 效果
*iter = val 将val写至迭代器所指的位置
++iter 向前步进(step forward), 返回新位置
iter++ 向前步进(step forward), 返回旧位置
TYPE(iter) 复制迭代器(copy 构造函数)

通常，迭代器可用来读，也可用来写; 几乎所有reading迭代器都有write的额外功能，这种情况下他们被称为mutable(可产生变化的)迭代器。
一个典型的pure output迭代器例子是：”将元素写至标准输出设备”。 如果采用两个output迭代器写至屏幕, 第二个字将跟在第一个字后面，而不是覆盖第一个字。另一个典型的例子是inserter, 那是一种用来将他插入容器。如果随后写入第二个value, 并不会覆盖第一个value, 而是安插进去。

Input迭代器

Input迭代器只能一次一个以前行方向读取元素，按此顺序一个个返回元素值。
Input迭代器的各项操作

表达式 效果
*iter 读取实际元素
iter->member 读取实际元素的成员(如果有的话)
++iter 向前步进(step forward), 返回新位置
iter++ 向前步进(step forward), 返回旧位置
iter1 == iter2 判断两个迭代器是否相等
iter1 != iter2 判断两个迭代器是否不相等
TYPE(iter) 复制迭代器(copy 构造函数)

Input迭代器只能读取元素一次。如果你复制input迭代器, 并令原input迭代器和新产生的拷贝都向前读取, 可能会遍历到不同的值。
所有的迭代器都具备input迭代器的能力，而且往往更强。Pure input迭代器的典型例子就是”从标准输入设备读取数据”。同一个值不会被读取两次。一旦从input stream读入一个字(离开input缓冲区), 下次读取时就会返回另一个字。

对于input迭代器, 操作符==和!=只用来检查”某个迭代器是否等于一个past-the-end迭代器(指指向最末元素的下一个位置)”.这有其必要, 因为处理input迭代器的操作函数通常会有以下行为。

1
2
3
4
5
6
InputIterator pos, end;

while (pos != end) {
  ... // read-only access using *pos
  ++pos;
}

没有任何保证说，两个迭代器如果都不是past-the-end迭代器, 且指向不同位置，他们的比较结果会不相等(这个条件是和forward迭代器搭配引入的)。

也请注意, input迭代器的后置式递增操作符(++iter)不一定会返回什么东西。不过通常它会返回旧位置。
你应该尽可能优先先选用前置式递增操作符(++iter)而非后置式递增操作符(iter++), 因为前者效能更好。因为后者会返回一个临时对象。

Forward(前向)迭代器

Forward迭代器是一种input迭代器且在前进读取时提供额外保证。

表达式 效果
*iter 访问实际元素
iter->member 访问实际元素的成员
++iter 向前步进(返回新位置)
iter++ 向前步进(返回旧位置)
iter1 == iter2 判断两个迭代器是否相等
iter1 != iter2 判断两个迭代器是否不等
TYPE() 创建迭代器(default构造函数)
TYPE(iter) 复制迭代器(拷贝构造函数)
iter1 = iter2 对迭代器赋值(assign)
和input迭代器不同的是, 两个forward迭代器如果指向同一元素, operator==会获得true, 如果两者都递增, 会再次指向同一元素。
例如： 
1
2
3
4
5
6
7
8
9
10
11
12
13
ForwardIterator pos1, pos2;

pos1 = pos2 = begin; /// both iterator refer to the same element
if(pos1 != end) {
  ++pos1; /// pos1 is one element ahead
  while(pos1 != end) {
    if(*pos1 == *pos2) {
      ... // precess adjacent duplicates
      ++pos1;
      ++pos2;
    }
  }
}

Forward迭代器由以下对象和类型提供：

  • Class
  • Unordered container
    然而标准库也允许unordered容器的实现提供bidirectional迭代器。
    如果forward迭代器履行了output迭代器应有的条件, 那么它就是一个mutable forward迭代器, 即可用于读取，也可用于涂写。

Bidirectional(双向)迭代器

Bidirectional迭代器在forward迭代器的基础上增加回头迭代(iterate backward)能力。

Bidirectional 迭代器的新增操作

表达式 效果
–iter 步退(返回新位置)
iter– 步退(返回旧位置)

Bidirectional迭代器由以下的对象和类型提供：

  • Class list<>.
  • Associative(关联式) 关联式容器提供

如果bidirectional迭代器履行了output迭代器应有的条件, 那么他就是个mutable bidirectional迭代器, 即可用于读取, 也可用于涂写。

Random-Access(随机访问)迭代器

Random-access迭代器在bidirectional迭代器的基础上增加了随机访问能里。因此它必须提供iterator算数运算。也就是说，它能增减某个偏移量、
计算距离(difference), 并运用诸如<和>等管理操作符(relational operator)进行比较。
随机访问迭代器的新增操作:

表达式 效果
iter[n] 访问索引位置为n的元素
iter+=n 前进n个元素(如果n是负数, 则改为回退)
iter-=n 回退n个元素(如果n是负数, 则改为前进)
iter+n 返回iter之后的第n个元素
n+iter 返回iter之后的第n个元素
iter-n 返回iter之前的第n个元素
iter1-iter2 返回iter1和iter2之间的距离
iter1 < iter2 判断iter1是否在iter2之前
iter1 > iter2 判断iter1是否在iter2之后
iter1 <= iter2 判断iter1是否不在iter2之后
iter1 >= iter2 判断iter1是否不在iter2之前

Random-access迭代器由以下对象和类型提供:

  • 可随机访问的容器(array、vector、deque)
  • String(string、wstring)
  • 寻常的C-Style(pointer)

迭代器相关辅助函数

std::advance()

std::advance()可将迭代器的位置增加, 增加的幅度由实参决定, 也就是说它令迭代器一次前进(或后退)多个元素:

1
2
#include <iterator>
void advance(InputIterator& pos, Dist n)
  • 令名称为pos的input迭代器前进(或后退)n个元素
  • 对bidirectinal迭代器和random-access迭代器而言, n可为负值, 表示后退
  • Dist是个template类型。通常它必须是个整数类型, 因为会调用诸如<、++、--等操作, 还要和0做比较。
  • std::advance()并不检查迭代器是否超过序列的end()(因为迭代器通常不知道其所操作的容器, 因此并无检查)。所以, 调用std::advance()有可能导致不明确行为–因为”对序列尾端调用operator++“是一种未定义的行为。

对于random-access迭代器, 此函数只是简单地调用pos+=n, 因此具有常量复杂度。 对于其他任何类型的迭代器, 则调用++pos(或--pos如果n为负值)n次。因此，对于其他任何类型地迭代器, 本函数具有线性复杂度。
如果你希望你的程序可以轻松地更换容器和迭代器种类, 你应该使用std::advance()而不是operator+=
另外, 请注意std::advance()不具有返回值, 而operator+=会返回新位置, 所以后者可作为更大表达式的一部分。

下面是一个std::advance()的实现。

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
/// 输入迭代器的情况
template <class _InIt, class _Diff>
inline void advance_impl(_InIt& _Where, _Diff _Off, std::input_iterator_tag) {
  /// 检查该偏移量不能为负值
  if (_Off < 0) {
    assert(false && "negative offset in advance");
  }
  /// 使用自增运算符来计算
  for (; 0 < _Off; --_Off) ++_Where;
}

/// 双向迭代器
template <class _BidIt, class _Diff>
inline void advance_impl(_BidIt& _Where, _Diff _Off,
                         std::bidirectional_iterator_tag) {
  /// 使用自增运算符来计算
  for (; 0 < _Off; --_Off) ++_Where;
  /// 如果偏移量为负值则使用自减运算符
  for (; _Off < 0; ++_Off) --_Where;
}

/// 随机访问迭代器
template <class _RanIt, class _Diff>
inline void advance_impl(_RanIt& _Where, _Diff _Off,
                         std::random_access_iterator_tag) {
  /// 使用operator += ，常量复杂度
  _Where += _Off;
}

template <class _InIt, class _Diff>
inline void advance(_InIt& _Where, _Diff _Off) {
  advance_impl(_Where, _Off,
               /// 在萃取迭代器的特性时去掉其const的属性来提高性能
               std::iterator_traits<_Iter>::iterator_category<
                   std::remove_const_t<_InIt>>());
}

std::next()和std::prev()

c++ 提供了两个新增的辅助函数, 允许你前进和后退移动迭代器的位置。

1
2
3
#include <iterator>
ForwardIterator next(ForwardIterator pos)
ForwardIterator next(ForwardIterator pos, Dist n)
  • 导致forward迭代器pos前进或n个位置
  • 如果处理的是bidirectional和random-access迭代器, n可为负值, 导致后退移动
  • Dist是类型std::iterator_traits<ForwardIterator>::difference_type
  • 其内部将对一个临时对象调用std::advance(pos, n)
  • 注意, std::next()并不检查是否会跨越序列的end()。因此调用者必须自行担保其结果有效。
1
2
3
#include <iterator>
BidirectionalIterator prev(BidirectionalIterator pos)
BidirectionalIterator prev(BidirectionalIterator pos, Dist n)
  • 导致bidirectional迭代器pos后退一个或n个位置
  • n可为负值, 导致向前移动
  • Dist是类型std::iterator_traits<ForwardIterator>::difference_type
  • 其内部将对一个临时对象调用std::advance(pos, -n)
  • 注意, std::prev()并不检查是否会跨越序列的begin()。因此调用者必须自行担保其结果有效。

下面写一个简单的实现：

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
template <class _InIt>
inline _InIt next(
    _InIt _First,
    std::iterator_traits<_InIt>::iterator_category<_InIt> _Off = 1) {
  static_assert(
      std::is_base_of<
          std::input_iterator_tag,
          typename std::iterator_traits<_InIt>::iterator_category>::value,
      "next requires input iterator");

  advance(_First, _Off);
  return (_First);
}

template <class _BidIt>
inline _BidIt prev(
    _BidIt _First,
    std::iterator_traits<_BidIt>::iterator_category<_BidIt> _Off = 1) {
  static_assert(
      std::is_base_of<
          std::bidirectional_iterator_tag,
          typename std::iterator_traits<_BidIt>::iterator_category>::value,
      "prev requires bidirectional iterator");

  advance(_First, -_Off);
  return (_First);
}

std::distance()

std::distance()用来处理两个迭代器之间的距离:

1
Dist distance(InputIterator pos1, InputIterator pos2)
  • 返回两个input迭代器pos1和pos2之间的距离。
  • 两个迭代器必须指向同一个容器
  • 如果不是random-access迭代器, 则从pos1开始前进必须能够到达pos2, 亦即pos2的位置必须与pos1相同或在其后。
  • 返回类型Dist是类型std::iterator_traits<ForwardIterator>::difference_type

注意： 处理两个non-random-access迭代器之间的距离时, 必须十分小心。第一个迭代器所指的元素绝不能在第二个迭代器所指元素之后方, 否则会导致不明确的行为。如果不知道哪个迭代器在前, 你必须先算出两个迭代器分别至容器起点的距离, 在根据这两个距离来判断。

一个简单的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template <typename it>
typename std::iterator_traits<it>::difference_type distance(it from, it to) {
  if constexpr (typename std::iterator_traits<it>::iterator_category() ==
                std::random_access_iterator_tag) {
    /// 随机访问迭代器
    return to - from;
  } else if constexpr (typename std::iterator_traits<it>::iterator_category() ==
                       std::input_iterator_tag) {
    /// input 迭代器
    typename std::iterator_traits<it>::difference_type res = 0;
    for (; from != to; ++from) {
      ++res;
    }
    return res;
  } else {
    static_assert("unknow iterator type.");
  }
}

std::iter_swap()

这个简单的辅助函数用来交换两个迭代器所指的元素值

1
2
#include <algorithm>
void iter_swap(ForwardIterator1 pos1, ForwardIterator pos2)
  • 交换迭代器pos1和pos2所指的值
  • 迭代器的类型不必相同, 但其所指的两个值必须可以相互赋值