C++ 精通 std::sort 与自定义比较器

第一部分：'魔法黑盒'—— std::sort 的基本用法

std::sort 的'按钮'需要你提供两个'书签'（迭代器），告诉它要排序的'范围'：

std::sort(起始书签，结束书签);

对于 vector，这两个'书签'就是：

• myVector.begin()：指向第一个元素。
• myVector.end()：指向最后一个元素之后的'无效'位置。

std::sort 会排序 [begin, end) 范围内的所有元素（包括 begin，不包括end）。

basic_sort.cpp

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

// 1. 包含'算法'工具包
using namespace std;

// 辅助函数：打印 vector 内容
void printVector(const string& title, const vector<int>& vec) {
    cout << title << "[ ";
    for (int x : vec) {
        cout << x << " ";
    }
    cout << "]" << endl;
}

int main() {
    vector<int> numbers = {12, 5, 13, 7, 2};
    printVector("原始：", numbers);

    // 2. '按下按钮'：传入'开始'和'结束'书签
    std::sort(numbers.begin(), numbers.end());
    printVector("排序后 (升序): ", numbers);

    return 0;
}

'手把手'终端模拟：

PS C:\MyCode> g++ basic_sort.cpp -o basic_sort.exe -std=c++11
PS C:\MyCode> .\basic_sort.exe
原始： [ 12 5 13 7 2 ]
排序后 (升序): [ 2 5 7 12 13 ]

顿悟时刻： 默认情况下，std::sort 使用 operator<（小于号）来比较元素，实现升序排序。

第二部分：'递上纸条'——自定义比较器 (Comparator)

如果你想降序（从大到小）排序呢？你需要给 sort'递一张纸条'（第三个参数），告诉它新的'比较规则'。

这个'规则'是一个函数（或 C++11 的 Lambda 表达式），它必须：

1. 接收两个同类型的参数（const& 是最高效的方式）。
2. 返回一个 bool 值。
3. '黄金法则'： 如果你希望 a 排在 b 的前面，就返回 **true**；否则返回 false。

custom_sort.cpp

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

using namespace std;

// (printVector 函数和上面一样) ...

// --- '自定义规则 1' (降序) ---
// '如果 a *大于* b，那么 a 就应该排在 b *前面*'
bool compareDescending(const int& a, const int& b) {
    return a > b;
}

// --- '自定义规则 2' (C++11 Lambda - 更简洁) ---
// auto compareDescLambda = [](const int& a, const int& b) {
//     return a > b;
// };

int main() {
    vector<int> numbers = {12, 5, 13, 7, 2};
    printVector("原始：", numbers);

    // 3. '按下按钮'并'递上纸条'
    std::sort(numbers.begin(), numbers.end(), compareDescending);
    printVector("排序后 (降序): ", numbers);

    // (使用 Lambda 的方式)
    // std::sort(numbers.begin(), numbers.end(), [](int a, int b) { return a > b; });

    return 0;
}

(假设 printVector 已被包含)

'手把手'终端模拟：

PS C:\MyCode> g++ custom_sort.cpp -o custom_sort.exe -std=c++11
PS C:\MyCode> .\custom_sort.exe
原始： [ 12 5 13 7 2 ]
排序后 (降序): [ 13 12 7 5 2 ]

第三部分：'终极应用'——排序'自定义盒子' (struct)

std::sort 的真正威力在于排序自定义对象。

'噩梦'演示：

struct Person {
    string name;
    int age;
};

vector<Person> people = {{"Bob", 30}, {"Alice", 25}};

// std::sort(people.begin(), people.end()); // 👈 '编译大爆炸'！
// 编译器：'我不知道如何用 '<' 比较两个 Person！'

解决方案： 我们必须提供一个'自定义比较器'！

struct_sort.cpp

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

using namespace std;

// '蓝图'：自定义盒子
struct Person {
    string name;
    int age;
};

// '规则'：告诉 sort 如何比较两个 Person
// (按年龄从小到大)
bool compareByAge(const Person& a, const Person& b) {
    // '如果 a 的年龄 *小于* b 的年龄，那么 a 就应该排在 b *前面*'
    return a.age < b.age;
}

int main() {
    vector<Person> people = {{"Charlie", 30}, {"Alice", 25}, {"Bob", 35}};
    cout << "--- 原始列表 ---" << endl;
    for (const auto& p : people) {
        cout << " " << p.name << " (Age: " << p.age << ")" << endl;
    }

    // '按下按钮'并'递上纸条' (按年龄排序)
    std::sort(people.begin(), people.end(), compareByAge);

    cout << "\n--- 按年龄排序后 ---" << endl;
    for (const auto& p : people) {
        cout << " " << p.name << " (Age: " << p.age << ")" << endl;
    }

    return 0;
}

'手把手'终端模拟：

PS C:\MyCode> g++ struct_sort.cpp -o struct_sort.exe -std=c++11
PS C:\MyCode> .\struct_sort.exe
--- 原始列表 ---
 Charlie (Age: 30)
 Alice (Age: 25)
 Bob (Age: 35)
--- 按年龄排序后 ---
 Alice (Age: 25)
 Charlie (Age: 30)
 Bob (Age: 35)

第四部分：std::sort vs std::stable_sort

