C++基础：（十）vector 类的基础使用

_OP_CHEN

发布于 2026-01-14 09:57:25

1000

文章被收录于专栏：C++C++

前言

在 C++ STL（标准模板库）中，vector 是最常用、最基础的数据结构之一，它本质上是一个动态数组，能够根据存储元素的数量自动调整内部容量，既保留了数组随机访问的高效性，又弥补了静态数组容量固定的缺陷。无论是日常开发中的数据存储，还是算法竞赛中的高效处理，vector 都扮演着不可或缺的角色。下面就让我们正式开始学习vector吧！

一、vector 基础：从文档到核心接口

1.1 认识 vector

vector 是 C++ 标准库中的序列容器，其底层实现基于动态数组，支持在尾部高效地插入和删除元素，并能通过下标运算符（[]）实现随机访问（时间复杂度为 O (1)）。与静态数组相比，vector 的核心优势在于动态扩容—— 当存储的元素数量超过当前容量时，vector 会自动分配一块更大的内存空间，将原有元素拷贝到新空间，并释放旧空间，从而实现 “动态增长”。

在实际开发中，vector 的文档是最好的学习工具（如cppreference），本文将聚焦于实际开发和面试中最常用的核心接口，帮助大家快速上手。

1.2 vector 核心接口使用详解

1.2.1 构造函数（vector 的初始化）

vector 中提供了 4 种常用的构造方式，不同场景下选择合适的构造函数可以提高代码效率和可读性。如下所示：

构造函数声明	接口说明	代码示例
vector()（重点）	无参构造，创建一个空的 vector，size 为 0，capacity 为 0	vector<int> v1;（空 vector，无元素）
vector (size_type n, const value_type& val = value_type())	构造一个包含 n 个 val 的 vector	vector<int> v2(5, 3);（包含 5 个 3，size=5，capacity=5）
vector (const vector& x)（重点）	拷贝构造，创建一个与 x 完全相同的 vector	vector<int> v3(v2);（v3 是 v2 的拷贝，元素与 v2 一致）
vector (InputIterator first, InputIterator last)	迭代器构造，用 [first, last) 区间内的元素初始化	vector<int> v4(v2.begin(), v2.end());（v4 与 v2 元素相同）；int arr[] = {1,2,3}; vector<int> v5(arr, arr+3);（用数组元素初始化）

代码示例如下所示：

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

int main() {
    // 1. 无参构造
    vector<int> v1;
    cout << "v1: size=" << v1.size() << ", capacity=" << v1.capacity() << endl; // 0, 0

    // 2. 初始化n个val
    vector<int> v2(5, 3);
    cout << "v2: ";
    for (int i = 0; i < v2.size(); ++i) {
        cout << v2[i] << " "; // 3 3 3 3 3
    }
    cout << "(size=" << v2.size() << ", capacity=" << v2.capacity() << ")" << endl; // 5, 5

    // 3. 拷贝构造
    vector<int> v3(v2);
    cout << "v3: ";
    for (auto e : v3) {
        cout << e << " "; // 3 3 3 3 3
    }
    cout << endl;

    // 4. 迭代器构造
    int arr[] = {1, 2, 3, 4};
    vector<int> v4(arr, arr + 4);
    cout << "v4: ";
    for (auto it = v4.begin(); it != v4.end(); ++it) {
        cout << *it << " "; // 1 2 3 4
    }
    cout << endl;

    return 0;
}

1.2.2 迭代器（vector 的遍历工具）

迭代器是 STL 中连接容器和算法的 “桥梁”，它提供了统一的接口来访问容器中的元素，屏蔽了不同容器底层数据结构的差异。vector 的迭代器本质是一个原生指针（如int*），支持随机访问（如it += 2、it - it2等操作）。

vector 常用的迭代器接口如下：

迭代器接口	接口说明
begin() + end()（重点）	begin()返回指向第一个元素的迭代器；end()返回指向最后一个元素的下一个位置的迭代器（“尾后迭代器”，不指向有效元素）
rbegin() + rend()	rbegin()返回指向最后一个元素的反向迭代器；rend()返回指向第一个元素的前一个位置的反向迭代器
cbegin() + cend()	与begin()/end()功能相同，但返回的是const迭代器，不能通过迭代器修改元素

迭代器遍历的代码演示如下：

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

