1/// An iterator that knows its exact length.
2///
3/// Many [`Iterator`]s don't know how many times they will iterate, but some do.
4/// If an iterator knows how many times it can iterate, providing access to
5/// that information can be useful. For example, if you want to iterate
6/// backwards, a good start is to know where the end is.
7///
8/// When implementing an `ExactSizeIterator`, you must also implement
9/// [`Iterator`]. When doing so, the implementation of [`Iterator::size_hint`]
10/// *must* return the exact size of the iterator.
11///
12/// The [`len`] method has a default implementation, so you usually shouldn't
13/// implement it. However, you may be able to provide a more performant
14/// implementation than the default, so overriding it in this case makes sense.
15///
16/// Note that this trait is a safe trait and as such does *not* and *cannot*
17/// guarantee that the returned length is correct. This means that `unsafe`
18/// code **must not** rely on the correctness of [`Iterator::size_hint`]. The
19/// unstable and unsafe [`TrustedLen`](super::marker::TrustedLen) trait gives
20/// this additional guarantee.
21///
22/// [`len`]: ExactSizeIterator::len
23///
24/// # When *shouldn't* an adapter be `ExactSizeIterator`?
25///
26/// If an adapter makes an iterator *longer*, then it's usually incorrect for
27/// that adapter to implement `ExactSizeIterator`. The inner exact-sized
28/// iterator might already be `usize::MAX`-long, and thus the length of the
29/// longer adapted iterator would no longer be exactly representable in `usize`.
30///
31/// This is why [`Chain<A, B>`](crate::iter::Chain) isn't `ExactSizeIterator`,
32/// even when `A` and `B` are both `ExactSizeIterator`.
33///
34/// # Examples
35///
36/// Basic usage:
37///
38/// ```
39/// // a finite range knows exactly how many times it will iterate
40/// let five = 0..5;
41///
42/// assert_eq!(5, five.len());
43/// ```
44///
45/// In the [module-level docs], we implemented an [`Iterator`], `Counter`.
46/// Let's implement `ExactSizeIterator` for it as well:
47///
48/// [module-level docs]: crate::iter
49///
50/// ```
51/// # struct Counter {
52/// # count: usize,
53/// # }
54/// # impl Counter {
55/// # fn new() -> Counter {
56/// # Counter { count: 0 }
57/// # }
58/// # }
59/// # impl Iterator for Counter {
60/// # type Item = usize;
61/// # fn next(&mut self) -> Option<Self::Item> {
62/// # self.count += 1;
63/// # if self.count < 6 {
64/// # Some(self.count)
65/// # } else {
66/// # None
67/// # }
68/// # }
69/// # }
70/// impl ExactSizeIterator for Counter {
71/// // We can easily calculate the remaining number of iterations.
72/// fn len(&self) -> usize {
73/// 5 - self.count
74/// }
75/// }
76///
77/// // And now we can use it!
78///
79/// let mut counter = Counter::new();
80///
81/// assert_eq!(5, counter.len());
82/// let _ = counter.next();
83/// assert_eq!(4, counter.len());
84/// ```
85#[stable(feature = "rust1", since = "1.0.0")]
86pub trait ExactSizeIterator: Iterator {
87 /// Returns the exact remaining length of the iterator.
88 ///
89 /// The implementation ensures that the iterator will return exactly `len()`
90 /// more times a [`Some(T)`] value, before returning [`None`].
91 /// This method has a default implementation, so you usually should not
92 /// implement it directly. However, if you can provide a more efficient
93 /// implementation, you can do so. See the [trait-level] docs for an
94 /// example.
95 ///
96 /// This function has the same safety guarantees as the
97 /// [`Iterator::size_hint`] function.
98 ///
99 /// [trait-level]: ExactSizeIterator
100 /// [`Some(T)`]: Some
101 ///
102 /// # Examples
103 ///
104 /// Basic usage:
105 ///
106 /// ```
107 /// // a finite range knows exactly how many times it will iterate
108 /// let mut range = 0..5;
109 ///
110 /// assert_eq!(5, range.len());
111 /// let _ = range.next();
112 /// assert_eq!(4, range.len());
113 /// ```
114 #[inline]
115 #[stable(feature = "rust1", since = "1.0.0")]
116 fn len(&self) -> usize {
117 let (lower, upper) = self.size_hint();
118 // Note: This assertion is overly defensive, but it checks the invariant
119 // guaranteed by the trait. If this trait were rust-internal,
120 // we could use debug_assert!; assert_eq! will check all Rust user
121 // implementations too.
122 assert_eq!(upper, Some(lower));
123 lower
124 }
125
126 /// Returns `true` if the iterator is empty.
127 ///
128 /// This method has a default implementation using
129 /// [`ExactSizeIterator::len()`], so you don't need to implement it yourself.
130 ///
131 /// # Examples
132 ///
133 /// Basic usage:
134 ///
135 /// ```
136 /// #![feature(exact_size_is_empty)]
137 ///
138 /// let mut one_element = std::iter::once(0);
139 /// assert!(!one_element.is_empty());
140 ///
141 /// assert_eq!(one_element.next(), Some(0));
142 /// assert!(one_element.is_empty());
143 ///
144 /// assert_eq!(one_element.next(), None);
145 /// ```
146 #[inline]
147 #[unstable(feature = "exact_size_is_empty", issue = "35428")]
148 fn is_empty(&self) -> bool {
149 self.len() == 0
150 }
151}
152
153#[stable(feature = "rust1", since = "1.0.0")]
154impl<I: ExactSizeIterator + ?Sized> ExactSizeIterator for &mut I {
155 fn len(&self) -> usize {
156 (**self).len()
157 }
158 fn is_empty(&self) -> bool {
159 (**self).is_empty()
160 }
161}
162