c++顺序容器（一）https://developer.aliyun.com/article/1437142?spm=a2c6h.13262185.profile.38.5bba685cuSQkDD
特殊的 forward_list 操作
在 C++ 标准模板库（STL）中，std::forward_list 是一个单向链表，它提供了一些特殊的操作，适用于单向链表的特性。这些操作与其他顺序容器（如 std::vector、std::list）有所不同。以下是 std::forward_list 的一些特殊操作的详细介绍：
1. 在指定位置前插入元素
insert_after()：在指定迭代器位置之后插入一个或多个元素。
示例：在 std::forward_list 中插入元素
std::forward_list<int> flist = {1, 2, 3}; auto it = flist.begin(); // 获取迭代器指向第一个元素 flist.insert_after(it, 4); // 在第一个元素之后插入 4
2. 删除元素
erase_after()：删除指定迭代器之后的元素。
示例：删除 std::forward_list 中的元素
flist.erase_after(it); // 删除第一个元素之后的元素
3. 改变容器大小
由于 std::forward_list 是单向链表，它没有提供 resize() 方法。相应的，你需要使用迭代器或其他方法来改变大小。
4. 添加和删除元素
push_front() 和 pop_front()：在容器的开头添加或删除元素。
示例：在 std::forward_list 的开头添加和删除元素
flist.push_front(0); // 在开始处添加 0 flist.pop_front(); // 删除开始处的元素
完整代码示例
下面是一个综合示例，展示了 std::forward_list 的这些特殊操作。
#include <iostream> #include <forward_list> int main() { std::forward_list<int> flist = {1, 2, 3}; // 插入元素 auto it = flist.begin(); // 迭代器指向第一个元素 flist.insert_after(it, 4); // 在第一个元素之后插入 4 // 删除元素 flist.erase_after(it); // 删除第一个元素之后的元素 // 添加和删除元素 flist.push_front(0); // 在开始处添加 0 flist.pop_front(); // 删除开始处的元素 // 输出 forward_list std::cout << "Forward list elements: "; for(int elem : flist) { std::cout << elem << " "; } std::cout << std::endl; return 0; }
输出：
Forward list elements: 1 2 3
容器操作可能使迭代器失效
在 C++ 中使用标准模板库（STL）的容器时，特别需要注意容器操作可能导致迭代器失效的情况。迭代器失效意味着迭代器不再指向有效的容器元素或容器的末尾。以下是导致迭代器失效的一些常见原因及其解释：
1. 添加或删除元素
影响：在 std::vector、std::string、std::deque 等容器中添加或删除元素可能导致所有指向容器元素的迭代器、指针和引用失效。
示例：std::vector 添加元素导致迭代器失效
std::vector<int> vec = {1, 2, 3}; auto it = vec.begin(); // 迭代器指向第一个元素 vec.push_back(4); // 可能导致 it 失效
2. std::vector 和 std::string 的动态内存重新分配
影响：如果容器需要扩展其底层的动态数组来容纳更多元素，所有现有迭代器、指针和引用都将失效。
3. std::list 和 std::forward_list 的元素删除
影响：在 std::list 或 std::forward_list 中删除元素会导致指向被删除元素的迭代器失效，但其他迭代器不受影响。
示例：std::list 删除元素导致迭代器失效
std::list<int> lst = {1, 2, 3}; auto it = lst.begin(); // 迭代器指向第一个元素 lst.erase(it); // it 现在失效
4. std::map 和 std::set 的元素删除
影响：删除 std::map 或 std::set 中的元素会导致指向该元素的迭代器失效，但其他迭代器不受影响。
防止迭代器失效的策略
使用返回的迭代器：某些操作，如 erase()，返回新的有效迭代器。
避免在容器迭代过程中进行插入或删除：在迭代容器时，避免执行可能导致迭代器失效的操作。
使用索引而非迭代器：对于支持随机访问的容器，比如 std::vector，使用索引而不是迭代器进行元素访问。
完整代码示例
这是一个展示如何处理迭代器可能失效的情况的示例：
#include <iostream> #include <vector> #include <list> int main() { // Vector 示例 std::vector<int> vec = {1, 2, 3}; vec.push_back(4); // 在迭代后添加元素，避免迭代器失效 // List 示例 std::list<int> lst = {1, 2, 3}; auto it = lst.begin(); it = lst.erase(it); // 使用返回的迭代器 // 输出结果 std::cout << "Vector: "; for (int v : vec) { std::cout << v << " "; } std::cout << "\nList: "; for (int l : lst) { std::cout << l << " "; } std::cout << std::endl; return 0; }
输出：
Vector: 1 2 3 4 List: 2 3
在这个示例中，std::vector 在迭代之后进行了添加操作，以避免迭代器失效。对于 std::list，使用 erase() 方法返回的新迭代器来避免迭代器失效的问题。
Vector 对象的增长机制
在 C++ 中，std::vector 是一个动态数组，它可以在运行时根据需要自动调整其大小。std::vector 的增长机制是通过动态内存分配和拷贝构造来实现的。以下是 std::vector 增长过程的详细介绍：
1. 动态内存分配
当向 std::vector 添加元素且当前容量不足以容纳更多元素时，它会执行一次动态内存分配。这个过程包括以下几个步骤：
a. 计算新的容量
新的容量通常是当前容量的两倍，这种增长策略旨在平衡内存使用和复制操作的次数，以实现渐进式扩展。这种增长策略称为几何增长。
b. 分配新内存
std::vector 会分配一个更大的内存块来存储其元素。新分配的内存大小至少与计算出的新容量一致。
c. 移动元素
现有元素被移动或复制到新的内存位置。这通常通过调用元素的移动构造函数或复制构造函数完成。
d. 释放旧内存
一旦所有元素都移动到新的内存位置，std::vector 会释放原来的内存块。
2. 复杂性和性能
由于重新分配涉及复制或移动所有现有元素到新的内存位置，因此这个操作的时间复杂度是线性的，即 O(n)，其中 n 是 std::vector 中的元素数量。然而，由于几何增长策略，这种重分配不是经常发生的。这意味着平均情况下，向 std::vector 添加一个元素的时间复杂度仍然是常数级的，即 O(1)。
3. 保留额外容量
通过 reserve() 成员函数，可以预先分配足够的内存以避免频繁的内存重新分配。这在已知 std::vector 将要存储大量元素时非常有用。
示例
#include <iostream> #include <vector> int main() { std::vector<int> vec; // 初始容量可能为零 std::cout << "Initial capacity: " << vec.capacity() << std::endl; // 添加元素，触发容量增长 for(int i = 0; i < 10; ++i) { vec.push_back(i); std::cout << "Capacity after adding element " << i << ": " << vec.capacity() << std::endl; } return 0; }
在这个示例中，每次向 std::vector 添加元素时，打印其容量，以观察其如何增长。不过要注意的是，具体的增长策略可能因编译器和库的实现而异。
额外的 string 操作
在 C++ 中，std::string 类提供了许多强大的操作，用于处理和操作字符串数据。除了基本的赋值、访问和大小操作之外，std::string 还提供了一些额外的功能，使得字符串处理更加灵活和高效。以下是一些常用的额外 std::string 操作：
1. 字符串连接
operator+= 和 append()：用于连接字符串或字符到现有的 std::string 对象。
示例：字符串连接
std::string str = "Hello"; str += ", World!"; // 使用 operator+= 进行连接 str.append(" Welcome."); // 使用 append() 方法进行连接
2. 查找和替换
- find()：查找子字符串或字符在字符串中的位置。
- replace()：替换字符串中的某部分为另一个字符串。
示例：查找和替换
std::string str2 = "Hello, World!"; size_t pos = str2.find("World"); // 查找 "World" if (pos != std::string::npos) { str2.replace(pos, 5, "C++"); // 替换 "World" 为 "C++" }
3. 插入和删除
- insert()：在指定位置插入字符串或字符。
- erase()：删除字符串中的一部分。
示例：插入和删除
std::string str3 = "Hello, World!"; str3.insert(6, "C++ "); // 在位置 6 插入 "C++ " str3.erase(0, 6); // 删除从位置 0 开始的 6 个字符
4. 子字符串
substr()：从字符串中提取子字符串。
示例：提取子字符串
std::string str4 = "Hello, World!"; std::string sub = str4.substr(7, 5); // 提取从位置 7 开始的 5 个字符
5. 字符串比较
compare()：比较两个字符串。
示例：字符串比较
std::string str5 = "Hello"; int result = str5.compare("Hello"); // 比较字符串
完整代码示例
这是一个展示上述 std::string 操作的综合示例：
#include <iostream> #include <string> int main() { // 字符串连接 std::string str = "Hello"; str += ", World!"; str.append(" Welcome."); // 查找和替换 std::string str2 = "Hello, World!"; size_t pos = str2.find("World"); if (pos != std::string::npos) { str2.replace(pos, 5, "C++"); } // 插入和删除 std::string str3 = "Hello, World!"; str3.insert(6, "C++ "); str3.erase(0, 6); // 提取子字符串 std::string str4 = "Hello, World!"; std::string sub = str4.substr(7, 5); // 字符串比较 std::string str5 = "Hello"; int result = str5.compare("Hello"); // 输出结果 std::cout << "Concatenated string: " << str << std::endl; std::cout << "Replaced string: " << str2 << std::endl; std::cout << "Modified string: " << str3 << std::endl; std::cout << "Substring: " << sub << std::endl; std::cout << "Comparison result: " << result << std::endl; return 0; }
输出：
Concatenated string: Hello, World! Welcome. Replaced string: Hello, C++! Modified string: C++ World! Substring: World Comparison result: 0
容器适配器
在 C++ 标准模板库（STL）中，容器适配器是一种特殊类型的容器，它在现有容器的基础上提供了一定的功能封装。容器适配器并不是真正的容器，而是在一定程度上改变或增加了基础容器的行为。常见的容器适配器包括 stack、queue 和 priority_queue。
1. Stack（栈）
特性：std::stack 提供了后进先出（LIFO）的数据结构。它只允许从一端（顶部）进行元素的添加和移除。
基础容器：默认情况下，stack 是基于 std::deque 实现的，但也可以使用 std::list 或 std::vector。
主要操作：
push()：在栈顶添加一个元素。
pop()：移除栈顶元素。
top()：访问栈顶元素。
empty()、size()：检查栈是否为空，获取栈中元素的数量。
示例：使用 std::stack
#include <stack> std::stack<int> stack; stack.push(1); // 添加元素 stack.push(2); stack.pop(); // 移除元素 int top = stack.top(); // 访问栈顶元素
2. Queue（队列）
特性：std::queue 提供了先进先出（FIFO）的数据结构。它允许在一端（队尾）添加元素，在另一端（队头）移除元素。
- 基础容器：默认情况下，queue 是基于 std::deque 实现的，但也可以使用 std::list。
- 主要操作：
- push()：在队尾添加一个元素。
- pop()：移除队头的元素。
- front()、back()：访问队头和队尾元素。
- empty()、size()：检查队列是否为空，获取队列中元素的数量。
示例：使用 std::queue
#include <queue> std::queue<int> queue; queue.push(1); // 添加元素 queue.push(2); queue.pop(); // 移除元素 int front = queue.front(); // 访问队头元素
3. Priority Queue（优先队列）
特性：std::priority_queue 提供了一种方式，使得队头总是包含最大元素（或根据指定的比较函数确定的顺序）的队列。
- 基础容器：默认情况下，priority_queue 是基于 std::vector 实现的，但也可以使用 std::deque。
- 主要操作：
- push()：添加一个元素。
- pop()：移除最大元素（位于队头）。
- top()：访问最大元素。
- empty()、size()：检查优先队列是否为空，获取元素的数量。
示例：使用 std::priority_queue
#include <queue> std::priority_queue<int> pq; pq.push(3); pq.push(1); pq.push(2); int top = pq.top(); // top 现在是 3 pq.pop(); // 移除最大元素
