【低成本擴容】動態擴容實戰指南

面對擴容操作時,下面這種操作是否也會迷惑你?下面來為大家解惑~

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(n2)(每次復制元素的成本累積)。

二、為什么選擇 "翻倍擴容"(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
英文地址,請注明出處:http://en.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中…