面對擴容操作時,下面這種操作是否也會迷惑你?下面來為大家解惑~
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),既滿足需求又避免不必要的空間浪費
這是一種 "按需擴容" 的補充策略,防止在批量添加元素時出現 "擴容不足" 或 "過度擴容" 的問題。
四、代碼本質
- 小規模添加元素時,用 "翻倍擴容" 減少擴容次數,優化時間效率。
- 大規模添加元素時,用 "按需擴容" 確保剛好夠用,優化空間效率。