C++ 自定义排序字符串

2024 年 8 月 28 日 | 阅读 10 分钟

“自定义排序字符串” 指的是一种特定的字符串排序方式，它偏离了标准的字典序（词典顺序）。在自定义排序中，您为字符串中的字符或子字符串定义了排序顺序。这种自定义顺序可以基于各种标准，例如特定的字符序列或预定义的字符顺序。

C++ 中的自定义排序是一项强大功能，它允许您以不完全基于其自然顺序的方式对元素进行排序，例如整数或字符串的默认排序。相反，您可以定义元素排序的标准。当您处理没有内置比较运算符的复杂数据结构或自定义对象时，通常需要此功能。

自定义字符串排序通常用于需要以特定应用程序或上下文合理的方式对字符串进行排序的场景。

为什么使用自定义字符串排序？

非字母顺序排序：在许多情况下，您可能希望对不包含字母表中所有字母的字符串进行排序。例如，使用标准排序对包含数字、特殊字符和文本的文件名进行排序可能很困难。

自定义优先级：有时，某些字符串无论其字典顺序如何，都应排在排序列表的前面。这在用户界面中很常见，当您希望优先显示某些选项或类别时。

按特定标准排序：在某些应用程序中，您可能需要根据重要性、相关性或频率等特定标准对字符串进行排序。自定义排序允许您定义这些标准。

使用函数对象进行自定义排序

使用函数对象（也称为仿函数）进行自定义排序是 C++ 中的一种技术，它允许您在处理没有自然排序的元素时定义自定义排序标准。当对复杂数据结构或默认排序顺序（例如字母顺序或数字顺序）不适用的自定义对象进行排序时，这尤其有用。在本说明中，我们将详细介绍 C++ 中使用函数对象进行自定义排序的详细信息。

函数对象自定义排序基础

函数对象（仿函数）：在 C++ 中，函数对象或仿函数是一个充当函数的对象。仿函数通过在类或结构中重载operator() 来创建。此运算符允许您定义将用于排序的比较逻辑。

std::sort 算法：C++ 标准库 (STL) 中的std::sort 函数用于对范围内的元素进行排序。默认情况下，std::sort 使用小于 (<) 运算符来比较元素以进行排序。但是，您可以通过将自定义仿函数传递给std::sort 来提供自定义比较逻辑。

创建自定义仿函数进行排序

以下是创建和使用自定义仿函数进行排序的分步指南：

定义仿函数类或结构：创建一个类或结构，重载 operator() 以定义排序标准。此运算符应在第一个元素应排在第二个元素之前时返回 true，否则返回 false。

struct CustomComparator {
 bool operator()(const T& element1, const T& element2) const {
 // Define your custom comparison logic here
 }
};

将T 替换为您要排序的元素的**数据类型**。

实例化仿函数：创建自定义比较器仿函数的一个**实例**。

使用 std::sort 和自定义仿函数：调用std::sort，传入要排序的元素范围和自定义比较器仿函数作为参数。

程序

让我们以一个示例来演示 C++ 中的自定义排序字符串。

#include <iostream>
#include <vector>
#include <algorithm>
class Person {
public:
 std::string name;
 int age;
 Person(const std::string& n, int a) : name(n), age(a) {}
};
struct AgeComparator {
 bool operator()(const Person& person1, const Person& person2) const {
 return person1.age < person2.age;
 }
};
int main() {
 std::vector<Person> people = {
 {"Alice", 30},
 {"Bob", 25},
 {"Charlie", 35},
 {"David", 22},
 };
 // Create an instance of the custom comparator functor
 AgeComparator ageComparator;
 // Sort the vector of Person objects by age
 std::sort(people.begin(), people.end(), ageComparator);
 //Display the sorted result
 for (const Person& person : people) {
 std::cout << person.name << " (" << person.age << " years) ";
 }
 return 0;
}

输出

David (22 years) Bob (25 years) Alice (30 years) Charlie (35 years)

说明

在此示例中，我们包含必要的 C++ 标准库头文件，例如<iostream> 以启用输入和输出操作，<vector> 头文件以创建动态数组（向量），并使用std::sort 函数进行排序。
之后，我们定义一个名为Person的自定义类来表示个人。该类有两个属性：name，一个代表姓名的字符串，以及 age，一个代表年龄的整数。该类还有一个构造函数，可在创建Person 对象时初始化这些属性。
接下来，我们定义一个名为AgeComparator的自定义比较仿函数。仿函数是充当函数的对象。在这种情况下，AgeComparator 重载了operator() 以定义自定义比较逻辑。该逻辑根据年龄（person1.age 和 person2.age）比较两个 Person 对象，如果 person1 应该排在 person2 之前，则返回 true，否则返回 false。

在 main() 函数中：

