数据结构 - 向量简单介绍
完成第一版了解数据结构概念和常用方法。
待做第二版常用方法的实现。
向量：存储同一种类型数据的一维数组。
向量和列表（list）属于序列。
向量是对数组的扩展。
通常将序列的下标称为秩（Rank）
向量分为有序和无序。
向量的数组的优缺点：
1、查找某位置的的元素是O(1)阶的，因为数组嘛例如a[1];
2、插入元素的代价是巨大的，最坏的情况是插到最前面，需要将原数组中的所有元素向后移动。O(n)；
3、删除一样花费巨大。O(n)；
4、对于插入删除元素在末尾时，这种情况是让人欣慰的O(1)。（所以文中实现了插入删除尾端元素，而不实现插入中间或者前端（因为在我看来这种操作花费如此巨大实现了也没有意义，如果需要我们可以用其他的数据结构来完成））。
基本操作：
1，创建
数组的创建
2，引用
数组的下标引用法。
3，集合运算
3.1，求交集 intersect
返回二个集的共有部分。
3.2，求并集 union
把二个集合合并，返回。
3.3，求差集 setdiff
去掉共有的集，返回其余的各自集的合集。
常见向量类型
数值向量常用函数列表
| 函数 | 功能说明 | 使用方法 |
| length | 获取向量的长度 | length(vector) int |
| max | 获取向量中的最大值 | max(vector) int |
| min | 获取向量中的量小值 | min(vector) int |
| mean | 获取向量中的平均值 | mean(vector) int |
| median | 获取向量中的中位数 中位数（Median）又称中值，统计学中的专有名词，是按顺序排列的一组数据中居于中间位置的数，代表一个样本、种群或概率分布中的一个数值，其可将数值集合划分为相等的上下两部分。 | median(vector) int |
| quantile | 获取向量中的分位数 分位数（Quantile），亦称分位点，是指将一个随机变量的概率分布范围分为几个等份的数值点，常用的有中位数（即二分位数）、四分位数、百分位数等。 | quantile(vector, prob=seq(0, 1, 0.25)) |
| sort | 将向量重新排序 | sort(vector) |
| rank | 返回向量 x 的秩，即 x 中数字的大小顺序 | rank(vector) |
| order | 返回一个向量升序排序后的数字在原数据中的位置 | order(vector) |
| match | 在 y 中逐个查找 x ，并返回在 y 中匹配的位置，若无返回 NA | match(x, y) |
| cut | 将数值型数据分区间转化成因子，即将数值型数据离散化 | cut(x, breaks, iabei) |
| isEmpty | 是否为空 | isEmpty(vector) bool |
| getAtRank | 获取秩 x 的元素 | getAtRank(x) int |
| replaceAtRank | 将秩 x 的元素替换为 obj | replaceAtRank(x int, obj interface{}) |
| insertAtRank | 插入秩和铁的值 | insertAtRank(x int, obj interface{}) |
| removeAtRank | 删除秩为 x 的元素 | removeAtRank( x int) |
| deduplicate, uniquify | 删除重复元素 向量/有序向量 |
|
| disordered | 判断所有元素是否已按非降序排列 |
|
代码来源：
https://github.com/liyue201/gostl/blob/master/ds/vector/vector.go
package vector
import (
"fmt"
"github.com/liyue201/gostl/utils/iterator"
)
// Options holds the Vector's options
type Options struct {
capacity int
}
// Option is a function type used to set Options
type Option func(option *Options)
// WithCapacity is used to set the capacity of a Vector
// 用于设置向量的容量
func WithCapacity(capacity int) Option {
return func(option *Options) {
option.capacity = capacity
}
}
// Vector is a linear data structure, the internal is a slice
// 向量的数据结构，数组
type Vector struct {
data []interface{}
}
// New creates a new Vector
// 创建一个新向量
func New(opts ...Option) *Vector {
option := Options{}
for _, opt := range opts {
opt(&option)
}
return &Vector{
data: make([]interface{}, 0, option.capacity),
}
}
// NewFromVector news a Vector from other Vector
// 通过其他向量创建一个新向量
func NewFromVector(other *Vector) *Vector {
v := &Vector{data: make([]interface{}, other.Size(), other.Capacity())}
for i := range other.data {
v.data[i] = other.data[i]
}
return v
}
// Size returns the size of the vector
// 获取向量的大小
func (v *Vector) Size() int {
return len(v.data)
}
// Capacity returns the capacity of the vector
// 获取向量的容量
func (v *Vector) Capacity() int {
return cap(v.data)
}
// Empty returns true if the vector is empty, otherwise returns false
// 判断向量是否为空，空返回 true
func (v *Vector) Empty() bool {
if len(v.data) == 0 {
return true
}
return false
}
// PushBack pushes val to the back of the vector
// 添加新值到向量尾
func (v *Vector) PushBack(val interface{}) {
v.data = append(v.data, val)
}
// SetAt sets the value val to the vector at position pos
// 设置向量的秩的值
func (v *Vector) SetAt(pos int, val interface{}) {
if pos < 0 || pos >= v.Size() {
return
}
v.data[pos] = val
}
// InsertAt inserts the value val to the vector at position pos
// 创建向量的秩和其值
func (v *Vector) InsertAt(pos int, val interface{}) {
if pos < 0 || pos > v.Size() {
return
}
v.data = append(v.data, val)
for i := len(v.data) - 1; i > pos; i-- {
v.data[i] = v.data[i-1]
}
v.data[pos] = val
}
// EraseAt erases the value at position pos
// 删除秩的值
func (v *Vector) EraseAt(pos int) {
v.EraseIndexRange(pos, pos+1)
}
// EraseIndexRange erases values at range[first, last)
// 删除秩范围内的值，不含参数的秩值
func (v *Vector) EraseIndexRange(first, last int) {
if first > last {
return
}
if first < 0 || last > v.Size() {
return
}
left := v.data[:first]
right := v.data[last:]
v.data = append(left, right...)
}
// At returns the value at position pos, returns nil if pos is out off range .
// 获取秩的值
func (v *Vector) At(pos int) interface{} {
if pos < 0 || pos >= v.Size() {
return nil
}
return v.data[pos]
}
//Front returns the first value in the vector, returns nil if the vector is empty.
// 获取向量的第一个值，如果为空返回空
func (v *Vector) Front() interface{} {
return v.At(0)
}
//Back returns the last value in the vector, returns nil if the vector is empty.
// 获取向量的最后（尾）的一个值，如果为空返回 nil
func (v *Vector) Back() interface{} {
return v.At(v.Size() - 1)
}
//PopBack returns the last value of the vector and erase it, returns nil if the vector is empty.
// 删除向量尾的一个值，如果向量为空返回 nil
func (v *Vector) PopBack() interface{} {
if v.Empty() {
return nil
}
val := v.Back()
v.data = v.data[:len(v.data)-1]
return val
}
//Reserve makes a new space for the vector with passed capacity
// 设置向量的新容量（扩大）
func (v *Vector) Reserve(capacity int) {
if cap(v.data) >= capacity {
return
}
data := make([]interface{}, v.Size(), capacity)
for i := 0; i < len(v.data); i++ {
data[i] = v.data[i]
}
v.data = data
}
// ShrinkToFit shrinks the capacity of the vector to the fit size
// 缩小向量的容量
func (v *Vector) ShrinkToFit() {
if len(v.data) == cap(v.data) {
return
}
len := v.Size()
data := make([]interface{}, len, len)
for i := 0; i < len; i++ {
data[i] = v.data[i]
}
v.data = data
}
// Clear clears all data in the vector
// 清空向量的所有数据
func (v *Vector) Clear() {
v.data = v.data[:0]
}
// Data returns internal data of the vector
// 返回向量的所有数据
func (v *Vector) Data() []interface{} {
return v.data
}
// Begin returns the first iterator of the vector
// 返回向量的第一个迭代器
func (v *Vector) Begin() *VectorIterator {
return v.First()
}
// End returns the end iterator of the vector
// 返回向量的最后的迭代器
func (v *Vector) End() *VectorIterator {
return v.IterAt(v.Size())
}
// First returns the first iterator of the vector
// 向量的第一个迭代器
func (v *Vector) First() *VectorIterator {
return v.IterAt(0)
}
// Last returns the last iterator of the vector
// 向量的最后的迭代器
func (v *Vector) Last() *VectorIterator {
return v.IterAt(v.Size() - 1)
}
// IterAt returns the iterator at position of the vector
// 返回向量位置的迭代器
func (v *Vector) IterAt(pos int) *VectorIterator {
return &VectorIterator{vec: v, position: pos}
}
// Insert inserts a value val to the vector at the position of the iterator iter point to
// 将值插入向量迭代器所指的位置
func (v *Vector) Insert(iter iterator.ConstIterator, val interface{}) *VectorIterator {
index := iter.(*VectorIterator).position
v.InsertAt(index, val)
return &VectorIterator{vec: v, position: index}
}
// Erase erases the element of the iterator iter point to
// 删除向量迭代器所指的秩位置
func (v *Vector) Erase(iter iterator.ConstIterator) *VectorIterator {
index := iter.(*VectorIterator).position
v.EraseAt(index)
return &VectorIterator{vec: v, position: index}
}
// EraseRange erases all elements in the range[first, last)
// 删除向量迭代器所指的范围
func (v *Vector) EraseRange(first, last iterator.ConstIterator) *VectorIterator {
from := first.(*VectorIterator).position
to := last.(*VectorIterator).position
v.EraseIndexRange(from, to)
return &VectorIterator{vec: v, position: from}
}
// Resize resizes the size of the vector to the passed size
// 调整向量的大小
func (v *Vector) Resize(size int) {
if size >= v.Size() {
return
}
v.data = v.data[:size]
}
// String returns a string representation of the vector
// 返回向量的字符串表达
func (v *Vector) String() string {
return fmt.Sprintf("%v", v.data)
}
参考：
https://zhuanlan.zhihu.com/p/50093468
https://www.jianshu.com/p/c653a93409b0