1 //! Composable external iteration.
3 //! If you've found yourself with a collection of some kind, and needed to
4 //! perform an operation on the elements of said collection, you'll quickly run
5 //! into 'iterators'. Iterators are heavily used in idiomatic Rust code, so
6 //! it's worth becoming familiar with them.
8 //! Before explaining more, let's talk about how this module is structured:
12 //! This module is largely organized by type:
14 //! * [Traits] are the core portion: these traits define what kind of iterators
15 //! exist and what you can do with them. The methods of these traits are worth
16 //! putting some extra study time into.
17 //! * [Functions] provide some helpful ways to create some basic iterators.
18 //! * [Structs] are often the return types of the various methods on this
19 //! module's traits. You'll usually want to look at the method that creates
20 //! the `struct`, rather than the `struct` itself. For more detail about why,
21 //! see '[Implementing Iterator](#implementing-iterator)'.
24 //! [Functions]: #functions
25 //! [Structs]: #structs
27 //! That's it! Let's dig into iterators.
31 //! The heart and soul of this module is the [`Iterator`] trait. The core of
32 //! [`Iterator`] looks like this:
37 //! fn next(&mut self) -> Option<Self::Item>;
41 //! An iterator has a method, [`next`], which when called, returns an
42 //! [`Option`]`<Item>`. [`next`] will return `Some(Item)` as long as there
43 //! are elements, and once they've all been exhausted, will return `None` to
44 //! indicate that iteration is finished. Individual iterators may choose to
45 //! resume iteration, and so calling [`next`] again may or may not eventually
46 //! start returning `Some(Item)` again at some point.
48 //! [`Iterator`]'s full definition includes a number of other methods as well,
49 //! but they are default methods, built on top of [`next`], and so you get
52 //! Iterators are also composable, and it's common to chain them together to do
53 //! more complex forms of processing. See the [Adapters](#adapters) section
54 //! below for more details.
56 //! [`Iterator`]: trait.Iterator.html
57 //! [`next`]: trait.Iterator.html#tymethod.next
58 //! [`Option`]: ../../std/option/enum.Option.html
60 //! # The three forms of iteration
62 //! There are three common methods which can create iterators from a collection:
64 //! * `iter()`, which iterates over `&T`.
65 //! * `iter_mut()`, which iterates over `&mut T`.
66 //! * `into_iter()`, which iterates over `T`.
68 //! Various things in the standard library may implement one or more of the
69 //! three, where appropriate.
71 //! # Implementing Iterator
73 //! Creating an iterator of your own involves two steps: creating a `struct` to
74 //! hold the iterator's state, and then `impl`ementing [`Iterator`] for that
75 //! `struct`. This is why there are so many `struct`s in this module: there is
76 //! one for each iterator and iterator adapter.
78 //! Let's make an iterator named `Counter` which counts from `1` to `5`:
81 //! // First, the struct:
83 //! /// An iterator which counts from one to five
88 //! // we want our count to start at one, so let's add a new() method to help.
89 //! // This isn't strictly necessary, but is convenient. Note that we start
90 //! // `count` at zero, we'll see why in `next()`'s implementation below.
92 //! fn new() -> Counter {
93 //! Counter { count: 0 }
97 //! // Then, we implement `Iterator` for our `Counter`:
99 //! impl Iterator for Counter {
100 //! // we will be counting with usize
101 //! type Item = usize;
103 //! // next() is the only required method
104 //! fn next(&mut self) -> Option<Self::Item> {
105 //! // Increment our count. This is why we started at zero.
108 //! // Check to see if we've finished counting or not.
109 //! if self.count < 6 {
117 //! // And now we can use it!
119 //! let mut counter = Counter::new();
121 //! let x = counter.next().unwrap();
122 //! println!("{}", x);
124 //! let x = counter.next().unwrap();
125 //! println!("{}", x);
127 //! let x = counter.next().unwrap();
128 //! println!("{}", x);
130 //! let x = counter.next().unwrap();
131 //! println!("{}", x);
133 //! let x = counter.next().unwrap();
134 //! println!("{}", x);
137 //! This will print `1` through `5`, each on their own line.
139 //! Calling `next()` this way gets repetitive. Rust has a construct which can
140 //! call `next()` on your iterator, until it reaches `None`. Let's go over that
143 //! Also note that `Iterator` provides a default implementation of methods such as `nth` and `fold`
144 //! which call `next` internally. However, it is also possible to write a custom implementation of
145 //! methods like `nth` and `fold` if an iterator can compute them more efficiently without calling
148 //! # for Loops and IntoIterator
150 //! Rust's `for` loop syntax is actually sugar for iterators. Here's a basic
151 //! example of `for`:
154 //! let values = vec![1, 2, 3, 4, 5];
156 //! for x in values {
157 //! println!("{}", x);
161 //! This will print the numbers one through five, each on their own line. But
162 //! you'll notice something here: we never called anything on our vector to
163 //! produce an iterator. What gives?
165 //! There's a trait in the standard library for converting something into an
166 //! iterator: [`IntoIterator`]. This trait has one method, [`into_iter`],
167 //! which converts the thing implementing [`IntoIterator`] into an iterator.
168 //! Let's take a look at that `for` loop again, and what the compiler converts
171 //! [`IntoIterator`]: trait.IntoIterator.html
172 //! [`into_iter`]: trait.IntoIterator.html#tymethod.into_iter
175 //! let values = vec![1, 2, 3, 4, 5];
177 //! for x in values {
178 //! println!("{}", x);
182 //! Rust de-sugars this into:
185 //! let values = vec![1, 2, 3, 4, 5];
187 //! let result = match IntoIterator::into_iter(values) {
188 //! mut iter => loop {
190 //! match iter.next() {
191 //! Some(val) => next = val,
195 //! let () = { println!("{}", x); };
202 //! First, we call `into_iter()` on the value. Then, we match on the iterator
203 //! that returns, calling [`next`] over and over until we see a `None`. At
204 //! that point, we `break` out of the loop, and we're done iterating.
206 //! There's one more subtle bit here: the standard library contains an
207 //! interesting implementation of [`IntoIterator`]:
209 //! ```ignore (only-for-syntax-highlight)
210 //! impl<I: Iterator> IntoIterator for I
213 //! In other words, all [`Iterator`]s implement [`IntoIterator`], by just
214 //! returning themselves. This means two things:
216 //! 1. If you're writing an [`Iterator`], you can use it with a `for` loop.
217 //! 2. If you're creating a collection, implementing [`IntoIterator`] for it
218 //! will allow your collection to be used with the `for` loop.
222 //! Functions which take an [`Iterator`] and return another [`Iterator`] are
223 //! often called 'iterator adapters', as they're a form of the 'adapter
226 //! Common iterator adapters include [`map`], [`take`], and [`filter`].
227 //! For more, see their documentation.
229 //! [`map`]: trait.Iterator.html#method.map
230 //! [`take`]: trait.Iterator.html#method.take
231 //! [`filter`]: trait.Iterator.html#method.filter
235 //! Iterators (and iterator [adapters](#adapters)) are *lazy*. This means that
236 //! just creating an iterator doesn't _do_ a whole lot. Nothing really happens
237 //! until you call [`next`]. This is sometimes a source of confusion when
238 //! creating an iterator solely for its side effects. For example, the [`map`]
239 //! method calls a closure on each element it iterates over:
242 //! # #![allow(unused_must_use)]
243 //! let v = vec![1, 2, 3, 4, 5];
244 //! v.iter().map(|x| println!("{}", x));
247 //! This will not print any values, as we only created an iterator, rather than
248 //! using it. The compiler will warn us about this kind of behavior:
251 //! warning: unused result that must be used: iterators are lazy and
252 //! do nothing unless consumed
255 //! The idiomatic way to write a [`map`] for its side effects is to use a
256 //! `for` loop instead:
259 //! let v = vec![1, 2, 3, 4, 5];
262 //! println!("{}", x);
266 //! [`map`]: trait.Iterator.html#method.map
268 //! The two most common ways to evaluate an iterator are to use a `for` loop
269 //! like this, or using the [`collect`] method to produce a new collection.
271 //! [`collect`]: trait.Iterator.html#method.collect
275 //! Iterators do not have to be finite. As an example, an open-ended range is
276 //! an infinite iterator:
279 //! let numbers = 0..;
282 //! It is common to use the [`take`] iterator adapter to turn an infinite
283 //! iterator into a finite one:
286 //! let numbers = 0..;
287 //! let five_numbers = numbers.take(5);
289 //! for number in five_numbers {
290 //! println!("{}", number);
294 //! This will print the numbers `0` through `4`, each on their own line.
296 //! Bear in mind that methods on infinite iterators, even those for which a
297 //! result can be determined mathematically in finite time, may not terminate.
298 //! Specifically, methods such as [`min`], which in the general case require
299 //! traversing every element in the iterator, are likely not to return
300 //! successfully for any infinite iterators.
303 //! let ones = std::iter::repeat(1);
304 //! let least = ones.min().unwrap(); // Oh no! An infinite loop!
305 //! // `ones.min()` causes an infinite loop, so we won't reach this point!
306 //! println!("The smallest number one is {}.", least);
309 //! [`take`]: trait.Iterator.html#method.take
310 //! [`min`]: trait.Iterator.html#method.min
312 #![stable(feature = "rust1", since = "1.0.0")]
316 #[stable(feature = "rust1", since = "1.0.0")]
317 pub use self::traits::Iterator;
319 #[unstable(feature = "step_trait",
320 reason = "likely to be replaced by finer-grained traits",
322 pub use self::range::Step;
324 #[stable(feature = "rust1", since = "1.0.0")]
325 pub use self::sources::{Repeat, repeat};
326 #[stable(feature = "iterator_repeat_with", since = "1.28.0")]
327 pub use self::sources::{RepeatWith, repeat_with};
328 #[stable(feature = "iter_empty", since = "1.2.0")]
329 pub use self::sources::{Empty, empty};
330 #[stable(feature = "iter_once", since = "1.2.0")]
331 pub use self::sources::{Once, once};
332 #[unstable(feature = "iter_once_with", issue = "57581")]
333 pub use self::sources::{OnceWith, once_with};
334 #[stable(feature = "iter_from_fn", since = "1.34.0")]
335 pub use self::sources::{FromFn, from_fn};
336 #[stable(feature = "iter_successors", since = "1.34.0")]
337 pub use self::sources::{Successors, successors};
339 #[stable(feature = "rust1", since = "1.0.0")]
340 pub use self::traits::{FromIterator, IntoIterator, DoubleEndedIterator, Extend};
341 #[stable(feature = "rust1", since = "1.0.0")]
342 pub use self::traits::{ExactSizeIterator, Sum, Product};
343 #[stable(feature = "fused", since = "1.26.0")]
344 pub use self::traits::FusedIterator;
345 #[unstable(feature = "trusted_len", issue = "37572")]
346 pub use self::traits::TrustedLen;
348 #[stable(feature = "rust1", since = "1.0.0")]
349 pub use self::adapters::{Rev, Cycle, Chain, Zip, Map, Filter, FilterMap, Enumerate};
350 #[stable(feature = "rust1", since = "1.0.0")]
351 pub use self::adapters::{Peekable, SkipWhile, TakeWhile, Skip, Take, Scan, FlatMap};
352 #[stable(feature = "rust1", since = "1.0.0")]
353 pub use self::adapters::{Fuse, Inspect};
354 #[stable(feature = "iter_cloned", since = "1.1.0")]
355 pub use self::adapters::Cloned;
356 #[stable(feature = "iterator_step_by", since = "1.28.0")]
357 pub use self::adapters::StepBy;
358 #[stable(feature = "iterator_flatten", since = "1.29.0")]
359 pub use self::adapters::Flatten;
360 #[stable(feature = "iter_copied", since = "1.36.0")]
361 pub use self::adapters::Copied;
363 pub(crate) use self::adapters::{TrustedRandomAccess, OptionShunt, ResultShunt};
370 /// Used to make try_fold closures more like normal loops
372 enum LoopState<C, B> {
377 impl<C, B> Try for LoopState<C, B> {
381 fn into_result(self) -> Result<Self::Ok, Self::Error> {
383 LoopState::Continue(y) => Ok(y),
384 LoopState::Break(x) => Err(x),
388 fn from_error(v: Self::Error) -> Self { LoopState::Break(v) }
390 fn from_ok(v: Self::Ok) -> Self { LoopState::Continue(v) }
393 impl<C, B> LoopState<C, B> {
395 fn break_value(self) -> Option<B> {
397 LoopState::Continue(..) => None,
398 LoopState::Break(x) => Some(x),
403 impl<R: Try> LoopState<R::Ok, R> {
405 fn from_try(r: R) -> Self {
406 match Try::into_result(r) {
407 Ok(v) => LoopState::Continue(v),
408 Err(v) => LoopState::Break(Try::from_error(v)),
412 fn into_try(self) -> R {
414 LoopState::Continue(v) => Try::from_ok(v),
415 LoopState::Break(v) => v,