在 1.1 线性表抽象数据类型 中，我们确立了线性表的逻辑模型与 List ADT 接口契约，并看到计算机物理内存本质上是一排带连续地址编号的字节盒子。

本节我们将探讨线性表的第一种物理实现——顺序表（Sequential List / 动态数组 Vector），重点回答四个核心问题：

1. 为什么物理连续内存能够带来 $O(1)$ 随机存取，以及 CPU Cache 为何能加速连续访问？
2. 静态数组容量固定，动态数组如何实现动态扩容？
3. 为什么加法扩容开销高昂，而乘法 2 倍扩容能达成摊还 $O(1)$？
4. 为什么 50% 对称缩容会引发高频反复重分配，25% 缩容阈值如何消除抖动（Thrashing）？

---

学习目标

完成本节后，你应该能够：

• 理解物理寻址：根据基地址和元素大小推导出任意下标的物理内存地址公式，解释 $O(1)$ 随机存取的底层硬件成因；
• 掌握缓存加速：从 CPU Cache 空间局部性（Spatial Locality）解释为什么顺序表遍历常数小、访问效率高；
• 对比扩容策略：对比加法扩容与乘法扩容的代码实现，解释为什么加法扩容会导致 $O(n^2)$ 的累积复制开销；
• 掌握聚合分析：说明为什么普通最坏情况分析会“失真”，并运用聚合分析法（Aggregate Analysis）严密证明 2 倍扩容的摊还 $O(1)$；
• 分析抖动成因：分析 50% 对称缩容引发“性能抖动（Thrashing）”的机制，说明 25% 延迟缩容阈值如何通过滞后阻尼消除高频振荡；
• 实现核心操作：正确编写具备完整动态扩缩容、边界防御与平移逻辑的顺序表代码。

---

2.1 物理连续性与寻址原理

2.1.1 存储结构与类声明

面对内存中一排排带编号的字节盒子，要把一维逻辑序列 $L=(a_0,a_1,\dots ,a_{n-1})$ 存入计算机，最直观的存储方式是：将数据元素连续存放在物理内存中。

DEF顺序表 (Sequential List)

顺序表 (Sequential List) 是指用一段物理地址连续的存储单元依次存放线性表数据元素的数据结构。

逻辑序列中的元素按相同次序映射到地址连续、间隔为 L 字节的物理存储单元

为了在程序中管理这段物理连续内存并实现 1.1 节定义的 List ADT 接口契约，顺序表类（通常称为 Vector）需要维护三个核心成员变量：

• _data：指向堆内存连续存储块的首地址指针；
• _size：当前已保存的有效元素数量（逻辑长度）；
• _capacity：底层实际分配的物理内存总容量。

其完整的 C++ 类声明骨架如下：

#pragma once
#include "list-adt.hpp"

const int DEFAULT_CAPACITY = 8;

template <typename T>
class Vector : public List<T> {
private:
    T*  _data;      // 物理连续存储空间首地址指针
    int _size;      // 当前有效元素数量 (逻辑长度)
    int _capacity;  // 实际分配的内存容量 (物理空间)

    // 私有辅助方法：动态容量管理
    void expand();  // 空间耗尽时扩容
    void shrink();  // 空间过剩时缩容

public:
    // 构造与析构
    Vector(int cap = DEFAULT_CAPACITY);
    virtual ~Vector();

    // 1. 访问与遍历 (实现 List 接口)
    int size() const override { return _size; }
    bool isEmpty() const override { return _size == 0; }
    T get(int index) const override;
    T& operator[](int index);
    const T& operator[](int index) const;

    // 2. 查找与更新 (实现 List 接口)
    int find(const T& value) const override;
    void set(int index, const T& elem) override;

    // 3. 插入与删除 (实现 List 接口)
    void insert(int index, const T& elem) override;
    T remove(int index) override;

    // 尾部快捷操作 (基于 insert/remove)
    void push_back(const T& elem) { insert(_size, elem); }
    T pop_back() { return remove(_size - 1); }
};

vector.hpp

---

