深入理解C++迭代器：让你的C++代码更加灵活

引言

在现代编程中，迭代器是一种非常重要且广泛应用的编程范式。它们为我们提供了一种通用的方法来访问和操作各种数据结构中的元素。C++是一种支持面向对象编程、泛型编程和过程编程的高性能编程语言。在C++中，迭代器在标准库（STL）中的容器和算法的实现中发挥着至关重要的作用。本文将介绍C++迭代器的基本概念、分类、操作和实际应用，并探讨C++11及以后版本中迭代器的新特性。

本文的目的是帮助读者理解C++迭代器的原理和使用方法，以便在编程实践中更有效地使用这一强大的工具。本文将首先简要介绍迭代器的概念和作用，然后详细讨论迭代器的分类和STL中的各种迭代器类型。接着，我们将介绍迭代器的基本操作，如增加和减少迭代器、读取和修改元素值等。此外，本文还将讨论迭代器失效的问题，并提供相应的解决方法。在后续部分，我们将探讨C++11及以后版本中的迭代器新特性，如范围for循环、auto关键字等。最后，我们将通过实际应用举例来演示如何使用迭代器实现常见算法和自定义数据结构。

在阅读本文后，您将对C++迭代器有一个全面的了解，并能在实际编程中灵活应用这一重要概念。让我们开始吧！

---

C++迭代器简介

迭代器(iterator)是一种检查容器内元素并遍历元素的数据类型。
C++更趋向于使用迭代器而不是下标操作，因为标准库为每一种标准容器（如vector）定义了一种迭代器类型，而只用少数容器（如vector）支持下标操作访问容器元素。

a. 迭代器的定义

每种容器都定义了自己的迭代器类型，如vector:

vector<int>::iterator    iter;    //定义一个名为iter的变量

每种容器都定义了一对名为begin和end的成员函数，用于返回迭代器。

下面对迭代器进行初始化操作：

vector<int> ivec;
vector<int>::iterator iter1 = ivec.begin(); //将迭代器iter1初始化为指向ivec容器的第一个元素vector<int>::iterator iter2 = ivec.end(); //将迭代器iter2初始化为指向ivec容器的最后一个元素的下一个位置

注意：

• end并不指向容器的任何元素，而是指向容器的最后元素的下一位置，称为超出末端迭代器（past-the-end iterator）。
• 如果vector为空，则begin返回的迭代器和end返回的迭代器相同。
  一旦像上面这样定义和初始化迭代器，就相当于把该迭代器和容器进行了某种关联，就像把一个指针初始化为指向某一空间地址一样。

b. 迭代器的作用

迭代器的主要作用有以下几点：

• 提供一种通用的访问和操作容器中元素的方法，使得算法可以独立于容器类型来实现。
• 对不同容器类型提供统一的接口，简化了编程过程。
• 实现容器和算法之间的解耦，使得算法可以高度复用。

c. 迭代器与指针的区别

迭代器和指针在很多方面具有相似性，但它们之间也有一些关键区别：

1. 指针是一种低级别的数据结构，直接与内存地址相关；而迭代器是一种抽象概念，可以通过类模板实现，不一定与内存地址直接相关。
2. 迭代器可以支持更丰富的操作，例如在关联容器和无序关联容器中，迭代器可以在插入和删除元素时保持稳定；而指针可能会失效。
3. 迭代器可以应对更加复杂的数据结构，如链表和树等；而指针更适用于连续的内存空间，如数组。
4. 迭代器可以提供更严格的类型检查，有助于提高代码的安全性；而指针操作容易导致内存泄漏、野指针等问题。
   总之，迭代器是一种比指针更高级、更安全的抽象工具，可以方便地操作各种容器中的元素，具有更好的兼容性和可扩展性。

---

迭代器分类

根据迭代器所支持的操作和功能，C++迭代器可分为五类：

a. 输入迭代器（Input Iterator）

输入迭代器是一种只读迭代器，主要用于访问容器中的元素。它支持以下操作：

1. 递增（++）
2. 间接访问（*）：仅限于读取，不能用于修改元素
3. 比较（== 和 !=）
   输入迭代器通常用于单遍扫描的算法，如find、count等.

