C++STL教程：迭代器与算法库

发布时间：2026-08-29 00:34:50

🕒 阅读时间：21 分钟📝 字数：3896👀 阅读量：Loading...

本文是 C++ 系列教程的第 13 篇。上一篇讲解了关联容器与无序容器，本篇讲解迭代器与算法库：迭代器五类与分类、常用算法（sort/find/find_if/count/copy/transform/accumulate/reverse/unique）、删除-擦除惯用法。

一、迭代器基础

1.1 什么是迭代器

迭代器是统一访问容器元素的接口，让算法不关心容器类型。可以把迭代器理解为「智能指针」，支持 *、->、++、-- 等操作。

1.2 迭代器分类

类别	支持操作	可用容器
输入迭代器	只读、++	istream
输出迭代器	只写、++	ostream
前向迭代器	读写、++	forward_list
双向迭代器	读写、++/–	list, set, map
随机访问迭代器	读写、±/[]	vector, deque, array

1.3 常用迭代器操作

1
#include <iostream>
2
#include <vector>
3
using namespace std;
4

5
int main() {
6
    vector<int> v = {10, 20, 30, 40, 50};
7

8
    // begin/end
9
    cout << "正向遍历: ";
10
    for (auto it = v.begin(); it != v.end(); it++) {
11
        cout << *it << " ";
12
    }
13
    cout << endl;
14

15
    // rbegin/rend（反向）
16
    cout << "反向遍历: ";
17
    for (auto it = v.rbegin(); it != v.rend(); it++) {
18
        cout << *it << " ";
19
    }
20
    cout << endl;
21

22
    // cbegin/cend（const 迭代器）
23
    auto cit = v.cbegin();
24
    cout << "首个元素: " << *cit << endl;
25
    // *cit = 99;   // 错误！const 迭代器不可修改
26

27
    // 随机访问
28
    auto it = v.begin();
29
    cout << "*(it+2) = " << *(it + 2) << endl;  // 30
30
    cout << "it[3] = " << it[3] << endl;        // 40
31
    it += 4;
32
    cout << "it[0] = " << it[0] << endl;        // 50
33
    return 0;
34
}

1.4 迭代器失效规则

操作	vector/deque	list/set/map
插入	可能全部失效（扩容）	其他迭代器不受彲响
删除	被删元素之后的失效	只影响被删元素
注意	删除后迭代器悬垂	相对安全

二、查找与统计算法

2.1 find 与 find_if

1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
using namespace std;
5

6
int main() {
7
    vector<int> v = {5, 2, 8, 1, 9, 3};
8

9
    // find：查找指定值，返回迭代器
10
    auto it = find(v.begin(), v.end(), 8);
11
    if (it != v.end()) {
12
        cout << "找到 8，位置: " << (it - v.begin()) << end
13
l;
14
    } else {
15
        cout << "未找到" << endl;
16
    }
17

18
    // find_if：按条件查找
19
    auto it2 = find_if(v.begin(), v.end(),
20
        [](int x) { return x > 5; });   // 第一个 >5 的元素
21
    if (it2 != v.end()) {
22
        cout << "第一个 >5 的元素: " << *it2 << endl;  // 8
23
    }
24
    return 0;
25
}

2.2 count 与 count_if

1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
using namespace std;
5

6
int main() {
7
    vector<int> v = {1, 2, 3, 1, 4, 1, 5};
8

9
    // count：统计指定值出现次数
10
    cout << "1 出现: " << count(v.begin(), v.end(), 1) << " 次" << endl;  // 3
11

12
    // count_if：按条件统计
13
    cout << "偶数个数: " << count_if(v.begin(), v.end(),
14
        [](int x) { return x % 2 == 0; }) << endl;   // 2
15

16
    // 判断是否全部满足
17
    bool allPositive = all_of(v.begin(), v.end(),
18
        [](int x) { return x > 0; });
19
    cout << "全部为正数: " << allPositive << endl;   // 1
20

21
    // 判断是否存在满足条件
22
    bool anyBig = any_of(v.begin(), v.end(),
23
        [](int x) { return x > 4; });
24
    cout << "存在大于 4: " << anyBig << endl;         // 1
25
    return 0;
26
}

三、排序与排列算法

3.1 sort 与自定义排序

1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
using namespace std;
5

6
struct Student {
7
    string name;
8
    int score;
9
};
10

