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

Question

考虑

• 前 n 个自然数的 vector ，I, I=[0, 1, ...n-1], n<=32。
• 另一个自然 vector ，S，S[i]<=2000，对于任何 i=0..n-1，不一定是唯一的
• I 的一个子集，有 m 个元素，J，0 <= J[j] < n，对于任何 j=0...m-1

是否有一种有效的方式(在 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 绑定(bind) J 和 S(J) 将允许使用 std::sort。缺点是需要额外的内存和额外的循环才能得到最终排序的 J。

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

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

Answer 1

My take is to sort both J and S(J) simultaneously using S(J) as a criteria in a hand written sort routine. However, writing a sort function in 2019 seems awkward.

您走在正确的轨道上，但您不需要编写自己的排序。您可以利用 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