b. 输出迭代器（Output Iterator）

输出迭代器是一种只写迭代器，主要用于向容器中插入或修改元素。它支持以下操作：

1. 递增（++）
2. 间接访问（*）：仅限于写入，不能用于读取元素
   输出迭代器通常用于单遍扫描的算法，如copy、transform等。

c. 前向迭代器（Forward Iterator）

前向迭代器同时具备输入迭代器和输出迭代器的功能，可以进行读写操作。它支持以下操作：

1. 递增（++）
2. 间接访问（*）：可用于读取和修改元素
3. 比较（== 和 !=）
   前向迭代器通常用于支持多遍扫描的算法，如replace、remove_if等。

d. 双向迭代器（Bidirectional Iterator）

双向迭代器在前向迭代器的基础上增加了递减操作，可以向前向后遍历容器。它支持以下操作：

1. 递增（++）
2. 递减（–）
3. 间接访问（*）：可用于读取和修改元素
4. 比较（== 和 !=）
   双向迭代器通常用于支持反向操作的算法，如reverse、find_end等。

e. 随机访问迭代器（Random Access Iterator）

随机访问迭代器具有最丰富的功能，可以实现随机访问容器中的任意元素。它支持以下操作：

1. 递增（++）和递减（–）
2. 间接访问（*）：可用于读取和修改元素
3. 比较（==、!=、<、>、<= 和 >=）
4. 加法和减法操作（+、-、+= 和 -=）
5. 下标操作（[]）
   随机访问迭代器通常用于支持快速访问容器中任意位置元素的算法，如sort、binary_search等。此类迭代器可以直接跳跃到容器中的任意位置，具有更高的遍历性能。

五类迭代器在C++标准库中的典型应用

• 输入迭代器：std::istream_iterator、std::istreambuf_iterator
• 输出迭代器：std::ostream_iterator、std::ostreambuf_iterator、std::back_insert_iterator、-std::front_insert_iterator、std::insert_iterator
• 前向迭代器：std::forward_list、std::unordered_set、std::unordered_map、std::unordered_multiset、std::unordered_multimap中的迭代器
• 双向迭代器：std::list、std::set、std::map、std::multiset、std::multimap中的迭代器
• 随机访问迭代器：std::vector、std::deque、std::array、std::string中的迭代器

---

STL中的迭代器

a. 容器和迭代器的关系

在STL中，容器和迭代器有着紧密的联系。容器负责存储和组织数据，而迭代器则提供了访问和操作容器中元素的统一接口。迭代器可以被视为容器的一个轻量级“视图”，它可以在不改变容器结构的情况下实现对元素的访问和修改。此外，迭代器还有助于将容器与算法解耦，使得算法可以更加通用地应用于不同类型的容器。

b. 各种容器的迭代器类型

STL中的容器大致可以分为三类：顺序容器、关联容器和无序关联容器。它们分别对应不同的迭代器类型：

i. 顺序容器（vector、list、deque）

顺序容器中的元素按照线性顺序存储，因此它们的迭代器通常具有随机访问（vector和deque）或双向访问（list）的功能。

• vector和deque的迭代器类型：随机访问迭代器（Random Access Iterator）
• list的迭代器类型：双向迭代器（Bidirectional Iterator）

ii. 关联容器（set、map、multiset、multimap）

关联容器中的元素按照一定的顺序或者规则存储，如按键值排序或者基于哈希值的存储。因此，它们的迭代器通常具有双向访问的功能。

• set、map、multiset、multimap的迭代器类型：双向迭代器（Bidirectional Iterator）

iii. 无序关联容器（unordered_set、unordered_map、unordered_multiset、unordered_multimap）

无序关联容器中的元素基于哈希表实现存储，元素的存储顺序并不固定。因此，它们的迭代器通常具有前向访问的功能。

• unordered_set、unordered_map、unordered_multiset、unordered_multimap的迭代器类型：前向迭代器（Forward Iterator）

---

了解STL中各种容器的迭代器类型有助于我们根据实际需求选择合适的容器和迭代器，从而提高编程效率和程序性能。同时，了解容器和迭代器之间的关系可以帮助我们更好地利用STL库提供的功能，编写更加高效和灵活的代码。

