C++ 从入门到精通之三

发表于 阅读次数： 评论数： 本文字数： 12k 阅读时长 ≈ 11 分钟

大纲

C++ 容器

扩展阅读

基础概念

STL 基础概念

  • C++ 标准库（C++ Standard Library）

    • C++ 标准库是 C++ 编程语言的重要组成部分，提供了大量经过标准化、可复用的功能组件，例如容器、算法、迭代器等。

  • 标准模板库（STL）

    • STL 是 C++ 标准库的核心组成部分之一，以模板为基础，提供容器、算法、迭代器等通用组件，是现代 C++ 开发中常用的基础工具。

  • 泛型编程（Generic Programming）

    • 泛型编程是一种以模板为主要技术手段的编程思想，通过编写与具体类型无关的通用代码，提高代码的复用性、通用性和扩展性。STL 正是泛型编程思想的典型应用。

常用的数据结构

C++ 常用的数据结构，包括：栈、队列、链表、树、散列表（哈希表）、图等，推荐阅读书籍 《算法导论》。

STL 发展历史

STL（标准模板库）的发展经历了多个重要版本，主要包括：

  • HP STL

    • 由惠普（HP）实现，是 STL 的早期版本。
    • 后续许多 STL 实现都在其基础上发展而来。

  • SGI STL

    • 由 Silicon Graphics（SGI）实现。
    • 曾广泛应用于 GNU C++（GCC、G++）环境，是早期 GNU C++ 标准库的重要 STL 实现之一。

  • Rogue Wave STL

    • 由 Rogue Wave Software 公司开发和维护。
    • 曾被多个商业 C++ 编译器和开发环境采用，是早期较有影响力的 STL 实现之一。

  • P.J. Plauger STL

    • 由 P.J. Plauger 实现。
    • 曾作为 Visual C++ 中使用的 STL 实现。

  • 现代 C++ 标准库

    • 随着 C++ 标准的发展，STL 中的容器、算法、迭代器等核心组件逐步纳入 C++ 标准库。
    • 现代 GCC、Clang、MSVC 等编译器均提供符合 C++ 标准的 STL 实现。

扩展阅读

STL 容器分类

在 C++ STL 中的容器按照数据组织方式和使用场景，通常可以分为以下三大类。值得一提的是，C++ 标准只规定了各类容器的接口、行为和复杂度要求，并未强制规定其底层必须采用某种特定的数据结构或实现方式。具体的实现由 C++ 标准库的开发者根据编译器、平台和性能需求自行决定。

  • 序列容器（Sequence Containers）

    • 元素按照一定的线性顺序进行存储和访问。
    • 底层通常采用数组、动态数组或链表等数据结构实现。
    • 常见容器包括：array、vector、deque、list、forward_list。

  • 有序关联容器（Ordered Associative Containers）

    • 元素按照键（Key）进行组织和查找，适合需要快速检索（查找）数据的场景。
    • 常见容器包括：set、multiset、map、multimap。
    • 底层通常采用平衡二叉搜索树（一般为红黑树）实现，因此元素会按照键进行有序排列。
    • 其中，set 和 multiset 以键本身作为元素；map 和 multimap 存储键值对。

  • 无序关联容器（Unordered Associative Containers）

    • 基于哈希表（Hash Table）实现，元素按照哈希值组织，不保证元素的顺序。
    • 常见容器包括：unordered_set、unordered_multiset、unordered_map、unordered_multimap。
    • 与有序关联容器相比，通常具有更快的平均查找效率，但不提供元素的有序访问（顺序访问）。

  • 容器适配器（Container Adaptors）

    • stack：后进先出（LIFO），默认底层容器为 deque，也可指定为 vector 或 list。
    • queue：先进先出（FIFO），默认底层容器为 deque，也可指定为 list。
    • priority_queue：优先队列，每次取出优先级最高的元素，默认底层容器为 vector，默认使用 std::less 和二叉堆算法维护堆序。
    • 共同特点：不提供迭代器，只暴露 push、pop、top、front、back 等特定操作，本质是对底层容器的接口限制和封装。

关联容器的分类

在 C++ STL 中，关联容器可分为基于树结构和基于哈希表两大类：前者包括 map / set 和 multimap / multiset，通常以红黑树实现，能保证元素始终有序；后者包括 unordered_map/ unordered_set 和 unordered_multimap / unordered_multiset，通过哈希函数将键映射到特定位置，提供平均常数时间的查找性能。与序列容器（如 vector、list 等）相比，关联容器最大的优势在于高效查找：序列容器中查找元素通常需要线性时间复杂度 O(n)，而基于树结构的关联容器可提供对数时间复杂度 O(log n) 的查找性能。

STL 推荐书籍

为了更好地学习和熟悉掌握 C++ 容器的使用，推荐阅读以下几本书籍：

  • 《算法导论》
  • 《STL 源码剖析》
  • 《C++ 标准库（第 2 版）》

string 容器

string 的概述

string 是 STL 的字符串类型，通常用来表示字符串。而在使用 string 之前，字符串通常是用 char* 表示的。string 与 char* 都可以用来表示字符串，两者的区别如下：

  • string 是一个类，char* 是一个指向字符的指针
  • string 封装了 char* 来管理字符串，本质是一个 char* 类型的容器
  • string 不用考虑内存释放和越界的问题
  • string 负责管理 char* 所分配的内存。每一次 string 的复制，取值都由 string 类负责维护，不用担心复制越界和取值越界等问题
  • string 提供了一系列的字符串操作函数，例如：查找（find）、拷贝（copy）、删除（erase）、替换（replace）、插入（insert）

