2026-09-25
merge_iter.rs
fn merge<T, A, B>(a: A, b: B) -> impl Iterator<Item = T>
where
T: Ord,
A: IntoIterator<Item = T>,
B: IntoIterator<Item = T>,
{
}
それぞれ昇順に値を返すaとb(どちらもIntoIterator)から、全ての値を昇順に返すイテレータを返すmergeを書いてください。値は必要になるまで取り出さず(無限のイテレータにも使えるように)、同じ値どうしはaの方を先に返します。片方が空なら、もう片方をそのまま返します。merge([1, 4, 9], [2, 4, 10]).collect::<Vec<_>>() → [1, 2, 4, 4, 9, 10]、merge(Vec::<i32>::new(), [3]).collect::<Vec<_>>() → [3]、merge((0..).step_by(2), (1..).step_by(2)).take(5).collect::<Vec<_>>() → [0, 1, 2, 3, 4]
Reference
fn merge<T, A, B>(a: A, b: B) -> impl Iterator<Item = T>
where
T: Ord,
A: IntoIterator<Item = T>,
B: IntoIterator<Item = T>,
{
let mut a = a.into_iter().peekable();
let mut b = b.into_iter().peekable();
std::iter::from_fn(move || match (a.peek(), b.peek()) {
(Some(x), Some(y)) if y < x => b.next(),
(Some(_), _) => a.next(),
(None, _) => b.next(),
})
}
併合では、両方の先頭を見比べてから小さい方だけを取り出したいので、取り出さずに先頭を覗けるPeekableにします。2つのPeekableはmoveクロージャが所有し、std::iter::from_fnがそのクロージャを「呼ばれるたびに次の値を返すイテレータ」にします。collectやtakeが値を求めたときに初めて1つずつ比較するので、無限の列でも止まりません。matchの腕は3つで足ります。両方に値がありbの方が真に小さいときだけbから取り、それ以外でaに値があればaから取ります(等しい値はaが先になり、併合が安定になります)。aが尽きていればb.next()で、両方尽きていればそれがNoneを返して終わります。peekが返す参照は腕のガードで使い終わるので、腕の中でnextを呼んでも借用は衝突しません。境界はT: Ordと、2つの入力が同じItem = Tを返すことだけです。Rust 2024では戻り値のimpl Iteratorが型引数をすべて自動で捕捉するので、+ use<...>などの注釈は要りません。これは参考実装であり、唯一の正解ではありません。2つのPeekableをフィールドに持つ構造体にIteratorを実装しても同じものが書けます。