第九章 顺序容器

9.1 顺序容器概述

1.顺序容器类型及核心特性

容器类型	底层结构	随机访问	插入/删除效率	内存管理	适用场景
vector	动态数组	O(1)	尾部O(1)，中间/头部O(n)	连续内存，扩容需拷贝	频繁随机访问、尾部操作（如排序、遍历）
deque	分段连续数组	O(1)	头尾O(1)，中间O(n)	分段存储，扩容代价小	双端队列、滑动窗口（需两端操作且偶尔随机访问）
list	双向链表	O(n)	任意位置O(1)	非连续内存，额外指针	频繁任意位置插入/删除（如游戏对象管理）
forward_list	单向链表	O(n)	仅支持单向插入/删除（O(1)）	最小内存开销	内存敏感场景，仅需单向操作
array	固定数组	O(1)	不支持	栈分配，大小固定	元素数量固定的场景（替代内置数组）
string	字符动态数组	O(1)	类似vector，尾部高效	连续内存，优化字符串	字符串处理（支持查找、拼接等特殊操作）

2. 性能折中与选择原则

关键权衡因素

• 随机访问 vs. 插入/删除效率

  • vector/deque支持快速随机访问，但中间插入代价高。

  • list/forward_list任意位置插入高效，但无法随机访问。

• 内存开销

  • 链表容器（list/forward_list）因指针开销占用更多内存，缓存不友好。

  • vector/deque内存连续，缓存命中率高，但扩容可能引发数据迁移。

选择建议

1. 默认选择 vector

   • 除非有特殊需求（如频繁中间插入），优先使用 vector（随机访问快、内存高效）。

2. 特定场景优化

   • 双端操作：deque（如任务队列）。

   • 频繁中间插入：list或 forward_list（如实时数据流处理）。

   • 固定大小：array（安全替代内置数组）。

3. 复合策略

   • 输入阶段用 list插入，完成后拷贝到 vector以优化后续访问。

3. 操作复杂度对比

操作	vector	deque	list	forward_list
随机访问	O(1)	O(1)	O(n)	O(n)
头部插入	O(n)	O(1)	O(1)	O(1)
尾部插入	O(1)	O(1)	O(1)	O(n)
中间插入	O(n)	O(n)	O(1)	O(1)
迭代器稳定性	可能失效	可能失效	稳定	稳定

4. 实际应用技巧

• 预分配内存：vector.reserve()避免频繁扩容。

• 避免迭代器失效：list插入/删除不影响其他迭代器，vector/deque需谨慎。

• 适配器选择：stack/queue默认基于 deque，priority_queue基于 vector。

总结

顺序容器的选择需综合访问模式、操作频率和内存效率。vector是通用首选，而 list/deque在特定场景下性能更优。现代C++标准库的实现已高度优化，建议优先使用标准容器而非原始数组

9.2 容器库概述

1. 容器操作的层次性

容器操作分为三个层次，适用于不同范围的容器类型：

1. 所有容器通用的操作

   • 包括构造函数、赋值操作（=）、大小查询（size()、empty()）、迭代器操作（begin()、end()）、比较运算符（==、!=）等。

   • 例如：swap()可交换两个同类型容器的内容，时间复杂度通常为O(1)。

2. 特定容器类别的操作

   • 顺序容器（如vector、list、deque）：支持push_back()、insert()、emplace()等位置相关操作。

   • 关联容器（如map、set）：提供基于键的查找（find()、count()）和排序操作。

   • 无序容器（如unordered_map）：支持哈希查找，平均O(1)时间复杂度。

3. 仅少数容器的特殊操作

   • 例如：list和forward_list的splice()用于链表拼接，priority_queue的top()访问最高优先级元素。

2. 容器的头文件与模板类

• 每个容器定义在与其同名的头文件中（如#include <vector>、#include <list>）。

• 容器均为模板类，需指定元素类型（如vector<int>、list<string>）。

  • 嵌套容器：支持容器元素为其他容器（如vector<vector<string>>），但旧编译器需在尖括号间加空格（如vector< vector<string> >）。

3. 元素类型的限制

• 通用限制：

  • 元素类型必须可拷贝或移动（如unique_ptr需满足移动语义）。

  • 析构函数不能抛出异常。

