library/core/src/iter/mod.rs

   1 //! Composable external iteration.
   2 //!
   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.
   7 //!
   8 //! Before explaining more, let's talk about how this module is structured:
   9 //!
  10 //! # Organization
  11 //!
  12 //! This module is largely organized by type:
  13 //!
  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)'.
  22 //!
  23 //! [Traits]: #traits
  24 //! [Functions]: #functions
  25 //! [Structs]: #structs
  26 //!
  27 //! That's it! Let's dig into iterators.
  28 //!
  29 //! # Iterator
  30 //!
  31 //! The heart and soul of this module is the [`Iterator`] trait. The core of
  32 //! [`Iterator`] looks like this:
  33 //!
  34 //! ```
  35 //! trait Iterator {
  36 //!     type Item;
  37 //!     fn next(&mut self) -> Option<Self::Item>;
  38 //! }
  39 //! ```
  40 //!
  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`]).
  47 //!
  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
  50 //! them for free.
  51 //!
  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.
  55 //!
  56 //! [`Some(Item)`]: Some
  57 //! [`next`]: Iterator::next
  58 //! [`TryIter`]: ../../std/sync/mpsc/struct.TryIter.html
  59 //!
  60 //! # The three forms of iteration
  61 //!
  62 //! There are three common methods which can create iterators from a collection:
  63 //!
  64 //! * `iter()`, which iterates over `&T`.
  65 //! * `iter_mut()`, which iterates over `&mut T`.
  66 //! * `into_iter()`, which iterates over `T`.
  67 //!
  68 //! Various things in the standard library may implement one or more of the
  69 //! three, where appropriate.
  70 //!
  71 //! # Implementing Iterator
  72 //!
  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.
  77 //!
  78 //! Let's make an iterator named `Counter` which counts from `1` to `5`:
  79 //!
  80 //! ```
  81 //! // First, the struct:
  82 //!
  83 //! /// An iterator which counts from one to five
  84 //! struct Counter {
  85 //!     count: usize,
  86 //! }
  87 //!
  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.
  91 //! impl Counter {
  92 //!     fn new() -> Counter {
  93 //!         Counter { count: 0 }
  94 //!     }
  95 //! }
  96 //!
  97 //! // Then, we implement `Iterator` for our `Counter`:
  98 //!
  99 //! impl Iterator for Counter {
 100 //!     // we will be counting with usize
 101 //!     type Item = usize;
 102 //!
 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.
 106 //!         self.count += 1;
 107 //!
 108 //!         // Check to see if we've finished counting or not.
 109 //!         if self.count < 6 {
 110 //!             Some(self.count)
 111 //!         } else {
 112 //!             None
 113 //!         }
 114 //!     }
 115 //! }
 116 //!
 117 //! // And now we can use it!
 118 //!
 119 //! let mut counter = Counter::new();
 120 //!
 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);
 127 //! ```
 128 //!
 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
 131 //! next.
 132 //!
 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
 136 //! `next`.
 137 //!
 138 //! # `for` loops and `IntoIterator`
 139 //!
 140 //! Rust's `for` loop syntax is actually sugar for iterators. Here's a basic
 141 //! example of `for`:
 142 //!
 143 //! ```
 144 //! let values = vec![1, 2, 3, 4, 5];
 145 //!
 146 //! for x in values {
 147 //!     println!("{}", x);
 148 //! }
 149 //! ```
 150 //!
 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?
 154 //!
 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
 159 //! it into:
 160 //!
 161 //! [`into_iter`]: IntoIterator::into_iter
 162 //!
 163 //! ```
 164 //! let values = vec![1, 2, 3, 4, 5];
 165 //!
 166 //! for x in values {
 167 //!     println!("{}", x);
 168 //! }
 169 //! ```
 170 //!
 171 //! Rust de-sugars this into:
 172 //!
 173 //! ```
 174 //! let values = vec![1, 2, 3, 4, 5];
 175 //! {
 176 //!     let result = match IntoIterator::into_iter(values) {
 177 //!         mut iter => loop {
 178 //!             let next;
 179 //!             match iter.next() {
 180 //!                 Some(val) => next = val,
 181 //!                 None => break,
 182 //!             };
 183 //!             let x = next;
 184 //!             let () = { println!("{}", x); };
 185 //!         },
 186 //!     };
 187 //!     result
 188 //! }
 189 //! ```
 190 //!
 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.
 194 //!
 195 //! There's one more subtle bit here: the standard library contains an
 196 //! interesting implementation of [`IntoIterator`]:
 197 //!
 198 //! ```ignore (only-for-syntax-highlight)
 199 //! impl<I: Iterator> IntoIterator for I
 200 //! ```
 201 //!
 202 //! In other words, all [`Iterator`]s implement [`IntoIterator`], by just
 203 //! returning themselves. This means two things:
 204 //!
 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.
 208 //!
 209 //! # Iterating by reference
 210 //!
 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:
 216 //!
 217 //! ```
 218 //! let mut values = vec![41];
 219 //! for x in values.iter_mut() {
 220 //!     *x += 1;
 221 //! }
 222 //! for x in values.iter() {
 223 //!     assert_eq!(*x, 42);
 224 //! }
 225 //! assert_eq!(values.len(), 1); // `values` is still owned by this function.
 226 //! ```
 227 //!
 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:
 233 //!
 234 //! ```
 235 //! let mut values = vec![41];
 236 //! for x in &mut values { // same as `values.iter_mut()`
 237 //!     *x += 1;
 238 //! }
 239 //! for x in &values { // same as `values.iter()`
 240 //!     assert_eq!(*x, 42);
 241 //! }
 242 //! assert_eq!(values.len(), 1);
 243 //! ```
 244 //!
 245 //! While many collections offer `iter()`, not all offer `iter_mut()`. For
 246 //! example, mutating the keys of a [`HashSet<T>`] or [`HashMap<K, V>`] could
 247 //! put the collection into an inconsistent state if the key hashes change, so
 248 //! these collections only offer `iter()`.
 249 //!
 250 //! [`into_iter()`]: IntoIterator::into_iter
 251 //! [`HashSet<T>`]: ../../std/collections/struct.HashSet.html
 252 //! [`HashMap<K, V>`]: ../../std/collections/struct.HashMap.html
 253 //!
 254 //! # Adapters
 255 //!
 256 //! Functions which take an [`Iterator`] and return another [`Iterator`] are
 257 //! often called 'iterator adapters', as they're a form of the 'adapter
 258 //! pattern'.
 259 //!
 260 //! Common iterator adapters include [`map`], [`take`], and [`filter`].
 261 //! For more, see their documentation.
 262 //!
 263 //! If an iterator adapter panics, the iterator will be in an unspecified (but
 264 //! memory safe) state.  This state is also not guaranteed to stay the same
 265 //! across versions of Rust, so you should avoid relying on the exact values
 266 //! returned by an iterator which panicked.
 267 //!
 268 //! [`map`]: Iterator::map
 269 //! [`take`]: Iterator::take
 270 //! [`filter`]: Iterator::filter
 271 //!
 272 //! # Laziness
 273 //!
 274 //! Iterators (and iterator [adapters](#adapters)) are *lazy*. This means that
 275 //! just creating an iterator doesn't _do_ a whole lot. Nothing really happens
 276 //! until you call [`next`]. This is sometimes a source of confusion when
 277 //! creating an iterator solely for its side effects. For example, the [`map`]
 278 //! method calls a closure on each element it iterates over:
 279 //!
 280 //! ```
 281 //! # #![allow(unused_must_use)]
 282 //! let v = vec![1, 2, 3, 4, 5];
 283 //! v.iter().map(|x| println!("{}", x));
 284 //! ```
 285 //!
 286 //! This will not print any values, as we only created an iterator, rather than
 287 //! using it. The compiler will warn us about this kind of behavior:
 288 //!
 289 //! ```text
 290 //! warning: unused result that must be used: iterators are lazy and
 291 //! do nothing unless consumed
 292 //! ```
 293 //!
 294 //! The idiomatic way to write a [`map`] for its side effects is to use a
 295 //! `for` loop or call the [`for_each`] method:
 296 //!
 297 //! ```
 298 //! let v = vec![1, 2, 3, 4, 5];
 299 //!
 300 //! v.iter().for_each(|x| println!("{}", x));
 301 //! // or
 302 //! for x in &v {
 303 //!     println!("{}", x);
 304 //! }
 305 //! ```
 306 //!
 307 //! [`map`]: Iterator::map
 308 //! [`for_each`]: Iterator::for_each
 309 //!
 310 //! Another common way to evaluate an iterator is to use the [`collect`]
 311 //! method to produce a new collection.
 312 //!
 313 //! [`collect`]: Iterator::collect
 314 //!
 315 //! # Infinity
 316 //!
 317 //! Iterators do not have to be finite. As an example, an open-ended range is
 318 //! an infinite iterator:
 319 //!
 320 //! ```
 321 //! let numbers = 0..;
 322 //! ```
 323 //!
 324 //! It is common to use the [`take`] iterator adapter to turn an infinite
 325 //! iterator into a finite one:
 326 //!
 327 //! ```
 328 //! let numbers = 0..;
 329 //! let five_numbers = numbers.take(5);
 330 //!
 331 //! for number in five_numbers {
 332 //!     println!("{}", number);
 333 //! }
 334 //! ```
 335 //!
 336 //! This will print the numbers `0` through `4`, each on their own line.
 337 //!
 338 //! Bear in mind that methods on infinite iterators, even those for which a
 339 //! result can be determined mathematically in finite time, might not terminate.
 340 //! Specifically, methods such as [`min`], which in the general case require
 341 //! traversing every element in the iterator, are likely not to return
 342 //! successfully for any infinite iterators.
 343 //!
 344 //! ```no_run
 345 //! let ones = std::iter::repeat(1);
 346 //! let least = ones.min().unwrap(); // Oh no! An infinite loop!
 347 //! // `ones.min()` causes an infinite loop, so we won't reach this point!
 348 //! println!("The smallest number one is {}.", least);
 349 //! ```
 350 //!
 351 //! [`take`]: Iterator::take
 352 //! [`min`]: Iterator::min
 353
 354 #![stable(feature = "rust1", since = "1.0.0")]
 355
 356 #[stable(feature = "rust1", since = "1.0.0")]
 357 pub use self::traits::Iterator;
 358
 359 #[unstable(
 360     feature = "step_trait",
 361     reason = "likely to be replaced by finer-grained traits",
 362     issue = "42168"
 363 )]
 364 pub use self::range::Step;
 365
 366 #[stable(feature = "iter_empty", since = "1.2.0")]
 367 pub use self::sources::{empty, Empty};
 368 #[stable(feature = "iter_from_fn", since = "1.34.0")]
 369 pub use self::sources::{from_fn, FromFn};
 370 #[stable(feature = "iter_once", since = "1.2.0")]
 371 pub use self::sources::{once, Once};
 372 #[stable(feature = "iter_once_with", since = "1.43.0")]
 373 pub use self::sources::{once_with, OnceWith};
 374 #[stable(feature = "rust1", since = "1.0.0")]
 375 pub use self::sources::{repeat, Repeat};
 376 #[stable(feature = "iterator_repeat_with", since = "1.28.0")]
 377 pub use self::sources::{repeat_with, RepeatWith};
 378 #[stable(feature = "iter_successors", since = "1.34.0")]
 379 pub use self::sources::{successors, Successors};
 380
 381 #[stable(feature = "fused", since = "1.26.0")]
 382 pub use self::traits::FusedIterator;
 383 #[unstable(issue = "none", feature = "inplace_iteration")]
 384 pub use self::traits::InPlaceIterable;
 385 #[unstable(feature = "trusted_len", issue = "37572")]
 386 pub use self::traits::TrustedLen;
 387 #[unstable(feature = "trusted_step", issue = "85731")]
 388 pub use self::traits::TrustedStep;
 389 #[stable(feature = "rust1", since = "1.0.0")]
 390 pub use self::traits::{
 391     DoubleEndedIterator, ExactSizeIterator, Extend, FromIterator, IntoIterator, Product, Sum,
 392 };
 393
 394 #[stable(feature = "iter_zip", since = "1.59.0")]
 395 pub use self::adapters::zip;
 396 #[stable(feature = "iter_cloned", since = "1.1.0")]
 397 pub use self::adapters::Cloned;
 398 #[stable(feature = "iter_copied", since = "1.36.0")]
 399 pub use self::adapters::Copied;
 400 #[stable(feature = "iterator_flatten", since = "1.29.0")]
 401 pub use self::adapters::Flatten;
 402 #[stable(feature = "iter_map_while", since = "1.57.0")]
 403 pub use self::adapters::MapWhile;
 404 #[unstable(feature = "inplace_iteration", issue = "none")]
 405 pub use self::adapters::SourceIter;
 406 #[stable(feature = "iterator_step_by", since = "1.28.0")]
 407 pub use self::adapters::StepBy;
 408 #[unstable(feature = "trusted_random_access", issue = "none")]
 409 pub use self::adapters::TrustedRandomAccess;
 410 #[unstable(feature = "trusted_random_access", issue = "none")]
 411 pub use self::adapters::TrustedRandomAccessNoCoerce;
 412 #[stable(feature = "rust1", since = "1.0.0")]
 413 pub use self::adapters::{
 414     Chain, Cycle, Enumerate, Filter, FilterMap, FlatMap, Fuse, Inspect, Map, Peekable, Rev, Scan,
 415     Skip, SkipWhile, Take, TakeWhile, Zip,
 416 };
 417 #[unstable(feature = "iter_intersperse", reason = "recently added", issue = "79524")]
 418 pub use self::adapters::{Intersperse, IntersperseWith};
 419
 420 pub(crate) use self::adapters::process_results;
 421
 422 mod adapters;
 423 mod range;
 424 mod sources;
 425 mod traits;