C++八股 —— vector底层

vector底层为动态数组

1. 类构成

   • class vector : protected _Vector_base
   • _Vector_base:
     • _M_start：容器元素开始的位置
     • _M_finish：容器元素结束的位置
     • _M_end_of_storage：动态内存最后一个元素的下一个位置

2. 构造函数

   • 无参构造

     根据性能优先规则，没有申请动态内存

   • 初始化元素个数的构造

     申请了动态内存，避免多次申请影响性能

3. 插入元素

   先检查空间，不够则申请内存翻倍

   • 插入到最后
   • 插入到非最后：待插入位置之后的元素往后移一位，然后插入

4. 删除元素

   删除元素不会释放已申请的内存

   • 删除最后：_M_finish往前移动一位
   • 删除非最后：待删除位置之后的元素往前移一位，然后执行“删除最后”操作

5. 读取元素

   返回的是具体元素的引用

   • 操作符[]
   • at()：比[]多一步越界检查操作

6. 修改元素

   • 不支持直接修改某个位置的元素
   • 通过读取元素，获取引用，然后修改
   • 先删除后插入

7. 释放空间

   • swap一个空容器
   • C++ 11：shrink_to_fit 将容器的空间收缩到容器大小。先clear()将容器清空（不会释放空间），然后收缩空间大小

参考：【C++面试题】vector底层实现原理_哔哩哔哩_bilibili

fill和assign

1. std::fill（算法库函数）

   • 功能：将指定范围内的元素逐个赋值为给定值。

   • 语法：

     #include <algorithm>
     std::fill(iterator begin, iterator end, value);
     

   • 行为

     • 遍历 [begin, end) 范围内的元素，将每个元素赋值为 value。
     • 不改变容器大小，仅修改已有元素的值。

   • 适用容器：所有支持迭代器的容器（如 vector, array, deque, 原生数组等）。

   • 优点：

     • 高效：直接覆盖现有元素，无需重新分配内存。
     • 灵活性：可局部修改（例如只修改某一部分元素）。

   • 缺点：需要确保目标范围有效（例如不越界）。

示例：

std::vector<int> vec = {1, 2, 3, 4};
std::fill(vec.begin(), vec.end(), 0); // vec → {0, 0, 0, 0}
std::fill(vec.begin() + 1, vec.end() - 1, 5); // vec → {0, 5, 5, 0}

2. assign（容器成员函数）

   • 功能：替换容器的内容，可以指定新元素的数量和值，或从其他容器/迭代器复制数据。

   • 语法：

     // 用 n 个 value 替换容器内容
     container.assign(n, value);
     
     // 用迭代器范围 [begin, end) 替换容器内容
     container.assign(begin, end);
     

   • 行为：

     • 销毁原有元素，重新分配内存（可能触发内存重新申请）。
     • 新内容可以是重复值或来自其他容器。

   • 适用容器：支持动态修改的序列容器（如 vector, deque, list, string）。

   • 优点：

     • 简洁性：一行代码即可替换整个容器的内容。
     • 灵活性：支持从不同数据源（如另一个容器或初始化列表）赋值。

   • 缺点：

     • 潜在性能开销：若新内容大小与原有内容不同，可能触发内存重分配。
     • 数据丢失：原有内容被完全覆盖。

示例：

std::vector<int> vec = {1, 2, 3, 4};
vec.assign(3, 10);       // vec → {10, 10, 10}（大小变为 3）
vec.assign({5, 6, 7});   // vec → {5, 6, 7}（用初始化列表替换）

3. 关键区别

4. 如何选择

• 使用 std::fill 当：
  • 需要保留容器原有结构（如大小不变）。
  • 仅需修改部分或全部元素的值（例如重置为默认值）。
  • 避免内存重分配（对性能敏感的场景）。
• 使用 assign 当：
  • 需要完全替换容器内容（例如用新数据覆盖旧数据）。
  • 需要调整容器大小（例如从 n 个元素变为 m 个元素）。
  • 从其他容器或初始化列表快速赋值。