• 特定操作的限制：

  • 顺序容器的resize(n)要求元素类型有默认构造函数（若无，需通过resize(n, val)指定初始值）。

  • 关联容器的元素需定义比较运算符（默认operator<）。

  • 无序容器的元素需支持哈希函数和相等比较（operator==）。

4. 容器选择与性能考量

• 默认选择：vector（连续内存、随机访问高效），除非有特殊需求。

• 特殊场景：

  • 频繁中间插入/删除：list或forward_list（链表结构）。

  • 双端操作：deque（头尾操作高效）。

  • 快速查找：关联容器（有序）或无序容器（哈希）。

5. 代码示例与注意事项

// 嵌套容器定义
vector<vector<string>> lines; // 每个元素是一个string的vector
​
// 元素类型无默认构造函数的处理
class MyClass {
public:
    MyClass(int x) {} // 无默认构造函数
};
vector<MyClass> vec; // 合法
// vec.resize(10);    // 错误！需改为：
vec.resize(10, MyClass(0)); // 提供初始值

注意事项：

• 关联容器的键需满足严格弱序（如自定义类型需重载operator<）。

• 无序容器的性能依赖哈希函数质量，复杂类型需自定义哈希。

9.2.1 迭代器

1. 迭代器的公共接口与特性

所有标准库迭代器遵循统一的接口规范，但不同类别的迭代器支持的操作存在差异：

• 基础操作

  • 解引用（*iter）：访问元素值，类似指针操作

  • 递增（++iter）：移动到下一个元素（前向迭代器及以上均支持）

  • 比较（==/!=）：判断迭代器位置是否相同

• 特殊操作

  • 递减（--iter）：仅双向和随机访问迭代器支持（如list、set的迭代器）

  • 算术运算（+n/-n）：仅随机访问迭代器支持（如vector、deque、array）

  • 例外：forward_list迭代器不支持递减操作，因其设计为单向链表

2. 迭代器范围的定义与性质

迭代器范围由两个迭代器 begin和 end表示，需满足以下条件：

• 合法性要求

  • 指向同一容器，且 end可为尾后位置（one past the last element）

  • 通过递增 begin可到达 end（即 end不在 begin之前）

• 左闭合区间（[begin, end)）

  • 包含 begin指向的元素，但不包含 end指向的位置

  • 关键性质：

    1. begin == end时范围为空

    2. begin != end时至少含一个元素，且 begin指向首元素

    3. 有限次递增 begin可使 begin == end（确保循环终止）

3. 迭代器范围的编程实践

安全遍历模式

// 标准遍历循环（适用于所有容器）
for (auto it = container.begin(); it != container.end(); ++it) {
    std::cout << *it << " "; // 安全解引用
}
​
// C++11 范围for循环（等价于迭代器遍历）
for (const auto& elem : container) {
    std::cout << elem << " ";
}

• 注意事项：

  • 避免在遍历中修改容器结构（如插入/删除），可能导致迭代器失效

    随机访问迭代器（如vector）支持 it + n，但其他迭代器需用 std::advance(it, n)

反向迭代器范围

// 从末尾向前遍历
for (auto rit = container.rbegin(); rit != container.rend(); ++rit) {
    std::cout << *rit << " "; // 注意：++rit实际向前移动
}

• 反向迭代器的 ++操作实际指向容器的前一个元素

4. 迭代器类别与容器适配性

迭代器类型	支持操作	典型容器
前向迭代器	++, *, ->	forward_list
双向迭代器	前向操作 + --	list, set, map
随机访问迭代器	双向操作 + +n, -n, []	vector, deque, array

• 容器适配器（如stack、queue）无迭代器，仅通过特定接口操作元素

5. 迭代器失效与安全建议

• 失效场景：

  • 序列容器（vector/deque）：插入/删除可能使所有迭代器失效（因内存重分配）

  • 链表容器（list/forward_list）：仅影响被操作位置的迭代器

• 安全实践：

  • 修改容器后重新获取迭代器（如 it = container.insert(it, value)）

  • 使用算法如 erase-remove模式避免手动管理迭代器

9.2.2 容器类型成员

标准库容器定义了多种类型别名，这些别名提供了与容器元素类型和容器特性相关的统一接口。主要类型别名包括：

• size_type：无符号整数类型，用于表示容器大小（如元素数量）

• iterator和const_iterator：用于遍历容器元素的迭代器类型

