我有一个排序的v: Vec<EventHandler<T>>
,我想在保持排序的同时向其中插入一个元素。最有效的方法是什么?Rust似乎没有内置的方法
EventHandler<T>
如下:
struct EventHandler<T: Event + ?Sized> {
priority: i32,
f: fn(&mut T),
}
由于排序的工作方式,插入和排序将是低效的,具有O(n log n)
的时间复杂性和2*n
的分配成本。
任务包括两个步骤:用binary_search
查找插入位置和用Vec::insert()
:插入
match v.binary_search(&new_elem) {
Ok(pos) => {} // element already in vector @ `pos`
Err(pos) => v.insert(pos, new_elem),
}
如果你想在你的向量中允许重复的元素,从而想插入已经存在的元素,你可以写得更短:
let pos = v.binary_search(&new_elem).unwrap_or_else(|e| e);
v.insert(pos, new_elem);
但是:请注意,这具有O(n)的运行时复杂性。要插入到中间,矢量必须将插入位置右侧的每个元素向右移动一个。
因此,不应该使用它在一个大小不小的向量中插入多个元素。特别是,不应该使用此方法对向量进行排序,因为此插入排序算法在O(n²)中运行。
在这种情况下,BinaryHeap
可能是更好的选择。每个插入(push
)的运行时复杂度仅为O(logn),而不是O(n)。如果您愿意,您甚至可以使用into_sorted_vec()
将其转换为排序的Vec
。您也可以继续使用堆而不是转换它。