1. Vector 的本质

• 定义：Vector 是一个动态数组（Dynamic Array）。
• 对比 Array：
  • std::array (或 C 数组)：静态空间。一旦定义，大小固定，无法改变。
  • std::vector：动态空间。随着元素加入，内部会自动扩充空间来容纳新元素。
• 关键点：Vector 的扩充不是在原空间后面“接”一段内存（因为堆空间后面可能被占用了），而是**“申请新空间 -> 拷贝数据 -> 释放旧空间”**的过程。

2. 核心数据结构 (3个指针)

Vector 对象本身非常小（通常只占 3 个指针的大小），它只负责管理堆内存的边界。

template <class T, class Alloc = alloc>
class vector {
    ...
protected:
    iterator start;           // 指向目前已使用空间的头
    iterator finish;          // 指向目前已使用空间的尾 (最后一个元素的下一个位置)
    iterator end_of_storage;  // 指向目前可用空间(Capacity)的尾
    ...
};

• size() (元素个数) = finish - start
• capacity() (容量) = end_of_storage - start
• empty() = start == finish

3. 迭代器 (Iterators)

• 类型：Vector 维护的是连续线性空间，所以它的迭代器就是普通指针 (T*)。
• 能力：属于 Random Access Iterator（随机访问迭代器）。
  • 支持 it + n, it - n, it[n]，it1 - it2。
  • 这也是为什么 std::sort 可以直接用于 vector（快排需要随机访问）。

4. 内存扩容机制 (The Growth Strategy)

当调用 push_back 且 size() == capacity() 时，会触发扩容：

1. 计算新容量：
   • 如果旧容量为 0，则新容量为 1。
   • 否则，新容量 = 旧容量 × 2 (SGI STL 实现)。
   • (注：Visual Studio 的 PJ STL 实现通常是 1.5 倍)。
2. 分配新空间：调用配置器 (allocator) 分配一块大小为新容量的连续内存。
3. 数据迁移：
   • 将旧内存中的数据拷贝（Copy）到新内存。
   • (C++11 之后优化为 Move，效率更高)。
4. 构造新元素：在新内存的 finish 位置构造新插入的元素。
5. 释放旧空间：
   • 调用析构函数销毁旧对象。
   • 释放旧内存块 (deallocate)。
6. 更新指针：调整 start, finish, end_of_storage 指向新地址。

为什么是成倍扩容而不是每次 +10？

答：为了保证均摊时间复杂度 (Amortized Complexity) 为 O(1)。如果固定增加，扩容次数太多，总复杂度退化为 O(N^2)。

5. 元素操作 (Insert & Erase)

• pop_back()：
  • 调整指针 finish--。
  • 销毁该位置的对象 (destroy)。
  • 注意：pop_back 不会释放内存（Capacity 不变），只会减小 Size。
• erase(iterator position)：
  • 如果删除的不是最后一个元素，需要将 position 之后的所有元素向前移动（拷贝/赋值）。
  • finish--。
  • 销毁尾部多余的那个对象。
• insert(iterator position, const T& x)：
  • 如果备用空间足够：将 position 之后的元素向后移动，腾出位置放入 x。
  • 如果备用空间不足：触发扩容机制，并在新内存的对应位置插入 x。

6. 迭代器失效 (Iterator Invalidation)

这是使用 Vector 最容易出的 Bug，也是源码剖析的重点结论：

1. 插入导致失效：
   • 如果发生了扩容：所有指向旧内存的迭代器、指针、引用全部失效。
   • 如果未发生扩容：插入点之后的迭代器失效（因为元素被移动了）。
2. 删除导致失效：
   • erase(pos) 会导致指向 pos 及其之后的所有迭代器失效（数据前移覆盖了）。
   • erase 通常会返回下一个有效迭代器，用于循环中安全删除。

vector 核心操作拆解

一、 push_back

“push_back 是 O(1) 吗？” 答：“平摊是 O(1)，但单次操作可能是 O(1) 也可能是 O(N)。”

情况 A：还有备用空间 (finish != end_of_storage)

这是最快的情况，真的是 O(1)。

1. 构造：在 finish 指向的内存位置，调用 construct(finish, x)（即 placement new）。
2. 移动指针：finish 指针向后移动一格 (++finish)。

情况 B：没有备用空间 (finish == end_of_storage)

这是触发“大搬家”的情况。

1. 计算新容量：
   • const size_type old_size = size();
   • const size_type len = old_size != 0 ? 2 * old_size : 1; (两倍扩容策略)。
2. 分配新空间 (Allocate)：
   • 调用 allocator::allocate(len) 在堆上申请一块全新的大内存。