int main() {
    vector<int> v = {1, 2, 3, 4, 5};

    // 1. 正向遍历（begin() + end()）
    cout << "正向遍历: ";
    auto it = v.begin();
    while (it != v.end()) {
        cout << *it << " "; // 1 2 3 4 5
        ++it;
    }
    cout << endl;

    // 2. 反向遍历（rbegin() + rend()）
    cout << "反向遍历: ";
    auto rit = v.rbegin();
    while (rit != v.rend()) {
        cout << *rit << " "; // 5 4 3 2 1
        ++rit; // 反向迭代器的++等价于正向迭代器的--
    }
    cout << endl;

    // 3. const迭代器（只读，不能修改元素）
    cout << "const迭代器（只读）: ";
    auto cit = v.cbegin();
    while (cit != v.cend()) {
        // *cit = 10; // 错误：const迭代器不能修改元素
        cout << *cit << " "; // 1 2 3 4 5
        ++cit;
    }
    cout << endl;

    return 0;
}

在这我们需要注意，尾后迭代器（end()/rend()）不指向有效元素，因此不能解引用（*end()）或递增（++end()），否则会导致未定义行为（程序崩溃或输出乱码）。

1.2.3 空间管理接口（size 与 capacity 的区别）

vector 的 “大小” 分为两种：size和capacity，这是初学者常常会混淆的概念：

size：当前 vector 中实际存储的元素个数（即 “有效元素数”）。
capacity：当前 vector 底层数组能容纳的最大元素个数（即 “总容量”），capacity >= size，多余的空间称为 “备用空间”。

vector 提供的空间管理接口如下：

空间接口	接口说明
size()	返回当前有效元素个数（size）
capacity()	返回当前底层数组的总容量（capacity）
empty()	判断 vector 是否为空（size == 0），返回bool值
resize(size_type n, value_type val = value_type())（重点）	调整 vector 的 size 为 n：1. 若 n > 当前 size：在尾部补 n - size 个 val（若未指定 val，内置类型补 0，自定义类型调用默认构造）；2. 若 n < 当前 size：删除尾部的 size - n 个元素；3. 若 n > 当前 capacity：会触发扩容
reserve(size_type n)（重点）	调整 vector 的 capacity 为 n（仅负责开辟空间，不初始化元素）：1. 若 n > 当前 capacity：扩容至 n；2. 若 n <= 当前 capacity：无操作（不缩容）

（1）size 与 capacity 的关系演示

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

int main() {
    vector<int> v;
    cout << "初始状态: size=" << v.size() << ", capacity=" << v.capacity() << endl; // 0, 0

    // push_back 5个元素
    for (int i = 1; i <= 5; ++i) {
        v.push_back(i);
        cout << "push_back(" << i << "): size=" << v.size() << ", capacity=" << v.capacity() << endl;
    }
    // 输出（vs下）：
    // push_back(1): size=1, capacity=1
    // push_back(2): size=2, capacity=2
    // push_back(3): size=3, capacity=3
    // push_back(4): size=4, capacity=4
    // push_back(5): size=5, capacity=6（vs下扩容1.5倍）

    // resize调整size
    v.resize(8, 6);
    cout << "resize(8,6)后: size=" << v.size() << ", capacity=" << v.capacity() << endl; // 8, 8（若原capacity不足，会扩容）
    cout << "元素: ";
    for (auto e : v) {
        cout << e << " "; // 1 2 3 4 5 6 6 6
    }
    cout << endl;

    // reserve调整capacity
    v.reserve(10);
    cout << "reserve(10)后: size=" << v.size() << ", capacity=" << v.capacity() << endl; // 8, 10（仅扩容，size不变）

    return 0;
}

（2）vector 的扩容机制（面试重点）

当 vector 的size达到capacity时，继续插入元素（如push_back）会触发扩容。扩容的核心逻辑是：

分配一块更大的内存空间（新容量大小由编译器实现决定）；
将旧空间中的元素拷贝到新空间；
释放旧空间；
更新迭代器（指向新空间）。

不同编译器下 vector 的扩容倍数不同：

VS（PJ 版本 STL）：按1.5 倍扩容（如 1→2→3→4→6→9→13...）；
GCC（SGI 版本 STL）：按2 倍扩容（如 1→2→4→8→16→32...）。

扩容机制代码验证如下：

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

