Generic Algorithm

不针对具体容器，在迭代器层次进行操作

Start

头文件algorithm, numeric

只读算法

find, accumulate, equal

find: 容器中查找元素; accumulate: 指定容器范围，给定初值（第三个参数， 确定使用哪个加法运算和返回值类型）; equal: 确定两个序列是否保存相同的值，传入第一个序列的首尾，和第二个序列的首，第二个序列的元素数目不小于第一个序列。

写容器元素算法

必须保证序列原大小至少不小于要求算法写入的元素数目。向目的位置迭代器写入数据的算法假定目的位置足够大，能容纳要写入的元素。

back_inserter: 插入迭代器。接受一个容器的引用，返回一个与该容器绑定的插入迭代器。使用此迭代器赋值时候，会调用push_back将元素添加到容器。

重排容器元素的算法

sort: 通过<实现排序; unique: 将序列重排，将相邻的重复项消除; erase: 删除两个迭代器之间的元素

定制操作

希望按照自己的想法完成操作，如，重载的sort函数接受第三个参数，谓词。

谓词: 一元谓词和二元谓词

lambda: 可以向一个算法传递任何类型的可调用对象。如果e是一个可调用表达式，则可以编写代码e(args)。

可调用对象: 函数，函数指针，重载了函数调用运算符的类，lambda表达式。

1
[capture list] {parameter list} -> return type {funtion body}

capture list: 捕获列表，函数中定义的局部变量列表

parameter list: 参数列表

return type: 返回值类型

function body: 函数体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    // 1. 最简单的 lambda
    []() {
        std::cout << "Hello, Lambda!" << std::endl;
    }(); // 立即调用

    // 2. 带参数和返回值的 lambda
    auto add = [](int a, int b) -> int {
        return a + b;
    };
    std::cout << "3 + 5 = " << add(3, 5) << std::endl;

    // 3. 捕获外部变量，-> return type可省略，编译器会优化
    int x = 10;
    auto multiply = [x](int y) {
        return x * y; // 使用按值捕获的 x
    };
    std::cout << "10 * 7 = " << multiply(7) << std::endl;

    // 4. 按引用捕获并修改外部变量
    auto increment = [&x]() {
        x++; // 修改外部变量 x
    };
    increment();
    std::cout << "x after increment: " << x << std::endl;

    // 5. 在 STL 算法中使用 lambda
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    int sum = 0;
    std::for_each(numbers.begin(), numbers.end(), [&sum](int n) {
        sum += n; // 累加所有元素
    });
    std::cout << "Sum of numbers: " << sum << std::endl;

    return 0;
}

捕获列表中的元素默认是const的，如果想要对捕获列表中的参数值进行调整（参数副本），需要在参数列表后加mutable，在返回值类型之前。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <iostream>

int main() {
    int x = 10;
    
    // 按值捕获 x，但未使用 mutable
    auto lambda1 = [x]() {
        // x++;  // 错误：按值捕获的变量默认是只读的
        std::cout << "lambda1 中的 x: " << x << std::endl;
    };
    
    // 按值捕获 x，并使用 mutable
    auto lambda2 = [x]() mutable {
        x++;  // 允许修改（但只影响 lambda 内部的副本）
        std::cout << "lambda2 中的 x: " << x << std::endl;
    };
    
    lambda1();  // 输出：lambda1 中的 x: 10
    lambda2();  // 输出：lambda2 中的 x: 11
    std::cout << "外部的 x: " << x << std::endl;  // 输出：外部的 x: 10（原始值未变）
    
    return 0;
}

bind: 将某个参数绑定到某个函数（提供默认参数），或者调整参数顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <functional> // 包含 std::bind

// 普通函数
int add(int a, int b) {
    return a + b;
}

// 成员函数
class Calculator {
public:
    int multiply(int a, int b) {
        return a * b;
    }
};