• reverse_iterator和const_reverse_iterator：反向迭代器类型

• value_type：容器中元素的类型

• reference和const_reference：元素引用类型

• difference_type：两个迭代器之间距离的有符号整数类型

9.2.3 begin和end成员

1. 返回的迭代器类型不同

• begin()：

  • 返回的迭代器类型取决于容器的常量性

  • 对于非常量容器，返回iterator（可修改元素）

  • 对于常量容器，返回const_iterator（不可修改元素）

• cbegin()：

  • 无论容器是否为常量，总是返回const_iterator（不可修改元素）

  • 这是C++11新引入的特性，专门用于获取常量迭代器

2. 使用场景不同

• begin()：

  • 适用于需要修改容器内容的场景

  • 当容器是非常量时，可以使用返回的iterator修改元素值

• cbegin()：

  • 适用于只需要读取容器内容而不修改的场景

  • 提供额外的安全性，防止意外修改容器内容

3. 与auto关键字结合时的行为

• 使用auto与begin()时，获得的迭代器类型取决于容器的常量性

• 使用auto与cbegin()时，总是获得const_iterator，无论容器的常量性如何

示例代码

#include <iostream>
#include <vector>
​
int main() {
    std::vector<int> v = {1, 2, 3};
    const std::vector<int> cv = {4, 5, 6};
    
    // 使用begin()
    auto it1 = v.begin();    // iterator
    *it1 = 10;              // 可以修改
    auto it2 = cv.begin();  // const_iterator
    // *it2 = 20;           // 编译错误，不能修改
    
    // 使用cbegin()
    auto cit1 = v.cbegin();   // const_iterator
    // *cit1 = 30;           // 编译错误，不能修改
    auto cit2 = cv.cbegin();  // const_iterator
    // *cit2 = 40;           // 编译错误，不能修改
    
    return 0;
}

4. 设计理念

cbegin()的设计遵循了”最小权限原则” – 只提供必要的访问权限（只读），从而增加代码的安全性和稳定性。当确定不需要修改容器内容时，应该优先使用cbegin()和cend()。

9.2.4 容器定义和初始化

一、默认构造函数初始化

所有STL容器都提供默认构造函数，用于创建一个空容器（array除外）。

std::vector<int> vec;      // 空vector
std::list<double> lst;     // 空list
std::map<std::string, int> m; // 空map

对于array容器，默认构造的array是非空的，它包含了与其大小一样多的元素，这些元素都被默认初始化。

std::array<int, 5> arr; // 创建包含5个int的array，元素值未定义

二、拷贝初始化

将一个容器初始化为另一个容器的拷贝有两种方式：

1. 直接拷贝整个容器：要求两个容器的类型及其元素类型必须匹配

std::vector<int> vec1 = {1, 2, 3};
std::vector<int> vec2(vec1); // 直接拷贝

1. 使用迭代器范围拷贝（array除外）：不要求容器类型相同，元素类型可以不同，只要能进行类型转换

std::list<int> lst = {1, 2, 3, 4, 5};
std::vector<double> vec(lst.begin(), lst.end()); // 使用迭代器范围拷贝

三、列表初始化

C++11引入了列表初始化，可以显式指定容器中每个元素的值。

std::vector<int> vec = {1, 2, 3, 4, 5};
std::list<std::string> lst = {"hello", "world"};
std::map<int, std::string> m = {{1, "one"}, {2, "two"}};

对于array容器，列表初始化时初始值数目可以小于array大小，剩余元素会进行值初始化。

std::array<int, 5> arr = {1, 2, 3}; // 前三个元素为1,2,3，后两个为0

四、大小和初始值初始化

顺序容器（array除外）还提供接受容器大小和（可选）元素初始值的构造函数。

std::vector<int> vec1(10);     // 10个元素，默认初始化为0
std::vector<std::string> vec2(5, "hi"); // 5个元素，每个都是"hi"

如果元素类型没有默认构造函数，必须指定显式的元素初始值。

五、array的特殊初始化

由于array的大小是类型的一部分，它有特殊的初始化要求：

1. 必须同时指定元素类型和大小

2. 不支持普通的容器构造函数

3. 可以进行拷贝和赋值（与内置数组不同）

std::array<int, 4> arr1 = {1, 2, 3, 4};
std::array<int, 4> arr2 = arr1; // 合法，与内置数组不同