string 的构造函数

  • 默认构造函数：string();
  • 带参数的构造函数：
    • string(const char *s);，用字符串 s 初始化
    • string(int n, char c);，用 n 个字符 c 初始化
  • 拷贝构造函数：string(const string &str);

字符串头文件说明

  • 在标准 C++ 中，使用 string 必须显式包含 <string> 头文件。任何在未包含 <string> 的情况下仍然能够使用 string 的代码，都依赖于标准库实现的间接包含行为，属于非标准、不可移植的用法。
  • 一些标准库实现（例如 libstdc++）在 <iostream> 等头文件的内部实现中，可能间接包含了 <string>，从而使代码在特定编译器和版本下 "看起来可以正常工作"。然而，这种行为是实现细节，不受 C++ 标准保证，随着编译器、标准库版本或编译选项（如不同的 -std= 标准级别）变化，代码都有可能无法通过编译。

string 的初始化方式

  • C 语言中，字符串的初始化方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 使用字符串字面量初始化：末尾自动追加 '\0'，其余元素补 0
char str1[100] = "C++";

// 等价于上面 s1 的写法效果，显式写出 '\0'，其余元素补 0
char str2[100] = {'C', '+', '+', '\0'};

// 不指定字符串长度，让编译器自动推导，实际大小是 4（包括末尾的 '\0'）
char str3[] = "C++";

// 使用字符列表初始化（末尾必须要有 '\0'，否则不是字符串）
char str4[] = {'C', '+', '+', '\0'};

// 部分初始化：其余元素补 0（非字符串语义，但结果满足 '\0' 结尾）
char str5[100] = {'C', '+', '+'};
  • C++ 中，字符串的初始化方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 默认初始化，s1 是空字符串，表示里面没有字符
string s1;

// 将指定的字符串内容拷贝到 s2 所代表的一段内存中，拷贝时不包括字符串末尾的 '\0'
string s2 = "I Love C++";

// 跟上面字符串 s2 的写法效果一样
string s3("I Love C++");

// 列表初始化
string s4{"I Love C++"};

// 将字符串 s2 的内容拷贝到 s4 所代表的一段内存中
string s5 = s2;

// 将 s5 初始化为连续 5 个字符 'a' 组成的字符串（aaaaa），可能会在系统内部创建临时对象
string s6(5, 'a');

// 从 s2 的下标 2（第 3 个字符）开始，连续拷贝到字符串末尾，构造新的字符串
string s7(s2, 2);

// 从 s2 的下标 2（第 3 个字符）开始，连续拷贝 4 个字符，构造新的字符串
string s8(s2, 2, 4);

// 通过字符数组（必须有一个元素是 '\0'，否则会出现未定义行为）初始化字符串
char buf[] = {'a', 'b', 'c', '\0'};
string s9(buf);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 使用 const char* 初始化 string
const char* p1 = "Modern C++";
string s1 = p1;

// 跟上面字符串 s1 的写法效果一样
string s2(p1);

// 使用 char 数组（必须有一个元素是 '\0'，否则会出现未定义行为）初始化字符串
char buf[] = {'a', 'b', 'c', '\0'};
string s3(buf);

// 使用 char*（必须有一个元素是 '\0'，否则会出现未定义行为）初始化 string
char buf2[] = {'a', 'b', 'c', '\0'};
char* p2 = buf2;
string s4 = p2;

// 指定长度进行构造（不依赖 '\0'）
char buf3[] = {'A', 'B', 'C', 'D', 'E'};
string s5(buf3, 3);  // 只拷贝前 3 个字符："ABC"

// 拷贝 char 数组的一部分（不依赖 '\0'）
char buf4[] = "Hello C++ World";
string s6(buf4 + 6, 3);  // 从第 7 个字符开始，拷贝 3 个字符："C++"

