STL容器实战：从基础到高级的排序问题解析

1. 理解STL容器的排序机制

STL容器作为C++标准库的核心组件，提供了多种高效的数据结构和算法实现。其中排序功能是日常开发中最常用的操作之一。理解不同容器的排序特性，能够帮助我们针对具体场景选择最优解决方案。

vector的排序特性：

• 连续内存布局，支持随机访问
• 默认使用快速排序算法（std::sort）
• 时间复杂度为O(N log N)
• 支持自定义比较函数

vector<int> nums = {3,1,4,1,5,9};
sort(nums.begin(), nums.end());  // 默认升序
sort(nums.begin(), nums.end(), greater<int>());  // 降序

map的排序特性：

• 基于红黑树实现，元素自动按键排序
• 插入时即保持有序状态
• 键值不可修改（const Key）
• 查找时间复杂度O(log N)

pair在排序中的应用：

• 将两个数据成员绑定为一个单元
• first成员默认作为主排序键
• 无需自定义比较函数即可实现多级排序

2. 基础排序实战：vector与pair的组合应用

2.1 单字段排序

最简单的排序场景是对单一数据类型进行排序：

vector<string> names = {"Alice", "Bob", "Charlie"};
sort(names.begin(), names.end());  // 字典序排序

2.2 多字段排序

使用pair实现多级排序时，STL已经内置了比较逻辑：

比较规则	说明
先比较first	如果first不等，按first排序
再比较second	如果first相等，按second排序

vector<pair<int, string>> people = {
    {25, "Alice"}, 
    {20, "Bob"}, 
    {25, "Charlie"}
};
sort(people.begin(), people.end());  // 自动按年龄和姓名排序

2.3 自定义排序规则

当默认排序不满足需求时，可以自定义比较函数：

bool customCompare(const pair<int, string>& a, const pair<int, string>& b) {
    if(a.first != b.first) 
        return a.first > b.first;  // 年龄降序
    return a.second < b.second;    // 姓名升序
}
sort(people.begin(), people.end(), customCompare);

3. 进阶排序技术：map的特殊排序场景

3.1 map按值排序的挑战

map本身按键排序，但实际业务中常需要按值排序。解决方案是将map转换为vector再排序：

map<string, int> wordCount = {{"apple",5}, {"banana",2}, {"cherry",8}};
vector<pair<string, int>> vec(wordCount.begin(), wordCount.end());

sort(vec.begin(), vec.end(), 
    [](const auto& a, const auto& b) { 
        return a.second > b.second; 
    });

3.2 保留插入顺序的排序

使用vector保存插入顺序，同时用map快速查找：

vector<string> insertionOrder;
map<string, int> dataMap;

void addItem(const string& key, int value) {
    if(dataMap.find(key) == dataMap.end()) {
        insertionOrder.push_back(key);
    }
    dataMap[key] = value;
}

3.3 多级map排序

对于嵌套map结构，需要逐层处理：

map<int, map<string, int>> multiMap;
// 填充数据...

// 对第二层map按值排序
for(auto& outer : multiMap) {
    vector<pair<string, int>> temp(outer.second.begin(), outer.second.end());
    sort(temp.begin(), temp.end(), 
        [](const auto& a, const auto& b) { return a.second > b.second; });
    
    outer.second.clear();
    for(const auto& item : temp) {
        outer.second.insert(item);
    }
}

4. 性能优化与特殊场景处理

4.1 排序算法选择

STL提供了多种排序算法，针对不同场景选择最优解：

算法	特点	适用场景
sort	快速排序实现，不稳定	通用排序
stable_sort	归并排序实现，稳定	需要保持相等元素顺序
partial_sort	部分排序	只关心前N个元素
nth_element	快速选择	找第N大元素

vector<int> bigData(1000000);
// 只需要前100个最小元素
partial_sort(bigData.begin(), bigData.begin()+100, bigData.end());

4.2 大对象排序优化

对于大型对象，避免拷贝提升性能：

vector<LargeObject> objects;
// 使用指针排序避免拷贝
sort(objects.begin(), objects.end(), 
    [](const LargeObject& a, const LargeObject& b) {
        return a.key < b.key;
    });

4.3 自定义对象排序

为自定义类实现比较运算符：

struct Person {
    string name;
    int age;
    
    bool operator<(const Person& other) const {
        return age < other.age;
    }
};

vector<Person> people;
sort(people.begin(), people.end());  // 使用重载的<运算符

5. 实战案例解析

5.1 学生成绩排名系统

struct Student {
    string name;
    int score;
    string classId;
};

vector<Student> students;
// 按班级分组后按成绩降序排序
map<string, vector<Student>> byClass;
for(const auto& s : students) {
    byClass[s.classId].push_back(s);
}

for(auto& [classId, classStudents] : byClass) {
    sort(classStudents.begin(), classStudents.end(),
        [](const Student& a, const Student& b) {
            return a.score > b.score;
        });
    
    cout << "Class " << classId << " ranking:\n";
    for(size_t i = 0; i < classStudents.size(); ++i) {
        cout << i+1 << ". " << classStudents[i].name 
             << ": " << classStudents[i].score << "\n";
    }
}

5.2 股票交易数据分析

map<string, vector<pair<time_t, double>>> stockHistory;

// 对每支股票按时间排序
for(auto& [stock, records] : stockHistory) {
    sort(records.begin(), records.end(),
        [](const auto& a, const auto& b) {
            return a.first < b.first;  // 按时间戳升序
        });
    
    // 计算日收益率
    vector<double> returns;
    for(size_t i = 1; i < records.size(); ++i) {
        double ret = (records[i].second - records[i-1].second) / records[i-1].second;
        returns.push_back(ret);
    }
}

5.3 社交网络好友推荐

map<string, set<string>> userFriends;
map<string, int> commonFriends;

// 计算共同好友数
for(const auto& [user, friends] : userFriends) {
    for(const auto& friendName : friends) {
        for(const auto& potentialFriend : userFriends[friendName]) {
            if(potentialFriend != user && 
               !friends.count(potentialFriend)) {
                commonFriends[potentialFriend]++;
            }
        }
    }
}

// 按共同好友数排序推荐
vector<pair<string, int>> recommendations(commonFriends.begin(), commonFriends.end());
sort(recommendations.begin(), recommendations.end(),
    [](const auto& a, const auto& b) {
        return a.second > b.second;
    });