1. 顺序表基本概念

1.1 线性表定义

• 线性表是n个具有相同特性的数据元素的有序序列

• 逻辑上呈现为连续的线段结构

1.2 顺序存储结构

• 顺序表是线性表的顺序存储实现

• 元素存储在连续的内存空间中，类似于数组

2. 顺序表的实现方式

2.1 静态顺序表

const int N = 1e6 + 10;  // 预定义最大容量
int a[N], n;            // 静态数组 + 元素个数计数器

优缺点：

• ✅ 优点：代码简单，无动态内存管理开销

• ❌ 缺点：空间固定，可能浪费或不足

2.2 动态顺序表（vector）

• 按需动态分配内存

• C++ STL中的vector是典型的动态顺序表实现

3. 顺序表基本操作及时间复杂度

3.1 插入操作

操作类型	时间复杂度	代码示例
尾插	O(1)	a[++n] = x
头插	O(n)	所有元素右移一位
任意位置插入	O(n)	部分元素右移

3.2 删除操作

操作类型	时间复杂度	代码示例
尾删	O(1)	n--
头删	O(n)	所有元素左移一位
任意位置删除	O(n)	部分元素左移

3.3 查找操作

操作类型	时间复杂度	代码示例
按值查找	O(n)	遍历整个数组
按位查找	O(1)	return a[p]

3.4 修改操作

• 时间复杂度：O(1)

• 代码示例：a[p] = x

4. Vector（STL动态顺序表）

4.1 创建vector

vector<int> a1;                    // 空vector
vector<int> a2(N);                 // 大小为N，默认值0
vector<int> a3(N, 2);             // 大小为N，初始值2
vector<int> a4 = {1,2,3,4,5};     // 初始化列表
vector<vector<int>> a5;            // 二维vector

4.2 常用接口及时间复杂度

基本信息

• size(): 返回元素个数 - O(1)

• empty(): 判断是否为空 - O(1)

迭代器

• begin(): 起始迭代器

• end(): 结束迭代器（最后一个元素的下一个位置）

元素访问

• front(): 首元素 - O(1)

• back(): 尾元素 - O(1)

• operator[]: 随机访问 - O(1)

修改操作

• push_back(x): 尾插 - 平均O(1)

• pop_back(): 尾删 - O(1)

• resize(new_size): 调整大小 - O(n)

• clear(): 清空 - O(n)

4.3 遍历方式

// 1. 下标遍历
for(int i = 0; i < a.size(); i++) 
    cout << a[i] << " ";

// 2. 迭代器遍历
for(auto it = a.begin(); it != a.end(); it++)
    cout << *it << " ";

// 3. 范围for循环
for(auto x : a)
    cout << x << " ";

5. Vector封装示例

struct SqList {
    static const int N = 1e6 + 10;
    int a[N], n;
    
    SqList() { n = 0; }
    
    void push_back(int x) { a[++n] = x; }
    void pop_back() { n--; }
    
    void print() {
        for(int i = 1; i <= n; i++)
            cout << a[i] << " ";
        cout << endl;
    }
};

6. 算法题应用

6.1 基础应用

• 询问学号：直接使用vector随机访问特性

• 寄包柜：使用vector数组模拟二维结构

6.2 双指针技巧

• 移动零：快慢指针划分数组

• 颜色分类：三指针划分三种颜色

• 合并有序数组：从后往前归并避免覆盖

7. 编程模式对比

ACM模式

#include<iostream>
#include<vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    // 处理逻辑...
    return 0;
}

核心代码模式

class Solution {
public:
    void function(vector<int>& nums) {
        // 只需实现核心逻辑
    }
};

8. 关键总结

8.1 Vector优势

• 动态扩容，内存使用更合理

• 提供丰富的接口，使用方便

• 支持随机访问，效率高

8.2 使用注意事项

• 避免频繁的中间插入删除（O(n)操作）

• 大规模数据时注意扩容开销

• 多维vector注意内存使用

8.3 适用场景

• 需要频繁随机访问

• 数据量变化不大或主要在尾部操作

• 算法竞赛中空间充足的情况

vector作为C++中最常用的顺序容器，结合了数组的高效访问和动态扩容的灵活性，是解决各类算法问题的利器。