Range::len()の時間計算量はO(1)か
概要
調査
code:rust
fn len(&self) -> usize {
let (lower, upper) = self.size_hint();
// Note: This assertion is overly defensive, but it checks the invariant
// guaranteed by the trait. If this trait were rust-internal,
// we could use debug_assert!; assert_eq! will check all Rust user
// implementations too.
assert_eq!(upper, Some(lower));
lower
}
0.. のように RangeFrom<T> 型は正確な長さが分からないため、ExactSizeIteratorを実装していない
len()関数のシグニチャの影響だと思うが、Range<u64>など長さがusizeを越える可能性がある場合も、ExactSizeIteratorを実装していない
Iterator の残りの長さを (usize /* 下限 */, Option<usize> /* 上限 */) で返す
基本的には下限と上限は一致する
code:rust
let mut iter = a.iter();
assert_eq!((3, Some(3)), iter.size_hint());
let _ = iter.next();
assert_eq!((2, Some(2)), iter.size_hint());
filter をかけた場合は下限と上限が一致しない
code:rust
// The even numbers in the range of zero to nine.
let iter = (0..10).filter(|x| x % 2 == 0);
// We might iterate from zero to ten times. Knowing that it's five
// exactly wouldn't be possible without executing filter().
assert_eq!((0, Some(10)), iter.size_hint());
// Let's add five more numbers with chain()
let iter = (0..10).filter(|x| x % 2 == 0).chain(15..20);
// now both bounds are increased by five
assert_eq!((5, Some(15)), iter.size_hint());
0.. のようにRangeの上限が存在しない場合は、(usize::MAX, None) が返る
Range型はIteratorを実装しており、その中で size_hint() も実装している
code:rust
fn size_hint(&self) -> (usize, Option<usize>) {
if self.start < self.end {
let hint = Step::steps_between(&self.start, &self.end);
(hint.unwrap_or(usize::MAX), hint)
} else {
(0, Some(0))
}
}
Step::steps_between() の戻り値を使用している
code:rust
fn steps_between(start: &Self, end: &Self) -> Option<usize> {
if *start <= *end {
// This relies on $u_narrower <= usize
Some((*end - *start) as usize)
} else {
None
}
}
サイズを$ O(1)で取得している
結論