---

常用的迭代器操作和STL算法的应用实例

1. 迭代器操作

以下是一些常见的迭代器操作：

递增（++）和递减（–）：用于将迭代器移动到容器中的下一个或上一个元素。
间接访问（*）：用于获取或修改迭代器所指向的元素的值。
加法和减法操作（+、-、+= 和 -=）：仅适用于随机访问迭代器，用于在容器中跳跃式地移动迭代器。
下标操作（[]）：仅适用于随机访问迭代器，用于直接访问容器中指定位置的元素。

2. STL算法实例

以下是一些使用迭代器的STL算法实例：

a. find（查找）

#include <algorithm>
#include <vector>
#include <iostream>int main() {std::vector<int> vec{3, 1, 4, 1, 5, 9, 2, 6};int target = 5;auto it = std::find(vec.begin(), vec.end(), target);if (it != vec.end()) {std::cout << "Found " << target << " at position: " << std::distance(vec.begin(), it) << std::endl;} else {std::cout << "Not found" << std::endl;}return 0;
}

b. sort（排序）

#include <algorithm>
#include <vector>
#include <iostream>int main() {std::vector<int> vec{3, 1, 4, 1, 5, 9, 2, 6};std::sort(vec.begin(), vec.end());for (const auto &val : vec) {std::cout << val << " ";}std::cout << std::endl;return 0;
}

c. count（计数）

#include <algorithm>
#include <vector>
#include <iostream>int main() {std::vector<int> vec{3, 1, 4, 1, 5, 9, 2, 6};int target = 1;int count = std::count(vec.begin(), vec.end(), target);std::cout << "Number of " << target << "s: " << count << std::endl;return 0;
}

---

迭代器操作

在本节中，我们将介绍迭代器的一些基本操作，这些操作有助于我们更好地使用迭代器来操作容器中的元素。

a. 常用操作

//迭代器常用运算操作
*iter                //对iter进行解引用，返回迭代器iter指向的元素的引用
iter->men            //对iter进行解引用，获取指定元素中名为men的成员。等效于(*iter).men
++iter                //给iter加1，使其指向容器的下一个元素
iter++
--iter                //给iter减1，使其指向容器的前一个元素
iter--
iter1==iter2        //比较两个迭代器是否相等，当它们指向同一个容器的同一个元素或者都指向同同一个容器的超出末端的下一个位置时，它们相等 
iter1!=iter2

//使用迭代器遍历容器,并把每个元素置0
for(vector<int>::iterator iter=ivec.begin();iter!=ivec.end();++iter)*iter=0;//初始化mid迭代器，使其指向v中最靠近正中间的元素
vector<int>::iterator    mid=v.begin()+v.size()/2;   

在C++定义的容器类型中，只有vector和queue容器提供迭代器算数运算和除!=和==之外的关系运算：

iter+n     //在迭代器上加（减）整数n，将产生指向容器中钱前面（后面）第n个元素的迭代器。新计算出来的迭代器必须指向容器中的元素或超出容器末端的下一个元素
iter-niter1+=iter2        //将iter1加上或减去iter2的运算结果赋给iter1。两个迭代器必须指向容器中的元素或超出容器末端的下一个元素
iter1-=iter2iter1-iter2      //两个迭代器的减法，得出两个迭代器的距离。两个迭代器必须指向容器中的元素或超出容器末端的下一个元素>,>=,<,<=        //元素靠后的迭代器大于靠前的迭代器。两个迭代器必须指向容器中的元素或超出容器末端的下一个元素

• 迭代器const_iterator

每种容器还定义了一种名为const_iterator的类型。

该类型的迭代器只能读取容器中的元素，不能用于改变其值。

之前的例子中，，而const_iterator类型的迭代器只能用于读不能进行重写。

for(vector<int>::const_iterator iter=ivec.begin();iter!=ivec.end();++iter)cout<<*iter<<endl;       //合法，读取容器中元素值for(vector<int>::const_iterator iter=ivec.begin();iter!=ivec.end();++iter)*iter=0;        //不合法，不能进行写操作

