如何按指定键序列对C++结构体向量进行排序？

已知输入的std::vector<Foo>包含预定义键序列中的所有键，要按指定键顺序排序输出，不用纠结std::sort的比较函数，有两种更优方案：

方案一：构建键值映射直接生成有序结果（推荐，O(n)时间复杂度） #

先把无序的Foo集合转成键到Foo的哈希映射，再按预定义键序列依次取出对应元素，直接得到有序容器。这种方法比排序效率更高，逻辑也更简单。

代码示例：

#include <unordered_map>
#include <vector>
#include <string>

struct Foo
{
    std::string key;
    int value;
};

int main()
{
    // 示例无序数据
    std::vector<Foo> unsortedFoos = {
        {"thenThisOne", 2},
        {"andThenThatOne", 3},
        {"thisMustBeFirst", 1}
    };
    // 预定义键序列
    const std::vector<std::string> keySequence = {"thisMustBeFirst", "thenThisOne", "andThenThatOne"};

    // 1. 将无序Foo转换为键值映射
    std::unordered_map<std::string, Foo> fooMap;
    for (const auto& foo : unsortedFoos) {
        fooMap[foo.key] = foo;
    }

    // 2. 按预定义序列生成有序vector（预分配空间避免扩容开销）
    std::vector<Foo> sortedFoos;
    sortedFoos.reserve(keySequence.size());
    for (const auto& key : keySequence) {
        sortedFoos.push_back(fooMap[key]);
    }

    // sortedFoos即为按要求排序后的结果
    return 0;
}

方案二：基于优先级映射使用std::sort（原地排序场景） #

如果必须原地修改原容器，可先构建键到序列索引的映射，再用这个映射作为比较依据实现排序。

代码示例：

#include <algorithm>
#include <unordered_map>
#include <vector>
#include <string>

struct Foo
{
    std::string key;
    int value;
};

int main()
{
    std::vector<Foo> foos = {
        {"thenThisOne", 2},
        {"andThenThatOne", 3},
        {"thisMustBeFirst", 1}
    };
    const std::vector<std::string> keySequence = {"thisMustBeFirst", "thenThisOne", "andThenThatOne"};

    // 构建键到序列索引的映射，索引越小优先级越高
    std::unordered_map<std::string, size_t> keyPriority;
    for (size_t i = 0; i < keySequence.size(); ++i) {
        keyPriority[keySequence[i]] = i;
    }

    // 用lambda表达式作为比较函数，按优先级排序
    std::sort(foos.begin(), foos.end(), [&keyPriority](const Foo& a, const Foo& b) {
        return keyPriority[a.key] < keyPriority[b.key];
    });

    // 此时foos已按指定序列排序完成
    return 0;
}

方案对比 #

• 方案一：时间复杂度O(n)，空间复杂度O(n)，适合不需要保留原容器、追求最高效率的场景。
• 方案二：时间复杂度O(n log n)，空间复杂度O(k)（k为键序列长度），适合必须原地排序的场景。

内容的提问来源于stack exchange，提问作者lo-asys