ソートされたベクトルに要素を挿入する最も効率的な方法は何ですか？

Question

私はソート済みv: Vec<EventHandler<T>>を持っていて、ソートしたまま要素を挿入したいと思います。そうする最も効率的な方法は何ですか？錆はそれを行うための組み込みの方法を持っていないようです。

ので、ソート作品は、挿入およびソートすることは非効率的になるかの

struct EventHandler<T: Event + ?Sized> { 
    priority: i32, 
    f: fn(&mut T), 
} 

、O(n log n) time complexity and 2*n allocation costで次のように

EventHandler<T>です。

Answer 1

タスクは2つのステップで構成されています。あなたは、ベクター内の重複する要素を許可するため、既存の要素を挿入したいしたい場合は、

match v.binary_search(&new_elem) { 
    Ok(pos) => {} // element already in vector @ `pos` 
    Err(pos) => v.insert(pos, new_elem), 
} 

：binary_searchで挿入位置を見つけ、Vec::insert()を挿入しますそれがさらに短く書くことができます。

let pos = v.binary_search(&new_elem).unwrap_or_else(|e| e); 
v.insert(pos, new_elem); 

---

しかしを：可能これは実行時の複雑さがO（n）であることを示しています。中央に挿入するには、挿入位置の右にあるすべての要素を右に移動する必要があります。

だから、はでサイズが小さくないベクトルにいくつかの要素を挿入する必要がありません。特に、は、この挿入ソートアルゴリズムがO（n²）で実行されるため、このメソッドを使用してベクトルをソートするべきではありません。

BinaryHeapは、このような状況では、より良い選択かもしれません。各インサート（push）は、O（n）ではなくO（log n）というランタイムの複雑さを持ちます。あなたが望むならば、それをとinto_sorted_vec()とソートしたものに変換することもできます。ヒープを変換せずに引き続き使用することもできます。