六、性能考虑

对于vector等动态容器，可以使用reserve()预先分配空间以减少动态扩展的开销。

std::vector<int> vec;
vec.reserve(100); // 预留空间，避免多次重新分配

七、不同类型容器的初始化特点

1. 序列容器（vector, list, deque）：

   • 支持大小和初始值初始化

   • 支持迭代器范围初始化

   • vector有capacity()和reserve()方法

2. 关联容器（set, map等）：

   • 不支持大小参数初始化

   • 通常使用列表初始化或迭代器范围初始化

3. 容器适配器（stack, queue）：

   • 通常基于其他容器初始化

   • 例如：std::stack<int, std::vector<int>> st;

9.2.5 赋值和swap

一、赋值运算符(=)

基本特性

1. 所有容器（包括array）都支持赋值运算符

2. 操作效果：将左边容器中的全部元素替换为右边容器中元素的拷贝

3. 类型要求：左右两边容器类型必须完全相同（容器类型和元素类型）

示例代码

vector<int> v1 = {1, 2, 3};
vector<int> v2;
v2 = v1;  // 正确，类型匹配

array<int, 3> a1 = {4, 5, 6};
array<int, 3> a2;
a2 = a1;  // 正确，array支持赋值（与内置数组不同）

list<string> lst1 = {"a", "b", "c"};
deque<string> deq;
// deq = lst1;  // 错误，容器类型不匹配

大小变化

• 赋值后，左边容器的大小将与右边容器相同

• 如果原大小不同，左边容器会调整大小

二、assign操作（仅顺序容器，array除外）

基本特性

1. 灵活性：可以从不同但相容的类型赋值，或从子序列赋值

2. 操作效果：用参数指定的元素替换容器中所有原有元素

3. 两种形式：

   • 接受迭代器范围

   • 接受数量和一个值

示例代码

list<string> names;
vector<const char*> oldstyle = {"hello", "world"};

// 使用迭代器范围assign
names.assign(oldstyle.begin(), oldstyle.end());  // 将const char*转换为string

// 使用数量和值assign
vector<int> v;
v.assign(5, 10);  // 5个元素，每个都是10

注意事项

• 传递给assign的迭代器不能指向调用assign的容器自身

• 会替换所有原有元素，容器大小可能改变

三、swap操作

基本特性

1. 所有容器都支持swap操作

2. 操作效果：交换两个相同类型容器的内容

3. 性能差异：

   • 对于非array容器：O(1)时间复杂度，只交换内部数据结构

   • 对于array容器：O(n)时间复杂度，真正交换所有元素

示例代码

vector<string> svec1(10);  // 10个空string
vector<string> svec2(24);  // 24个空string
svec1.swap(svec2);  // 交换后svec1有24个元素，svec2有10个

array<int, 3> a1 = {1, 2, 3};
array<int, 3> a2 = {4, 5, 6};
swap(a1, a2);  // 真正交换元素

迭代器有效性

容器类型	迭代器/指针/引用有效性
非array容器	保持有效，但指向的元素现在属于另一个容器
array容器	保持绑定到相同元素，但元素值已交换
string	失效

四、成员与非成员swap

两种版本

1. 成员函数版本：container1.swap(container2)

2. 非成员函数版本：swap(container1, container2)

使用建议

• 在泛型编程中优先使用非成员版本

• 两种版本效果相同，但非成员版本更通用

五、综合比较表

操作	支持容器	类型要求	时间复杂度	大小影响	迭代器有效性
赋值(=)	所有	完全相同	O(n)	可能改变	通常失效
assign	顺序容器(array除外)	元素类型可转换	O(n)	可能改变	通常失效
swap	所有	完全相同	array: O(n) 其他: O(1)	交换大小	非array: 保持有效但所属容器改变 array: 保持绑定但值交换 string: 失效

六、最佳实践建议

1. 赋值操作：

   • 需要完全替换容器内容时使用

   • 注意类型严格匹配要求

2. assign操作：

   • 当需要从不同类型容器或子序列初始化时使用

   • 比先clear()再insert()更高效

3. swap操作：

   • 需要高效交换容器内容时优先使用

   • 注意array的性能特点

   • 对于非array容器，可用于快速清空容器(vector<int>().swap(v))