我们创建一个名为people的向量，该向量存储 Person 类的实例。这些实例代表具有姓名和年龄的个人。
我们创建了一个名为 ageComparator 的自定义比较仿函数AgeComparator 的实例。此仿函数将用于定义排序顺序。
我们使用std::sort 函数对 Person 对象向量 people 进行排序。std::sort 函数接受三个参数：要排序的范围的开始和结束迭代器（people.begin() 和 people.end()）以及自定义比较仿函数 ageComparator。它告诉std::sort 使用 AgeComparator 仿函数来确定基于年龄的排序顺序。
最后，我们通过遍历 people 向量并将每个人的姓名和年龄打印到控制台来显示排序结果。
代码的输出将是按年龄排序的 Person 对象列表，其姓名和年龄按年龄升序显示。

复杂度分析

时间复杂度

创建 Person 对象：创建Person 类的实例并初始化其属性，每个对象的**时间复杂度**为 **O(1)**。如果 people 向量中有 **'n'** 个人，则创建和初始化对象的总**时间复杂度**为 **O(n)**。
排序 (std::sort)：在此代码中，最重要的时间复杂度因素是使用std::sort 的排序操作。std::sort 的时间复杂度通常取决于所使用的排序算法。在大多数 STL 实现中，它使用高效的排序算法，如introsort（快速排序、堆排序和插入排序的组合）。
平均而言，快速排序（它是 introsort 的一部分）的**平均情况时间复杂度**为 **O(n log n)**。
在最坏的情况下，快速排序可能会退化到 **O(n^2)**，但这种情况发生的可能性很小，并且 introsort 会采取措施来防止这种情况。
实际上，std::sort 经过高度优化，并且对于中小型输入，其性能通常优于 **O(n log n)** 算法。
因此，对于排序步骤，**平均**和**最坏情况**下的**总时间复杂度**通常为 **O(n log n)**。不过，由于优化，它在实践中可能会更快。

空间复杂度

向量 people：people 向量的**空间复杂度**为 **O(n)**，其中 **'n'** 是向量中存储的 Person 对象的数量。这包括存储每个人姓名和年龄属性的内存。
自定义比较仿函数 (AgeComparator)：自定义比较仿函数AgeComparator 的**空间复杂度**可忽略不计。它只存储比较逻辑，这只需要很小的内存量。
局部变量和常量：像ageComparator 这样的局部变量和代码中使用的常量的**空间复杂度**也可忽略不计，并且不取决于输入大小。

使用 lambda 函数进行自定义排序

C++ 中使用 lambda 函数进行自定义排序是一种技术，它允许您在不需要单独的比较函数或仿函数的情况下内联定义自定义排序标准。Lambda 是匿名函数，可以捕获其封闭作用域中的变量，使其成为小型、一次性排序操作的简洁方便的选择。在本说明中，我们将探讨如何在 C++ 中使用 lambda 函数进行自定义排序。

Lambda 函数自定义排序基础

Lambda 函数：Lambda 函数是一个紧凑的匿名函数，可以在内联定义。Lambda 函数允许您指定自定义行为，而无需定义单独的命名函数或仿函数。

std::sort 算法：就像使用函数对象进行自定义排序一样，您可以使用 C++ 标准库中的std::sort 函数和 lambda 函数对一系列元素进行排序，其顺序基于您的自定义标准。

创建用于排序的 Lambda 函数

以下是创建和使用 lambda 函数进行自定义排序的分步指南：

Lambda 语法：Lambda 函数使用以下语法定义：

[capture_clause](parameter_list) -> return_type {
 // Function body with custom logic
}

capture_clause：它指定应捕获封闭作用域中的哪些变量，并使其在 lambda 函数内部可用。

parameter_list：它指定函数的参数。

return_type：它指定返回类型。

自定义逻辑：在 lambda 的函数体内，您可以定义自定义比较逻辑。

使用 Lambda 进行 std::sort：调用std::sort，传入要排序的元素范围和 lambda 函数作为参数。

程序

让我们以一个示例来演示 C++ 中带有lambda 的自定义排序字符串。

#include <iostream>
#include <vector>
#include <algorithm>
int main() {
 std::vector<std::string> words = {"apple", "banana", "cherry", "date", "fig"};
 // Sort the vector of strings by length in descending order using a lambda function
 std::sort(words.begin(), words.end(), [](const std::string& str1, const std::string& str2) {
 return str1.length() > str2.length(); // Custom comparison logic
 });
 //Display the sorted result
 for (const std::string& word : words) {
 std::cout << word << " ";
 }
 return 0;
}

输出

banana cherry apple date fig

说明

在此示例中，我们使用#include 包含必要的 C++ 标准库头文件。

在 main() 函数中：