std::sort 还有一个'兄弟'叫 std::stable_sort（也在 <algorithm> 中）。

• 问题： 如果你有两个'相等'的元素（比如，两个 Person 年龄都是 30），排序后它们原来的'前后'顺序可能会被打乱。
• std::sort ('快，但不保证')：不保证保留'相等'元素的原始相对顺序。它优先追求最快的速度。
• std::stable_sort ('稳，稍慢')：保证保留'相等'元素的原始相对顺序。
  • 例子：{{"Charlie", 30}, {"Adam", 30}}
  • stable_sort 保证排序后 Adam 仍然在 Charlie 的前面（如果 Adam 原本就在前面，并且你只按年龄排）。

'黄金法则'：

• 如果你不在乎相等元素的相对顺序（大部分情况），使用 std::sort（它更快）。
• 如果你必须保持相等元素的原始顺序，使用 std::stable_sort（它会稍慢一点）。

第五部分：'X 光透视'——亲眼目睹'自定义规则'被调用

我们无法（也不需要）用调试器'步入' (F11) std::sort 内部，因为它是一个高度优化的、编译好的'黑盒'。 但是，我们可以'步入'它调用我们的'自定义规则'！

'X 光'实战（基于 struct_sort.cpp）

1. 设置断点：
   • 动作： 在 VS Code 中，把你的鼠标移动到 '规则'函数 compareByAge 内部的第 19 行（return a.age < b.age;）的行号左边。
   • 点击那个小 red dot，设置一个断点。
2. 启动'子指时间'（F5）：
   • 动作： 按下 F5 键。
   • 你会看到： 程序执行 main，创建 vector，打印'原始列表'。
   • 当程序执行到 std::sort(...) 这一行时，它会 **'跳进'你的 compareByAge 函数，'冻结'**在第 19 行！
3. 开启'X 光'（观察'裁判'工作）：
   • 动作： 仔细看那个'变量'(VARIABLES) 窗口。
   • 你会看到：
     • a: {name: "Alice", age: 25}
     • b: {name: "Charlie", age: 30}
   • 顿悟时刻：std::sort（'黑盒'）为了决定 'Alice' 和 'Charlie' 谁该排前面，它把这两个对象'递'给了你的'裁判' (compareByAge)！
   • 动作： 按下 F10 键（'Step Over'）。
   • 你会看到：a.age < b.age (即 25 < 30) 计算为 true。函数返回 true。sort 知道了 'Alice' 应该在 'Charlie' 前面。
4. 继续执行 (F5)。
5. 第二次'冻结' (在 compareByAge 内部)：
   • 动作： 按下 F5 键，程序会再次停在 compareByAge 断点处。
   • 观察'变量'窗口：
     • a: {name: "Bob", age: 35}
     • b: {name: "Charlie", age: 30}
   • 顿悟时刻：std::sort 现在正在比较 'Bob' 和 'Charlie'！
   • 动作： 按下 F10 键。
   • 你会看到：a.age < b.age (即 35 < 30) 计算为 false。函数返回 false。sort 知道了 'Bob' 应该在 'Charlie' 后面。
6. （继续按 F5，sort 会调用你的'裁判'很多次…）
   • 最终顿悟： 你亲眼见证了 std::sort 是如何利用你的'自定义规则'来驱动其内部（你看不见）的排序算法的。

动手试试！(终极挑战：你的'高级'排序)

现在，你来当一次'数据分析师'。

任务：

1. 复制本教程 struct_sort.cpp 的 Person 结构体和 main 函数框架。
2. 修改vector<Person> people，添加几个同龄人，比如：
   {{"Charlie", 30}, {"Alice", 25}, {"David", 30}, {"Bob", 35}}
3. **编写一个新的'自定义规则'**函数，名叫 compareByNameDescending。
4. 规则： 必须按姓名进行降序排序（Z -> A）。
5. 在 main 函数中，调用std::sort，但传入你这个新的 compareByNameDescending 规则。
6. 打印最终结果，验证姓名是否按 Z 到 A 排序。

sort_challenge.cpp (你的 TODO):

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

using namespace std;

struct Person {
    string name;
    int age;
};

// --- TODO 3: 编写 *新* 的'规则' (按姓名降序) ---
// bool compareByNameDescending(const Person& a, const Person& b) {
//     // 提示：'大于' (>) 意味着'排在前面'
//     // return a.name > b.name;
// }

int main() {
    // --- TODO 2: 使用新数据 (包含同龄人) ---
    vector<Person> people = {{"Charlie", 30}, {"Alice", 25}, {"David", 30}, {"Bob", 35}};
    cout << "--- 原始列表 ---" << endl;
    // (在此处添加 for 循环打印)

    // --- TODO 4 & 5: 调用 sort，使用 *新* 规则 ---
    // std::sort(people.begin(), people.end(), ...);

    cout << "\n--- 按姓名降序排序后 ---" << endl;

    // --- TODO 6: 打印结果 ---
    // (在此处添加 for 循环打印)

    return 0;
}

这个挑战让你亲手实践了 std::sort 最强大的功能：根据你提供的任意逻辑，对任意对象列表进行排序。完成它，你就掌握了 C++ STL 中最强大的工具之一！