数据结构

字数

3187 字

阅读时间

16 分钟

• https://golang.org/doc/code
• https://tour.golang.org/

一、初始化

1. 常量

type ByteSize float64

const (
    _            = iota //  iota 是枚举器（0 开始，每行+1），用 _ 忽略第一个值
    KB ByteSize  = 1 << (10 * iota)
    MB
    GB
)

2. 变量

x := 10

var (
    home = os.Getenv("HOME")
    user = os.Getenv("USER")
)

• 如果左边多个变量，可以有已经定义过的变量（同一作用域里），但必须至少有一个是未定义过的。对于已经定义过的变量就是赋值操作。

var err error.Error
res, err := get()

• 如果是在全局区域，只能用 var 初始化，不能用 :=。

3. 包

• 会让可读性变差、带来意料之外的副作用。
• 最好是提供相应初始化函数给调用者来避免使用init。
• 避免I/O调用（单元测试时不希望有）、避免依赖其它的 init() 函数、避免修改全局函数、环境状态。

func init() {
    这里执行的代码会在当前包被 import 时执行。
}

二、数据

1. 基本类型

• int int8 int16 int32 int64
• uint uint8 uint16 uint32 uint64 uintptr
• bool string byte(uint8别名) rune(int32 别名)
• float32 float64 complex64 complex128

2. 结构体

// 这样初始化拿到的是该类型的零值的指针，里面每个属性都是对应类型的零值
f := &File{} 或 f := new(File)
f.fd = fd
f.name = name

// 填写每个属性
f := &File{fd, name, nil, 0}

// 通过 label 可以只赋值部分属性
f := &File{fd: fd, name: name}

4. Embedding Struct (嵌入结构体)

嵌入的结构体的字段会被提升到外层结构体。

type Reader interface {
    Read(p []byte) (n int, err error) 
}

type Writer interface {
    Write(p []byte) (n int, err error) 
}

type ReadWriter interface {
    Reader
    Writer 
}

// 使用时
var rw ReadWriter
rw = os.Stdout
rw.Read([]byte{})

嵌入的结构体可以有相同的字段名，这样访问时会有歧义，需要使用完整的路径。

type Cat struct {
    Name string
    Weight int
    Food []string 
}

func (c *Cat) Meow() {
    fmt.Println(c.Name + ": Meow")
}

type Dog struct {
    Name string
    Weight int
    Food []string 
}

type Animal struct {
    Cat
    Dog 
}

a := Animal{Cat: Cat{Name: "cat"}, Dog: Dog{Name: "dog"}}
a.Cat.Name = "Tom"
a.Dog.Name = "Doo"
// 使用只有 Cat 有的方法时，可以忽略 Cat
a.Meow() // 等价 a.Cat.Meow()

3. array 和 slice

1. array 的定义方式

a := [100]int{}
var b [10]int
c := [...]int{1, 2, 3}

2. slice 的定义方式

s := make([]int, 100)
var nums []float

3. 二维数组/切片

var s [][]byte

// 定义了一个 5 行 8 列的数组
picture := make([][]uint8, 5)
for i := range picture {
    picture[i] = make([]uint8, 8)
}

4. 切片的内存布局

切片的底层结构是一个结构体，包含一个指向底层数组的指针，一个长度和一个容量。

var a = []int{1, 2, 3}
var b = a[1:]
b[0] = 4 // a = [1, 4, 3], b = [4, 3]

5. 整体赋值

// 数组整体赋值是拷贝
a := [1]int{1}
b := a // 此时 a 和 b 不是同一个数组
b[0] = 2 // a = [1], b = [2]

// slice 的整体赋值是指向同一个底层数组
s := []int{1}
t := s
t[0] = 2 // s = [2], t = [2]

6. 切片操作

起点可以省略，不能像 python 一样用负数。切片底层指向同一块空间。

s := a[1:3]
prefix := str[:len(str)-10]