2.1.2 寻址公式与随机访问

因为物理内存是严格连续且每个元素占用相同字节数 $L$（sizeof(T)），任意第 $i$ 个元素 $a_i$ 的物理内存地址可以直接通过初等数学公式计算：

$$Loc(a_i)=Loc(a_0)+i\times L$$

PROP寻址性质 · 随机存取 (Random Access)

CPU 的算术逻辑单元（ALU）用一条基址变址寻址指令（如 x86 的 [base + index * scale]），只需 1 次乘法 + 1 次加法 就能在单个时钟周期内直达目标地址。无论表长 $n$ 的规模多大，访问任意位置耗时恒定，时间复杂度为严格的 $O(1)$。

---

2.1.3 缓存局部性与遍历加速

正如在 0.3 从内存视角理解复杂度 中所述，现代 CPU 访问主存时会以 Cache Line（通常 64 字节） 为单位批量加载连续内存。

IDEA缓存加速 · 顺序表的空间局部性红利

得益于空间局部性 (Spatial Locality)，当 CPU 访问 $a_0$ 时，硬件会自动将同一 Cache Line 内的后续连续元素预载进高速缓存。因此，顺序表的顺序遍历能获得极高的缓存命中率，实际运行常数极小。

---

2.2 动态扩容与缩容机制

2.2.1 扩容的物理必要性

物理连续性提供了 $O(1)$ 的随机存取性能，但也带来了一个约束：内存空间的不可就地扩展。

在静态数组中，如果你向操作系统申请了 10 个连续内存盒子，第 11 个盒子可能已经被系统的其他变量占用了。当第 11 个数据到来时，你无法在原地向后延长空间。

为了解决这一矛盾，工业级线性表必须从“静态数组”跨越到 动态顺序表（Dynamic Array / Vector）。

PROP动态数组不变量 (Class Invariant)

在任何操作发生的前后，顺序表必须恒满足：

$$0\le \text{\_size}\le \text{\_capacity}$$

当 $\text{\_size}==\text{\_capacity}$ 时，容量耗尽，必须触发私有辅助函数 expand() 执行扩容机制：向操作系统堆内存申请一块更大的新空间，将原数据全量拷贝过去，释放旧空间，并让 _data 指向新空间。

---

2.2.2 加法扩容与乘法扩容

在实现私有辅助函数 expand() 时，核心抉择在于新容量（new_capacity）的增长策略。业界存在两种典型的设计思路：

策略 A：加法扩容（Fixed Increment / 每次固定增加 $K$）

void Vector<T>::expand() {
    int new_capacity = _capacity + INCREMENT; // 每次固定增加常数 K
    T* new_data = new T[new_capacity];
    for (int i = 0; i < _size; i++) {
        new_data[i] = _data[i];               // 全量复制旧元素
    }
    delete[] _data;                           // 释放旧内存
    _data = new_data;
    _capacity = new_capacity;
}

expand-additive.cpp

策略 B：乘法扩容（Geometric Doubling / 每次容量翻倍 $\times 2$）

void Vector<T>::expand() {
    int new_capacity = (_capacity == 0) ? DEFAULT_CAPACITY : _capacity * 2; // 翻倍扩容
    T* new_data = new T[new_capacity];
    for (int i = 0; i < _size; i++) {
        new_data[i] = _data[i];                          // 全量复制旧元素
    }
    delete[] _data;                                      // 释放旧内存
    _data = new_data;
    _capacity = new_capacity;
}

expand-multiplicative.cpp

表面上看，加法扩容每次只多要一点空间，似乎更节省内存；乘法扩容每次翻倍，看似消耗了更多空闲空间。然而，通过具体数值的手算对比，便能直观看到两种策略在累积开销上的巨大差异。

例题 1：手算两种扩容策略的复制开销

假设分别使用以下两种策略向一个初始为空的动态顺序表中连续插入 $16$ 个元素：

• 策略 A（加法扩容）：初始容量为 $4$，每次扩容固定增加 $K=4$；
• 策略 B（乘法扩容）：初始容量为 $1$，每次扩容容量翻倍（$\times 2$）。