// 测试vector默认扩容机制
void TestVectorExpand() {
    size_t sz;
    vector<int> v;
    sz = v.capacity();
    cout << "VS下扩容（1.5倍）：" << endl;
    for (int i = 0; i < 100; ++i) {
        v.push_back(i);
        if (sz != v.capacity()) {
            sz = v.capacity();
            cout << "capacity changed to: " << sz << endl;
            // VS输出：1, 2, 3, 4, 6, 9, 13, 19, 28, 42, 63, 94, 141...
            // GCC输出：1, 2, 4, 8, 16, 32, 64, 128...
        }
    }
}

int main() {
    TestVectorExpand();
    return 0;
}

由于在扩容过程中涉及 “内存分配 + 元素拷贝 + 旧空间释放”的问题，频繁扩容会严重影响性能。因此，若提前知道 vector 需要存储的元素个数，应使用reserve(n)提前开辟足够的空间，避免频繁扩容。我们可以做出如下的优化：

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

void TestVectorExpandOP() {
    vector<int> v;
    size_t sz = v.capacity();
    v.reserve(100); // 提前开辟100个元素的空间
    cout << "提前reserve(100)后的扩容情况：" << endl;
    for (int i = 0; i < 100; ++i) {
        v.push_back(i);
        if (sz != v.capacity()) {
            sz = v.capacity();
            cout << "capacity changed to: " << sz << endl; // 仅输出1次：100
        }
    }
}

int main() {
    TestVectorExpandOP();
    return 0;
}

1.2.4 增删查改接口（vector 的核心操作）

vector 的增删查改接口是日常开发中最常用的功能，重点掌握尾部操作（高效）和迭代器操作（灵活）。

增删查改接口	接口说明	时间复杂度
push_back(const value_type& val)（重点）	尾部插入 val，若 size == capacity 则先扩容	O (1)（ amortized，平均时间复杂度；扩容时为 O (n)）
pop_back()（重点）	尾部删除最后一个元素，不改变 capacity	O(1)
find(InputIterator first, InputIterator last, const T& val)	查找 [first, last) 区间内的 val，返回指向 val 的迭代器（未找到返回 last）；注意：find 是<algorithm>中的算法，不是 vector 的成员函数	O(n)
insert(iterator pos, const value_type& val)	在 pos 位置插入 val，pos 之后的元素后移；若 size == capacity 则先扩容	O (n)（pos 越靠前，移动元素越多）
erase(iterator pos)	删除 pos 位置的元素，pos 之后的元素前移；不改变 capacity	O (n)（pos 越靠前，移动元素越多）
swap(vector& x)	交换两个 vector 的底层数据（size、capacity、元素指针），不拷贝元素	O (1)（仅交换指针，高效）
operator[](size_type n)（重点）	下标访问第 n 个元素（0-based），无越界检查（与数组类似）	O(1)
at(size_type n)	下标访问第 n 个元素，有越界检查（越界时抛出out_of_range异常）	O(1)

增删查改代码演示如下：

#include <iostream>
#include <vector>
#include <algorithm> // for find
using namespace std;

int main() {
    vector<int> v = {1, 2, 3, 4};

    // 1. 尾插（push_back）
    v.push_back(5);
    cout << "push_back(5)后: ";
    for (auto e : v) { cout << e << " "; } // 1 2 3 4 5
    cout << endl;

    // 2. 尾删（pop_back）
    v.pop_back();
    cout << "pop_back()后: ";
    for (auto e : v) { cout << e << " "; } // 1 2 3 4
    cout << endl;

    // 3. 查找（find）
    auto pos = find(v.begin(), v.end(), 3);
    if (pos != v.end()) {
        cout << "找到元素3，位置：" << pos - v.begin() << endl; // 2（下标从0开始）
    } else {
        cout << "未找到元素3" << endl;
    }

    // 4. 插入（insert）
    pos = v.begin() + 2; // 指向第3个元素（3）
    v.insert(pos, 30); // 在3之前插入30
    cout << "insert(30)后: ";
    for (auto e : v) { cout << e << " "; } // 1 2 30 3 4
    cout << endl;

    // 5. 删除（erase）
    pos = v.begin() + 2; // 指向30
    v.erase(pos); // 删除30
    cout << "erase(30)后: ";
    for (auto e : v) { cout << e << " "; } // 1 2 3 4
    cout << endl;

    // 6. 交换（swap）
    vector<int> v2 = {10, 20, 30};
    v.swap(v2);
    cout << "swap后v: ";
    for (auto e : v) { cout << e << " "; } // 10 20 30
    cout << "，v2: ";
    for (auto e : v2) { cout << e << " "; } // 1 2 3 4
    cout << endl;

    // 7. 下标访问（operator[] vs at）
    cout << "v[1] = " << v[1] << endl; // 20（无越界检查）
    // cout << "v[10] = " << v[10] << endl; // 未定义行为（乱码或崩溃）
    try {
        cout << "v.at(10) = " << v.at(10) << endl; // 抛出out_of_range异常
    } catch (const out_of_range& e) {
        cout << "at()越界：" << e.what() << endl;
    }

    return 0;
}

