Сортировка фрагмента на основе ключей в другом фрагменте без выделения

Question

Это не дубликат Как я могу совместно отсортировать два Vecs на основе значений в одном из Vecs? , потому что реализация контейнера permutation выделяет их.

Как Могу ли я отсортировать фрагмент на основе содержимого другого фрагмента без выделения?

slice1 = [
    AAA, BBB, CCC, DDD
]

slice2 = [
    12, -3, 6, 17
]

Результат:

[BBB, CCC, AAA, DDD]

Оба slice1 и slice2 не слишком велики (целые числа, максимум около 1 КиБ, обычно намного меньше), но такую ​​сортировку можно проводить очень часто. Сохранять slice2 не требуется, поэтому его можно реализовать путем сортировки slice2 и одновременного выполнения тех же операций с slice1, но любая реализация сортировки, которую я сделал, будет работать хуже, чем реализация стандартной библиотеки.

Answer 1

Стандартный алгоритм сортировки библиотеки доступен тремя способами:

• [T]::sort
• [T]::sort_by (принимает FnMut(&T, &T) -> Ordering в качестве оператора)
• [T]::sort_by_key (принимает FnMut(&T) -> K)

Последние два важны, когда вам нужно какое-либо нестандартное поведение сортировки. Но, как видите, вы получаете доступ только к элементам сортируемого фрагмента.

Ну, вы могли бы взять эту ссылку &T, преобразовать ее в необработанный указатель, вычтите из него основу среза и тада: у вас есть индекс! С помощью индекса вы можете заглянуть в другой массив. (edit: nope, см. Комментарии.) Однако это работает только до тех пор, пока алгоритм не поменяет местами первые два элемента. Вам также придется продублировать все свопы в целочисленном массиве. А стандартная библиотека просто не предлагает вам "получать уведомления" о свопах.

Насколько я понимаю: в вашем сценарии вы должны либо выделить, либо написать алгоритм сортировки самостоятельно.

В случае, если распределение не является жестким пределом, а просто соображением производительности: вы должны это измерить.

Один простой способ, который я мог придумать:

let mut vec = slice2.iter().zip(slice1).collect::<Vec<_>>();
vec.sort();

С этим вы получить [(-3, BBB), (6, CCC), (12, AAA), (17, DDD)] как результат. Конечно, вы можете легко выбрать только второй элемент из этого. Конечно, есть множество альтернативных решений.