7. 完整的切片表达式

代表容量（cap）为 max-low，容量会影响 append 操作的具体实现。字符串不适用。

a[low : high : max]

8. make

// slice 的初始化，会有一个容量是 cap，有 len 个 0 （int 的零值）的 int 数组。
s := make([]int, len, cap)

// len 和 cap 相等时可以忽略 cap，这样更简洁
s := make([]int, len)

// map 的初始化
m := make(map[string]string, cap)

• 对于最大长度确定的时候，初始化 len，通过下标修改值，会比 append 更高效。

9. append

// append slice。数组不能 append。
func append(slice []T, elements ...T) []T

// 可以 append 多个
s = append(s, 0, 1, 2)

// append 后 len 就是原来的 len 加上新元素个数。
// 扩容逻辑：cap < 1024时，会翻倍增长，否则 1.25 倍。
var s []int
s = append(s, 0) // len 是 1, cap 是 1
s = append(s, 1) // len 是 2, cap 是 2
s = append(s, 2) // len 是 3, cap 是 4
fmt.Println(s) // [0, 1, 2]


func modifySlice(s []int) {
    s = append(s, 3)
    s[0] = -1
}

// 函数都是传值的，slice 的数据结构里包含指向数组的指针、len、cap。
modifySlice(s)
fmt.Println(s) // [-1, 1, 2]，append 修改了 cap 和 len 不会作用在这里的 s

10. 切片的拷贝

// 切片的拷贝是浅拷贝，指向同一块底层数组。
a := []int{1, 2, 3}
b := a
b[0] = 2 // a = [2, 2, 3], b = [2, 2, 3]

// 切片的拷贝是深拷贝，指向不同的底层数组。
a := []int{1, 2, 3}
b := make([]int, len(a))
copy(b, a)
b[0] = 2 // a = [1, 2, 3], b = [2, 2, 3]

4. map

1. 定义与使用

var timeZone = map[string]int{
    "UTC": 0,
    "CST": -6,
    "PST": -8,
}