// 拷贝 char 数组的一部分（依赖 '\0'，否则会出现未定义行为）
char buf5[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', '\0'};
string s7(buf5 + 3);  // 从第 4 个字符开始，一直拷贝，直到遇到 '\0'，最终拷贝 4 个字符：DEFG
通过 char[] 或者 char * 初始化 string 的写法传入的真实类型是否依赖 '\0'说明
string(p)const char*依赖 C 风格字符串，必须包含 '\0'，遇 '\0' 结束拷贝
string(p, n)const char* + size_t不依赖精确拷贝 n 个字节，p 可以没有 '\0'
string(arr)const char*（arr 衰变）依赖 arr 必须包含 '\0'，遇 '\0' 结束拷贝
string(arr, n)const char* + size_t不依赖精确拷贝 n 个字节，arr 可以没有 '\0'

char 与 string 之间的转换

  • 在 C++ 中，char[] 与 char* 可以隐式转换为 string，而 string 不能自动转换为 char[] 或者 char*，只能通过 string::c_str() 显式获取 const char *。
  • string 的构造函数并不区分 char* 和 char[]，因为字符数组在参数传递时会退化为字符指针；是否依赖 '\0'，只取决于开发者调用的是 string(const char*) 还是 string(const char*, size_t)。

从 string 取得 char*

从 string 取得 char*，可以使用：

  • const char *c_str() const;，返回一个以 \0 结尾的字符串的首地址

特别注意

  • 在 C++ 中，char[] 与 char * 可以隐式转换为 string 类型，反过来则不可以，例如右边这种写法是合法的： char *p = "abc"; string str = p;

将 string 拷贝到 char*

将 string 拷贝到 char* 指向的内存空间，可以使用：

  • int copy(char *s, int n, int pos=0) const;

将当前串中以 pos 位置开始的 n 个字符拷贝到以 s 为起始位置的字符数组中，返回实际拷贝的字符数量。特别注意，要保证指针 s 所指向的内存空间足以容纳当前的字符串，不然可能会发生越界。

从 string 与范围 for 使用

1
2
3
4
5
6
7
8
9
10
11
12
13
string s10 = "hello c++";
// 通过范围 for 遍历字符串所有元素，使用常量引用
for (const char& c : s10) {
    cout << c;
}
cout << endl;

// 通过范围 for 和引用遍历字符串所有元素，并更改其元素的值，使用普通引用
for (char& c : s10) {
    c = toupper(c);
    cout << c;
}
cout << endl;

程序运行输出的结果如下：

1
2
hello c++
HELLO C++

array 容器

array 的概述

std::array 是 C++ 11 引入的固定大小容器，本质上是对原生数组的一层轻量级封装，元素在内存中连续存储，数据结构通常可以理解为内部直接包含一个固定长度的元素数组，因此 std::array<T, N> 本身一般不需要额外的动态内存分配，数组大小在编译期确定，sizeof 通常与 N * sizeof(T) 相关。它支持随机访问，访问效率与原生数组基本一致，同时提供 size()、begin()、end()、front()、back() 等 STL 容器接口，可以方便地与其他 STL 算法配合使用。与 std::vector 不同，std::array 的容量固定，创建后不能扩容或缩容，因此适合元素数量确定、希望获得连续内存和较低运行时开销的场景。

array 的使用

常用操作

  • 声明

    • std::array<int, 5> myarray;，声明一个包含 5 个 int 元素的 std::array（数组大小必须在编译期确定）
    • std::array<int, 5> myarray = {1, 2, 3, 4, 5};，声明并初始化

  • 访问元素

    • myarray[0]，通过下标访问元素（不检查越界）
    • myarray.at(0)，通过下标访问元素（会检查越界，越界抛出异常）
    • myarray.front()，访问第一个元素
    • myarray.back()，访问最后一个元素
    • myarray.data()，返回指向底层数组首元素的指针

  • 修改元素

    • myarray[0] = 10;，通过下标修改元素
    • myarray.at(0) = 10;，通过 at() 修改元素
    • myarray.fill(0);，将所有元素填充为指定值
    • myarray.swap(other);，与另一个同类型同大小的 std::array 交换内容

  • 查询

    • iterator：迭代器遍历（支持 begin() / end()，也支持反向迭代器 rbegin() / rend()）
    • for (auto& x : myarray)：基于范围的 for 循环遍历
    • std::get<0>(myarray)，编译期获取第 0 个元素的引用（下标必须是常量表达式）

  • 大小

    • myarray.size()，返回元素个数（编译期常量）
    • myarray.empty()，判断是否为空（std::array 大小固定，通常恒为 false）
    • myarray.max_size()，返回可容纳的最大元素数（等于 size）

特别注意

  • std::array 是聚合类型，内存连续，大小固定，不支持插入和删除操作（没有 push_back / pop_back / insert / erase）。
  • std::array 相比 C 语义风格的数组，不会退化为指针，且支持 size()、迭代器、赋值等操作
案例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <array>
#include <iostream>
#include <string>

using namespace std;

int main() {
    array<string, 3> arr = {"I", "Love", "C++"};

    cout << "array size: " << arr.size() << endl;

    cout << "string size: " << sizeof(string) << endl;

    for (int i = 0; i < arr.size(); i++) {
        cout << "--------------------------" << endl;
        const char* ptr = arr[i].c_str();
        cout << "数组元素值：" << arr[i] << endl;
        cout << "数组元素地址：" << &arr[i] << endl;  // 表示 std::string 对象本身的地址
        printf("指向的字符串地址：0x%llx\n", ptr);    // 表示字符串字符数据存储的起始地址
    }

    return 0;
}

程序运行输出的结果如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
array size: 3
string size: 32
--------------------------
数组元素值：I
数组元素地址：0x54b21ff810
指向的字符串地址：0x54b21ff820
--------------------------
数组元素值：Love
数组元素地址：0x54b21ff830
指向的字符串地址：0x54b21ff840
--------------------------
数组元素值：C++
数组元素地址：0x54b21ff850
指向的字符串地址：0x54b21ff860
案例分析

上面这段案例代码通过 std::array<std::string, 3>，可以观察 std::array 中的元素以及 string 内部字符数据的地址关系。

  • (1) std::array 的大小

    • arr.size() 返回 3，说明该 std::array 中包含 3 个 std::string 元素。
    • std::array 是固定大小容器，其元素通常是按顺序连续存储的。

  • (2) std::string 对象大小

    • 输出 sizeof(string) = 32，表示当前编译器和标准库实现中，一个 std::string 对象本身占用 32 个字节。
    • 这里需要特别注意，这并不表示字符串内容占用 32 个字节，sizeof 获取的是 string 对象自身的大小。

  • (3) 三个 string 对象连续存储

    • 从输出可以看到：
      • 第一个数组元素的地址：0x...810
      • 第二个数组元素的地址：0x...830
      • 第三个数组元素的地址：0x...850
    • 数组元素相邻地址之间相差 0x20，也就是 32 个字节，正好与 sizeof(string) 一致。
    • 这说明当前编译器和标准库实现中，std::array 里面的三个 string 对象是连续存储的。

  • (4) string 对象地址与字符串地址

    • 例如第一个数组元素：
      • string 对象地址：0x...810
      • 字符串字符数据地址：0x...820
    • 两者相差 16 个字节，而且其他两个元素也具有相同关系。
    • 这里需要特别注意：c_str() 返回的是字符串字符数据的地址，并不一定指向独立的堆内存。本例中的 "I"、"Love"、"C++" 都属于较短字符串，很可能触发了 SSO（Small String Optimization，小字符串优化），字符串字符数据直接存储在 std::string 对象内部，因此可以看到字符串地址落在 string 对象的地址范围内。

  • (5) 需要注意实现相关性

    • 上面的 sizeof(string) = 32 以及地址相差 16 个字节，都是当前编译器和标准库实现下的结果。
    • C++ 标准并没有规定 std::string 对象必须是 32 个字节，也没有规定其内部具体的内存布局。

  • (6) std::array 的内存布局

总结

std::array 的元素是连续存储的；上述案例中每个 std::string 对象占 32 个字节，而由于字符串较短触发了 SSO（Small String Optimization，小字符串优化），字符串字符数据直接存储在 std::string 对象内部。具体的 std::string 对象大小和内部内存布局属于标准库实现细节，并非 C++ 标准规定。

vector 容器

vector 的概述

vector 的数据存储以及操作方式，与 Array 非常相似，两者的唯一差别在于空间运用的灵活性。Array 是静态空间，一旦配置了就不能改变，要换大一点或者小一点的空间，可以，一切琐碎的细节得由自己来实现；首先配置一块新的空间，然后将旧空间的数据搬往新空间，再释放原来的空间。Vector 是动态空间，随着元素的加入，它的内部机制会自动扩充空间以容纳新元素。因此 vector 的运用对于内存的合理利用与运用的灵活性有很大的帮助，我们再也不必害怕空间不足而一开始就初始化一个大的 Array 了。Vector 的实现技术，关键在于其对大小的控制以及重新配置时的数据移动效率，一旦 vector 旧空间满了，如果客户每新增一个元素 vector 内部只是扩充一个元素的空间，实为不智，因为所谓的扩充空间（不论多大），一如刚才所说，是 “配置新空间 - 数据移动 - 释放旧空间” 的大工程，时间成本很高，应该加入某种未雨绸缪的考虑。

总结

  • vector 是将元素置于一个动态数组中加以管理的容器。
  • vector 可以随机存取元素（支持使用索引值直接存取， 用 [] 操作符或 at() 函数。
  • vector 尾部添加或移除元素非常快速，但是在头部或中部插入元素或移除元素比较耗时。

vector 的结构

vector 底层所采用的数据结构是线性连续空间（单向开口的连续内存空间），可以理解为支持动态开辟内存空间的数组（单向开口）；它以两个迭代器（_Myfirst 和 _Mylast）分别指向配置得来的连续空间中目前已被使用的范围，并以迭代器 _Myend 指向整块连续内存空间的尾端。vector 往尾部添加或移除元素的效率非常高，但是往头部或者中部插入元素或移除元素则比较耗时。为了降低空间配置时的速度成本，vector 实际配置的大小可能比客户端需求大一些，以应付将来可能的扩充，这里是容量的概念。换句话说，一个 vector 的容量永远大于或等于其大小，一旦容量等于大小，便是满载，下次再需要新增元素时，整个 vector 容器就得另觅居所（即扩容）。值得一提的是，所谓动态增加大小，并不是在原空间之后续接新空间（因为无法保证原空间之后尚有可配置的连续空间），而是申请一块更大的内存空间，然后将原数据拷贝到新空间，并释放原空间。因此，对 vector 的任何操作，一旦引起空间的重新配置，指向原 vector 的所有迭代器就都失效了，这是程序最容易出错的地方，务必小心。特别注意，vector 一旦需要执行扩容操作，那么每次都会以原来空间大小的 2 倍进行扩容。

vector 的初始化方式

  • 默认初始化
1
2
// 创建一个空 vector 对象
vector<int> v;
  • 指定大小（元素值默认初始化）
1
2
// 创建指定大小的 vector 对象
vector<int> v(5); // size = 5，int 全部为 0，结果是：[0, 0, 0, 0, 0]
  • 指定大小 + 指定初始值
1
2
// 创建指定大小的 vector 对象，并指定元素的初始值
vector<int> v(5, 10); // size = 5，int 全部为 10，结果是：[10, 10, 10, 10, 10]
  • 列表初始化
1
2
3
4
5
6
7
8
// 列表初始化，指定 vector 中的元素值
vector<int> v1 = {1, 2, 3};

// 跟上面 v1 的写法效果一样
vector<int> v2{1, 2, 3};

// 初始化一个空 vector 对象
vector<int> v{};
  • 拷贝初始化
1
2
3
4
5
6
7
vector<int> v1 = {1, 2, 3};

// v2 是 v1 的深拷贝
vector<int> v2(v1);

// 跟上面 v2 的写法效果一样
vector<int> v3 = v1;
  • 移动初始化
1
2
3
4
vector<int> v1 = {1, 2, 3};

// 移动初始化
vector<int> v2(move(v1));  // v1 被置为有效但未指定状态，v2 接管内存（高效）
  • 迭代器范围初始化
1
2
int arr[] = {1, 2, 3, 4};
vector<int> v(arr, arr + 4);
1
2
list<int> lst = {1, 2, 3};
vector<int> v(lst.begin(), lst.end());
  • 从 C 风格数组初始化
1
2
int arr[] = {1, 2, 3};
vector<int> v(begin(arr), end(arr));
  • C++ 17 / 20 的编译器自动推导类型
1
auto v = vector{1, 2, 3};

vector 容易混淆的初始化写法

  • vector 初始化时，使用括号与花括号，语义完全不同，比如：
  • vector<int> v(3, 2); 使用圆括号 () 初始化，调用的是 vector(size_type count, const T& value) 构造函数，表示创建一个包含 3 个元素 的 std::vector，并将每个元素都初始化为 2，因此最终结果为 [2, 2, 2]。
  • vector<int> v{3, 2}; 使用花括号 {} 初始化，优先匹配 vector(initializer_list<T>) 构造函数，表示直接使用初始化列表中的元素进行构造，初始化列表中包含两个元素 3 和 2，因此最终结果为 [3, 2]。

vector 与范围 for 使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<string> v1 = {"a", "b", "c"};

// 通过范围 for 和引用遍历 vector 所有元素，使用常量引用
for (const string& item : v1) {
    cout << item << " ";
}
cout << endl;

// 通过范围 for 和引用遍历 vector 所有元素，并更改其元素的值，使用普通引用
for (string& item : v1) {
    item = item + "1";
    cout << item << " ";
}
cout << endl;

程序运行输出的结果如下：

1
2
a b c 
a1 b1 c1

特别注意

  • 在 C++ 中使用范围 for 遍历 vector 时，不应在遍历过程中对容器执行插入或删除元素的操作，否则会导致未定义行为，可能表现为程序崩溃、数据异常或难以复现的内存错误。
  • 这是因为范围 for 遍历 vector 本质上依赖迭代器，而 vector 在插入或删除元素时可能发生内存重分配（比如扩容）或元素整体移动，导致迭代器失效；遍历过程中继续使用失效的迭代器会产生未定义行为，从而引发崩溃或各种不可预期的内存问题。
  • 不只是范围 for，任何使用迭代器遍历 vector 的场景，在对 vector 进行结构性修改（插入 / 删除）时都需要格外小心。

vector 的默认大小和容量

std::vector 的默认大小（即默认构造时的大小）是 0。但是，它通常会有一些默认的容量（Capacity），具体取决于 C++ 标准库的实现。

  • (1) 默认构造的大小（Size）

    • 当直接声明一个空的 std::vector 时，它不包含任何元素，因此默认 v.size() 是 0。
      1
      2
      std::vector<int> v; 
      std::cout << v.size(); // 输出 0
    • 此时，v.empty() 返回 true，且不能通过 v[0] 访问元素（这会触发未定义行为）。

  • (2) 默认构造的容量（Capacity）

    • 容量（Capacity）是指 std::vector 在不需要重新分配内存（扩容）的情况下可以容纳的最大元素数量。
    • C++ 标准库并没有规定 std::vector 的默认容量（Capacity）是多少。
    • 在大多数现代 C++ 标准库实现（如 GCC 的 libstdc++、Clang 的 libc++、MSVC 的 STL）中，默认构造的 std::vector 不分配任何堆内存。
    • 因此，默认 v.capacity() 通常也是 0。

  • (3) 特殊情况：预留容器空间

    • 如果使用了 v.reserve()，情况会不同：
      1
      2
      std::vector<int> v;
      v.reserve(100);     // 此时 size() 仍为 0，但 capacity() >= 100
    • 此时，std::vector 已经分配了内存，但还没有构造任何元素。

  • (4) 指定大小的构造

    • 如果 std::vector 在构造时指定了大小，那么 size 和 capacity 都会等于该值：
      1
      std::vector<int> v(10);    // size() == 10, capacity() >= 10，并且这 10 个 int 元素会被默认初始化为 0

  • (5) 总结说明

    构造方式size()capacity()
    std::vector<T> v;0 通常为 0（取决于 C++ 标准库的实现）
    std::vector<T> v(10);10>= 10
    std::vector<T> v; v.reserve(10);0>= 10

特别注意

千万不要将 size 和 capacity 混淆。size 是实际存储的元素个数，capacity 是当前分配的内存能容纳的最大元素个数（超过这个数量就会触发容器扩容 / 重新分配内存）。

vector 的自动扩容机制

std::vector 的扩容机制是指当当前容量（capacity）不足以容纳新元素时，容器会重新申请一块更大的连续内存，将原有元素移动或复制到新内存中，再释放旧内存。扩容后的容量通常会按照一定的增长策略扩大，而不是每次只增加一个元素，以减少频繁内存分配带来的开销。扩容过程中会导致原有元素的地址、迭代器和引用失效，因此如果能够预估元素数量，可以提前使用 reserve() 预留容量，从而减少扩容次数，提高容器性能。

自动扩容案例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <vector>
#include <string>

using namespace std;

class MyClass {
public:
    MyClass() {
        std::cout << "MyClass()" << std::endl;
    }

    MyClass(const MyClass& obj) {
        std::cout << "MyClass(const MyClass & obj)" << std::endl;
    }

    ~MyClass() {
        std::cout << "~MyClass()" << std::endl;
    }

private:
    string m_str;
};

int main() {
    vector<MyClass> vec;

    for (int i = 0; i < 3; ++i) {
        cout << "---------- begin ----------" << endl;
        cout << "容器插入元素之前 size = " << vec.size() << endl;
        cout << "容器插入元素之前 capacity = " << vec.capacity() << endl;
        vec.push_back(MyClass());
        cout << "容器插入元素之后 size = " << vec.size() << endl;
        cout << "容器插入元素之后 capacity = " << vec.capacity() << endl;
        cout << "---------- end ------------" << endl;
    }

    return 0;
}

程序运行输出的结果如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
---------- begin ----------
容器插入元素之前 size = 0
容器插入元素之前 capacity = 0
MyClass()
MyClass(const MyClass & obj)
~MyClass()
容器插入元素之后 size = 1
容器插入元素之后 capacity = 1
---------- end ------------
---------- begin ----------
容器插入元素之前 size = 1
容器插入元素之前 capacity = 1
MyClass()
MyClass(const MyClass & obj)
MyClass(const MyClass & obj)
~MyClass()
~MyClass()
容器插入元素之后 size = 2
容器插入元素之后 capacity = 2
---------- end ------------
---------- begin ----------
容器插入元素之前 size = 2
容器插入元素之前 capacity = 2
MyClass()
MyClass(const MyClass & obj)
MyClass(const MyClass & obj)
MyClass(const MyClass & obj)
~MyClass()
~MyClass()
~MyClass()
容器插入元素之后 size = 3
容器插入元素之后 capacity = 4
---------- end ------------
~MyClass()
~MyClass()
~MyClass()
自动扩容案例分析

在上面这段案例代码中，通过 push_back() 不断向 std::vector 中添加 MyClass 对象，可以观察到 std::vector 的扩容过程以及扩容时拷贝构造函数、析构函数的调用情况。

  • (1) 第一次插入

    • 初始状态：size = 0、capacity = 0。
    • 插入元素后：size = 1、capacity = 1。
    • 执行 push_back(MyClass()) 时，首先会创建临时 MyClass 对象，然后通过拷贝构造函数将临时对象复制到 std::vector 中，最后析构临时对象。
    • 因此本次操作出现 1 次拷贝构造 + 1 次析构。

  • (2) 第二次插入触发扩容

    • 此时 size = 1、capacity = 1，没有剩余空间，因此需要扩容到 capacity = 2。
    • 扩容过程：
      • 原来的 1 个元素需要通过拷贝构造函数复制到新的内存空间，因此调用 1 次拷贝构造函数。
      • 新插入的临时对象也通过拷贝构造函数进入 std::vector，再调用 1 次拷贝构造函数。
      • 原内存中的旧元素被销毁，调用 1 次析构函数。
      • push_back 使用的临时对象随后也被销毁，再调用 1 次析构函数。
    • 因此本次操作出现 2 次拷贝构造函数 + 2 次析构函数。

  • (3) 第三次插入再次扩容

    • 此时 size = 2、capacity = 2，再次触发扩容，当前实现将 capacity 从 2 扩大到 4。
    • 扩容过程：
      • 原来的 2 个元素分别进行拷贝构造，共调用 2 次拷贝构造函数。
      • 新插入的临时对象也通过拷贝构造函数进入 std::vector，再调用 1 次拷贝构造函数。
      • 原内存中的 2 个旧元素被销毁，共调用 2 次析构函数。
      • 新插入的临时对象随后被销毁，再调用 1 次析构函数。
    • 因此本次操作出现 3 次拷贝构造 + 3 次析构。

  • (4) 为什么会调用多次拷贝构造函数？

    • 每次 std::vector 扩容时，大致需要经历：
      • 申请更大的连续内存 → 将原有元素迁移到新内存 → 销毁旧内存中的元素 → 插入新元素
    • 本例中的 MyClass 没有移动构造函数，因此元素迁移时使用的是拷贝构造函数。

  • (5) 总结说明

    • 上述案例中拷贝构造函数的调用次数可以概括为：
      插入元素capacity拷贝构造次数
      第 1 次 0 → 11
      第 2 次 1 → 22
      第 3 次 2 → 43
    • 因此，std::vector 扩容的核心代价就是重新分配内存并迁移已有元素。如果元素没有移动构造函数，旧元素迁移过程中就可能会大量调用拷贝构造函数。

  • (6) 案例代码分析图解：

自动扩容案例优化

std::vector 扩容时会重新申请更大的内存，并将原有元素迁移到新内存中。当元素类型提供 noexcept 移动构造函数时，std::vector 通常会优先使用移动构造，从而减少拷贝构造带来的额外开销；如果移动构造可能抛出异常，则可能会选择拷贝构造，以保证扩容过程的异常安全性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <string>
#include <utility>
#include <vector>

using namespace std;

class MyClass {
public:
    MyClass() {
        m_str = "Hello C++";
        std::cout << "MyClass()" << std::endl;
    }

    // 拷贝构造函数
    MyClass(const MyClass& obj) {
        m_str = obj.m_str;
        std::cout << "MyClass(const MyClass & obj)" << std::endl;
    }

    // 移动构造函数
    MyClass(MyClass&& obj) noexcept {
        m_str = std::move(obj.m_str);
        std::cout << "MyClass(MyClass&& obj)" << std::endl;
    }

    ~MyClass() {
        std::cout << "~MyClass()" << std::endl;
    }

private:
    string m_str;
};

int main() {
    vector<MyClass> vec;

    for (int i = 0; i < 3; ++i) {
        cout << "---------- begin ----------" << endl;
        cout << "容器插入元素之前 size = " << vec.size() << endl;
        cout << "容器插入元素之前 capacity = " << vec.capacity() << endl;
        vec.push_back(MyClass());
        cout << "容器插入元素之后 size = " << vec.size() << endl;
        cout << "容器插入元素之后 capacity = " << vec.capacity() << endl;
        cout << "---------- end ------------" << endl;
    }

    return 0;
}

程序运行输出的结果如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
---------- begin ----------
容器插入元素之前 size = 0
容器插入元素之前 capacity = 0
MyClass()
MyClass(MyClass&& obj)
~MyClass()
容器插入元素之后 size = 1
容器插入元素之后 capacity = 1
---------- end ------------
---------- begin ----------
容器插入元素之前 size = 1
容器插入元素之前 capacity = 1
MyClass()
MyClass(MyClass&& obj)
MyClass(MyClass&& obj)
~MyClass()
~MyClass()
容器插入元素之后 size = 2
容器插入元素之后 capacity = 2
---------- end ------------
---------- begin ----------
容器插入元素之前 size = 2
容器插入元素之前 capacity = 2
MyClass()
MyClass(MyClass&& obj)
MyClass(MyClass&& obj)
~MyClass()
MyClass(MyClass&& obj)
~MyClass()
~MyClass()
容器插入元素之后 size = 3
容器插入元素之后 capacity = 4
---------- end ------------
~MyClass()
~MyClass()
~MyClass()

特别注意

如果使用 v.emplace_back()，虽然可以避免插入新元素时产生不必要的临时对象以及拷贝 / 移动操作，但无法避免 std::vector 扩容时对已有元素的迁移（会调用拷贝构造函数来实现）。通过提供 noexcept 移动构造函数，可以让 std::vector 在扩容迁移元素时优先使用移动构造，从而减少拷贝构造的开销。需要注意的是，移动构造并不会消除析构函数的调用，它只是避免了对象内容的拷贝。每一个构造出来的对象，都必须对应一次析构，包括临时对象。

vector 与迭代器的使用

迭代器的概述

std::vector 提供了多种迭代器类型，用于以不同方式遍历和访问容器元素。其迭代器属于随机访问迭代器（Random Access Iterator），支持 ++、--、+n、-n、[] 下标访问等操作，效率与指针相当。

迭代器的使用注意事项

  • std::vector 的迭代器，本质上类似指针，内部通常就是原始指针或指针封装。
  • 往 std::vector 插入、删除元素（尤其是触发扩容时）会导致迭代器失效。
  • 范围 for、STL 算法（如 std::find()、std::sort()）底层都依赖迭代器来实现。
  • 使用范围 for 遍历 std::vector 时，不应在遍历过程中对容器执行插入或删除元素的操作，否则会导致未定义行为，从而引发崩溃或各种不可预期的内存问题。
迭代器的类型

vector 容器的迭代器有四种类型：

  • iterator：普通正向迭代器
  • const_iterator：只读正向迭代器
  • reverse_iterator：普通反向迭代器（逆序）
  • const_reverse_iterator：只读反向迭代器（逆序）

  • vector<string>::iterator

    • 普通正向迭代器
    • 从第一个元素遍历到最后一个元素
    • 允许修改元素内容
      1
      2
      3
      4
      5
      vector<string> v = {"a", "b", "c"};

      for (vector<string>::iterator it = v.begin(); it != v.end(); ++it) {
          *it = "x";   // 可以修改元素值
      }

  • vector<string>::const_iterator

    • 只读正向迭代器
    • 不能通过迭代器修改元素的值
    • 常用于只读遍历，提升代码语义安全性
      1
      2
      3
      4
      5
      vector<string> v = {"a", "b", "c"};

      for (vector<string>::const_iterator it = v.cbegin(); it != v.cend(); ++it) {
          cout << *it << endl;
      }

  • vector<string>::reverse_iterator

    • 普通反向迭代器
    • 从最后一个元素遍历到第一个元素
    • 允许修改元素内容
    • 底层仍基于普通迭代器实现
      1
      2
      3
      4
      5
      vector<string> v = {"a", "b", "c"};

      for (vector<string>::reverse_iterator it = v.rbegin(); it != v.rend(); ++it) {
          *it = "x";   // 可以修改元素值
      }

  • vector<string>::const_reverse_iterator

    • 只读反向迭代器
    • 不能通过迭代器修改元素的值
    • 常用于反向只读访问
      1
      2
      3
      4
      5
      vector<string> v = {"a", "b", "c"};

      for (vector<string>::const_reverse_iterator it = v.crbegin(); it != v.crend(); ++it) {
          cout << *it << " ";
      }

迭代器的操作

vector 的迭代器属于随机访问迭代器（Random Access Iterator），支持 ++、--、+n、-n、[] 下标访问等操作，效率与指针相当。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<string> v1 = {"a", "b", "c", "d", "e"};
vector<string>::iterator it = v1.begin();

// 迭代器支持 * 操作
cout << *it << endl;

// 迭代器支持 [] 操作
cout << it[1] << endl;

// 迭代器支持 ++ 操作
++it;
cout << *it << endl;

// 迭代器支持 -- 操作
--it;
cout << *it << endl;

程序运行输出的结果如下：

1
2
3
4
a
b
b
a
迭代器的失效

迭代器失效是指：在使用容器迭代器的过程中，由于对容器进行了结构性修改（如调用容器的 erase()、insert()、push_back()、resize()、clear() 等成员函数），导致原本指向容器元素的迭代器不再指向有效元素或合法位置，此时继续使用该迭代器会产生未定义行为。因此，修改容器后必须确认迭代器是否仍然有效，必要时重新获取或使用返回的新迭代器。

  • 错误示例一：范围 for 中删除 vector 的元素
1
2
3
4
5
6
// 一边遍历 vector，一边删除元素
for (int x : v) {
    if (x == 3) {
        v.erase(v.begin());  // 错误写法：范围 for 内部迭代器失效，会导致未定义行为
    }
}
  • 错误示例二：遍历 vector 时删除元素（迭代器失效）
1
2
3
4
5
6
7
8
vector<int> v1 = {1, 2, 3, 4, 5};

// 一边遍历 vector，一边删除元素
for (vector<int>::iterator it = v1.begin(); it != v1.end(); ++it) {
    if (*it % 2 == 0) {
        v1.erase(it);   // 错误写法：erase() 调用后会导致当前位置及其后的迭代器全部失效，后续 ++it 操作的是失效迭代器，属于未定义行为
    }
}
  • 错误示例三：遍历 vector 时插入元素（迭代器失效）
1
2
3
4
5
6
7
8
vector<int> v = {1, 2, 3};

// 一边遍历 vector，一边插入元素
for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it == 2) {
        v.insert(it, 100);   // 错误写法：可能触发扩容，导致迭代器 it 失效
    }
}
  • 正确示例一：使用 erase() 的返回值继续遍历