1.2.5 迭代器失效问题（面试高频考点）

迭代器失效是 vector 使用中的 “坑点”，指迭代器底层指向的内存空间被释放或元素位置发生改变，导致迭代器无法正确访问元素。若继续使用失效的迭代器，会引发未定义行为（程序崩溃、输出乱码等）。

（1）迭代器失效的本质

vector 的迭代器本质是原生指针（如int*），当底层内存空间发生改变（如扩容）或元素位置移动（如插入 / 删除）时，指针指向的地址要么变为 “野指针”（旧空间被释放），要么指向错误的元素（元素移动），从而导致迭代器失效。

（2）导致迭代器失效的操作

引发底层空间改变的操作：resize、reserve、insert、assign、push_back等（可能触发扩容，释放旧空间）。
指定位置的删除操作（erase）：删除 pos 位置元素后，pos 之后的元素前移，pos 迭代器指向的元素发生改变；若 pos 是最后一个元素，删除后 pos 变为尾后迭代器（失效）。

（3）迭代器失效的代码示例及其解决办法

示例 1：扩容导致迭代器失效

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

int main() {
    vector<int> v = {1, 2, 3, 4, 5};
    auto it = v.begin(); // it指向旧空间的第一个元素（地址假设为0x100）

    // 操作1：resize触发扩容（假设原capacity=5，resize(100)需要扩容）
    v.resize(100, 8);
    // 操作2：reserve触发扩容
    // v.reserve(100);
    // 操作3：insert触发扩容
    // v.insert(v.begin(), 0);
    // 操作4：assign触发扩容
    // v.assign(100, 8);

    // 此时it指向的旧空间已被释放，迭代器失效
    while (it != v.end()) {
        cout << *it << " "; // 未定义行为（崩溃或乱码）
        ++it;
    }

    return 0;
}

要解决上面的问题，我们可以在引发扩容的操作后，重新给迭代器赋值（让迭代器指向新空间的元素）：

// 扩容操作后，重新赋值迭代器
v.resize(100, 8);
it = v.begin(); // 重新指向新空间的第一个元素
while (it != v.end()) {
    cout << *it << " "; // 正常输出
    ++it;
}

示例 2：erase 导致迭代器失效

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

int main() {
    vector<int> v = {1, 2, 3, 4};
    auto it = find(v.begin(), v.end(), 3); // it指向3

    // 删除it位置的元素，it迭代器失效
    v.erase(it);
    cout << *it << endl; // 未定义行为（VS下崩溃，GCC下可能输出4，但逻辑错误）

    return 0;
}

我们可以利用erase的返回值 ——erase(pos)会返回指向 “删除元素的下一个元素” 的有效迭代器，因此可以将返回值重新赋值给 it：

auto it = find(v.begin(), v.end(), 3);
if (it != v.end()) {
    it = v.erase(it); // it指向删除元素的下一个元素（4）
}
cout << *it << endl; // 正常输出4

（4）经典错误：删除 vector 中的所有偶数

不少C++初学者常犯的错误是忽略erase后的迭代器失效，导致程序崩溃。正确的写法是利用erase的返回值更新迭代器。如下：

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

int main() {
    vector<int> v = {1, 2, 3, 4};
    auto it = v.begin();
    while (it != v.end()) {
        if (*it % 2 == 0) {
            it = v.erase(it); // 用返回值更新it，指向删除元素的下一个元素
        } else {
            ++it; // 未删除时，正常递增
        }
    }
    for (auto e : v) { cout << e << " "; } // 正确输出1 3
    return 0;
}

