c++泛型算法

C++ 泛型算法概述

在 C++ 中，标准模板库（STL）提供了一套强大的泛型算法，这些算法设计用来处理 STL 容器中的数据。泛型算法的“泛型”一词指的是这些算法能够独立于它们所操作对象的具体类型。这些算法大多定义在 <algorithm> 和 <numeric> 头文件中。

泛型算法的特点

• 与容器类型无关：泛型算法可以作用于任何提供迭代器接口的容器，如 std::vector、std::list、std::set 等。
• 操作通过迭代器进行：算法通常通过迭代器来访问和处理容器中的元素，这使得算法与容器的具体类型解耦。
• 高度可重用和可定制：通过模板参数和函数对象（比如谓词和比较函数），算法可以被定制以适应不同的处理需求。

常用的泛型算法

1. 排序和搜索：

   • sort(begin, end)：对元素进行排序。
   • binary_search(begin, end, value)：在已排序的序列中进行二分查找。

2. 修改序列操作：

   • copy(begin, end, dest)：复制元素到另一个位置。
   • fill(begin, end, value)：用特定值填充序列。
   • replace(begin, end, old_val, new_val)：替换序列中的特定值。
   • unique(begin, end)：移除相邻的重复元素。

3. 分区操作：

   • partition(begin, end, predicate)：根据谓词对序列进行分区。

4. 数值操作（在 <numeric> 中定义）：

   • accumulate(begin, end, init)：计算序列中元素的累积总和。
   • inner_product(begin1, end1, begin2, init)：计算两个序列的内积。

5. 查询操作：

   • count(begin, end, value)：计算序列中特定值出现的次数。
   • find(begin, end, value)：在序列中查找特定值。

示例

#include <algorithm>
#include <vector>
#include <iostream>

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

    // 排序
    std::sort(vec.begin(), vec.end());

    // 查找
    bool found = std::binary_search(vec.begin(), vec.end(), 3);

    // 输出
    std::cout << "Sorted vector: ";
    for (int val : vec) {
        std::cout << val << " ";
    }
    std::cout << "\n3 found: " << found << std::endl;

    return 0;
}

输出：

Sorted vector: 1 2 3 4 5 
3 found: 1

向算法传递函数

在 C++ 的标准模板库（STL）中，许多泛型算法允许你传递函数或函数对象，以自定义算法的行为。这种机制增加了算法的灵活性和可重用性，允许你为算法指定特定的操作或自定义的比较、条件判断逻辑。

函数传递的方式

1. 函数指针：传统的方法是使用指向函数的指针。
2. 函数对象（Functors）：对象的类重载了 operator()，可以像函数一样被调用。
3. Lambda 表达式：C++11 引入的特性，允许你以匿名函数的方式直接在算法调用处定义函数逻辑。

示例

1. 使用函数指针

bool is_odd(int n) {
    return n % 2 != 0;
}

// 在算法中使用函数指针
std::vector<int> vec = {1, 2, 3, 4, 5};
auto it = std::find_if(vec.begin(), vec.end(), is_odd);

2. 使用函数对象

struct IsOdd {
    bool operator()(int n) const {
        return n % 2 != 0;
    }
};

// 在算法中使用函数对象
IsOdd is_odd_obj;
auto it = std::find_if(vec.begin(), vec.end(), is_odd_obj);

3. 使用 Lambda 表达式

// 在算法中直接使用 Lambda 表达式
auto it = std::find_if(vec.begin(), vec.end(), [](int n) { return n % 2 != 0; });

在所有这三个示例中，std::find_if 算法被用来查找 vec 中的第一个奇数。每个示例都展示了向算法传递函数的不同方式。

为什么使用函数传递

• 灵活性：你可以在不修改算法本身的情况下，改变算法的行为。
• 代码重用：可以在不同的上下文中重用相同的算法，应用不同的操作。
• 表达力：特别是使用 Lambda 表达式，你可以在算法调用的地方直接定义操作逻辑，使代码更加紧凑和易读。

Lambda 表达式

C++ 中的 Lambda 表达式是 C++11 引入的功能，它允许定义匿名函数。Lambda 表达式在 C++ 中非常有用，尤其是在需要简短且一次性的函数对象时，例如作为参数传递给 STL 算法。以下是 Lambda 表达式的主要知识点：

1. 基本语法

Lambda 表达式的基本语法如下：

[ capture_clause ] ( parameters ) -> return_type { body }

• 捕获子句（capture_clause）：定义了 Lambda 表达式从封闭作用域捕获变量的方式。
• 参数列表（parameters）：类似于常规函数的参数列表。
• 返回类型（return_type）：Lambda 表达式的返回类型。在某些情况下可以省略，让编译器自动推导。
• 函数体（body）：包含 Lambda 表达式的代码。

