На месте heapsort с использованием std :: collections :: BinaryHeap

Question

Я хотел бы создать на месте функцию heapsort в Rust. В стандартной библиотеке я нашел std::collections::BinaryHeap, который выглядел многообещающим. Я могу использовать его, чтобы создать функцию потребляя свой аргумент:

use std::collections::BinaryHeap; 

fn heapsort<T: Ord>(list: Vec<T>) -> Vec<T> { 
    let heap = BinaryHeap::from(list); 
    heap.into_sorted_vec() 
} 

Документы утверждают, что «преобразование вектора в двоичный куче может быть сделано на месте», но у меня возникают проблемы при создании, который работает по ссылке и может сделать это на месте (heapsort<T: Ord>(list: &mut Vec<T>)). Могу ли я достичь этого, используя только std::collections::BinaryHeap?

Answer 1

У меня возникают проблемы при создании, который работает на ссылке и может сделать это на месте

BinaryHeapis built on top of Vec. Когда вы создаете новую кучу из Vec, вы должны предоставить ей полную собственность. Затем он гарантирует, что вектор находится в хорошем состоянии, чтобы действовать как куча.

Поскольку BinaryHeap не построен поверх &mut Vec (что в большинстве случаев было бы ужасной эргономикой), вы не можете этого сделать.

Непонятно, почему вы не просто используете slice::sort на векторе.

состояние Docs, что «преобразование вектора в двоичном куче может быть сделано на месте»

Для уточнения, документация правильно - есть no extra memory allocation needed, что он находится в месте. Важным аспектом является то, что BinaryHeapвладеет его данными и не раскрывает все внутренние компоненты в мире.

То, о чем вы просите, это возможность позвонить rebuild по предоставленному пользователем вектору. Для меня это имеет сомнительную полезность, но вы всегда можете отправить RFC, чтобы разоблачить его.

Answer 2

Вы можете использовать mem::replace для «перемещения» что-то из-за &mut ссылки:

use std::collections::BinaryHeap; 
use std::mem; 

fn heapsort<T: Ord>(list: &mut Vec<T>) { 
    let tmp = mem::replace(list, Vec::new()); 
    let heap = BinaryHeap::from(tmp); 
    *list = heap.into_sorted_vec(); 
} 

Таким образом, в течение короткого времени *list делается равным пустым вектором. В этом случае это нормально, потому что создание и удаление пустых Vec s очень дешево.

IIRC есть даже ящик, который помогает заимствовать около *mutref по стоимости, без использования фиктивного значения на месте во время заимствования. Но я не могу найти его прямо сейчас. Это будет выглядеть примерно так:

fn heapsort<T: Ord>(list: &mut Vec<T>) { 
    borrow_by_value(list, |tmp| { 
     BinaryHeap::from(tmp).into_sorted_vec() 
    }); 
} 

где borrow_by_value использует некоторые небезопасного кода (возможно ptr::read), чтобы дать вам Vec по значению и поместит Vec назад *list с некоторыми более небезопасным кодом (вероятно ptr::write). Фактическая реализация может быть немного сложнее, чтобы каким-то образом защитить вас от паники. Я не знаю. А если нет, вы должны, вероятно, избегать его использования в конце концов.

Редактировать: Ящик, о котором я говорил, это take_mut. Существует даже RFC, чтобы добавить что-то вроде этого к std::mem.