我们创建一个名为words的字符串向量，并用五个字符串元素初始化它。
之后，我们使用std::sort 函数对 words 向量进行排序。lambda 函数用作自定义比较逻辑，以按长度降序比较字符串。
使用 for 循环将排序后的结果显示到控制台，并打印每个单词。

复杂度分析

时间复杂度

代码的时间复杂度由排序操作决定，对于按长度降序排序字符串，**平均**约为 **O(n log n)**。

空间复杂度

代码的空间复杂度主要由 words 向量的大小决定，导致**空间复杂度**为 **O(n)**。**时间复杂度**由排序操作决定，该操作的**平均情况时间复杂度**为 **O(n log n)**。不过，由于 std::sort 算法提供的优化，它在实践中可能会更快。

使用复杂数据结构进行自定义排序

C++ 中使用复杂数据结构进行自定义排序涉及根据特定标准或属性在诸如数组、向量或自定义类之类的数据结构中排列元素。它允许您根据自己的独特要求对数据进行排序，而不是依赖于元素的默认排序顺序。以下是使用复杂数据结构进行自定义排序的说明：

自定义排序过程

定义数据结构：您首先定义包含数据的复杂数据结构。它可以是数组、向量或封装多个属性的自定义类。

自定义比较逻辑：确定对数据进行排序的标准。您需要创建一个自定义比较函数、仿函数或 lambda 函数，以定义元素的比较方式。比较逻辑通常侧重于数据结构的一个或多个属性。

使用排序算法：使用自定义比较逻辑，应用排序算法，例如向量的std::sort 或数组的自定义排序例程。排序算法根据您的标准重新排列元素。

显示或使用排序后的数据：排序后，您可以显示排序后的数据或在程序中将其用于进一步处理。

程序

让我们以一个示例来演示 C++ 中带有复杂数据结构的自定义排序字符串。

#include <iostream>
#include <algorithm>
class Student {
public:
 std::string name;
 int age;
 Student(const std::string& n, int a) : name(n), age(a) {}
};
bool compareByAge(const Student& student1, const Student& student2) {
 return student1.age < student2.age;
}
int main() {
 Student students[] = {{"Alice", 20}, {"Bob", 22}, {"Charlie", 19}};
 int numStudents = sizeof(students) / sizeof(students[0]);
 std::sort(students, students + numStudents, compareByAge);
 // Display sorted students by age
 for (int i = 0; i < numStudents; i++) {
 std::cout << students[i].name << " (" << students[i].age << " years) ";
 }
 return 0;
}

输出

Charlie (19 years) Alice (20 years) Bob (22 years)

说明

在此示例中，我们定义了一个名为Person的自定义类来表示个人，它有两个属性：name（字符串）和age（整数）。该类有一个构造函数，可在创建Person对象时初始化这些属性。

在 main() 函数中：

在此函数中，我们创建一个名为people的 Person 对象向量，并用三个 Person 实例对其进行初始化，每个实例都有一个name和age。
我们使用std::sort 函数对 people 向量进行排序。我们提供了一个 lambda 函数作为自定义比较逻辑。lambda 函数接受两个 Person 对象（person1 和 person2）作为参数，并使用< 运算符根据它们的姓名属性进行比较。此 lambda 函数定义了按姓名升序排序的顺序。
排序后，people 向量包含按姓名字母顺序排序的 Person 对象。
我们使用基于范围的 for 循环遍历已排序的 people 向量，并将每个人的姓名和年龄显示到控制台。

复杂度分析

时间复杂度

代码的时间复杂度由排序操作决定，对于按姓名对 people 向量进行排序，**平均**约为 **O(n log n)**。

空间复杂度

代码的空间复杂度主要由 people 向量的大小决定，导致**空间复杂度**为 **O(n)**。

下一个主题C++ 中的堆栈函数：

C++ 自定义排序字符串

为什么使用自定义字符串排序？

使用函数对象进行自定义排序

函数对象自定义排序基础

创建自定义仿函数进行排序

程序

在 main() 函数中：

复杂度分析

使用 lambda 函数进行自定义排序

Lambda 函数自定义排序基础

创建用于排序的 Lambda 函数

程序

使用复杂数据结构进行自定义排序

自定义排序过程

程序

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 自定义排序字符串

为什么使用自定义字符串排序？

使用函数对象进行自定义排序

函数对象自定义排序基础

创建自定义仿函数进行排序

程序

在 main() 函数中：

复杂度分析

使用 lambda 函数进行自定义排序

Lambda 函数自定义排序基础

创建用于排序的 Lambda 函数

程序

使用复杂数据结构进行自定义排序

自定义排序过程

程序

相关帖子

C++ Is_open 函数

C++ 五法则

C++ 符号表

C++ unordered_multimap max_load_factor() 函数

在 C++ 的 Map 中按值搜索

C++ 智能指针