请解释 C++ 中 vector 的内部实现原理,并阐述 resize 与 reserve 之间的区别,以及 size 与 capacity 的区别。
考察说明
考查对 vector 内存管理机制的理解,以及容量和大小相关操作的区别。
回答思路
- 【回答框架 1】vector 是动态数组,内部管理一块连续内存,通过三个指针或迭代器实现:start、finish、end_of_storage,分别指向已使用空间开头、已使用空间末尾和已分配空间末尾。
- 【回答框架 2】size 表示当前已存储的元素个数,capacity 表示当前已分配内存能容纳的元素个数。resize 改变 size,若新 size 大于 capacity,会触发重新分配。reserve 只改变 capacity,不改变 size。
- 【回答框架 3】当插入元素导致 size 超过 capacity 时,vector 会重新分配更大的内存(通常为原来的 2 倍),移动或拷贝旧元素到新内存,并释放旧内存。
- 【回答框架 4】reserve 的作用是预留空间,避免多次重新分配,提高性能。resize 用于调整 size,新元素会进行默认初始化或赋值。
- 【关键点 1】vector 内部是连续内存,支持随机访问,但插入删除可能移动元素。
- 【关键点 2】size 是已用元素数,capacity 是已分配容量,capacity >= size。
- 【关键点 3】resize 改变 size,reserve 只改变 capacity。
- 【关键点 4】重新分配时,迭代器、指针和引用会失效。
- 【关键点 5】预留空间用 reserve,调整大小用 resize。
- 【易错点 1】误认为 reserve 会改变 size。
- 【易错点 2】忽视重新分配导致的迭代器失效。
- 【易错点 3】对 capacity 增长的精确倍数不确定,通常实现为 2 倍但非标准。