【C++ 泛型编程 入门篇】 C++ 中的泛型算法 STL（sort，find）（一）https://developer.aliyun.com/article/1465319
4. 自定义类型和泛型算法
4.1 为什么需要为自定义类型设计算法
在C++编程中，我们常常需要处理不仅仅是基本类型（basic types）如int, double等，而是自定义类型（custom types），例如结构体（structures）或类（classes）。这就引入了对自定义类型（也称为用户定义类型，User-Defined Types, UDT）的泛型算法设计的需求。
泛型算法（Generic algorithms）的核心是提供一种可以对不同类型的元素进行操作的方式，而不是为每种可能的类型编写单独的函数。在“Effective STL”（《高效STL》）一书中，Scott Meyers强调了泛型编程（generic programming）的重要性，它的目标是将软件组件的行为与它们操作的数据类型分离。这就意味着，我们可以编写一套代码，然后用于各种数据类型，包括我们自定义的类型。
从心理学角度来看，这种方式可以降低我们的认知负荷（Cognitive Load）。在处理复杂任务，如编程时，我们的工作记忆（Working Memory）是有限的。通过使用泛型算法，我们可以将复杂性（complexity）从我们处理数据类型的方式中抽象出来，使我们可以专注于解决问题的核心部分。
让我们考虑一个常见的编程任务——排序（sorting）。对于基本类型，如int或double，排序是简单明了的，因为这些类型有明确的比较规则。但是，对于自定义类型，我们需要提供一个比较方法，定义怎样的对象“大于”或“小于”另一个对象。这就是为自定义类型设计算法的需求所在。
下表比较了基本类型和自定义类型排序的不同。
| 基本类型排序 | 自定义类型排序 |
| 有明确的比较规则 | 需要自定义比较规则 |
| 无需为特定类型编写代码 | 需要为特定类型编写代码 |
在英语口语交流中，我们可能会这样描述：“In C++ programming, not only do we handle basic types like integers and doubles, but we often work with custom types such as structures and classes. This leads to the need for designing generic algorithms for these custom types.”（在C++编程中，我们不仅处理基本类型，如整数和双精度浮点数，我们经常使用自定义类型，如结构和类。这就引起了为这些自定义类型设计泛型算法的需求。）
这里使用了现在进行时（Present Continuous Tense），表示一种正在进行或者经常发生的情况。
而"leads to"表示导致的意思，是一个常用的英语表达方式，后接名词或者动名词形式的结果。
请注意，理解这个过程的核心在于理解你正在编写的代码中的数据类型，以及你可以如何用泛型算法来简化你的代码。根据心理学家George A. Miller的“魔数七”理论，人类的短期记忆的容量大约为七个信息单元。如果我们能够使用泛型算法来减少我们需要记住的代码和规则，我们就能更有效地利用我们的认知资源，编写出更清晰、更高效的代码。
4.2 如何为自定义类型设计sort和find算法
设计自定义类型的泛型算法，如sort和find，需要为这些类型提供比较函数和等价函数。这些函数定义了如何比较和搜索自定义类型的实例。
4.2.1 自定义类型的比较函数
对于sort算法，我们需要提供一个比较函数，这个函数接受两个参数并返回一个布尔值，表示第一个参数是否应该在排序顺序中位于第二个参数之前。例如，假设我们有一个Person类，它有一个name字段和一个age字段，我们可以这样定义一个比较函数：
struct Person { std::string name; int age; }; bool comparePersons(const Person& a, const Person& b) { return a.name < b.name; // sort by name in ascending order }
然后，我们可以使用这个函数与sort算法一起，对Person对象的std::vector进行排序：
std::vector<Person> people = {...}; std::sort(people.begin(), people.end(), comparePersons);
在英语口语交流中，你可能会说：“To sort custom types, we need to provide a comparison function that takes two arguments and returns a boolean value indicating whether the first argument should come before the second one in the sorted order.”（要对自定义类型进行排序，我们需要提供一个比较函数，这个函数接受两个参数，返回一个布尔值，表示第一个参数在排序顺序中是否应该在第二个参数之前。）
4.2.2 自定义类型的查找函数
对于find算法，我们需要提供一个等价函数，这个函数接受一个元素和一个目标值，并返回一个布尔值，表示这个元素是否等于目标值。例如，假设我们想要在上述Person对象的std::vector中找到一个具有特定名字的人，我们可以定义一个等价函数：
bool hasName(const Person& person, const std::string& targetName) { return person.name == targetName; }
然后，我们可以使用std::find_if函数和这个等价函数，来找到名字匹配的Person：
std::string nameToFind = "Alice"; auto it = std::find_if(people.begin(), people.end(), [&nameToFind](const Person& person) { return hasName(person, nameToFind); }); if (it != people.end()) { // found a person named Alice } else { // no person named Alice found }
在英语口语交流中，你可能会说：“To find a specific element in a container of custom types, we need to provide an equivalence function that takes an element and a target value and returns a boolean value indicating whether the element is equal to the target value.”（要在自定义类型的容器中找到特定元素，我们需要提供一个等价函数，这个函数接受一个元素和一个目标值，并返回一个布尔值，表示这个元素是否等于目标值。）
自定义类型的比较函数和等价函数使我们能够将STL的泛型算法应用于自定义类型，使得我们的代码更加通用和灵活。在高级C++编程中，这是一种重要的技巧。
5. 使用泛型算法处理复杂数据结构
5.1 泛型算法在处理容器时的优势
在开始前，我想引用一位著名的心理学家，Abraham Maslow的话：“如果你只有一把锤子，你会看待每一样东西都像是钉子。” (Abraham Maslow once said: “If the only tool you have is a hammer, you tend to see every problem as a nail.”) 这句话也适用于我们的编程世界，尤其是在处理复杂数据结构时。如果我们只会使用单一的编程策略，可能会错失许多更高效，更优雅的解决问题的方式。
STL（Standard Template Library，标准模板库）中的泛型算法（Generic algorithms）提供了一种强大的工具，让我们能以更加抽象、更加高效的方式处理复杂的数据结构。比如说，STL中的sort和find算法可以用于各种类型的容器（Containers），而无需我们为每种容器单独编写排序或查找的代码。这就是所谓的“针对接口编程，而不是针对实现编程”（Program to an interface, not an implementation）这一编程原则的应用。
以下是STL中常见的一些容器类型，以及他们在某些常见泛型算法中性能的对比：
| 容器（Containers） | sort算法时间复杂度 | find算法时间复杂度 |
| vector（向量） | O(n log n) | O(n) |
| deque（双端队列） | O(n log n) | O(n) |
| list（链表） | O(n log n) | O(n) |
| set/map（集合/映射） | - | O(log n) |
这表明泛型算法可以将算法的实现从数据结构中解耦出来，使得算法可以独立于它们处理的数据结构。这不仅有助于提高代码的可重用性，也大大提高了代码的效率。
在实际的编程工作中，如果你能熟练运用STL中的泛型算法，就如同在你的工具箱中多了一把“瑞士军刀”。当你面临复杂的编程问题时，你不再需要花费大量的时间和精力去编写繁琐的代码，只需要调用STL中的泛型算法，就能以更加简洁、高效的方式解决问题。在心理学角度来看，这种方式不仅可以降低你的心理压力，提高你的工作满足感，也可以提高你的工作效率。
这就是泛型算法在处理复杂数据结构时的优势。在下一节中，我将会介绍如何应用这些泛型算法处理更复杂的数据结构。
5.2 如何应用于复杂数据结构
处理复杂数据结构时，STL的泛型算法具有巨大优势。接下来，我们以处理嵌套数据结构（Nested Data Structures）为例，解释如何在实际情况中应用泛型算法。
嵌套数据结构是在数据结构中包含另一个数据结构的情况。例如，我们可能有一个std::vector<std::list<int>>，这是一个内部元素为std::list<int>的std::vector。
这是一个挑战，因为我们可能需要在所有内部列表中查找一个元素，或对所有内部列表进行排序。这在没有泛型算法的情况下可能需要编写大量的手动循环。
然而，STL的泛型算法使这些任务变得简单。例如，要在所有内部列表中查找元素，我们可以使用STL的find_if和find来编写一个简洁的单行代码：
auto it = std::find_if(vec.begin(), vec.end(), [value](const auto& list){return std::find(list.begin(), list.end(), value) != list.end();});
在这里，find_if（查找如果）用于在std::vector中查找满足特定条件的元素。这个特定条件是一个lambda函数，它使用find在std::list中查找特定值。
同样，我们也可以使用for_each和sort来对所有内部列表进行排序：
std::for_each(vec.begin(), vec.end(), [](auto& list){std::sort(list.begin(), list.end());});
在这里，for_each（对每一个）用于对std::vector中的每个元素执行特定操作。这个特定操作是一个lambda函数，它使用sort对std::list进行排序。
通过这两个例子，我们可以看到，泛型算法使处理复杂数据结构变得非常简单。只需一行代码，我们就可以实现在所有内部列表中查找元素或对所有内部列表进行排序，这要比使用手动循环简洁得多，也更不容易出错。
总的来说，STL的泛型算法为我们提供了一种简洁、高效且强大的工具，使我们能够轻松处理复杂的数据结构。在实际编程工作中，无论我们面临什么样的问题，都应尽可能地利用这些泛型算法，以提高我们的工作效率和代码质量。
6. 泛型算法与Qt6的融合应用
6.1. 如何在Qt6环境下使用STL泛型算法
在Qt6环境下使用STL泛型算法（Standard Template Library Generic Algorithms）是一个普遍的技巧，可以高效地解决许多问题。我们不仅可以在Qt6中使用预定义的STL类型，而且还可以在自定义数据类型中使用STL。
首先，让我们回顾一下STL泛型算法的本质。泛型编程（Generic Programming）让我们可以写出类型独立的代码，这是通过使用模板（Templates）来实现的。而STL泛型算法，正是这种泛型编程思想的体现，它们可以操作各种数据类型的元素，只要这些元素满足算法的基本需求即可。
在C++的"Effective STL"一书中，Scott Meyers强调了泛型算法的灵活性和泛用性：“STL的算法部分是库中最好的部分。如果你找到了一种手动管理数据结构的方法，那么有一种可能性：STL已经有了更好的方法。”(STL’s algorithm component is the best part of the library. If you’re manually manipulating data structures, there’s a good chance that STL has a better way.)
6.1.1 使用STL算法
在Qt中使用STL算法很简单。首先，包含必要的头文件，比如#include <algorithm>。然后，像在任何其他C++环境中一样调用算法。
例如，假设我们有一个QVector<int>，我们想要找出这个向量中的最大元素。我们可以用STL的std::max_element算法来做这件事：
#include <algorithm> #include <QVector> QVector<int> data = {1, 3, 2, 8, 5, 7}; auto maxElementIter = std::max_element(data.begin(), data.end());
在上面的代码中，std::max_element会返回一个指向data中最大元素的迭代器（iterator）。这是一个典型的使用STL算法的例子。
我们说 “I am looking for the maximum element in the vector using the std::max_element function.” (我正在使用std::max_element函数寻找向量中的最大元素。)
在英语中，这个句子的语法结构是我+正在进行的动作+宾语的描述。在这里，“looking for the maximum element in the vector”是进行的动作，“using the std::max_element function”是这个动作的方法或工具。
6.1.2 适用于Qt的STL算法
Qt库有一些自己的容器类，如QVector，QList等。这些类有与STL容器类似的接口，因此你可以在它们上使用STL算法。但需要注意的是，Qt容器和STL容器的迭代器是不兼容的，你不能将STL迭代器用在Qt容器上，反之亦然。
不过，Qt提供了一种将Qt容器转换为STL容器的方法。例如，你可以使用QVector::toStdVector将QVector转换为std::vector。
QVector<int> data = {1, 3, 2, 8, 5, 7}; std::vector<int> stdData = data.toStdVector(); auto maxElementIter = std::max_element(stdData.begin(), stdData.end());
同样，我们可以说 “I am converting the QVector to a standard vector using the toStdVector method before applying the max_element algorithm.” (我在应用max_element算法之前，正在使用toStdVector方法将QVector转换为标准向量。)
在这个句子中，我们使用了“before applying the max_element algorithm”来指出在执行主要动作（“converting the QVector”）之前做了什么。这是英语中常见的描述动作顺序的一种方式。
此外，值得一提的是心理学家在研究人类认知过程时发现，人们在理解和解决问题时通常会进行模型转换，即将问题从一个表现形式转换为另一个更容易处理的表现形式，这在编程中也是常见的策略，如上面的QVector到std::vector的转换。
在下一个章节中，我们将探讨如何在Qt Quick中使用STL泛型算法。
6.2. STL泛型算法在Qt Quick中的应用示例
Qt Quick，作为Qt框架中的一部分，是用于创建动态的、跨平台的用户界面的工具。它主要使用一种叫做QML的声明式语言，这种语言是面向JavaScript的。然而，C++代码也可以和QML进行交互，这就为我们在Qt Quick应用中使用STL泛型算法提供了可能性。
为了让QML和C++交互，我们需要使用Qt的元对象系统（Meta-Object System）。具体来说，我们需要在C++中创建一个QObject派生类，然后在QML中注册这个类。然后，我们可以在QML中创建这个类的实例，并访问它的属性、调用它的方法、接收它的信号等。
假设我们有一个在C++中定义的QObject派生类，它有一个公共槽（public slot）用于处理一个整数列表：
class ListProcessor : public QObject { Q_OBJECT public slots: QVariantList processList(const QVariantList &list) { // Convert the QVariantList to a std::vector. std::vector<int> data; for (const QVariant &var : list) { data.push_back(var.toInt()); } // Use the std::sort algorithm to sort the data. std::sort(data.begin(), data.end()); // Convert the std::vector back to a QVariantList and return it. QVariantList sortedList; for (int i : data) { sortedList.append(i); } return sortedList; } };
在上述代码中，processList方法接受一个QVariantList（在QML中就是一个普通的JavaScript数组），然后使用std::sort算法对其进行排序，并返回排序后的列表。我们在C++中实现了这个方法，然后在QML中调用它。
在QML中，我们可以这样使用ListProcessor类：
import MyModule 1.0 ListProcessor { id: processor } Component.onCompleted: { var list = [5, 3, 1, 4, 2]; console.log("Original list: " + list); list = processor.processList(list); console.log("Sorted list: " + list); }
上述代码在QML中创建了一个ListProcessor的实例，并使用了它的processList方法来对一个数组进行排序。结果会在控制台中打印出来。
如此，我们将C++中的STL泛型算法成功地应用到了Qt Quick中。在英语中，我们可以这样描述这个过程：“I am using the ListProcessor class defined in C++ to sort an array in QML. This is done by calling the processList method of the ListProcessor instance.” (我正在使用在C++中定义的ListProcessor类来对QML中的一个数组进行排序。这是通过调用ListProcessor实例的processList方法来实现的。) 在这个句子中，“using the ListProcessor class defined in C++”是主要的动作，“to sort an array in QML”是这个动作的目的，“This is done by calling the processList method of the ListProcessor instance” 是实现这个动作的具体步骤。
7.1 基于ffmpeg的音视频数据处理中的STL泛型算法应用案例
在音视频处理领域中，C++ STL（Standard Template Library, 标准模板库）中的泛型算法被广泛使用，尤其是在使用ffmpeg库进行开发时。
使用STL泛型算法处理音频数据
音频数据通常是以一定的顺序存储在容器（例如，std::vector）中的。一个常见的任务是对这些数据进行排序或查找。例如，您可能需要找到音频数据中的最大值或最小值，或者将数据按照一定的顺序进行排序。这些任务都可以通过STL的泛型算法（generic algorithm）来实现。
在使用STL的泛型算法处理音频数据时，你需要特别注意数据的类型（type）。因为音频数据可能是整数（int）、浮点数（float）或者双精度浮点数（double）等不同的类型。对于不同类型的数据，需要使用适当的STL泛型算法。比如，如果数据是整数类型，那么你可以使用std::sort算法进行排序；如果数据是浮点类型，你可能需要使用std::stable_sort算法，以保证相同的元素在排序后保持原来的相对顺序（In English: To ensure the relative order of equal elements remains the same after sorting, you may need to use std::stable_sort when dealing with floating-point data. 这个句子的主语是"To ensure the relative order of equal elements remains the same after sorting"，而谓语动词是"may need"，代表可能需要做的行动。这是一种英语语法中的主谓倒装句型，通常用于强调句子的主语）。
在处理音频数据时，我们可能也会用到其他的STL泛型算法，例如std::transform，它可以对容器中的所有数据应用一个函数；std::for_each，它可以对容器中的所有数据执行一个操作。这些都是非常高效且强大的工具，可以帮助我们更快更好地处理音频数据。
下表对比了几种常用的STL泛型算法的应用：
| 算法 | 功能 | 适用数据类型 | 应用场景 |
| std::sort | 排序 | 所有可比较类型 | 对音频数据进行排序 |
| std::stable_sort | 稳定排序 | 所有可比较类型 | 对音频数据进行排序，且保证相等元素的相对顺序 |
| std::find | 查找 | 所有类型 | 查找音频数据中的某个值 |
| std::transform | 应用函数 | 所有类型 | 对音频数据应用一个函数，如将所有数据乘以一个因子 |
| std::for_each | 执行操作 | 所有类型 | 对音频数据执行一个操作，如打印所有数据 |
在ffmpeg中使用STL泛型算法
在ffmpeg中，我们经常需要处理音频和视频数据。这些数据通常被存储在C数组或者std::vector中。ffmpeg提供了一些函数和结构体来操作这些数据，但有时候使用STL的泛型算法可以更方便高效。
例如，如果我们想要找出一个音频数据数组中的最大值，我们可以使用std::max_element算法。这个算法会返回指向数组中最大元素的迭代器。然后，我们可以通过解引用这个迭代器来获得最大值。
这里有一个使用ffmpeg和STL泛型算法处理音频数据的例子。在这个例子中，我们首先使用ffmpeg读取一个音频文件的数据，然后使用std::max_element找出数据中的最大值，最后使用std::for_each将所有的数据减去这个最大值（In English: Here is an example of using ffmpeg and STL generic algorithms to process audio data. In this example, we first use ffmpeg to read the data of an audio file, then use std::max_element to find the maximum value in the data, and finally use std::for_each to subtract this maximum value from all data. 这个句子使用了并列句型，即将多个简单句通过并列连词"and"连接起来，形成一个复合句。在这个句子中，每个并列的简单句都是一个完整的行动，这三个行动共同组成了一个完整的过程）。
8. 结语
C++标准模板库（STL）的泛型算法持续发展，展望未来，其在编程世界中的作用将更加重要。随着编程语言和技术的进步，我们可以期待更多的泛型算法会被添加到STL中。在处理各种复杂的编程问题时，泛型算法将为我们提供强大的工具。
编程是一门艺术，也是一门科学。作为编程者，我们要勇于挑战，乐于探索，不断学习，才能在这个不断变化的领域中找到自己的位置。我希望你们在学习C++泛型算法和STL的过程中，不仅能掌握其理论知识，更能理解其背后的设计哲学，发现其中的美学。
让我们一起用编程语言塑造世界，创造未来。愿你在编程的道路上越走越远，成为真正的编程大师。
