容器、迭代器与区间

读完能做什么

• 能说出容器、迭代器、区间 [first, last) 分别是什么，各自解决什么问题。
• 能画出 [10,20,30] 的格子图，并指出 begin() 和 end() 分别站在哪个位置。
• 能用迭代器遍历整个容器，也能只遍历其中一段。
• 能判断一种迭代器支不支持 it + n 和相减，并说出迭代器什么时候会失效。

为什么需要它

数组用下标定位元素：a[2] 是第 3 个。但容器不止数组一种：list 链表 串成一条链、set 有序集合 排成一棵树，它们没有连续下标，a[2] 这种写法根本用不了、也没有 it + 2 可以跳着走。（map 键值映射 虽然也能写 m[2]，但那表示“键 2 对应的值”，不是“第 3 个位置”。）

可算法（排序、查找）又想对“任意容器”都管用。于是就冒出一个问题：怎么用一种统一的说法，描述“数据里的某个位置”？ 答案就是迭代器。有了它，算法只要会说“从哪个位置到哪个位置”，就能处理数组、链表、集合……不必为每种容器重写。

它是什么

先记住三句话：

• 容器是数据的组织方式——它决定这组数据怎么摆放。
• 迭代器是一个位置，像游标一样指向容器里的某个地方。
• 区间由两个位置组成，写成左闭右开的 [first, last)：包含 first 指向的元素，不包含 last 指向的元素。

对 [10,20,30] 来说，各个位置是这样分布的：

       ↓                ↓
       begin()          end()
    +-----+-----+-----+ ·
    |  10 |  20 |  30 |
    +-----+-----+-----+ ·
    └── [begin(), end())：10 20 30

begin() 指向首元素，end() 是尾后位置。 end() 不是“最后一个元素”，而是“最后一个元素再往后一格”，那里没有数据。所以 [begin(), end()) 正好圈住整个容器；[begin() + 1, end()) 就从第二个元素圈到末尾。这种“起点走得到、终点取不到”的写法叫左闭右开，本课所有算法的区间都是这个约定。

迭代器属于它所在的容器。 v.begin() 是 v 的迭代器，只能用来在 v 里移动；容器的内容一变（扩容、插入、删除），旧的迭代器可能失效，不能再拿来用。

最小可运行示例

用迭代器从头走一遍 [10,20,30]：

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {10, 20, 30};

    vector<int>::iterator it;                 // 先写清楚类型
    for (it = v.begin(); it != v.end(); it++) {
        cout << *it << ' ';
    }
    cout << '\n';
    return 0;
}

输出：

10 20 30 

逐行看：

• vector<int>::iterator it; 声明一个 vector<int> 的迭代器变量。这里故意把类型完整写出来，让你看清它是“vector<int> 的迭代器”，而不是别的容器的迭代器。
• it = v.begin() 让游标站到第一个元素的位置。
• it != v.end() 是循环条件：只要还没走到尾后位置，就继续。
• *it 是解引用，取出当前游标指向的元素；it++ 把游标往后移一格（指向下一个元素）。
• 循环依次打印 10、20、30。走到 end() 时条件不成立，循环结束。

一步步看变化

上例的每一步，游标的位置和输出都对应得上：

只要把起点往后挪一格，就能只处理后半段：

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {10, 20, 30};

    // 左闭右开区间 [v.begin() + 1, v.end())：从下标 1 到末尾
    for (vector<int>::iterator it = v.begin() + 1; it != v.end(); it++) {
        cout << *it << ' ';
    }
    cout << '\n';
    return 0;
}

输出：

20 30 

             ↓          ↓
             begin()+1  end()
    +-----+-----+-----+ ·
    |  10 |  20 |  30 |
    +-----+-----+-----+ ·
    └── [begin()+1, end())：20 30

起点是 begin() + 1（下标 1 的 20），终点仍是 end()，所以打印 20 30，把第一个元素 10 排除在外。

空容器的两个端点是同一个位置：

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v;                            // 空容器

    cout << "begin() == end()：" << (v.begin() == v.end()) << '\n';
    cout << "size = " << v.size() << '\n';
    return 0;
}

输出：

begin() == end()：1
size = 0

空容器里没有任何元素，begin() 和 end() 都落在“第一个位置”，于是相等。打印 1 表示“相等为真”（布尔值默认输出成 0/1）。这也是判断“区间是不是空的”的通用办法：first == last 就是空区间。

逐项扩展核心操作

显式类型与 auto

上面每次都写 vector<int>::iterator，类型很长。C++ 提供 auto，意思是“让编译器根据右边的值推断类型”：

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {10, 20, 30};

    for (auto it = v.begin(); it != v.end(); it++) {   // auto：让编译器推断迭代器类型
        cout << *it << ' ';
    }
    cout << '\n';
    return 0;
}

输出：

10 20 30 

auto it = v.begin(); 里，编译器看到右边是 v.begin()，自动把 it 推断成 vector<int>::iterator。所以 auto 不改变程序做的事，只是省去手写长类型——初学者建议先写显式类型，弄清楚它是谁的迭代器，再换成 auto。

迭代器的能力分层