2. 捕获列表

捕获列表定义了 Lambda 表达式可以从封闭作用域中捕获哪些变量，以及如何捕获（值捕获或引用捕获）。

示例

• 值捕获：[x] 捕获变量 x 的副本。
• 引用捕获：[&x] 通过引用捕获变量 x。
• 隐式捕获：[=] 捕获所有外部变量的副本，[&] 捕获所有外部变量的引用。

3. 参数和返回类型

• 参数用于传递值给 Lambda 表达式。
• 返回类型可以显式指定，也可以让编译器自动推导。

示例

• 带参数的 Lambda：[](int x, int y) { return x + y; }
• 显式指定返回类型：[](int x, int y) -> int { return x + y; }

4. 使用场景

• 作为参数传递给 STL 算法。
• 用于定义短小的函数操作，避免定义单独的函数或函数对象。
• 在需要临时函数对象的场合使用。

5. Lambda 表达式与函数指针

Lambda 表达式可以转换为函数指针，前提是它不捕获任何外部变量。

示例

• void (*func)(int) = [](int x) { std::cout << x; };

6. 可变 Lambda

使用关键字 mutable 允许在值捕获模式下修改捕获的变量。

示例

• [x]() mutable { x = 42; }

7. 泛型 Lambda

C++14 引入的特性，使用自动类型推导的参数。

示例

• auto lambda = [](auto x, auto y) { return x + y; };

C++ 参数绑定

C++ 参数绑定是一种将函数或函数对象的部分参数预先设定（或“绑定”）的技术。这在 C++11 中通过 std::bind 函数模板实现，它位于 <functional> 头文件中。参数绑定通常用于将已有函数或函数对象的参数接口适配到特定场景的需求。

基本概念

std::bind

std::bind 接受一个可调用对象和一系列参数，返回一个新的可调用对象。新的可调用对象可以用更少的参数调用，因为一些参数已经被绑定。

占位符

std::placeholders 命名空间中的 _1、_2、_3 等是占位符，用于 std::bind 中表示未绑定的参数。

示例

1. 绑定普通函数

#include <functional>
#include <iostream>

void print(int a, int b, int c) {
    std::cout << a << ", " << b << ", " << c << std::endl;
}

int main() {
    auto bindPrint = std::bind(print, std::placeholders::_1, 2, std::placeholders::_2);
    bindPrint(1, 3); // 相当于 print(1, 2, 3);
    return 0;
}

2. 绑定成员函数

class MyClass {
public:
    void memberFunc(int x) {
        std::cout << "Value: " << x << std::endl;
    }
};

int main() {
    MyClass obj;
    auto bindMemberFunc = std::bind(&MyClass::memberFunc, &obj, std::placeholders::_1);
    bindMemberFunc(10); // 相当于 obj.memberFunc(10);
    return 0;
}

3. 绑定函数对象

struct Adder {
    int operator()(int a, int b) {
        return a + b;
    }
};

int main() {
    Adder adder;
    auto bindAdder = std::bind(adder, 5, std::placeholders::_1);
    std::cout << bindAdder(3); // 相当于 adder(5, 3);
    return 0;
}

注意事项

• 参数拷贝：std::bind 在绑定时会对其参数进行拷贝，除非使用 std::ref 或 std::cref 显式指定引用传递。
• 可读性：虽然 std::bind 提供了强大的功能，但过度使用可能会降低代码的可读性。在 C++11 及更高版本中，Lambda 表达式通常是更简洁和直观的选择。

再探迭代器

在 C++ 中，除了标准容器自带的迭代器之外，标准库还在 <iterator> 头文件中定义了四种特殊的迭代器。这些迭代器提供了不同于普通迭代器的特殊功能，使得操作容器和 IO 流更加灵活。

插入迭代器

插入迭代器绑定到容器上，使得可以通过迭代器向容器插入元素，而不是修改容器中已有的元素。

类型

• back_inserter：创建一个使用 push_back 的迭代器。
• front_inserter：创建一个使用 push_front 的迭代器（仅对支持 push_front 的容器有效）。
• inserter：创建一个使用 insert 的迭代器，可以在指定位置之前插入元素。

示例

std::vector<int> vec;
std::copy(vec.begin(), vec.end(), std::back_inserter(vec)); // 将 vec 的元素复制到其自身末尾

流迭代器

流迭代器绑定到输入或输出流上，可以用来遍历所关联的 IO 流。

类型

• istream_iterator：从 std::istream 对象读取数据。
• ostream_iterator：向 std::ostream 对象写入数据。