1
2
3
4
5
6
7
8
9
10
vector<int> v1 = {1, 2, 3, 4, 5};

// 一边遍历 vector，一边删除元素
for (vector<int>::iterator it = v1.begin(); it != v1.end();) {
    if (*it % 2 == 0) {
        it = v1.erase(it);  // 正确写法：使用 erase() 返回的新迭代器，erase() 返回指向被删除元素下一个位置的有效迭代器
    } else {
        ++it;
    }
}
  • 正确示例二：使用 erase() + remove_if()，避免遍历时删除
1
2
3
4
5
6
7
8
9
vector<int> v1 = {1, 2, 3, 4, 5};

// 正确写法：先用算法调整元素，再统一 erase()，避免遍历过程中修改容器
// remove_if() 算法负责把不需要的元素移动到容器末尾，并返回新的逻辑结尾；erase() 再把这段无效区间真正删除，这样可以避免在遍历过程中修改容器
v1.erase(
    remove_if(v1.begin(), v1.end(),
                [](int x) { return x % 2 == 0; }),
    v1.end()
);
  • 正确示例三：使用 insert() 的返回值继续遍历
1
2
3
4
5
6
7
8
9
10
11
vector<int> v1 = {1, 2, 3};

// 一边遍历 vector，一边插入元素
for (auto it = v1.begin(); it != v1.end();) {
    if (*it == 2) {
        it = v1.insert(it, 100);  // 正确写法：使用 insert() 返回的新迭代器
        it += 2;                  // 跳过原元素和新插入的元素
    } else {
        ++it;
    }
}
  • 正确示例四：不在遍历时插入