请分别列出两种策略在插入过程中触发扩容的时机，并计算累计复制元素的总次数。

查看分析

1. 策略 A（加法扩容，每次 $+4$）

• 第 1~4 次插入：容量为 4，无需扩容，复制 0 次；
• 第 5 次插入：满载，扩容至 8，复制 4 个元素；
• 第 9 次插入：满载，扩容至 12，复制 8 个元素；
• 第 13 次插入：满载，扩容至 16，复制 12 个元素；
• 累计复制次数：$4+8+12=24$ 次。

2. 策略 B（乘法扩容，每次 $\times 2$）

• 第 1 次插入：容量为 1，无需扩容，复制 0 次；
• 第 2 次插入：满载，扩容至 2，复制 1 个元素；
• 第 3 次插入：满载，扩容至 4，复制 2 个元素；
• 第 5 次插入：满载，扩容至 8，复制 4 个元素；
• 第 9 次插入：满载，扩容至 16，复制 8 个元素；
• 累计复制次数：$1+2+4+8=15$ 次。

直观对比：在同样插入 16 个元素时，加法扩容（24 次）的搬移开销明显高于乘法扩容（15 次）。加法扩容的扩容间隔固定，每次拷贝规模线性递增；乘法扩容则成倍拉长了扩容间隔，大幅减少了累积数据搬移。

---

2.2.3 摊还分析与聚合分析法

如果我们使用传统的单次最坏情况时间复杂度 (Worst-Case Analysis) 来评估 push_back（尾部追加元素）：

• 当某一次操作恰好触发扩容时，需要拷贝 $n$ 个元素，单次耗时为 $O(n)$；
• 传统分析因此会得出结论：“push_back 的最坏时间复杂度是 $O(n)$。”

为什么这个结论严重失真？ 因为 $O(n)$ 的扩容在正常乘法扩容策略下不会频繁连续发生——两次扩容之间至少隔着 $O(n)$ 次常规插入操作。触发一次扩容后，底层留出了大量的空余槽位，紧接着的许多次插入操作都是代价极小的纯 $O(1)$ 赋值。孤立地看单次最坏情况，完全脱离了操作序列的真实运行规律。

为了科学评估由一系列连续操作组成的序列中，单次操作的真实平均成本，算法分析引入了 摊还分析 (Amortized Analysis)。

DEF摊还分析 (Amortized Analysis) 与 聚合分析法 (Aggregate Method)

• 摊还分析 (Amortized Analysis)：在最坏情况下，评估执行一个包含连续 $n$ 个操作的序列时，每个操作所分摊到的平均保证开销（摊还成本 Amortized Cost）。它不同于依赖概率假设的“平均情况分析”，具有确定性的最坏序列保证。
• 聚合分析法 (Aggregate Analysis)：摊还分析中最直接的数学计算工具。其核心思路是“先算总账，再除以次数”：先求出 $n$ 个连续操作在最坏情况下的总时间成本上界 $T(n)$，则单次操作的摊还成本定义为：

$$\text{Amortized Cost}=\frac{T(n)}{n}$$

---

2.2.4 扩容策略的渐近分析

假设我们从空数组开始，连续执行 $n$ 次 push_back 插入 $n$ 个元素。

1. 加法扩容的累积开销推导

设初始容量为 $0$，每次增加 $K$。扩容将发生在第 $K,2K,3K,\dots ,\frac{n}{K}\cdot K$ 次插入时。全量拷贝的元素总次数为等差数列求和：

$$T_{copy}(n)=K+2K+3K+\cdots +\left(\frac{n}{K}\right)K=K\cdot \frac{(1+\frac{n}{K})\frac{n}{K}}{2}\approx \frac{n^2}{2K}=O(n^2)$$

算上 $n$ 次常规写入，总代价 $T(n)=n+O(n^2)=O(n^2)$。

WARN加法扩容的累积复制开销