4. 通用编程：

   • 优先使用非成员swap

   • 利用swap实现异常安全编程

9.3 顺序容器的操作

9.3.1 向顺序容器添加元素

一、顺序容器概述

顺序容器是C++标准库中一类数据结构，用于在内存中线性存储元素。它们支持元素的动态添加、删除和访问，同时保持元素的顺序

。主要顺序容器包括：

• vector：动态数组，支持快速随机访问

• deque：双端队列，支持头尾高效插入/删除

• list：双向链表，支持任意位置高效插入/删除

• forward_list：单向链表，更节省空间

• string：专门用于字符处理的容器

• array：固定大小数组

二、向顺序容器添加元素

1. 尾部添加元素

push_back和emplace_back是向容器尾部添加元素的主要方法：

vector<int> vec;
vec.push_back(10);  // 添加元素10到末尾
vec.emplace_back(20); // 直接构造元素20到末尾[6](@ref)

• 除array和forward_list外，所有顺序容器(包括string)都支持push_back

• emplace_back直接在容器内存中构造对象，避免了临时对象的创建和移动操作

2. 头部添加元素

push_front和emplace_front用于在容器头部添加元素：

list<int> lst;
lst.push_front(10);  // 在头部插入10
lst.emplace_front(20); // 直接构造20在头部[6](@ref)

• 仅list、forward_list和deque支持push_front

• deque保证在容器首尾进行插入和删除元素的操作都只花费常数时间

3. 任意位置插入元素

insert和emplace提供了更灵活的插入方式：

vector<string> svec;
svec.insert(svec.begin(), "Hello"); // 在开始位置插入
svec.emplace(svec.begin()+1, "World"); // 在第二个位置构造元素[1](@ref)

• 所有顺序容器(除array)都支持insert操作

• forward_list有特殊版本的insert

• 插入操作可能使迭代器失效，特别是vector和string

4. 插入多个元素

insert还支持插入多个相同元素或一个范围内的元素：

svec.insert(svec.end(), 10, "Anna"); // 插入10个"Anna"
vector<string> v = {"quasi","simba","frollo","scarn"};
svec.insert(svec.begin(), v.end()-2, v.end()); // 插入v的最后两个元素[1](@ref)

三、关键概念与性能考虑

1. 容器元素是拷贝

当对象被插入容器时，放入的是对象值的拷贝而非对象本身。容器中的元素与原始对象无关联，后续修改互不影响。

2. 性能影响

不同容器和不同位置的插入操作性能差异显著：

• vector/string在尾部之外的插入需要移动元素，可能引发内存重分配

• deque在首尾插入高效(O(1))，中间插入较慢

• list在任何位置插入都高效(O(1))

3. emplace与push的区别

特性	push操作	emplace操作
对象构造	先构造临时对象再拷贝/移动	直接在容器内存中构造
效率	较低(有额外拷贝/移动)	较高(避免临时对象)
语法	需显式创建对象	直接传递构造参数

9.3.2 访问元素

一、顺序容器元素访问方法概述

顺序容器提供了多种访问元素的方法，主要包括以下几种：

1. front()：返回容器首元素的引用（所有顺序容器都支持，除forward_list外）

2. back()：返回容器尾元素的引用（除forward_list外的所有顺序容器支持）

3. operator[]：通过下标访问元素（string、vector、deque和array支持）

4. at()：带边界检查的下标访问（string、vector、deque和array支持）

5. 迭代器访问：通过begin()/end()等迭代器访问元素（所有容器支持）

二、各访问方法详解与比较

1. front() 和 back() 成员函数

vector<int> v = {1, 2, 3};
int& first = v.front();  // 获取首元素引用
int& last = v.back();    // 获取尾元素引用
first = 10;             // 修改首元素值

• 特点：

  • 返回元素的引用，可直接修改元素值

  • 容器为空时行为未定义

  • front()在所有顺序容器中可用（除forward_list）

  • back()在除forward_list外的所有顺序容器中可用

2. 下标运算符 operator[]

vector<int> v = {1, 2, 3};
int elem = v[1];  // 获取第二个元素
v[1] = 20;       // 修改第二个元素

• 特点：

  • 仅支持快速随机访问容器（string、vector、deque和array）

  • 不进行边界检查，越界访问是未定义行为

  • 访问效率高，但不安全