1
2
3
4
5
6
7
8
9
10
11
vector<int> v = {1, 2, 3};
vector<int> result;

for (int x : v) {
    if (x == 2) {
        result.push_back(100);
    }
    result.push_back(x);
}

v.swap(result);

总结

  • C++ 中迭代器失效是指在容器发生结构性修改后，原有迭代器不再指向有效元素，继续使用失效的迭代器会导致未定义行为，正确做法是使用 erase()、insert() 的返回值或避免在遍历过程中修改（插入 / 删除）容器。
  • 由于范围 for 遍历 vector 本质上依赖迭代器，因此使用范围 for 遍历 std::vector 时，不应在遍历过程中对容器执行插入或删除元素的操作，否则会导致未定义行为，从而引发崩溃或各种不可预期的内存问题。
容器类型内存结构insert() 导致的迭代器失效erase() 导致的迭代器失效推荐写法说明
vector 连续内存⚠️ 发生扩容时：所有迭代器、指针、引用全部失效
⚠️ 未扩容时：插入点及其后的迭代器失效		⚠️ 被删位置及其后的迭代器全部失效it = v.erase(it)
erase() + remove_if()		连续内存，插入 / 删除需要移动元素，是迭代器最容易失效的容器。
deque 分段连续⚠️ 可能导致所有迭代器失效
⚠️ C++ 标准未保证稳定性，尤其是中间插入		⚠️ 可能导致所有迭代器失效尽量只在头尾两端操作分段连续结构，迭代器稳定性差，不要依赖 deque 的迭代器长期有效。
list 双向链表✅ 插入不使任何已有迭代器失效✅ 仅被删除元素的迭代器失效list::insert()
list::remove_if()		节点独立，插入删除只改指针，迭代器最稳定。
map / set 红黑树✅ 插入不使任何已有迭代器失效✅ 仅被删除元素的迭代器失效it = m.erase(it)树结构保持节点稳定，删除时必须接收返回迭代器继续遍历。