timeZone["MST"] // 0，不存在的 key，会得到 value 类型的零值。
t, ok := timeZone["MST"] // 会得到 0, false
if _, ok := timeZone["MST"]; ok { // 如果只是判断是否存在

delete(timeZone, "UTC") // 删除某个 key

2. Map 的 value 存的是值，会发生 copy，所以一般用指针类型。
3. Map 的 key 不应用指针类型，否则值相同也是不同 key。
4. slice、function、map 类型不能作为 map 的 key。
5. 不能对 map 的 value 进行取地址，因为一扩容地址就变了。

&timeZone["UTC"] // 是错误的, cannot take address of timeZone["UTC"]

6. 不能对 map 的值的字段修改，除非是指针类型。

myMap := map[string]Point{"origin": {x: 0, y: 0}}
myMap["origin"].x = 3 // 是错误的。cannot assign to struct field .. in map

myMap := map[string]*Point{"origin": {x: 0, y: 0}}
myMap["origin"].x = 1 // 是可以的

7. map 不支持并发读写，只能并发读。并发写回强行退出程序，抛出 fatal error: concurrent map read and map write。
8. 删除 key 时，Map 不会自动缩容，需要设置为 nil，或是手动调用 gc。

runtime.GC()

9. 避免在map 的值中引用大数组

name := "/path/to/file"
data, _ := ioutil.ReadFile(name)
myMap[name] = data[:10] // Bad：data 不会被回收
myMap[name] = append([]byte{}, data[:10]...) //  Good：data 会被回收

用 map 实现 set

Go 中没有集合，可以用 map 实现，并用struct{} 作为值，因为它被编译器优化过，指向同一个内存地址，不额外占空间。

type MySet map[int]struct{}

func (s MySet) Add(num int) {
    if s == nil {
        s = make(MySet)
    }
    s[num] = struct{}{}
}

set := MySet{}
set.Add(1)

5. string

1. 底层实现是一个指向数据的指针和一个长度字段。
2. String 和 []byte 直接做类型转换会进行拷贝。
3. 中文的 string 切片或获取长度时应转为 []rune 再使用。

三、结构

1. if

如果只是 if 里用的变量，尽量写在 if 的初始化里，代码看起来更简洁

if r, ok := dst.(ReaderFrom); ok {
   return r.ReadFrom(src)
}

2. for 循环

for init; condition; post {}

// 相当于 while
for condition {}

// 相当于 for(;;)
for {}

// 可以这样初始化、改变多个变量，但是不能像 C++ 里用`,`划分多个语句。
for i, j := 0, len(a) - 1; i < j; i, j = i+1, j-1 {
    a[i], a[j] = a[j], a[i]
}

// 遍历的是 key
for x := range myMap {}

// 遍历的是 value
for _, v := range myMap {}

// 遍历的是 index
for x := range mySlice {}

// 遍历的是 value
for _, v := range mySlice {}

3. switch

1. 可以不根据某个变量的值进行选择，而是从上到下找到第一个为真的表达式

func unhex(c byte) byte {
    switch {
    case '0' <= c && c <= '9':
        return c - '0'
    case 'a' <= c && c <= 'f':
        return c - 'a' + 10
    case 'A' <= c && c <= 'F':
        return c - 'A' + 10
    }
    return 0
}

2. 不会像 C++ 一样自动进入下一个 case，如果需要可以用 fallthrough 关键字，或者

switch c {
case ' ', '?', '&':
    f(c)
}

3. 使用 label 跳出循环（适用于 for 循环里的 switch、select 代码块）

Loop:
    for {
        r, size := decode(s[i:])
        switch {
        case size == 1 && r == invalidMsg:
            return "", fmt.Errorf("invalid: %q", s) // %q 带双引号

        case size == 0:
            // 跳出 for 循环
            break Loop

        default:
            result += r
        }
        i += size
    }

4. interface{} 的类型判断

func f(x int) interface{} {
    switch x {
    case 1:
        return 1
    case 2:
        return "1"
    }
    return nil
}

t = f(1)
switch t := t.(type) {
default:
    fmt.Printf("unexpected type: %T\n", t)
case int:
    fmt.Printf("integer %d\n", t)
case string:
    fmt.Printf("string %s\n", t)
}
}

四、函数

1. 返回多个值

多个返回值需要用括号括起来。 返回值可以有名字，初始值为类型的零值。return 可后面不加内容。

func Cut(s, sep []byte) (before, after []byte, found bool) {
        if i := Index(s, sep); i >= 0 {
                return s[:i], s[i+len(sep):], true
        }
        return s, nil, false
}

2. 闭包

1. 引用了函数体外面的变量的函数。也就是这些变量和该函数绑定在一起。

func adder() func(int) int {
    sum := 0
    return func(x int) int {
        sum += x
        return sum
    }
}

pos, neg = adder(), adder()
for i := 0; i < 10; i++ {
    fmt.Println(pos(i), net(-i))
}

