根据某些标准对索引进行排序

Question

考虑

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

是否有效率方式（就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的事实？

考虑前n个自然数的向量，I，I = [0，1，... n-1]，n <= 32。对于任何i = 0..n-1，另一个自然向量S，S [i] <= 2000，不一定是具有m个元素的I子集唯一，...

Answer 1

实际上，在排序时使用J在S中进行此操作非常简单。如果将J中的元素值用作S的索引，则可以使用其返回的值作为比较的排序对象。这将为您提供代码，例如