2026-10-24
sorted.rs
trait Order {
fn before(&self, a: i32, b: i32) -> bool;
}
struct Desc;
impl Order for Desc {
fn before(&self, a: i32, b: i32) -> bool {
a > b
}
}
struct Sorted<O> {
items: Vec<i32>,
order: O,
}
impl<O: Order> Sorted<O> {
fn insert(&mut self, x: i32) {
}
}
Sorted<O> は、items を並び順 order に従って常に整列させておく列です。a を b より前に置くべきときに order.before(a, b) が true を返します。items が整列済みであるとして、x を順序が崩れない位置に挿入する insert を書いてください。items が空なら x だけの列になります。items の長さを n として、挿入位置は O(log n) 回の比較で見つけます。
入力例 1
let mut s = Sorted { items: vec![5, 3, 1], order: Desc };
s.insert(4);
s.items
出力例 1
[5, 4, 3, 1]
入力例 2
let mut s = Sorted { items: vec![5, 4, 3, 1], order: Desc };
s.insert(3);
s.items
出力例 2
[5, 4, 3, 3, 1]
入力例 3
let mut s = Sorted { items: Vec::new(), order: Desc };
s.insert(7);
s.items
出力例 3
[7]
Reference
impl<O: Order> Sorted<O> {
fn insert(&mut self, x: i32) {
let i = self.items.partition_point(|&y| !self.order.before(x, y));
self.items.insert(i, x);
}
}
partition_point は、述語が前半で true、後半で false に分かれているスライスについて、最初に false になる位置を二分探索で返します。整列済みの items では、!before(x, y) を満たす y(x を前に置かなくてよい要素)が先頭側にまとまり、x を前に置くべき要素が後ろ側にまとまります。境目が x を入れる位置で、x と等しい要素の直後にあたります。全要素が前半に入れば末尾に、items が空なら位置0に入ります。
Desc はフィールドを持たないユニット構造体で、大きさ0の型です。order フィールドとして持たせても Sorted<Desc> は Vec<i32> と同じ大きさのままで、並び順は値ではなく型 O として渡ります。self.order.before の呼び出し先はコンパイル時に決まり、Box<dyn Fn> で比較関数を持たせた場合と違い、関数の番地を持つことも、それを通して呼ぶこともありません。クロージャが借りるのは self.order と x だけで、partition_point が返った時点でその借用は終わるので、続く self.items.insert で items を可変で借りられます。
掲載したのは参考実装で、唯一の正解ではありません。binary_search_by で位置を探す書き方もありますが、等しい要素があるとそのどれかの位置を返すので、Ok と Err の両方から位置を取り出す必要があります。先頭から順に比べる書き方は O(n) 回の比較になり、条件を満たしません。