示例

std::istream_iterator<int> in_iter(std::cin), eof;
std::vector<int> vec(in_iter, eof); // 从标准输入读取数据填充到 vec

std::ostream_iterator<int> out_iter(std::cout, " ");
std::copy(vec.begin(), vec.end(), out_iter); // 将 vec 的内容输出到标准输出

反向迭代器

反向迭代器使迭代器在容器中向后移动，除了 std::forward_list 外，所有标准库容器都支持反向迭代器。

示例

std::vector<int> v = {1, 2, 3};
for (auto rit = v.rbegin(); rit != v.rend(); ++rit) {
    std::cout << *rit << " "; // 输出：3 2 1
}

移动迭代器

移动迭代器允许在算法中移动而非拷贝元素，这对于管理资源密集型对象的容器特别有用。

示例

std::vector<std::unique_ptr<int>> vec;
// 使用移动迭代器以避免拷贝 unique_ptr
std::vector<std::unique_ptr<int>> vec2(std::make_move_iterator(vec.begin()), 
                                       std::make_move_iterator(vec.end()));

泛型算法结构

C++ 标准模板库（STL）的泛型算法结构是一种高度模块化和可复用的设计，它使得这些算法能够独立于它们所处理的数据类型。泛型算法通常是通过模板实现的，这意味着算法可以用于不同类型的容器和迭代器。以下是泛型算法结构的关键特点：

5 类迭代器

在 STL 中，迭代器被分为五种类别，每种类别定义了迭代器支持的操作集合。这些类别是：

1. 输入迭代器：仅支持读操作，单向移动。
2. 输出迭代器：仅支持写操作，单向移动。
3. 前向迭代器：支持读写操作，单向移动。
4. 双向迭代器：支持读写操作，可前后双向移动。
5. 随机访问迭代器：支持读写操作，可在序列中随机访问。

这种分类方式使得泛型算法可以根据所需的迭代器类型来适配于不同的容器类型。

算法形参模式

泛型算法通常接受一对迭代器（表示一个范围）作为参数，这种设计使得算法可以在任何容器类型上操作，只要容器提供了适当类型的迭代器。例如，许多算法都接受形如 begin 和 end 的迭代器参数，用于指定算法作用的元素范围。

算法命名规范

为了表明算法的特定版本或特性，STL 算法通常遵循一定的命名规范。例如：

• 算法名称后缀 _if 表示算法接受一个谓词（如 find_if）。
• 算法名称后缀 _copy 表示算法会生成一个拷贝（如 copy_if）。
• 算法名称后缀 _n 表示算法作用于特定数量的元素（如 copy_n）。

特点与优势

• 类型独立性：泛型算法可以作用于任何数据类型。
• 灵活性：算法可以与不同的容器和迭代器类型配合使用。
• 可重用性：相同的算法可以用于多种数据结构和操作。
• 效率：泛型算法经过高度优化，能提供良好的性能。

特定容器算法

在 C++ 标准模板库（STL）中，除了通用的泛型算法之外，一些特定的容器还提供了它们自己的专用算法。这些特定容器算法利用了容器的内部结构，以提供更高效或更适合该容器类型的操作。以下是一些常见容器及其特定算法的概述：

1. std::list

由于 std::list 是一个双向链表，它提供了一些专门的成员函数来进行有效操作：

• sort()：在 std::list 内部对元素进行排序，比通用的 std::sort 算法更高效，因为 std::sort 要求随机访问迭代器。
• merge()：合并两个已排序的 std::list。
• remove()、remove_if()：从列表中移除元素。
• unique()：移除连续并且相等的元素。
• splice()：将来自另一个 std::list 的元素插入到当前列表的指定位置。

2. std::forward_list

作为单向链表，std::forward_list 提供了一些专门的成员函数，类似于 std::list，但适合单向迭代：

• merge()、remove()、remove_if()、splice_after()、unique()：功能与 std::list 中的相应方法类似，但适用于单向链表的特性。

3. std::map 和 std::set

基于红黑树的关联容器，提供了一些特定的成员函数：

• find()：在 std::map 或 std::set 中查找键值。
• count()：返回特定键出现的次数（对于 set 要么是 0 要么是 1）。
• lower_bound()、upper_bound()：返回指向范围的迭代器，该范围包含具有特定键的元素。
• equal_range()：返回一个迭代器对，表示具有特定键的元素的范围。

4. std::vector 和 std::deque

尽管 std::vector 和 std::deque 主要使用通用算法，但它们提供了一些特殊的成员函数，如 push_back()、pop_back()，以及 std::vector 的 reserve() 和 capacity()，这些函数利用了它们底层连续存储的特性。