2. for 循环里用闭包的坑(govet 会检测出来）

for i := 0; i < 100; i++ {
    go func() {
        fmt.Println(i)
    }()
}
select{} // 阻塞

会得到100 个 0-100 中的任意数字。应该改为

go func(num int) {
    fmt.Println(num)
}(i) // 将变量拷贝传进函数

会得到 0-100 的某个排列

另一种方法是

for i := 0; i < 100; i++ {
    ii := i // 局部变量逃逸，指的是编译器会根据实际使用域决定放堆上还是栈上。这里会放到堆上。
    go func() {
        fmt.Println(ii)
    }()
}

3. defer

1. 常用来解锁、关闭连接、关闭文件描述符、recover panic。

// Contents returns the file's contents as a string.
func Contents(filename string) (string, error) {
    f, err := os.Open(filename)
    if err != nil {
        return "", err
    }
    defer f.Close()  // Close 应该放到 err 判断后面，否则会 panic

    var result []byte
    buf := make([]byte, 100)
    for {
        n, err := f.Read(buf[0:])
        result = append(result, buf[0:n]...) // append is discussed later.
        if err != nil {
            if err == io.EOF {
                break
            }
            return "", err  // f will be closed if we return here.
        }
    }
    return string(result), nil // f will be closed if we return here.
}

2. 按栈的顺序，先进后出。
3. 预计算参数

func f() {
    startedAt := time.Now()
 
    // 这样会立刻计算出函数用到的参数并进行拷贝，而不是执行 defer 时才计算。
    defer fmt.Println("假执行时间: ", time.Since(startedAt))
    
    // 利用闭包。这样拷贝的是函数指针。退出函数 f 时才计算。
    defer func() { fmt.Println("真执行时间: ", time.Since(startedAt)) }()
        
    time.Sleep(time.Second)
}

4. 注意 defer 属于哪个函数

func f() {
    for {
        func(..) {
            row, err := db.Query("...")
            if err != nil {
                ..
            }
            defer row.Close() // 这样会在内层函数退出时就执行
            ..
        }(..)
    }
}

4. 函数类型参数

func compute(f func(float64, float64) float64) float64 {
    return f(3, 4)
}

add := func(x, y float64) float64 {
    return math.Sqrt(x*x + y*y)
}

compute(add)

五、方法

1. 结构体的方法

可以给结构体定义方法。接收者可以用值或指针。

// 不修改函数接收者时，用值作为函数接收者
func (r Response) Code() int {
    return r.code
}

// 修改时，用指针。但是有时为了统一写法，就都用指针。
func (r *Response) SetCode(code int) {
    r.code = code
}

// 使用值接收者的函数可以被指针、值调用。而指针接收者只能被指针调用。
var r *Response
r.SetCode(1)
r.Code()

2. Sringers

为结构体实现 String 方法，方便打印，尤其是带有指针成员的结构体。

type Point struct {
    x, y int
}

func (p *Point) String() string {
    return fmt.Sprintf("(%d, %d)", p.x, p.y)
}

myMap := map[string]*Point{"origin": {x: 0, y: 0}}
fmt.Printf("%s", myMap)

六、接口（Interfaces）

1. 定义接口

type Writer interface {
  
}

2. 一个类型可以实现多个接口。

如下是实现 sort.Interface 接口，需要实现 Len(), Less(), Swap() 函数

type Sequence []int

// Methods required by sort.Interface.
func (s Sequence) Len() int {
    return len(s)
}
func (s Sequence) Less(i, j int) bool {
    return s[i] < s[j]
}
func (s Sequence) Swap(i, j int) {
    s[i], s[j] = s[j], s[i]
}

// Copy returns a copy of the Sequence.
func (s Sequence) Copy() Sequence {
    copy := make(Sequence, 0, len(s))
    return append(copy, s...)
}

// Method for printing - sorts the elements before printing.
func (s Sequence) String() string {
    s = s.Copy() // Make a copy; don't overwrite argument.
    
    sort.Sort(s)
    // 也可以直接 sort.IntSlice(s).Sort()，就不用自己实现接口了。
    
    return fmt.Sprint([]int(s))
}

七、泛型

1. 泛型函数

func Index[T comparable](s []T, x T) int {
    for i, v := range s {
        // v and x are type T, which has the comparable
        // constraint, so we can use == here.
        if v == x {
            return i
        }
    }
    return -1
}

2. 泛型类型

type List[T any] struct {
    next *List[T]
    val  T
}

贡献者

间歇收拾癖

页面历史

最后编辑于 21 天前

查看完整历史

eda715d-chore: change order

f697f06-doc(go-design): 新增数据结构、并发、CI/CD 等文档

9801640-doc(go-standard): 添加了Go风格规范，制定25年规划等