【低成本扩容】动态扩容实战指南

面对扩容操作时,下面这种操作是否也会迷惑你?下面来为大家解惑~

size_t newcapacity = 2*_capacity > (_size + len)?2*_capacity:(_size+len);
//len为即将插入的字符串有效字符个数//_size为当前字符串有效字符个数//_capacity为当前容量大小//newcapacity为扩容后容量大小

一、为什么需要动态扩容?

静态数组(如 C 语言的int arr[10])的容量是固定的,一旦存储的元素数量超过容量,就会发生溢出。而动态数组(如 C++ 的vector、Java 的ArrayList)需要支持灵活添加元素,因此必须在容量不足时自动扩容。

但扩容的过程是 "昂贵" 的:

  • 需要申请一块更大的内存空间
  • 把原有元素复制到新空间
  • 释放旧空间的内存

如果每次添加元素都只扩容 1 个单位,会导致频繁扩容(添加 n 个元素可能需要 n 次扩容),时间复杂度会退化到O(n²)(每次复制元素的成本累积)。

二、为什么选择 "翻倍扩容"(2 * _capacity)?

这是一种避免频繁扩容的优化策略:

  • 每次扩容时直接将容量翻倍,能保证后续多次添加元素都不需要再次扩容
  • 从数学上可以证明,这种策略能让单次添加元素的平均时间复杂度降为O(1)( amortized O(1))

例如:

  • 初始容量为 1,添加 1 个元素后扩容到 2
  • 再添加 1 个元素(总 2 个),下次添加时扩容到 4
  • 再添加 2 个元素(总 4 个),下次添加时扩容到 8
  • 以此类推,每扩容一次,能支持的新增元素数量也翻倍

这种 "批量扩容" 的思路,用少量的空间冗余换取了时间效率的极大提升。

三、为什么还要考虑 "_size + len"?

当一次性添加大量元素(len很大)时,如果固执地用 "翻倍扩容" 可能导致空间浪费

  • 假设当前容量_capacity=100,已存储_size=50个元素
  • 现在要一次性添加len=200个元素,此时_size + len = 250
  • 如果按翻倍扩容(2*100=200),容量仍然不够,还需要再次扩容
  • 因此直接扩容到_size + len(250),既满足需求又避免不必要的空间浪费

这是一种 "按需扩容" 的补充策略,防止在批量添加元素时出现 "扩容不足" 或 "过度扩容" 的问题。

四、代码本质

  • 小规模添加元素时,用 "翻倍扩容" 减少扩容次数,优化时间效率。
  • 大规模添加元素时,用 "按需扩容" 确保刚好够用,优化空间效率。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.pswp.cn/web/93404.shtml
繁体地址,请注明出处:http://hk.pswp.cn/web/93404.shtml

如若内容造成侵权/违法违规/事实不符,请联系多彩编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Product Hunt 每日热榜 | 2025-08-14

1. Autumn 标语:为AI初创公司简化的Stripe服务 介绍:Autumn帮助AI初创公司通过只需三个API调用来定价、计量和控制使用情况。基于Stripe搭建,它可以在一个地方管理订阅、使用情况和访问权限。无需复杂的webhooks或后端逻辑,非常…

Scrapy + Django爬虫可视化项目实战(二) 详细版

系列文章 Scrapy + Django爬虫可视化项目实战(一)_django scrapy-CSDN博客 实现技术 Scrapy Django Echarts 引言 可视化部分需要读者具备一定的Django基础!!! 上一个文章我们已经实现了爬取景点的数据,那么接下来就是根据爬取到的数据进行可视化 一、环境搭建 (一) 创…

选择式与生成式超启发算法总结

这里写目录标题Selection HHGeneration HHGPHH示例存在大量针对特定问题设计的启发式算法,近年来学术界提出了一个关键问题:如何选择最合适的启发式方法。这一问题推动了超启发式(hyper-heuristic)方法的研究发展。超启发式是一种…

NetBIOS 设置

在 Windows 系统中,WINS (Windows Internet Name Service) 和 NetBIOS 紧密相关,主要用于 NetBIOS 名称解析(将计算机名转换为 IP 地址)。WINS 是一个动态数据库,类似于 DNS,但专门用于 NetBIOS 名称解析,适用于早期 Windows 网络(如 Windows NT/2000/XP)。 1. 查看 N…

vue2 + SimpleMindMap 制作思维导图

vue2 SimpleMindMap 制作思维导图 该代码包含SimpleMindMap已知的所有功能&#xff0c;有需要的小伙伴可自行copy&#xff0c;框架使用el-ementui。其中有些图标是阿里巴巴矢量图的图片&#xff0c;可自行进行替换。保姆级教程 以下是vue文件&#xff1a; <template><…

Discord x Pulsar: 使用 Pulsar、Flink 和 Iceberg 搭建流式机器学习平台

本文整理自 Discord 机器学习工程师 David Christle 在 Pulsar Summit NA 上的演讲内容&#xff0c;一起来看 Discord 是如何基于 Pulsar 实现兼顾安全和个性化功能的实时流式机器学习平台的&#xff5e;1. 背景Discord 是一个实时⾳视频通信平台&#xff0c;⽀持⽂本/语⾳/视频…

【数据结构入门】二叉树(2)