加法扩容单次操作的摊还成本为 $\frac{O(n^2)}{n}=O(n)$。随着数据量增长，插入操作的平均时间开销退化为线性阶，频繁扩容带来的大量元素搬移会导致效率显著降低。

2. 乘法扩容的摊还 $O(1)$ 证明

THM乘法扩容摊还定理

采用乘法几何翻倍扩容的动态顺序表，连续执行 $n$ 次尾部插入操作的总时间复杂度为 $O(n)$，单次插入的摊还时间复杂度为 $O(1)$。

PROOF乘法扩容摊还定理证明

设初始容量为 1，每次扩容为原来的 2 倍。扩容将发生在第 $1,2,4,8,\dots ,2^k$ 次插入时（其中 $2^k\le n$）。 全量拷贝的元素总次数为等比数列求和：

$$T_{copy}(n)=1+2+4+8+\cdots +2^k=\sum _{j=0}^k{2}^j=2^{k+1}-1<2n=O(n)$$

算上 $n$ 次常规写入，连续插入 $n$ 个元素的总时间开销 $T(n)<n+2n=3n=O(n)$。 单次插入的摊还成本为：

$$\text{Amortized Cost}=\frac{T(n)}{n}<\frac{3n}{n}=3=O(1)$$

证明完毕。

---

2.2.5 滞后缩容与消除抖动

有扩容自然就该有缩容。为了防止大量元素被删除后占用无效内存，我们需要在数据变少时释放多余空间。

边界缺陷：对称扩缩容

• 扩容规则：当 $\text{\_size}==\text{\_capacity}$（满载 100%）时，容量扩大为 2 倍（$200\mathrm{\%}$）；
• 缩容规则：当 $\text{\_size}==\text{\_capacity}/2$（半满 50%）时，容量立即减半（$50\mathrm{\%}$）。

在 50% 边界对称缩容会使 push_back 与 pop_back 反复触发 O(n) 的扩容、缩容和全量搬移

WARN性能抖动 (Thrashing / 颠簸)

在容量临界点附近交替执行插入与删除时，每一次操作都会触发内存重新分配与全量数据搬移，导致单次操作时间复杂度退化为 $O(n)$，形成高频的反复重分配。

改进方案：25% 滞后阻尼机制 (Hysteresis)

25% 缩容阈值与 100% 扩容阈值之间保留阻尼区，避免容量在临界点来回振荡

PROP滞后阻尼机制 (Hysteresis)

• 规则：当装载因子 $\alpha =\text{\_size}/\text{\_capacity}\le 25\mathrm{\%}$（四分之一满）时，才将容量减半到原来的 $50\mathrm{\%}$。
• 阻尼效果：缩容完成后，装载因子刚好回到 $\frac{25\mathrm{\%}}{50\mathrm{\%}}=50\mathrm{\%}$。此时无论是想继续插入直到装满（需要再加 $50\mathrm{\%}$ 的数据），还是想继续删除直到再次缩容（需要再删 $25\mathrm{\%}$ 的数据），都必须经过大量的常规操作缓冲，消除了临界振荡抖动。

其私有辅助函数 shrink() 的实现如下：

void Vector<T>::shrink() {
    if (_capacity <= DEFAULT_CAPACITY) return; // 维持基础容量
    if (_size > 0 && _size <= _capacity / 4) {
        int new_capacity = _capacity / 2;
        T* new_data = new T[new_capacity];
        for (int i = 0; i < _size; i++) {
            new_data[i] = _data[i];           // 复制剩余元素
        }
        delete[] _data;                       // 释放多余空间
        _data = new_data;
        _capacity = new_capacity;
    }
}

shrink.cpp

例题 2：分析临界交替操作的内存开销

假设某顺序表当前处于满载状态（_size = 1000, _capacity = 1000）。现对该表连续执行 1000 轮 push_back 与 pop_back 交替操作（共 2000 次增删）。

请分别计算在以下两种策略下，系统发生的堆内存重分配次数与元素累计拷贝次数：

1. 50% 对称缩容：当 _size <= _capacity / 2 时容量减半；
2. 25% 滞后缩容：当 _size <= _capacity / 4 时容量减半。