（5）编译器差异：VS 与 GCC 对迭代器失效的检测

VS（PJ STL）：对迭代器失效的检测非常严格，一旦迭代器失效（如扩容后、erase 后），继续使用会直接触发断言错误（程序崩溃），便于调试。
GCC（SGI STL）：对迭代器失效的检测较宽松，部分情况下迭代器失效后程序仍能运行，但输出结果错误（如扩容后迭代器指向旧空间，输出乱码）；如果迭代器超出[begin(), end())范围，则会崩溃。

二、vector 实战：OJ 经典题目解析

vector 在算法竞赛（OJ）中应用广泛，以下博主选取了几道经典题目，来讲解 vector 的实战技巧。

2.1 题目 1：只出现一次的数字（LeetCode 136）

题目描述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

解题思路

利用异或运算的性质：

异或运算满足交换律和结合律：a ^ b ^ c = a ^ c ^ b；
任何数与 0 异或仍为其本身：a ^ 0 = a；
任何数与自身异或为 0：a ^ a = 0。

因此，将数组中所有元素异或，最终结果即为只出现一次的元素。

代码实现如下：

#include <vector>
using namespace std;

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = 0;
        for (auto e : nums) { // 遍历vector
            result ^= e;
        }
        return result;
    }
};

3.2 题目 2：杨辉三角（LeetCode 118）

题目描述

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。杨辉三角中，每个数是它左上方和右上方的数的和。

解题思路

初始化一个二维 vectorvv，外层 vector 的大小为 numRows；
第 i 行（0-based）的大小为 i+1，且首尾元素为 1；
第 i 行（i >= 2）的中间元素（j >= 1 且 j < i）等于第 i-1 行第 j-1 列和第 j 列元素之和。

代码实现如下：

#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> vv(numRows); // 外层vector有numRows个元素

        for (int i = 0; i < numRows; ++i) {
            vv[i].resize(i + 1, 1); // 第i行有i+1个元素，默认值1
        }

        // 填充中间元素
        for (int i = 2; i < numRows; ++i) {
            for (int j = 1; j < i; ++j) {
                vv[i][j] = vv[i-1][j-1] + vv[i-1][j];
            }
        }

        return vv;
    }
};

3.3 题目 3：删除排序数组中的重复项（LeetCode 26）

题目描述

给你一个升序排列的数组 nums，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。元素的相对顺序应该保持一致。

解题思路

利用 “双指针” 技巧：

定义指针i（慢指针），指向当前不重复元素的最后一个位置；
定义指针j（快指针），遍历数组，寻找与nums[i]不同的元素；
当nums[j] != nums[i]时，i递增，将nums[j]赋值给nums[i]；
最终i+1即为新数组的长度。

代码实现如下：

#include <vector>
using namespace std;

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) {
            return 0;
        }

        int i = 0; // 慢指针：指向不重复元素的最后一个位置
        for (int j = 1; j < nums.size(); ++j) { // 快指针：遍历数组
            if (nums[j] != nums[i]) {
                ++i;
                nums[i] = nums[j]; // 覆盖重复元素
            }
        }

        return i + 1; // 新数组长度
    }
};

3.4 题目 4：只出现一次的数字 II（LeetCode 137）

题目描述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现三次。找出那个只出现了一次的元素。

解题思路

利用 “位运算” 统计每一位出现的次数：

对于整数的每一位（0~31 位），统计数组中所有元素在该位上的 1 的总次数；
若总次数能被 3 整除，则只出现一次的元素在该位上为 0；
若总次数不能被 3 整除，则只出现一次的元素在该位上为 1。

代码实现如下：

#include <vector>
using namespace std;

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = 0;
        // 遍历每一位（0~31位）
        for (int bit = 0; bit < 32; ++bit) {
            int count = 0; // 统计当前位上1的次数
            for (auto e : nums) {
                // 检查当前元素的第bit位是否为1
                if ((e >> bit) & 1) {
                    ++count;
                }
            }
            // 若count不能被3整除，说明结果的第bit位为1
            if (count % 3 != 0) {
                // 注意：int是有符号类型，第31位是符号位，需要特殊处理
                if (bit == 31) {
                    result -= (1 << bit);
                } else {
                    result |= (1 << bit);
                }
            }
        }
        return result;
    }
};