• cbegin和cend运算符

**cbegin和cend 运算符无论对象本身是否是常量，返回值都是const_iterator.

• 注意

const_iterator和const iterator是不一样的，

后者对迭代器进行声明时，必须对迭代器进行初始化，并且一旦初始化后就不能修改其值。

这有点像常量指针和指针常量的关系。

vector<int>    ivec(10);
const    vector<int>::iterator    iter=ivec.begin();
*iter=0;    //合法，可以改变其指向的元素的值
++iter;    //不合法，无法改变其指向的位置

b. 增加和减少迭代器

迭代器可以通过递增和递减操作来移动到容器中的其他元素。对于双向迭代器和随机访问迭代器，可以使用++和–操作符。对于随机访问迭代器，还可以使用+=和-=操作符来实现跳跃式的移动。

std::vector<int> vec{1, 2, 3, 4, 5};
auto it = vec.begin();++it; // it现在指向元素2
--it; // it现在指向元素1
it += 2; // it现在指向元素3
it -= 1; // it现在指向元素2

c. 读取和修改元素值

使用迭代器可以方便地读取和修改容器中的元素。通过对迭代器进行解引用操作，我们可以获得迭代器所指向的元素的引用。

std::vector<int> vec{1, 2, 3, 4, 5};
auto it = vec.begin();int val = *it; // 读取元素值，此时val为1
*it = 10; // 修改元素值，此时vec为{10, 2, 3, 4, 5}

d. 迭代器间的关系比较

迭代器之间可以进行关系比较，如等于、不等于、小于、小于等于、大于和大于等于等。这些比较操作对于判断迭代器是否到达某个位置或者在某个范围内非常有用。

std::vector<int> vec{1, 2, 3, 4, 5};
auto it1 = vec.begin();
auto it2 = vec.end();if (it1 != it2) {std::cout << "it1 and it2 are not equal" << std::endl;
}

e. 迭代器适配器（如反向迭代器、插入迭代器等）

迭代器适配器是一种特殊的迭代器，它可以在原有迭代器的基础上提供额外的功能。

反向迭代器

反向迭代器允许我们从后向前遍历容器。使用rbegin()和rend()函数可以获得容器的反向迭代器。

std::vector<int> vec{1, 2, 3, 4, 5};
for (auto it = vec.rbegin(); it != vec.rend(); ++it) {std::cout << *it << " ";
}
std::cout << std::endl;

插入迭代器

插入迭代器允许我们在不改变原有容器迭代器的情况下，向容器中插入新元素。C++标准库提供了三种插入迭代器：back_inserter、front_inserter和inserter。

std::vector<int> vec1{1, 2, 3};
std::vector<int> vec2{4, 5, 6};// 使用back_inserter将vec2的元素追加到vec1的末尾
std::copy(vec2.begin(), vec2.end(), std::back_inserter(vec1));
// vec1现在为{1, 2, 3, 4, 5, 6}std::deque<int> deq1{1, 2, 3};
std::deque<int> deq2{4, 5, 6};// 使用front_inserter将deq2的元素插入到deq1的前面
std::copy(deq2.begin(), deq2.end(), std::front_inserter(deq1));
// deq1现在为{6, 5, 4, 1, 2, 3}std::list<int> list1{1, 2, 3, 6, 7, 8};
std::list<int> list2{4, 5};// 使用inserter将list2的元素插入到list1的指定位置（在3和6之间）
std::copy(list2.begin(), list2.end(), std::inserter(list1, std::next(list1.begin(), 3)));
// list1现在为{1, 2, 3, 4, 5, 6, 7, 8}

---

迭代器失效问题

迭代器失效是在编写C++代码时常常需要注意的问题，尤其是在操作容器时。以下是迭代器失效的相关概念、原因和避免方法。

a. 什么是迭代器失效

迭代器失效是指一个原本指向容器中某个元素的迭代器，在容器发生某些操作后，不再有效地指向原先的元素或者无法完成预期的操作。这种情况可能导致程序的行为变得不可预测，甚至引发程序崩溃。

b. 迭代器失效的原因

