]>
Commit | Line | Data |
---|---|---|
a7813a04 XL |
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 | //! | |
cc61c64b | 41 | //! An iterator has a method, [`next`], which when called, returns an |
3dfed10e | 42 | //! [`Option`]`<Item>`. [`next`] will return [`Some(Item)`] as long as there |
a7813a04 XL |
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 | |
cc61c64b | 45 | //! resume iteration, and so calling [`next`] again may or may not eventually |
3dfed10e | 46 | //! start returning [`Some(Item)`] again at some point (for example, see [`TryIter`]). |
a7813a04 XL |
47 | //! |
48 | //! [`Iterator`]'s full definition includes a number of other methods as well, | |
cc61c64b | 49 | //! but they are default methods, built on top of [`next`], and so you get |
a7813a04 XL |
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 | //! | |
3dfed10e | 56 | //! [`Some(Item)`]: Some |
1b1a35ee | 57 | //! [`next`]: Iterator::next |
74b04a01 | 58 | //! [`TryIter`]: ../../std/sync/mpsc/struct.TryIter.html |
a7813a04 XL |
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 | |
3dfed10e XL |
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. | |
a7813a04 XL |
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 | |
532ac7d7 | 104 | //! fn next(&mut self) -> Option<Self::Item> { |
a1dfa0c6 | 105 | //! // Increment our count. This is why we started at zero. |
a7813a04 XL |
106 | //! self.count += 1; |
107 | //! | |
a1dfa0c6 | 108 | //! // Check to see if we've finished counting or not. |
a7813a04 XL |
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 | //! | |
e74abb32 XL |
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); | |
a7813a04 XL |
127 | //! ``` |
128 | //! | |
e74abb32 XL |
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 | |
a7813a04 XL |
131 | //! next. |
132 | //! | |
dc9dc135 XL |
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 | //! | |
1b1a35ee | 138 | //! # `for` loops and `IntoIterator` |
a7813a04 XL |
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 | |
cc61c64b | 156 | //! iterator: [`IntoIterator`]. This trait has one method, [`into_iter`], |
a7813a04 XL |
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 | //! | |
1b1a35ee | 161 | //! [`into_iter`]: IntoIterator::into_iter |
a7813a04 XL |
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 { | |
7cac9316 | 178 | //! let next; |
a7813a04 | 179 | //! match iter.next() { |
7cac9316 | 180 | //! Some(val) => next = val, |
a7813a04 | 181 | //! None => break, |
7cac9316 XL |
182 | //! }; |
183 | //! let x = next; | |
184 | //! let () = { println!("{}", x); }; | |
a7813a04 XL |
185 | //! }, |
186 | //! }; | |
187 | //! result | |
188 | //! } | |
189 | //! ``` | |
190 | //! | |
191 | //! First, we call `into_iter()` on the value. Then, we match on the iterator | |
cc61c64b | 192 | //! that returns, calling [`next`] over and over until we see a `None`. At |
a7813a04 XL |
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 | //! | |
041b39d2 | 198 | //! ```ignore (only-for-syntax-highlight) |
a7813a04 XL |
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 | //! | |
fc512014 XL |
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 | //! | |
a7813a04 XL |
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 | //! | |
cc61c64b | 260 | //! Common iterator adapters include [`map`], [`take`], and [`filter`]. |
a7813a04 XL |
261 | //! For more, see their documentation. |
262 | //! | |
dfeec247 XL |
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 | //! | |
1b1a35ee XL |
268 | //! [`map`]: Iterator::map |
269 | //! [`take`]: Iterator::take | |
270 | //! [`filter`]: Iterator::filter | |
a7813a04 XL |
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 | |
cc61c64b XL |
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`] | |
a7813a04 XL |
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 | |
0731742a | 290 | //! warning: unused result that must be used: iterators are lazy and |
a7813a04 XL |
291 | //! do nothing unless consumed |
292 | //! ``` | |
293 | //! | |
cc61c64b | 294 | //! The idiomatic way to write a [`map`] for its side effects is to use a |
e74abb32 | 295 | //! `for` loop or call the [`for_each`] method: |
a7813a04 XL |
296 | //! |
297 | //! ``` | |
298 | //! let v = vec![1, 2, 3, 4, 5]; | |
299 | //! | |
e74abb32 XL |
300 | //! v.iter().for_each(|x| println!("{}", x)); |
301 | //! // or | |
a7813a04 XL |
302 | //! for x in &v { |
303 | //! println!("{}", x); | |
304 | //! } | |
305 | //! ``` | |
306 | //! | |
1b1a35ee XL |
307 | //! [`map`]: Iterator::map |
308 | //! [`for_each`]: Iterator::for_each | |
a7813a04 | 309 | //! |
e74abb32 XL |
310 | //! Another common way to evaluate an iterator is to use the [`collect`] |
311 | //! method to produce a new collection. | |
a7813a04 | 312 | //! |
1b1a35ee | 313 | //! [`collect`]: Iterator::collect |
a7813a04 XL |
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 | //! | |
cc61c64b | 324 | //! It is common to use the [`take`] iterator adapter to turn an infinite |
a7813a04 XL |
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 | //! | |
2c00a5a8 | 338 | //! Bear in mind that methods on infinite iterators, even those for which a |
94222f64 | 339 | //! result can be determined mathematically in finite time, might not terminate. |
2c00a5a8 XL |
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 | //! | |
1b1a35ee XL |
351 | //! [`take`]: Iterator::take |
352 | //! [`min`]: Iterator::min | |
a7813a04 XL |
353 | |
354 | #![stable(feature = "rust1", since = "1.0.0")] | |
355 | ||
a7813a04 | 356 | #[stable(feature = "rust1", since = "1.0.0")] |
9fa01778 | 357 | pub use self::traits::Iterator; |
a7813a04 | 358 | |
dfeec247 XL |
359 | #[unstable( |
360 | feature = "step_trait", | |
361 | reason = "likely to be replaced by finer-grained traits", | |
362 | issue = "42168" | |
363 | )] | |
a7813a04 | 364 | pub use self::range::Step; |
a7813a04 | 365 | |
a7813a04 | 366 | #[stable(feature = "iter_empty", since = "1.2.0")] |
dfeec247 XL |
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}; | |
a7813a04 | 370 | #[stable(feature = "iter_once", since = "1.2.0")] |
dfeec247 | 371 | pub use self::sources::{once, Once}; |
74b04a01 | 372 | #[stable(feature = "iter_once_with", since = "1.43.0")] |
dfeec247 XL |
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}; | |
9fa01778 | 378 | #[stable(feature = "iter_successors", since = "1.34.0")] |
dfeec247 | 379 | pub use self::sources::{successors, Successors}; |
a7813a04 | 380 | |
0531ce1d | 381 | #[stable(feature = "fused", since = "1.26.0")] |
9e0c209e | 382 | pub use self::traits::FusedIterator; |
fc512014 XL |
383 | #[unstable(issue = "none", feature = "inplace_iteration")] |
384 | pub use self::traits::InPlaceIterable; | |
c30ab7b3 SL |
385 | #[unstable(feature = "trusted_len", issue = "37572")] |
386 | pub use self::traits::TrustedLen; | |
17df50a5 XL |
387 | #[unstable(feature = "trusted_step", issue = "85731")] |
388 | pub use self::traits::TrustedStep; | |
9fa01778 | 389 | #[stable(feature = "rust1", since = "1.0.0")] |
fc512014 XL |
390 | pub use self::traits::{ |
391 | DoubleEndedIterator, ExactSizeIterator, Extend, FromIterator, IntoIterator, Product, Sum, | |
392 | }; | |
1b1a35ee | 393 | |
cdc7bbd5 XL |
394 | #[unstable(feature = "iter_zip", issue = "83574")] |
395 | pub use self::adapters::zip; | |
9fa01778 XL |
396 | #[stable(feature = "iter_cloned", since = "1.1.0")] |
397 | pub use self::adapters::Cloned; | |
48663c56 | 398 | #[stable(feature = "iter_copied", since = "1.36.0")] |
9fa01778 | 399 | pub use self::adapters::Copied; |
dfeec247 XL |
400 | #[stable(feature = "iterator_flatten", since = "1.29.0")] |
401 | pub use self::adapters::Flatten; | |
74b04a01 XL |
402 | #[unstable(feature = "iter_map_while", reason = "recently added", issue = "68537")] |
403 | pub use self::adapters::MapWhile; | |
fc512014 | 404 | #[unstable(feature = "inplace_iteration", issue = "none")] |
1b1a35ee | 405 | pub use self::adapters::SourceIter; |
dfeec247 XL |
406 | #[stable(feature = "iterator_step_by", since = "1.28.0")] |
407 | pub use self::adapters::StepBy; | |
1b1a35ee XL |
408 | #[unstable(feature = "trusted_random_access", issue = "none")] |
409 | pub use self::adapters::TrustedRandomAccess; | |
94222f64 XL |
410 | #[unstable(feature = "trusted_random_access", issue = "none")] |
411 | pub use self::adapters::TrustedRandomAccessNoCoerce; | |
dfeec247 | 412 | #[stable(feature = "rust1", since = "1.0.0")] |
fc512014 XL |
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 | }; | |
dc3f5686 | 417 | #[unstable(feature = "iter_intersperse", reason = "recently added", issue = "79524")] |
5869c6ff | 418 | pub use self::adapters::{Intersperse, IntersperseWith}; |
9fa01778 | 419 | |
1b1a35ee | 420 | pub(crate) use self::adapters::process_results; |
9fa01778 | 421 | |
dfeec247 | 422 | mod adapters; |
a7813a04 XL |
423 | mod range; |
424 | mod sources; | |
425 | mod traits; |