查看分析

1. 50% 对称缩容（高频重分配）

• 每次 push_back：满载触发扩容至 2000，拷贝 1000 个元素；
• 每次 pop_back：降至半满触发缩容至 1000，拷贝 1000 个元素；
• 开销统计：1000 轮交替共触发 2000 次堆内存分配，累计拷贝元素 $2000\times 1000=2,000,000$ 次（200 万次），单次操作退化为 $O(n)$。

2. 25% 滞后缩容（阻尼缓冲）

• 第 1 次 push_back：满载扩容至 2000，拷贝 1000 个元素（_size = 1001, _capacity = 2000）；
• 后续 999 轮交替：_size 处于 $[1000,1001]$ 之间，未达扩容线（2000）且远高于缩容线（$2000/4=500$），均为 $O(1)$ 常规读写；
• 开销统计：全程仅触发 1 次堆内存分配，累计拷贝元素 1000 次。

结论：25% 阈值在扩容点与缩容点之间建立了阻尼缓冲区，避免了临界点附近的反复重分配。

---

2.3 核心操作与平移代价

在完成物理寻址与容量管理后，我们可以实现 List ADT 中定义的核心接口。其中：

• size() 与 isEmpty() 仅需读取 _size 成员，耗时为 $O(1)$；
• get(index) 与 set(index, elem) 依托寻址公式直接读写 _data[index]，耗时为 $O(1)$。

接下来，我们重点剖析涉及元素搬移与查找的三个核心操作：插入 insert(index, elem)、删除 remove(index) 与按值查找 find(value)。

2.3.1 插入与倒序平移

PROP插入平移原则 · 必须倒序

在指定位置 index 插入新元素时，必须从最后一个元素 $\text{\_size}-1$ 开始向前倒序遍历到 $\text{index}$ 依次后移，为新元素腾出槽位。

void Vector<T>::insert(int index, const T& elem) {
    // 1. 前置条件越界检查: 允许在 0 到 _size 之间插入 (index == _size 为尾插)
    if (index < 0 || index > _size) {
        throw std::out_of_range("Insert index out of bounds");
    }
    
    // 2. 容量检查与动态扩容
    if (_size == _capacity) {
        expand();
    }
    
    // 3. 倒序平移: 将 [index, _size - 1] 范围内的元素向后平移一格
    for (int i = _size - 1; i >= index; i--) {
        _data[i + 1] = _data[i];
    }
    
    // 4. 写入新元素并维护不变量
    _data[index] = elem;
    _size++;
}

vector-insert.cpp

• 最好情况：尾部追加（$\text{index}=\text{\_size}$），无需移动任何元素，摊还 $O(1)$；
• 最坏情况：头部插入（$\text{index}=0$），需要平移全部 $n$ 个元素，耗时 $O(n)$；
• 平均情况：假设插入各个位置的概率均等，平均移动次数为 $\frac{1}{n+1}\sum _{i=0}^n(n-i)=\frac{n}{2}$，耗时 $O(n)$。

例题 3：追踪一段平移代码

假设顺序表当前存储的数据为 [10, 20, 30, 40]（_size = 4, _capacity = 8）。现需要在 index = 1 处插入元素 99。若执行以下代码：

for (int i = index; i < _size; i++) {
    _data[i + 1] = _data[i];
}
_data[index] = elem;
_size++;

执行完毕后，顺序表中的元素依次是什么？为什么？

查看分析

最终结果为：[10, 99, 20, 20, 20]，原有的数据 30 和 40 被覆盖丢失。

执行过程追踪：

1. i = 1：执行 _data[2] = _data[1]，_data[2] 变为 20（原有的 30 被覆盖），数组变为 [10, 20, 20, 40]；
2. i = 2：执行 _data[3] = _data[2]，此时 _data[2] 已是 20，导致 _data[3] 也被赋值为 20（原有的 40 被覆盖），数组变为 [10, 20, 20, 20]；
3. i = 3：执行 _data[4] = _data[3]，_data[4] 同样被赋值为 20，数组变为 [10, 20, 20, 20, 20]；
4. 写入新元素 _data[1] = 99，最终得到 [10, 99, 20, 20, 20]。