3. at() 成员函数

vector<int> v = {1, 2, 3};
try {
    int elem = v.at(3);  // 越界访问，抛出异常
} catch (const out_of_range& e) {
    cerr << "Error: " << e.what() << endl;
}

• 特点：

  • 支持与operator[]相同的容器

  • 进行边界检查，越界时抛出std::out_of_range异常

  • 比operator[]安全，但性能稍低

4. 迭代器访问

vector<int> v = {1, 2, 3};
auto it = v.begin();  // 获取首元素迭代器
int first = *it;      // 解引用获取值
*it = 10;             // 通过迭代器修改值

// 获取尾元素
auto last_it = v.end();
--last_it;           // 必须递减，因为end指向尾后位置
int last = *last_it;

• 特点：

  • 所有容器都支持迭代器访问

  • 更通用的访问方式，可用于算法

  • 需要小心处理end()迭代器

三、访问方法的安全性与性能比较

方法	边界检查	异常安全	性能	适用容器范围
operator[]	无	不安全	最高	string/vector/deque/array
at()	有	安全	较高	string/vector/deque/array
front()/back()	无	不安全	高	所有顺序容器（部分限制）
迭代器	无	不安全	高	所有容器

9.3.3 删除元素

1. 删除元素的基本原则

• 删除操作不会检查参数的有效性，程序员必须保证要删除的位置是合法的。

• 删除前最好确认容器非空，否则会引发未定义行为。

2. pop_front 和 pop_back

• pop_front：删除第一个元素。

• pop_back：删除最后一个元素。

• 限制：

  • vector 和 string 没有 pop_front。

  • forward_list 没有 pop_back。

• 都返回 void，如果需要被删除的元素值，必须 先保存 它再删除。

3. erase 删除指定位置的元素

• 单个位置删除：

  it = c.erase(it); // 删除 it 指向的元素，并返回指向下一个元素的迭代器

• 范围删除：

  it = c.erase(first, last); // 删除 [first, last) 范围内的元素

• 返回值是 指向被删元素之后的迭代器。

4. 删除所有元素的两种方法

1. 调用 clear()。

2. 调用 erase(c.begin(), c.end())。

📌 要点记忆

• pop_* 只能删除首尾，erase 可以删任意位置/范围。

• 删除后迭代器会失效，必须使用返回的迭代器继续操作。

• clear() 等价于 erase(begin, end)。

9.3.4 特殊的forward_list操作

1. 单向链表的结构特点

• forward_list 是单向链表，每个节点只知道“下一个节点”是谁（next 指针）。

• 没有办法直接得到前驱节点，因为它的链接是单向的。

• 删除一个元素时，要改的是它前驱节点的 next 指针，而不是它自己的。

2. 为什么需要特殊操作

举个例子： 假设链表是：

elem1 -> elem2 -> elem3 -> elem4

要删除 elem3，需要让 elem2->next 指向 elem4。 但单向链表没有从 elem3 找到 elem2 的直接方法，所以你必须先拿到 elem2，才能删除它后面的节点。

因此：

• 删除操作变成了 “删除某节点之后的节点” → erase_after

• 插入操作变成了 “在某节点之后插入” → insert_after / emplace_after

3. 特殊迭代器 before_begin

• 在链表头部插入/删除时，仍然需要“前驱”概念。

• before_begin 提供了一个指向首元素“之前”的位置（实际上是个虚拟位置）。

• 这样就能用 insert_after(before_begin(), x) 在链表最前面插入元素。

4. 遍历和删除的模式

删除 odd 数（奇数）的例子：

cpp复制编辑auto prev = flist.before_begin();
auto curr = flist.begin();

while (curr != flist.end()) {
    if (*curr % 2)  // 是奇数
        curr = flist.erase_after(prev); // 删除 curr
    else {
        prev = curr;  // 都向前走
        ++curr;
    }
}

关键点：

• prev 永远指向 curr 的前驱。

• 删除时只更新 curr，prev 不动。

• 不删除时两个一起前进。

5. 总结核心思想

• 单向链表无法直接访问前驱节点 → 操作必须基于“某节点之后”。

• 所以有 insert_after、erase_after 代替 insert、erase。

• before_begin 让我们能处理链表头的特殊情况。

• 遍历删除时要同时维护 prev 和 curr 两个迭代器。

