golang数据结构初探之动态数组slice

2023-11-07

动态数组slice

slice 又称动态数组,依托于数组实现,可以方便的进行扩容和传递,实际使用时比数组更灵活。但正是因为灵活,实际使用时更容易出错,避免出错的最好方法便是了解其实现原理。

特性速览

初始化

声明和初始化切片的方式主要有以下几种方式:

  • 变量声明
  • 字面量
  • 使用内置函数make()
  • 从切片和数组中切取
变量声明

这种声明方式的切片变量与声明其他类型变量一样,变量值都为零值,对于切片来讲零值为nil

var s []int
字面量

也可以使用字面量初始化切片,需要了解的是空切片是指长度为空,其值并不是nil。

声明长度为0的切片时,推荐使用变量声明的方式获得一个nil切片,而不是空切片,因为nil切片不需要内存分配。

s1:=[]int{}	//空切片
s2:=[]int{1,2,3}	//长度为3的切片
内置函数make()

内置函数make() 可以创建切片,切片元素均初始化为相应类型的零值。

推荐指定长度的同时预估空间,可有效的减少切片扩容时内存分配以及拷贝次数。

s1:=make([]int,12)	//指定长度
s2:=make([]int,10,100)	//指定长度和空间
切取

切片可以基于数组和切片创建,需要了解的是切片与原数组或者原切片共享底层空间,修改切片会影响原数组或者原切片。

切片表达式[low:high] 表示的是左闭右开[low,high)区间,切取的长度为 high - low。

array := [5]int{1,2,3,4,5}
s1 := array[0:2]	//从数组中切取
s2 := s1[0:1]			//从切片切取
fmt.Println(s1)		// [1,2]
fmt.Println(s2)		// [1]

另外,适用于任意类型的内置函数new() 也可以创建切片:

s := *new([]int)	//此时创建的切片值为nil

切片操作

内置函数append()用于向切片中追加元素:

s := make([]int,0)	//初始化切片
s = append(s,1)			//添加1个元素
s = append(s,2,3,4)			//添加多个元素
s = append(s,[]int{5,6}...)			//添加1个切片
fmt.Println(s)			//[1,2,3,4,5,6]

当切片空间不足时,append()会先创建新的大容量切片,添加元素后返回新切片。

内置函数len()和cap()分别用于查询切片的长度和容量,由于切片的本质为结构体,结构体中直接存储了切片的长度和容量,所以这两个函数的时间复杂度都为O(1)。

实现原理

slice依托数组实现,底层数组对用户屏蔽,在底层数组容量不足的时候可以 实现自动重分配并生产新的slice。

数据结构

源码包中src/runtime/slice.go:slice 定义了slice的数据结构:

type slice struct {
	array unsafe.Pointer	//底层数组
	len   int		//长度
	cap   int		//容量
}

从数据结构上看slice很清晰,array指针指向底层数组,len表示数组长度,cap表示底层数组的容量。

切片操作

使用make()创建slice

使用make()创建slice时,可以同时指定长度和容量,创建时底层会分配一个数组,数组的长度即为容量。

例如,slice := make([]int , 5 , 10)语句所创建的slice的结构如下图所示:

image-20210817165334892

该slice的长度为5,即可以使用下标slice[0]~slice[4]来操作里面的元素,capacity为10,表示后续想slice添加新元素的时候可以不必重新分配内存,直接使用预留的内存即可,直到预留的内存不足再进行扩容。

使用数组创建slice

使用数组创建slice时,slice将于原数组共用一部分内存

例如,slice := array[5,7]语句所创建的slice的结构如下图所示:

image-20210817171146578

切片从数组array[5]开始,到数组array[7]结束(不包含7),即切片的长度为2,数组后面的内存都作为切片的预留内存,即capacity为5。

数组和数组的切片共享底层存储空间,这是使用过程中需要额外注意的地方。如果切片是从数组中创建而来,那么对切片的操作会影响原始数组,如果有多个切片从同一个数组中创建,那么对一个切片的操作会影响其他切片。

slice扩容

