时间戳

首页 > 解决方案 > 根据某些标准对索引子集进行排序

c++ - 根据某些标准对索引子集进行排序

问题描述

考虑

是否有一种有效的方法（在 CPU 周期/缓存友好性/内存方面）根据 S(J) 对 J 的元素进行排序？

首选使用标准算法的 C++ 代码。

例子：

I     = [0, 1, 2, 3, 4]
S     = [10, 50, 40, 20, 30]
J     = [1, 3, 4]
S(J)  = [50, 20, 30]
J sorted according to S(J) = [3, 4, 1]

我考虑过使用 std::multimap 来获得“免费”的排序，但 std::multimap 背后的机制（分配等）似乎很昂贵。

使用 std::pair 绑定 J 和 S(J) 将允许使用 std::sort。缺点是需要额外的内存和额外的循环来获得最终排序的 J。

我的做法是在手写排序例程中使用 S(J) 作为标准同时对 J 和 S(J) 进行排序。然而，在 2019 年写一个排序函数似乎很尴尬。

这是一个聪明的方法吗？是否可以利用 n<=32 的事实？

标签： c++algorithmsortingstl

解决方案

我的做法是在手写排序例程中使用 S(J) 作为标准同时对 J 和 S(J) 进行排序。然而，在 2019 年写一个排序函数似乎很尴尬。

你在正确的轨道上，但你不需要编写自己的排序。您可以利用 lambda 来获得所需的自定义排序行为，同时仍std::sort用于为您对数组进行排序。您要做的是获取提供给 lambda 的值并将它们用作索引S并比较这些结果。那会给你这样的代码

int main() 
{
    int S[] = {10, 50, 40, 20, 30};
    int J[] = {1, 3, 4};
    std::sort(std::begin(J), std::end(J),[&S](auto lhs, auto rhs){ return S[lhs] < S[rhs]; });
    for (auto e : J)
    {
        std::cout << e << " ";
    }
}

哪个输出

3 4 1

推荐阅读