C++迭代器深度解析:从STL核心到自定义实现
1. 项目概述:为什么迭代器是C++的“瑞士军刀”?
如果你写过C++,尤其是用过STL容器,那你肯定对for(auto it = vec.begin(); it != vec.end(); ++it)这行代码不陌生。这个it,就是迭代器。但很多人对它的理解,可能就停留在“一个用来遍历容器的指针”。这就像把瑞士军刀只当成开瓶器用,太可惜了。
迭代器在C++中,远不止是一个遍历工具。它是连接算法和容器的桥梁,是泛型编程的基石。STL的设计哲学是“数据结构和算法分离”,而迭代器就是让它们俩“握手”的那个中间人。没有迭代器,std::sort、std::find这些通用算法就得为vector、list、deque每一种容器都写一个版本,那代码量将是灾难性的。
我刚开始学C++时,也觉得迭代器有点绕,不如直接下标访问vec[i]来得直观。但踩过几次坑之后才明白,下标访问只对vector、array、deque这类连续内存的容器友好。当你需要处理一个list(链表)或者set(集合)时,下标操作符[]根本不存在,这时候迭代器就成了唯一且统一的访问方式。更关键的是,当你开始写模板函数,希望它能处理任何容器时,迭代器是唯一的解决方案。理解了迭代器,你才算真正摸到了C++泛型编程和STL设计思想的门槛。
2. 迭代器核心概念与分类体系
2.1 迭代器到底是什么?—— 超越指针的抽象
从最直观的角度看,迭代器确实像一个“智能指针”。它封装了对容器内部元素的访问,提供了类似指针的操作:解引用(*it)来获取元素,自增(++it)来移动到下一个元素。但它的内涵比原生指针丰富得多。
迭代器是一种抽象,它定义了一组操作契约。一个类型只要满足了这组契约,就可以被当作迭代器来使用。这组契约根据支持操作的不同,被分成了五个层次,也就是我们常说的“迭代器类别”。这种分层设计非常精妙,它允许算法根据迭代器能力的不同,选择最高效的实现。比如,std::sort算法需要随机访问元素(即能it + 5直接跳到后面第5个元素),所以它要求传入随机访问迭代器。而std::list的迭代器只支持向前/向后移动(双向迭代器),因此list不能直接用std::sort,但它有自己专用的list::sort成员函数。
注意:很多人混淆“迭代器类型”和“迭代器类别”。我们说的
vector<int>::iterator这是一个具体的迭代器类型,它是vector模板类内部定义的一个类型。而这个类型所属的迭代器类别(如随机访问迭代器),决定了它能进行哪些操作。类别是概念,类型是实体。
2.2 五大迭代器类别详解与能力对比
C++标准定义了五种迭代器类别,它们形成一个层次结构,后者继承前者的所有能力并增加新能力。理解这个层次,是高效使用算法库的关键。
1. 输入迭代器:只读一次的“单程票”这是要求最低的迭代器。它允许你读取它指向的元素(*it),并且可以向前移动(++it),但只能走一次,不能回头。典型代表是从标准输入(如cin)读取数据的迭代器,数据流过就没了。你无法用两个输入迭代器来“倒退”比较。
2. 输出迭代器:只写一次的“单程票”与输入迭代器对应,它只支持写入操作(*it = value)和向前移动。同样是一次性的。向标准输出(cout)写入的迭代器就是例子。
3. 前向迭代器:可重复读写的“多次票”它在输入迭代器的基础上,增加了“可多次通行”的能力。你可以保存一个前向迭代器的副本,之后再用这个副本重新遍历同一段数据。std::forward_list(单链表)的迭代器就是典型的前向迭代器。它支持读写和多次遍历,但仍只能单向前进。
4. 双向迭代器:能进能退的“往返票”这是前向迭代器的增强版,增加了自减(--it)操作,从而可以反向移动。std::list、std::set、std::map等容器的迭代器都是双向迭代器。这让我们可以方便地从后向前遍历。
5. 随机访问迭代器:随心所欲的“直升机”这是功能最强大的迭代器类别。它拥有双向迭代器的所有能力,并额外支持在常数时间内进行跳跃访问。具体来说,它支持:
- 与整数进行加减法:
it + n,it - n - 自增减任意偏移量:
it += n,it -= n - 迭代器相减得到距离:
it1 - it2 - 使用下标运算符:
it[n](等价于*(it + n)) - 关系比较:
it1 < it2,it1 > it2(双向迭代器只支持==和!=)
std::vector、std::deque、std::array和原生指针的迭代器都是随机访问迭代器。这也是为什么vector的性能通常表现最佳的原因之一,算法可以对其使用最灵活、最高效的访问模式。
为了方便你理解,我将它们的核心操作和能力总结成下表:
| 迭代器类别 | 读 (*it) | 写 (*it=) | 自增 (++) | 自减 (--) | 随机访问 (it+n,it[n]) | 关系比较 (<,>) | 典型容器 |
|---|---|---|---|---|---|---|---|
| 输入迭代器 | ✔ | ✘ | ✔ | ✘ | ✘ | ✘ (仅==,!=) | istream_iterator |
| 输出迭代器 | ✘ | ✔ | ✔ | ✘ | ✘ | ✘ (仅==,!=) | ostream_iterator |
| 前向迭代器 | ✔ | ✔ | ✔ | ✘ | ✘ | ✘ (仅==,!=) | std::forward_list |
| 双向迭代器 | ✔ | ✔ | ✔ | ✔ | ✘ | ✘ (仅==,!=) | std::list,std::set,std::map |
| 随机访问迭代器 | ✔ | ✔ | ✔ | ✔ | ✔ | ✔ | std::vector,std::deque,std::array, 原生指针 |
2.3 相关类型:iterator、const_iterator 与反向迭代器
在具体使用时,我们还会遇到几种相关的迭代器类型,它们是对上述类别概念的具体化。
iterator 与 const_iterator几乎所有标准容器都定义了这两种类型。iterator是可读可写的迭代器,而const_iterator是只读迭代器。当你只需要遍历容器而不修改元素时,应优先使用const_iterator,这既是良好的编程习惯(表明意图),也能避免一些意外的修改错误。C++11的cbegin()和cend()函数就是用来获取const_iterator的。
std::vector<int> vec = {1, 2, 3}; // 可修改的迭代器 for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) { *it *= 2; // 可以修改元素 } // 只读的迭代器(推荐用于只读遍历) for (std::vector<int>::const_iterator cit = vec.cbegin(); cit != vec.cend(); ++cit) { // *cit *= 2; // 错误!不能通过const_iterator修改元素 std::cout << *cit << std::endl; }反向迭代器反向迭代器适配器允许你从后向前遍历容器。对于支持双向迭代器的容器,你可以通过rbegin()和rend()成员函数获取反向迭代器。rbegin()指向容器的最后一个元素,rend()指向第一个元素之前的理论位置。反向迭代器自增(++)操作是向容器的前端移动,这需要一点时间来适应。
std::vector<int> vec = {1, 2, 3, 4, 5}; // 正向输出: 1 2 3 4 5 // 反向输出: 5 4 3 2 1 for (auto rit = vec.rbegin(); rit != vec.rend(); ++rit) { std::cout << *rit << " "; }实操心得:反向迭代器的一个常见“坑”是它与正向迭代器的转换。
reverse_iterator有一个base()成员函数,可以返回对应的正向迭代器。但要注意,rit.base()指向的是rit所指向元素的下一个位置。例如,vec.rbegin().base()等于vec.end()。在需要将反向迭代器指向的位置插入或删除元素时,这个关系非常重要,否则很容易造成差一错误。
3. 迭代器实战:从基础遍历到高级应用
理解了概念,我们就要上手实操。迭代器的使用贯穿C++编程的始终,下面我通过几个由浅入深的场景,带你掌握它的核心用法。
3.1 基础遍历:告别下标,拥抱泛型
最基本的用法就是遍历容器。虽然C++11引入了基于范围的for循环,但理解迭代器遍历是理解后者的基础。
#include <iostream> #include <vector> #include <list> #include <set> int main() { std::vector<int> vec = {10, 20, 30, 40, 50}; std::list<std::string> lst = {"Hello", "World", "C++"}; std::set<double> st = {3.14, 2.718, 1.414}; // 1. 传统迭代器遍历 (vector) std::cout << "Vector traversal: "; for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) { std::cout << *it << " "; } std::cout << std::endl; // 2. 使用auto简化 (list) std::cout << "List traversal: "; for (auto it = lst.begin(); it != lst.end(); ++it) { std::cout << *it << " "; } std::cout << std::endl; // 3. 基于范围的for循环 (set) - 其底层实现就是迭代器 std::cout << "Set traversal: "; for (const auto& value : st) { std::cout << value << " "; } std::cout << std::endl; // 4. 反向迭代器遍历 std::cout << "Vector reverse traversal: "; for (auto rit = vec.rbegin(); rit != vec.rend(); ++rit) { std::cout << *rit << " "; } std::cout << std::endl; return 0; }注意事项:在遍历容器并可能修改其结构(如删除元素)时,要特别小心迭代器失效问题。对于
vector和deque,在中间插入或删除元素会使所有指向其后位置的迭代器、引用和指针失效。对于list和关联容器,只有指向被删除元素的迭代器会失效。一个常见的做法是使用it = container.erase(it)的返回值来获取下一个有效迭代器,或者在删除前用it++先行移动到下一个元素。
3.2 与算法库的完美配合:解锁STL的真正力量
迭代器的高光时刻在于与<algorithm>库的配合。标准库提供了上百个通用算法,绝大多数都通过迭代器来操作数据范围。
示例1:查找与计数
#include <algorithm> #include <vector> #include <iostream> int main() { std::vector<int> data = {5, 2, 8, 2, 9, 1, 2, 7}; // 使用 std::find 查找第一个等于2的元素 auto find_it = std::find(data.begin(), data.end(), 2); if (find_it != data.end()) { std::cout << "Found first 2 at position: " << std::distance(data.begin(), find_it) << std::endl; } // 使用 std::count 计算2出现的次数 int count = std::count(data.begin(), data.end(), 2); std::cout << "Number 2 appears " << count << " times." << std::endl; // 使用 std::find_if 查找第一个大于5的元素 auto find_if_it = std::find_if(data.begin(), data.end(), [](int x) { return x > 5; }); if (find_if_it != data.end()) { std::cout << "First element > 5 is: " << *find_if_it << std::endl; } return 0; }示例2:排序与变换
#include <algorithm> #include <vector> #include <iostream> #include <iterator> // 用于 std::back_inserter int main() { std::vector<int> src = {1, 3, 5, 7, 9}; std::vector<int> dst; // 使用 std::copy 复制元素到另一个容器 // std::back_inserter 创建一个输出迭代器,在dst尾部插入 std::copy(src.begin(), src.end(), std::back_inserter(dst)); // 使用 std::transform 对每个元素进行操作 std::vector<int> squared; std::transform(src.begin(), src.end(), std::back_inserter(squared), [](int x) { return x * x; }); // 输出结果 std::cout << "Copied vector: "; for (int x : dst) std::cout << x << " "; std::cout << "\nSquared vector: "; for (int x : squared) std::cout << x << " "; std::cout << std::endl; // 使用 std::sort 排序 (需要随机访问迭代器) std::vector<int> to_sort = {5, 3, 8, 1, 9}; std::sort(to_sort.begin(), to_sort.end()); // 默认升序 std::cout << "Sorted: "; for (int x : to_sort) std::cout << x << " "; std::cout << std::endl; return 0; }示例3:更复杂的算法组合我们来看一个综合例子:从一组数据中移除所有偶数,然后将剩下的数字乘以3,最后输出。
#include <algorithm> #include <vector> #include <iostream> #include <iterator> int main() { std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // 1. 使用 std::remove_if 将不需要的元素“移动”到容器末尾 // 注意:remove_if 并不真正删除元素,而是返回一个新的“逻辑终点”迭代器 auto new_end = std::remove_if(numbers.begin(), numbers.end(), [](int n) { return n % 2 == 0; }); // 移除偶数 // 2. 真正从容器中擦除这些元素 numbers.erase(new_end, numbers.end()); // 此时 numbers = {1, 3, 5, 7, 9} // 3. 使用 std::transform 修改剩余元素 std::transform(numbers.begin(), numbers.end(), numbers.begin(), [](int n) { return n * 3; }); // 此时 numbers = {3, 9, 15, 21, 27} // 4. 使用输出迭代器将结果输出到cout std::cout << "Result: "; std::copy(numbers.begin(), numbers.end(), std::ostream_iterator<int>(std::cout, " ")); std::cout << std::endl; return 0; }这个例子展示了“erase-remove”惯用法,这是STL中删除特定元素的标准且高效的做法。直接在一个循环中调用erase会导致多次元素移动和迭代器失效,而remove_if配合一次erase则高效得多。
3.3 迭代器适配器:扩展迭代器的能力
迭代器适配器是标准库提供的工具,它们包装现有的迭代器,赋予其新的行为。上面用到的std::back_inserter和std::ostream_iterator就是输出迭代器适配器。这里再介绍两个强大的适配器。
插入迭代器当我们使用std::copy等算法时,目标容器必须有足够的空间。插入迭代器解决了这个问题,它会在赋值时调用容器的插入操作。
std::back_inserter(container): 使用container.push_back(),在尾部插入。std::front_inserter(container): 使用container.push_front(),在头部插入(要求容器支持)。std::inserter(container, pos): 在指定迭代器位置pos之前插入。
std::vector<int> src = {1, 2, 3}; std::vector<int> dst; // 错误:dst为空,copy会访问非法内存 // std::copy(src.begin(), src.end(), dst.begin()); // 正确:使用back_inserter std::copy(src.begin(), src.end(), std::back_inserter(dst)); // dst 现在为 {1, 2, 3} std::list<int> lst; // 使用front_inserter,结果会是逆序 std::copy(src.begin(), src.end(), std::front_inserter(lst)); // lst 现在为 {3, 2, 1} (注意顺序)流迭代器流迭代器允许你将输入/输出流当作序列来操作。
std::istream_iterator<T>: 从输入流读取T类型的数据。std::ostream_iterator<T>: 向输出流写入T类型的数据。
#include <iostream> #include <iterator> #include <vector> #include <algorithm> int main() { // 从标准输入读取整数,直到遇到非整数或EOF std::cout << "Enter some integers (Ctrl+Z/D to end): "; std::istream_iterator<int> input_start(std::cin); std::istream_iterator<int> input_end; // 默认构造表示“流结束” std::vector<int> numbers(input_start, input_end); // 用迭代器范围构造vector // 对数字排序 std::sort(numbers.begin(), numbers.end()); // 输出到标准输出,每个数后跟一个空格 std::cout << "Sorted numbers: "; std::copy(numbers.begin(), numbers.end(), std::ostream_iterator<int>(std::cout, " ")); std::cout << std::endl; return 0; }这段代码非常简洁地实现了从控制台读取一串数字、排序、再输出的功能,完全通过迭代器和算法完成,无需显式循环。
4. 手把手实现一个自定义迭代器
理解了迭代器的使用,再深入一层就是实现它。这能让你彻底明白迭代器的抽象是如何工作的。我们来为一个简单的自定义容器实现一个迭代器。
假设我们有一个固定大小的环形缓冲区RingBuffer。它内部使用数组存储,当到达数组末尾时,会绕回到开头。
4.1 定义容器与迭代器类
首先,我们定义容器类的基本结构:
template <typename T, size_t Capacity> class RingBuffer { private: T data[Capacity]; size_t head = 0; // 指向下一个可写入的位置 size_t tail = 0; // 指向下一个可读取的位置 size_t count = 0; // 当前元素数量 public: // 嵌套的迭代器类声明 class iterator; // 容器操作函数(省略部分,如push, pop) void push(const T& value) { /* ... */ } T pop() { /* ... */ } // 获取迭代器 iterator begin(); iterator end(); };接下来是核心部分——实现嵌套的iterator类。为了让我们的迭代器能与STL算法协同工作,我们需要为其定义一些必要的类型别名(typedef或using),这被称为迭代器特征。
template <typename T, size_t Capacity> class RingBuffer<T, Capacity>::iterator { private: RingBuffer* buffer; // 指向所属容器的指针 size_t pos; // 当前逻辑位置(0 到 count-1) size_t index; // 在内部数组中的实际索引 // 私有构造函数,仅供RingBuffer的begin/end函数调用 iterator(RingBuffer* buf, size_t logical_pos) : buffer(buf), pos(logical_pos) { // 计算实际索引:从head开始,考虑环形绕回 index = (buffer->head + logical_pos) % Capacity; } friend class RingBuffer<T, Capacity>; // 允许RingBuffer访问私有构造函数 public: // --- 迭代器特征 (Iterator Traits) --- // 这些类型别名是让迭代器与STL算法兼容的关键 using iterator_category = std::random_access_iterator_tag; using value_type = T; using difference_type = std::ptrdiff_t; using pointer = T*; using reference = T&; // --- 必需的操作符重载 --- // 解引用操作符 reference operator*() const { return buffer->data[index]; } // 成员访问操作符 (->) pointer operator->() const { return &(buffer->data[index]); } // 前缀自增 iterator& operator++() { ++pos; index = (buffer->head + pos) % Capacity; return *this; } // 后缀自增 (int是伪参数,用于区分前缀) iterator operator++(int) { iterator temp = *this; ++(*this); // 调用前缀自增 return temp; } // 比较操作符 bool operator==(const iterator& other) const { // 两个迭代器相等,当且仅当它们指向同一个缓冲区且逻辑位置相同 return buffer == other.buffer && pos == other.pos; } bool operator!=(const iterator& other) const { return !(*this == other); } // --- 为支持随机访问迭代器类别而增加的操作 --- // 这些让我们的迭代器更强大 // 自减操作符(双向迭代器要求) iterator& operator--() { --pos; index = (buffer->head + pos) % Capacity; return *this; } iterator operator--(int) { iterator temp = *this; --(*this); return temp; } // 与整数加减(随机访问迭代器要求) iterator operator+(difference_type n) const { iterator temp = *this; temp.pos += n; temp.index = (buffer->head + temp.pos) % Capacity; return temp; } iterator operator-(difference_type n) const { return *this + (-n); } iterator& operator+=(difference_type n) { pos += n; index = (buffer->head + pos) % Capacity; return *this; } iterator& operator-=(difference_type n) { return *this += (-n); } // 下标操作符 reference operator[](difference_type n) const { return *(*this + n); } // 迭代器相减得到距离 difference_type operator-(const iterator& other) const { return static_cast<difference_type>(pos) - static_cast<difference_type>(other.pos); } // 关系比较操作符 bool operator<(const iterator& other) const { return pos < other.pos; } bool operator>(const iterator& other) const { return pos > other.pos; } bool operator<=(const iterator& other) const { return pos <= other.pos; } bool operator>=(const iterator& other) const { return pos >= other.pos; } };4.2 实现容器的begin和end函数
现在,我们在RingBuffer类中实现begin()和end()函数,它们返回指向第一个元素和“尾后”位置的迭代器。
template <typename T, size_t Capacity> typename RingBuffer<T, Capacity>::iterator RingBuffer<T, Capacity>::begin() { // 逻辑位置0,即第一个有效元素 return iterator(this, 0); } template <typename T, size_t Capacity> typename RingBuffer<T, Capacity>::iterator RingBuffer<T, Capacity>::end() { // 逻辑位置count,即最后一个有效元素之后 return iterator(this, count); }4.3 测试我们的自定义迭代器
最后,我们写一个简单的测试程序,验证迭代器是否工作,并且能否与STL算法一起使用。
#include <iostream> #include <algorithm> // 用于std::for_each int main() { RingBuffer<int, 5> rb; // 向环形缓冲区添加一些数据 for (int i = 0; i < 5; ++i) { rb.push(i * 10); // 添加 0, 10, 20, 30, 40 } std::cout << "Traversal using iterator: "; // 使用迭代器遍历 for (auto it = rb.begin(); it != rb.end(); ++it) { std::cout << *it << " "; } std::cout << std::endl; std::cout << "Traversal using range-based for loop: "; // 基于范围的for循环也能用了! for (const auto& val : rb) { std::cout << val << " "; } std::cout << std::endl; std::cout << "Using std::for_each algorithm: "; // 使用STL算法 std::for_each(rb.begin(), rb.end(), [](int x) { std::cout << x << " "; }); std::cout << std::endl; // 测试随机访问能力 if (std::distance(rb.begin(), rb.end()) > 2) { auto it = rb.begin(); std::cout << "Third element (using it[2]): " << it[2] << std::endl; // 应输出20 it += 3; std::cout << "After it+=3, element is: " << *it << std::endl; // 应输出30 } return 0; }通过这个完整的例子,你可以看到,一旦我们正确地实现了迭代器接口(特别是那些类型别名和操作符),我们的自定义容器就能无缝融入C++的生态系统,享受所有泛型算法带来的便利。这就是迭代器模式的威力所在。
5. 迭代器实战中的“坑”与高级技巧
在实际项目中,迭代器用起来很爽,但也有一些需要特别注意的地方和可以提升效率的技巧。
5.1 迭代器失效:最常见的“坑”及其规避策略
迭代器失效是使用STL容器时最常遇到的问题之一。当容器结构发生变化(插入、删除元素)时,指向容器元素的迭代器、引用或指针可能会变得无效。失效规则因容器而异:
| 容器类型 | 插入操作导致失效 | 删除操作导致失效 |
|---|---|---|
std::vector/std::string | 若导致重分配,所有迭代器失效;否则,插入点及之后的迭代器失效。 | 删除点及之后的迭代器失效。 |
std::deque | 在首尾插入,迭代器失效但引用/指针不失效;在中间插入,所有迭代器失效。 | 在首尾删除,只有被删元素的迭代器失效;在中间删除,所有迭代器失效。 |
std::list/std::forward_list | 不会使其他迭代器失效。 | 只有指向被删除元素的迭代器失效。 |
关联容器 (set,map, 等) | 不会使其他迭代器失效。 | 只有指向被删除元素的迭代器失效。 |
无序关联容器 (unordered_set, 等) | 若导致重哈希,所有迭代器失效;否则,不影响。 | 只有指向被删除元素的迭代器失效。 |
规避策略:
- 最小化失效范围:对于
vector,尽量使用reserve()预先分配足够空间,避免插入时的重分配。 - 使用返回值更新迭代器:
erase()函数会返回指向被删除元素之后位置的迭代器,利用它。std::vector<int> vec = {1, 2, 3, 2, 4}; for (auto it = vec.begin(); it != vec.end(); /* 不在for循环中自增 */) { if (*it == 2) { it = vec.erase(it); // erase返回下一个有效迭代器 } else { ++it; } } - 先自增,后删除:对于
list、map等,可以先保存下一个迭代器。std::list<int> lst = {1, 2, 3, 4}; for (auto it = lst.begin(); it != lst.end(); /* 不在for循环中自增 */) { if (*it % 2 == 0) { auto next_it = std::next(it); // 保存下一个 lst.erase(it); it = next_it; } else { ++it; } }
5.2 性能考量:迭代器与下标访问的选择
对于vector和array,使用下标[]访问和迭代器访问在性能上没有区别,现代编译器都能优化得很好。选择哪种更多是风格和场景问题。
迭代器访问的优势:
- 泛型性:编写的模板代码可以适用于所有容器。
- 与算法结合:直接用于STL算法。
- 明确性:使用
const_iterator可以明确表达“只读”意图。
下标访问的优势:
- 直观:对于简单的循环,
for(int i=0; i<vec.size(); ++i)可能更易读。 - 需要索引时:当你确实需要元素的索引位置时,下标更直接。
- 直观:对于简单的循环,
我的经验是,在容器通用的算法或函数模板中,坚持使用迭代器。在明确的、只针对vector/array的局部循环中,可以根据可读性选择下标。不要因为性能的臆测而牺牲代码的清晰度和通用性。
5.3 使用C++11/14/17新特性简化迭代
现代C++提供了更多工具来简化迭代器相关的代码。
auto关键字:这是迭代器最好的朋友,省去了冗长的类型声明。// C++98 风格 for (std::vector<std::pair<int, std::string>>::iterator it = map.begin(); it != map.end(); ++it) // C++11 以后 for (auto it = map.begin(); it != map.end(); ++it)基于范围的for循环:在大多数只需要遍历元素值的场景下,这是最简洁的写法。
for (const auto& element : container) { ... }它的底层就是使用迭代器实现的,等价于:
for (auto it = std::begin(container); it != std::end(container); ++it) { const auto& element = *it; ... }非成员函数的
begin()和end():在C++11后,推荐使用非成员函数std::begin(cont)和std::end(cont),而不是成员函数cont.begin()。因为它们更通用,可以用于数组和自定义类型(只要你为自定义类型提供了begin/end的重载)。int arr[] = {1, 2, 3}; // 可以用于原生数组 std::sort(std::begin(arr), std::end(arr));结构化绑定 (C++17):在遍历
map或元素为pair的容器时,结构化绑定让代码极其清晰。std::map<int, std::string> id_name = {{1, "Alice"}, {2, "Bob"}}; // C++17 之前 for (const auto& kv : id_name) { std::cout << "ID: " << kv.first << ", Name: " << kv.second << std::endl; } // C++17 结构化绑定 for (const auto& [id, name] : id_name) { std::cout << "ID: " << id << ", Name: " << name << std::endl; }
5.4 自定义算法与迭代器搭配
当你需要编写自己的泛型算法时,迭代器是你的核心参数。设计时,应尽量使用要求最低的迭代器类别,以最大化算法的适用范围。
例如,一个查找算法可能只需要输入迭代器:
template <typename InputIt, typename T> InputIt my_find(InputIt first, InputIt last, const T& value) { for (; first != last; ++first) { if (*first == value) { return first; } } return last; // 未找到 }这个算法可以用于任何提供输入迭代器的序列,包括输入流、链表、数组等。
而一个二分查找算法则需要随机访问迭代器,因为它需要快速跳到中间位置:
template <typename RandomIt, typename T> bool my_binary_search(RandomIt first, RandomIt last, const T& value) { auto left = first; auto right = last; while (left < right) { auto mid = left + (right - left) / 2; // 随机访问迭代器支持 `+` 和 `-` if (*mid == value) return true; if (*mid < value) left = mid + 1; else right = mid; } return false; } // 注意:这个简化版本要求序列已排序理解迭代器的类别,并据此设计你的函数接口,是编写高质量、可复用C++库代码的关键技能。
