如何对存储成对数据的两个std::vector进行排序？

当需要保持两个vector元素的对应关系并按其中一个排序时，自定义迭代器确实容易踩std::sort的规则坑，以下两种是更简单可靠的标准实现方式：

方法1：合并为pair容器排序 #

把两个vector的对应元素打包成std::pair<int, int>，利用pair默认按first元素排序的特性，排序后再拆分回原vector：

#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec1 = {6, -3, 18, 0};
    std::vector<int> vec2 = {100, 2, 3, 4};

    // 合并成pair容器
    std::vector<std::pair<int, int>> pairs;
    pairs.reserve(vec1.size());
    for (size_t i = 0; i < vec1.size(); ++i) {
        pairs.emplace_back(vec1[i], vec2[i]);
    }

    // 按pair的first（即原vec1元素）排序
    std::sort(pairs.begin(), pairs.end());

    // 拆分回原vector
    for (size_t i = 0; i < pairs.size(); ++i) {
        vec1[i] = pairs[i].first;
        vec2[i] = pairs[i].second;
    }

    // 此时vec1: [-3, 0, 6, 18], vec2: [2, 4, 100, 3]
    return 0;
}

这种方法逻辑直观，完全符合std::sort的要求，不会出现迭代器相关的错误。

方法2：基于索引排序 #

创建一个存储索引的vector，按原vec1的元素值对索引排序，再根据排序后的索引重新构建vec1和vec2：

#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec1 = {6, -3, 18, 0};
    std::vector<int> vec2 = {100, 2, 3, 4};

    // 创建索引容器
    std::vector<size_t> indices(vec1.size());
    for (size_t i = 0; i < indices.size(); ++i) {
        indices[i] = i;
    }

    // 按vec1的元素值排序索引
    std::sort(indices.begin(), indices.end(),
              [&vec1](size_t a, size_t b) { return vec1[a] < vec1[b]; });

    // 根据排序后的索引重建vec1和vec2
    std::vector<int> sorted_vec1(vec1.size());
    std::vector<int> sorted_vec2(vec2.size());
    for (size_t i = 0; i < indices.size(); ++i) {
        sorted_vec1[i] = vec1[indices[i]];
        sorted_vec2[i] = vec2[indices[i]];
    }

    // 替换原vector（如果需要）
    vec1.swap(sorted_vec1);
    vec2.swap(sorted_vec2);

    // 此时vec1: [-3, 0, 6, 18], vec2: [2, 4, 100, 3]
    return 0;
}

这种方法的优势是不需要移动原始数据的配对，适合数据量较大或者不想改变原始数据存储结构的场景，同样完全符合标准库的规则。

为什么自定义迭代器容易出问题？ #

std::sort要求迭代器指向的对象必须是可移动构造、可移动赋值的，且迭代器的operator*必须返回指向有效对象的引用。如果自定义迭代器返回临时对象的引用，会导致悬垂引用；同时如果迭代器的行为不符合std::sort对随机访问迭代器的要求（比如不支持加减运算、距离计算），也会触发未定义行为。上面两种方法都完全规避了这些问题，是工业界常用的规范实现。

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