吃透 Golang 基础：数据结构之 Struct

吃透 Golang 基础：数据结构之 Struct

结构体的声明

结构体是聚合类型，是由零个或多个任意类型的值聚合而成的实体。每个值称为结构体的成员。

下例声明了一个名为 Employee 的结构体类型，并定义了一个 Employee 类型的变量：

type Employee struct {ID 			intName 		stringAddress 	stringDoB 		time.TimePosition 	stringSalary 		intManagerID 	int
}var dilbert Employee

在结构体定义时，如果两个相邻成员的类型是相同的，那么它们可以被合并到一行，比如：

type Employee struct {ID            intName, Address stringDoB           time.TimePosition      stringSalary        intManagerID     int
}

一个重要的性质是： 结构体成员的输入顺序有重要的意义。在定义时，如果定义的结构体成员的顺序不一致，那么我们定义的就是两个不同的结构体（相当于结构体定义的成员顺序也是标识结构体类型的因素之一，就像是长度不相等的数组不是同一类型的数组）。

如果结构体成员的名字以大写字母开头，那么该成员就是导出的，它对其他包可见。一个结构体可以同时包含导出和未导出的成员，结构体自身也可以是导出或未导出的。

通常，一个名为 S 的结构体的成员不能重复包含值类型的 S，但是可以包含一个 S 类型的指针，最常见的应用场景是链表（需要 next/prev 指针）、二叉树（需要 left/right 指针）等数据结构的定义。

点运算符

可以通过点访问符.来访问结构体变量当中的成员，比如dilbert.Name和dilbert.DoB。需要注意的是，dilbert及其成员都是变量，因此可以直接修改dilbert的值。

dilbert.Salary -= 5000

由于结构体变量及变量包含的成员都是变量，故我们不仅可以建立针对dilbert的指针，还可以建立针对dilbert成员的指针。

position := &dilbert.Position
*position = "Senior" + *position

Golang 有一个语法糖，那就是点运算符可以直接作用在结构体类型的指针变量上，以直接访问指针所指向变量的成员，一个例子如下：

var employeeOfTheMonth *Employee = &dilbert
employeeOfTheMonth.Position += " (proactive team player)"// 等价于
(*employeeOfTheMonth).Position += " (proactive team player)"

深入探讨结构体的初始化

定义一个结构体类型之后，可以通过结构体字面值初始化一个结构体变量：

type Point struct { X, Y int }p := Point{1, 2}// 等价于
p := Point{}
p.X, p.Y = 1, 2

上面这种写法需要我们明确知道结构体每个成员的类型和顺序，另一种写法是以成员的名字和相应的值来进行初始化，可以包含全部或部分的成员（未被包含的成员将直接赋零值）：

type Point struct { X, Y int }p := Point{X: 1, Y: 2}

上述两种写法不能混用。

结构体与函数

结构体可以作为函数的参数或返回值，下例通过Scale函数将Point类型的值缩放后返回：

