Namaran

Code daily. Without assist.

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) 回の比較になり、条件を満たしません。