Golang: 内建容器的用法

1.数组

 

数组是值类型

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

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

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

package main
import "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.

package main
import "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)
}

2.2 slice的扩展

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

package main
import "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])
}

2.2 slice的其它操作

向slice添加元素

package main
import "fmt"
//查看操作系统怎么扩充slice的cap
func 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,添加,删除元素操作

package main
import (
    "fmt"
)
//查看操作系统怎么扩充slice的cap
func 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获得元素个数

package main
import "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)
}

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 main
import "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获得字节

package main
import (
    "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()
}

4.1 map的例题:寻找最长不含有重复字符的子串(国际版)

//国际版
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. 下面我们分别学习。

heap

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

golang堆实现接口如下：

// src/container/heap.go
type 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 n
func 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 的长度，时间复杂度 n
func (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{}
}

// 链表 + map
type lru struct {
  list *list.list
  cachemap map[interface{}]*list.element
  size int
}

// 初始化一个lru
func 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