Условная сортировка Vec в Rust
Допустим, я хочу отсортировать Vec элементов, не являющихся клонами, но только возможно (это упрощенный пример проблемы в моем коде).
Моя попытка будет примерно такой:
fn maybe_sort<T>(x: Vec<T>) -> Vec<T>
where
T: std::cmp::Ord,
{
// First, I need a copy of the vector - but only the vector, not the items inside
let mut copied = x.iter().collect::<Vec<_>>();
copied.sort();
// In my actual code the line below depends on the sorted vec
if rand::random() {
return copied.into_iter().map(|x| *x).collect::<Vec<_>>();
} else {
return x;
}
}
Увы, контролер заимствования недоволен. У меня есть общая ссылка на каждый элемент в Vec, и хотя я никогда не возвращаю 2 ссылки на один и тот же элемент, Rust не может этого сказать.
Есть ли способ сделать это без unsafe? (а если нет, то какой самый чистый способ сделать это с помощью unsafe.
почему бы просто не отсортировать x? ссылка на детскую площадку
Я добавил комментарий над строкой подбрасывания монеты, который, надеюсь, прояснит ситуацию — мне нужно сначала отсортировать, а затем решить, возвращать ее или нет.
@Acorn «только вектор, а не элементы внутри» - я имею в виду только то, что я не могу клонировать элементы внутри. Элементы не клонируются.
@xixixao По какой причине ты не можешь Clone? (например, ваш тип действительно такой «большой»?). Можно делать то, что вы хотите, и сейчас я пишу ответ, но для этого требуется двойная сортировка Vec.
Ответы 2
Вы можете .enumerate() сохранить исходный индекс значений. Вы можете отсортировать это на основе его значения T и решить, следует ли вернуть отсортированную версию или отменить сортировку, отсортировав по исходному индексу.
fn maybe_sort<T: Ord>(x: Vec<T>) -> Vec<T> {
let mut items: Vec<_> = x.into_iter().enumerate().collect();
items.sort_by(|(_, a), (_, b)| a.cmp(b));
if rand::random() {
// return items in current order
}
else {
// undo the sort
items.sort_by_key(|(index, _)| *index);
}
items.into_iter().map(|(_, value)| value).collect()
}
Спасибо, это полезно, потому что это действительно работает. Я чувствую, что должно быть решение, которое не связано с другим видом (и связанной с этим сложностью кода, особенно в моем коде, который сложнее, чем пример), но я собираюсь принять это сейчас.
Если T реализует Default, вы можете сделать это с одной сортировкой и без unsafe вот так:
fn maybe_sort<T: Ord + Default> (mut x: Vec<T>) -> Vec<T> {
let mut idx = (0..x.len()).collect::<Vec<_>>();
idx.sort_by_key (|&i| &x[i]);
if rand::random() {
return x;
} else {
let mut r = Vec::new();
r.resize_with (x.len(), Default::default);
for (i, v) in idx.into_iter().zip (x.drain(..)) {
r[i] = v;
}
return r;
}
}
Если T не реализует Default, то же самое можно сделать с MaybeUninit:
use std::mem::{self, MaybeUninit};
fn maybe_sort<T: Ord> (mut x: Vec<T>) -> Vec<T> {
let mut idx = (0..x.len()).collect::<Vec<_>>();
idx.sort_by_key (|&i| &x[i]);
if rand::random() {
return x;
} else {
let mut r = Vec::new();
r.resize_with (x.len(), || unsafe { MaybeUninit::uninit().assume_init() });
for (i, v) in idx.into_iter().zip (x.drain(..)) {
r[i] = MaybeUninit::new (v);
}
return unsafe { mem::transmute::<_, Vec<T>> (r) };
}
}
Наконец, вот безопасное решение, которое не требует T для реализации Default, но выделяет дополнительный буфер (теоретически есть способ переупорядочить индексы на месте, но я оставлю это читателю в качестве упражнения ☺):
fn maybe_sort<T: Ord> (mut x: Vec<T>) -> Vec<T> {
let mut idx = (0..x.len()).collect::<Vec<_>>();
idx.sort_by_key (|&i| &x[i]);
if rand::random() {
let mut rev = vec![0; x.len()];
for (i, &j) in idx.iter().enumerate() {
rev[j] = i;
}
for i in 0..x.len() {
while rev[i] != i {
let j = rev[i];
x.swap (j, i);
rev.swap (j, i);
}
}
}
x
}
Что вы подразумеваете под «только вектором, а не элементами внутри»? Кроме того, сортировка вектора не требует его копирования. В любом случае, вы можете делать с вектором все, что захотите, поскольку вы передаете и возвращаете его по значению.