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>`] could put the collection |
247 | //! into an inconsistent state if the key hashes change, so this collection |
248 | //! only offers `iter()`. |
249 | //! |
250 | //! [`into_iter()`]: IntoIterator::into_iter |
251 | //! [`HashSet<T>`]: ../../std/collections/struct.HashSet.html |
252 | //! |
253 | //! # Adapters |
254 | //! |
255 | //! Functions which take an [`Iterator`] and return another [`Iterator`] are |
256 | //! often called 'iterator adapters', as they're a form of the 'adapter |
257 | //! pattern'. |
258 | //! |
259 | //! Common iterator adapters include [`map`], [`take`], and [`filter`]. |
260 | //! For more, see their documentation. |
261 | //! |
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. |
266 | //! |
267 | //! [`map`]: Iterator::map |
268 | //! [`take`]: Iterator::take |
269 | //! [`filter`]: Iterator::filter |
270 | //! |
271 | //! # Laziness |
272 | //! |
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: |
278 | //! |
279 | //! ``` |
280 | //! # #![allow(unused_must_use)] |
281 | //! # #![allow(map_unit_fn)] |
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 | // This needs to be up here in order to be usable in the child modules |
357 | macro_rules! impl_fold_via_try_fold { |
358 | (fold -> try_fold) => { |
359 | impl_fold_via_try_fold! { @internal fold -> try_fold } |
360 | }; |
361 | (rfold -> try_rfold) => { |
362 | impl_fold_via_try_fold! { @internal rfold -> try_rfold } |
363 | }; |
364 | (spec_fold -> spec_try_fold) => { |
365 | impl_fold_via_try_fold! { @internal spec_fold -> spec_try_fold } |
366 | }; |
367 | (spec_rfold -> spec_try_rfold) => { |
368 | impl_fold_via_try_fold! { @internal spec_rfold -> spec_try_rfold } |
369 | }; |
370 | (@internal $fold:ident -> $try_fold:ident) => { |
371 | #[inline] |
372 | fn $fold<AAA, FFF>(mut self, init: AAA, fold: FFF) -> AAA |
373 | where |
374 | FFF: FnMut(AAA, Self::Item) -> AAA, |
375 | { |
376 | use crate::ops::NeverShortCircuit; |
377 | |
378 | self.$try_fold(init, NeverShortCircuit::wrap_mut_2(fold)).0 |
379 | } |
380 | }; |
381 | } |
382 | |
383 | #[stable (feature = "rust1" , since = "1.0.0" )] |
384 | pub use self::traits::Iterator; |
385 | |
386 | #[unstable ( |
387 | feature = "step_trait" , |
388 | reason = "likely to be replaced by finer-grained traits" , |
389 | issue = "42168" |
390 | )] |
391 | pub use self::range::Step; |
392 | |
393 | #[unstable ( |
394 | feature = "iter_from_coroutine" , |
395 | issue = "43122" , |
396 | reason = "coroutines are unstable" |
397 | )] |
398 | pub use self::sources::from_coroutine; |
399 | #[stable (feature = "iter_empty" , since = "1.2.0" )] |
400 | pub use self::sources::{empty, Empty}; |
401 | #[stable (feature = "iter_from_fn" , since = "1.34.0" )] |
402 | pub use self::sources::{from_fn, FromFn}; |
403 | #[stable (feature = "iter_once" , since = "1.2.0" )] |
404 | pub use self::sources::{once, Once}; |
405 | #[stable (feature = "iter_once_with" , since = "1.43.0" )] |
406 | pub use self::sources::{once_with, OnceWith}; |
407 | #[stable (feature = "rust1" , since = "1.0.0" )] |
408 | pub use self::sources::{repeat, Repeat}; |
409 | #[unstable (feature = "iter_repeat_n" , issue = "104434" )] |
410 | pub use self::sources::{repeat_n, RepeatN}; |
411 | #[stable (feature = "iterator_repeat_with" , since = "1.28.0" )] |
412 | pub use self::sources::{repeat_with, RepeatWith}; |
413 | #[stable (feature = "iter_successors" , since = "1.34.0" )] |
414 | pub use self::sources::{successors, Successors}; |
415 | |
416 | #[stable (feature = "fused" , since = "1.26.0" )] |
417 | pub use self::traits::FusedIterator; |
418 | #[unstable (issue = "none" , feature = "inplace_iteration" )] |
419 | pub use self::traits::InPlaceIterable; |
420 | #[unstable (issue = "none" , feature = "trusted_fused" )] |
421 | pub use self::traits::TrustedFused; |
422 | #[unstable (feature = "trusted_len" , issue = "37572" )] |
423 | pub use self::traits::TrustedLen; |
424 | #[unstable (feature = "trusted_step" , issue = "85731" )] |
425 | pub use self::traits::TrustedStep; |
426 | #[stable (feature = "rust1" , since = "1.0.0" )] |
427 | pub use self::traits::{ |
428 | DoubleEndedIterator, ExactSizeIterator, Extend, FromIterator, IntoIterator, Product, Sum, |
429 | }; |
430 | |
431 | #[stable (feature = "iter_zip" , since = "1.59.0" )] |
432 | pub use self::adapters::zip; |
433 | #[unstable (feature = "iter_array_chunks" , reason = "recently added" , issue = "100450" )] |
434 | pub use self::adapters::ArrayChunks; |
435 | #[unstable (feature = "std_internals" , issue = "none" )] |
436 | pub use self::adapters::ByRefSized; |
437 | #[stable (feature = "iter_cloned" , since = "1.1.0" )] |
438 | pub use self::adapters::Cloned; |
439 | #[stable (feature = "iter_copied" , since = "1.36.0" )] |
440 | pub use self::adapters::Copied; |
441 | #[stable (feature = "iterator_flatten" , since = "1.29.0" )] |
442 | pub use self::adapters::Flatten; |
443 | #[stable (feature = "iter_map_while" , since = "1.57.0" )] |
444 | pub use self::adapters::MapWhile; |
445 | #[unstable (feature = "iter_map_windows" , reason = "recently added" , issue = "87155" )] |
446 | pub use self::adapters::MapWindows; |
447 | #[unstable (feature = "inplace_iteration" , issue = "none" )] |
448 | pub use self::adapters::SourceIter; |
449 | #[stable (feature = "iterator_step_by" , since = "1.28.0" )] |
450 | pub use self::adapters::StepBy; |
451 | #[unstable (feature = "trusted_random_access" , issue = "none" )] |
452 | pub use self::adapters::TrustedRandomAccess; |
453 | #[unstable (feature = "trusted_random_access" , issue = "none" )] |
454 | pub use self::adapters::TrustedRandomAccessNoCoerce; |
455 | #[stable (feature = "rust1" , since = "1.0.0" )] |
456 | pub use self::adapters::{ |
457 | Chain, Cycle, Enumerate, Filter, FilterMap, FlatMap, Fuse, Inspect, Map, Peekable, Rev, Scan, |
458 | Skip, SkipWhile, Take, TakeWhile, Zip, |
459 | }; |
460 | #[unstable (feature = "iter_intersperse" , reason = "recently added" , issue = "79524" )] |
461 | pub use self::adapters::{Intersperse, IntersperseWith}; |
462 | |
463 | pub(crate) use self::adapters::try_process; |
464 | pub(crate) use self::traits::UncheckedIterator; |
465 | |
466 | mod adapters; |
467 | mod range; |
468 | mod sources; |
469 | mod traits; |
470 | |