11
int main() {
12
    vector<int> v = {3, 1, 4, 1, 5, 9};
13

14
    // 默认升序
15
    sort(v.begin(), v.end());
16
    for (int x : v) cout << x << " ";
17
    cout << endl;   // 1 1 3 4 5 9
18

19
    // 降序
20
    sort(v.begin(), v.end(), greater<int>());
21
    for (int x : v) cout << x << " ";
22
    cout << endl;   // 9 5 4 3 1 1
23

24
    // 结构体自定义排序
25
    vector<Student> students = {
26
        {"张三", 88}, {"李四", 92}, {"王五", 76}
27
    };
28
    // 按分数降序
29
    sort(students.begin(), students.end(),
30
        [](const Student &a, const Student &b) {
31
            return a.score > b.score;
32
        });
33
    for (const auto &s : students) {
34
        cout << s.name << " " << s.score << endl;
35
    }
36
    return 0;
37
}

3.2 stable_sort 与 partial_sort

1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
using namespace std;
5

6
int main() {
7
    // stable_sort：相等元素保持原顺序
8
    vector<pair<int, int>> v = {{1, 5}, {2, 3}, {1, 7}, {2, 1}};
9
    stable_sort(v.begin(), v.end(),
10
        [](const auto &a
11
, const auto &b) { return a.first < b.first; });
12
    // 相同 first 的元素保持相对顺序：(1,5) 在 (1,7) 前
13
    for (const auto &p : v) {
14
        cout << "(" << p.first << "," << p.second << ") ";
15
    }
16
    cout << endl;
17

18
    // partial_sort：只保证前 n 个是最小的
19
    vector<int> nums = {5, 2, 8, 1, 9, 3, 7};
20
    partial_sort(nums.begin(), nums.begin() + 3, nums.end());
21
    cout << "前 3 个最小: ";
22
    for (int i = 0; i < 3; i++) cout << nums[i] << " ";
23
    cout << endl;   // 1 2 3
24
    return 0;
25
}

3.3 nth_element 与 reverse

1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
using namespace std;
5

6
int main() {
7
    // nth_element：第 n 个位置是正确排序值，左侧都小右侧都大
8
    vector<int> v = {7, 2, 9, 1, 5, 3, 8};
9
    nth_element(v.begin(), v.begin() + 3, v.end());
10
    cout << "第 4 小的元素: " << v[3] << endl;  // 5
11

12
    // reverse：反转
13
    vector<int> r = {1, 2, 3, 4, 5};
14
    reverse(r.begin(), r.end());
15
    for (int x : r) cout << x << " ";
16
    cout << endl;   // 5 4 3 2 1
17

18
    // rotate：旋转
19
    vector<int> rot = {1, 2, 3, 4, 5};
20
    rotate(rot.begin(), rot.begin() + 2, rot.end());
21
    for (int x : rot) cout << x << " ";
22
    cout << endl;   // 3 4 5 1 2
23
    return 0;
24
}

四、复制与变换算法

4.1 copy 与 copy_if

1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
using namespace std;
5

6
int main() {
7
    vector<int> src = {1, 2, 3, 4, 5};
8

9
    // copy：整段复制
10
    vector<int> dest(src.size());
11
    copy(src.begin(), src.end(), dest.begin());
12
    for (int x : dest) cout << x << " ";
13
    cout << endl;   // 1 2 3 4 5
14

15
    // copy_if：按条件复制
16
    vector<int> evens;
17
    copy_if(src.begin(), src.end(), back_inserter(evens),
18
        [](int x) { return x % 2 == 0; });
19
    for (int x : evens) cout << x << " ";
20
    cout << endl;   // 2 4
21

22
    // back_inserter：自动扩容追加
23
    vector<int> more;
24
    copy(src.begin(), src.end(), back_inserter(more));
25
    cout << "more size = " << more.size() << endl;  // 5
26
    return 0;
27
}

4.2 transform 变换

1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
using namespace std;
5

6
int main() {
7
    vector<int> nums = {1, 2, 3, 4};
8

9
    // transform：一元变换（每个元素平方）
10
    vector<int> squares(nums.size());
11
    transform(nums.begin(), nums.end(), squares.begin(),
12

13
        [](int x) { return x * x; });
14
    for (int x : squares) cout << x << " ";
15
    cout << endl;   // 1 4 9 16
16

17
    // transform：二元变换（两序列对应相加）
18
    vector<int> a = {1, 2, 3};
19
    vector<int> b = {10, 20, 30};
20
    vector<int> sum(3);
21
    transform(a.begin(), a.end(), b.begin(), sum.begin(),
22
        [](int x, int y) { return x + y; });
23
    for (int x : sum) cout << x << " ";
24
    cout << endl;   // 11 22 33
25

26
    // 原地变换
27
    transform(nums.begin(), nums.end(), nums.begin(),
28
        [](int x) { return x * 10; });
29
    for (int x : nums) cout << x << " ";
30
    cout << endl;   // 10 20 30 40
31
    return 0;
32
}

