李建聪的博客
0%

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<forward_list>
  • 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所指的值
  • 迭代器的类型不必相同, 但其所指的两个值必须可以相互赋值

Posted on Edited on In

integer_sequence

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
#include <array>
#include <iostream>
#include <tuple>
#include <utility>

template <typename T, T... ints>
void print_sequence(std::integer_sequence<T, ints...> int_seq) {
  std::cout << "" << int_seq.size() << ": ";
  ((std::cout << ints << ' '), ...);
  std::cout << '\n';
}

/// 转化数组为tuple
template <typename Array, std::size_t... I>
auto a2t_impl(const Array& a, std::index_sequence<I...>) {
  return std::make_tuple(a[I]...);
}

template <typename T, std::size_t N,
          typename Indices = std::make_index_sequence<N>>
auto a2t(const std::array<T, N>& a) {
  return a2t_impl(a, Indices{});
}

/// 漂亮地打印 tuple
template <class Ch, class Tr, class Tuple, std::size_t... Is>
void print_tuple_impl(std::basic_ostream<Ch, Tr>& os, const Tuple& t,
                      std::index_sequence<Is...>) {
  ((os << (Is == 0 ? "" : ", ") << std::get<Is>(t)), ...);
}

template <class Ch, class Tr, class... Args>
auto& operator<<(std::basic_ostream<Ch, Tr>& os, const std::tuple<Args...>& t) {
  os << "(";
  print_tuple_impl(os, t, std::index_sequence_for<Args...>{});
  return os << ")";
}

int main() {
  print_sequence(std::integer_sequence<unsigned, 9, 2, 5, 1, 9, 1, 6>{});
  print_sequence(std::make_integer_sequence<int, 20>{});
  print_sequence(std::make_index_sequence<10>{});
  print_sequence(std::index_sequence_for<float, std::iostream, char>{});

  std::array<int, 4> array = {1, 6, 3, 4};

  auto tuple = a2t(array);
  static_assert(std::is_same<decltype(tuple), std::tuple<int, int, int, int>>::value, "");

  std::cout << tuple <<'\n';
  system("pause");
}

Posted on Edited on In

正确写法

该写法在第一次调用get_instance()后构造该实例，线程安全。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class object{
  public:
  ~object() = default;
  static std::unique_ptr<object>& get_instance();
  private:
  object() = default; ///< 构造函数写为private，防止其他调用者单独构造该对象实例。
};

std::unique_ptr<object>& object::get_instance();
  static std::unique_ptr<object> instance;  ///< 该对象的唯一实例
  static std::once_flag flag; ///< 标志位, 标记只调用一次
  std::call_once(flag, [&](){
    instance = std::make_unique<object>();  ///< C++14以后版本的方法
    /*
    instance = std::unique_ptr<object>(new object()); ///< C++14 到 C++11 可用的方法
    */
  });
  return instance;
}

其他写法比较

最简单的写法: 线程不安全
由于new object()这个构造的过程需要时间，所以可能造成两个线程同时获取到instance变量为空指针。从而导致实例化两次，从未导致硬件驱动加载两次，而导致崩溃。

1
2
3
4
5
6
7
object* object::get_instance() {
  object* instance = nullptr;
  if(instance == nullptr) {
    instance = new object();
  }
  return instance;
}

double check写法： 看起来线程安全，其实有条件竞争。
在#1和#2处，可能发生一个线程正在对instance变量赋值(写操作), 而另一个线程在进行在进行判断instance变量是否为空(读操作)，从而导致条件竞争，而导致崩溃。

1
2
3
4
5
6
7
8
9
10
11
object* object::get_instance(){
  static std::mutex mt;
  volatile object* instance = nullptr;  ///< volatile关键字为了防止编译器优化
  if(instance == nullptr) { ///< #1 读操作
    std::lock_guard<std::mutex> lock(mt);
    if(instance == nullptr) {
        instance = new object();  ///< #2 写操作
    }
  }
  return instance;
}

Posted on Edited on In

官网解释

Qt::ConnectionType

