C++STL迭代器适配器与操作算法深度解析

### C++ STL 迭代器适配器与操作算法深度解析 #### 1. 容器初始化与迭代器适配器概述 在 C++ 编程中，容器的初始化是一个基础操作。例如，可以使用特定的初始大小来初始化 `deque` 容器，确保它有足够的空间容纳另一个容器的所有元素： ```cpp deque<int> coll3(coll1.size()); ``` 需要注意的是，调整大小和初始化大小都会创建新元素，这些元素会通过默认构造函数进行初始化，因为没有为它们传递参数。你可以为构造函数和 `resize()` 传递额外的参数来初始化新元素。 迭代器是一种抽象概念，任何行为像迭代器的对象都可以被视为迭代器。C++ 标准库提供了几种预定义的特殊迭代器，即迭代器适配器，它们不仅是辅助类，还增强了整个概念的功能。常见的迭代器适配器有以下几种： 1. 插入迭代器 2. 流迭代器 3. 反向迭代器 4. 移动迭代器（自 C++11 起） #### 2. 插入迭代器 插入迭代器（或插入器）用于让算法以插入模式而非覆盖模式操作。特别是，插入器解决了算法写入目标空间不足的问题，它能让目标容器相应地增长。插入迭代器内部重新定义了其接口： - 当为其元素赋值时，会将该值插入到所属的集合中。有三种不同的插入迭代器，它们在元素插入位置上有所不同，分别是在前端、后端或指定位置。 - 调用前进操作是无操作。 插入迭代器属于输出迭代器类别，只能在向前迭代时写入/赋值。以下是一个使用插入迭代器的示例代码： ```cpp // stl/copy2.cpp #include <algorithm> #include <iterator> #include <list> #include <vector> #include <deque> #include <set> #include <iostream> using namespace std; int main() { list<int> coll1 = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; // copy the elements of coll1 into coll2 by appending them vector<int> coll2; copy (coll1.cbegin(), coll1.cend(), // source back_inserter(coll2)); // destination // copy the elements of coll1 into coll3 by inserting them at the front // - reverses the order of the elements deque<int> coll3; copy (coll1.cbegin(), coll1.cend(), // source front_inserter(coll3)); // destination // copy elements of coll1 into coll4 // - only inserter that works for associative collections set<int> coll4; copy (coll1.cbegin(), coll1.cend(), // source inserter(coll4,coll4.begin())); // destination } ``` 这个示例使用了三种预定义的插入迭代器： - **后端插入器**：通过调用 `push_back()` 将元素插入到容器的后端。例如： ```cpp copy (coll1.cbegin(), coll1.cend(), // source back_inserter(coll2)); // destination ``` 后端插入器只能用于提供 `push_back()` 成员函数的容器，如 `vector`、`deque`、`list` 和字符串。 - **前端插入器**：通过调用 `push_front()` 将元素插入到容器的前端。例如： ```cpp copy (coll1.cbegin(), coll1.cend(), // source front_inserter(coll3)); // destination ``` 这种插入方式会反转插入元素的顺序。前端插入器只能用于提供 `push_front()` 成员函数的容器，如 `deque`、`list` 和 `forward_list`。 - **通用插入器**：直接在初始化时作为第二个参数传递的位置之前插入元素。通用插入器调用 `insert()` 成员函数，将新值和新位置作为参数。除了 `array` 和 `forward_list` 之外的所有预定义容器都有这样的 `insert()` 成员函数，因此它是关联和无序容器唯一预定义的插入器。对于关联和无序容器，传递的位置只是作为查找正确位置的提示，容器可以选择忽略它。 插入迭代器的功能总结如下表： | 表达式 | 插入器类型 | 功能 | | --- | --- | --- | | `back_inserter(container)` | 后端插入器 | 通过 `push_back(val)` 以相同顺序追加元素 | | `front_inserter(container)` | 前端插入器 | 通过 `push_front(val)` 以相反顺序在前端插入元素 | | `inserter(container,pos)` | 通用插入器 | 通过 `insert(pos,val)` 在 `pos` 位置（以相同顺序）插入元素 | #### 3. 流迭代器 流迭代器用于从流中读取或写入数据，它提供了一种抽象，使键盘输入可以像一个可读取的集合一样操作。同样，你可以将算法的输出直接重定向到文件或屏幕。以下是一个典型的示例代码： ```cpp // stl/ioiter1.cpp #include <iterator> #include <algorithm> #include <vector> #include <string> #include <iostream> using namespace std; int main() { vector<string> coll; // read all words from the standard input // - source: all strings until end-of-file (or error) // - destination: coll (inserting) copy (istream_iterator<string>(cin), // start of source istream_iterator<string>(), // end of source back_inserter(coll)); // destination // sort elements sort (coll.begin(), coll.end()); // print all elements without duplicates // - source: coll // - destination: standard output (with newline between elements) unique_copy (coll.cbegin(), coll.cend(), // source ostream_iterator<string>(cout,"\n")); // destination } ``` 这个程序通过三个语句实现了从标准输入读取所有单词并打印排序后的无重复列表。具体步骤如下： 1. **读取输入**： ```cpp copy (istream_iterator<string>(cin), istream_iterator<string>(), back_inserter(coll)); ``` 这里使用了两个输入流迭代器： - `istream_iterator<string>(cin)`：创建一个从标准输入流 `cin` 读取数据的流迭代器，模板参数 `string` 指定了流迭代器读取的元素类型。每次算法需要处理下一个元素时，输入流迭代器会将其转换为 `cin >> string` 的调用，通常会按单词读取。 - `istream_iterator<string>()`：调用输入流迭代器的默认构造函数，创建一个所谓的流结束迭代器，表示一个无法再读取数据的流。 `copy()` 算法会一直运行，直到第一个参数（递增后）与第二个参数不同。流结束迭代器作为范围的结束，因此算法会从 `cin` 读取所有字符串，直到无法再读取（由于文件结束或错误）。这些单词通过后端插入器插入到 `coll` 中。 2. **排序元素**： ```cpp sort (coll.begin(), coll.end()); ``` 使用 `sort()` 算法对 `coll` 中的所有元素进行排序。 3. **打印无重复元素**： ```cpp unique_copy (coll.cbegin(), coll.cend(), ostream_iterator<string>(cout,"\n")); ``` `unique_copy()` 算法将集合中的所有元素复制到目标 `cout` 中，并消除相邻的重复值。`ostream_iterator<string>(cout,"\n")` 创建一个输出流迭代器，通过调用 `operator <<` 将字符串写入 `cout`，第二个参数 `"\n"` 作为元素之间的分隔符，因此每个元素会单独一行输出。 整个程序的所有组件都是模板，因此你可以轻松更改程序以对其他值类型（如整数或更复杂的对象）进行排序。 #### 4. 反向迭代器 反向迭代器允许算法反向操作，它将内部的递增操作转换为递减操作，反之亦然。所有具有双向迭代器或随机访问迭代器的容器（除了 `forward_list` 之外的所有序列容器和所有关联容器）都可以通过其成员函数 `rbegin()` 和 `rend()` 创建反向迭代器。自 C++11 起，还提供了返回只读迭代器的相应成员函数 `crbegin()` 和 `crend()`。 以下是一个使用反向迭代器的示例代码： ```cpp // stl/reviter1.cpp #include <iterator> #include <algorithm> #include <vector> #include <iostream> using namespace std; int main() { vector<int> coll; // insert elements from 1 to 9 for (int i=1; i<=9; ++i) { coll.push_back(i); } ```