Search

Finding things in a collection has been discussed throughout this book, and the Rust standard library provides a few ways by default. These functions are attached to the Iterator<T> trait or slice types and work regardless of the actual type, provided that a function to compare two elements is furnished.

This can either be the Ord trait or a custom comparator function, such as the position() function on the Iterator<T>.

Linear search

The classic linear search is provided via position() (or rposition()) on the Iterator<T> trait, and it even utilizes other iterator functions that are implemented on the trait itself:

fn position<P>(&mut self, mut predicate: P) -> Option<usize> where
    Self: Sized,
    P: FnMut(Self::Item) -> bool,
{
    // The addition might panic on overflow
    self.try_fold(0, move |i, x| {
        if predicate(x) { LoopState::Break(i) }
        else { LoopState::Continue(i + 1) }
    }).break_value()
}

try_fold() is a short-circuit...