跨线程的信号和槽
Qt支持这些信号槽的连接方式：

  1. Auto Connection(默认): 假如信号在一个接收者的线程中发射，则行为等同于 Direct Connect. 否则行为等同于Queued Connection.
  2. Direct Connect: 当信号被发射，槽函数将会被立即调用。槽函数将会在发射者的线程中执行, 而不一定在接收者线程中执行。
  3. Queued Connect: 槽函数在控制权返回到接收者线程的事件循环时被调用。槽函数在接收者线程中被执行。
  4. Blocking Queued Connection: 槽函数除了阻塞当前线程直到槽函数返回，其他像Queued Connection一样被调用。备注：在同一线程中使用这个类型的connect会导致死锁。
  5. Unique Connect: 这个行为等同于Auto Connection，但是这个connection是只能在现有连接不重复的情况下生效。假如相同的信号已经连接到相同的槽函数中，这个连接不会建立且connect()返回false。
  • 连接的类型可以通过connect()额外的参数指定，注意：在发送者和接收者在不同线程中使用direct connect是不安全的。如同一个事件循环在接收者的线程中，在另一个线程中调用存活对象的任何函数是不安全的。
  • QObject::connect() 它本身是线程安全的。

在使用Queue Connection的时候，参数必须是Qt 元对象系统已知的类型，因为Qt需要拷贝入参并保存在事件背后的场景。假如你使用Queue Connection并得到以下错误信息：

QObject::connect: Cannot queue arguments of type ‘MyType’

在connection建立之前，调用qRegisterMetaType()去注册数据类型。

Posted on Edited on 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
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
#include <iostream>

template <typename T>
class queue {
 public:
  queue(size_t size) : size_(size), front_(0), end_(0) { data_ = new T[size]; }
  ~queue() { delete[] data_; }
  queue(const queue& other) = delete;
  queue(queue&& other) = delete;
  queue operator=(const queue& other) = delete;
  queue operator=(queue&& other) = delete;

  bool is_empty() { return front_ == end_; }
  bool is_full() { return front_ = (end_ + 1) % size_; }

  const T& front() const { return data_[front_]; }

  void push(const T& val) {
    if ((end_ + 1) % size_ != front_) {
      data_[end_] = val;
      end_ = (end_ + 1) % size_;
    }
  }

  void pop() {
    if (front_ != end_) {
      front_ = (front_ + 1) % size_;
    }
  }

 private:
  size_t front_;
  size_t end_;
  size_t size_;
  T* data_;
};

int main() {
  queue<int> q(5);
  q.push(1);
  q.push(2);
  q.push(3);
  q.push(4);
  q.push(5);
  q.pop();
  q.pop();
  q.push(6);
  q.push(7);
  q.push(8);
  while (!q.is_empty()) {
    std::cout << q.front() << std::endl;
    q.pop();
  }
  return 0;
}

不采用哨兵值，使用状态来实现

spdlog 循环队列实现

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
98
99
100
template <typename T>
class circular_q {
  size_t max_items_ = 0;
  typename std::vector<T>::size_type head_ = 0;
  typename std::vector<T>::size_type tail_ = 0;
  size_t overrun_counter_ = 0;
  std::vector<T> v_;

 public:
  using value_type = T;

  // empty ctor - create a disabled queue with no elements allocated at all
  circular_q() = default;

  explicit circular_q(size_t max_items)
      : max_items_(max_items + 1)  // one item is reserved as marker for full q
        ,
        v_(max_items_) {}

  circular_q(const circular_q &) = default;
  circular_q &operator=(const circular_q &) = default;

  // move cannot be default,
  // since we need to reset head_, tail_, etc to zero in the moved object
  circular_q(circular_q &&other) noexcept {
    copy_moveable(std::move(other));
  }

  circular_q &operator=(circular_q &&other) noexcept {
    copy_moveable(std::move(other));
    return *this;
  }

  // push back, overrun (oldest) item if no room left
  void push_back(T &&item) {
    if (max_items_ > 0) {
      v_[tail_] = std::move(item);
      tail_ = (tail_ + 1) % max_items_;

      if (tail_ == head_)  // overrun last item if full
      {
        head_ = (head_ + 1) % max_items_;
        ++overrun_counter_;
      }
    }
  }

  // Return reference to the front item.
  // If there are no elements in the container, the behavior is undefined.
  const T &front() const { return v_[head_]; }

  T &front() { return v_[head_]; }

  // Return number of elements actually stored
  size_t size() const {
    if (tail_ >= head_) {
      return tail_ - head_;
    } else {
      return max_items_ - (head_ - tail_);
    }
  }