五、数值与去重算法

5.1 accumulate 与 iota

1
#include <iostream>
2
#include <vector>
3
#include <numeric>
4
#include <algorithm>
5
using namespace std;
6

7
int main() {
8
    vector<int> v = {1, 2, 3, 4, 5};
9

10
    // accumulate：求和（初始值 0）
11
    int sum = accumulate(v.begin(), v.end(), 0);
12
    cout << "总和: " << sum << endl;   // 15
13

14
    // accumulate：自定义累加（求积）
15
    int product = accumulate(v.begin(), v.end(), 1,
16
        [](int a, int b) { return a * b; });
17
    cout << "乘积: " << product << endl;   // 120
18

19
    // iota：填充递增序列
20
    vector<int> seq(5);
21
    iota(seq.begin(), seq.end(), 10);   // 10 11 12 13 14
22
    for (int x : seq) cout << x << " ";
23
    cout << endl;
24

25
    // inner_product：内积
26
    vector<int> a = {1, 2, 3};
27
    vector<int> b = {4, 5, 6};
28
    int dot = inner_product(a.begin(), a.end(), b.begin(), 0);
29
    cout << "内积: " << dot << endl;    // 32
30
    return 0;
31
}

5.2 unique 与 erase

1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
using namespace std;
5

6
int main() {
7
    // unique 只去重相邻重复，通常先排序
8
    vector<int> v = {1, 1, 2, 2, 3, 1, 2};
9

10
    sort(v.begin(), v.end());
11
    auto last = unique(v.begin(), v.end());
12
    // 此时 v 是 1 2 3 2 3（尾部是"垃圾"）
13

14
    // 删除-擦除惯用法：unique 返回新结尾，erase 删除尾部
15
    v.erase(last, v.end());
16
    for (int x : v) cout << x << " ";
17
    cout << endl;   // 1 2 3
18

19
    // 删除所有偶数（remove_if + erase 惯用法）
20
    vector<int> nums = {1, 2, 3, 4, 5, 6};
21
    nums.erase(
22
        remove_if(nums.begin(), nums.end(),
23
            [](int x) { return x % 2 == 0; }),
24
        nums.end());
25
    for (int x : nums) cout << x << " "
26
;
27
    cout << endl;   // 1 3 5
28
    return 0;
29
}

5.3 删除-擦除惯用法详解

1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
using namespace std;
5

6
int main() {
7
    vector<int> v = {1, 2, 3, 2, 4, 2, 5};
8

9
    // remove 不真正删除，只是把保留元素移到前面，返回新逻辑结尾
10
    auto newEnd = remove(v.begin(), v.end(), 2);
11
    cout << "remove 后 size 未变: " << v.size() << endl;  // 7
12

13
    // erase 真正删除尾部
14
    v.erase(newEnd, v.end());
15
    cout << "erase 后 size: " << v.size() << endl;        // 4
16
    for (int x : v) cout << x << " ";
17
    cout << endl;   // 1 3 4 5
18

19
    // 一行惯用法
20
    vector<int> w = {1, 2, 3, 4, 5, 6};
21
    w.erase(remove_if(w.begin(), w.end(),
22
        [](int x) { return x % 2 == 0; }), w.end());
23
    for (int x : w) cout << x << " ";
24
    cout << endl;   // 1 3 5
25
    return 0;
26
}

六、最小最大值与二分查找

6.1 min/max 系列

1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
using namespace std;
5

6
int main() {
7
    vector<int> v = {5, 2, 8, 1, 9};
8

9
    cout << "max: " << *max_element(v.begin(), v.end()) << endl;  // 9
10
    cout << "min: " << *min_element(v.begin(), v.end()) << endl;  // 1
11

12
    // minmax：同时获取
13
    auto result = minmax_element(v.begin(), v.end());
14
    cout << "min=" << *result.first << ", max=" << *result.second << endl;
15

16
    // 两个值比较
17
    cout << "max(3,7) = " << max(3, 7) << endl;     // 7
18
    cout << "min(3,7) = " << min(3, 7) << endl;     // 3
19

20
    // clamp：限制范围
21
    cout << "clamp(15, 0, 10) = " << clamp(15, 0, 10) << endl;  // 10
22
    cout << "clamp(-5, 0, 10) = " << clamp(-5, 0, 10) << endl;  // 0
23
    return 0;
24
}

