如何使用STL sort函数按'd'参数排序数组并保留原索引

嘿，我来帮你搞定这个问题——用C++ STL的sort函数按指定的'd'字段排序数组，同时保留每个元素的原始索引其实很简单，核心就是把元素和它的初始位置绑定起来，或者直接排序索引数组而非原数组。下面给你两种实用的实现方案：

方案1：排序索引数组（不修改原数组） #

这种方法的好处是不会改动原数组的结构，我们只需要创建一个存储原索引的数组，然后根据原数组中对应元素的'd'值来排序这个索引数组。

代码示例 #

假设我们的元素是一个包含'd'字段的结构体：

struct Data {
    int d;
    // 你可以添加其他需要的字段
};

具体实现代码：

#include <vector>
#include <algorithm>
#include <iostream>

int main() {
    // 示例输入数组
    std::vector<Data> arr = {{5}, {2}, {8}, {3}};
    // 创建索引数组，存储每个元素的原始位置
    std::vector<int> indices(arr.size());
    // 初始化索引为0, 1, 2, ..., n-1
    for (int i = 0; i < arr.size(); ++i) {
        indices[i] = i;
    }

    // 用STL sort排序索引数组，自定义排序规则：比较对应元素的'd'值
    std::sort(indices.begin(), indices.end(), [&arr](int idx_a, int idx_b) {
        // 这里是升序排序，要降序的话改成 arr[idx_a].d > arr[idx_b].d
        return arr[idx_a].d < arr[idx_b].d;
    });

    // 输出排序后的结果（原索引 + 对应的'd'值）
    std::cout << "排序结果（原索引，d值）：\n";
    for (int idx : indices) {
        std::cout << "(" << idx << ", " << arr[idx].d << ")\n";
    }
    return 0;
}

逻辑解释 #

• 我们没有直接操作原数组，而是对索引数组进行排序，这样原数组的顺序完全保留，同时通过排序后的索引就能拿到按'd'排序后的元素顺序，还能追踪到每个元素最初的位置。
• 作为sort第三个参数的lambda表达式，是告诉排序函数如何比较两个索引：看它们在原数组中对应元素的'd'值大小。

方案2：打包元素与原索引后排序 #

如果允许创建新的数组，我们可以把每个元素和它的原索引打包成一个新的组合（比如pair或者自定义结构体），然后直接对这个组合数组排序。

代码示例 #

#include <vector>
#include <algorithm>
#include <iostream>
#include <utility> // 用于pair

struct Data {
    int d;
    // 其他字段...
};

int main() {
    std::vector<Data> arr = {{5}, {2}, {8}, {3}};
    // 创建一个数组，每个元素是（原索引，对应Data元素）的pair
    std::vector<std::pair<int, Data>> indexed_arr;
    for (int i = 0; i < arr.size(); ++i) {
        indexed_arr.emplace_back(i, arr[i]);
    }

    // 按pair中Data的'd'值排序
    std::sort(indexed_arr.begin(), indexed_arr.end(), [](const auto& elem_a, const auto& elem_b) {
        return elem_a.second.d < elem_b.second.d;
    });

    // 输出结果
    std::cout << "排序结果（原索引，d值）：\n";
    for (const auto& elem : indexed_arr) {
        std::cout << "(" << elem.first << ", " << elem.second.d << ")\n";
    }
    return 0;
}

逻辑解释 #

• 我们把原索引和对应的元素打包成pair<int, Data>，这样每个元素都自带自己的原始位置信息。
• 排序时直接比较pair中第二个元素（也就是原Data对象）的'd'值，排序完成后，每个pair的first就是原索引，second是对应的元素，完美保留了我们需要的信息。

输入输出示例 #

假设你的输入是：

5 2 8 3
0 1 2 3

运行上面的代码后，按'd'升序排序的输出会是：

排序结果（原索引，d值）：
(1, 2)
(3, 3)
(0, 5)
(2, 8)

如果需要降序排序，只需要把lambda表达式里的<改成>就行啦。

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