array

Array

数组是编程语言作为一种基本类型提供出来的，相同数据类型的元素按一定顺序排列的集合。

它的作用只有一种：存放数据，让你很快能找到存的数据。如果你不去额外改进它，它就只是存放数据而已，它不会将一个数据节点和另外一个数据节点关联起来。

数组这一数据类型，是被编程语言高度抽象封装的结构，下标 会转换成 虚拟内存地址，然后操作系统会自动帮我们进行寻址，这个寻址过程是特别快的，所以往数组的某个下标取一个值和放一个值，时间复杂度都为 O(1)。

它是一种将 虚拟内存地址 和 数据元素 映射起来的内置语法结构，数据和数据之间是挨着，存放在一个连续的内存区域，每一个固定大小（8字节）的内存片段都有一个虚拟的地址编号。当然这个虚拟内存不是真正的内存，每个程序启动都会有一个虚拟内存空间来映射真正的内存。

Variable-length array

因为数组大小是固定的，当数据元素特别多时，固定的数组无法储存这么多的值，所以可变长数组出现了，这也是一种数据结构。

slice是对底层数组的抽象和控制。它是一个结构体：

type slice struct {
    array unsafe.Pointer  // 指向底层数组的指针。( Golang 语言是没有操作原始内存的指针的，所以 unsafe 包提供相关的对内存指针的操作，一般情况下非专业人员勿用)
    len   int // 切片的真正长度，也就是实际元素占用的大小。
    cap   int // 切片的容量，底层固定数组的长度。
}

实现可变长数组

我们来实现一个简单的，存放整数的，可变长的数组版本。

因为 Golang 的限制，不允许使用 [n]int 来创建一个固定大小为 n 的整数数组，只允许使用常量来创建大小。

所以我们这里会使用切片的部分功能来代替数组，虽然切片本身是可变长数组，但是我们不会用到它的 append 功能，只把它当数组用。

import (
    "sync"
)

// Array 可变长数组
type Array struct {
    array []int      // 固定大小的数组，用满容量和满大小的切片来代替
    len   int        // 真正长度
    cap   int        // 容量
    lock  sync.Mutex // 为了并发安全使用的锁
}

初始化数组

// Make 新建一个可变长数组
func Make(len, cap int) *Array {
    s := new(Array)
    if len > cap {
        panic("len large than cap")
    }

    // 把切片当数组用
    array := make([]int, cap, cap)

    // 元数据
    s.array = array
    s.cap = cap
    s.len = 0
    return s
}
主要利用满容量和满大小的切片来充当固定数组，
结构体 Array 里面的字段 len 和 cap 来控制值的存取。不允许设置 len > cap 的可变长数组。

时间复杂度为：O(1)，因为分配内存空间和设置几个值是常数时间。

添加元素

// Append 增加一个元素
func (a *Array) Append(element int) {
    // 并发锁
    a.lock.Lock()
    defer a.lock.Unlock()

    // 大小等于容量，表示没多余位置了
    if a.len == a.cap {
        // 没容量，数组要扩容，扩容到两倍
        newCap := 2 * a.len

        // 如果之前的容量为0，那么新容量为1
        if a.cap == 0 {
            newCap = 1
        }

        newArray := make([]int, newCap, newCap)

        // 把老数组的数据移动到新数组
        for k, v := range a.array {
            newArray[k] = v
        }
        // 替换数组
        a.array = newArray
        a.cap = newCap
    }
    // 把元素放在数组里
    a.array[a.len] = element
    // 真实长度+1
    a.len = a.len + 1
}

//首先添加一个元素到可变长数组里，会加锁，这样会保证并发安全。然后将值放在数组里：
//a.array[a.len] = element，然后 len + 1，表示真实大小又多了一个。
//
//当真实大小 len = cap 时，表明位置都用完了，没有多余的空间放新值，
//那么会创建一个固定大小 2*len 的新数组来替换老数组：a.array = newArray，
//当然容量也会变大：a.cap = newCap。如果一开始设置的容量 cap = 0，
//那么新的容量会是从 1 开始。
//
//添加元素中，耗时主要在老数组中的数据移动到新数组，时间复杂度为：O(n)。当然，
//如果容量够的情况下，时间复杂度会变为：O(1)。

// AppendMany 增加多个元素
func (a *Array) AppendMany(element ...int) {
    for _, v := range element {
        a.Append(v)
    }
}

获取指定下标元素

// Get 获取某个下标的元素
func (a *Array) Get(index int) int {
    // 越界了
    if a.len == 0 || index >= a.len {
        panic("index over len")
    }
    return a.array[index]
}

// 当可变长数组的真实大小为0，或者下标 index 超出了真实长度 len ，将会 panic 越界。

// 因为只获取下标的值，所以时间复杂度为 O(1)。

获取真实长度和容量

// Len 返回真实长度
func (a *Array) Len() int {
    return a.len
}

// Cap 返回容量
func (a *Array) Cap() int {
    return a.cap
}

//时间复杂度为 O(1)。