6.2 binary_search 与 lower_bound

1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
using namespace std;
5

6
int main() {
7
    vector<int> v = {1, 3, 5, 7, 9, 11};
8

9
    // binary_search：二分查找（要求已排序）
10
    cout << "查找 5: " << binary_search(v.begin(), v.end(), 5) << endl;   // 1
11
    cout << "查找 6: " << binary_search(v.begin(), v.end(), 6) << endl;   // 0
12

13
    // lower_bound：第一个 >= 值的位置
14
    auto lb = lower_bound(v.begin(), v.end(), 6);
15
    cout << "lower_bound(6) = " << *lb << endl;   // 7
16

17
    // upper_bound：第一个 > 值的位置
18
    auto ub = upper_bound(v.begin(), v.end(), 7);
19
    cout << "upper_bound(7) = " <<
20
 *ub << endl;   // 9
21

22
    // equal_range：等于值的一整段
23
    vector<int> dup = {1, 2, 2, 2, 3, 4};
24
    auto range = equal_range(dup.begin(), dup.end(), 2);
25
    cout << "2 的出现次数: " << (range.second - range.first) << endl;  // 3
26
    return 0;
27
}

七、实战：文本分析工具

综合本篇全部算法，实现文本统计工具：

1
#include <iostream>
2
#include <vector>
3
#include <string>
4
#include <algorithm>
5
#include <numeric>
6
#include <map>
7
using namespace std;
8

9
class TextAnalyzer {
10
private:
11
    vector<string> words;
12

13
public:
14
    void addWords(const vector<string> &newWords) {
15
        words.insert(words.end(), newWords.begin(), newWords.end());
16
    }
17

18
    size_t totalCount() const {
19
        return words.size();
20
    }
21

22
    // 去重后单词种类
23
    size_t uniqueCount() const {
24
        vector<string> temp = words;
25
        sort(temp.begin(), temp.end());
26
        temp.erase(unique(temp.begin(), temp.end()), temp.end());
27
        return temp.size();
28
    }
29

30
    // 平均单词长度
31
    double averageLength() const {
32
        if (words.empty()) return 0;
33
        int total = accumulate(words.begin(), words.end(), 0,
34
            [](int sum, const string &w) { return sum + w.length(); });
35
        return static_cast<double>(total) / words.size();
36
    }
37

38
    // 最长单词
39
    string longestWord() const {
40
        return *max_element(words.begin(), words.end(),
41
            [](const string &a, const string &b) {
42
                return a.length() < b.length();
43
            });
44
    }
45

46
    // 词频统计（Top N）
47
    void showTopFrequent(int n = 3) const {
48
        map<string, int> freq;
49
        for (const auto &w : words) freq[w]++;
50

51
        vector<pair<string, int>> items(freq.begin(), freq.end());
52
        sort(items.begin(), items.end(),
53
            [](const auto &a, const auto &b) { return a.second > b.second; });
54

55
        cout << "===== Top " << n << " 高频词 =====" << endl;
56
        for (int i = 0; i < min(n, (int)items.size()); i++) {
57
            cout << items[i].first << ": " << items[i].second << " 次" << endl;
58
        }
59
    }
60
};
61

62
int main() {
63
    TextAnalyzer analyzer;
64
    analyzer.addWords({"cpp", "python", "java", "cpp", "go",
65
                       "python", "cpp", "rust", "java"});
66

67
    cout << "总词数: " << analyzer.totalCount() << endl;        // 9
68
    cout << "去重词数: " << analyzer.uniqueCount() << endl;     // 5
69
    cout << "平均长度: " << analyzer.averageLength() << endl;
70
    cout << "最长单词: " << analyzer.longestWord() << endl;
71
    analyzer.showTopFrequent(3);
72
    return 0;
73
}

总结

本篇讲解了迭代器的五类与失效规则、查找统计算法（find/count）、排序排列算法（sort/stable_sort/nth_element）、复制变换算法（copy/transform）、数值去重算法（accumulate/unique）、最小最大值与二分查找，并用文本分析工具串联实战。重点掌握：删除-擦除惯用法、transform 的一元/二元变换、back_inserter、二分查找的前提（有序）。

下一篇将讲解函数对象与 Lambda 表达式，敬请期待！