C++容器适配器与迭代器详解

# C++ 容器适配器与迭代器详解 ## 1. 容器适配器 C++ 标准库除了基本容器类之外，还提供了容器适配器。容器适配器是预定义的容器，它们提供受限的接口以满足特殊需求，并且是通过基本容器类实现的。常见的容器适配器有以下几种： - **栈（Stack）**：遵循后进先出（LIFO）原则管理元素。 - **队列（Queue）**：遵循先进先出（FIFO）原则管理元素，相当于普通的缓冲区。 - **优先队列（Priority Queue）**：元素可以有不同的优先级，优先级基于程序员提供的排序准则（默认使用 `<` 运算符）。优先队列中，下一个元素总是队列中优先级最高的元素。如果有多个元素具有最高优先级，它们的顺序是未定义的。 容器适配器在历史上是 STL 的一部分，但从程序员的角度来看，它们只是使用 STL 提供的容器、迭代器和算法通用框架的特殊容器类。 ## 2. 迭代器 ### 2.1 迭代器的概念 自 C++11 起，可以使用基于范围的 for 循环处理所有元素。但要查找某个元素时，可能不想处理所有元素，而是需要遍历元素直到找到目标元素，并且可能希望存储该元素的位置以便后续继续迭代或进行其他处理。因此，需要一个表示容器中元素位置的对象概念，满足该概念的对象称为迭代器。实际上，基于范围的 for 循环是该概念的便捷接口，它内部使用迭代器对象遍历所有元素。 迭代器是可以遍历元素（从一个元素导航到另一个元素）的对象，这些元素可以是 STL 容器的全部或部分元素。迭代器表示容器中的某个位置，其基本操作定义了迭代器的行为： - `*` 运算符：返回当前位置的元素。如果元素有成员，可以使用 `->` 运算符直接从迭代器访问这些成员。 - `++` 运算符：使迭代器前进到下一个元素。大多数迭代器也允许使用 `--` 运算符后退。 - `==` 和 `!=` 运算符：返回两个迭代器是否表示相同的位置。 - `=` 运算符：赋值迭代器（即它所指向元素的位置）。 这些操作提供了与 C 和 C++ 中普通指针遍历普通数组元素时相同的接口，但迭代器可能是智能指针，用于遍历容器中更复杂的数据结构。迭代器的内部行为取决于其所遍历的数据结构，因此每种容器类型都提供自己的迭代器类型。迭代器共享相同的接口但类型不同，这直接引出了泛型编程的概念：操作使用相同的接口但不同的类型，因此可以使用模板来编写适用于满足该接口的任意类型的通用操作。 ### 2.2 容器的迭代器相关函数 所有容器类都提供相同的基本成员函数，以便使用迭代器遍历其元素，其中最重要的函数如下： - `begin()`：返回表示容器中元素起始位置的迭代器。如果容器有元素，起始位置是第一个元素的位置。 - `end()`：返回表示容器中元素结束位置的迭代器。结束位置是最后一个元素之后的位置，这种迭代器也称为超尾迭代器。 `begin()` 和 `end()` 定义了一个半开区间，包含第一个元素但不包含最后一个元素，这种半开区间有两个优点： 1. 对于遍历元素的循环，有一个简单的结束条件：只要未到达 `end()` 就继续循环。 2. 避免了对空区间的特殊处理。对于空区间，`begin()` 等于 `end()`。 以下是一个使用迭代器打印列表容器所有元素的示例： ```cpp // stl/list1old.cpp #include <list> #include <iostream> using namespace std; int main() { list<char> coll; // list container for character elements // append elements from ’a’ to ’z’ for (char c = 'a'; c <= 'z'; ++c) { coll.push_back(c); } // print all elements: // - iterate over all elements list<char>::const_iterator pos; for (pos = coll.begin(); pos != coll.end(); ++pos) { cout << *pos << ' '; } cout << endl; } ``` 在创建列表并填充字符 `'a'` 到 `'z'` 后，使用迭代器在普通 for 循环中打印所有元素。迭代器 `pos` 在循环前声明，其类型是容器类用于常量元素访问的迭代器类型。 每个容器定义两种迭代器类型： 1. `container::iterator`：用于以读写模式遍历元素。 2. `container::const_iterator`：用于以只读模式遍历元素。 例如，在 `list` 类中，定义可能如下： ```cpp namespace std { template <typename T> class list { public: typedef ... iterator; typedef ... const_iterator; ... }; } ``` `iterator` 和 `const_iterator` 的具体类型由实现定义。 在 for 循环中，迭代器 `pos` 首先初始化为第一个元素的位置，循环继续直到 `pos` 到达容器元素的末尾。在循环体中，`*pos` 表示当前元素，由于使用了 `const_iterator`，不能修改元素。但如果使用非常量迭代器且元素类型不是常量，则可以更改元素的值，例如： ```cpp // make all characters in the list uppercase list<char>::iterator pos; for (pos = coll.begin(); pos != coll.end(); ++pos) { *pos = toupper(*pos); } ``` 如果使用迭代器遍历（无序）映射和多重映射的元素，`pos` 将引用键/值对。`pos->second` 将产生键/值对的第二部分，即元素的值，而 `pos->first` 将产生其（常量）键。 ### 2.3 `++pos` 与 `pos++` 在将迭代器移动到下一个元素时，建议使用前置递增运算符 `++pos`，因为它可能比后置递增运算符 `pos++` 具有更好的性能。后置递增运算符内部涉及一个临时对象，因为它必须返回迭代器的旧位置。虽然这种性能改进通常无关紧要，但在这种情况下，使用前置递增运算符不会带来额外的代价，因此一般建议优先使用前置递增和前置递减运算符。 ### 2.4 `cbegin()` 和 `cend()` 自 C++11 起，可以使用 `auto` 关键字指定迭代器的确切类型（前提是在声明迭代器时进行初始化，以便从初始值推导其类型）。例如： ```cpp for (auto pos = coll.begin(); pos != coll.end(); ++pos) { cout << *pos << ' '; } ``` 使用 `auto` 的一个优点是代码更简洁，另一个优点是循环对于更改容器类型等代码修改更健壮。但缺点是迭代器失去了常量性，可能会增加意外赋值的风险。为确保仍然使用常量迭代器，自 C++11 起，容器提供了 `cbegin()` 和 `cend()` 函数，它们返回 `cont::const_iterator` 类型的对象。 总结自 C++11 起，不使用基于范围的 for 循环遍历容器所有元素的循环可能如下： ```cpp for (auto pos = coll.cbegin(); pos != coll.cend(); ++pos) { ... } ``` ### 2.5 基于范围的 for 循环与迭代器 引入迭代器后，可以解释基于范围的 for 循环的具体行为。对于容器，基于范围的 for 循环实际上只是一个便捷接口，用于遍历传递的范围/集合中的所有元素。在每个循环体中，实际元素由当前迭代器指向的值初始化。 因此， ```cpp for (type elem : coll) { ... } ``` 被解释为