使用append向slice追加元素时,如果slice空间不足,则会触发slice扩容,扩容实际上是重新分配一块更大的内存,将原slice的数据拷贝进新的slice中,然后返回新slice,扩容后再将数据追加进去。

例如,当向一个capacity为5,且length也为5的slice再次追加1个元素时,就会发生扩容,如下图所示:

image-20210817172105601

扩容操作只关心容量,会把原slice的数据拷贝到新slice中,追加数据由append在扩容结束后进行。在上图中可以看出,扩容完成后,len还是5,但是cap由5变成了10,原slice的数据也拷贝到了新slice中了。

扩容容量的选择遵循一下基本规则:

  • 如果原slice的容量小于1024,则新slice的容量将扩容到2倍
  • 如果原slice的容量大于等于1024,则新slice的容量将扩容1.25倍
image-20210817172421806

在该规则的基础上,还会考虑元素类型与内存分配规则,对实际扩展值做一些微调。从这个基本规则中可以看出Go对slice的性能和空间使用率的思考。

  • 当切片较小时,采用较大的扩容倍速,可以避免频繁扩容,从而减少内存分配次数和数据拷贝的代价
  • 当切片较大时,采用较小的扩容倍速,主要是为了避免浪费空间

使用append()向slice添加一个元素的实现步骤如下:

  • 加入slice的容量够用,直接追加进去,slice.len++,返回slice
  • 原slice的容量不够,将slice先扩容,扩容后得到新的slice
  • 将新元素追加进新slice中,slice.len++,返回新slice
slice拷贝

使用copy()内置函数拷贝两个切片时,会将原切片的数据逐个拷贝到目标切片指向的数组中,拷贝数量取决于两个切片长度的最小值。假如目标切片容量不够,不会发生扩容的情况。

小结

  • 每个切片都指向一个底层数组
  • 每个切片都保存了当前切片的长度和容量
  • 使用len()计算切片长度的时间复杂度为O(1)
  • 使用cat()计算切片容量的时间复杂度为O(1)
  • 通过函数传递切片时,不会拷贝整个切片,因为切片本身只是一个结构体而已
  • 使用append()向切片追加元素时有可能会发生扩容现象,扩容后会生成新的切片

此处有几个值得注意的编程建议:

  • 创建切片时,如果可以估计到使用容量,尽可能的指定,可以避免在追加元素的过程中出现扩容操作,有利于提升性能
  • Copy()函数切片拷贝时需要判断实际拷贝的元素个数,有可能目标切片长度不足,产生丢失数据的情况
  • 谨慎使用多个切片操作同一个数组,以防出现读写冲突

切片表达式

slice表达式可以基于一个字符串生成子字符串,也可以从一个数组或者切片中生成切片。Go语言提供了两种表达式:

  • 简单表达式: array[low : high]
  • 扩展表达式: array[low : high : max]

简单表达式

简单表达式日常使用的频率最高,其格式为 array[low : high]。如果a为数组或者切片,则该表达式将切取 array位于[low : high)区间的元素并生成一个新的切片。如果array为字符串,稍微有一点特殊的是该表达式会生成一个字符串,而不是切片。

简单表达式生成的切片的长度为 high - low。例如我们使用简单表达式切取数组array并生成新的切片b:

array :=[5]int{1,2,3,4,5}
b := a[1:4]

此时得到的切片b的长度为3,元素分别为:

b[0] ==2 
b[1] ==3 
b[2] ==4 
底层数组共享

根据之前介绍的切片的数据结构,我们知道每个切片包含三个元素:

type slice struct {
	array unsafe.Pointer	//底层数组
	len   int		//长度
	cap   int		//容量
}

这里需要着重强调的是,使用简单表达式生成的切片将于原数组或者切片共享底层数组。 新切片的生成逻辑可以使用以下伪代码表示:

b.array = &array[low]
b.len = high - low
b.cap = len(a) = low
边界问题

如果简单表达式切取的对象为字符串或者数组,那么在表达式 a[low : high] 中 low 和 high的取值需要满足以下关系

0 <= low <= high < len(a)

如果简单表达式切片的对象为切片,那么在表达式 a[low : high] 中 low 和 high 的最大取值可以为a的容量,而不是a的长度:

a <= low <= high <= cap(a)
切取string

表达式a[low : high]作用于数组、切片时会产生新的切片,作用于字符串时则会产生新的字符串,而不是切片。

这是由string和slice的类型差异决定的,slice可以支持随机读写,而string不可以。

默认值

为了使用方便,简单表达式 a[low : high] 中low 和high 都是可以省略的。

low默认值为0,而high的默认值为表达式作用对象的长度

a[:high] 等同于 a[0:high]
a[0:] 等同于 a[0:len(a)]
a[:] 等同于 a[0:len(a)]

扩展表达式

简单表达式生成的切片与原数组或者切片共享底层数组避免了拷贝元素,节约内存空间的同时,也会带来读写冲突的风险。

新切片b( b := a[low : high] ) 不仅可以读写a[low] 到 a[high-1]之间的元素,而且在使用append(b,x)函数增加新元素x时,还可能会覆盖a[high]以及后面的元素。例如:

a := [5]int{1,2,3,4,5}
b := a[1:4]
b = append(b,0)	//此时a[4]将由5变为0

使用新切片覆盖a[high]以及后面的元素,有可能是非预期的,从而产生灾难性的后果。

Go团队很早就关注到了这个风险,并且在Go1.2中就提供了一种可以限制新切片容量的表达式,即扩展表达式:

a[low : high : max]

扩展表达式中的max用于限制新生成切片的容量,新切片的容量为 max-low,表达式中low、high 和max的关系需要满足如下:

o <= low <= high <= max <= cap(a)

对于一个长度为10的数组,使用扩展表达式切取其中两个元素生成的新切片的拓扑结构如下图所示:

image-20210817182149227

如果使用简单表达式,那么上图中切片的容量为5,而使用扩展表达式时切片的容量则被限制为2.

扩展表达式常见于偏底层的代码中,比如Go源码。扩展表达式生成的切片被限制存储容量,当使用append()函数向此切片追加元素时,如果容量不足则会产生一个全新的slice,而不会覆盖原数组或者切片。

扩展表达式中的a[low : high : max]只有low是可以省略的,其默认值为0。这一点与简单表达式不同。

如果缺失了 high 或者max, 则会产生编译错误。

小结

  • slice表达式分为简单表达式 a[low , high] 和扩展表达式 a[low : high : max]
  • 简单表达式作用于数组、切片时会产生新的切片,作用于字符串时会产生新的字符串
  • 扩展表达式只能作用于数组、切片,不用作用于字符串
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

golang数据结构初探之动态数组slice 的相关文章