func Scale(p Point, factor int) Point {return Point{p.X * factor, p.Y * factor}
}fmt.Println(Scale(Point{1, 2}, 5)	// "{5, 10}"

考虑效率的话，针对较大的结构体，可以通过指针的方式传入并返回（Golang 的函数默认只有传值调用，因此传递一个值作为实参到函数当中，函数会复制一个相同的变量，而不是引用。传指针需要注意潜在的内存逃逸问题，在对象频繁创建和删除的场景下，如果函数的返回值是指针，将会导致局部变量从栈逃逸到堆上，从而增加 GC 的开销，影响性能。一般情况下，对于需要修改原对象的值或是传递占用内存较大的结构体时，才选择传指针。对于只读的占用内存较小的结构体，直接传值的性能更好）。

由于结构体通常通过指针处理，下面的写法会创建并初始化一个结构体变量，并返回结构体的地址：

pp := &Point{1, 2}

上述语句等价于：

pp := new(Point)	// new 函数对所有变量通用, 它创建一块该变量的地址并返回其指针
*pp = Point{1, 2}

结构体比较

如果结构体的全部成员都是可比较的，那么结构体本身也是可比较的，也就是可以使用==和!=进行比较：

type Point { X, Y int }p := Point{1, 2}
q := Point{2, 1}fmt.Println(p == q)	// "false"

可比较的结构体和其他可比较的类型一样，可以用作 Map 的 Key，这样 Map 就可以通过==和!=判断当前 Key 是否存在：

type address struct {hostname stringport 	 int
}hits := make(map[address]int)
hits[address{"yggp", 443}] ++

结构体嵌入与匿名成员

这一部分是结构体当中比较重要的知识，这几天学习设计模式的过程中频繁见到结构体嵌入的写法。

需要事先重复强调的是，Golang 没有继承，而 Go 当中 struct 的嵌入可以被视为“继承”的一种方式，但从语法上来说确实不是继承，可以视为“组合”。

下例实现了一个简单的二维绘图程序库，定义了两个结构体：

type Circle struct {X, Y, Radius int
}type Wheel struct {X, Y, Radius, Spokes int
}

显然 Wheel 当中完全包含了 Circle 的重复成员，且 Circle 的成员可以进一步抽象成Point结构。因此我们对上述定义进行修改：

type Point struct {X, Y int
}type Circle struct {Center PointRadius int
}type Wheel struct {Circle CircleSpokes int
}

经过上述改动，结构体之间的嵌套关系非常清晰，但是想要修改具体的成员仍然非常麻烦：

var w Wheel
w.Circle.Center.X = 8
w.Circle.Center.Y = 8
w.Circle.Radius = 5
w.Spokes = 20

Go 的特性使得我们可以在结构体定义时只声明一个成员对应的数据类型，而不需要明确指出该成员的变量名，这类成员就是匿名成员。匿名成员的数据类型必须是命名的类型或指向一个命名的类型的指针。下例是对之前非匿名嵌入的改写：

type Point struct {X, Y int
}type Circle struct {PointRadius int
}type Wheel struct {Circle Spokes int
}var w Wheel
w.X = 8            // equivalent to w.Circle.Point.X = 8
w.Y = 8            // equivalent to w.Circle.Point.Y = 8
w.Radius = 5       // equivalent to w.Circle.Radius = 5
w.Spokes = 20

针对包含匿名嵌入的结构体，通过字面值初始化结构体的时候必须遵循结构体声明时的结构，以下是通过字面值初始化结构体的例子：

w := Wheel{Circle{Point{8, 8}, 5}, 20}
m := Wheel{Circle: Circle{Point: Point{X: 8, Y: 8},Radius: 5,},Spokes: 20,
}

需要注意的是，如果在包内定义了匿名嵌入了的结构体，且嵌入的子结构体是非导出的，那么在包外将不能直接访问匿名嵌入的子结构体的成员。

LRU Cache：综合使用 struct 和 map 的例子

下面我们以 LeetCode 146. LRU Cache 这道经典的题目为例，综合使用一下 Golang 当中的 struct 与 map 数据结构。

type Node struct {key, val   intnext, prev *Node
}func newNode(_key, _val int) Node {return Node{key: _key, val: _val, next: nil, prev: nil}
}type LRUCache struct {cache           map[int]*Nodehead, tail      *Nodecapacity, size  int
}func Constructor(_capacity int) LRUCache {var lru_cache LRUCachelru_cache.cache = map[int]*Node{}lru_cache.capacity, lru_cache.size = _capacity, 0lru_cache.head, lru_cache.tail = new(Node), new(Node)lru_cache.head.next, lru_cache.tail.prev = lru_cache.tail, lru_cache.headreturn lru_cache
}func (this *LRUCache) Get(key int) int {if node, ok := this.cache[key]; !ok {return -1} else {this.moveToHead(node)return node.val}
}func (this *LRUCache) Put(key int, value int)  {if node, ok := this.cache[key]; !ok {new_node := newNode(key, value)this.cache[key] = &new_nodethis.addToHead(&new_node)this.size ++if this.size > this.capacity {t := this.removeTail()delete(this.cache, t.key)this.size --}} else {this.moveToHead(node)node.val = value}
}func (this *LRUCache) addToHead(node *Node) {node.next = this.head.nextnode.next.prev = nodethis.head.next = nodenode.prev = this.head
}func (this *LRUCache) removeNode(node *Node) {node.next.prev = node.prevnode.prev.next = node.next
}func (this *LRUCache) moveToHead(node *Node) {this.removeNode(node)this.addToHead(node)
}func (this *LRUCache) removeTail() *Node {t := this.tail.prevthis.removeNode(t)return t
}/*** Your LRUCache object will be instantiated and called as such:* obj := Constructor(capacity);* param_1 := obj.Get(key);* obj.Put(key,value);*/