Function nekolib::algo::minmax_by_key

pub fn minmax_by_key<T, K, U>(buf: &[T], key: K) -> Option<(&T, &T)>where
    K: FnMut(&T) -> U,
    U: Ord,

キー key におけるスライスの最小値および最大値を求める。

該当する要素が複数個あった場合、最小値は最左のもの、最大値は最右のものが選ばれる。 スライスが空の場合は None を返す。

Complexity

minmax_by における compare の呼び出し回数と同じだけ、要素間の比較を行う。 また、key の呼び出しをその $2$ 倍の回数だけ行う。

Implementation notes

実装を minmax_by に丸投げしているので key を $3n$ 回程度呼び出しうるが、 適切に実装することで $n$ 回に抑えられるはず。

key のコストが大きい場合は予め別の配列を作る方がよさそう。

Notes

詳細については minmax_by を参照。

Examples

use nekolib::algo::minmax_by_key;

let buf: Vec<_> =
    vec![3, 5, 0, 1, 2, 0, 5].into_iter().enumerate().collect();
assert_eq!(minmax_by_key(&buf, |&(_, x)| x), Some((&(2, 0), &(6, 5))));

let buf: Vec<i32> = vec![];
assert_eq!(minmax_by_key(&buf, |&x| x), None);