int main() {
    // 1. 绑定普通函数，固定部分参数
    auto add5 = std::bind(add, 5, std::placeholders::_1); // 固定第一个参数为5
    std::cout << "5 + 3 = " << add5(3) << std::endl; // 等价于 add(5, 3)
    std::cout << "5 + 7 = " << add5(7) << std::endl; // 等价于 add(5, 7)

    // 2. 调整参数顺序
    auto swap_add = std::bind(add, std::placeholders::_2, std::placeholders::_1);
    std::cout << "3 + 5 = " << swap_add(5, 3) << std::endl; // 等价于 add(3, 5)

    // 3. 绑定成员函数（需要传入对象指针或引用）
    Calculator calc;
    auto multiply_by_2 = std::bind(&Calculator::multiply, &calc, 2, std::placeholders::_1);
    std::cout << "2 * 4 = " << multiply_by_2(4) << std::endl; // 等价于 calc.multiply(2, 4)

    // 4. 绑定 lambda 表达式
    auto lambda = [](int a, int b, int c) { return a * b + c; };
    auto bound_lambda = std::bind(lambda, std::placeholders::_1, 10, 5);
    std::cout << "3 * 10 + 5 = " << bound_lambda(3) << std::endl; // 等价于 lambda(3, 10, 5)

    return 0;
}

迭代器again

插入迭代器，流迭代器，反向迭代器，移动迭代器

插入迭代器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <iterator>  // 包含插入迭代器

int main() {
    std::vector<int> source = {1, 2, 3, 4, 5};

    // 1. 使用 back_inserter：在末尾插入
    std::vector<int> dest1;
    std::copy(source.begin(), source.end(), std::back_inserter(dest1));
    // dest1 现在是 {1, 2, 3, 4, 5}

    // 2. 使用 front_inserter：在头部插入（结果会逆序）
    std::list<int> dest2;
    std::copy(source.begin(), source.end(), std::front_inserter(dest2));
    // dest2 现在是 {5, 4, 3, 2, 1}

    // 3. 使用 inserter：在指定位置插入
    std::vector<int> dest3 = {10, 20, 30};
    // 在 dest3 的第一个元素（10）前插入 source 的所有元素
    std::copy(source.begin(), source.end(), std::inserter(dest3, dest3.begin()));
    // dest3 现在是 {1, 2, 3, 4, 5, 10, 20, 30}

    // 打印结果
    std::cout << "dest1: ";
    for (int num : dest1) std::cout << num << " ";

    std::cout << "\ndest2: ";
    for (int num : dest2) std::cout << num << " ";

    std::cout << "\ndest3: ";
    for (int num : dest3) std::cout << num << " ";

    return 0;
}

iostream迭代器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>  // 包含 iostream 迭代器

int main() {
    // 1. 使用 istream_iterator 从标准输入读取数据
    std::cout << "请输入一些整数（按 Ctrl+Z 结束输入）：" << std::endl;
    std::istream_iterator<int> in_iter(std::cin);  // 绑定到 std::cin
    std::istream_iterator<int> end_iter;           // 默认构造，作为结束标志

    // 将输入的整数复制到 vector 中
    std::vector<int> nums;
    std::copy(in_iter, end_iter, std::back_inserter(nums));

    // 2. 使用 ostream_iterator 向标准输出写入数据
    std::cout << "你输入的整数是：";
    std::ostream_iterator<int> out_iter(std::cout, " ");  // 绑定到 std::cout，每个元素后加空格
    std::copy(nums.begin(), nums.end(), out_iter);
    std::cout << std::endl;

    // 3. 排序后输出
    std::sort(nums.begin(), nums.end());
    std::cout << "排序后的整数是：";
    std::copy(nums.begin(), nums.end(), out_iter);
    std::cout << std::endl;

    return 0;
}

反向迭代器

从尾到首迭代。单向链表不支持。使用base可以相互转化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> nums = {1, 2, 3, 4, 5};

    // 1. 正向遍历（普通迭代器）
    std::cout << "正向遍历: ";
    for (auto it = nums.begin(); it != nums.end(); ++it) {
        std::cout << *it << " ";  // 输出：1 2 3 4 5
    }
    std::cout << std::endl;

    // 2. 反向遍历（反向迭代器）
    std::cout << "反向遍历: ";
    for (auto it = nums.rbegin(); it != nums.rend(); ++it) {
        std::cout << *it << " ";  // 输出：5 4 3 2 1
    }
    std::cout << std::endl;

    // 3. 反向迭代器与算法配合（例如反向排序）
    std::sort(nums.rbegin(), nums.rend());  // 从大到小排序
    std::cout << "反向排序后: ";
    for (int num : nums) {
        std::cout << num << " ";  // 输出：5 4 3 2 1
    }
    std::cout << std::endl;

    return 0;
}