随机推荐

  • Android 模拟返回键、菜单键、主页键

    发送命令模拟按键操作 方法一 用Runtime模拟按键操作 param keyCode 按键事件 KeyEvent 的按键值 private void sendKeyCode1 int keyCode try String keyComma
  • python实现ip地址查询

    encoding utf8 根据ip地址查询出IP所在的地理位置 import requests def get ip info ip r requests get http ip taobao com service getIpInfo
  • websocket简单使用

    简单实现 参考 https websockets readthedoc PS 此文章只限于python版本大于3 6 前期准备 pip install websocket server端 import asyncio import webs
  • 怎么插入svg_公众号文章SVG使用教程分享

    嘿 胖友们大家好呀 我是三儿 每天 困扰在我们新时代新媒体人面前的 不是今天不知道该写啥 也不是粉丝咋又掉了 而是 今天中午吃啥 每天一到饭点 公司的外卖群里就开始了灵魂质问 今天吃啥 这个时候 就轮到貌美如花的小三儿出场了 先来看看三儿是
  • 小程序用户隐私保护指引设置填写指南(小程序隐私保护说明如何填写)

    小程序隐私保护指引完整填写范本 小程序隐私保护说明如何填写 小程序用户隐私保护指南填写指南仅供参考 为了区分用户 开发者在征得你明确同意后 会收集你的微信昵称和头像 为了显示距离 开发商在征得你的明确同意后 会收集你的位置信息 对于用户互动
  • MCU学习笔记_PWR电源管理系统

    MCU学习笔记 电源管理系统 1 STM32电源监控器概述 2 STM32电源 3 HAL库配置PVD实例 1 STM32电源监控器概述 原因 保持系统正常运行 实现特定条件下的低功耗模式 上电复位 POR 掉电复位 PDR 上电复位是指上
  • 面试官:说说react的渲染过程

    hello 这里是潇晨 大家在面试的过程中有没有遇到过一些和react相关的问题呢 比如面试官让你说说react渲染的过程 这到题目比较开放 也比较考验大家对react渲染原理以及源码的整体架构的理解 整体流程 react的核心可以用ui
  • STM32局部变量过大导致栈溢出

    最近项目调试中发现只要使用memset函数对一个局部数组赋值时 就会导致其他全局变量值被更改 接着就进入HardFault错误 后来发现局部变量和全局变量地址重叠 Data Write结构体为全局变量 OTA Data为局部数组 看了启动文
  • 利用类实现rand函数,以及相应的优化

    亮点 实现了一个非常高效的跳越性调用函数 见代码part 4 include
  • IDEA将jar包部署到Docker中使用TLS认证

    一 无CA认证 1 修改服务器配置 开放Docker的远程连接访问 root localhost vim usr lib systemd system docker service 将ExecStart属性value值改为 usr bin
  • vue + elementui:分页查询,el-pagination,纯前端分页

    效果 新建pages js文件 文件内容 数据分页 function pageData total pageRow currentPage allTableDataList var dealData var onePageList var
  • ChatGPT在指尖跳舞: open-interpreter实现本地数据采集、处理一条龙

    更多详情请点击查看原文ChatGPT在指尖跳舞 open interpreter实现本地数据采集 处理一条龙 Python教学专栏 旨在为初学者提供系统 全面的Python编程学习体验 通过逐步讲解Python基础语言和编程逻辑 结合实操案
  • vue集成汉字转拼音(附多音字解决方案)

    1 结果显示 输出首字母 N 输出拼音 NiHaoMa 2 js调用 import HanziToPinyin from hanziToPinyin export default class Message extends Vue moun
  • Intellij IDEA的激活(使用破解补丁永久激活)

    1 先下载个idea 给个官网下载吧 https www jetbrains com idea 这里只介绍破解补丁方式 个人觉得破解补丁方式是最一劳永逸的 破解步骤如下 2 从http idea lanyus com 这个网址下载破解补丁
  • HTTPS加密流程详解

    文章目录 HTTPS与HTTP的关系 HTTPS基本工作过程 对称密钥 非对称密钥 中间人攻击 证书 HTTPS与HTTP的关系 HTTPS协议基于HTTP 只是比HTTP多了一个加密层 为什么要加密呢 因为网络传输的过程中 明文传输的数据
  • 华为OD机试 - 找终点(Java)

    题目描述 给定一个正整数数组 设为nums 最大为100个成员 求从第一个成员开始 正好走到数组最后一个成员 所使用的最少步骤数 要求 第一步必须从第一元素开始 且1 lt 第一步的步长
  • css-赛博朋克风动画组件

    css 赛博朋克风动画组件 目录 文章目录 前言 结果展示 代码 前言 Tutorials收费课程中的一种实现 实现思路 先绘制盒子 制作动画 通过颜色位置变化来实现流转 webkit box reflect below 2px linea
  • 李宏毅机器学习课程笔记1:Regression、Error、Gradient Descent

    台湾大学李宏毅老师的机器学习课程是一份非常好的ML DL入门资料 李宏毅老师将课程录像上传到了YouTube 地址 NTUEE ML 2016 这篇文章是学习本课程第1 3课所做的笔记和自己的理解 Lecture 1 Regression
  • android开发:gradle 3.X中dependencies依赖api、compile和implementation的区别

    参考 Android Studio3 X中dependencies依赖api compile和implementation的区别 注意 文中的Android Studio3 X应该是gradle3 x
  • golang数据结构初探之动态数组slice

    动态数组slice slice 又称动态数组 依托于数组实现 可以方便的进行扩容和传递 实际使用时比数组更灵活 但正是因为灵活 实际使用时更容易出错 避免出错的最好方法便是了解其实现原理 特性速览 初始化 声明和初始化切片的方式主要有以下几