【C++ 泛型编程 入门篇】 C++ 中的泛型算法 STL（sort，find）（一）

1. 引言

1.1 简述泛型编程和STL的重要性

在C++编程中，泛型编程（Generic Programming）和标准模板库（Standard Template Library，简称STL）在许多场景中起着不可替代的作用。让我们从心理学角度来看待这一问题。

泛型编程就像是一种心理弹性，它允许程序员抽象地考虑问题，而不仅仅是具体的数据类型或算法。正如心理学家Carol Dweck在她的《思维模式》一书中指出的，拥有"成长型思维模式"的人在面对挑战和困难时能够更加坚韧，因为他们看到了成长和学习的机会。泛型编程就是这样一种"成长型思维模式"的体现，它为我们提供了一种方式，可以在不知道具体类型的情况下编写代码，这极大地提高了代码的复用性和可维护性。

STL，即标准模板库，是C++的一部分，它包含了一些泛型算法（generic algorithms），例如sort、find等。这些算法可以操作各种不同类型的数据，这就像心理学家Abraham Maslow的“需求层次理论”中的“自我实现”层次，它代表着人们寻求实现自我最大潜能的愿望。通过使用STL中的泛型算法，我们可以实现代码的最大潜能，因为我们可以对各种数据类型执行相同的操作，无需为每种数据类型编写特定的代码。

英语中，我们可以这样描述泛型编程和STL的重要性：“Generic programming allows us to write code in a type-independent way, which significantly enhances code reusability and maintainability. The Standard Template Library, or STL, provides us with generic algorithms such as ‘sort’ and ‘find’, which can operate on various types of data. This maximizes the potential of our code as we don’t need to write specific code for each data type."

这句话中，“Generic programming allows us to write code in a type-independent way”是一个主从复合句。主句是"Generic programming allows us"，"to write code in a type-independent way"是一个表示目的的不定式短语作宾语补足语。"The Standard Template Library, or STL, provides us with generic algorithms"也是主从复合句，其中“or STL”是一个并列关系的插入语，"with generic algorithms"是介词短语作宾语补足语，"such as ‘sort’ and ‘find’"是一个举例说明的短语。

1.2 介绍泛型算法的基本概念

泛型算法（Generic Algorithms）是一种独立于任何特定类型的算法。这种算法可以作用于不同的数据类型，而不需要为每一种数据类型都编写特定的版本。它是通过模板（Templates）实现的，可以把模板看作是产生特定函数或类的蓝图。

心理学中的"模式化思维"（Patterned Thinking）与泛型算法有着惊人的相似性。模式化思维是一种重复使用思维模式以解决问题或理解事物的心理策略，正如泛型算法使用相同的模板解决不同类型的问题一样。

在STL中，泛型算法大致分为五类：排序和相关操作、heap操作、初始化和交换、修改序列操作、以及其他算法。

在英文口语交流中，我们可以这样描述泛型算法：“Generic algorithms are algorithms that are independent of any specific type. They can work with different data types without having to write specific versions for each one. They are implemented through templates, which can be thought of as blueprints for creating specific functions or classes."

这句话中，“Generic algorithms are algorithms that are independent of any specific type”是一个简单的主谓宾句。其中，“that are independent of any specific type”是一个定语从句，修饰前面的名词"algorithms"。句子后半部分 “They can work with different data types without having to write specific versions for each one"是一个主谓宾复合句，其中“without having to write specific versions for each one”是一个表示否定目的的短语，修饰前面的动词"work”。

2. STL中的泛型算法

2.1 定义及主要特性

泛型算法（Generic algorithms），是C++标准模板库（STL，Standard Template Library）中的一个重要组成部分。在日常的口语交流中，我们会说 “generic algorithms are a key part of the C++ Standard Template Library”.

泛型算法主要提供了一套在各种数据结构上执行操作的方法，而不需要编写重复的代码。它们的这种特性源自一种心理学上的现象，我们称之为抽象化（Abstraction）。抽象化是人类认知的一种基本方式，它帮助我们通过忽视细节来理解复杂的情况和概念。同样的，泛型编程和泛型算法，正是编程中的这种抽象化的体现。

根据著名的C++专家Bjarne Stroustrup的观点，他在《C++ 程序设计语言》一书中指出，泛型算法提供了高度的重用性和灵活性。

在STL中，泛型算法主要有以下特性：

1. 它们能够操作大多数容器类型。无论是STL内置的容器如vector, list, 还是自定义的容器，只要其满足迭代器的使用要求，都可以使用泛型算法。
   
2. 它们以迭代器为参数，而非容器。这种设计使得泛型算法能够与任何满足要求的容器进行交互。
   