结论：如果平移循环采用从前向后的正序遍历，前一个元素的值会一路向后覆盖，导致后续所有数据被抹除。因此，插入平移必须严格从后向前倒序进行。

---

2.3.2 删除与正序平移

PROP删除平移原则 · 必须正序

删除指定位置 index 的元素后，原位置留出空洞，平移必须从 $\text{index}+1$ 开始向后遍历到 $\text{\_size}-1$，依次向前覆盖 _data[i-1] = _data[i]。

T Vector<T>::remove(int index) {
    // 1. 前置条件越界检查: 空表不可删，index 必须在 [0, _size - 1]
    if (index < 0 || index >= _size) {
        throw std::out_of_range("Remove index out of bounds");
    }
    
    T removed_elem = _data[index]; // 暂存被删除元素
    
    // 2. 正序平移: 将 [index + 1, _size - 1] 范围内的元素向前平移一格
    for (int i = index + 1; i < _size; i++) {
        _data[i - 1] = _data[i];
    }
    
    _size--; // 维护表长不变量
    
    // 3. 滞后缩容检查
    shrink();
    
    return removed_elem;
}

vector-remove.cpp

• 最好情况：尾部删除（$\text{index}=\text{\_size}-1$），无需移动任何元素，耗时 $O(1)$；
• 最坏情况：头部删除（$\text{index}=0$），需要平移前移剩余全部 $n-1$ 个元素，耗时 $O(n)$；
• 平均情况：平均移动次数为 $\frac{1}{n}\sum _{i=0}^{n-1}(n-1-i)=\frac{n-1}{2}$，耗时 $O(n)$。

---

2.3.3 按值查找（find）

template <typename T>
int Vector<T>::find(const T& value) const {
    for (int i = 0; i < _size; i++) {
        if (_data[i] == value) {
            return i; // 找到首个匹配项，返回其下标
        }
    }
    return -1; // 遍历结束仍未找到，安全返回 -1
}

vector-find.cpp

• 最好情况：目标元素位于表头（index = 0），仅需 1 次比对，耗时 $O(1)$；
• 最坏情况：目标元素位于表尾或不存在，需遍历全部 $n$ 个元素，耗时 $O(n)$；
• 平均情况：假设等概率分布，平均比较次数为 $\frac{n+1}{2}$（推导参见 0.2 节），耗时 $O(n)$。

知识延伸：二分查找的物理与逻辑前提

无序顺序表只能进行 $O(n)$ 线性扫描。若要使用 0.2 节 介绍的 $O(\log n)$ 二分查找（Binary Search），必须同时满足两个前提：

1. 逻辑前提（数据有序）：序列元素已预先按大小排列；
2. 物理前提（随机存取）：底层存储必须支持 $O(1)$ 访问任意中点 _data[mid]（这正是顺序表的物理特长；后续的链表因无法常数时间定位中点而无法直接二分）。

---

2.4 性能总结与物理局限

2.4.1 复杂度矩阵

O(·)顺序表核心操作复杂度矩阵

操作接口	时间复杂度 (最好)	时间复杂度 (最坏)	时间复杂度 (平均/摊还)	核心成因
get(index) / set(index, e)	$O(1)$	$O(1)$	$O(1)$	连续物理内存，地址直接公式计算
push_back(e) (尾插)	$O(1)$	$O(n)$	$O(1)$ 摊还	几何乘法扩容稀释搬移代价
pop_back() (尾删)	$O(1)$	$O(n)$	$O(1)$ 摊还	25% 延迟缩容消除抖动震荡
find(value) (无序查找)	$O(1)$	$O(n)$	$O(n)$	逐个比对，平均检查半数元素
insert(index, e) (头/中插)	$O(1)$ (尾插)	$O(n)$ (头插)	$O(n)$	维持无缝隙特征必须倒序批量平移
remove(index) (头/中删)	$O(1)$ (尾删)	$O(n)$ (头删)	$O(n)$	填补空洞必须正序批量平移