3. 数据迁移 (Copy)：
   • 调用 uninitialized_copy，将旧地址 [start, finish) 的所有元素拷贝到新地址。
   • (C++11 优化：如果元素支持移动，这里会调用 std::move， 将所有权转移而非深拷贝)_。
4. 构造新元素：
   • 在新地址的尾部（即原 finish 对应的相对位置），构造新元素 x。
5. 释放旧空间 (Deallocate)：
   • 析构：调用 destroy 析构旧地址上的所有对象。
   • 释放：调用 deallocate 归还旧内存给操作系统。
6. 重置指针：
   • start 指向新内存头。
   • finish 指向新元素的下一个位置。
   • end_of_storage 指向新内存的尾。

二、insert

有三种情况：之所以会有“三种情况”，是因为 STL 为了极致的效率，必须严格区分以下两个概念：

1. 赋值 (Assignment)：在已构造的内存上填值（用 operator=）。
2. 构造 (Construction)：在未初始化的内存上填值（用 placement new / uninitialized_copy）。 我们假设你要在 position 位置插入 n 个新元素 x。 这时候，vector 会根据 “剩余空间够不够” 以及 “插入点后的元素搬运后落在哪里”，分出三种情况。 我们定义一个变量：elems_after = finish - position （插入点之后，原本有多少个老元素需要被挪动）。

第一种情况：备用空间不足 (Capacity < Size + n)

这是最简单、最暴力的“整体搬家”。 既然当前这块地皮已经塞不下新加入的 n 个元素了：

1. 申请新地皮：开辟一块更大的新内存（通常是旧大小的 2 倍或 +n）。
2. 搬运 Part 1：把 start 到 position 之间的老元素拷贝到新地址。
3. 填入新元素：在新地址接着构造 n 个 x。
4. 搬运 Part 2：把 position 到 finish 之间的老元素拷贝到新地址的后面。
5. 拆迁：析构并释放旧内存，更新指针。

第二种情况：备用空间足够，且 n <= elems_after

这是“局部搬家”的简单模式。 这意味着：插入点后面的老元素非常多，比新增的 n 个元素还要多。 当你把这些老元素往后推 n 格时，只有一部分会被推到“未初始化区”，另一部分依然留在“已初始化区”。 操作步骤：

1. 先处理尾部：把 finish - n 到 finish 的这些老元素，搬运到 finish 之后的未初始化内存中（用构造）。
   • 为什么是 n 个？因为你要腾出 n 个位置，所以整体要往后移 n 步。
2. 再处理中间：把 position 到 finish - n 的老元素，往后挪 n 步，覆盖掉刚刚搬走的那部分元素（用赋值）。
3. 最后填入：在 position 处填入 n 个新元素 x（用赋值，因为这里原本就有对象）。

图解逻辑：

内存状态：[ 已初始化区 (A B C D E) ] [ 未初始化区 _ _ _ ]
操作：在 B 后面插入 1 个 X (n=1, elems_after=3(CDE))。 1 <= 3。

1. 原始： A B C D E | _ _ _
2. 搬运尾部(E)： A B C D E | E _ _  (E 构造在未初始化区)
3. 挪动中间(CD)：A B C D D | E _ _  (D 覆盖 E)
               A B C C D | E _ _  (C 覆盖 D)
4. 填入新值(X)： A B X C D | E _ _  (X 覆盖 C)

第三种情况：备用空间足够，且 n > elems_after

这是“局部搬家”的复杂模式。 这意味着：插入点后面的老元素很少，新增的 n 个元素很多。 即使你把老元素全部往后推，它们也全部都会落入“未初始化区”。而且，新增的 n 个元素，有一部分也会落入“未初始化区”。 操作步骤：

1. 先填一部分新元素：因为新元素太多了，先在 finish 之后的未初始化区，构造 n - elems_after 个新元素 x。
2. 搬运老元素：把 position 到 finish 的所有老元素，直接搬运到刚刚填好的新元素后面（全部去未初始化区，用构造）。
3. 填满剩余新元素：现在 position 到 finish 这段老元素已经搬走了，变成了旧房子，直接用剩下的新元素 x 覆盖进去（用赋值）。 图解逻辑：

内存状态：[ 已初始化区 (A B C) ] [ 未初始化区 _ _ _ _ _ ]
操作：在 A 后面插入 3 个 X (n=3, elems_after=2(BC))。 3 > 2。

