排序轻量索引：保留原数据顺序，也写清失效规则

视图顺序不必等于存储顺序

Item 34 分析索引表而不是重写一个排序算法。这里把同一思路用于有名称与耗时的任务记录：原数组顺序代表提交次序，另一个索引序列代表从短到长的展示次序。排序只移动 size_t 值，不移动名称和完整记录，也不复制第二份任务列表。

本例选择位置索引而不是保存迭代器，接口因此明确限定为可随机访问的固定数组。没有为了可能出现的任意容器发明适配层；实际需求只要这一个稳定的数据集，简单表示就足够。扩展能力应来自真实使用场景，不是模板参数越多越好。

比较规则包含平局时的决定

比较器通过下标读取任务耗时。耗时不同时按小值优先，相同时按原始位置优先，形成确定的展示顺序。因此断言可以验证确切的索引序列，而不用依赖 std::sort 对等价元素的未承诺排列。若业务只要求保留输入中的同键顺序，也可以选 stable_sort。

比较器捕获源数组引用，这个引用只在同步排序调用期间使用，源数组始终存活且未修改。返回索引并不会复制记录，也不会获得数据所有权；它只是让调用方能够用第二种顺序解释同一批对象。

节省搬运，不等于免除维护

索引必须与源数据一起解释。对于 vector，单纯重新分配不会改变位置编号，但中间插入、擦除或整体重排会改变编号对应的对象；保存的迭代器还会额外受重新分配影响。即使记录位置不变，只更新一个耗时字段，也可能使旧展示顺序过期。

因此使用索引视图前应制定规则：源数据在视图期间冻结，或者修改后重建索引。当前完整程序选前者，用 const 固定数组将规则直接写进类型。书中关于可读性与重用标准库的建议在此体现为减少手写管理逻辑，而不是逐行移植二十年前的辅助类。

最低标准 C++11 · 完整程序 · 下载 .cpp

#include <algorithm>
#include <array>
#include <cassert>
#include <cstddef>
#include <numeric>
#include <string>

struct Job {
    std::string name;
    int duration;
};

int main() {
    const std::array<Job, 4> jobs{{
        {"parse", 7}, {"cache", 3}, {"index", 7}, {"send", 1}
    }};
    std::array<std::size_t, 4> order{};
    std::iota(order.begin(), order.end(), std::size_t{0});
    std::sort(order.begin(), order.end(), [&jobs](std::size_t a, std::size_t b) {
        if (jobs[a].duration != jobs[b].duration) {
            return jobs[a].duration < jobs[b].duration;
        }
        return a < b;
    });
    assert((order == std::array<std::size_t, 4>{{3, 1, 0, 2}}));
    assert(jobs[0].name == "parse");
    assert(jobs[order[0]].name == "send");
    assert(jobs[order[2]].name == "parse");
}

在本地编译

g++ -std=c++11 -Wall -Wextra -Wpedantic -pthread books-exceptional-cpp-style.cpp -o example && ./example

预期结果

预期：正常退出、无输出；所有 assert 通过。

CHECK YOUR UNDERSTANDING

合上答案，试着解释。

改成耗时从大到小，同耗时仍保持原始位置优先，应改哪一处？

继续查证

• Exceptional C++ Style Item 34, pp.246–257
• C++ draft [alg.sorting] — strict weak ordering

标准草案链接会随工作草案更新；本文版本标记对应示例最低要求，不表示草案中的所有新规则都适用于旧标准。