泛型算法结构

输入迭代器、输出迭代器、前向迭代器、双向迭代器、随机访问迭代器

  1. 输入迭代器: 只读

    • 比较两个迭代器的相等和不相等运算符
    • 递增运算 ++
    • 解引用 *
    • 解引用迭代器 ->

  2. 输出迭代器: 只写

    • 递增运算 ++
    • 解引用 *

  3. 前向迭代器: 单向移动，可读写

  4. 双向迭代器: 单向 + 递减运算

  5. 随机访问迭代器: 双向迭代器 +

    • 用于比较两个迭代器相对位置的关系运算符( <, <=, >, >= )
    • 迭代器和整数的值运算
    • 迭代器之间减法
    • 下标运算符

特定容器算法

list & forward_list：特殊的成员函数算法

  • lst.merge(lst2): 将lst2的元素合并入lst。必须都是有序的。
  • lst.merge(lst2, comp): 元素将从lst2中删除。在合并后，lst2变为空，第一个版本使用<运算符；第二个版本使用给定的比较操作。
  • lst.remove(val) & lst.remove_if(pred): 调用erase删除掉与给定值相等或令一元谓词为真的每个元素。
  • lst.reverse(): 反转lst中元素的顺序。
  • lst.sort(): 使用<或给定比较操作排序元素。
  • lst.sort(comp):
  • lst.unique() & lst.unique(pred): 调用erase删除同一个值的连续拷贝。第一个版本使用==，第二个版本使用给定的二元谓词。

链表的splice算法成员：链表数据结构特有的，不需要通用版本。

  • lst.splice(args) or flst.splice_after(arge)
    • (p, lst2): p是一个指向lst中元素的迭代器，将lst2中元素转移到lst中p位置之后，或者将lst元素转移到flst中p位置之前
    • (p, lst2, p2): p2是一个指向lst2中位置的有效的迭代器。将p2指向的元素移动到lst中，或将p2之后的元素移动到flst中
    • (p, lst, b, e): b, e是lst2中的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <list>
#include <forward_list>

// 打印list内容
void print_list(const std::list<int>& lst, const std::string& name) {
    std::cout << name << ": ";
    for (int num : lst) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

// 打印forward_list内容
void print_forward_list(const std::forward_list<int>& flst, const std::string& name) {
    std::cout << name << ": ";
    for (int num : flst) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

int main() {
    // 1. std::list的splice示例（双向链表）
    std::cout << "=== std::list 的 splice 示例 ===" << std::endl;
    std::list<int> list1 = {1, 2, 3};
    std::list<int> list2 = {4, 5, 6};

    print_list(list1, "初始 list1");
    print_list(list2, "初始 list2");

    // 在list1的2后面插入list2的所有元素
    auto it_list = list1.begin();
    std::advance(it_list, 1);  // 指向元素2
    list1.splice(it_list, list2);  // 转移list2的所有元素到it_list位置

    print_list(list1, "splice后 list1");  // 1 2 4 5 6 3
    print_list(list2, "splice后 list2");  // 空（所有元素已转移）

    // 2. std::forward_list的splice_after示例（单向链表）
    std::cout << "\n=== std::forward_list 的 splice_after 示例 ===" << std::endl;
    std::forward_list<int> flist1 = {1, 2, 3};
    std::forward_list<int> flist2 = {4, 5, 6};

    print_forward_list(flist1, "初始 flist1");
    print_forward_list(flist2, "初始 flist2");

    // 在flist1的2后面插入flist2的所有元素
    auto it_flist = flist1.begin();
    std::advance(it_flist, 1);  // 指向元素2
    flist1.splice_after(it_flist, flist2);  // 转移flist2的所有元素到it_flist之后

    print_forward_list(flist1, "splice_after后 flist1");  // 1 2 4 5 6 3
    print_forward_list(flist2, "splice_after后 flist2");  // 空（所有元素已转移）

    return 0;
}