迭代器失效的原因主要与容器的结构和操作有关。以下是一些常见的迭代器失效原因：

• 容器的内存重新分配：当向容器中添加元素时，如vector、deque等，如果超过容器当前的容量，容器可能会重新分配内存空间，导致原有的迭代器失效。
• 元素的删除：从容器中删除元素，如erase()等操作，可能导致指向被删除元素的迭代器失效。此外，在某些容器（如list）中，删除操作可能还会影响指向其他元素的迭代器。
• 元素的插入：向容器中插入元素，如insert()等操作，可能导致指向插入位置之后的元素的迭代器失效。

c. 如何避免迭代器失效

以下是一些避免迭代器失效的策略：

• 尽量使用支持自动更新的容器：在某些容器（如list）中，元素的插入和删除操作不会影响其他元素的迭代器。在可能出现迭代器失效问题的场景中，使用这类容器可以降低风险。
• 避免在遍历过程中修改容器结构：在使用迭代器遍历容器时，避免同时进行插入或删除操作。如果需要修改容器结构，可以先收集需要修改的元素，然后在遍历结束后进行统一的操作。
• 使用返回的迭代器：对于可能导致迭代器失效的操作，如erase()等，通常会返回一个有效的迭代器。在操作后，可以使用返回的迭代器更新失效的迭代器，以保持迭代器的有效性。
• 预留足够的空间：在可能导致内存重新分配的容器（如vector）中，可以预先使用reserve()函数为容器预留足够的空间，以减少内存重新分配的风险。

---

C++11及以后版本中的新特性

C++11及以后版本中的新特性为迭代器带来了许多便利，使得我们在操作容器时能够更加简洁和高效。以下是这些新特性的简介及其在迭代器中的应用。

a. 范围for循环

范围for循环是C++11引入的一种新的循环结构，它允许我们直接遍历容器中的元素，而无需显式创建迭代器。范围for循环的语法如下：

for (declaration : range) {// loop body
}

以下是一个使用范围for循环遍历容器的示例：

#include <vector>
#include <iostream>int main() {std::vector<int> vec{1, 2, 3, 4, 5};for (const auto &val : vec) {std::cout << val << " ";}std::cout << std::endl;return 0;
}

---

b. auto关键字在迭代器中的应用

C++11引入了auto关键字，它可以让编译器根据初始化表达式自动推导出变量的类型。在迭代器中，我们可以利用auto关键字简化迭代器的声明和初始化。以下是一个使用auto关键字的示例：

#include <vector>
#include <iostream>int main() {std::vector<int> vec{1, 2, 3, 4, 5};for (auto it = vec.begin(); it != vec.end(); ++it) {std::cout << *it << " ";}std::cout << std::endl;return 0;
}

c. 基于范围的迭代器适配器

C++14及以后的版本引入了一些基于范围的迭代器适配器，如std::begin()、std::end()、std::cbegin()和std::cend()等，它们可以作用于任何具有.begin()和.end()成员函数的类型，为我们提供了一种统一的访问方式。以下是一个使用基于范围的迭代器适配器的示例：

#include <vector>
#include <iostream>
#include <iterator>int main() {std::vector<int> vec{1, 2, 3, 4, 5};for (auto it = std::begin(vec); it != std::end(vec); ++it) {std::cout << *it << " ";}std::cout << std::endl;return 0;
}

---

通过使用C++11及以后版本中的新特性，我们可以编写更加简洁、易读和高效的代码。在实际编程中，熟练运用这些新特性将有助于提高我们的编程能力和代码质量。

---

实际应用举例

迭代器在实际编程中有很多应用，以下是一些常见的迭代器应用示例。

a. 使用迭代器实现常见算法

i. 查找

#include <vector>
#include <iostream>
#include <algorithm>int main() {std::vector<int> vec{1, 2, 3, 4, 5};int target = 3;auto it = std::find(vec.begin(), vec.end(), target);if (it != vec.end()) {std::cout << "Found " << target << " at position: " << std::distance(vec.begin(), it) << std::endl;} else {std::cout << "Not found" << std::endl;}return 0;
}

ii. 排序

