Golang: 内建容器的用法

1.数组

数组是值类型

[10]int 和 [20]int是不同类型

调用func(arr [10]int)会拷贝数组

在go语言中一般不直接使用数据

package mainimport 'fmt'func updateArr(arr *[5]int) {arr[0] = 100}func updateArrThroughSlice(arr []int) {arr[0] = 100}func main() {//创建一个数据var arr [5]intarr2 := [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个元素为:%dn', 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[:]) //传入Slicefmt.Println('update after')fmt.Println(arr3)}2.Slice(切片)2.1 Slice的实现

Slice本身没有数据,是对底层array的一个view

Slice内部有个指针(ptr)指向开头的元素,Slice有长度(len),容量(cap);cap代表从指针(ptr)开始到数组(arr)末尾的长度,Slice在扩展的时候不能超过cap.

package mainimport 'fmt'func updateSlice(s []int) {s[0] = 100}func main() {arr := [...]int{0, 1, 2, 3, 4, 5, 6, 7}//创建一个Slices1 := arr[:]s2 := arr[2:6]fmt.Printf('s1:%vns2:%vn', s1, s2)//改变Slice内部元素updateSlice(s2)fmt.Println(s2)//ReSlice:对Slice再进行一次Slice操作s3 := s1[:5]fmt.Println(s3)s3 = s3[:2]fmt.Println(s3)}2.2 Slice的扩展

s[i]不可以超越len(i),向后扩展不可以超过底层数组cap(s)

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=%vn', arr)//Extending Slice 不能超过cap(s)s1 := arr[2:6]fmt.Printf('s1=%v, len(s1)=%d, cap(s1)=%dn', s1, len(s1), cap(s1))s2 := s1[3:5]fmt.Printf('s2=%v, len(s2)=%d, cap(s2)=%dn', 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])}2.2 Slice的其它操作

向Slice添加元素

package mainimport 'fmt'//查看操作系统怎么扩充Slice的capfunc printSlice(s []int) {fmt.Printf('%v, len=%d, cap=%dn', 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=%vn', s1)s2 := s1[3:5] //[s1[3], s1[4]]fmt.Printf('s2=%v, len(s2)=%d, cap(s2)=%dn', s2, len(s2), cap(s2))s3 := append(s2, 10)s4 := append(s3, 11)s5 := append(s4, 12)fmt.Printf('s3=%v, s4=%v, s5=%vn', s3, s4, s5)// s4 and s5 no longer view arrfmt.Printf('arr=%vn', arr)//创建一个Slicevar s []int//Zero value for slice is nilfor i := 0; i < 100; i++ {printSlice(s)s = append(s, i*2+1)}fmt.Println(s)}

Slice的copy,添加,删除元素操作

package mainimport ('fmt')//查看操作系统怎么扩充Slice的capfunc printSlice(str string, s []int) {fmt.Printf('%s=%v, len=%d, cap=%dn', str, s, len(s), cap(s))}func main() {//初始化slices1 := []int{2, 4, 6, 8}fmt.Println(s1)//[2 4 6 8]//创建一个len为16的Slices2 := make([]int, 16)//创建一个len为10,cap为32的Slices3 := 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=16printSlice('s3', s3)//[0 0 0 0 0 0 0 0 0 0], len=10, cap=32//拷贝Slicefmt.Println('Copying Slice')//dst srccopy(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.Map3.1 Map的操作

创建: make(map[string]int)

获取元素:m[key]

key不存在时,获得Value类型的初始值

用value,ok := m[key]来判断是否存在key

用delete删除一个key

使用range遍历key,或者遍历key, value对

不保证遍历顺序,如需顺序,需手动对key排序

使用len获得元素个数

package mainimport 'fmt'func main() {//创建一个map//map中的key是无序的,是一个HashMapm := map[string]string{'name': 'Cocktail_py','course': 'golang','site': 'CSDN','quality': 'pretty well',}m2 := make(map[string]int) // m2 = empty mapvar m3 map[string]int // m3 == nilfmt.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)}3.2 Map的key

map使用哈希表,必须可以比较相等

除了Slice,map,function的内建类型都可以作为key

Struct类型不包含上述字段,也可作为key

3.3 Map的例题:寻找最长不含有重复字符的子串

/*当前一个字符串,从左往后开始扫描,只要扫描一遍就可以,如果扫到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 := 0maxLength := 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获得字节

package mainimport ('fmt''unicode/utf8')func main() {//英文占一个字节,中文占三个字节s := 'yes我爱CSDN!'fmt.Println(len(s)) // 14//%X十六进制,大写字符,每个字节两个字符//796573E68891E788B14353444E21fmt.Printf('%Xn',[]byte(s))//%T 相应值的类型//使用for range遍历字符串时，会默认将byte（int8）类型转化为rune（int32）类型，因为go采用UTF-8编码 可变长的编码for _,b := range s{fmt.Printf('%T %Xn',b,b)}for _,b := range []byte(s){fmt.Printf('%T %Xn',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()}4.1 Map的例题:寻找最长不含有重复字符的子串(国际版)

//国际版func lengthOfNonRepeatingSubStr(s string) int {lastOccurred := make(map[rune]int)start := 0maxLength := 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. 下面我们分别学习。

heap

heap 是一个堆的实现。一个堆正常保证了获取/弹出最大（最小）元素的时间为log n、插入元素的时间为 log n.

Golang堆实现接口如下：

// 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 实现的。

// src/sort/type Interface interface { Len() int Less(i, j int) bool Swap(i, j int)}

因此，如果要使用官方提供的 heap，需要我们实现如下几个接口：

Len() int {} // 获取元素个数Less(i, j int) bool {} // 比较方法Swap(i, j int) // 元素交换方法Push(x interface{}){} // 在末尾追加元素Pop() interface{} // 返回末尾元素

然后在使用时，我们可以使用如下几种方法：

// 初始化一个堆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 链表

list 实现了一个双向链表，链表不需要实现 heap 类似的接口，可以直接使用。

链表的构造：

// 返回一个链表对象 func New() *List {}

官方提供了丰富的方法供我们操作列表，方法如下：

// 返回链表的长度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 中的元素。除此之外，我们还可以用下面方法做链表遍历：

// 返回下一个元素func (e *Element) Next() *Element {}// 返回上一个元素func (e *Element) Prev() *Element {}下面是队列的遍历的例子：// l 为队列，for e := l.Front(); e != nil; e = e.Next() { //通过 e.Value 做数据访问}ring 循环列表

container 中的循环列表是采用链表实现的。

// 构造一个包含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，而使我们的缓存中持续保持着最近使用的数据。

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 的指针，行为是未定义的

以上为个人经验，希望能给大家一个参考，也希望大家多多支持优爱好网。如有错误或未考虑完全的地方，望不吝赐教。