3. 它们并不直接进行元素的读写，而是通过迭代器来完成。这使得它们与具体的容器实现解耦。
   

以下表格对比了几种常用的泛型算法：

讲述这些技术时，你可能会说 “The sort function can be used to order the elements of a container in a certain way. The find function can help us locate a specific element in a container. And the count function counts the number of occurrences of a specific element in a container.”

记住，泛型算法在大多数情况下都能够极大提高代码的效率和质量，因此了解并熟练应用它们是我们每个C++程序员的必修课。

2.2 常见泛型算法的分类

泛型算法（Generic algorithms）在STL中的种类繁多，可以根据其功能大致分为几个主要类别。通常，我们在讨论这些算法时，可以说 “Generic algorithms in the STL can be broadly divided into several categories based on their functionality.”

以下是主要的分类：

2.2.1 非修改序列算法（Non-modifying sequence algorithms）

非修改序列算法不会改变容器中的元素。例如查找（find），计数（count），比较（equal），搜索（search）等。如我们在英语口语中描述这类算法时，可以说 “Non-modifying sequence algorithms, such as find, count, equal, or search, don’t alter the elements in the container.”

2.2.2 修改序列算法（Modifying sequence algorithms）

修改序列算法会更改容器中的元素。如复制（copy），替换（replace），移除（remove），反转（reverse）等。对应的英语口语描述可以是 “Modifying sequence algorithms, like copy, replace, remove, or reverse, alter the elements in the container.”

2.2.3 排序和相关算法（Sorting and related algorithms）

排序和相关算法主要用于排序和其他相关的操作。这类算法包括排序（sort），部分排序（partial_sort），堆操作（make_heap, push_heap, pop_heap）等。在口语中，我们会说 “Sorting and related algorithms, including sort, partial_sort, and heap operations, are mainly used for sorting and related operations.”

2.2.4 数值算法（Numeric algorithms）

数值算法主要用于数值计算，包括求和（accumulate），内积（inner_product），部分求和（partial_sum）等。英语口语描述可以是 “Numeric algorithms, such as accumulate, inner_product, and partial_sum, are mainly used for numerical calculations.”

对于这四类泛型算法，其主要特点如下表：

以上就是STL中泛型算法的主要分类。理解这些分类有助于我们更好地理解和应用这些算法。

3.1 sort 算法(sort algorithm)

3.1.1 基本原理 (Basic Principles)

std::sort 是C++ STL中的一个泛型算法，它对序列进行排序(sorting)，使得排序后的序列按照某种特定顺序排列(ordered in a specific order)。在内部，std::sort 通常采用快速排序(Quick Sort)算法，但这并不是强制性的，因为C++标准并没有规定其必须使用哪种排序算法。这也是泛型编程的一种魅力，即抽象化，让我们专注于要解决的问题，而不是解决问题的具体方法。

在口语交流中，我们可以这样描述std::sort的工作原理：

“The std::sort function in the C++ Standard Template Library arranges elements in a sequence in a specific order. While it often uses the Quick Sort algorithm, it’s not a strict requirement according to the C++ standard.”

(在C++标准模板库中，std::sort函数将序列中的元素按照特定顺序排列。虽然它经常使用快速排序算法，但根据C++标准，这并不是一个严格的要求。)

这个句子使用了"The…arranges elements in a sequence"这样的结构来说明std::sort的主要功能，然后用"While…it’s not a strict requirement"的结构来表述std::sort的灵活性。

3.1.2 使用示例 (Usage Examples)

我们将开始使用一些示例来展示std::sort的用法。

#include <vector>
#include <algorithm>
int main() {
    std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    std::sort(v.begin(), v.end());
    // Now v = {1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9}
    return 0;
}

在这个例子中，我们首先创建了一个包含整数的std::vector。然后，我们调用std::sort，并将v.begin()和v.end()作为参数传递，这样std::sort就会对整个向量进行排序。

3.1.3 自定义类型排序策略 (Custom Type Sorting Strategies)

现在，我们来看看如何为自定义类型设计排序策略。假设我们有一个名为Person的类，其中包含firstName和lastName两个成员。我们想要按照lastName，然

后是firstName进行排序。