  // Return const reference to item by index.
  // If index is out of range 0…size()-1, the behavior is undefined.
  const T &at(size_t i) const {
    assert(i < size());
    return v_[(head_ + i) % max_items_];
  }

  // Pop item from front.
  // If there are no elements in the container, the behavior is undefined.
  void pop_front() { head_ = (head_ + 1) % max_items_; }

  bool empty() const { return tail_ == head_; }

  bool full() const {
    // head is ahead of the tail by 1
    if (max_items_ > 0) {
      return ((tail_ + 1) % max_items_) == head_;
    }
    return false;
  }

  size_t overrun_counter() const { return overrun_counter_; }

 private:
  // copy from other&& and reset it to disabled state
  void copy_moveable(circular_q &&other) noexcept {
    max_items_ = other.max_items_;
    head_ = other.head_;
    tail_ = other.tail_;
    overrun_counter_ = other.overrun_counter_;
    v_ = std::move(other.v_);

    // put &&other in disabled, but valid state
    other.max_items_ = 0;
    other.head_ = other.tail_ = 0;
    other.overrun_counter_ = 0;
  }
};

Posted on Edited on 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
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
98
99
#include <algorithm>
#include <atomic>
#include <cassert>
#include <iostream>
#include <map>
#include <mutex>
#include <vector>

class Container {
 public:
  Container() {
      std::lock_guard<std::mutex> lock(mut);
      auto it = uuid.load();
      uuid.store(++it);
      serial_number_ = it;
      container_map.insert({ serial_number_, this });
  }

  virtual int get_fluid_capacity() = 0;

  friend int totalFluidCapacity() {
    std::lock_guard<std::mutex> lock(mut);
    int result = 0;
    for (auto& it : container_map) {
      result += it.second->get_fluid_capacity();
    }
    return result;
  }

  friend Container* find_container(size_t serial_number) {
    std::lock_guard<std::mutex> lock(mut);
    if(container_map.find(serial_number) != container_map.end()) {
      return container_map[serial_number];
    } else {
      return nullptr;
    }
  }
  inline static std::mutex mut;
  inline static std::atomic<size_t> uuid;
  inline static std::map<size_t, Container*> container_map;

 protected:
  size_t serial_number_;
};

int totalFluidCapacity();
Container* find_container(size_t serial_number);

class Buckets : public Container {
  static constexpr double pi = 3.1415926;

 public:
  Buckets(int height, int radius) : height_(height), radius_(radius) {}
  virtual int get_fluid_capacity() override final {
    return static_cast<int>(radius_ * radius_ * height_ * pi);
  }

 private:
  int height_;
  int radius_;
};

class Boxes : public Container {
 public:
  enum class material_type : int {
    m = 0,  /// for metal
    c = 1,  /// for cardboard
  };

  Boxes(const int length, const int width, const int height, material_type type)
      : length_(length), width_(width), height_(height), type_(type) {}
  virtual int get_fluid_capacity() override final {
    if (type_ == material_type::c) {
      return length_ * width_ * height_;
    } else {
      return 0;
    }
  }

 private:
  int length_;
  int width_;
  int height_;
  material_type type_;
};

int main() {
  Boxes box_c(1, 1, 1, Boxes::material_type::c);
  Boxes box_m(1, 1, 1, Boxes::material_type::m);

  Buckets bucket(1, 1);

  auto capa = totalFluidCapacity();
  assert(capa == 4);

  auto p_container = find_container(2);
  assert(p_container == & box_m);
  return 0;
}

Posted on Edited on In

C++序列化与反序列化二叉树

首先我们定义树节点的数据结构

1
2
3
4
5
6
struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

序列化函数

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
inline std::string serialize(TreeNode* root) {
  if (root == nullptr) {
    return "null";
  }
  std::vector<TreeNode*> queue;
  std::vector<std::vector<std::string>> result;
  queue.push_back(root);
  int height = 0;
  while (!queue.empty() &&
    !std::all_of(queue.begin(), queue.end(),
      [](const TreeNode* node) { return node == nullptr; })) {
    std::vector<std::string> temp;
    int count = static_cast<int>(std::pow(2, height));
    while (count-- != 0) {
      auto front = queue.front();
      queue.erase(queue.begin());
      if (front == nullptr) {
        temp.push_back("null");
        queue.push_back(nullptr);
        queue.push_back(nullptr);
      }
      else {
        temp.push_back(std::to_string(front->val));
        queue.push_back(front->left);
        queue.push_back(front->right);
      }
    }
    result.push_back(temp);
    ++height;
  }

  std::string str = "[";
  /// 组装字符串
  for (auto& it : result) {
    for (auto& it1 : it) {
      str += it1 + ",";
    }
  }
  if (str.back() == ',') {
    str.erase(std::prev(str.end()));
    str += "]";
  }
  return str;
}