---

2.4.2 顺序表的物理局限

顺序表基于物理连续存储，其优缺点十分明确：

• 核心优势：$O(1)$ 随机存取 + CPU Cache 空间局部性硬件加速；
• 物理局限：只要涉及头部或中间的插入与删除，为了维持物理内存的无缝连续，就必须付出 $O(n)$ 的批量元素搬移代价。

如果业务场景需要频繁在头部或任意中间位置插入、删除数据，顺序表的平移开销将成为系统的性能瓶颈。要打破这一桎梏，就必须放弃物理连续的假设，转向允许节点离散存放、通过指针链接的结构——1.3 链表与演进设计。

---

不变量与易错点清单

实现顺序表时，不要只观察一组“看起来正确”的输出。至少检查：

• _size 与 _capacity 始终满足 $0\le \text{\_size}\le \text{\_capacity}$；
• 满载（_size == _capacity）时插入先触发扩容，空表（_size == 0）时禁止删除；
• 插入元素必须从后向前倒序平移，防止覆盖原有数据；
• 删除元素必须从前向后正序平移，依次向前填补空洞；
• 读取与修改严格限制在 [0, _size - 1] 的有效下标区间内；
• 扩容或缩容后旧内存已被释放，不再解引用此前保存的旧元素指针或引用；
• 缩容采用滞后阻尼策略（如装载因子 $\le 25\mathrm{\%}$ 时减半），防止增删交替引发内存抖动；
• 析构函数正确释放堆内存，显式定义深拷贝或禁用默认拷贝，避免重复释放与内存泄漏。

---

小结与自测

请尝试回答以下问题以检验对顺序表底层原理的理解：

1. 为什么顺序表支持 $O(1)$ 的随机存取，而不仅仅是因为“内存连续”？
2. 从 CPU 缓存机制来看，为什么顺序表在连续遍历时能够获得硬件加速？
3. 在纯插入场景下，为什么加法扩容的摊还代价是 $O(n)$，而 2 倍乘法扩容的摊还代价是 $O(1)$？
4. 为什么 50% 立即减半的对称缩容会引发“性能抖动”？25% 滞后阈值是如何消除它的？
5. 顺序表在删除指定位置元素时，为什么必须正序平移？如果倒序平移会发生什么？

查看自测答案

1. 随机存取依赖两个前提：物理内存连续 且 每个元素占用相同字节数 $L$。满足这两个条件后，CPU 可通过寻址公式 $Loc(a_i)=Loc(a_0)+i\times L$ 在 1 次时钟周期内直接算出物理地址。
2. CPU 从主存读取数据时会按 Cache Line（通常 64 字节）批量加载相邻数据。由于顺序表物理内存完全连续，访问 $a_0$ 时后续元素已被自动预载进 L1 Cache，后续连续遍历几乎全中缓存（高空间局部性）。
3. 加法扩容的数据拷贝总次数构成等差数列，累积开销为 $O(n^2)$，除以 $n$ 后均摊为 $O(n)$；2 倍乘法扩容的数据拷贝总次数构成等比数列，累积开销 $<2n=O(n)$，除以 $n$ 后均摊为 $O(1)$。
4. 50% 对称缩容在满载临界点处，交替执行 1 次 push 和 1 次 pop 会连续触发全量内存重分配与搬移；25% 缩容完成后装载因子回到 50%，在临界点两侧留出了宽裕的阻尼缓冲区，阻断了连续重分配。
5. 删除操作是要填补被删除位置留下的空洞，必须从前向后正序平移（_data[i-1] = _data[i]），让后一个元素覆盖前一个空洞；若倒序平移，最后一个元素会提前把前一个槽位覆盖，破坏中间有效数据。

接下来可以完成 Lab 01-T-01：顺序表选择题精练 与 Lab 01-E-01：顺序表去重，在实践中检验对动态扩缩容与平移操作的理解。