#include <vector>
#include <algorithm>
#include <string>
class Person {
public:
    std::string firstName;
    std::string lastName;
    Person(const std::string& firstName, const std::string& lastName)
        : firstName(firstName), lastName(lastName) {}
};
int main() {
    std::vector<Person> people = {
        Person("John", "Doe"),
        Person("Jane", "Doe"),
        Person("John", "Smith")
    };
    std::sort(people.begin(), people.end(),
        [](const Person& lhs, const Person& rhs) {
            if (lhs.lastName == rhs.lastName)
                return lhs.firstName < rhs.firstName;
            else
                return lhs.lastName < rhs.lastName;
        }
    );
    // Now people = {Person("Jane", "Doe"), Person("John", "Doe"), Person("John", "Smith")}
    return 0;
}

在这个例子中，我们创建了一个包含Person对象的std::vector。然后我们调用std::sort并传入一个自定义的比较函数。这个函数接受两个Person对象作为参数，首先比较它们的lastName，如果lastName相同，那么就比较firstName。通过这种方式，我们就能实现复杂的排序策略。这就体现出了STL泛型算法的威力，它可以轻易地适应各种复杂的需求。

在《Effective STL》中，Scott Meyers强调了自定义比较函数的重要性，并给出了许多实用的示例和建议。他说：“有效地使用STL，就要习惯于编写和使用自定义的操作函数”。这个建议对于理解和掌握STL的泛型算法非常有帮助。

对于泛型算法的理解，心理学家和计算机科学家George A. Miller的名言“人的短期记忆能容纳七项信息，误差范围为正负两项”给了我们一些启示。这表明我们应该在设计和使用泛型算法时，要考虑到人的认知限制，尽量将问题简化，只关注重要的部分，例如在设计比较函数时，我们只需要关注如何比较两个元素，而不需要考虑如何遍历序列或者如何交换元素，这些都是泛型算法已经帮我们处理好的。

3.2 find 算法(find algorithm)

3.2.1 基本原理 (Basic Principles)

std::find 是C++ STL中的另一个泛型算法，其功能是在一个序列中查找特定的元素(find a specific element in a sequence)。它将首尾迭代器(first and last iterators)作为参数，并顺序遍历(sequence)该范围内的所有元素，直到找到目标元素或到达末尾。

在口语交流中，我们可以这样描述std::find的工作原理：

“The std::find function in the C++ Standard Template Library searches for a specific element in a sequence. It takes two iterators representing the beginning and end of the sequence, and traverses the sequence in order until it finds the target or reaches the end.”

(在C++标准模板库中，std::find函数用于在序列中搜索特定元素。它接受两个迭代器，这两个迭代器代表序列的开始和结束，然后按顺序遍历序列，直到找到目标或者达到序列的末尾。)

这个句子使用了"The…searches for a specific element"这样的结构来描述std::find的主要功能，然后用"It takes…and traverses the sequence in order"来描述std::find的工作流程。

3.2.2 使用示例 (Usage Examples)

接下来我们用一个例子来说明std::find的用法。

#include <vector>
#include <algorithm>
#include <iostream>
int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    auto it = std::find(v.begin(), v.end(), 3);
    if (it != v.end())
        std::cout << "Element found: " << *it << std::endl;
    else
        std::cout << "Element not found" << std::endl;
    // Output: Element found: 3
    return 0;
}

在这个例子中，我们首先创建了一个std::vector，然后使用std::find来查找特定的元素。如果std::find找到了元素，它将返回指向该元素的迭代器，否则，它将返回end()迭代器。

3.2.3 自定义类型查找策略 (Custom Type Searching Strategies)

现在我们来看如何为自定义类型设计查找策略。我们还是使用Person类作为例子，但这次我们想要找到特定的人。

#include <vector>
#include <algorithm>
#include <string>
#include <iostream>
class Person {
public:
    std::string firstName;
    std::string lastName;
    Person(const std::string& firstName
, const std::string& lastName)
        : firstName(firstName), lastName(lastName) {}
};
int main() {
    std::vector<Person> people = {
        Person("John", "Doe"),
        Person("Jane", "Doe"),
        Person("John", "Smith")
    };
    auto it = std::find_if(people.begin(), people.end(),
        [](const Person& person) {
            return person.firstName == "John" && person.lastName == "Smith";
        }
    );
    if (it != people.end())
        std::cout << "Person found: " << it->firstName << " " << it->lastName << std::endl;
    else
        std::cout << "Person not found" << std::endl;
    // Output: Person found: John Smith
    return 0;
}

在这个例子中，我们创建了一个包含Person对象的std::vector。然后我们调用std::find_if并传入一个自定义的匹配函数。这个函数接受一个Person对象作为参数，并检查其是否满足我们的查找条件。这个例子显示了STL泛型算法的强大之处，即可以很容易地适应各种复杂的需求。

【C++ 泛型编程 入门篇】 C++ 中的泛型算法 STL（sort，find）（二）https://developer.aliyun.com/article/1465321