1. 原始： A B C | _ _ _ _ _
2. 填出界的新元素：A B C | X _ _ _ _ (先在未初始化区构造 3-2=1 个 X)
3. 搬运老元素(BC)：A B C | X B C _ _ (把 B,C 搬到 X 后面)
4. 填入剩余新元素：A X X | X B C _ _ (用剩下的 2 个 X 覆盖原来的 B,C)

为什么要搞这么复杂？

你可能会问：“为什么不直接把所有东西往后挪 n 位，然后把空位填满不就完了吗？” 答案是：为了省钱（性能）。

• 赋值 (Assignment) 通常比 构造 (Construction) 快，特别是对于内置类型（int, float），赋值就是汇编级的 mov 指令。
• STL 尽最大努力利用已存在的对象空间进行赋值操作，而不是盲目地销毁再重建。
• 通过区分这三种情况，STL 保证了：
  1. 绝不对未初始化的内存进行赋值（会导致崩溃）。
  2. 绝不对已初始化的内存进行重复构造（浪费性能）。 记忆口诀：
• 空间不够：整体搬家。
• 空间够，老元素多：老元素自己覆盖自己，只有尾巴去新地盘。
• 空间够，新元素多：新元素太强势，把老元素全部挤到新地盘去了。

三、 erase

erase 的难点在于：它不能真的把中间挖个洞，而是要把后面的元素整体前移覆盖。

情况 A：删除单个元素 erase(position)

假设内存：A B C D E，我们要删除 C (position 指向 C)。

1. 判断位置：如果 position + 1 != finish（说明删的不是最后一个元素）。
2. 整体左移 (Copy Over)：
   • 将 position + 1 到 finish 之间的元素（即 D E），向前拷贝到 position 开始的位置。
   • 内存变化：
     • 原始：A B [C] D E
     • 拷贝后：A B [D] [E] E (注意最后那个 E 是残留的尸体)。
3. 销毁尾部：
   • 指针 finish 向前移动一格 (--finish)。
   • 调用 destroy 销毁原来的那个 finish 位置的对象（即残留的 E）。
   • 最终状态：A B D E。

情况 B：删除区间 erase(first, last)

假设内存：A B C D E F G，我们要删除 C D E (first指C, last指F)。

1. 计算搬运量：计算 last 之后还有多少个元素需要保留。
2. 整体平移：
   • 调用 copy(last, finish, first)。
   • 意思是：把 F G 搬过来，覆盖掉 C D。
   • 内存变化：A B [F] [G] E F G (后三个是残留)。
3. 批量销毁：
   • 新的 finish 应该在 start + (old_size - delete_count) 的位置。
   • 调用 destroy(new_finish, old_finish)，把后面残留的 E F G 全部析构。

核心结论：erase 永远不会释放内存（Capacity 不变），它只是把有效数据往前挤，然后销毁尾部的多余对象。

四、 pop_back

很多人以为 pop_back 很复杂，其实它是 erase 的简化版。

1. 移动指针：--finish。
2. 销毁对象：destroy(finish)。

硬核细节：

• 它完全不涉及内存搬运。
• 它绝对不会让 capacity 变小。即使你把 100万个元素 pop 剩 1 个，vector 依然占用 100万个元素的内存空间。
• 如何释放内存？ 面试必考题：使用 shrink_to_fit() 或者 swap 技巧。

五、 resize vs reserve (混淆粉碎机)

这两个函数是初学者最容易搞混的，源码逻辑完全不同。

1. reserve(n) —— 只管房产证 (Capacity)

• 逻辑：
  • 如果 n <= capacity()：啥也不做。
  • 如果 n > capacity()：触发扩容（分配新内存 -> 拷贝 -> 释放旧内存）。
• 关键点：它不创建任何对象。finish 指针不动，size() 不变。

2. resize(n, x) —— 既管房产也管装修 (Size)

这分为三种情况：

• 情况 A：n < size() (变小)
  • 不需要动内存。
  • 直接从 start + n 到 finish 这一段区间，全部调用 destroy。
  • 移动 finish 指针。
• 情况 B：size() < n <= capacity() (变大，但有余粮)
  • 在 finish 到 start + n 这段未初始化的内存上，调用 uninitialized_fill 填充默认值 x。
  • 移动 finish 指针。
• 情况 C：n > capacity() (变得超级大)
  • 先触发扩容机制（类似 reserve）。
  • 然后在新内存的后半段构造对象。

总结

"Vector 其实就是披着对象外衣的三个指针。它维护了一段连续内存。 它的方便之处在于自动扩容，但代价是扩容时的深拷贝。 所以，如果在已知数据量的情况下，使用 reserve() 预分配内存，可以避免扩容带来的性能损耗，这是优化 Vector 最直接的手段。"