std::list结构体按head字段依自定义规则排序的效率优化方法

现有实现的瓶颈说明 #

原实现每次比较两个Data元素时，都需要对规则列表执行2次线性遍历查找head对应的位置，配合std::list::sort本身O(n log n)的比较次数，整体时间复杂度达到O(n log n * m)（n为数据元素个数，m为规则列表长度），在数据量或规则长度较大时，性能会快速下降。

可落地的优化方案 #

核心思路是将规则的位置查找从排序阶段前置为一次性预处理，把每次比较的查找复杂度从O(m)降到O(1)，同时可以结合容器特性进一步提升排序本身的效率。

1. 预构建哈希映射表，消除排序阶段的线性查找 #

排序前仅需对规则列表做1次遍历，用std::unordered_map记录每个head值对应的优先级索引，后续比较时直接从哈希表取值即可：

• 逻辑和原实现完全对齐：如果规则列表存在重复head，保留第一次出现的位置作为优先级；如果Data的head不在规则列表中，统一分配一个比所有规则位置更靠后的索引（即规则列表的总长度），保证这类元素都排在规则指定元素的最后，不会改变原有的排序结果。
• 这一步的优化收益最大，直接把排序阶段的比较开销从O(m)降到O(1)。

2. 可选优化：改用vector存储数据执行排序 #

如果业务没有强制要求用std::list存储数据（比如不需要频繁在中间位置插入、删除节点），可以把数据迁移到std::vector中排序。vector的元素在内存中连续存储，配合标准库std::sort的高性能排序实现，缓存命中率远高于节点分散存储的std::list，整体排序性能会比list原生sort提升数倍。
即使最终必须输出list类型的结果，也可以先转成vector排序后，再把元素写回list，整体开销依然远高于直接用list sort。

优化后的完整代码 #

#include <iostream>
#include <list>
#include <vector>
#include <unordered_map>
#include <algorithm>

struct Data {
    std::string code;
    std::string text;
    std::string head;
};

int main() {
    Data data1{"0010", "it is text1", "head3"};
    Data data2{"0025", "it is text2", "head1"};
    Data data3{"0065", "it is text3", "head2"};
    Data data4{"0011", "it is text4", "head2"};
    
    std::list<Data> data = {data1, data2, data3, data4};
    std::list<std::string> rule = {"head1", "head2", "head3", "head4"};

    // 预构建规则优先级映射，仅需遍历一次rule
    std::unordered_map<std::string, size_t> rule_priority;
    size_t idx = 0;
    for (const auto& head : rule) {
        // 重复head只保留第一次出现的位置，和原逻辑完全对齐
        if (rule_priority.find(head) == rule_priority.end()) {
            rule_priority[head] = idx;
        }
        idx++;
    }
    const size_t default_priority = rule.size(); // 未匹配规则的元素统一排到最后

    // 优化后的list排序比较器，所有操作都是O(1)
    data.sort([&rule_priority, default_priority](const Data& first, const Data& second) {
        auto get_priority = [&](const Data& d) -> size_t {
            auto it = rule_priority.find(d.head);
            return it == rule_priority.end() ? default_priority : it->second;
        };
        return get_priority(first) < get_priority(second);
    });

    // 更高性能的vector版本（无强制list需求时可使用）：
    // std::vector<Data> data_vec(data.begin(), data.end());
    // std::sort(data_vec.begin(), data_vec.end(), [&rule_priority, default_priority](const Data& a, const Data& b) {
    //     auto get_priority = [&](const Data& d) -> size_t {
    //         auto it = rule_priority.find(d.head);
    //         return it == rule_priority.end() ? default_priority : it->second;
    //     };
    //     return get_priority(a) < get_priority(b);
    // });

    for (const auto& it : data)
        std::cout << it.code << "\t" << it.text << "\t" << it.head << "\n";
    
    return 0;
}

复杂度对比 #

• 原实现：O(n log n * m)，每次比较伴随2次长度为m的规则线性查找
• 优化后：O(m + n log n)，仅需1次长度为m的预遍历，后续比较全为O(1)操作

内容的提问来源于stack exchange，提问作者ivanovIAVDD