反序列化函数

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
inline void split(const std::string& s, std::vector<std::string>& tokens,
  const std::string& delimiters = " ") {
  std::string::size_type lastPos = s.find_first_not_of(delimiters, 0);
  std::string::size_type pos = s.find_first_of(delimiters, lastPos);
  while (std::string::npos != pos || std::string::npos != lastPos) {
    tokens.push_back(s.substr(lastPos, pos - lastPos));
    lastPos = s.find_first_not_of(delimiters, pos);
    pos = s.find_first_of(delimiters, lastPos);
  }
}
// Decodes your encoded data to tree.
inline TreeNode* deserialize(std::string data) {
  if (data.front() != '[' || data.back() != ']') {
    return nullptr;
  }
  data.erase(data.begin());
  data.erase(std::prev(data.end()));
  std::vector<std::string> vec_str;
  split(data, vec_str, ",");
  if (vec_str.empty() || vec_str.front() == "null") {
    return nullptr;
  }

  std::vector<TreeNode*> result;
  for (const auto& it : vec_str) {
    if (it == "null") {
      result.push_back(nullptr);
    }
    else {
      result.push_back(new TreeNode(std::stoi(it)));
    }
  }

  for (size_t i = 0; i < result.size(); ++i) {
    if(result.at(i) != nullptr){
      if (result.size() > i * 2 + 2) {
      result.at(i)->left = result.at(i*2+1);
      result.at(i)->right = result.at(i*2+2);
      }
    }
  }

  return result.at(0);
}

例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <cassert>

int main(){

  auto result = deserialize("[5,null,7,null,null,6,8]");
  assert(serialize(result) == "[5,null,7,null,null,6,8]");

  auto string =
      "[0,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,98,"
      "99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,"
      "117,118,119,120,121,122,123,124,125,126]";
  auto result3 = deserialize(string);
  assert(serialize(result3) == string);
}

序列化改进版

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
 public:
  // Encodes a tree to a single string.
  string serialize(TreeNode* root) {
    std::string res = "[";
    std::queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
      auto temp = q.front();
      q.pop();
      if (temp == nullptr) {
        res += "null,";
      } else {
        res += std::to_string(temp->val) + ",";
        q.push(temp->left);
        q.push(temp->right);
      }
    }
    res += "]";
    return res;
  }

  // Decodes your encoded data to tree.
  TreeNode* deserialize(string data) {
    /// 去除首尾的'[]'
    data.erase(data.begin());
    data.erase(std::prev(data.end()));
    /// 把字符串解析成数组
    auto begin = 0;
    auto lastPos = data.find_first_not_of(',', 0);
    auto pos = data.find_first_of(',', lastPos);
    std::queue<std::string> q;
    while (pos != std::string::npos || std::string::npos != lastPos) {
      q.push(data.substr(lastPos, pos - lastPos));
      lastPos = data.find_first_not_of(',', pos);
      pos = data.find_first_of(',', lastPos);
    }
    /// 遍历数组建立树
    auto head = q.front();
    std::queue<TreeNode*> q_ceng;
    std::queue<TreeNode*> q_next_ceng;
    TreeNode* r = nullptr;
    if (head != "null") {
      auto thead = new TreeNode(std::atoi(head.c_str()));
      q_ceng.push(thead);
      r = thead;
    }
    q.pop();
    while (!q.empty()) {
      while (!q_ceng.empty()) {
        auto t = q_ceng.front();
        q_ceng.pop();
        auto l_t = q.front();
        q.pop();
        auto r_t = q.front();
        q.pop();
        if (l_t != "null") {
          t->left = new TreeNode(std::atoi(l_t.c_str()));
          q_next_ceng.push(t->left);
        }
        if (r_t != "null") {
          t->right = new TreeNode(std::atoi(r_t.c_str()));
          q_next_ceng.push(t->right);
        }
      }
      while (!q_next_ceng.empty()) {
        q_ceng.push(q_next_ceng.front());
        q_next_ceng.pop();
      }
    }
    return r;
  }
};