9.3.6 容器操作可能时迭代器失效

1. 添加元素（insert / push_back / emplace 等）

• vector / string

  • 重新分配存储空间（capacity 扩张）：所有迭代器、指针、引用失效。

  • 未重新分配：插入点之前的迭代器、指针、引用仍有效；插入点之后的失效。

• deque

  • 首尾位置插入：迭代器失效，指针/引用仍有效。

  • 中间位置插入：所有迭代器、指针、引用失效。

• list / forward_list

  • 插入不会使迭代器、指针、引用失效（包括首前/尾后迭代器）。

2. 删除元素（erase / pop 等）

• vector / string

  • 删除点之前的迭代器、指针、引用有效。

  • 删除点及之后的失效（尾后迭代器总是失效）。

• deque

  • 删除首/尾：大部分仍有效（删除尾会使尾后迭代器失效）。

  • 删除中间：所有迭代器、指针、引用失效。

• list / forward_list

  • 删除元素只会使指向该元素的迭代器、指针、引用失效，其他位置的不受影响。

3. 循环中修改容器的注意事项

• 修改后必须更新迭代器：

  • erase 返回指向下一个元素的迭代器 → 不要再手动 ++iter。

  • insert 返回指向新插入元素的迭代器 → 需 ++ 两次跳过新元素和当前元素。

• 不要缓存 end() 返回的迭代器：

  • 对 vector / string / deque（非首尾操作）修改后，原来的 end() 会失效。

  • 解决：每次循环都重新调用 end()。

4. 口诀记忆

“增删之后，更新迭代器；end别缓存，容器随时变。” vector/string：看位置，看扩容。deque：中间毁灭，首尾安全。list系：基本免疫。

运算表达式

#include <iostream>
#include <stack>
#include <string>
#include <cctype> // for isdigit()
#include <stdexcept> // for runtime_error

// 辅助函数：执行具体的计算
int perform_operation(int b, int a, char op) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': 
            if (b == 0) throw std::runtime_error("Division by zero");
            return a / b;
    }
    return 0;
}

// 辅助函数：定义操作符的优先级
int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0; // 对于括号，优先级最低
}

int main() {
    std::string expression = "(1 + ((2 + 3) * 4) - 5)";
    std::cout << "Processing expression: " << expression << std::endl;

```C++
std::stack<int> values;    // 存放操作数的栈
std::stack<char> ops;      // 存放操作符和括号的栈

for (int i = 0; i < expression.length(); ++i) {
    char token = expression[i];

    if (token == ' ') {
        continue; // 忽略空格
    }

    // 如果是数字
    if (isdigit(token)) {
        int num = 0;
        // 处理多位数
        while (i < expression.length() && isdigit(expression[i])) {
            num = num * 10 + (expression[i] - '0');
            i++;
        }
        i--; // 循环会多加一次i，需要减回来
        values.push(num);
    }
    // 如果是左括号
    else if (token == '(') {
        ops.push(token);
    }
    // 如果是右括号
    else if (token == ')') {
        // 这就是题目描述的核心部分
        // 循环计算，直到遇到左括号
        while (!ops.empty() && ops.top() != '(') {
            int val2 = values.top(); values.pop();
            int val1 = values.top(); values.pop();
            char op = ops.top(); ops.pop();
            values.push(perform_operation(val2, val1, op));
        }
        if (!ops.empty()) {
            ops.pop(); // 弹出左括号 '('
        }
    }
    // 如果是操作符
    else {
        // 当栈顶操作符优先级更高或相等时，先计算栈顶的
        while (!ops.empty() && precedence(ops.top()) >= precedence(token)) {
            int val2 = values.top(); values.pop();
            int val1 = values.top(); values.pop();
            char op = ops.top(); ops.pop();
            values.push(perform_operation(val2, val1, op));
        }
        ops.push(token); // 将当前操作符压栈
    }
}

// 处理栈中剩余的操作符
while (!ops.empty()) {
    int val2 = values.top(); values.pop();
    int val1 = values.top(); values.pop();
    char op = ops.top(); ops.pop();
    values.push(perform_operation(val2, val1, op));
}

// 最终，values栈中剩下的唯一元素就是结果
if (!values.empty()) {
    std::cout << "Final result: " << values.top() << std::endl;
}

return 0;
```

}