2026-09-10
sorted.rs
pub struct Sorted<T>(Vec<T>);
impl<T: Ord> Sorted<T> {
pub fn new(mut v: Vec<T>) -> Self {
}
}
Sorted<T>は、中の要素が常に昇順に並んでいることを保証する型です。newと、Sorted<T>を読み取り用のスライスとして使えるようにする実装を書いてください。&[T]を受け取る関数に&sをそのまま渡せ、lenやbinary_searchのようなスライスのメソッドをsに直接呼べるようにします。ただし、外から要素を書き換えて並びを崩すことはできないようにします。Sorted::new(vec![3, 1, 2])でs.first() → Some(&1)、s.binary_search(&3) → Ok(2)、空のVecから作るとs.is_empty() → true
Reference
use std::ops::Deref;
impl<T: Ord> Sorted<T> {
pub fn new(mut v: Vec<T>) -> Self {
v.sort();
Sorted(v)
}
}
impl<T> Deref for Sorted<T> {
type Target = [T];
fn deref(&self) -> &[T] {
&self.0
}
}
Deref<Target = [T]>を実装すると、&Sorted<T>は関数の引数などで&[T]に型強制されます。メソッド呼び出しでもs.len()が(*s).len()、つまりスライスのlenとして解決されるので、スライスのメソッドを1つずつ転送する必要はありません。
並びを守るために、DerefMutは実装しません。Derefが渡すのは&[T]だけなので、s[0] = 9やs.reverse()のように&mut [T]が要る操作はコンパイルが通りません。フィールドをpubにしないのも同じ理由です。TargetをVec<T>ではなく[T]にしたのは、中身がVecであることを外に見せないためで、Vec<T>にするとcapacityのようなVecだけのメソッドまで公開の約束に入ります。
2つのimplで境界が違うのも意図したものです。並べ替えにはT: Ordが要りますが、借りて見せるだけのDerefには要らないので、impl<T>にしています。これは参考実装であり、唯一の正解ではありません1。
Derefはスマートポインタのためのトレイトなので、新しい型からメソッドを借りる目的では使わない方がよい、という意見もあります。その立場ならAsRef<[T]>やas_sliceのようなメソッドを用意します。型強制は起きなくなりますが、スライスとして見せていることが呼び出し側のコードに表れます。