Сортировка подмножества индексов по некоторым критериям

Question

Рассмотрим

• вектор первых n натуральных чисел, I, I = [0, 1, ... n-1], n <= 32. </li>
• другой вектор натуральных чисел, S, S [i] <= 2000, для любого i = 0..n-1, не обязательно уникального </li>
• подмножества I с m элементами, J, 0 <= J [j] <n, для любого j = 0 ... m-1 </li>

Есть ли эффективный способ (с точки зрения циклов ЦП / удобства кэша / памяти)сортировать элементы J по S (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, чтобы получить сортировку для 'free', но механизм, стоящий за std :: multimap (размещения и т. д.), кажется дорогим.

Использование std :: pair для связывания J и S (J) позволило бы использовать std :: sort.Недостатком является то, что для получения окончательно отсортированной буквы J. требуется дополнительная память и дополнительный циклрутина сортировкиОднако написание функции сортировки в 2019 году кажется неловким.

Это умный способ сделать это?Можно ли использовать тот факт, что n <= 32? </p>

Answer 1

Мне нужно отсортировать J и S (J) одновременно, используя S (J) в качестве критерия в написанной от руки процедуре сортировки.Однако написание функции сортировки в 2019 году кажется неудобным.

Вы на правильном пути, но вам не нужно писать собственную сортировку.Вы можете использовать лямбду, чтобы получить желаемое поведение при сортировке, в то же время используя std::sort для сортировки массива.Что вы будете делать, это взять значения, предоставленные лямбда-выражению, и использовать их в качестве индексов для 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