目录 1.二叉树遍历顺序 1.1 前序&#xff08;先根&#xff09;遍历 1.2 中序&#xff08;中根&#xff09;遍历 1.3 后序&#xff08;后根&#xff09;遍历 1.4 层序遍历 1.5 深度优先遍历&广度优先遍历 2.二叉树的遍历 2.1 前根遍历&#xff08;递归&#xff09; …

【电机参数】电压、电流、转速标幺化推算过程

【电机参数】电压、电流、转速标幺化推算过程 文章目录[TOC](文章目录)前言一、标幺化目的——优化计算二、Q15与标幺化的关系三、标幺值计算1.电压标幺值2.电流标幺值3.转速标幺值四、参考资料总结前言 一、标幺化目的——优化计算 不同物理量的量纲和数值范围差异巨大&#…

v-scale-scree: 根据屏幕尺寸缩放内容

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》、《前端求职突破计划》 &#x1f35a; 蓝桥云课签约作者、…

linux设备驱动之字符设备驱动

一、cdev结构体‌成员/功能‌‌说明‌‌相关操作函数/宏‌‌kobj‌内嵌的kobject对象&#xff0c;用于Linux设备模型管理&#xff0c;实现引用计数和sysfs接口kobject_init()‌owner‌指向拥有该结构体的模块指针&#xff08;通常为THIS_MODULE&#xff09;&#xff0c;防止模块…

★CentOS:MySQL数据备份

一、cp 命令备份特点&#xff1a;优点&#xff1a;备份恢复数据快&#xff1a;直接复制文件&#xff0c;无需进行数据转换和复杂的处理&#xff0c;因此备份恢复速度非常快缺点&#xff1a;需要停止数据库服务&#xff0c;灵活性差&#xff0c;占用空间大&#xff0c;可移植性差…

Python代码规范与静态检查(ruff/black/mypy + pyproject.toml + Makefile)自动化工具链介绍

文章目录**1. 核心工具的作用****(1) black&#xff1a;代码格式化工具****(2) ruff&#xff1a;代码质量检查工具****(3) mypy&#xff1a;静态类型检查工具****2. pyproject.toml&#xff1a;统一配置中心****示例配置**&#xff08;pyproject.toml&#xff09;&#xff1a;*…

软件需求管理过程详解

需求管理过程需求管理是软件工程和系统开发中的核心过程&#xff0c;它确保项目始终围绕正确、稳定且可追溯的需求进行。在复杂系统开发中&#xff0c;需求往往动态变化&#xff0c;需求管理通过系统化的方法控制变更、维护版本、建立追溯关系&#xff0c;从而降低项目风险、保…

MySQL性能优化实战指南:从入门到精通的完整优化体系

MySQL性能优化实战指南&#xff1a;从入门到精通的完整优化体系&#x1f680; 前言&#xff1a;在当今数据驱动的时代&#xff0c;MySQL作为世界上最流行的开源关系型数据库&#xff0c;其性能优化能力直接决定了应用系统的响应速度和用户体验。本文将从多个维度深入探讨MySQL优…

KingbaseES主备读写分离集群安装教程

首先我们先要找数据库集群安装软件和脚本。这里我事先安装一台单机。 [rootlocalhost zip]# mkdir -p /home/kingbase/software [rootlocalhost zip]# scp -r * /home/kingbase/software/ #安装软件和脚本在单机版本的/opt/Kingbase/ES/V9/ClientTools/guitools/DeployTools/z…

electron程序适配loongArch64

一、原始项目 1.原始程序适配arm&#xff0c;x86国产linux设备;新增需求适配loongArch64麒麟v10sp1。 2.原始devDependencies "devDependencies": {"electron": "^17.2.0","electron-builder": "^23.0.3",}二、可能遇到的问…

窗口系统(windowing system)的架构思考

我想做一个通用窗口系统&#xff0c;窗口、控件等&#xff0c;一切都抽象成树形结构的层叠矩形块&#xff0c;可支持半透明、模糊等混合选项&#xff0c;那么每个窗口是不是需要一块存储区&#xff1f;我之前的代码为了计算模糊&#xff0c;还不止一块&#xff0c;要三块。那么…

极简工具箱:安卓工具箱合集

软件介绍 极简工具箱是一个安卓工具箱合集软件&#xff1b;软件支持安卓。 它支持将近 400 个实用功能&#xff0c;支持将近 40 款单机游戏&#xff0c;提供 140 多个实用网站导航&#xff0c;包括电子书导航、学习导航、设计导航、产品经理导航、大数据导航、文档格式转换、…

TOGAF八步一法笔记2

业务需求和验收标准一旦方向确定&#xff0c;接下来的关键就是&#xff1a;创建业务需求、明确验收标准当“预备阶段”完成&#xff0c;能力愿景和范围被管理层确认后&#xff0c;我们正式进入能力建设的“实施轨道”。而这个轨道的起点&#xff0c;是两个核心动作&#xff1a;…

各种读取csv文件的工具性能比较

在翻阅calamine作者的quick-csv存储库时无意中看到有个10年前的csv读取比赛, 把比赛选手源程序下载下来测试看到底有多快。 git clone https://bitbucket.org/ewanhiggs/csv-game.git这些源程序只有比赛程序本身&#xff0c;依赖的文件有的在主页&#xff0c;有的在makefile中…