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 //! <code>[Option]\<Item></code>. Calling [`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 (for example, see [`TryIter`]).
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 //! [`Some(Item)`]: Some
57 //! [`next`]: Iterator::next
58 //! [`TryIter`]: ../../std/sync/mpsc/struct.TryIter.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 implementing [`Iterator`] for that `struct`.
75 //! This is why there are so many `struct`s in this module: there is one for
76 //! 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 //! assert_eq!(counter.next(), Some(1));
122 //! assert_eq!(counter.next(), Some(2));
123 //! assert_eq!(counter.next(), Some(3));
124 //! assert_eq!(counter.next(), Some(4));
125 //! assert_eq!(counter.next(), Some(5));
126 //! assert_eq!(counter.next(), None);
129 //! Calling [`next`] this way gets repetitive. Rust has a construct which can
130 //! call [`next`] on your iterator, until it reaches `None`. Let's go over that
133 //! Also note that `Iterator` provides a default implementation of methods such as `nth` and `fold`
134 //! which call `next` internally. However, it is also possible to write a custom implementation of
135 //! methods like `nth` and `fold` if an iterator can compute them more efficiently without calling
138 //! # `for` loops and `IntoIterator`
140 //! Rust's `for` loop syntax is actually sugar for iterators. Here's a basic
141 //! example of `for`:
144 //! let values = vec![1, 2, 3, 4, 5];
146 //! for x in values {
151 //! This will print the numbers one through five, each on their own line. But
152 //! you'll notice something here: we never called anything on our vector to
153 //! produce an iterator. What gives?
155 //! There's a trait in the standard library for converting something into an
156 //! iterator: [`IntoIterator`]. This trait has one method, [`into_iter`],
157 //! which converts the thing implementing [`IntoIterator`] into an iterator.
158 //! Let's take a look at that `for` loop again, and what the compiler converts
161 //! [`into_iter`]: IntoIterator::into_iter
164 //! let values = vec![1, 2, 3, 4, 5];
166 //! for x in values {
171 //! Rust de-sugars this into:
174 //! let values = vec![1, 2, 3, 4, 5];
176 //! let result = match IntoIterator::into_iter(values) {
177 //! mut iter => loop {
179 //! match iter.next() {
180 //! Some(val) => next = val,
184 //! let () = { println!("{x}"); };
191 //! First, we call `into_iter()` on the value. Then, we match on the iterator
192 //! that returns, calling [`next`] over and over until we see a `None`. At
193 //! that point, we `break` out of the loop, and we're done iterating.
195 //! There's one more subtle bit here: the standard library contains an
196 //! interesting implementation of [`IntoIterator`]:
198 //! ```ignore (only-for-syntax-highlight)
199 //! impl<I: Iterator> IntoIterator for I
202 //! In other words, all [`Iterator`]s implement [`IntoIterator`], by just
203 //! returning themselves. This means two things:
205 //! 1. If you're writing an [`Iterator`], you can use it with a `for` loop.
206 //! 2. If you're creating a collection, implementing [`IntoIterator`] for it
207 //! will allow your collection to be used with the `for` loop.
209 //! # Iterating by reference
211 //! Since [`into_iter()`] takes `self` by value, using a `for` loop to iterate
212 //! over a collection consumes that collection. Often, you may want to iterate
213 //! over a collection without consuming it. Many collections offer methods that
214 //! provide iterators over references, conventionally called `iter()` and
215 //! `iter_mut()` respectively:
218 //! let mut values = vec![41];
219 //! for x in values.iter_mut() {
222 //! for x in values.iter() {
223 //! assert_eq!(*x, 42);
225 //! assert_eq!(values.len(), 1); // `values` is still owned by this function.
228 //! If a collection type `C` provides `iter()`, it usually also implements
229 //! `IntoIterator` for `&C`, with an implementation that just calls `iter()`.
230 //! Likewise, a collection `C` that provides `iter_mut()` generally implements
231 //! `IntoIterator` for `&mut C` by delegating to `iter_mut()`. This enables a
232 //! convenient shorthand:
235 //! let mut values = vec![41];
236 //! for x in &mut values { // same as `values.iter_mut()`
239 //! for x in &values { // same as `values.iter()`
240 //! assert_eq!(*x, 42);
242 //! assert_eq!(values.len(), 1);
245 //! While many collections offer `iter()`, not all offer `iter_mut()`. For
246 //! example, mutating the keys of a [`HashSet<T>`] could put the collection
247 //! into an inconsistent state if the key hashes change, so this collection
248 //! only offers `iter()`.
250 //! [`into_iter()`]: IntoIterator::into_iter
251 //! [`HashSet<T>`]: ../../std/collections/struct.HashSet.html
255 //! Functions which take an [`Iterator`] and return another [`Iterator`] are
256 //! often called 'iterator adapters', as they're a form of the 'adapter
259 //! Common iterator adapters include [`map`], [`take`], and [`filter`].
260 //! For more, see their documentation.
262 //! If an iterator adapter panics, the iterator will be in an unspecified (but
263 //! memory safe) state. This state is also not guaranteed to stay the same
264 //! across versions of Rust, so you should avoid relying on the exact values
265 //! returned by an iterator which panicked.
267 //! [`map`]: Iterator::map
268 //! [`take`]: Iterator::take
269 //! [`filter`]: Iterator::filter
273 //! Iterators (and iterator [adapters](#adapters)) are *lazy*. This means that
274 //! just creating an iterator doesn't _do_ a whole lot. Nothing really happens
275 //! until you call [`next`]. This is sometimes a source of confusion when
276 //! creating an iterator solely for its side effects. For example, the [`map`]
277 //! method calls a closure on each element it iterates over:
280 //! # #![allow(unused_must_use)]
281 //! let v = vec![1, 2, 3, 4, 5];
282 //! v.iter().map(|x| println!("{x}"));
285 //! This will not print any values, as we only created an iterator, rather than
286 //! using it. The compiler will warn us about this kind of behavior:
289 //! warning: unused result that must be used: iterators are lazy and
290 //! do nothing unless consumed
293 //! The idiomatic way to write a [`map`] for its side effects is to use a
294 //! `for` loop or call the [`for_each`] method:
297 //! let v = vec![1, 2, 3, 4, 5];
299 //! v.iter().for_each(|x| println!("{x}"));
306 //! [`map`]: Iterator::map
307 //! [`for_each`]: Iterator::for_each
309 //! Another common way to evaluate an iterator is to use the [`collect`]
310 //! method to produce a new collection.
312 //! [`collect`]: Iterator::collect
316 //! Iterators do not have to be finite. As an example, an open-ended range is
317 //! an infinite iterator:
320 //! let numbers = 0..;
323 //! It is common to use the [`take`] iterator adapter to turn an infinite
324 //! iterator into a finite one:
327 //! let numbers = 0..;
328 //! let five_numbers = numbers.take(5);
330 //! for number in five_numbers {
331 //! println!("{number}");
335 //! This will print the numbers `0` through `4`, each on their own line.
337 //! Bear in mind that methods on infinite iterators, even those for which a
338 //! result can be determined mathematically in finite time, might not terminate.
339 //! Specifically, methods such as [`min`], which in the general case require
340 //! traversing every element in the iterator, are likely not to return
341 //! successfully for any infinite iterators.
344 //! let ones = std::iter::repeat(1);
345 //! let least = ones.min().unwrap(); // Oh no! An infinite loop!
346 //! // `ones.min()` causes an infinite loop, so we won't reach this point!
347 //! println!("The smallest number one is {least}.");
350 //! [`take`]: Iterator::take
351 //! [`min`]: Iterator::min
353 #![stable(feature = "rust1", since = "1.0.0")]
355 // This needs to be up here in order to be usable in the child modules
356 macro_rules! impl_fold_via_try_fold {
357 (fold -> try_fold) => {
358 impl_fold_via_try_fold! { @internal fold -> try_fold }
360 (rfold -> try_rfold) => {
361 impl_fold_via_try_fold! { @internal rfold -> try_rfold }
363 (@internal $fold:ident -> $try_fold:ident) => {
365 fn $fold<AAA, FFF>(mut self, init: AAA, mut fold: FFF) -> AAA
367 FFF: FnMut(AAA, Self::Item) -> AAA,
369 use crate::const_closure::ConstFnMutClosure;
370 use crate::ops::NeverShortCircuit;
372 let fold = ConstFnMutClosure::new(&mut fold, NeverShortCircuit::wrap_mut_2_imp);
373 self.$try_fold(init, fold).0
378 #[stable(feature = "rust1", since = "1.0.0")]
379 pub use self::traits::Iterator;
382 feature = "step_trait",
383 reason = "likely to be replaced by finer-grained traits",
386 pub use self::range::Step;
389 feature = "iter_from_generator",
391 reason = "generators are unstable"
393 pub use self::sources::from_generator;
394 #[stable(feature = "iter_empty", since = "1.2.0")]
395 pub use self::sources::{empty, Empty};
396 #[stable(feature = "iter_from_fn", since = "1.34.0")]
397 pub use self::sources::{from_fn, FromFn};
398 #[stable(feature = "iter_once", since = "1.2.0")]
399 pub use self::sources::{once, Once};
400 #[stable(feature = "iter_once_with", since = "1.43.0")]
401 pub use self::sources::{once_with, OnceWith};
402 #[stable(feature = "rust1", since = "1.0.0")]
403 pub use self::sources::{repeat, Repeat};
404 #[stable(feature = "iterator_repeat_with", since = "1.28.0")]
405 pub use self::sources::{repeat_with, RepeatWith};
406 #[stable(feature = "iter_successors", since = "1.34.0")]
407 pub use self::sources::{successors, Successors};
409 #[stable(feature = "fused", since = "1.26.0")]
410 pub use self::traits::FusedIterator;
411 #[unstable(issue = "none", feature = "inplace_iteration")]
412 pub use self::traits::InPlaceIterable;
413 #[unstable(feature = "trusted_len", issue = "37572")]
414 pub use self::traits::TrustedLen;
415 #[unstable(feature = "trusted_step", issue = "85731")]
416 pub use self::traits::TrustedStep;
417 #[stable(feature = "rust1", since = "1.0.0")]
418 pub use self::traits::{
419 DoubleEndedIterator, ExactSizeIterator, Extend, FromIterator, IntoIterator, Product, Sum,
422 #[stable(feature = "iter_zip", since = "1.59.0")]
423 pub use self::adapters::zip;
424 #[unstable(feature = "iter_array_chunks", reason = "recently added", issue = "100450")]
425 pub use self::adapters::ArrayChunks;
426 #[unstable(feature = "std_internals", issue = "none")]
427 pub use self::adapters::ByRefSized;
428 #[stable(feature = "iter_cloned", since = "1.1.0")]
429 pub use self::adapters::Cloned;
430 #[stable(feature = "iter_copied", since = "1.36.0")]
431 pub use self::adapters::Copied;
432 #[stable(feature = "iterator_flatten", since = "1.29.0")]
433 pub use self::adapters::Flatten;
434 #[stable(feature = "iter_map_while", since = "1.57.0")]
435 pub use self::adapters::MapWhile;
436 #[unstable(feature = "inplace_iteration", issue = "none")]
437 pub use self::adapters::SourceIter;
438 #[stable(feature = "iterator_step_by", since = "1.28.0")]
439 pub use self::adapters::StepBy;
440 #[unstable(feature = "trusted_random_access", issue = "none")]
441 pub use self::adapters::TrustedRandomAccess;
442 #[unstable(feature = "trusted_random_access", issue = "none")]
443 pub use self::adapters::TrustedRandomAccessNoCoerce;
444 #[stable(feature = "rust1", since = "1.0.0")]
445 pub use self::adapters::{
446 Chain, Cycle, Enumerate, Filter, FilterMap, FlatMap, Fuse, Inspect, Map, Peekable, Rev, Scan,
447 Skip, SkipWhile, Take, TakeWhile, Zip,
449 #[unstable(feature = "iter_intersperse", reason = "recently added", issue = "79524")]
450 pub use self::adapters::{Intersperse, IntersperseWith};
452 pub(crate) use self::adapters::try_process;