#include <vector>
#include <iostream>
#include <algorithm>int main() {std::vector<int> vec{5, 3, 1, 4, 2};std::sort(vec.begin(), vec.end());for (const auto &val : vec) {std::cout << val << " ";}std::cout << std::endl;return 0;
}

iii. 复制

#include <vector>
#include <iostream>
#include <algorithm>int main() {std::vector<int> src{1, 2, 3, 4, 5};std::vector<int> dest(src.size());std::copy(src.begin(), src.end(), dest.begin());for (const auto &val : dest) {std::cout << val << " ";}std::cout << std::endl;return 0;
}

iv. 删除

#include <vector>
#include <iostream>
#include <algorithm>int main() {std::vector<int> vec{1, 2, 3, 4, 5};int target = 3;auto it = std::remove(vec.begin(), vec.end(), target);vec.erase(it, vec.end());for (const auto &val : vec) {std::cout << val << " ";}std::cout << std::endl;return 0;
}

b. 迭代器在自定义数据结构中的应用

当我们需要为自定义数据结构提供迭代器支持时，可以通过实现相应的迭代器类来完成。以下是一个简单的自定义链表类及其迭代器的示例：

#include <iostream>template <typename T>
class LinkedList {
public:struct Node {T data;Node *next;};class Iterator {public:Iterator(Node *ptr) : current(ptr) {}bool operator!=(const Iterator &other) const { return current != other.current; }T &operator*() { return current->data; }Iterator &operator++() {current = current->next;return *this;}private:Node *current;};LinkedList() : head(nullptr), tail(nullptr) {}~LinkedList() { clear(); }void push_back(const T &value) {Node *newNode = new Node{value, nullptr};if (tail) {tail->next = newNode;tail = newNode;} else {head = tail = newNode;
}Iterator begin() { return Iterator(head); }
Iterator end() { return Iterator(nullptr); }void clear() {Node *current = head;while (current) {Node *next = current->next;delete current;current = next;}head = tail = nullptr;
}
private:
Node *head;
Node *tail;
};int main() {
LinkedList<int> list;
list.push_back(1);
list.push_back(2);
list.push_back(3);
list.push_back(4);
list.push_back(5);       
for (int val : list) {std::cout << val << " ";
}
std::cout << std::endl;list.clear();return 0;
}

在这个示例中，我们实现了一个简单的链表类LinkedList，并为其提供了迭代器支持。LinkedList::Iterator类实现了常用的迭代器操作，如operator!=()、operator*()和operator++()等。通过这些操作，我们可以方便地使用范围for循环遍历自定义链表。

---

实际应用中，迭代器可以帮助我们编写更加通用、高效和易于维护的代码。熟练掌握迭代器的使用方法对于提高编程能力和代码质量具有重要意义。

---

总结

在本文中，我们详细讨论了C++迭代器的相关概念和应用。

a. 回顾本文讨论的主要内容

我们首先介绍了迭代器的定义和初始化，以及与指针的区别。
然后，我们详细讨论了迭代器的分类，包括输入迭代器、输出迭代器、前向迭代器、双向迭代器和随机访问迭代器。
接着，我们探讨了STL中各种容器的迭代器类型，包括顺序容器、关联容器和无序关联容器。
此外，我们还讨论了C++11及以后版本中迭代器的新特性，如范围for循环、auto关键字和基于范围的迭代器适配器。
我们还介绍了迭代器失效的问题，包括失效的原因和如何避免失效。
最后，我们提供了一些迭代器在实际应用中的示例，包括常见算法和自定义数据结构中的应用。

b. C++迭代器在编程中的重要性

C++迭代器在编程中具有重要意义。迭代器为我们提供了一种通用、高效且抽象的方式来访问和操作容器中的元素。通过掌握迭代器的使用，我们可以更好地理解C++容器和算法的工作原理，提高编程能力和代码质量。

c. 鼓励读者深入学习和实践

我们鼓励读者深入学习和实践迭代器的相关知识。在实际编程过程中，可以尝试为自定义数据结构实现迭代器，或者使用迭代器编写一些通用的算法。通过不断的实践，你将更加熟练地运用迭代器，从而编写出更加优雅、高效的代码。