不是所有迭代器都支持同样的操作。能不能 it + n、能不能两个迭代器相减，取决于容器类型：

vector、deque、string 的迭代器是随机访问迭代器，像指针一样能加减；list、set、map 的迭代器是双向迭代器，只能一步一步 ++ / --。

这些容器各自长什么样，后面按顺序都会讲：vector 动态数组、deque 双端队列、list 链表、set 有序集合、map 键值映射。本页只需要记住它们在“能不能跳着走”这一点的差别。

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {10, 20, 30};
    list<int> l = {10, 20, 30};

    cout << "vector 可以 it + n：" << *(v.begin() + 2) << '\n';
    cout << "vector 可以相减：(end - begin) = " << (v.end() - v.begin()) << '\n';

    cout << "list 只能一个一个走：";
    for (list<int>::iterator it = l.begin(); it != l.end(); ++it) {
        cout << *it << ' ';
    }
    cout << '\n';
    return 0;
}

输出：

vector 可以 it + n：30
vector 可以相减：(end - begin) = 3
list 只能一个一个走：10 20 30 

对 list 用 it + 1 或 < 会怎样？

// 错误示例：list 的迭代器是双向迭代器，不支持 it + n 和 it < it2，下面这段不能通过编译
#include <bits/stdc++.h>
using namespace std;

int main() {
    list<int> l = {10, 20, 30};

    for (list<int>::iterator it = l.begin(); it < l.end(); it = it + 1) {  // 既用了 < 又用了 +
        cout << *it << ' ';
    }
    return 0;
}

这段编译不过：list 的迭代器没有定义 + 和 <。要遍历 list，老老实实用 ++it 和 it != l.end()；要“第几个元素”，得从头数着走。

end() 不能解引用

end() 指向尾后位置，那里没有元素：

// 错误示例：end() 是尾后位置，解引用它属于越界，结果不确定，不能运行出固定结果
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {10, 20, 30};

    cout << *v.end() << '\n';   // 尾后位置没有元素，结果不确定
    return 0;
}

不要为它编造输出：*end() 是越界解引用，程序可能打印垃圾值，也可能崩溃。使用前先确认 it != v.end()，确认它指向真实元素再解引用。

容器一变，迭代器可能失效

迭代器依附于容器。一旦容器调整了内部存储（比如 vector 扩容，或插入、删除元素），之前记下的迭代器可能就失效了：

// 错误示例：erase 之后旧迭代器可能失效，继续解引用结果不确定
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {10, 20, 30};

    vector<int>::iterator it = v.begin() + 1;   // 指向 20
    v.erase(v.begin());                          // 删除 10，it 指向的位置不再可靠
    cout << *it << '\n';                         // 结果不确定
    return 0;
}

删除后位置关系变了，it 可能指向别处甚至无效。要接着用，就重新取一次 v.begin()；不要拿旧游标继续走。

什么时候选它、哪里容易错

end() 是尾后位置，不是最后一个元素。 想取最后一个元素用 *(v.end() - 1)（仅限随机访问迭代器）或 v.back()；*v.end() 是越界。

区间是左闭右开。 [first, last) 不包含 last。所以“处理前 n 个元素”写 [begin(), begin() + n)，“处理整个容器”写 [begin(), end())。

不是所有迭代器都能加减。 只有 vector、deque、string 支持 it + n、相减和 <；list、set、map 只能 ++ / --。写遍历代码时，用 it != end() 比用 it < end() 更通用。

迭代器会失效。 插入、删除、扩容之后，旧迭代器可能不再可靠，要重新获取。这是一条安全习惯，不必先理解底层内存怎么搬。

选读。 标准把迭代器分成五类（输入、输出、前向、双向、随机访问），能力由弱到强，上位类别可以当下面类别用。日常只要记住“随机访问能加减、双向只能一步步走”就够用，不必背全分类。

操作速查表

动手检查

第 1 题：预测输出

下面是一段片段（省略了头文件和 main），[10,20,30] 只遍历到 end() - 1。先手推输出，再展开折叠核对：

vector<int> v = {10, 20, 30};

for (vector<int>::iterator it = v.begin(); it != v.end() - 1; it++) {
    cout << *it << ' ';
}

第 2 题：修改代码

把最小可运行示例改成只遍历前两个元素（输出 10 20 ），验证条件：先说出循环在哪个位置停下，再运行核对。

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {10, 20, 30};

    // 区间 [v.begin(), v.end() - 1)：最后一个元素之前
    for (vector<int>::iterator it = v.begin(); it != v.end() - 1; it++) {
        cout << *it << ' ';
    }
    cout << '\n';
    return 0;
}

10 20 

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {10, 20, 30};

    // 只遍历前两个元素：从 begin() 到 begin() + 2
    for (vector<int>::iterator it = v.begin(); it != v.begin() + 2; it++) {
        cout << *it << ' ';
    }
    cout << '\n';
    return 0;
}

10 20 

立即练习

本页是容器与迭代器的基础概念课，页面里的两道动手检查已经覆盖了“区间少一个端点”“只遍历一部分”这类核心操作，所以不安排 OJ 题目。等你学过具体容器后，再去各页的「立即练习」做题更合适。