1.数组
数组是值类型
[10]int 和 [20]int是不同类型
调用func(arr [10]int)会拷贝数组
在go语言中一般不直接使用数据
|
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 mainimport "fmt"func updatearr(arr *[5]int) { arr[0] = 100}func updatearrthroughslice(arr []int) { arr[0] = 100}func main() { //创建一个数据 var arr [5]int arr2 := [5]int{1, 2, 3, 4, 5} //长度让编译器来数 arr3 := [...]int{1, 2, 3, 4, 5} //[0 0 0 0 0] [1 2 3 4 5] [1 2 3 4 5] fmt.println(arr, arr2, arr3) //定义二维数组 4行5列 var arr4 [4][5]int //[[0 0 0 0 0] [0 0 0 0 0] [0 0 0 0 0] [0 0 0 0 0]] fmt.println(arr4) //遍历数据 //for i:=0;i<len(arr3);i++{ // fmt.println(arr3[i]) //} for num, v := range arr2 { fmt.printf("第%d个元素为:%d\n", num, v) } //数据是值类型,通过指针可以改变值的大小 fmt.println("update before") fmt.println(arr2) updatearr(&arr2) //传入arr3的地址 fmt.println("update after") fmt.println(arr2) //通过slice改变数据 fmt.println("update before") fmt.println(arr3) updatearrthroughslice(arr3[:]) //传入slice fmt.println("update after") fmt.println(arr3)} |
2.slice(切片)
2.1 slice的实现
slice本身没有数据,是对底层array的一个view
slice内部有个指针(ptr)指向开头的元素,slice有长度(len),容量(cap);cap代表从指针(ptr)开始到数组(arr)末尾的长度,slice在扩展的时候不能超过cap.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
package mainimport "fmt"func updateslice(s []int) { s[0] = 100}func main() { arr := [...]int{0, 1, 2, 3, 4, 5, 6, 7} //创建一个slice s1 := arr[:] s2 := arr[2:6] fmt.printf("s1:%v\ns2:%v\n", s1, s2) //改变slice内部元素 updateslice(s2) fmt.println(s2) //reslice:对slice再进行一次slice操作 s3 := s1[:5] fmt.println(s3) s3 = s3[:2] fmt.println(s3)} |
s[i]不可以超越len(i),向后扩展不可以超过底层数组cap(s)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
package mainimport "fmt"func updateslice(s []int) { s[0] = 100}func main() { arr := [...]int{0, 1, 2, 3, 4, 5, 6, 7} fmt.printf("arr=%v\n", arr) //extending slice 不能超过cap(s) s1 := arr[2:6] fmt.printf("s1=%v, len(s1)=%d, cap(s1)=%d\n", s1, len(s1), cap(s1)) s2 := s1[3:5] fmt.printf("s2=%v, len(s2)=%d, cap(s2)=%d\n", s2, len(s2), cap(s2)) // s[i]不能超过len(s) fmt.printf("get slice element:%v",s2[1]) //panic: runtime error: index out of range [2] with length 2 //fmt.printf("get slice element:%v",s2[2])} |
向slice添加元素
|
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
|
package mainimport "fmt"//查看操作系统怎么扩充slice的capfunc printslice(s []int) { fmt.printf("%v, len=%d, cap=%d\n", s, len(s), cap(s))}func main() { arr := [...]int{0, 1, 2, 3, 4, 5, 6, 7} //添加元素时如果超越cap,系统会重新分配更大的底层数组 //由于值传递的关系,必须接收append的返回值 // s = append(s,val) s1 := arr[2:] fmt.printf("s1=%v\n", s1) s2 := s1[3:5] //[s1[3], s1[4]] fmt.printf("s2=%v, len(s2)=%d, cap(s2)=%d\n", s2, len(s2), cap(s2)) s3 := append(s2, 10) s4 := append(s3, 11) s5 := append(s4, 12) fmt.printf("s3=%v, s4=%v, s5=%v\n", s3, s4, s5) // s4 and s5 no longer view arr fmt.printf("arr=%v\n", arr) //创建一个slice var s []int //zero value for slice is nil for i := 0; i < 100; i++ { printslice(s) s = append(s, i*2+1) } fmt.println(s)} |
slice的copy,添加,删除元素操作
|
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
|
package mainimport ( "fmt")//查看操作系统怎么扩充slice的capfunc printslice(str string, s []int) { fmt.printf("%s=%v, len=%d, cap=%d\n", str, s, len(s), cap(s))}func main() { //初始化slice s1 := []int{2, 4, 6, 8} fmt.println(s1) //[2 4 6 8] //创建一个len为16的slice s2 := make([]int, 16) //创建一个len为10,cap为32的slice s3 := make([]int, 10, 32) printslice("s2", s2) //[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0], len=16, cap=16 printslice("s3", s3) //[0 0 0 0 0 0 0 0 0 0], len=10, cap=32 //拷贝slice fmt.println("copying slice") //dst src copy(s2, s1) printslice("s2", s2) //[2 4 6 8 0 0 0 0 0 0 0 0 0 0 0 0], len=16, cap=16 //删除slice中的元素 fmt.println("deleting element from slice") //删除下标为3的元素 //通过...append s2下标为4后的元素 s2 = append(s2[:3], s2[4:]...) printslice("s2", s2) //删除头尾元素 fmt.println("popping from front") front := s2[0] s2 = s2[1:] fmt.println(front) fmt.println(s2) fmt.println("popping from back") tail := s2[len(s2)-1] s2 = s2[:len(s2)-1] fmt.println(tail) fmt.println(s2)} |
3.map
3.1 map的操作
创建: make(map[string]int)
获取元素:m[key]
key不存在时,获得value类型的初始值
用value,ok := m[key]来判断是否存在key
用delete删除一个key
使用range遍历key,或者遍历key, value对
不保证遍历顺序,如需顺序,需手动对key排序
使用len获得元素个数
|
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
|
package mainimport "fmt"func main() { //创建一个map //map中的key是无序的,是一个hashmap m := map[string]string{ "name": "cocktail_py", "course": "golang", "site": "csdn", "quality": "pretty well", } m2 := make(map[string]int) // m2 = empty map var m3 map[string]int // m3 == nil fmt.println(m, m2, m3) fmt.println("traversing map") for k, v := range m { fmt.println(k, v) } //map 操作 //获取元素:m[key] fmt.println("getting values") coursename, ok := m["course"] fmt.println(coursename, ok) //当key不存在 if courname, ok := m["courname"]; ok { fmt.println(courname) // zero value } else { fmt.println("key does not exist") } fmt.println("deleting values") delete(m, "name") name, ok := m["name"] fmt.println(name, ok)} |
map使用哈希表,必须可以比较相等
除了slice,map,function的内建类型都可以作为key
struct类型不包含上述字段,也可作为key
3.3 map的例题:寻找最长不含有重复字符的子串
|
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
|
/*当前一个字符串,从左往后开始扫描,只要扫描一遍就可以,如果扫到x的位置,看到一个字母x应该怎么做呢首先,记录一个start表示当前找到的最长不含有重复字符的子串的开始,保证start到x之前的子串是不含有重复字符的,之后,需要查看从start到x-1这个位置之间有没有x,使用一个叫lastoccurred[x]记录x最后出现的位置在哪里,使用map会有三种情况:1.x重来没有出现过,或者x出现在start之前,若x出现在start之前,最长的子串+1; 2.lastoccurred[x]出现在start到x中间,更新start位置,start指向lastoccurred[x+1]的位置*/package mainimport "fmt"func lengthofnonrepeatingsubstr(s string)int { lastoccurred := make(map[byte]int) start := 0 maxlength := 0 //遍历字符串 go语言中char类型是使用了一种rune(32位)类型 for x, ch := range []byte(s){ //lastoccurred[ch]有可能不存在;若不存在出现0,会影响运算 if lastl, ok:= lastoccurred[ch];ok && lastl >= start{ start = lastl + 1 } //stat到i结束 if x-start + 1 > maxlength{ maxlength = x -start + 1 } lastoccurred[ch] = x } return maxlength}func main() { fmt.println(lengthofnonrepeatingsubstr("hellohello"))} |
4.rune
rune相当于go的char
使用range遍历pos,rune对
使用utf8.runecountlnstring获得字符数量
使用len获得字节长度
使用[]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
29
30
31
32
33
34
35
36
|
package mainimport ( "fmt" "unicode/utf8")func main() { //英文占一个字节,中文占三个字节 s := "yes我爱csdn!" fmt.println(len(s)) // 14 //%x十六进制,大写字符,每个字节两个字符 //796573e68891e788b14353444e21 fmt.printf("%x\n",[]byte(s)) //%t 相应值的类型 //使用for range遍历字符串时，会默认将byte（int8）类型转化为rune（int32）类型，因为go采用utf-8编码 可变长的编码 for _,b := range s{ fmt.printf("%t %x\n",b,b) } for _,b := range []byte(s){ fmt.printf("%t %x\n",b,b) } //打印字符的个数 fmt.println("rune count:",utf8.runecountinstring(s)) bytes := []byte(s) fmt.println(bytes) for len(bytes) > 0{ ch,size := utf8.decoderune(bytes) bytes = bytes[size:] //相应unicode码点所表示的字符 fmt.printf("%c",ch) } //获取第几个字符是谁 for i, ch := range []rune(s) { fmt.printf("(%d %c) ", i, ch) } fmt.println()} |
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
//国际版func lengthofnonrepeatingsubstr(s string) int { lastoccurred := make(map[rune]int) start := 0 maxlength := 0 //遍历字符串 go语言中char类型是使用了一种rune(32位) //for i, ch := range s{ for i, ch := range []rune(s) { //lastoccurred[ch]有可能不存在;若不存在出现0,会影响运算 if lasti, ok := lastoccurred[ch]; ok && lasti >= start { start = lasti + 1 } //start到i结束 if i-start+1 > maxlength { maxlength = i - start + 1 } lastoccurred[ch] = i } return maxlength} |
补充：golang 容器的学习与实践
golang 提供了几个简单的容器供我们使用，本文在介绍几种 golang 容器的基础上，实现一个基于 golang 容器的lru算法。
容器介绍
golang 容器位于 container 包下，提供了三种包供我们使用，heap、list、ring. 下面我们分别学习。
heapheap 是一个堆的实现。一个堆正常保证了获取/弹出最大（最小）元素的时间为log n、插入元素的时间为 log n.
golang堆实现接口如下：
|
1
2
3
4
5
6
|
// src/container/heap.gotype interface interface { sort.interface push(x interface{}) // add x as element len() pop() interface{} // remove and return element len() - 1.} |
heap 是基于 sort.interface 实现的。
|
1
2
3
4
5
6
|
// src/sort/type interface interface { len() int less(i, j int) bool swap(i, j int)} |
因此，如果要使用官方提供的 heap，需要我们实现如下几个接口：
|
1
2
3
4
5
|
len() int {} // 获取元素个数less(i, j int) bool {} // 比较方法swap(i, j int) // 元素交换方法push(x interface{}){} // 在末尾追加元素pop() interface{} // 返回末尾元素 |
然后在使用时，我们可以使用如下几种方法：
|
1
2
3
4
5
6
7
8
9
10
|
// 初始化一个堆func init(h interface){}// push一个元素倒堆中func push(h interface, x interface{}){}// pop 堆顶元素func pop(h interface) interface{} {}// 删除堆中某个元素，时间复杂度 log nfunc remove(h interface, i int) interface{} {}// 调整i位置的元素位置（位置i的数据变更后）func fix(h interface, i int){} |
list 实现了一个双向链表，链表不需要实现 heap 类似的接口，可以直接使用。
链表的构造：
|
1
2
|
// 返回一个链表对象 func new() *list {} |
官方提供了丰富的方法供我们操作列表，方法如下：
|
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 (l *list) len() int {}// 返回链表中的第一个元素func (l *list) front() *element {}// 返回链表中的末尾元素func (l *list) back() *element {}// 移除链表中的某个元素func (l *list) remove(e *element) interface{} {}// 在表头插入值为 v 的元素func (l *list) pushfront(v interface{}) *element {}// 在表尾插入值为 v 的元素func (l *list) pushback(v interface{}) *element {}// 在mark之前插入值为v 的元素func (l *list) insertbefore(v interface{}, mark *element) *element {}// 在mark 之后插入值为 v 的元素func (l *list) insertafter(v interface{}, mark *element) lement {}// 移动e某个元素到表头func (l *list) movetofront(e *element) {}// 移动e到队尾func (l *list) movetoback(e *element) {}// 移动e到mark之前func (l *list) movebefore(e, mark *element) {}// 移动e 到mark 之后func (l *list) moveafter(e, mark *element) {}// 追加到队尾func (l *list) pushbacklist(other *list) {}// 将链表list放在队列前func (l *list) pushfrontlist(other *list) {} |
我们可以通过 value 方法访问 element 中的元素。除此之外，我们还可以用下面方法做链表遍历：
|
1
2
3
4
5
6
7
8
9
|
// 返回下一个元素func (e *element) next() *element {}// 返回上一个元素func (e *element) prev() *element {}下面是队列的遍历的例子：// l 为队列，for e := l.front(); e != nil; e = e.next() { //通过 e.value 做数据访问} |
container 中的循环列表是采用链表实现的。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
// 构造一个包含n个元素的循环列表func new(n int) *ring {}// 返回列表下一个元素func (r *ring) next() *ring {}// 返回列表上一个元素func (r *ring) prev() *ring {}// 移动n个元素 （可以前移，可以后移）func (r *ring) move(n int) *ring {}// 把 s 链接到 r 后面。如果s 和r 在一个ring 里面，会把r到s的元素从ring 中删掉func (r *ring) link(s *ring) *ring {}// 删除n个元素 （内部就是ring 移动n个元素，然后调用link)func (r *ring) unlink(n int) *ring {}// 返回ring 的长度，时间复杂度 nfunc (r *ring) len() int {}// 遍历ring，执行 f 方法 （不建议内部修改ring）func (r *ring) do(f func(interface{})) {} |
访问 ring 中元素，直接 ring.value 即可。
容器的使用
下面，我们通过 map 和 官方包中的双向链表实现一个简单的 lru 算法，用来熟悉golang 容器的使用。
lru 算法 (least recently used)，在做缓存置换时用的比较多。逐步淘汰最近未使用的 cache，而使我们的缓存中持续保持着最近使用的数据。
|
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
|
package main import "fmt"import "container/list" // lru 中的数据type node struct { k, v interface{}} // 链表 + maptype lru struct { list *list.list cachemap map[interface{}]*list.element size int} // 初始化一个lrufunc newlru(cap int) *lru { return &lru{ size: cap, list: list.new(), cachemap: make(map[interface{}]*list.element, cap), }} // 获取lru中数据func (lru *lru) get(k interface{}) (v interface{}, ret bool) { // 如果存在，则把数据放到链表最前面 if ele, ok := lru.cachemap[k]; ok { lru.list.movetofront(ele) return ele.value.(*node).v, true } return nil, false}// 设置lru中数据func (lru *lru) set(k, v interface{}) { // 如果存在，则把数据放到最前面 if ele, ok := lru.cachemap[k]; ok { lru.list.movetofront(ele) ele.value.(*node).v = v // 更新数据值 return } // 如果数据是满的，先删除数据，后插入 if lru.list.len() == lru.size { last := lru.list.back() node := last.value.(*node) delete(lru.cachemap, node.k) lru.list.remove(last) } ele := lru.list.pushfront(&node{k: k, v: v}) lru.cachemap[k] = ele} |
注意事项
上述的容器都不是 goroutines 安全的
1、上面的lr 也不是 goroutines 安全的
2、ring 中不建议在 do 方法中修改 ring 的指针，行为是未定义的
以上为个人经验，希望能给大家一个参考，也希望大家多多支持服务器之家。如有错误或未考虑完全的地方，望不吝赐教。
原文链接：https://blog.csdn.net/Cocktail_py/article/details/104422076
