core/iter/traits/iterator.rs
1#[cfg(not(feature = "ferrocene_certified"))]
2use super::super::{
3 ArrayChunks, ByRefSized, Chain, Cloned, Copied, Cycle, Enumerate, Filter, FilterMap, FlatMap,
4 Flatten, Fuse, Inspect, Intersperse, IntersperseWith, Map, MapWhile, MapWindows, Peekable,
5 Product, Rev, Scan, Skip, SkipWhile, StepBy, Sum, Take, TakeWhile, TrustedRandomAccessNoCoerce,
6 Zip, try_process,
7};
8#[cfg(not(feature = "ferrocene_certified"))]
9use super::TrustedLen;
10#[cfg(not(feature = "ferrocene_certified"))]
11use crate::array;
12#[cfg(not(feature = "ferrocene_certified"))]
13use crate::cmp::{self, Ordering};
14#[cfg(not(feature = "ferrocene_certified"))]
15use crate::num::NonZero;
16#[cfg(not(feature = "ferrocene_certified"))]
17use crate::ops::{ChangeOutputType, ControlFlow, FromResidual, Residual, Try};
18
19#[cfg(not(feature = "ferrocene_certified"))]
20fn _assert_is_dyn_compatible(_: &dyn Iterator<Item = ()>) {}
21
22/// A trait for dealing with iterators.
23///
24/// This is the main iterator trait. For more about the concept of iterators
25/// generally, please see the [module-level documentation]. In particular, you
26/// may want to know how to [implement `Iterator`][impl].
27///
28/// [module-level documentation]: crate::iter
29/// [impl]: crate::iter#implementing-iterator
30#[stable(feature = "rust1", since = "1.0.0")]
31#[rustc_on_unimplemented(
32 on(
33 Self = "core::ops::range::RangeTo<Idx>",
34 note = "you might have meant to use a bounded `Range`"
35 ),
36 on(
37 Self = "core::ops::range::RangeToInclusive<Idx>",
38 note = "you might have meant to use a bounded `RangeInclusive`"
39 ),
40 label = "`{Self}` is not an iterator",
41 message = "`{Self}` is not an iterator"
42)]
43#[cfg_attr(not(feature = "ferrocene_certified"), doc(notable_trait))]
44#[lang = "iterator"]
45#[rustc_diagnostic_item = "Iterator"]
46#[must_use = "iterators are lazy and do nothing unless consumed"]
47pub trait Iterator {
48 /// The type of the elements being iterated over.
49 #[rustc_diagnostic_item = "IteratorItem"]
50 #[stable(feature = "rust1", since = "1.0.0")]
51 type Item;
52
53 /// Advances the iterator and returns the next value.
54 ///
55 /// Returns [`None`] when iteration is finished. Individual iterator
56 /// implementations may choose to resume iteration, and so calling `next()`
57 /// again may or may not eventually start returning [`Some(Item)`] again at some
58 /// point.
59 ///
60 /// [`Some(Item)`]: Some
61 ///
62 /// # Examples
63 ///
64 /// ```
65 /// let a = [1, 2, 3];
66 ///
67 /// let mut iter = a.into_iter();
68 ///
69 /// // A call to next() returns the next value...
70 /// assert_eq!(Some(1), iter.next());
71 /// assert_eq!(Some(2), iter.next());
72 /// assert_eq!(Some(3), iter.next());
73 ///
74 /// // ... and then None once it's over.
75 /// assert_eq!(None, iter.next());
76 ///
77 /// // More calls may or may not return `None`. Here, they always will.
78 /// assert_eq!(None, iter.next());
79 /// assert_eq!(None, iter.next());
80 /// ```
81 #[lang = "next"]
82 #[stable(feature = "rust1", since = "1.0.0")]
83 fn next(&mut self) -> Option<Self::Item>;
84
85 /// Advances the iterator and returns an array containing the next `N` values.
86 ///
87 /// If there are not enough elements to fill the array then `Err` is returned
88 /// containing an iterator over the remaining elements.
89 ///
90 /// # Examples
91 ///
92 /// Basic usage:
93 ///
94 /// ```
95 /// #![feature(iter_next_chunk)]
96 ///
97 /// let mut iter = "lorem".chars();
98 ///
99 /// assert_eq!(iter.next_chunk().unwrap(), ['l', 'o']); // N is inferred as 2
100 /// assert_eq!(iter.next_chunk().unwrap(), ['r', 'e', 'm']); // N is inferred as 3
101 /// assert_eq!(iter.next_chunk::<4>().unwrap_err().as_slice(), &[]); // N is explicitly 4
102 /// ```
103 ///
104 /// Split a string and get the first three items.
105 ///
106 /// ```
107 /// #![feature(iter_next_chunk)]
108 ///
109 /// let quote = "not all those who wander are lost";
110 /// let [first, second, third] = quote.split_whitespace().next_chunk().unwrap();
111 /// assert_eq!(first, "not");
112 /// assert_eq!(second, "all");
113 /// assert_eq!(third, "those");
114 /// ```
115 #[inline]
116 #[unstable(feature = "iter_next_chunk", reason = "recently added", issue = "98326")]
117 #[cfg(not(feature = "ferrocene_certified"))]
118 fn next_chunk<const N: usize>(
119 &mut self,
120 ) -> Result<[Self::Item; N], array::IntoIter<Self::Item, N>>
121 where
122 Self: Sized,
123 {
124 array::iter_next_chunk(self)
125 }
126
127 /// Returns the bounds on the remaining length of the iterator.
128 ///
129 /// Specifically, `size_hint()` returns a tuple where the first element
130 /// is the lower bound, and the second element is the upper bound.
131 ///
132 /// The second half of the tuple that is returned is an <code>[Option]<[usize]></code>.
133 /// A [`None`] here means that either there is no known upper bound, or the
134 /// upper bound is larger than [`usize`].
135 ///
136 /// # Implementation notes
137 ///
138 /// It is not enforced that an iterator implementation yields the declared
139 /// number of elements. A buggy iterator may yield less than the lower bound
140 /// or more than the upper bound of elements.
141 ///
142 /// `size_hint()` is primarily intended to be used for optimizations such as
143 /// reserving space for the elements of the iterator, but must not be
144 /// trusted to e.g., omit bounds checks in unsafe code. An incorrect
145 /// implementation of `size_hint()` should not lead to memory safety
146 /// violations.
147 ///
148 /// That said, the implementation should provide a correct estimation,
149 /// because otherwise it would be a violation of the trait's protocol.
150 ///
151 /// The default implementation returns <code>(0, [None])</code> which is correct for any
152 /// iterator.
153 ///
154 /// # Examples
155 ///
156 /// Basic usage:
157 ///
158 /// ```
159 /// let a = [1, 2, 3];
160 /// let mut iter = a.iter();
161 ///
162 /// assert_eq!((3, Some(3)), iter.size_hint());
163 /// let _ = iter.next();
164 /// assert_eq!((2, Some(2)), iter.size_hint());
165 /// ```
166 ///
167 /// A more complex example:
168 ///
169 /// ```
170 /// // The even numbers in the range of zero to nine.
171 /// let iter = (0..10).filter(|x| x % 2 == 0);
172 ///
173 /// // We might iterate from zero to ten times. Knowing that it's five
174 /// // exactly wouldn't be possible without executing filter().
175 /// assert_eq!((0, Some(10)), iter.size_hint());
176 ///
177 /// // Let's add five more numbers with chain()
178 /// let iter = (0..10).filter(|x| x % 2 == 0).chain(15..20);
179 ///
180 /// // now both bounds are increased by five
181 /// assert_eq!((5, Some(15)), iter.size_hint());
182 /// ```
183 ///
184 /// Returning `None` for an upper bound:
185 ///
186 /// ```
187 /// // an infinite iterator has no upper bound
188 /// // and the maximum possible lower bound
189 /// let iter = 0..;
190 ///
191 /// assert_eq!((usize::MAX, None), iter.size_hint());
192 /// ```
193 #[inline]
194 #[stable(feature = "rust1", since = "1.0.0")]
195 #[cfg(not(feature = "ferrocene_certified"))]
196 fn size_hint(&self) -> (usize, Option<usize>) {
197 (0, None)
198 }
199
200 /// Consumes the iterator, counting the number of iterations and returning it.
201 ///
202 /// This method will call [`next`] repeatedly until [`None`] is encountered,
203 /// returning the number of times it saw [`Some`]. Note that [`next`] has to be
204 /// called at least once even if the iterator does not have any elements.
205 ///
206 /// [`next`]: Iterator::next
207 ///
208 /// # Overflow Behavior
209 ///
210 /// The method does no guarding against overflows, so counting elements of
211 /// an iterator with more than [`usize::MAX`] elements either produces the
212 /// wrong result or panics. If overflow checks are enabled, a panic is
213 /// guaranteed.
214 ///
215 /// # Panics
216 ///
217 /// This function might panic if the iterator has more than [`usize::MAX`]
218 /// elements.
219 ///
220 /// # Examples
221 ///
222 /// ```
223 /// let a = [1, 2, 3];
224 /// assert_eq!(a.iter().count(), 3);
225 ///
226 /// let a = [1, 2, 3, 4, 5];
227 /// assert_eq!(a.iter().count(), 5);
228 /// ```
229 #[inline]
230 #[stable(feature = "rust1", since = "1.0.0")]
231 #[cfg(not(feature = "ferrocene_certified"))]
232 fn count(self) -> usize
233 where
234 Self: Sized,
235 {
236 self.fold(
237 0,
238 #[rustc_inherit_overflow_checks]
239 |count, _| count + 1,
240 )
241 }
242
243 /// Consumes the iterator, returning the last element.
244 ///
245 /// This method will evaluate the iterator until it returns [`None`]. While
246 /// doing so, it keeps track of the current element. After [`None`] is
247 /// returned, `last()` will then return the last element it saw.
248 ///
249 /// # Examples
250 ///
251 /// ```
252 /// let a = [1, 2, 3];
253 /// assert_eq!(a.into_iter().last(), Some(3));
254 ///
255 /// let a = [1, 2, 3, 4, 5];
256 /// assert_eq!(a.into_iter().last(), Some(5));
257 /// ```
258 #[inline]
259 #[stable(feature = "rust1", since = "1.0.0")]
260 #[cfg(not(feature = "ferrocene_certified"))]
261 fn last(self) -> Option<Self::Item>
262 where
263 Self: Sized,
264 {
265 #[inline]
266 fn some<T>(_: Option<T>, x: T) -> Option<T> {
267 Some(x)
268 }
269
270 self.fold(None, some)
271 }
272
273 /// Advances the iterator by `n` elements.
274 ///
275 /// This method will eagerly skip `n` elements by calling [`next`] up to `n`
276 /// times until [`None`] is encountered.
277 ///
278 /// `advance_by(n)` will return `Ok(())` if the iterator successfully advances by
279 /// `n` elements, or a `Err(NonZero<usize>)` with value `k` if [`None`] is encountered,
280 /// where `k` is remaining number of steps that could not be advanced because the iterator ran out.
281 /// If `self` is empty and `n` is non-zero, then this returns `Err(n)`.
282 /// Otherwise, `k` is always less than `n`.
283 ///
284 /// Calling `advance_by(0)` can do meaningful work, for example [`Flatten`]
285 /// can advance its outer iterator until it finds an inner iterator that is not empty, which
286 /// then often allows it to return a more accurate `size_hint()` than in its initial state.
287 ///
288 /// [`Flatten`]: crate::iter::Flatten
289 /// [`next`]: Iterator::next
290 ///
291 /// # Examples
292 ///
293 /// ```
294 /// #![feature(iter_advance_by)]
295 ///
296 /// use std::num::NonZero;
297 ///
298 /// let a = [1, 2, 3, 4];
299 /// let mut iter = a.into_iter();
300 ///
301 /// assert_eq!(iter.advance_by(2), Ok(()));
302 /// assert_eq!(iter.next(), Some(3));
303 /// assert_eq!(iter.advance_by(0), Ok(()));
304 /// assert_eq!(iter.advance_by(100), Err(NonZero::new(99).unwrap())); // only `4` was skipped
305 /// ```
306 #[inline]
307 #[unstable(feature = "iter_advance_by", reason = "recently added", issue = "77404")]
308 #[cfg(not(feature = "ferrocene_certified"))]
309 fn advance_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
310 /// Helper trait to specialize `advance_by` via `try_fold` for `Sized` iterators.
311 trait SpecAdvanceBy {
312 fn spec_advance_by(&mut self, n: usize) -> Result<(), NonZero<usize>>;
313 }
314
315 impl<I: Iterator + ?Sized> SpecAdvanceBy for I {
316 default fn spec_advance_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
317 for i in 0..n {
318 if self.next().is_none() {
319 // SAFETY: `i` is always less than `n`.
320 return Err(unsafe { NonZero::new_unchecked(n - i) });
321 }
322 }
323 Ok(())
324 }
325 }
326
327 impl<I: Iterator> SpecAdvanceBy for I {
328 fn spec_advance_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
329 let Some(n) = NonZero::new(n) else {
330 return Ok(());
331 };
332
333 let res = self.try_fold(n, |n, _| NonZero::new(n.get() - 1));
334
335 match res {
336 None => Ok(()),
337 Some(n) => Err(n),
338 }
339 }
340 }
341
342 self.spec_advance_by(n)
343 }
344
345 /// Returns the `n`th element of the iterator.
346 ///
347 /// Like most indexing operations, the count starts from zero, so `nth(0)`
348 /// returns the first value, `nth(1)` the second, and so on.
349 ///
350 /// Note that all preceding elements, as well as the returned element, will be
351 /// consumed from the iterator. That means that the preceding elements will be
352 /// discarded, and also that calling `nth(0)` multiple times on the same iterator
353 /// will return different elements.
354 ///
355 /// `nth()` will return [`None`] if `n` is greater than or equal to the length of the
356 /// iterator.
357 ///
358 /// # Examples
359 ///
360 /// Basic usage:
361 ///
362 /// ```
363 /// let a = [1, 2, 3];
364 /// assert_eq!(a.into_iter().nth(1), Some(2));
365 /// ```
366 ///
367 /// Calling `nth()` multiple times doesn't rewind the iterator:
368 ///
369 /// ```
370 /// let a = [1, 2, 3];
371 ///
372 /// let mut iter = a.into_iter();
373 ///
374 /// assert_eq!(iter.nth(1), Some(2));
375 /// assert_eq!(iter.nth(1), None);
376 /// ```
377 ///
378 /// Returning `None` if there are less than `n + 1` elements:
379 ///
380 /// ```
381 /// let a = [1, 2, 3];
382 /// assert_eq!(a.into_iter().nth(10), None);
383 /// ```
384 #[inline]
385 #[stable(feature = "rust1", since = "1.0.0")]
386 #[cfg(not(feature = "ferrocene_certified"))]
387 fn nth(&mut self, n: usize) -> Option<Self::Item> {
388 self.advance_by(n).ok()?;
389 self.next()
390 }
391
392 /// Creates an iterator starting at the same point, but stepping by
393 /// the given amount at each iteration.
394 ///
395 /// Note 1: The first element of the iterator will always be returned,
396 /// regardless of the step given.
397 ///
398 /// Note 2: The time at which ignored elements are pulled is not fixed.
399 /// `StepBy` behaves like the sequence `self.next()`, `self.nth(step-1)`,
400 /// `self.nth(step-1)`, …, but is also free to behave like the sequence
401 /// `advance_n_and_return_first(&mut self, step)`,
402 /// `advance_n_and_return_first(&mut self, step)`, …
403 /// Which way is used may change for some iterators for performance reasons.
404 /// The second way will advance the iterator earlier and may consume more items.
405 ///
406 /// `advance_n_and_return_first` is the equivalent of:
407 /// ```
408 /// fn advance_n_and_return_first<I>(iter: &mut I, n: usize) -> Option<I::Item>
409 /// where
410 /// I: Iterator,
411 /// {
412 /// let next = iter.next();
413 /// if n > 1 {
414 /// iter.nth(n - 2);
415 /// }
416 /// next
417 /// }
418 /// ```
419 ///
420 /// # Panics
421 ///
422 /// The method will panic if the given step is `0`.
423 ///
424 /// # Examples
425 ///
426 /// ```
427 /// let a = [0, 1, 2, 3, 4, 5];
428 /// let mut iter = a.into_iter().step_by(2);
429 ///
430 /// assert_eq!(iter.next(), Some(0));
431 /// assert_eq!(iter.next(), Some(2));
432 /// assert_eq!(iter.next(), Some(4));
433 /// assert_eq!(iter.next(), None);
434 /// ```
435 #[inline]
436 #[stable(feature = "iterator_step_by", since = "1.28.0")]
437 #[cfg(not(feature = "ferrocene_certified"))]
438 fn step_by(self, step: usize) -> StepBy<Self>
439 where
440 Self: Sized,
441 {
442 StepBy::new(self, step)
443 }
444
445 /// Takes two iterators and creates a new iterator over both in sequence.
446 ///
447 /// `chain()` will return a new iterator which will first iterate over
448 /// values from the first iterator and then over values from the second
449 /// iterator.
450 ///
451 /// In other words, it links two iterators together, in a chain. 🔗
452 ///
453 /// [`once`] is commonly used to adapt a single value into a chain of
454 /// other kinds of iteration.
455 ///
456 /// # Examples
457 ///
458 /// Basic usage:
459 ///
460 /// ```
461 /// let s1 = "abc".chars();
462 /// let s2 = "def".chars();
463 ///
464 /// let mut iter = s1.chain(s2);
465 ///
466 /// assert_eq!(iter.next(), Some('a'));
467 /// assert_eq!(iter.next(), Some('b'));
468 /// assert_eq!(iter.next(), Some('c'));
469 /// assert_eq!(iter.next(), Some('d'));
470 /// assert_eq!(iter.next(), Some('e'));
471 /// assert_eq!(iter.next(), Some('f'));
472 /// assert_eq!(iter.next(), None);
473 /// ```
474 ///
475 /// Since the argument to `chain()` uses [`IntoIterator`], we can pass
476 /// anything that can be converted into an [`Iterator`], not just an
477 /// [`Iterator`] itself. For example, arrays (`[T]`) implement
478 /// [`IntoIterator`], and so can be passed to `chain()` directly:
479 ///
480 /// ```
481 /// let a1 = [1, 2, 3];
482 /// let a2 = [4, 5, 6];
483 ///
484 /// let mut iter = a1.into_iter().chain(a2);
485 ///
486 /// assert_eq!(iter.next(), Some(1));
487 /// assert_eq!(iter.next(), Some(2));
488 /// assert_eq!(iter.next(), Some(3));
489 /// assert_eq!(iter.next(), Some(4));
490 /// assert_eq!(iter.next(), Some(5));
491 /// assert_eq!(iter.next(), Some(6));
492 /// assert_eq!(iter.next(), None);
493 /// ```
494 ///
495 /// If you work with Windows API, you may wish to convert [`OsStr`] to `Vec<u16>`:
496 ///
497 /// ```
498 /// #[cfg(windows)]
499 /// fn os_str_to_utf16(s: &std::ffi::OsStr) -> Vec<u16> {
500 /// use std::os::windows::ffi::OsStrExt;
501 /// s.encode_wide().chain(std::iter::once(0)).collect()
502 /// }
503 /// ```
504 ///
505 /// [`once`]: crate::iter::once
506 /// [`OsStr`]: ../../std/ffi/struct.OsStr.html
507 #[inline]
508 #[stable(feature = "rust1", since = "1.0.0")]
509 #[cfg(not(feature = "ferrocene_certified"))]
510 fn chain<U>(self, other: U) -> Chain<Self, U::IntoIter>
511 where
512 Self: Sized,
513 U: IntoIterator<Item = Self::Item>,
514 {
515 Chain::new(self, other.into_iter())
516 }
517
518 /// 'Zips up' two iterators into a single iterator of pairs.
519 ///
520 /// `zip()` returns a new iterator that will iterate over two other
521 /// iterators, returning a tuple where the first element comes from the
522 /// first iterator, and the second element comes from the second iterator.
523 ///
524 /// In other words, it zips two iterators together, into a single one.
525 ///
526 /// If either iterator returns [`None`], [`next`] from the zipped iterator
527 /// will return [`None`].
528 /// If the zipped iterator has no more elements to return then each further attempt to advance
529 /// it will first try to advance the first iterator at most one time and if it still yielded an item
530 /// try to advance the second iterator at most one time.
531 ///
532 /// To 'undo' the result of zipping up two iterators, see [`unzip`].
533 ///
534 /// [`unzip`]: Iterator::unzip
535 ///
536 /// # Examples
537 ///
538 /// Basic usage:
539 ///
540 /// ```
541 /// let s1 = "abc".chars();
542 /// let s2 = "def".chars();
543 ///
544 /// let mut iter = s1.zip(s2);
545 ///
546 /// assert_eq!(iter.next(), Some(('a', 'd')));
547 /// assert_eq!(iter.next(), Some(('b', 'e')));
548 /// assert_eq!(iter.next(), Some(('c', 'f')));
549 /// assert_eq!(iter.next(), None);
550 /// ```
551 ///
552 /// Since the argument to `zip()` uses [`IntoIterator`], we can pass
553 /// anything that can be converted into an [`Iterator`], not just an
554 /// [`Iterator`] itself. For example, arrays (`[T]`) implement
555 /// [`IntoIterator`], and so can be passed to `zip()` directly:
556 ///
557 /// ```
558 /// let a1 = [1, 2, 3];
559 /// let a2 = [4, 5, 6];
560 ///
561 /// let mut iter = a1.into_iter().zip(a2);
562 ///
563 /// assert_eq!(iter.next(), Some((1, 4)));
564 /// assert_eq!(iter.next(), Some((2, 5)));
565 /// assert_eq!(iter.next(), Some((3, 6)));
566 /// assert_eq!(iter.next(), None);
567 /// ```
568 ///
569 /// `zip()` is often used to zip an infinite iterator to a finite one.
570 /// This works because the finite iterator will eventually return [`None`],
571 /// ending the zipper. Zipping with `(0..)` can look a lot like [`enumerate`]:
572 ///
573 /// ```
574 /// let enumerate: Vec<_> = "foo".chars().enumerate().collect();
575 ///
576 /// let zipper: Vec<_> = (0..).zip("foo".chars()).collect();
577 ///
578 /// assert_eq!((0, 'f'), enumerate[0]);
579 /// assert_eq!((0, 'f'), zipper[0]);
580 ///
581 /// assert_eq!((1, 'o'), enumerate[1]);
582 /// assert_eq!((1, 'o'), zipper[1]);
583 ///
584 /// assert_eq!((2, 'o'), enumerate[2]);
585 /// assert_eq!((2, 'o'), zipper[2]);
586 /// ```
587 ///
588 /// If both iterators have roughly equivalent syntax, it may be more readable to use [`zip`]:
589 ///
590 /// ```
591 /// use std::iter::zip;
592 ///
593 /// let a = [1, 2, 3];
594 /// let b = [2, 3, 4];
595 ///
596 /// let mut zipped = zip(
597 /// a.into_iter().map(|x| x * 2).skip(1),
598 /// b.into_iter().map(|x| x * 2).skip(1),
599 /// );
600 ///
601 /// assert_eq!(zipped.next(), Some((4, 6)));
602 /// assert_eq!(zipped.next(), Some((6, 8)));
603 /// assert_eq!(zipped.next(), None);
604 /// ```
605 ///
606 /// compared to:
607 ///
608 /// ```
609 /// # let a = [1, 2, 3];
610 /// # let b = [2, 3, 4];
611 /// #
612 /// let mut zipped = a
613 /// .into_iter()
614 /// .map(|x| x * 2)
615 /// .skip(1)
616 /// .zip(b.into_iter().map(|x| x * 2).skip(1));
617 /// #
618 /// # assert_eq!(zipped.next(), Some((4, 6)));
619 /// # assert_eq!(zipped.next(), Some((6, 8)));
620 /// # assert_eq!(zipped.next(), None);
621 /// ```
622 ///
623 /// [`enumerate`]: Iterator::enumerate
624 /// [`next`]: Iterator::next
625 /// [`zip`]: crate::iter::zip
626 #[inline]
627 #[stable(feature = "rust1", since = "1.0.0")]
628 #[cfg(not(feature = "ferrocene_certified"))]
629 fn zip<U>(self, other: U) -> Zip<Self, U::IntoIter>
630 where
631 Self: Sized,
632 U: IntoIterator,
633 {
634 Zip::new(self, other.into_iter())
635 }
636
637 /// Creates a new iterator which places a copy of `separator` between adjacent
638 /// items of the original iterator.
639 ///
640 /// In case `separator` does not implement [`Clone`] or needs to be
641 /// computed every time, use [`intersperse_with`].
642 ///
643 /// # Examples
644 ///
645 /// Basic usage:
646 ///
647 /// ```
648 /// #![feature(iter_intersperse)]
649 ///
650 /// let mut a = [0, 1, 2].into_iter().intersperse(100);
651 /// assert_eq!(a.next(), Some(0)); // The first element from `a`.
652 /// assert_eq!(a.next(), Some(100)); // The separator.
653 /// assert_eq!(a.next(), Some(1)); // The next element from `a`.
654 /// assert_eq!(a.next(), Some(100)); // The separator.
655 /// assert_eq!(a.next(), Some(2)); // The last element from `a`.
656 /// assert_eq!(a.next(), None); // The iterator is finished.
657 /// ```
658 ///
659 /// `intersperse` can be very useful to join an iterator's items using a common element:
660 /// ```
661 /// #![feature(iter_intersperse)]
662 ///
663 /// let words = ["Hello", "World", "!"];
664 /// let hello: String = words.into_iter().intersperse(" ").collect();
665 /// assert_eq!(hello, "Hello World !");
666 /// ```
667 ///
668 /// [`Clone`]: crate::clone::Clone
669 /// [`intersperse_with`]: Iterator::intersperse_with
670 #[inline]
671 #[unstable(feature = "iter_intersperse", reason = "recently added", issue = "79524")]
672 #[cfg(not(feature = "ferrocene_certified"))]
673 fn intersperse(self, separator: Self::Item) -> Intersperse<Self>
674 where
675 Self: Sized,
676 Self::Item: Clone,
677 {
678 Intersperse::new(self, separator)
679 }
680
681 /// Creates a new iterator which places an item generated by `separator`
682 /// between adjacent items of the original iterator.
683 ///
684 /// The closure will be called exactly once each time an item is placed
685 /// between two adjacent items from the underlying iterator; specifically,
686 /// the closure is not called if the underlying iterator yields less than
687 /// two items and after the last item is yielded.
688 ///
689 /// If the iterator's item implements [`Clone`], it may be easier to use
690 /// [`intersperse`].
691 ///
692 /// # Examples
693 ///
694 /// Basic usage:
695 ///
696 /// ```
697 /// #![feature(iter_intersperse)]
698 ///
699 /// #[derive(PartialEq, Debug)]
700 /// struct NotClone(usize);
701 ///
702 /// let v = [NotClone(0), NotClone(1), NotClone(2)];
703 /// let mut it = v.into_iter().intersperse_with(|| NotClone(99));
704 ///
705 /// assert_eq!(it.next(), Some(NotClone(0))); // The first element from `v`.
706 /// assert_eq!(it.next(), Some(NotClone(99))); // The separator.
707 /// assert_eq!(it.next(), Some(NotClone(1))); // The next element from `v`.
708 /// assert_eq!(it.next(), Some(NotClone(99))); // The separator.
709 /// assert_eq!(it.next(), Some(NotClone(2))); // The last element from `v`.
710 /// assert_eq!(it.next(), None); // The iterator is finished.
711 /// ```
712 ///
713 /// `intersperse_with` can be used in situations where the separator needs
714 /// to be computed:
715 /// ```
716 /// #![feature(iter_intersperse)]
717 ///
718 /// let src = ["Hello", "to", "all", "people", "!!"].iter().copied();
719 ///
720 /// // The closure mutably borrows its context to generate an item.
721 /// let mut happy_emojis = [" ❤️ ", " 😀 "].into_iter();
722 /// let separator = || happy_emojis.next().unwrap_or(" 🦀 ");
723 ///
724 /// let result = src.intersperse_with(separator).collect::<String>();
725 /// assert_eq!(result, "Hello ❤️ to 😀 all 🦀 people 🦀 !!");
726 /// ```
727 /// [`Clone`]: crate::clone::Clone
728 /// [`intersperse`]: Iterator::intersperse
729 #[inline]
730 #[unstable(feature = "iter_intersperse", reason = "recently added", issue = "79524")]
731 #[cfg(not(feature = "ferrocene_certified"))]
732 fn intersperse_with<G>(self, separator: G) -> IntersperseWith<Self, G>
733 where
734 Self: Sized,
735 G: FnMut() -> Self::Item,
736 {
737 IntersperseWith::new(self, separator)
738 }
739
740 /// Takes a closure and creates an iterator which calls that closure on each
741 /// element.
742 ///
743 /// `map()` transforms one iterator into another, by means of its argument:
744 /// something that implements [`FnMut`]. It produces a new iterator which
745 /// calls this closure on each element of the original iterator.
746 ///
747 /// If you are good at thinking in types, you can think of `map()` like this:
748 /// If you have an iterator that gives you elements of some type `A`, and
749 /// you want an iterator of some other type `B`, you can use `map()`,
750 /// passing a closure that takes an `A` and returns a `B`.
751 ///
752 /// `map()` is conceptually similar to a [`for`] loop. However, as `map()` is
753 /// lazy, it is best used when you're already working with other iterators.
754 /// If you're doing some sort of looping for a side effect, it's considered
755 /// more idiomatic to use [`for`] than `map()`.
756 ///
757 /// [`for`]: ../../book/ch03-05-control-flow.html#looping-through-a-collection-with-for
758 ///
759 /// # Examples
760 ///
761 /// Basic usage:
762 ///
763 /// ```
764 /// let a = [1, 2, 3];
765 ///
766 /// let mut iter = a.iter().map(|x| 2 * x);
767 ///
768 /// assert_eq!(iter.next(), Some(2));
769 /// assert_eq!(iter.next(), Some(4));
770 /// assert_eq!(iter.next(), Some(6));
771 /// assert_eq!(iter.next(), None);
772 /// ```
773 ///
774 /// If you're doing some sort of side effect, prefer [`for`] to `map()`:
775 ///
776 /// ```
777 /// # #![allow(unused_must_use)]
778 /// // don't do this:
779 /// (0..5).map(|x| println!("{x}"));
780 ///
781 /// // it won't even execute, as it is lazy. Rust will warn you about this.
782 ///
783 /// // Instead, use a for-loop:
784 /// for x in 0..5 {
785 /// println!("{x}");
786 /// }
787 /// ```
788 #[rustc_diagnostic_item = "IteratorMap"]
789 #[inline]
790 #[stable(feature = "rust1", since = "1.0.0")]
791 #[cfg(not(feature = "ferrocene_certified"))]
792 fn map<B, F>(self, f: F) -> Map<Self, F>
793 where
794 Self: Sized,
795 F: FnMut(Self::Item) -> B,
796 {
797 Map::new(self, f)
798 }
799
800 /// Calls a closure on each element of an iterator.
801 ///
802 /// This is equivalent to using a [`for`] loop on the iterator, although
803 /// `break` and `continue` are not possible from a closure. It's generally
804 /// more idiomatic to use a `for` loop, but `for_each` may be more legible
805 /// when processing items at the end of longer iterator chains. In some
806 /// cases `for_each` may also be faster than a loop, because it will use
807 /// internal iteration on adapters like `Chain`.
808 ///
809 /// [`for`]: ../../book/ch03-05-control-flow.html#looping-through-a-collection-with-for
810 ///
811 /// # Examples
812 ///
813 /// Basic usage:
814 ///
815 /// ```
816 /// use std::sync::mpsc::channel;
817 ///
818 /// let (tx, rx) = channel();
819 /// (0..5).map(|x| x * 2 + 1)
820 /// .for_each(move |x| tx.send(x).unwrap());
821 ///
822 /// let v: Vec<_> = rx.iter().collect();
823 /// assert_eq!(v, vec![1, 3, 5, 7, 9]);
824 /// ```
825 ///
826 /// For such a small example, a `for` loop may be cleaner, but `for_each`
827 /// might be preferable to keep a functional style with longer iterators:
828 ///
829 /// ```
830 /// (0..5).flat_map(|x| (x * 100)..(x * 110))
831 /// .enumerate()
832 /// .filter(|&(i, x)| (i + x) % 3 == 0)
833 /// .for_each(|(i, x)| println!("{i}:{x}"));
834 /// ```
835 #[inline]
836 #[stable(feature = "iterator_for_each", since = "1.21.0")]
837 #[cfg(not(feature = "ferrocene_certified"))]
838 fn for_each<F>(self, f: F)
839 where
840 Self: Sized,
841 F: FnMut(Self::Item),
842 {
843 #[inline]
844 fn call<T>(mut f: impl FnMut(T)) -> impl FnMut((), T) {
845 move |(), item| f(item)
846 }
847
848 self.fold((), call(f));
849 }
850
851 /// Creates an iterator which uses a closure to determine if an element
852 /// should be yielded.
853 ///
854 /// Given an element the closure must return `true` or `false`. The returned
855 /// iterator will yield only the elements for which the closure returns
856 /// `true`.
857 ///
858 /// # Examples
859 ///
860 /// Basic usage:
861 ///
862 /// ```
863 /// let a = [0i32, 1, 2];
864 ///
865 /// let mut iter = a.into_iter().filter(|x| x.is_positive());
866 ///
867 /// assert_eq!(iter.next(), Some(1));
868 /// assert_eq!(iter.next(), Some(2));
869 /// assert_eq!(iter.next(), None);
870 /// ```
871 ///
872 /// Because the closure passed to `filter()` takes a reference, and many
873 /// iterators iterate over references, this leads to a possibly confusing
874 /// situation, where the type of the closure is a double reference:
875 ///
876 /// ```
877 /// let s = &[0, 1, 2];
878 ///
879 /// let mut iter = s.iter().filter(|x| **x > 1); // needs two *s!
880 ///
881 /// assert_eq!(iter.next(), Some(&2));
882 /// assert_eq!(iter.next(), None);
883 /// ```
884 ///
885 /// It's common to instead use destructuring on the argument to strip away one:
886 ///
887 /// ```
888 /// let s = &[0, 1, 2];
889 ///
890 /// let mut iter = s.iter().filter(|&x| *x > 1); // both & and *
891 ///
892 /// assert_eq!(iter.next(), Some(&2));
893 /// assert_eq!(iter.next(), None);
894 /// ```
895 ///
896 /// or both:
897 ///
898 /// ```
899 /// let s = &[0, 1, 2];
900 ///
901 /// let mut iter = s.iter().filter(|&&x| x > 1); // two &s
902 ///
903 /// assert_eq!(iter.next(), Some(&2));
904 /// assert_eq!(iter.next(), None);
905 /// ```
906 ///
907 /// of these layers.
908 ///
909 /// Note that `iter.filter(f).next()` is equivalent to `iter.find(f)`.
910 #[inline]
911 #[stable(feature = "rust1", since = "1.0.0")]
912 #[rustc_diagnostic_item = "iter_filter"]
913 #[cfg(not(feature = "ferrocene_certified"))]
914 fn filter<P>(self, predicate: P) -> Filter<Self, P>
915 where
916 Self: Sized,
917 P: FnMut(&Self::Item) -> bool,
918 {
919 Filter::new(self, predicate)
920 }
921
922 /// Creates an iterator that both filters and maps.
923 ///
924 /// The returned iterator yields only the `value`s for which the supplied
925 /// closure returns `Some(value)`.
926 ///
927 /// `filter_map` can be used to make chains of [`filter`] and [`map`] more
928 /// concise. The example below shows how a `map().filter().map()` can be
929 /// shortened to a single call to `filter_map`.
930 ///
931 /// [`filter`]: Iterator::filter
932 /// [`map`]: Iterator::map
933 ///
934 /// # Examples
935 ///
936 /// Basic usage:
937 ///
938 /// ```
939 /// let a = ["1", "two", "NaN", "four", "5"];
940 ///
941 /// let mut iter = a.iter().filter_map(|s| s.parse().ok());
942 ///
943 /// assert_eq!(iter.next(), Some(1));
944 /// assert_eq!(iter.next(), Some(5));
945 /// assert_eq!(iter.next(), None);
946 /// ```
947 ///
948 /// Here's the same example, but with [`filter`] and [`map`]:
949 ///
950 /// ```
951 /// let a = ["1", "two", "NaN", "four", "5"];
952 /// let mut iter = a.iter().map(|s| s.parse()).filter(|s| s.is_ok()).map(|s| s.unwrap());
953 /// assert_eq!(iter.next(), Some(1));
954 /// assert_eq!(iter.next(), Some(5));
955 /// assert_eq!(iter.next(), None);
956 /// ```
957 #[inline]
958 #[stable(feature = "rust1", since = "1.0.0")]
959 #[cfg(not(feature = "ferrocene_certified"))]
960 fn filter_map<B, F>(self, f: F) -> FilterMap<Self, F>
961 where
962 Self: Sized,
963 F: FnMut(Self::Item) -> Option<B>,
964 {
965 FilterMap::new(self, f)
966 }
967
968 /// Creates an iterator which gives the current iteration count as well as
969 /// the next value.
970 ///
971 /// The iterator returned yields pairs `(i, val)`, where `i` is the
972 /// current index of iteration and `val` is the value returned by the
973 /// iterator.
974 ///
975 /// `enumerate()` keeps its count as a [`usize`]. If you want to count by a
976 /// different sized integer, the [`zip`] function provides similar
977 /// functionality.
978 ///
979 /// # Overflow Behavior
980 ///
981 /// The method does no guarding against overflows, so enumerating more than
982 /// [`usize::MAX`] elements either produces the wrong result or panics. If
983 /// overflow checks are enabled, a panic is guaranteed.
984 ///
985 /// # Panics
986 ///
987 /// The returned iterator might panic if the to-be-returned index would
988 /// overflow a [`usize`].
989 ///
990 /// [`zip`]: Iterator::zip
991 ///
992 /// # Examples
993 ///
994 /// ```
995 /// let a = ['a', 'b', 'c'];
996 ///
997 /// let mut iter = a.into_iter().enumerate();
998 ///
999 /// assert_eq!(iter.next(), Some((0, 'a')));
1000 /// assert_eq!(iter.next(), Some((1, 'b')));
1001 /// assert_eq!(iter.next(), Some((2, 'c')));
1002 /// assert_eq!(iter.next(), None);
1003 /// ```
1004 #[inline]
1005 #[stable(feature = "rust1", since = "1.0.0")]
1006 #[rustc_diagnostic_item = "enumerate_method"]
1007 #[cfg(not(feature = "ferrocene_certified"))]
1008 fn enumerate(self) -> Enumerate<Self>
1009 where
1010 Self: Sized,
1011 {
1012 Enumerate::new(self)
1013 }
1014
1015 /// Creates an iterator which can use the [`peek`] and [`peek_mut`] methods
1016 /// to look at the next element of the iterator without consuming it. See
1017 /// their documentation for more information.
1018 ///
1019 /// Note that the underlying iterator is still advanced when [`peek`] or
1020 /// [`peek_mut`] are called for the first time: In order to retrieve the
1021 /// next element, [`next`] is called on the underlying iterator, hence any
1022 /// side effects (i.e. anything other than fetching the next value) of
1023 /// the [`next`] method will occur.
1024 ///
1025 ///
1026 /// # Examples
1027 ///
1028 /// Basic usage:
1029 ///
1030 /// ```
1031 /// let xs = [1, 2, 3];
1032 ///
1033 /// let mut iter = xs.into_iter().peekable();
1034 ///
1035 /// // peek() lets us see into the future
1036 /// assert_eq!(iter.peek(), Some(&1));
1037 /// assert_eq!(iter.next(), Some(1));
1038 ///
1039 /// assert_eq!(iter.next(), Some(2));
1040 ///
1041 /// // we can peek() multiple times, the iterator won't advance
1042 /// assert_eq!(iter.peek(), Some(&3));
1043 /// assert_eq!(iter.peek(), Some(&3));
1044 ///
1045 /// assert_eq!(iter.next(), Some(3));
1046 ///
1047 /// // after the iterator is finished, so is peek()
1048 /// assert_eq!(iter.peek(), None);
1049 /// assert_eq!(iter.next(), None);
1050 /// ```
1051 ///
1052 /// Using [`peek_mut`] to mutate the next item without advancing the
1053 /// iterator:
1054 ///
1055 /// ```
1056 /// let xs = [1, 2, 3];
1057 ///
1058 /// let mut iter = xs.into_iter().peekable();
1059 ///
1060 /// // `peek_mut()` lets us see into the future
1061 /// assert_eq!(iter.peek_mut(), Some(&mut 1));
1062 /// assert_eq!(iter.peek_mut(), Some(&mut 1));
1063 /// assert_eq!(iter.next(), Some(1));
1064 ///
1065 /// if let Some(p) = iter.peek_mut() {
1066 /// assert_eq!(*p, 2);
1067 /// // put a value into the iterator
1068 /// *p = 1000;
1069 /// }
1070 ///
1071 /// // The value reappears as the iterator continues
1072 /// assert_eq!(iter.collect::<Vec<_>>(), vec![1000, 3]);
1073 /// ```
1074 /// [`peek`]: Peekable::peek
1075 /// [`peek_mut`]: Peekable::peek_mut
1076 /// [`next`]: Iterator::next
1077 #[inline]
1078 #[stable(feature = "rust1", since = "1.0.0")]
1079 #[cfg(not(feature = "ferrocene_certified"))]
1080 fn peekable(self) -> Peekable<Self>
1081 where
1082 Self: Sized,
1083 {
1084 Peekable::new(self)
1085 }
1086
1087 /// Creates an iterator that [`skip`]s elements based on a predicate.
1088 ///
1089 /// [`skip`]: Iterator::skip
1090 ///
1091 /// `skip_while()` takes a closure as an argument. It will call this
1092 /// closure on each element of the iterator, and ignore elements
1093 /// until it returns `false`.
1094 ///
1095 /// After `false` is returned, `skip_while()`'s job is over, and the
1096 /// rest of the elements are yielded.
1097 ///
1098 /// # Examples
1099 ///
1100 /// Basic usage:
1101 ///
1102 /// ```
1103 /// let a = [-1i32, 0, 1];
1104 ///
1105 /// let mut iter = a.into_iter().skip_while(|x| x.is_negative());
1106 ///
1107 /// assert_eq!(iter.next(), Some(0));
1108 /// assert_eq!(iter.next(), Some(1));
1109 /// assert_eq!(iter.next(), None);
1110 /// ```
1111 ///
1112 /// Because the closure passed to `skip_while()` takes a reference, and many
1113 /// iterators iterate over references, this leads to a possibly confusing
1114 /// situation, where the type of the closure argument is a double reference:
1115 ///
1116 /// ```
1117 /// let s = &[-1, 0, 1];
1118 ///
1119 /// let mut iter = s.iter().skip_while(|x| **x < 0); // need two *s!
1120 ///
1121 /// assert_eq!(iter.next(), Some(&0));
1122 /// assert_eq!(iter.next(), Some(&1));
1123 /// assert_eq!(iter.next(), None);
1124 /// ```
1125 ///
1126 /// Stopping after an initial `false`:
1127 ///
1128 /// ```
1129 /// let a = [-1, 0, 1, -2];
1130 ///
1131 /// let mut iter = a.into_iter().skip_while(|&x| x < 0);
1132 ///
1133 /// assert_eq!(iter.next(), Some(0));
1134 /// assert_eq!(iter.next(), Some(1));
1135 ///
1136 /// // while this would have been false, since we already got a false,
1137 /// // skip_while() isn't used any more
1138 /// assert_eq!(iter.next(), Some(-2));
1139 ///
1140 /// assert_eq!(iter.next(), None);
1141 /// ```
1142 #[inline]
1143 #[doc(alias = "drop_while")]
1144 #[stable(feature = "rust1", since = "1.0.0")]
1145 #[cfg(not(feature = "ferrocene_certified"))]
1146 fn skip_while<P>(self, predicate: P) -> SkipWhile<Self, P>
1147 where
1148 Self: Sized,
1149 P: FnMut(&Self::Item) -> bool,
1150 {
1151 SkipWhile::new(self, predicate)
1152 }
1153
1154 /// Creates an iterator that yields elements based on a predicate.
1155 ///
1156 /// `take_while()` takes a closure as an argument. It will call this
1157 /// closure on each element of the iterator, and yield elements
1158 /// while it returns `true`.
1159 ///
1160 /// After `false` is returned, `take_while()`'s job is over, and the
1161 /// rest of the elements are ignored.
1162 ///
1163 /// # Examples
1164 ///
1165 /// Basic usage:
1166 ///
1167 /// ```
1168 /// let a = [-1i32, 0, 1];
1169 ///
1170 /// let mut iter = a.into_iter().take_while(|x| x.is_negative());
1171 ///
1172 /// assert_eq!(iter.next(), Some(-1));
1173 /// assert_eq!(iter.next(), None);
1174 /// ```
1175 ///
1176 /// Because the closure passed to `take_while()` takes a reference, and many
1177 /// iterators iterate over references, this leads to a possibly confusing
1178 /// situation, where the type of the closure is a double reference:
1179 ///
1180 /// ```
1181 /// let s = &[-1, 0, 1];
1182 ///
1183 /// let mut iter = s.iter().take_while(|x| **x < 0); // need two *s!
1184 ///
1185 /// assert_eq!(iter.next(), Some(&-1));
1186 /// assert_eq!(iter.next(), None);
1187 /// ```
1188 ///
1189 /// Stopping after an initial `false`:
1190 ///
1191 /// ```
1192 /// let a = [-1, 0, 1, -2];
1193 ///
1194 /// let mut iter = a.into_iter().take_while(|&x| x < 0);
1195 ///
1196 /// assert_eq!(iter.next(), Some(-1));
1197 ///
1198 /// // We have more elements that are less than zero, but since we already
1199 /// // got a false, take_while() ignores the remaining elements.
1200 /// assert_eq!(iter.next(), None);
1201 /// ```
1202 ///
1203 /// Because `take_while()` needs to look at the value in order to see if it
1204 /// should be included or not, consuming iterators will see that it is
1205 /// removed:
1206 ///
1207 /// ```
1208 /// let a = [1, 2, 3, 4];
1209 /// let mut iter = a.into_iter();
1210 ///
1211 /// let result: Vec<i32> = iter.by_ref().take_while(|&n| n != 3).collect();
1212 ///
1213 /// assert_eq!(result, [1, 2]);
1214 ///
1215 /// let result: Vec<i32> = iter.collect();
1216 ///
1217 /// assert_eq!(result, [4]);
1218 /// ```
1219 ///
1220 /// The `3` is no longer there, because it was consumed in order to see if
1221 /// the iteration should stop, but wasn't placed back into the iterator.
1222 #[inline]
1223 #[stable(feature = "rust1", since = "1.0.0")]
1224 #[cfg(not(feature = "ferrocene_certified"))]
1225 fn take_while<P>(self, predicate: P) -> TakeWhile<Self, P>
1226 where
1227 Self: Sized,
1228 P: FnMut(&Self::Item) -> bool,
1229 {
1230 TakeWhile::new(self, predicate)
1231 }
1232
1233 /// Creates an iterator that both yields elements based on a predicate and maps.
1234 ///
1235 /// `map_while()` takes a closure as an argument. It will call this
1236 /// closure on each element of the iterator, and yield elements
1237 /// while it returns [`Some(_)`][`Some`].
1238 ///
1239 /// # Examples
1240 ///
1241 /// Basic usage:
1242 ///
1243 /// ```
1244 /// let a = [-1i32, 4, 0, 1];
1245 ///
1246 /// let mut iter = a.into_iter().map_while(|x| 16i32.checked_div(x));
1247 ///
1248 /// assert_eq!(iter.next(), Some(-16));
1249 /// assert_eq!(iter.next(), Some(4));
1250 /// assert_eq!(iter.next(), None);
1251 /// ```
1252 ///
1253 /// Here's the same example, but with [`take_while`] and [`map`]:
1254 ///
1255 /// [`take_while`]: Iterator::take_while
1256 /// [`map`]: Iterator::map
1257 ///
1258 /// ```
1259 /// let a = [-1i32, 4, 0, 1];
1260 ///
1261 /// let mut iter = a.into_iter()
1262 /// .map(|x| 16i32.checked_div(x))
1263 /// .take_while(|x| x.is_some())
1264 /// .map(|x| x.unwrap());
1265 ///
1266 /// assert_eq!(iter.next(), Some(-16));
1267 /// assert_eq!(iter.next(), Some(4));
1268 /// assert_eq!(iter.next(), None);
1269 /// ```
1270 ///
1271 /// Stopping after an initial [`None`]:
1272 ///
1273 /// ```
1274 /// let a = [0, 1, 2, -3, 4, 5, -6];
1275 ///
1276 /// let iter = a.into_iter().map_while(|x| u32::try_from(x).ok());
1277 /// let vec: Vec<_> = iter.collect();
1278 ///
1279 /// // We have more elements that could fit in u32 (such as 4, 5), but `map_while` returned `None` for `-3`
1280 /// // (as the `predicate` returned `None`) and `collect` stops at the first `None` encountered.
1281 /// assert_eq!(vec, [0, 1, 2]);
1282 /// ```
1283 ///
1284 /// Because `map_while()` needs to look at the value in order to see if it
1285 /// should be included or not, consuming iterators will see that it is
1286 /// removed:
1287 ///
1288 /// ```
1289 /// let a = [1, 2, -3, 4];
1290 /// let mut iter = a.into_iter();
1291 ///
1292 /// let result: Vec<u32> = iter.by_ref()
1293 /// .map_while(|n| u32::try_from(n).ok())
1294 /// .collect();
1295 ///
1296 /// assert_eq!(result, [1, 2]);
1297 ///
1298 /// let result: Vec<i32> = iter.collect();
1299 ///
1300 /// assert_eq!(result, [4]);
1301 /// ```
1302 ///
1303 /// The `-3` is no longer there, because it was consumed in order to see if
1304 /// the iteration should stop, but wasn't placed back into the iterator.
1305 ///
1306 /// Note that unlike [`take_while`] this iterator is **not** fused.
1307 /// It is also not specified what this iterator returns after the first [`None`] is returned.
1308 /// If you need a fused iterator, use [`fuse`].
1309 ///
1310 /// [`fuse`]: Iterator::fuse
1311 #[inline]
1312 #[stable(feature = "iter_map_while", since = "1.57.0")]
1313 #[cfg(not(feature = "ferrocene_certified"))]
1314 fn map_while<B, P>(self, predicate: P) -> MapWhile<Self, P>
1315 where
1316 Self: Sized,
1317 P: FnMut(Self::Item) -> Option<B>,
1318 {
1319 MapWhile::new(self, predicate)
1320 }
1321
1322 /// Creates an iterator that skips the first `n` elements.
1323 ///
1324 /// `skip(n)` skips elements until `n` elements are skipped or the end of the
1325 /// iterator is reached (whichever happens first). After that, all the remaining
1326 /// elements are yielded. In particular, if the original iterator is too short,
1327 /// then the returned iterator is empty.
1328 ///
1329 /// Rather than overriding this method directly, instead override the `nth` method.
1330 ///
1331 /// # Examples
1332 ///
1333 /// ```
1334 /// let a = [1, 2, 3];
1335 ///
1336 /// let mut iter = a.into_iter().skip(2);
1337 ///
1338 /// assert_eq!(iter.next(), Some(3));
1339 /// assert_eq!(iter.next(), None);
1340 /// ```
1341 #[inline]
1342 #[stable(feature = "rust1", since = "1.0.0")]
1343 #[cfg(not(feature = "ferrocene_certified"))]
1344 fn skip(self, n: usize) -> Skip<Self>
1345 where
1346 Self: Sized,
1347 {
1348 Skip::new(self, n)
1349 }
1350
1351 /// Creates an iterator that yields the first `n` elements, or fewer
1352 /// if the underlying iterator ends sooner.
1353 ///
1354 /// `take(n)` yields elements until `n` elements are yielded or the end of
1355 /// the iterator is reached (whichever happens first).
1356 /// The returned iterator is a prefix of length `n` if the original iterator
1357 /// contains at least `n` elements, otherwise it contains all of the
1358 /// (fewer than `n`) elements of the original iterator.
1359 ///
1360 /// # Examples
1361 ///
1362 /// Basic usage:
1363 ///
1364 /// ```
1365 /// let a = [1, 2, 3];
1366 ///
1367 /// let mut iter = a.into_iter().take(2);
1368 ///
1369 /// assert_eq!(iter.next(), Some(1));
1370 /// assert_eq!(iter.next(), Some(2));
1371 /// assert_eq!(iter.next(), None);
1372 /// ```
1373 ///
1374 /// `take()` is often used with an infinite iterator, to make it finite:
1375 ///
1376 /// ```
1377 /// let mut iter = (0..).take(3);
1378 ///
1379 /// assert_eq!(iter.next(), Some(0));
1380 /// assert_eq!(iter.next(), Some(1));
1381 /// assert_eq!(iter.next(), Some(2));
1382 /// assert_eq!(iter.next(), None);
1383 /// ```
1384 ///
1385 /// If less than `n` elements are available,
1386 /// `take` will limit itself to the size of the underlying iterator:
1387 ///
1388 /// ```
1389 /// let v = [1, 2];
1390 /// let mut iter = v.into_iter().take(5);
1391 /// assert_eq!(iter.next(), Some(1));
1392 /// assert_eq!(iter.next(), Some(2));
1393 /// assert_eq!(iter.next(), None);
1394 /// ```
1395 ///
1396 /// Use [`by_ref`] to take from the iterator without consuming it, and then
1397 /// continue using the original iterator:
1398 ///
1399 /// ```
1400 /// let mut words = ["hello", "world", "of", "Rust"].into_iter();
1401 ///
1402 /// // Take the first two words.
1403 /// let hello_world: Vec<_> = words.by_ref().take(2).collect();
1404 /// assert_eq!(hello_world, vec!["hello", "world"]);
1405 ///
1406 /// // Collect the rest of the words.
1407 /// // We can only do this because we used `by_ref` earlier.
1408 /// let of_rust: Vec<_> = words.collect();
1409 /// assert_eq!(of_rust, vec!["of", "Rust"]);
1410 /// ```
1411 ///
1412 /// [`by_ref`]: Iterator::by_ref
1413 #[doc(alias = "limit")]
1414 #[inline]
1415 #[stable(feature = "rust1", since = "1.0.0")]
1416 #[cfg(not(feature = "ferrocene_certified"))]
1417 fn take(self, n: usize) -> Take<Self>
1418 where
1419 Self: Sized,
1420 {
1421 Take::new(self, n)
1422 }
1423
1424 /// An iterator adapter which, like [`fold`], holds internal state, but
1425 /// unlike [`fold`], produces a new iterator.
1426 ///
1427 /// [`fold`]: Iterator::fold
1428 ///
1429 /// `scan()` takes two arguments: an initial value which seeds the internal
1430 /// state, and a closure with two arguments, the first being a mutable
1431 /// reference to the internal state and the second an iterator element.
1432 /// The closure can assign to the internal state to share state between
1433 /// iterations.
1434 ///
1435 /// On iteration, the closure will be applied to each element of the
1436 /// iterator and the return value from the closure, an [`Option`], is
1437 /// returned by the `next` method. Thus the closure can return
1438 /// `Some(value)` to yield `value`, or `None` to end the iteration.
1439 ///
1440 /// # Examples
1441 ///
1442 /// ```
1443 /// let a = [1, 2, 3, 4];
1444 ///
1445 /// let mut iter = a.into_iter().scan(1, |state, x| {
1446 /// // each iteration, we'll multiply the state by the element ...
1447 /// *state = *state * x;
1448 ///
1449 /// // ... and terminate if the state exceeds 6
1450 /// if *state > 6 {
1451 /// return None;
1452 /// }
1453 /// // ... else yield the negation of the state
1454 /// Some(-*state)
1455 /// });
1456 ///
1457 /// assert_eq!(iter.next(), Some(-1));
1458 /// assert_eq!(iter.next(), Some(-2));
1459 /// assert_eq!(iter.next(), Some(-6));
1460 /// assert_eq!(iter.next(), None);
1461 /// ```
1462 #[inline]
1463 #[stable(feature = "rust1", since = "1.0.0")]
1464 #[cfg(not(feature = "ferrocene_certified"))]
1465 fn scan<St, B, F>(self, initial_state: St, f: F) -> Scan<Self, St, F>
1466 where
1467 Self: Sized,
1468 F: FnMut(&mut St, Self::Item) -> Option<B>,
1469 {
1470 Scan::new(self, initial_state, f)
1471 }
1472
1473 /// Creates an iterator that works like map, but flattens nested structure.
1474 ///
1475 /// The [`map`] adapter is very useful, but only when the closure
1476 /// argument produces values. If it produces an iterator instead, there's
1477 /// an extra layer of indirection. `flat_map()` will remove this extra layer
1478 /// on its own.
1479 ///
1480 /// You can think of `flat_map(f)` as the semantic equivalent
1481 /// of [`map`]ping, and then [`flatten`]ing as in `map(f).flatten()`.
1482 ///
1483 /// Another way of thinking about `flat_map()`: [`map`]'s closure returns
1484 /// one item for each element, and `flat_map()`'s closure returns an
1485 /// iterator for each element.
1486 ///
1487 /// [`map`]: Iterator::map
1488 /// [`flatten`]: Iterator::flatten
1489 ///
1490 /// # Examples
1491 ///
1492 /// ```
1493 /// let words = ["alpha", "beta", "gamma"];
1494 ///
1495 /// // chars() returns an iterator
1496 /// let merged: String = words.iter()
1497 /// .flat_map(|s| s.chars())
1498 /// .collect();
1499 /// assert_eq!(merged, "alphabetagamma");
1500 /// ```
1501 #[inline]
1502 #[stable(feature = "rust1", since = "1.0.0")]
1503 #[cfg(not(feature = "ferrocene_certified"))]
1504 fn flat_map<U, F>(self, f: F) -> FlatMap<Self, U, F>
1505 where
1506 Self: Sized,
1507 U: IntoIterator,
1508 F: FnMut(Self::Item) -> U,
1509 {
1510 FlatMap::new(self, f)
1511 }
1512
1513 /// Creates an iterator that flattens nested structure.
1514 ///
1515 /// This is useful when you have an iterator of iterators or an iterator of
1516 /// things that can be turned into iterators and you want to remove one
1517 /// level of indirection.
1518 ///
1519 /// # Examples
1520 ///
1521 /// Basic usage:
1522 ///
1523 /// ```
1524 /// let data = vec![vec![1, 2, 3, 4], vec![5, 6]];
1525 /// let flattened: Vec<_> = data.into_iter().flatten().collect();
1526 /// assert_eq!(flattened, [1, 2, 3, 4, 5, 6]);
1527 /// ```
1528 ///
1529 /// Mapping and then flattening:
1530 ///
1531 /// ```
1532 /// let words = ["alpha", "beta", "gamma"];
1533 ///
1534 /// // chars() returns an iterator
1535 /// let merged: String = words.iter()
1536 /// .map(|s| s.chars())
1537 /// .flatten()
1538 /// .collect();
1539 /// assert_eq!(merged, "alphabetagamma");
1540 /// ```
1541 ///
1542 /// You can also rewrite this in terms of [`flat_map()`], which is preferable
1543 /// in this case since it conveys intent more clearly:
1544 ///
1545 /// ```
1546 /// let words = ["alpha", "beta", "gamma"];
1547 ///
1548 /// // chars() returns an iterator
1549 /// let merged: String = words.iter()
1550 /// .flat_map(|s| s.chars())
1551 /// .collect();
1552 /// assert_eq!(merged, "alphabetagamma");
1553 /// ```
1554 ///
1555 /// Flattening works on any `IntoIterator` type, including `Option` and `Result`:
1556 ///
1557 /// ```
1558 /// let options = vec![Some(123), Some(321), None, Some(231)];
1559 /// let flattened_options: Vec<_> = options.into_iter().flatten().collect();
1560 /// assert_eq!(flattened_options, [123, 321, 231]);
1561 ///
1562 /// let results = vec![Ok(123), Ok(321), Err(456), Ok(231)];
1563 /// let flattened_results: Vec<_> = results.into_iter().flatten().collect();
1564 /// assert_eq!(flattened_results, [123, 321, 231]);
1565 /// ```
1566 ///
1567 /// Flattening only removes one level of nesting at a time:
1568 ///
1569 /// ```
1570 /// let d3 = [[[1, 2], [3, 4]], [[5, 6], [7, 8]]];
1571 ///
1572 /// let d2: Vec<_> = d3.into_iter().flatten().collect();
1573 /// assert_eq!(d2, [[1, 2], [3, 4], [5, 6], [7, 8]]);
1574 ///
1575 /// let d1: Vec<_> = d3.into_iter().flatten().flatten().collect();
1576 /// assert_eq!(d1, [1, 2, 3, 4, 5, 6, 7, 8]);
1577 /// ```
1578 ///
1579 /// Here we see that `flatten()` does not perform a "deep" flatten.
1580 /// Instead, only one level of nesting is removed. That is, if you
1581 /// `flatten()` a three-dimensional array, the result will be
1582 /// two-dimensional and not one-dimensional. To get a one-dimensional
1583 /// structure, you have to `flatten()` again.
1584 ///
1585 /// [`flat_map()`]: Iterator::flat_map
1586 #[inline]
1587 #[stable(feature = "iterator_flatten", since = "1.29.0")]
1588 #[cfg(not(feature = "ferrocene_certified"))]
1589 fn flatten(self) -> Flatten<Self>
1590 where
1591 Self: Sized,
1592 Self::Item: IntoIterator,
1593 {
1594 Flatten::new(self)
1595 }
1596
1597 /// Calls the given function `f` for each contiguous window of size `N` over
1598 /// `self` and returns an iterator over the outputs of `f`. Like [`slice::windows()`],
1599 /// the windows during mapping overlap as well.
1600 ///
1601 /// In the following example, the closure is called three times with the
1602 /// arguments `&['a', 'b']`, `&['b', 'c']` and `&['c', 'd']` respectively.
1603 ///
1604 /// ```
1605 /// #![feature(iter_map_windows)]
1606 ///
1607 /// let strings = "abcd".chars()
1608 /// .map_windows(|[x, y]| format!("{}+{}", x, y))
1609 /// .collect::<Vec<String>>();
1610 ///
1611 /// assert_eq!(strings, vec!["a+b", "b+c", "c+d"]);
1612 /// ```
1613 ///
1614 /// Note that the const parameter `N` is usually inferred by the
1615 /// destructured argument in the closure.
1616 ///
1617 /// The returned iterator yields 𝑘 − `N` + 1 items (where 𝑘 is the number of
1618 /// items yielded by `self`). If 𝑘 is less than `N`, this method yields an
1619 /// empty iterator.
1620 ///
1621 /// The returned iterator implements [`FusedIterator`], because once `self`
1622 /// returns `None`, even if it returns a `Some(T)` again in the next iterations,
1623 /// we cannot put it into a contiguous array buffer, and thus the returned iterator
1624 /// should be fused.
1625 ///
1626 /// [`slice::windows()`]: slice::windows
1627 /// [`FusedIterator`]: crate::iter::FusedIterator
1628 ///
1629 /// # Panics
1630 ///
1631 /// Panics if `N` is zero. This check will most probably get changed to a
1632 /// compile time error before this method gets stabilized.
1633 ///
1634 /// ```should_panic
1635 /// #![feature(iter_map_windows)]
1636 ///
1637 /// let iter = std::iter::repeat(0).map_windows(|&[]| ());
1638 /// ```
1639 ///
1640 /// # Examples
1641 ///
1642 /// Building the sums of neighboring numbers.
1643 ///
1644 /// ```
1645 /// #![feature(iter_map_windows)]
1646 ///
1647 /// let mut it = [1, 3, 8, 1].iter().map_windows(|&[a, b]| a + b);
1648 /// assert_eq!(it.next(), Some(4)); // 1 + 3
1649 /// assert_eq!(it.next(), Some(11)); // 3 + 8
1650 /// assert_eq!(it.next(), Some(9)); // 8 + 1
1651 /// assert_eq!(it.next(), None);
1652 /// ```
1653 ///
1654 /// Since the elements in the following example implement `Copy`, we can
1655 /// just copy the array and get an iterator over the windows.
1656 ///
1657 /// ```
1658 /// #![feature(iter_map_windows)]
1659 ///
1660 /// let mut it = "ferris".chars().map_windows(|w: &[_; 3]| *w);
1661 /// assert_eq!(it.next(), Some(['f', 'e', 'r']));
1662 /// assert_eq!(it.next(), Some(['e', 'r', 'r']));
1663 /// assert_eq!(it.next(), Some(['r', 'r', 'i']));
1664 /// assert_eq!(it.next(), Some(['r', 'i', 's']));
1665 /// assert_eq!(it.next(), None);
1666 /// ```
1667 ///
1668 /// You can also use this function to check the sortedness of an iterator.
1669 /// For the simple case, rather use [`Iterator::is_sorted`].
1670 ///
1671 /// ```
1672 /// #![feature(iter_map_windows)]
1673 ///
1674 /// let mut it = [0.5, 1.0, 3.5, 3.0, 8.5, 8.5, f32::NAN].iter()
1675 /// .map_windows(|[a, b]| a <= b);
1676 ///
1677 /// assert_eq!(it.next(), Some(true)); // 0.5 <= 1.0
1678 /// assert_eq!(it.next(), Some(true)); // 1.0 <= 3.5
1679 /// assert_eq!(it.next(), Some(false)); // 3.5 <= 3.0
1680 /// assert_eq!(it.next(), Some(true)); // 3.0 <= 8.5
1681 /// assert_eq!(it.next(), Some(true)); // 8.5 <= 8.5
1682 /// assert_eq!(it.next(), Some(false)); // 8.5 <= NAN
1683 /// assert_eq!(it.next(), None);
1684 /// ```
1685 ///
1686 /// For non-fused iterators, they are fused after `map_windows`.
1687 ///
1688 /// ```
1689 /// #![feature(iter_map_windows)]
1690 ///
1691 /// #[derive(Default)]
1692 /// struct NonFusedIterator {
1693 /// state: i32,
1694 /// }
1695 ///
1696 /// impl Iterator for NonFusedIterator {
1697 /// type Item = i32;
1698 ///
1699 /// fn next(&mut self) -> Option<i32> {
1700 /// let val = self.state;
1701 /// self.state = self.state + 1;
1702 ///
1703 /// // yields `0..5` first, then only even numbers since `6..`.
1704 /// if val < 5 || val % 2 == 0 {
1705 /// Some(val)
1706 /// } else {
1707 /// None
1708 /// }
1709 /// }
1710 /// }
1711 ///
1712 ///
1713 /// let mut iter = NonFusedIterator::default();
1714 ///
1715 /// // yields 0..5 first.
1716 /// assert_eq!(iter.next(), Some(0));
1717 /// assert_eq!(iter.next(), Some(1));
1718 /// assert_eq!(iter.next(), Some(2));
1719 /// assert_eq!(iter.next(), Some(3));
1720 /// assert_eq!(iter.next(), Some(4));
1721 /// // then we can see our iterator going back and forth
1722 /// assert_eq!(iter.next(), None);
1723 /// assert_eq!(iter.next(), Some(6));
1724 /// assert_eq!(iter.next(), None);
1725 /// assert_eq!(iter.next(), Some(8));
1726 /// assert_eq!(iter.next(), None);
1727 ///
1728 /// // however, with `.map_windows()`, it is fused.
1729 /// let mut iter = NonFusedIterator::default()
1730 /// .map_windows(|arr: &[_; 2]| *arr);
1731 ///
1732 /// assert_eq!(iter.next(), Some([0, 1]));
1733 /// assert_eq!(iter.next(), Some([1, 2]));
1734 /// assert_eq!(iter.next(), Some([2, 3]));
1735 /// assert_eq!(iter.next(), Some([3, 4]));
1736 /// assert_eq!(iter.next(), None);
1737 ///
1738 /// // it will always return `None` after the first time.
1739 /// assert_eq!(iter.next(), None);
1740 /// assert_eq!(iter.next(), None);
1741 /// assert_eq!(iter.next(), None);
1742 /// ```
1743 #[inline]
1744 #[unstable(feature = "iter_map_windows", reason = "recently added", issue = "87155")]
1745 #[cfg(not(feature = "ferrocene_certified"))]
1746 fn map_windows<F, R, const N: usize>(self, f: F) -> MapWindows<Self, F, N>
1747 where
1748 Self: Sized,
1749 F: FnMut(&[Self::Item; N]) -> R,
1750 {
1751 MapWindows::new(self, f)
1752 }
1753
1754 /// Creates an iterator which ends after the first [`None`].
1755 ///
1756 /// After an iterator returns [`None`], future calls may or may not yield
1757 /// [`Some(T)`] again. `fuse()` adapts an iterator, ensuring that after a
1758 /// [`None`] is given, it will always return [`None`] forever.
1759 ///
1760 /// Note that the [`Fuse`] wrapper is a no-op on iterators that implement
1761 /// the [`FusedIterator`] trait. `fuse()` may therefore behave incorrectly
1762 /// if the [`FusedIterator`] trait is improperly implemented.
1763 ///
1764 /// [`Some(T)`]: Some
1765 /// [`FusedIterator`]: crate::iter::FusedIterator
1766 ///
1767 /// # Examples
1768 ///
1769 /// ```
1770 /// // an iterator which alternates between Some and None
1771 /// struct Alternate {
1772 /// state: i32,
1773 /// }
1774 ///
1775 /// impl Iterator for Alternate {
1776 /// type Item = i32;
1777 ///
1778 /// fn next(&mut self) -> Option<i32> {
1779 /// let val = self.state;
1780 /// self.state = self.state + 1;
1781 ///
1782 /// // if it's even, Some(i32), else None
1783 /// (val % 2 == 0).then_some(val)
1784 /// }
1785 /// }
1786 ///
1787 /// let mut iter = Alternate { state: 0 };
1788 ///
1789 /// // we can see our iterator going back and forth
1790 /// assert_eq!(iter.next(), Some(0));
1791 /// assert_eq!(iter.next(), None);
1792 /// assert_eq!(iter.next(), Some(2));
1793 /// assert_eq!(iter.next(), None);
1794 ///
1795 /// // however, once we fuse it...
1796 /// let mut iter = iter.fuse();
1797 ///
1798 /// assert_eq!(iter.next(), Some(4));
1799 /// assert_eq!(iter.next(), None);
1800 ///
1801 /// // it will always return `None` after the first time.
1802 /// assert_eq!(iter.next(), None);
1803 /// assert_eq!(iter.next(), None);
1804 /// assert_eq!(iter.next(), None);
1805 /// ```
1806 #[inline]
1807 #[stable(feature = "rust1", since = "1.0.0")]
1808 #[cfg(not(feature = "ferrocene_certified"))]
1809 fn fuse(self) -> Fuse<Self>
1810 where
1811 Self: Sized,
1812 {
1813 Fuse::new(self)
1814 }
1815
1816 /// Does something with each element of an iterator, passing the value on.
1817 ///
1818 /// When using iterators, you'll often chain several of them together.
1819 /// While working on such code, you might want to check out what's
1820 /// happening at various parts in the pipeline. To do that, insert
1821 /// a call to `inspect()`.
1822 ///
1823 /// It's more common for `inspect()` to be used as a debugging tool than to
1824 /// exist in your final code, but applications may find it useful in certain
1825 /// situations when errors need to be logged before being discarded.
1826 ///
1827 /// # Examples
1828 ///
1829 /// Basic usage:
1830 ///
1831 /// ```
1832 /// let a = [1, 4, 2, 3];
1833 ///
1834 /// // this iterator sequence is complex.
1835 /// let sum = a.iter()
1836 /// .cloned()
1837 /// .filter(|x| x % 2 == 0)
1838 /// .fold(0, |sum, i| sum + i);
1839 ///
1840 /// println!("{sum}");
1841 ///
1842 /// // let's add some inspect() calls to investigate what's happening
1843 /// let sum = a.iter()
1844 /// .cloned()
1845 /// .inspect(|x| println!("about to filter: {x}"))
1846 /// .filter(|x| x % 2 == 0)
1847 /// .inspect(|x| println!("made it through filter: {x}"))
1848 /// .fold(0, |sum, i| sum + i);
1849 ///
1850 /// println!("{sum}");
1851 /// ```
1852 ///
1853 /// This will print:
1854 ///
1855 /// ```text
1856 /// 6
1857 /// about to filter: 1
1858 /// about to filter: 4
1859 /// made it through filter: 4
1860 /// about to filter: 2
1861 /// made it through filter: 2
1862 /// about to filter: 3
1863 /// 6
1864 /// ```
1865 ///
1866 /// Logging errors before discarding them:
1867 ///
1868 /// ```
1869 /// let lines = ["1", "2", "a"];
1870 ///
1871 /// let sum: i32 = lines
1872 /// .iter()
1873 /// .map(|line| line.parse::<i32>())
1874 /// .inspect(|num| {
1875 /// if let Err(ref e) = *num {
1876 /// println!("Parsing error: {e}");
1877 /// }
1878 /// })
1879 /// .filter_map(Result::ok)
1880 /// .sum();
1881 ///
1882 /// println!("Sum: {sum}");
1883 /// ```
1884 ///
1885 /// This will print:
1886 ///
1887 /// ```text
1888 /// Parsing error: invalid digit found in string
1889 /// Sum: 3
1890 /// ```
1891 #[inline]
1892 #[stable(feature = "rust1", since = "1.0.0")]
1893 #[cfg(not(feature = "ferrocene_certified"))]
1894 fn inspect<F>(self, f: F) -> Inspect<Self, F>
1895 where
1896 Self: Sized,
1897 F: FnMut(&Self::Item),
1898 {
1899 Inspect::new(self, f)
1900 }
1901
1902 /// Creates a "by reference" adapter for this instance of `Iterator`.
1903 ///
1904 /// Consuming method calls (direct or indirect calls to `next`)
1905 /// on the "by reference" adapter will consume the original iterator,
1906 /// but ownership-taking methods (those with a `self` parameter)
1907 /// only take ownership of the "by reference" iterator.
1908 ///
1909 /// This is useful for applying ownership-taking methods
1910 /// (such as `take` in the example below)
1911 /// without giving up ownership of the original iterator,
1912 /// so you can use the original iterator afterwards.
1913 ///
1914 /// Uses [`impl<I: Iterator + ?Sized> Iterator for &mut I { type Item = I::Item; ...}`](https://doc.rust-lang.org/nightly/std/iter/trait.Iterator.html#impl-Iterator-for-%26mut+I).
1915 ///
1916 /// # Examples
1917 ///
1918 /// ```
1919 /// let mut words = ["hello", "world", "of", "Rust"].into_iter();
1920 ///
1921 /// // Take the first two words.
1922 /// let hello_world: Vec<_> = words.by_ref().take(2).collect();
1923 /// assert_eq!(hello_world, vec!["hello", "world"]);
1924 ///
1925 /// // Collect the rest of the words.
1926 /// // We can only do this because we used `by_ref` earlier.
1927 /// let of_rust: Vec<_> = words.collect();
1928 /// assert_eq!(of_rust, vec!["of", "Rust"]);
1929 /// ```
1930 #[stable(feature = "rust1", since = "1.0.0")]
1931 #[cfg(not(feature = "ferrocene_certified"))]
1932 fn by_ref(&mut self) -> &mut Self
1933 where
1934 Self: Sized,
1935 {
1936 self
1937 }
1938
1939 /// Transforms an iterator into a collection.
1940 ///
1941 /// `collect()` can take anything iterable, and turn it into a relevant
1942 /// collection. This is one of the more powerful methods in the standard
1943 /// library, used in a variety of contexts.
1944 ///
1945 /// The most basic pattern in which `collect()` is used is to turn one
1946 /// collection into another. You take a collection, call [`iter`] on it,
1947 /// do a bunch of transformations, and then `collect()` at the end.
1948 ///
1949 /// `collect()` can also create instances of types that are not typical
1950 /// collections. For example, a [`String`] can be built from [`char`]s,
1951 /// and an iterator of [`Result<T, E>`][`Result`] items can be collected
1952 /// into `Result<Collection<T>, E>`. See the examples below for more.
1953 ///
1954 /// Because `collect()` is so general, it can cause problems with type
1955 /// inference. As such, `collect()` is one of the few times you'll see
1956 /// the syntax affectionately known as the 'turbofish': `::<>`. This
1957 /// helps the inference algorithm understand specifically which collection
1958 /// you're trying to collect into.
1959 ///
1960 /// # Examples
1961 ///
1962 /// Basic usage:
1963 ///
1964 /// ```
1965 /// let a = [1, 2, 3];
1966 ///
1967 /// let doubled: Vec<i32> = a.iter()
1968 /// .map(|x| x * 2)
1969 /// .collect();
1970 ///
1971 /// assert_eq!(vec![2, 4, 6], doubled);
1972 /// ```
1973 ///
1974 /// Note that we needed the `: Vec<i32>` on the left-hand side. This is because
1975 /// we could collect into, for example, a [`VecDeque<T>`] instead:
1976 ///
1977 /// [`VecDeque<T>`]: ../../std/collections/struct.VecDeque.html
1978 ///
1979 /// ```
1980 /// use std::collections::VecDeque;
1981 ///
1982 /// let a = [1, 2, 3];
1983 ///
1984 /// let doubled: VecDeque<i32> = a.iter().map(|x| x * 2).collect();
1985 ///
1986 /// assert_eq!(2, doubled[0]);
1987 /// assert_eq!(4, doubled[1]);
1988 /// assert_eq!(6, doubled[2]);
1989 /// ```
1990 ///
1991 /// Using the 'turbofish' instead of annotating `doubled`:
1992 ///
1993 /// ```
1994 /// let a = [1, 2, 3];
1995 ///
1996 /// let doubled = a.iter().map(|x| x * 2).collect::<Vec<i32>>();
1997 ///
1998 /// assert_eq!(vec![2, 4, 6], doubled);
1999 /// ```
2000 ///
2001 /// Because `collect()` only cares about what you're collecting into, you can
2002 /// still use a partial type hint, `_`, with the turbofish:
2003 ///
2004 /// ```
2005 /// let a = [1, 2, 3];
2006 ///
2007 /// let doubled = a.iter().map(|x| x * 2).collect::<Vec<_>>();
2008 ///
2009 /// assert_eq!(vec![2, 4, 6], doubled);
2010 /// ```
2011 ///
2012 /// Using `collect()` to make a [`String`]:
2013 ///
2014 /// ```
2015 /// let chars = ['g', 'd', 'k', 'k', 'n'];
2016 ///
2017 /// let hello: String = chars.into_iter()
2018 /// .map(|x| x as u8)
2019 /// .map(|x| (x + 1) as char)
2020 /// .collect();
2021 ///
2022 /// assert_eq!("hello", hello);
2023 /// ```
2024 ///
2025 /// If you have a list of [`Result<T, E>`][`Result`]s, you can use `collect()` to
2026 /// see if any of them failed:
2027 ///
2028 /// ```
2029 /// let results = [Ok(1), Err("nope"), Ok(3), Err("bad")];
2030 ///
2031 /// let result: Result<Vec<_>, &str> = results.into_iter().collect();
2032 ///
2033 /// // gives us the first error
2034 /// assert_eq!(Err("nope"), result);
2035 ///
2036 /// let results = [Ok(1), Ok(3)];
2037 ///
2038 /// let result: Result<Vec<_>, &str> = results.into_iter().collect();
2039 ///
2040 /// // gives us the list of answers
2041 /// assert_eq!(Ok(vec![1, 3]), result);
2042 /// ```
2043 ///
2044 /// [`iter`]: Iterator::next
2045 /// [`String`]: ../../std/string/struct.String.html
2046 /// [`char`]: type@char
2047 #[inline]
2048 #[stable(feature = "rust1", since = "1.0.0")]
2049 #[must_use = "if you really need to exhaust the iterator, consider `.for_each(drop)` instead"]
2050 #[rustc_diagnostic_item = "iterator_collect_fn"]
2051 #[cfg(not(feature = "ferrocene_certified"))]
2052 fn collect<B: FromIterator<Self::Item>>(self) -> B
2053 where
2054 Self: Sized,
2055 {
2056 // This is too aggressive to turn on for everything all the time, but PR#137908
2057 // accidentally noticed that some rustc iterators had malformed `size_hint`s,
2058 // so this will help catch such things in debug-assertions-std runners,
2059 // even if users won't actually ever see it.
2060 if cfg!(debug_assertions) {
2061 let hint = self.size_hint();
2062 assert!(hint.1.is_none_or(|high| high >= hint.0), "Malformed size_hint {hint:?}");
2063 }
2064
2065 FromIterator::from_iter(self)
2066 }
2067
2068 /// Fallibly transforms an iterator into a collection, short circuiting if
2069 /// a failure is encountered.
2070 ///
2071 /// `try_collect()` is a variation of [`collect()`][`collect`] that allows fallible
2072 /// conversions during collection. Its main use case is simplifying conversions from
2073 /// iterators yielding [`Option<T>`][`Option`] into `Option<Collection<T>>`, or similarly for other [`Try`]
2074 /// types (e.g. [`Result`]).
2075 ///
2076 /// Importantly, `try_collect()` doesn't require that the outer [`Try`] type also implements [`FromIterator`];
2077 /// only the inner type produced on `Try::Output` must implement it. Concretely,
2078 /// this means that collecting into `ControlFlow<_, Vec<i32>>` is valid because `Vec<i32>` implements
2079 /// [`FromIterator`], even though [`ControlFlow`] doesn't.
2080 ///
2081 /// Also, if a failure is encountered during `try_collect()`, the iterator is still valid and
2082 /// may continue to be used, in which case it will continue iterating starting after the element that
2083 /// triggered the failure. See the last example below for an example of how this works.
2084 ///
2085 /// # Examples
2086 /// Successfully collecting an iterator of `Option<i32>` into `Option<Vec<i32>>`:
2087 /// ```
2088 /// #![feature(iterator_try_collect)]
2089 ///
2090 /// let u = vec![Some(1), Some(2), Some(3)];
2091 /// let v = u.into_iter().try_collect::<Vec<i32>>();
2092 /// assert_eq!(v, Some(vec![1, 2, 3]));
2093 /// ```
2094 ///
2095 /// Failing to collect in the same way:
2096 /// ```
2097 /// #![feature(iterator_try_collect)]
2098 ///
2099 /// let u = vec![Some(1), Some(2), None, Some(3)];
2100 /// let v = u.into_iter().try_collect::<Vec<i32>>();
2101 /// assert_eq!(v, None);
2102 /// ```
2103 ///
2104 /// A similar example, but with `Result`:
2105 /// ```
2106 /// #![feature(iterator_try_collect)]
2107 ///
2108 /// let u: Vec<Result<i32, ()>> = vec![Ok(1), Ok(2), Ok(3)];
2109 /// let v = u.into_iter().try_collect::<Vec<i32>>();
2110 /// assert_eq!(v, Ok(vec![1, 2, 3]));
2111 ///
2112 /// let u = vec![Ok(1), Ok(2), Err(()), Ok(3)];
2113 /// let v = u.into_iter().try_collect::<Vec<i32>>();
2114 /// assert_eq!(v, Err(()));
2115 /// ```
2116 ///
2117 /// Finally, even [`ControlFlow`] works, despite the fact that it
2118 /// doesn't implement [`FromIterator`]. Note also that the iterator can
2119 /// continue to be used, even if a failure is encountered:
2120 ///
2121 /// ```
2122 /// #![feature(iterator_try_collect)]
2123 ///
2124 /// use core::ops::ControlFlow::{Break, Continue};
2125 ///
2126 /// let u = [Continue(1), Continue(2), Break(3), Continue(4), Continue(5)];
2127 /// let mut it = u.into_iter();
2128 ///
2129 /// let v = it.try_collect::<Vec<_>>();
2130 /// assert_eq!(v, Break(3));
2131 ///
2132 /// let v = it.try_collect::<Vec<_>>();
2133 /// assert_eq!(v, Continue(vec![4, 5]));
2134 /// ```
2135 ///
2136 /// [`collect`]: Iterator::collect
2137 #[inline]
2138 #[unstable(feature = "iterator_try_collect", issue = "94047")]
2139 #[cfg(not(feature = "ferrocene_certified"))]
2140 fn try_collect<B>(&mut self) -> ChangeOutputType<Self::Item, B>
2141 where
2142 Self: Sized,
2143 Self::Item: Try<Residual: Residual<B>>,
2144 B: FromIterator<<Self::Item as Try>::Output>,
2145 {
2146 try_process(ByRefSized(self), |i| i.collect())
2147 }
2148
2149 /// Collects all the items from an iterator into a collection.
2150 ///
2151 /// This method consumes the iterator and adds all its items to the
2152 /// passed collection. The collection is then returned, so the call chain
2153 /// can be continued.
2154 ///
2155 /// This is useful when you already have a collection and want to add
2156 /// the iterator items to it.
2157 ///
2158 /// This method is a convenience method to call [Extend::extend](trait.Extend.html),
2159 /// but instead of being called on a collection, it's called on an iterator.
2160 ///
2161 /// # Examples
2162 ///
2163 /// Basic usage:
2164 ///
2165 /// ```
2166 /// #![feature(iter_collect_into)]
2167 ///
2168 /// let a = [1, 2, 3];
2169 /// let mut vec: Vec::<i32> = vec![0, 1];
2170 ///
2171 /// a.iter().map(|x| x * 2).collect_into(&mut vec);
2172 /// a.iter().map(|x| x * 10).collect_into(&mut vec);
2173 ///
2174 /// assert_eq!(vec, vec![0, 1, 2, 4, 6, 10, 20, 30]);
2175 /// ```
2176 ///
2177 /// `Vec` can have a manual set capacity to avoid reallocating it:
2178 ///
2179 /// ```
2180 /// #![feature(iter_collect_into)]
2181 ///
2182 /// let a = [1, 2, 3];
2183 /// let mut vec: Vec::<i32> = Vec::with_capacity(6);
2184 ///
2185 /// a.iter().map(|x| x * 2).collect_into(&mut vec);
2186 /// a.iter().map(|x| x * 10).collect_into(&mut vec);
2187 ///
2188 /// assert_eq!(6, vec.capacity());
2189 /// assert_eq!(vec, vec![2, 4, 6, 10, 20, 30]);
2190 /// ```
2191 ///
2192 /// The returned mutable reference can be used to continue the call chain:
2193 ///
2194 /// ```
2195 /// #![feature(iter_collect_into)]
2196 ///
2197 /// let a = [1, 2, 3];
2198 /// let mut vec: Vec::<i32> = Vec::with_capacity(6);
2199 ///
2200 /// let count = a.iter().collect_into(&mut vec).iter().count();
2201 ///
2202 /// assert_eq!(count, vec.len());
2203 /// assert_eq!(vec, vec![1, 2, 3]);
2204 ///
2205 /// let count = a.iter().collect_into(&mut vec).iter().count();
2206 ///
2207 /// assert_eq!(count, vec.len());
2208 /// assert_eq!(vec, vec![1, 2, 3, 1, 2, 3]);
2209 /// ```
2210 #[inline]
2211 #[unstable(feature = "iter_collect_into", reason = "new API", issue = "94780")]
2212 #[cfg(not(feature = "ferrocene_certified"))]
2213 fn collect_into<E: Extend<Self::Item>>(self, collection: &mut E) -> &mut E
2214 where
2215 Self: Sized,
2216 {
2217 collection.extend(self);
2218 collection
2219 }
2220
2221 /// Consumes an iterator, creating two collections from it.
2222 ///
2223 /// The predicate passed to `partition()` can return `true`, or `false`.
2224 /// `partition()` returns a pair, all of the elements for which it returned
2225 /// `true`, and all of the elements for which it returned `false`.
2226 ///
2227 /// See also [`is_partitioned()`] and [`partition_in_place()`].
2228 ///
2229 /// [`is_partitioned()`]: Iterator::is_partitioned
2230 /// [`partition_in_place()`]: Iterator::partition_in_place
2231 ///
2232 /// # Examples
2233 ///
2234 /// ```
2235 /// let a = [1, 2, 3];
2236 ///
2237 /// let (even, odd): (Vec<_>, Vec<_>) = a
2238 /// .into_iter()
2239 /// .partition(|n| n % 2 == 0);
2240 ///
2241 /// assert_eq!(even, [2]);
2242 /// assert_eq!(odd, [1, 3]);
2243 /// ```
2244 #[stable(feature = "rust1", since = "1.0.0")]
2245 #[cfg(not(feature = "ferrocene_certified"))]
2246 fn partition<B, F>(self, f: F) -> (B, B)
2247 where
2248 Self: Sized,
2249 B: Default + Extend<Self::Item>,
2250 F: FnMut(&Self::Item) -> bool,
2251 {
2252 #[inline]
2253 fn extend<'a, T, B: Extend<T>>(
2254 mut f: impl FnMut(&T) -> bool + 'a,
2255 left: &'a mut B,
2256 right: &'a mut B,
2257 ) -> impl FnMut((), T) + 'a {
2258 move |(), x| {
2259 if f(&x) {
2260 left.extend_one(x);
2261 } else {
2262 right.extend_one(x);
2263 }
2264 }
2265 }
2266
2267 let mut left: B = Default::default();
2268 let mut right: B = Default::default();
2269
2270 self.fold((), extend(f, &mut left, &mut right));
2271
2272 (left, right)
2273 }
2274
2275 /// Reorders the elements of this iterator *in-place* according to the given predicate,
2276 /// such that all those that return `true` precede all those that return `false`.
2277 /// Returns the number of `true` elements found.
2278 ///
2279 /// The relative order of partitioned items is not maintained.
2280 ///
2281 /// # Current implementation
2282 ///
2283 /// The current algorithm tries to find the first element for which the predicate evaluates
2284 /// to false and the last element for which it evaluates to true, and repeatedly swaps them.
2285 ///
2286 /// Time complexity: *O*(*n*)
2287 ///
2288 /// See also [`is_partitioned()`] and [`partition()`].
2289 ///
2290 /// [`is_partitioned()`]: Iterator::is_partitioned
2291 /// [`partition()`]: Iterator::partition
2292 ///
2293 /// # Examples
2294 ///
2295 /// ```
2296 /// #![feature(iter_partition_in_place)]
2297 ///
2298 /// let mut a = [1, 2, 3, 4, 5, 6, 7];
2299 ///
2300 /// // Partition in-place between evens and odds
2301 /// let i = a.iter_mut().partition_in_place(|n| n % 2 == 0);
2302 ///
2303 /// assert_eq!(i, 3);
2304 /// assert!(a[..i].iter().all(|n| n % 2 == 0)); // evens
2305 /// assert!(a[i..].iter().all(|n| n % 2 == 1)); // odds
2306 /// ```
2307 #[unstable(feature = "iter_partition_in_place", reason = "new API", issue = "62543")]
2308 #[cfg(not(feature = "ferrocene_certified"))]
2309 fn partition_in_place<'a, T: 'a, P>(mut self, ref mut predicate: P) -> usize
2310 where
2311 Self: Sized + DoubleEndedIterator<Item = &'a mut T>,
2312 P: FnMut(&T) -> bool,
2313 {
2314 // FIXME: should we worry about the count overflowing? The only way to have more than
2315 // `usize::MAX` mutable references is with ZSTs, which aren't useful to partition...
2316
2317 // These closure "factory" functions exist to avoid genericity in `Self`.
2318
2319 #[inline]
2320 fn is_false<'a, T>(
2321 predicate: &'a mut impl FnMut(&T) -> bool,
2322 true_count: &'a mut usize,
2323 ) -> impl FnMut(&&mut T) -> bool + 'a {
2324 move |x| {
2325 let p = predicate(&**x);
2326 *true_count += p as usize;
2327 !p
2328 }
2329 }
2330
2331 #[inline]
2332 fn is_true<T>(predicate: &mut impl FnMut(&T) -> bool) -> impl FnMut(&&mut T) -> bool + '_ {
2333 move |x| predicate(&**x)
2334 }
2335
2336 // Repeatedly find the first `false` and swap it with the last `true`.
2337 let mut true_count = 0;
2338 while let Some(head) = self.find(is_false(predicate, &mut true_count)) {
2339 if let Some(tail) = self.rfind(is_true(predicate)) {
2340 crate::mem::swap(head, tail);
2341 true_count += 1;
2342 } else {
2343 break;
2344 }
2345 }
2346 true_count
2347 }
2348
2349 /// Checks if the elements of this iterator are partitioned according to the given predicate,
2350 /// such that all those that return `true` precede all those that return `false`.
2351 ///
2352 /// See also [`partition()`] and [`partition_in_place()`].
2353 ///
2354 /// [`partition()`]: Iterator::partition
2355 /// [`partition_in_place()`]: Iterator::partition_in_place
2356 ///
2357 /// # Examples
2358 ///
2359 /// ```
2360 /// #![feature(iter_is_partitioned)]
2361 ///
2362 /// assert!("Iterator".chars().is_partitioned(char::is_uppercase));
2363 /// assert!(!"IntoIterator".chars().is_partitioned(char::is_uppercase));
2364 /// ```
2365 #[unstable(feature = "iter_is_partitioned", reason = "new API", issue = "62544")]
2366 #[cfg(not(feature = "ferrocene_certified"))]
2367 fn is_partitioned<P>(mut self, mut predicate: P) -> bool
2368 where
2369 Self: Sized,
2370 P: FnMut(Self::Item) -> bool,
2371 {
2372 // Either all items test `true`, or the first clause stops at `false`
2373 // and we check that there are no more `true` items after that.
2374 self.all(&mut predicate) || !self.any(predicate)
2375 }
2376
2377 /// An iterator method that applies a function as long as it returns
2378 /// successfully, producing a single, final value.
2379 ///
2380 /// `try_fold()` takes two arguments: an initial value, and a closure with
2381 /// two arguments: an 'accumulator', and an element. The closure either
2382 /// returns successfully, with the value that the accumulator should have
2383 /// for the next iteration, or it returns failure, with an error value that
2384 /// is propagated back to the caller immediately (short-circuiting).
2385 ///
2386 /// The initial value is the value the accumulator will have on the first
2387 /// call. If applying the closure succeeded against every element of the
2388 /// iterator, `try_fold()` returns the final accumulator as success.
2389 ///
2390 /// Folding is useful whenever you have a collection of something, and want
2391 /// to produce a single value from it.
2392 ///
2393 /// # Note to Implementors
2394 ///
2395 /// Several of the other (forward) methods have default implementations in
2396 /// terms of this one, so try to implement this explicitly if it can
2397 /// do something better than the default `for` loop implementation.
2398 ///
2399 /// In particular, try to have this call `try_fold()` on the internal parts
2400 /// from which this iterator is composed. If multiple calls are needed,
2401 /// the `?` operator may be convenient for chaining the accumulator value
2402 /// along, but beware any invariants that need to be upheld before those
2403 /// early returns. This is a `&mut self` method, so iteration needs to be
2404 /// resumable after hitting an error here.
2405 ///
2406 /// # Examples
2407 ///
2408 /// Basic usage:
2409 ///
2410 /// ```
2411 /// let a = [1, 2, 3];
2412 ///
2413 /// // the checked sum of all of the elements of the array
2414 /// let sum = a.into_iter().try_fold(0i8, |acc, x| acc.checked_add(x));
2415 ///
2416 /// assert_eq!(sum, Some(6));
2417 /// ```
2418 ///
2419 /// Short-circuiting:
2420 ///
2421 /// ```
2422 /// let a = [10, 20, 30, 100, 40, 50];
2423 /// let mut iter = a.into_iter();
2424 ///
2425 /// // This sum overflows when adding the 100 element
2426 /// let sum = iter.try_fold(0i8, |acc, x| acc.checked_add(x));
2427 /// assert_eq!(sum, None);
2428 ///
2429 /// // Because it short-circuited, the remaining elements are still
2430 /// // available through the iterator.
2431 /// assert_eq!(iter.len(), 2);
2432 /// assert_eq!(iter.next(), Some(40));
2433 /// ```
2434 ///
2435 /// While you cannot `break` from a closure, the [`ControlFlow`] type allows
2436 /// a similar idea:
2437 ///
2438 /// ```
2439 /// use std::ops::ControlFlow;
2440 ///
2441 /// let triangular = (1..30).try_fold(0_i8, |prev, x| {
2442 /// if let Some(next) = prev.checked_add(x) {
2443 /// ControlFlow::Continue(next)
2444 /// } else {
2445 /// ControlFlow::Break(prev)
2446 /// }
2447 /// });
2448 /// assert_eq!(triangular, ControlFlow::Break(120));
2449 ///
2450 /// let triangular = (1..30).try_fold(0_u64, |prev, x| {
2451 /// if let Some(next) = prev.checked_add(x) {
2452 /// ControlFlow::Continue(next)
2453 /// } else {
2454 /// ControlFlow::Break(prev)
2455 /// }
2456 /// });
2457 /// assert_eq!(triangular, ControlFlow::Continue(435));
2458 /// ```
2459 #[inline]
2460 #[stable(feature = "iterator_try_fold", since = "1.27.0")]
2461 #[cfg(not(feature = "ferrocene_certified"))]
2462 fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
2463 where
2464 Self: Sized,
2465 F: FnMut(B, Self::Item) -> R,
2466 R: Try<Output = B>,
2467 {
2468 let mut accum = init;
2469 while let Some(x) = self.next() {
2470 accum = f(accum, x)?;
2471 }
2472 try { accum }
2473 }
2474
2475 /// An iterator method that applies a fallible function to each item in the
2476 /// iterator, stopping at the first error and returning that error.
2477 ///
2478 /// This can also be thought of as the fallible form of [`for_each()`]
2479 /// or as the stateless version of [`try_fold()`].
2480 ///
2481 /// [`for_each()`]: Iterator::for_each
2482 /// [`try_fold()`]: Iterator::try_fold
2483 ///
2484 /// # Examples
2485 ///
2486 /// ```
2487 /// use std::fs::rename;
2488 /// use std::io::{stdout, Write};
2489 /// use std::path::Path;
2490 ///
2491 /// let data = ["no_tea.txt", "stale_bread.json", "torrential_rain.png"];
2492 ///
2493 /// let res = data.iter().try_for_each(|x| writeln!(stdout(), "{x}"));
2494 /// assert!(res.is_ok());
2495 ///
2496 /// let mut it = data.iter().cloned();
2497 /// let res = it.try_for_each(|x| rename(x, Path::new(x).with_extension("old")));
2498 /// assert!(res.is_err());
2499 /// // It short-circuited, so the remaining items are still in the iterator:
2500 /// assert_eq!(it.next(), Some("stale_bread.json"));
2501 /// ```
2502 ///
2503 /// The [`ControlFlow`] type can be used with this method for the situations
2504 /// in which you'd use `break` and `continue` in a normal loop:
2505 ///
2506 /// ```
2507 /// use std::ops::ControlFlow;
2508 ///
2509 /// let r = (2..100).try_for_each(|x| {
2510 /// if 323 % x == 0 {
2511 /// return ControlFlow::Break(x)
2512 /// }
2513 ///
2514 /// ControlFlow::Continue(())
2515 /// });
2516 /// assert_eq!(r, ControlFlow::Break(17));
2517 /// ```
2518 #[inline]
2519 #[stable(feature = "iterator_try_fold", since = "1.27.0")]
2520 #[cfg(not(feature = "ferrocene_certified"))]
2521 fn try_for_each<F, R>(&mut self, f: F) -> R
2522 where
2523 Self: Sized,
2524 F: FnMut(Self::Item) -> R,
2525 R: Try<Output = ()>,
2526 {
2527 #[inline]
2528 fn call<T, R>(mut f: impl FnMut(T) -> R) -> impl FnMut((), T) -> R {
2529 move |(), x| f(x)
2530 }
2531
2532 self.try_fold((), call(f))
2533 }
2534
2535 /// Folds every element into an accumulator by applying an operation,
2536 /// returning the final result.
2537 ///
2538 /// `fold()` takes two arguments: an initial value, and a closure with two
2539 /// arguments: an 'accumulator', and an element. The closure returns the value that
2540 /// the accumulator should have for the next iteration.
2541 ///
2542 /// The initial value is the value the accumulator will have on the first
2543 /// call.
2544 ///
2545 /// After applying this closure to every element of the iterator, `fold()`
2546 /// returns the accumulator.
2547 ///
2548 /// This operation is sometimes called 'reduce' or 'inject'.
2549 ///
2550 /// Folding is useful whenever you have a collection of something, and want
2551 /// to produce a single value from it.
2552 ///
2553 /// Note: `fold()`, and similar methods that traverse the entire iterator,
2554 /// might not terminate for infinite iterators, even on traits for which a
2555 /// result is determinable in finite time.
2556 ///
2557 /// Note: [`reduce()`] can be used to use the first element as the initial
2558 /// value, if the accumulator type and item type is the same.
2559 ///
2560 /// Note: `fold()` combines elements in a *left-associative* fashion. For associative
2561 /// operators like `+`, the order the elements are combined in is not important, but for non-associative
2562 /// operators like `-` the order will affect the final result.
2563 /// For a *right-associative* version of `fold()`, see [`DoubleEndedIterator::rfold()`].
2564 ///
2565 /// # Note to Implementors
2566 ///
2567 /// Several of the other (forward) methods have default implementations in
2568 /// terms of this one, so try to implement this explicitly if it can
2569 /// do something better than the default `for` loop implementation.
2570 ///
2571 /// In particular, try to have this call `fold()` on the internal parts
2572 /// from which this iterator is composed.
2573 ///
2574 /// # Examples
2575 ///
2576 /// Basic usage:
2577 ///
2578 /// ```
2579 /// let a = [1, 2, 3];
2580 ///
2581 /// // the sum of all of the elements of the array
2582 /// let sum = a.iter().fold(0, |acc, x| acc + x);
2583 ///
2584 /// assert_eq!(sum, 6);
2585 /// ```
2586 ///
2587 /// Let's walk through each step of the iteration here:
2588 ///
2589 /// | element | acc | x | result |
2590 /// |---------|-----|---|--------|
2591 /// | | 0 | | |
2592 /// | 1 | 0 | 1 | 1 |
2593 /// | 2 | 1 | 2 | 3 |
2594 /// | 3 | 3 | 3 | 6 |
2595 ///
2596 /// And so, our final result, `6`.
2597 ///
2598 /// This example demonstrates the left-associative nature of `fold()`:
2599 /// it builds a string, starting with an initial value
2600 /// and continuing with each element from the front until the back:
2601 ///
2602 /// ```
2603 /// let numbers = [1, 2, 3, 4, 5];
2604 ///
2605 /// let zero = "0".to_string();
2606 ///
2607 /// let result = numbers.iter().fold(zero, |acc, &x| {
2608 /// format!("({acc} + {x})")
2609 /// });
2610 ///
2611 /// assert_eq!(result, "(((((0 + 1) + 2) + 3) + 4) + 5)");
2612 /// ```
2613 /// It's common for people who haven't used iterators a lot to
2614 /// use a `for` loop with a list of things to build up a result. Those
2615 /// can be turned into `fold()`s:
2616 ///
2617 /// [`for`]: ../../book/ch03-05-control-flow.html#looping-through-a-collection-with-for
2618 ///
2619 /// ```
2620 /// let numbers = [1, 2, 3, 4, 5];
2621 ///
2622 /// let mut result = 0;
2623 ///
2624 /// // for loop:
2625 /// for i in &numbers {
2626 /// result = result + i;
2627 /// }
2628 ///
2629 /// // fold:
2630 /// let result2 = numbers.iter().fold(0, |acc, &x| acc + x);
2631 ///
2632 /// // they're the same
2633 /// assert_eq!(result, result2);
2634 /// ```
2635 ///
2636 /// [`reduce()`]: Iterator::reduce
2637 #[doc(alias = "inject", alias = "foldl")]
2638 #[inline]
2639 #[stable(feature = "rust1", since = "1.0.0")]
2640 #[cfg(not(feature = "ferrocene_certified"))]
2641 fn fold<B, F>(mut self, init: B, mut f: F) -> B
2642 where
2643 Self: Sized,
2644 F: FnMut(B, Self::Item) -> B,
2645 {
2646 let mut accum = init;
2647 while let Some(x) = self.next() {
2648 accum = f(accum, x);
2649 }
2650 accum
2651 }
2652
2653 /// Reduces the elements to a single one, by repeatedly applying a reducing
2654 /// operation.
2655 ///
2656 /// If the iterator is empty, returns [`None`]; otherwise, returns the
2657 /// result of the reduction.
2658 ///
2659 /// The reducing function is a closure with two arguments: an 'accumulator', and an element.
2660 /// For iterators with at least one element, this is the same as [`fold()`]
2661 /// with the first element of the iterator as the initial accumulator value, folding
2662 /// every subsequent element into it.
2663 ///
2664 /// [`fold()`]: Iterator::fold
2665 ///
2666 /// # Example
2667 ///
2668 /// ```
2669 /// let reduced: i32 = (1..10).reduce(|acc, e| acc + e).unwrap_or(0);
2670 /// assert_eq!(reduced, 45);
2671 ///
2672 /// // Which is equivalent to doing it with `fold`:
2673 /// let folded: i32 = (1..10).fold(0, |acc, e| acc + e);
2674 /// assert_eq!(reduced, folded);
2675 /// ```
2676 #[inline]
2677 #[stable(feature = "iterator_fold_self", since = "1.51.0")]
2678 #[cfg(not(feature = "ferrocene_certified"))]
2679 fn reduce<F>(mut self, f: F) -> Option<Self::Item>
2680 where
2681 Self: Sized,
2682 F: FnMut(Self::Item, Self::Item) -> Self::Item,
2683 {
2684 let first = self.next()?;
2685 Some(self.fold(first, f))
2686 }
2687
2688 /// Reduces the elements to a single one by repeatedly applying a reducing operation. If the
2689 /// closure returns a failure, the failure is propagated back to the caller immediately.
2690 ///
2691 /// The return type of this method depends on the return type of the closure. If the closure
2692 /// returns `Result<Self::Item, E>`, then this function will return `Result<Option<Self::Item>,
2693 /// E>`. If the closure returns `Option<Self::Item>`, then this function will return
2694 /// `Option<Option<Self::Item>>`.
2695 ///
2696 /// When called on an empty iterator, this function will return either `Some(None)` or
2697 /// `Ok(None)` depending on the type of the provided closure.
2698 ///
2699 /// For iterators with at least one element, this is essentially the same as calling
2700 /// [`try_fold()`] with the first element of the iterator as the initial accumulator value.
2701 ///
2702 /// [`try_fold()`]: Iterator::try_fold
2703 ///
2704 /// # Examples
2705 ///
2706 /// Safely calculate the sum of a series of numbers:
2707 ///
2708 /// ```
2709 /// #![feature(iterator_try_reduce)]
2710 ///
2711 /// let numbers: Vec<usize> = vec![10, 20, 5, 23, 0];
2712 /// let sum = numbers.into_iter().try_reduce(|x, y| x.checked_add(y));
2713 /// assert_eq!(sum, Some(Some(58)));
2714 /// ```
2715 ///
2716 /// Determine when a reduction short circuited:
2717 ///
2718 /// ```
2719 /// #![feature(iterator_try_reduce)]
2720 ///
2721 /// let numbers = vec![1, 2, 3, usize::MAX, 4, 5];
2722 /// let sum = numbers.into_iter().try_reduce(|x, y| x.checked_add(y));
2723 /// assert_eq!(sum, None);
2724 /// ```
2725 ///
2726 /// Determine when a reduction was not performed because there are no elements:
2727 ///
2728 /// ```
2729 /// #![feature(iterator_try_reduce)]
2730 ///
2731 /// let numbers: Vec<usize> = Vec::new();
2732 /// let sum = numbers.into_iter().try_reduce(|x, y| x.checked_add(y));
2733 /// assert_eq!(sum, Some(None));
2734 /// ```
2735 ///
2736 /// Use a [`Result`] instead of an [`Option`]:
2737 ///
2738 /// ```
2739 /// #![feature(iterator_try_reduce)]
2740 ///
2741 /// let numbers = vec!["1", "2", "3", "4", "5"];
2742 /// let max: Result<Option<_>, <usize as std::str::FromStr>::Err> =
2743 /// numbers.into_iter().try_reduce(|x, y| {
2744 /// if x.parse::<usize>()? > y.parse::<usize>()? { Ok(x) } else { Ok(y) }
2745 /// });
2746 /// assert_eq!(max, Ok(Some("5")));
2747 /// ```
2748 #[inline]
2749 #[unstable(feature = "iterator_try_reduce", reason = "new API", issue = "87053")]
2750 #[cfg(not(feature = "ferrocene_certified"))]
2751 fn try_reduce<R>(
2752 &mut self,
2753 f: impl FnMut(Self::Item, Self::Item) -> R,
2754 ) -> ChangeOutputType<R, Option<R::Output>>
2755 where
2756 Self: Sized,
2757 R: Try<Output = Self::Item, Residual: Residual<Option<Self::Item>>>,
2758 {
2759 let first = match self.next() {
2760 Some(i) => i,
2761 None => return Try::from_output(None),
2762 };
2763
2764 match self.try_fold(first, f).branch() {
2765 ControlFlow::Break(r) => FromResidual::from_residual(r),
2766 ControlFlow::Continue(i) => Try::from_output(Some(i)),
2767 }
2768 }
2769
2770 /// Tests if every element of the iterator matches a predicate.
2771 ///
2772 /// `all()` takes a closure that returns `true` or `false`. It applies
2773 /// this closure to each element of the iterator, and if they all return
2774 /// `true`, then so does `all()`. If any of them return `false`, it
2775 /// returns `false`.
2776 ///
2777 /// `all()` is short-circuiting; in other words, it will stop processing
2778 /// as soon as it finds a `false`, given that no matter what else happens,
2779 /// the result will also be `false`.
2780 ///
2781 /// An empty iterator returns `true`.
2782 ///
2783 /// # Examples
2784 ///
2785 /// Basic usage:
2786 ///
2787 /// ```
2788 /// let a = [1, 2, 3];
2789 ///
2790 /// assert!(a.into_iter().all(|x| x > 0));
2791 ///
2792 /// assert!(!a.into_iter().all(|x| x > 2));
2793 /// ```
2794 ///
2795 /// Stopping at the first `false`:
2796 ///
2797 /// ```
2798 /// let a = [1, 2, 3];
2799 ///
2800 /// let mut iter = a.into_iter();
2801 ///
2802 /// assert!(!iter.all(|x| x != 2));
2803 ///
2804 /// // we can still use `iter`, as there are more elements.
2805 /// assert_eq!(iter.next(), Some(3));
2806 /// ```
2807 #[inline]
2808 #[stable(feature = "rust1", since = "1.0.0")]
2809 #[cfg(not(feature = "ferrocene_certified"))]
2810 fn all<F>(&mut self, f: F) -> bool
2811 where
2812 Self: Sized,
2813 F: FnMut(Self::Item) -> bool,
2814 {
2815 #[inline]
2816 fn check<T>(mut f: impl FnMut(T) -> bool) -> impl FnMut((), T) -> ControlFlow<()> {
2817 move |(), x| {
2818 if f(x) { ControlFlow::Continue(()) } else { ControlFlow::Break(()) }
2819 }
2820 }
2821 self.try_fold((), check(f)) == ControlFlow::Continue(())
2822 }
2823
2824 /// Tests if any element of the iterator matches a predicate.
2825 ///
2826 /// `any()` takes a closure that returns `true` or `false`. It applies
2827 /// this closure to each element of the iterator, and if any of them return
2828 /// `true`, then so does `any()`. If they all return `false`, it
2829 /// returns `false`.
2830 ///
2831 /// `any()` is short-circuiting; in other words, it will stop processing
2832 /// as soon as it finds a `true`, given that no matter what else happens,
2833 /// the result will also be `true`.
2834 ///
2835 /// An empty iterator returns `false`.
2836 ///
2837 /// # Examples
2838 ///
2839 /// Basic usage:
2840 ///
2841 /// ```
2842 /// let a = [1, 2, 3];
2843 ///
2844 /// assert!(a.into_iter().any(|x| x > 0));
2845 ///
2846 /// assert!(!a.into_iter().any(|x| x > 5));
2847 /// ```
2848 ///
2849 /// Stopping at the first `true`:
2850 ///
2851 /// ```
2852 /// let a = [1, 2, 3];
2853 ///
2854 /// let mut iter = a.into_iter();
2855 ///
2856 /// assert!(iter.any(|x| x != 2));
2857 ///
2858 /// // we can still use `iter`, as there are more elements.
2859 /// assert_eq!(iter.next(), Some(2));
2860 /// ```
2861 #[inline]
2862 #[stable(feature = "rust1", since = "1.0.0")]
2863 #[cfg(not(feature = "ferrocene_certified"))]
2864 fn any<F>(&mut self, f: F) -> bool
2865 where
2866 Self: Sized,
2867 F: FnMut(Self::Item) -> bool,
2868 {
2869 #[inline]
2870 fn check<T>(mut f: impl FnMut(T) -> bool) -> impl FnMut((), T) -> ControlFlow<()> {
2871 move |(), x| {
2872 if f(x) { ControlFlow::Break(()) } else { ControlFlow::Continue(()) }
2873 }
2874 }
2875
2876 self.try_fold((), check(f)) == ControlFlow::Break(())
2877 }
2878
2879 /// Searches for an element of an iterator that satisfies a predicate.
2880 ///
2881 /// `find()` takes a closure that returns `true` or `false`. It applies
2882 /// this closure to each element of the iterator, and if any of them return
2883 /// `true`, then `find()` returns [`Some(element)`]. If they all return
2884 /// `false`, it returns [`None`].
2885 ///
2886 /// `find()` is short-circuiting; in other words, it will stop processing
2887 /// as soon as the closure returns `true`.
2888 ///
2889 /// Because `find()` takes a reference, and many iterators iterate over
2890 /// references, this leads to a possibly confusing situation where the
2891 /// argument is a double reference. You can see this effect in the
2892 /// examples below, with `&&x`.
2893 ///
2894 /// If you need the index of the element, see [`position()`].
2895 ///
2896 /// [`Some(element)`]: Some
2897 /// [`position()`]: Iterator::position
2898 ///
2899 /// # Examples
2900 ///
2901 /// Basic usage:
2902 ///
2903 /// ```
2904 /// let a = [1, 2, 3];
2905 ///
2906 /// assert_eq!(a.into_iter().find(|&x| x == 2), Some(2));
2907 /// assert_eq!(a.into_iter().find(|&x| x == 5), None);
2908 /// ```
2909 ///
2910 /// Stopping at the first `true`:
2911 ///
2912 /// ```
2913 /// let a = [1, 2, 3];
2914 ///
2915 /// let mut iter = a.into_iter();
2916 ///
2917 /// assert_eq!(iter.find(|&x| x == 2), Some(2));
2918 ///
2919 /// // we can still use `iter`, as there are more elements.
2920 /// assert_eq!(iter.next(), Some(3));
2921 /// ```
2922 ///
2923 /// Note that `iter.find(f)` is equivalent to `iter.filter(f).next()`.
2924 #[inline]
2925 #[stable(feature = "rust1", since = "1.0.0")]
2926 #[cfg(not(feature = "ferrocene_certified"))]
2927 fn find<P>(&mut self, predicate: P) -> Option<Self::Item>
2928 where
2929 Self: Sized,
2930 P: FnMut(&Self::Item) -> bool,
2931 {
2932 #[inline]
2933 fn check<T>(mut predicate: impl FnMut(&T) -> bool) -> impl FnMut((), T) -> ControlFlow<T> {
2934 move |(), x| {
2935 if predicate(&x) { ControlFlow::Break(x) } else { ControlFlow::Continue(()) }
2936 }
2937 }
2938
2939 self.try_fold((), check(predicate)).break_value()
2940 }
2941
2942 /// Applies function to the elements of iterator and returns
2943 /// the first non-none result.
2944 ///
2945 /// `iter.find_map(f)` is equivalent to `iter.filter_map(f).next()`.
2946 ///
2947 /// # Examples
2948 ///
2949 /// ```
2950 /// let a = ["lol", "NaN", "2", "5"];
2951 ///
2952 /// let first_number = a.iter().find_map(|s| s.parse().ok());
2953 ///
2954 /// assert_eq!(first_number, Some(2));
2955 /// ```
2956 #[inline]
2957 #[stable(feature = "iterator_find_map", since = "1.30.0")]
2958 #[cfg(not(feature = "ferrocene_certified"))]
2959 fn find_map<B, F>(&mut self, f: F) -> Option<B>
2960 where
2961 Self: Sized,
2962 F: FnMut(Self::Item) -> Option<B>,
2963 {
2964 #[inline]
2965 fn check<T, B>(mut f: impl FnMut(T) -> Option<B>) -> impl FnMut((), T) -> ControlFlow<B> {
2966 move |(), x| match f(x) {
2967 Some(x) => ControlFlow::Break(x),
2968 None => ControlFlow::Continue(()),
2969 }
2970 }
2971
2972 self.try_fold((), check(f)).break_value()
2973 }
2974
2975 /// Applies function to the elements of iterator and returns
2976 /// the first true result or the first error.
2977 ///
2978 /// The return type of this method depends on the return type of the closure.
2979 /// If you return `Result<bool, E>` from the closure, you'll get a `Result<Option<Self::Item>, E>`.
2980 /// If you return `Option<bool>` from the closure, you'll get an `Option<Option<Self::Item>>`.
2981 ///
2982 /// # Examples
2983 ///
2984 /// ```
2985 /// #![feature(try_find)]
2986 ///
2987 /// let a = ["1", "2", "lol", "NaN", "5"];
2988 ///
2989 /// let is_my_num = |s: &str, search: i32| -> Result<bool, std::num::ParseIntError> {
2990 /// Ok(s.parse::<i32>()? == search)
2991 /// };
2992 ///
2993 /// let result = a.into_iter().try_find(|&s| is_my_num(s, 2));
2994 /// assert_eq!(result, Ok(Some("2")));
2995 ///
2996 /// let result = a.into_iter().try_find(|&s| is_my_num(s, 5));
2997 /// assert!(result.is_err());
2998 /// ```
2999 ///
3000 /// This also supports other types which implement [`Try`], not just [`Result`].
3001 ///
3002 /// ```
3003 /// #![feature(try_find)]
3004 ///
3005 /// use std::num::NonZero;
3006 ///
3007 /// let a = [3, 5, 7, 4, 9, 0, 11u32];
3008 /// let result = a.into_iter().try_find(|&x| NonZero::new(x).map(|y| y.is_power_of_two()));
3009 /// assert_eq!(result, Some(Some(4)));
3010 /// let result = a.into_iter().take(3).try_find(|&x| NonZero::new(x).map(|y| y.is_power_of_two()));
3011 /// assert_eq!(result, Some(None));
3012 /// let result = a.into_iter().rev().try_find(|&x| NonZero::new(x).map(|y| y.is_power_of_two()));
3013 /// assert_eq!(result, None);
3014 /// ```
3015 #[inline]
3016 #[unstable(feature = "try_find", reason = "new API", issue = "63178")]
3017 #[cfg(not(feature = "ferrocene_certified"))]
3018 fn try_find<R>(
3019 &mut self,
3020 f: impl FnMut(&Self::Item) -> R,
3021 ) -> ChangeOutputType<R, Option<Self::Item>>
3022 where
3023 Self: Sized,
3024 R: Try<Output = bool, Residual: Residual<Option<Self::Item>>>,
3025 {
3026 #[inline]
3027 fn check<I, V, R>(
3028 mut f: impl FnMut(&I) -> V,
3029 ) -> impl FnMut((), I) -> ControlFlow<R::TryType>
3030 where
3031 V: Try<Output = bool, Residual = R>,
3032 R: Residual<Option<I>>,
3033 {
3034 move |(), x| match f(&x).branch() {
3035 ControlFlow::Continue(false) => ControlFlow::Continue(()),
3036 ControlFlow::Continue(true) => ControlFlow::Break(Try::from_output(Some(x))),
3037 ControlFlow::Break(r) => ControlFlow::Break(FromResidual::from_residual(r)),
3038 }
3039 }
3040
3041 match self.try_fold((), check(f)) {
3042 ControlFlow::Break(x) => x,
3043 ControlFlow::Continue(()) => Try::from_output(None),
3044 }
3045 }
3046
3047 /// Searches for an element in an iterator, returning its index.
3048 ///
3049 /// `position()` takes a closure that returns `true` or `false`. It applies
3050 /// this closure to each element of the iterator, and if one of them
3051 /// returns `true`, then `position()` returns [`Some(index)`]. If all of
3052 /// them return `false`, it returns [`None`].
3053 ///
3054 /// `position()` is short-circuiting; in other words, it will stop
3055 /// processing as soon as it finds a `true`.
3056 ///
3057 /// # Overflow Behavior
3058 ///
3059 /// The method does no guarding against overflows, so if there are more
3060 /// than [`usize::MAX`] non-matching elements, it either produces the wrong
3061 /// result or panics. If overflow checks are enabled, a panic is
3062 /// guaranteed.
3063 ///
3064 /// # Panics
3065 ///
3066 /// This function might panic if the iterator has more than `usize::MAX`
3067 /// non-matching elements.
3068 ///
3069 /// [`Some(index)`]: Some
3070 ///
3071 /// # Examples
3072 ///
3073 /// Basic usage:
3074 ///
3075 /// ```
3076 /// let a = [1, 2, 3];
3077 ///
3078 /// assert_eq!(a.into_iter().position(|x| x == 2), Some(1));
3079 ///
3080 /// assert_eq!(a.into_iter().position(|x| x == 5), None);
3081 /// ```
3082 ///
3083 /// Stopping at the first `true`:
3084 ///
3085 /// ```
3086 /// let a = [1, 2, 3, 4];
3087 ///
3088 /// let mut iter = a.into_iter();
3089 ///
3090 /// assert_eq!(iter.position(|x| x >= 2), Some(1));
3091 ///
3092 /// // we can still use `iter`, as there are more elements.
3093 /// assert_eq!(iter.next(), Some(3));
3094 ///
3095 /// // The returned index depends on iterator state
3096 /// assert_eq!(iter.position(|x| x == 4), Some(0));
3097 ///
3098 /// ```
3099 #[inline]
3100 #[stable(feature = "rust1", since = "1.0.0")]
3101 #[cfg(not(feature = "ferrocene_certified"))]
3102 fn position<P>(&mut self, predicate: P) -> Option<usize>
3103 where
3104 Self: Sized,
3105 P: FnMut(Self::Item) -> bool,
3106 {
3107 #[inline]
3108 fn check<'a, T>(
3109 mut predicate: impl FnMut(T) -> bool + 'a,
3110 acc: &'a mut usize,
3111 ) -> impl FnMut((), T) -> ControlFlow<usize, ()> + 'a {
3112 #[rustc_inherit_overflow_checks]
3113 move |_, x| {
3114 if predicate(x) {
3115 ControlFlow::Break(*acc)
3116 } else {
3117 *acc += 1;
3118 ControlFlow::Continue(())
3119 }
3120 }
3121 }
3122
3123 let mut acc = 0;
3124 self.try_fold((), check(predicate, &mut acc)).break_value()
3125 }
3126
3127 /// Searches for an element in an iterator from the right, returning its
3128 /// index.
3129 ///
3130 /// `rposition()` takes a closure that returns `true` or `false`. It applies
3131 /// this closure to each element of the iterator, starting from the end,
3132 /// and if one of them returns `true`, then `rposition()` returns
3133 /// [`Some(index)`]. If all of them return `false`, it returns [`None`].
3134 ///
3135 /// `rposition()` is short-circuiting; in other words, it will stop
3136 /// processing as soon as it finds a `true`.
3137 ///
3138 /// [`Some(index)`]: Some
3139 ///
3140 /// # Examples
3141 ///
3142 /// Basic usage:
3143 ///
3144 /// ```
3145 /// let a = [1, 2, 3];
3146 ///
3147 /// assert_eq!(a.into_iter().rposition(|x| x == 3), Some(2));
3148 ///
3149 /// assert_eq!(a.into_iter().rposition(|x| x == 5), None);
3150 /// ```
3151 ///
3152 /// Stopping at the first `true`:
3153 ///
3154 /// ```
3155 /// let a = [-1, 2, 3, 4];
3156 ///
3157 /// let mut iter = a.into_iter();
3158 ///
3159 /// assert_eq!(iter.rposition(|x| x >= 2), Some(3));
3160 ///
3161 /// // we can still use `iter`, as there are more elements.
3162 /// assert_eq!(iter.next(), Some(-1));
3163 /// assert_eq!(iter.next_back(), Some(3));
3164 /// ```
3165 #[inline]
3166 #[stable(feature = "rust1", since = "1.0.0")]
3167 #[cfg(not(feature = "ferrocene_certified"))]
3168 fn rposition<P>(&mut self, predicate: P) -> Option<usize>
3169 where
3170 P: FnMut(Self::Item) -> bool,
3171 Self: Sized + ExactSizeIterator + DoubleEndedIterator,
3172 {
3173 // No need for an overflow check here, because `ExactSizeIterator`
3174 // implies that the number of elements fits into a `usize`.
3175 #[inline]
3176 fn check<T>(
3177 mut predicate: impl FnMut(T) -> bool,
3178 ) -> impl FnMut(usize, T) -> ControlFlow<usize, usize> {
3179 move |i, x| {
3180 let i = i - 1;
3181 if predicate(x) { ControlFlow::Break(i) } else { ControlFlow::Continue(i) }
3182 }
3183 }
3184
3185 let n = self.len();
3186 self.try_rfold(n, check(predicate)).break_value()
3187 }
3188
3189 /// Returns the maximum element of an iterator.
3190 ///
3191 /// If several elements are equally maximum, the last element is
3192 /// returned. If the iterator is empty, [`None`] is returned.
3193 ///
3194 /// Note that [`f32`]/[`f64`] doesn't implement [`Ord`] due to NaN being
3195 /// incomparable. You can work around this by using [`Iterator::reduce`]:
3196 /// ```
3197 /// assert_eq!(
3198 /// [2.4, f32::NAN, 1.3]
3199 /// .into_iter()
3200 /// .reduce(f32::max)
3201 /// .unwrap_or(0.),
3202 /// 2.4
3203 /// );
3204 /// ```
3205 ///
3206 /// # Examples
3207 ///
3208 /// ```
3209 /// let a = [1, 2, 3];
3210 /// let b: [u32; 0] = [];
3211 ///
3212 /// assert_eq!(a.into_iter().max(), Some(3));
3213 /// assert_eq!(b.into_iter().max(), None);
3214 /// ```
3215 #[inline]
3216 #[stable(feature = "rust1", since = "1.0.0")]
3217 #[cfg(not(feature = "ferrocene_certified"))]
3218 fn max(self) -> Option<Self::Item>
3219 where
3220 Self: Sized,
3221 Self::Item: Ord,
3222 {
3223 self.max_by(Ord::cmp)
3224 }
3225
3226 /// Returns the minimum element of an iterator.
3227 ///
3228 /// If several elements are equally minimum, the first element is returned.
3229 /// If the iterator is empty, [`None`] is returned.
3230 ///
3231 /// Note that [`f32`]/[`f64`] doesn't implement [`Ord`] due to NaN being
3232 /// incomparable. You can work around this by using [`Iterator::reduce`]:
3233 /// ```
3234 /// assert_eq!(
3235 /// [2.4, f32::NAN, 1.3]
3236 /// .into_iter()
3237 /// .reduce(f32::min)
3238 /// .unwrap_or(0.),
3239 /// 1.3
3240 /// );
3241 /// ```
3242 ///
3243 /// # Examples
3244 ///
3245 /// ```
3246 /// let a = [1, 2, 3];
3247 /// let b: [u32; 0] = [];
3248 ///
3249 /// assert_eq!(a.into_iter().min(), Some(1));
3250 /// assert_eq!(b.into_iter().min(), None);
3251 /// ```
3252 #[inline]
3253 #[stable(feature = "rust1", since = "1.0.0")]
3254 #[cfg(not(feature = "ferrocene_certified"))]
3255 fn min(self) -> Option<Self::Item>
3256 where
3257 Self: Sized,
3258 Self::Item: Ord,
3259 {
3260 self.min_by(Ord::cmp)
3261 }
3262
3263 /// Returns the element that gives the maximum value from the
3264 /// specified function.
3265 ///
3266 /// If several elements are equally maximum, the last element is
3267 /// returned. If the iterator is empty, [`None`] is returned.
3268 ///
3269 /// # Examples
3270 ///
3271 /// ```
3272 /// let a = [-3_i32, 0, 1, 5, -10];
3273 /// assert_eq!(a.into_iter().max_by_key(|x| x.abs()).unwrap(), -10);
3274 /// ```
3275 #[inline]
3276 #[stable(feature = "iter_cmp_by_key", since = "1.6.0")]
3277 #[cfg(not(feature = "ferrocene_certified"))]
3278 fn max_by_key<B: Ord, F>(self, f: F) -> Option<Self::Item>
3279 where
3280 Self: Sized,
3281 F: FnMut(&Self::Item) -> B,
3282 {
3283 #[inline]
3284 fn key<T, B>(mut f: impl FnMut(&T) -> B) -> impl FnMut(T) -> (B, T) {
3285 move |x| (f(&x), x)
3286 }
3287
3288 #[inline]
3289 fn compare<T, B: Ord>((x_p, _): &(B, T), (y_p, _): &(B, T)) -> Ordering {
3290 x_p.cmp(y_p)
3291 }
3292
3293 let (_, x) = self.map(key(f)).max_by(compare)?;
3294 Some(x)
3295 }
3296
3297 /// Returns the element that gives the maximum value with respect to the
3298 /// specified comparison function.
3299 ///
3300 /// If several elements are equally maximum, the last element is
3301 /// returned. If the iterator is empty, [`None`] is returned.
3302 ///
3303 /// # Examples
3304 ///
3305 /// ```
3306 /// let a = [-3_i32, 0, 1, 5, -10];
3307 /// assert_eq!(a.into_iter().max_by(|x, y| x.cmp(y)).unwrap(), 5);
3308 /// ```
3309 #[inline]
3310 #[stable(feature = "iter_max_by", since = "1.15.0")]
3311 #[cfg(not(feature = "ferrocene_certified"))]
3312 fn max_by<F>(self, compare: F) -> Option<Self::Item>
3313 where
3314 Self: Sized,
3315 F: FnMut(&Self::Item, &Self::Item) -> Ordering,
3316 {
3317 #[inline]
3318 fn fold<T>(mut compare: impl FnMut(&T, &T) -> Ordering) -> impl FnMut(T, T) -> T {
3319 move |x, y| cmp::max_by(x, y, &mut compare)
3320 }
3321
3322 self.reduce(fold(compare))
3323 }
3324
3325 /// Returns the element that gives the minimum value from the
3326 /// specified function.
3327 ///
3328 /// If several elements are equally minimum, the first element is
3329 /// returned. If the iterator is empty, [`None`] is returned.
3330 ///
3331 /// # Examples
3332 ///
3333 /// ```
3334 /// let a = [-3_i32, 0, 1, 5, -10];
3335 /// assert_eq!(a.into_iter().min_by_key(|x| x.abs()).unwrap(), 0);
3336 /// ```
3337 #[inline]
3338 #[stable(feature = "iter_cmp_by_key", since = "1.6.0")]
3339 #[cfg(not(feature = "ferrocene_certified"))]
3340 fn min_by_key<B: Ord, F>(self, f: F) -> Option<Self::Item>
3341 where
3342 Self: Sized,
3343 F: FnMut(&Self::Item) -> B,
3344 {
3345 #[inline]
3346 fn key<T, B>(mut f: impl FnMut(&T) -> B) -> impl FnMut(T) -> (B, T) {
3347 move |x| (f(&x), x)
3348 }
3349
3350 #[inline]
3351 fn compare<T, B: Ord>((x_p, _): &(B, T), (y_p, _): &(B, T)) -> Ordering {
3352 x_p.cmp(y_p)
3353 }
3354
3355 let (_, x) = self.map(key(f)).min_by(compare)?;
3356 Some(x)
3357 }
3358
3359 /// Returns the element that gives the minimum value with respect to the
3360 /// specified comparison function.
3361 ///
3362 /// If several elements are equally minimum, the first element is
3363 /// returned. If the iterator is empty, [`None`] is returned.
3364 ///
3365 /// # Examples
3366 ///
3367 /// ```
3368 /// let a = [-3_i32, 0, 1, 5, -10];
3369 /// assert_eq!(a.into_iter().min_by(|x, y| x.cmp(y)).unwrap(), -10);
3370 /// ```
3371 #[inline]
3372 #[stable(feature = "iter_min_by", since = "1.15.0")]
3373 #[cfg(not(feature = "ferrocene_certified"))]
3374 fn min_by<F>(self, compare: F) -> Option<Self::Item>
3375 where
3376 Self: Sized,
3377 F: FnMut(&Self::Item, &Self::Item) -> Ordering,
3378 {
3379 #[inline]
3380 fn fold<T>(mut compare: impl FnMut(&T, &T) -> Ordering) -> impl FnMut(T, T) -> T {
3381 move |x, y| cmp::min_by(x, y, &mut compare)
3382 }
3383
3384 self.reduce(fold(compare))
3385 }
3386
3387 /// Reverses an iterator's direction.
3388 ///
3389 /// Usually, iterators iterate from left to right. After using `rev()`,
3390 /// an iterator will instead iterate from right to left.
3391 ///
3392 /// This is only possible if the iterator has an end, so `rev()` only
3393 /// works on [`DoubleEndedIterator`]s.
3394 ///
3395 /// # Examples
3396 ///
3397 /// ```
3398 /// let a = [1, 2, 3];
3399 ///
3400 /// let mut iter = a.into_iter().rev();
3401 ///
3402 /// assert_eq!(iter.next(), Some(3));
3403 /// assert_eq!(iter.next(), Some(2));
3404 /// assert_eq!(iter.next(), Some(1));
3405 ///
3406 /// assert_eq!(iter.next(), None);
3407 /// ```
3408 #[inline]
3409 #[doc(alias = "reverse")]
3410 #[stable(feature = "rust1", since = "1.0.0")]
3411 #[cfg(not(feature = "ferrocene_certified"))]
3412 fn rev(self) -> Rev<Self>
3413 where
3414 Self: Sized + DoubleEndedIterator,
3415 {
3416 Rev::new(self)
3417 }
3418
3419 /// Converts an iterator of pairs into a pair of containers.
3420 ///
3421 /// `unzip()` consumes an entire iterator of pairs, producing two
3422 /// collections: one from the left elements of the pairs, and one
3423 /// from the right elements.
3424 ///
3425 /// This function is, in some sense, the opposite of [`zip`].
3426 ///
3427 /// [`zip`]: Iterator::zip
3428 ///
3429 /// # Examples
3430 ///
3431 /// ```
3432 /// let a = [(1, 2), (3, 4), (5, 6)];
3433 ///
3434 /// let (left, right): (Vec<_>, Vec<_>) = a.into_iter().unzip();
3435 ///
3436 /// assert_eq!(left, [1, 3, 5]);
3437 /// assert_eq!(right, [2, 4, 6]);
3438 ///
3439 /// // you can also unzip multiple nested tuples at once
3440 /// let a = [(1, (2, 3)), (4, (5, 6))];
3441 ///
3442 /// let (x, (y, z)): (Vec<_>, (Vec<_>, Vec<_>)) = a.into_iter().unzip();
3443 /// assert_eq!(x, [1, 4]);
3444 /// assert_eq!(y, [2, 5]);
3445 /// assert_eq!(z, [3, 6]);
3446 /// ```
3447 #[stable(feature = "rust1", since = "1.0.0")]
3448 #[cfg(not(feature = "ferrocene_certified"))]
3449 fn unzip<A, B, FromA, FromB>(self) -> (FromA, FromB)
3450 where
3451 FromA: Default + Extend<A>,
3452 FromB: Default + Extend<B>,
3453 Self: Sized + Iterator<Item = (A, B)>,
3454 {
3455 let mut unzipped: (FromA, FromB) = Default::default();
3456 unzipped.extend(self);
3457 unzipped
3458 }
3459
3460 /// Creates an iterator which copies all of its elements.
3461 ///
3462 /// This is useful when you have an iterator over `&T`, but you need an
3463 /// iterator over `T`.
3464 ///
3465 /// # Examples
3466 ///
3467 /// ```
3468 /// let a = [1, 2, 3];
3469 ///
3470 /// let v_copied: Vec<_> = a.iter().copied().collect();
3471 ///
3472 /// // copied is the same as .map(|&x| x)
3473 /// let v_map: Vec<_> = a.iter().map(|&x| x).collect();
3474 ///
3475 /// assert_eq!(v_copied, [1, 2, 3]);
3476 /// assert_eq!(v_map, [1, 2, 3]);
3477 /// ```
3478 #[stable(feature = "iter_copied", since = "1.36.0")]
3479 #[rustc_diagnostic_item = "iter_copied"]
3480 #[cfg(not(feature = "ferrocene_certified"))]
3481 fn copied<'a, T>(self) -> Copied<Self>
3482 where
3483 T: Copy + 'a,
3484 Self: Sized + Iterator<Item = &'a T>,
3485 {
3486 Copied::new(self)
3487 }
3488
3489 /// Creates an iterator which [`clone`]s all of its elements.
3490 ///
3491 /// This is useful when you have an iterator over `&T`, but you need an
3492 /// iterator over `T`.
3493 ///
3494 /// There is no guarantee whatsoever about the `clone` method actually
3495 /// being called *or* optimized away. So code should not depend on
3496 /// either.
3497 ///
3498 /// [`clone`]: Clone::clone
3499 ///
3500 /// # Examples
3501 ///
3502 /// Basic usage:
3503 ///
3504 /// ```
3505 /// let a = [1, 2, 3];
3506 ///
3507 /// let v_cloned: Vec<_> = a.iter().cloned().collect();
3508 ///
3509 /// // cloned is the same as .map(|&x| x), for integers
3510 /// let v_map: Vec<_> = a.iter().map(|&x| x).collect();
3511 ///
3512 /// assert_eq!(v_cloned, [1, 2, 3]);
3513 /// assert_eq!(v_map, [1, 2, 3]);
3514 /// ```
3515 ///
3516 /// To get the best performance, try to clone late:
3517 ///
3518 /// ```
3519 /// let a = [vec![0_u8, 1, 2], vec![3, 4], vec![23]];
3520 /// // don't do this:
3521 /// let slower: Vec<_> = a.iter().cloned().filter(|s| s.len() == 1).collect();
3522 /// assert_eq!(&[vec![23]], &slower[..]);
3523 /// // instead call `cloned` late
3524 /// let faster: Vec<_> = a.iter().filter(|s| s.len() == 1).cloned().collect();
3525 /// assert_eq!(&[vec![23]], &faster[..]);
3526 /// ```
3527 #[stable(feature = "rust1", since = "1.0.0")]
3528 #[rustc_diagnostic_item = "iter_cloned"]
3529 #[cfg(not(feature = "ferrocene_certified"))]
3530 fn cloned<'a, T>(self) -> Cloned<Self>
3531 where
3532 T: Clone + 'a,
3533 Self: Sized + Iterator<Item = &'a T>,
3534 {
3535 Cloned::new(self)
3536 }
3537
3538 /// Repeats an iterator endlessly.
3539 ///
3540 /// Instead of stopping at [`None`], the iterator will instead start again,
3541 /// from the beginning. After iterating again, it will start at the
3542 /// beginning again. And again. And again. Forever. Note that in case the
3543 /// original iterator is empty, the resulting iterator will also be empty.
3544 ///
3545 /// # Examples
3546 ///
3547 /// ```
3548 /// let a = [1, 2, 3];
3549 ///
3550 /// let mut iter = a.into_iter().cycle();
3551 ///
3552 /// loop {
3553 /// assert_eq!(iter.next(), Some(1));
3554 /// assert_eq!(iter.next(), Some(2));
3555 /// assert_eq!(iter.next(), Some(3));
3556 /// # break;
3557 /// }
3558 /// ```
3559 #[stable(feature = "rust1", since = "1.0.0")]
3560 #[inline]
3561 #[cfg(not(feature = "ferrocene_certified"))]
3562 fn cycle(self) -> Cycle<Self>
3563 where
3564 Self: Sized + Clone,
3565 {
3566 Cycle::new(self)
3567 }
3568
3569 /// Returns an iterator over `N` elements of the iterator at a time.
3570 ///
3571 /// The chunks do not overlap. If `N` does not divide the length of the
3572 /// iterator, then the last up to `N-1` elements will be omitted and can be
3573 /// retrieved from the [`.into_remainder()`][ArrayChunks::into_remainder]
3574 /// function of the iterator.
3575 ///
3576 /// # Panics
3577 ///
3578 /// Panics if `N` is zero.
3579 ///
3580 /// # Examples
3581 ///
3582 /// Basic usage:
3583 ///
3584 /// ```
3585 /// #![feature(iter_array_chunks)]
3586 ///
3587 /// let mut iter = "lorem".chars().array_chunks();
3588 /// assert_eq!(iter.next(), Some(['l', 'o']));
3589 /// assert_eq!(iter.next(), Some(['r', 'e']));
3590 /// assert_eq!(iter.next(), None);
3591 /// assert_eq!(iter.into_remainder().unwrap().as_slice(), &['m']);
3592 /// ```
3593 ///
3594 /// ```
3595 /// #![feature(iter_array_chunks)]
3596 ///
3597 /// let data = [1, 1, 2, -2, 6, 0, 3, 1];
3598 /// // ^-----^ ^------^
3599 /// for [x, y, z] in data.iter().array_chunks() {
3600 /// assert_eq!(x + y + z, 4);
3601 /// }
3602 /// ```
3603 #[track_caller]
3604 #[unstable(feature = "iter_array_chunks", reason = "recently added", issue = "100450")]
3605 #[cfg(not(feature = "ferrocene_certified"))]
3606 fn array_chunks<const N: usize>(self) -> ArrayChunks<Self, N>
3607 where
3608 Self: Sized,
3609 {
3610 ArrayChunks::new(self)
3611 }
3612
3613 /// Sums the elements of an iterator.
3614 ///
3615 /// Takes each element, adds them together, and returns the result.
3616 ///
3617 /// An empty iterator returns the *additive identity* ("zero") of the type,
3618 /// which is `0` for integers and `-0.0` for floats.
3619 ///
3620 /// `sum()` can be used to sum any type implementing [`Sum`][`core::iter::Sum`],
3621 /// including [`Option`][`Option::sum`] and [`Result`][`Result::sum`].
3622 ///
3623 /// # Panics
3624 ///
3625 /// When calling `sum()` and a primitive integer type is being returned, this
3626 /// method will panic if the computation overflows and overflow checks are
3627 /// enabled.
3628 ///
3629 /// # Examples
3630 ///
3631 /// ```
3632 /// let a = [1, 2, 3];
3633 /// let sum: i32 = a.iter().sum();
3634 ///
3635 /// assert_eq!(sum, 6);
3636 ///
3637 /// let b: Vec<f32> = vec![];
3638 /// let sum: f32 = b.iter().sum();
3639 /// assert_eq!(sum, -0.0_f32);
3640 /// ```
3641 #[stable(feature = "iter_arith", since = "1.11.0")]
3642 #[cfg(not(feature = "ferrocene_certified"))]
3643 fn sum<S>(self) -> S
3644 where
3645 Self: Sized,
3646 S: Sum<Self::Item>,
3647 {
3648 Sum::sum(self)
3649 }
3650
3651 /// Iterates over the entire iterator, multiplying all the elements
3652 ///
3653 /// An empty iterator returns the one value of the type.
3654 ///
3655 /// `product()` can be used to multiply any type implementing [`Product`][`core::iter::Product`],
3656 /// including [`Option`][`Option::product`] and [`Result`][`Result::product`].
3657 ///
3658 /// # Panics
3659 ///
3660 /// When calling `product()` and a primitive integer type is being returned,
3661 /// method will panic if the computation overflows and overflow checks are
3662 /// enabled.
3663 ///
3664 /// # Examples
3665 ///
3666 /// ```
3667 /// fn factorial(n: u32) -> u32 {
3668 /// (1..=n).product()
3669 /// }
3670 /// assert_eq!(factorial(0), 1);
3671 /// assert_eq!(factorial(1), 1);
3672 /// assert_eq!(factorial(5), 120);
3673 /// ```
3674 #[stable(feature = "iter_arith", since = "1.11.0")]
3675 #[cfg(not(feature = "ferrocene_certified"))]
3676 fn product<P>(self) -> P
3677 where
3678 Self: Sized,
3679 P: Product<Self::Item>,
3680 {
3681 Product::product(self)
3682 }
3683
3684 /// [Lexicographically](Ord#lexicographical-comparison) compares the elements of this [`Iterator`] with those
3685 /// of another.
3686 ///
3687 /// # Examples
3688 ///
3689 /// ```
3690 /// use std::cmp::Ordering;
3691 ///
3692 /// assert_eq!([1].iter().cmp([1].iter()), Ordering::Equal);
3693 /// assert_eq!([1].iter().cmp([1, 2].iter()), Ordering::Less);
3694 /// assert_eq!([1, 2].iter().cmp([1].iter()), Ordering::Greater);
3695 /// ```
3696 #[stable(feature = "iter_order", since = "1.5.0")]
3697 #[cfg(not(feature = "ferrocene_certified"))]
3698 fn cmp<I>(self, other: I) -> Ordering
3699 where
3700 I: IntoIterator<Item = Self::Item>,
3701 Self::Item: Ord,
3702 Self: Sized,
3703 {
3704 self.cmp_by(other, |x, y| x.cmp(&y))
3705 }
3706
3707 /// [Lexicographically](Ord#lexicographical-comparison) compares the elements of this [`Iterator`] with those
3708 /// of another with respect to the specified comparison function.
3709 ///
3710 /// # Examples
3711 ///
3712 /// ```
3713 /// #![feature(iter_order_by)]
3714 ///
3715 /// use std::cmp::Ordering;
3716 ///
3717 /// let xs = [1, 2, 3, 4];
3718 /// let ys = [1, 4, 9, 16];
3719 ///
3720 /// assert_eq!(xs.into_iter().cmp_by(ys, |x, y| x.cmp(&y)), Ordering::Less);
3721 /// assert_eq!(xs.into_iter().cmp_by(ys, |x, y| (x * x).cmp(&y)), Ordering::Equal);
3722 /// assert_eq!(xs.into_iter().cmp_by(ys, |x, y| (2 * x).cmp(&y)), Ordering::Greater);
3723 /// ```
3724 #[unstable(feature = "iter_order_by", issue = "64295")]
3725 #[cfg(not(feature = "ferrocene_certified"))]
3726 fn cmp_by<I, F>(self, other: I, cmp: F) -> Ordering
3727 where
3728 Self: Sized,
3729 I: IntoIterator,
3730 F: FnMut(Self::Item, I::Item) -> Ordering,
3731 {
3732 #[inline]
3733 fn compare<X, Y, F>(mut cmp: F) -> impl FnMut(X, Y) -> ControlFlow<Ordering>
3734 where
3735 F: FnMut(X, Y) -> Ordering,
3736 {
3737 move |x, y| match cmp(x, y) {
3738 Ordering::Equal => ControlFlow::Continue(()),
3739 non_eq => ControlFlow::Break(non_eq),
3740 }
3741 }
3742
3743 match iter_compare(self, other.into_iter(), compare(cmp)) {
3744 ControlFlow::Continue(ord) => ord,
3745 ControlFlow::Break(ord) => ord,
3746 }
3747 }
3748
3749 /// [Lexicographically](Ord#lexicographical-comparison) compares the [`PartialOrd`] elements of
3750 /// this [`Iterator`] with those of another. The comparison works like short-circuit
3751 /// evaluation, returning a result without comparing the remaining elements.
3752 /// As soon as an order can be determined, the evaluation stops and a result is returned.
3753 ///
3754 /// # Examples
3755 ///
3756 /// ```
3757 /// use std::cmp::Ordering;
3758 ///
3759 /// assert_eq!([1.].iter().partial_cmp([1.].iter()), Some(Ordering::Equal));
3760 /// assert_eq!([1.].iter().partial_cmp([1., 2.].iter()), Some(Ordering::Less));
3761 /// assert_eq!([1., 2.].iter().partial_cmp([1.].iter()), Some(Ordering::Greater));
3762 /// ```
3763 ///
3764 /// For floating-point numbers, NaN does not have a total order and will result
3765 /// in `None` when compared:
3766 ///
3767 /// ```
3768 /// assert_eq!([f64::NAN].iter().partial_cmp([1.].iter()), None);
3769 /// ```
3770 ///
3771 /// The results are determined by the order of evaluation.
3772 ///
3773 /// ```
3774 /// use std::cmp::Ordering;
3775 ///
3776 /// assert_eq!([1.0, f64::NAN].iter().partial_cmp([2.0, f64::NAN].iter()), Some(Ordering::Less));
3777 /// assert_eq!([2.0, f64::NAN].iter().partial_cmp([1.0, f64::NAN].iter()), Some(Ordering::Greater));
3778 /// assert_eq!([f64::NAN, 1.0].iter().partial_cmp([f64::NAN, 2.0].iter()), None);
3779 /// ```
3780 ///
3781 #[stable(feature = "iter_order", since = "1.5.0")]
3782 #[cfg(not(feature = "ferrocene_certified"))]
3783 fn partial_cmp<I>(self, other: I) -> Option<Ordering>
3784 where
3785 I: IntoIterator,
3786 Self::Item: PartialOrd<I::Item>,
3787 Self: Sized,
3788 {
3789 self.partial_cmp_by(other, |x, y| x.partial_cmp(&y))
3790 }
3791
3792 /// [Lexicographically](Ord#lexicographical-comparison) compares the elements of this [`Iterator`] with those
3793 /// of another with respect to the specified comparison function.
3794 ///
3795 /// # Examples
3796 ///
3797 /// ```
3798 /// #![feature(iter_order_by)]
3799 ///
3800 /// use std::cmp::Ordering;
3801 ///
3802 /// let xs = [1.0, 2.0, 3.0, 4.0];
3803 /// let ys = [1.0, 4.0, 9.0, 16.0];
3804 ///
3805 /// assert_eq!(
3806 /// xs.iter().partial_cmp_by(ys, |x, y| x.partial_cmp(&y)),
3807 /// Some(Ordering::Less)
3808 /// );
3809 /// assert_eq!(
3810 /// xs.iter().partial_cmp_by(ys, |x, y| (x * x).partial_cmp(&y)),
3811 /// Some(Ordering::Equal)
3812 /// );
3813 /// assert_eq!(
3814 /// xs.iter().partial_cmp_by(ys, |x, y| (2.0 * x).partial_cmp(&y)),
3815 /// Some(Ordering::Greater)
3816 /// );
3817 /// ```
3818 #[unstable(feature = "iter_order_by", issue = "64295")]
3819 #[cfg(not(feature = "ferrocene_certified"))]
3820 fn partial_cmp_by<I, F>(self, other: I, partial_cmp: F) -> Option<Ordering>
3821 where
3822 Self: Sized,
3823 I: IntoIterator,
3824 F: FnMut(Self::Item, I::Item) -> Option<Ordering>,
3825 {
3826 #[inline]
3827 fn compare<X, Y, F>(mut partial_cmp: F) -> impl FnMut(X, Y) -> ControlFlow<Option<Ordering>>
3828 where
3829 F: FnMut(X, Y) -> Option<Ordering>,
3830 {
3831 move |x, y| match partial_cmp(x, y) {
3832 Some(Ordering::Equal) => ControlFlow::Continue(()),
3833 non_eq => ControlFlow::Break(non_eq),
3834 }
3835 }
3836
3837 match iter_compare(self, other.into_iter(), compare(partial_cmp)) {
3838 ControlFlow::Continue(ord) => Some(ord),
3839 ControlFlow::Break(ord) => ord,
3840 }
3841 }
3842
3843 /// Determines if the elements of this [`Iterator`] are equal to those of
3844 /// another.
3845 ///
3846 /// # Examples
3847 ///
3848 /// ```
3849 /// assert_eq!([1].iter().eq([1].iter()), true);
3850 /// assert_eq!([1].iter().eq([1, 2].iter()), false);
3851 /// ```
3852 #[stable(feature = "iter_order", since = "1.5.0")]
3853 #[cfg(not(feature = "ferrocene_certified"))]
3854 fn eq<I>(self, other: I) -> bool
3855 where
3856 I: IntoIterator,
3857 Self::Item: PartialEq<I::Item>,
3858 Self: Sized,
3859 {
3860 self.eq_by(other, |x, y| x == y)
3861 }
3862
3863 /// Determines if the elements of this [`Iterator`] are equal to those of
3864 /// another with respect to the specified equality function.
3865 ///
3866 /// # Examples
3867 ///
3868 /// ```
3869 /// #![feature(iter_order_by)]
3870 ///
3871 /// let xs = [1, 2, 3, 4];
3872 /// let ys = [1, 4, 9, 16];
3873 ///
3874 /// assert!(xs.iter().eq_by(ys, |x, y| x * x == y));
3875 /// ```
3876 #[unstable(feature = "iter_order_by", issue = "64295")]
3877 #[cfg(not(feature = "ferrocene_certified"))]
3878 fn eq_by<I, F>(self, other: I, eq: F) -> bool
3879 where
3880 Self: Sized,
3881 I: IntoIterator,
3882 F: FnMut(Self::Item, I::Item) -> bool,
3883 {
3884 #[inline]
3885 fn compare<X, Y, F>(mut eq: F) -> impl FnMut(X, Y) -> ControlFlow<()>
3886 where
3887 F: FnMut(X, Y) -> bool,
3888 {
3889 move |x, y| {
3890 if eq(x, y) { ControlFlow::Continue(()) } else { ControlFlow::Break(()) }
3891 }
3892 }
3893
3894 SpecIterEq::spec_iter_eq(self, other.into_iter(), compare(eq))
3895 }
3896
3897 /// Determines if the elements of this [`Iterator`] are not equal to those of
3898 /// another.
3899 ///
3900 /// # Examples
3901 ///
3902 /// ```
3903 /// assert_eq!([1].iter().ne([1].iter()), false);
3904 /// assert_eq!([1].iter().ne([1, 2].iter()), true);
3905 /// ```
3906 #[stable(feature = "iter_order", since = "1.5.0")]
3907 #[cfg(not(feature = "ferrocene_certified"))]
3908 fn ne<I>(self, other: I) -> bool
3909 where
3910 I: IntoIterator,
3911 Self::Item: PartialEq<I::Item>,
3912 Self: Sized,
3913 {
3914 !self.eq(other)
3915 }
3916
3917 /// Determines if the elements of this [`Iterator`] are [lexicographically](Ord#lexicographical-comparison)
3918 /// less than those of another.
3919 ///
3920 /// # Examples
3921 ///
3922 /// ```
3923 /// assert_eq!([1].iter().lt([1].iter()), false);
3924 /// assert_eq!([1].iter().lt([1, 2].iter()), true);
3925 /// assert_eq!([1, 2].iter().lt([1].iter()), false);
3926 /// assert_eq!([1, 2].iter().lt([1, 2].iter()), false);
3927 /// ```
3928 #[stable(feature = "iter_order", since = "1.5.0")]
3929 #[cfg(not(feature = "ferrocene_certified"))]
3930 fn lt<I>(self, other: I) -> bool
3931 where
3932 I: IntoIterator,
3933 Self::Item: PartialOrd<I::Item>,
3934 Self: Sized,
3935 {
3936 self.partial_cmp(other) == Some(Ordering::Less)
3937 }
3938
3939 /// Determines if the elements of this [`Iterator`] are [lexicographically](Ord#lexicographical-comparison)
3940 /// less or equal to those of another.
3941 ///
3942 /// # Examples
3943 ///
3944 /// ```
3945 /// assert_eq!([1].iter().le([1].iter()), true);
3946 /// assert_eq!([1].iter().le([1, 2].iter()), true);
3947 /// assert_eq!([1, 2].iter().le([1].iter()), false);
3948 /// assert_eq!([1, 2].iter().le([1, 2].iter()), true);
3949 /// ```
3950 #[stable(feature = "iter_order", since = "1.5.0")]
3951 #[cfg(not(feature = "ferrocene_certified"))]
3952 fn le<I>(self, other: I) -> bool
3953 where
3954 I: IntoIterator,
3955 Self::Item: PartialOrd<I::Item>,
3956 Self: Sized,
3957 {
3958 matches!(self.partial_cmp(other), Some(Ordering::Less | Ordering::Equal))
3959 }
3960
3961 /// Determines if the elements of this [`Iterator`] are [lexicographically](Ord#lexicographical-comparison)
3962 /// greater than those of another.
3963 ///
3964 /// # Examples
3965 ///
3966 /// ```
3967 /// assert_eq!([1].iter().gt([1].iter()), false);
3968 /// assert_eq!([1].iter().gt([1, 2].iter()), false);
3969 /// assert_eq!([1, 2].iter().gt([1].iter()), true);
3970 /// assert_eq!([1, 2].iter().gt([1, 2].iter()), false);
3971 /// ```
3972 #[stable(feature = "iter_order", since = "1.5.0")]
3973 #[cfg(not(feature = "ferrocene_certified"))]
3974 fn gt<I>(self, other: I) -> bool
3975 where
3976 I: IntoIterator,
3977 Self::Item: PartialOrd<I::Item>,
3978 Self: Sized,
3979 {
3980 self.partial_cmp(other) == Some(Ordering::Greater)
3981 }
3982
3983 /// Determines if the elements of this [`Iterator`] are [lexicographically](Ord#lexicographical-comparison)
3984 /// greater than or equal to those of another.
3985 ///
3986 /// # Examples
3987 ///
3988 /// ```
3989 /// assert_eq!([1].iter().ge([1].iter()), true);
3990 /// assert_eq!([1].iter().ge([1, 2].iter()), false);
3991 /// assert_eq!([1, 2].iter().ge([1].iter()), true);
3992 /// assert_eq!([1, 2].iter().ge([1, 2].iter()), true);
3993 /// ```
3994 #[stable(feature = "iter_order", since = "1.5.0")]
3995 #[cfg(not(feature = "ferrocene_certified"))]
3996 fn ge<I>(self, other: I) -> bool
3997 where
3998 I: IntoIterator,
3999 Self::Item: PartialOrd<I::Item>,
4000 Self: Sized,
4001 {
4002 matches!(self.partial_cmp(other), Some(Ordering::Greater | Ordering::Equal))
4003 }
4004
4005 /// Checks if the elements of this iterator are sorted.
4006 ///
4007 /// That is, for each element `a` and its following element `b`, `a <= b` must hold. If the
4008 /// iterator yields exactly zero or one element, `true` is returned.
4009 ///
4010 /// Note that if `Self::Item` is only `PartialOrd`, but not `Ord`, the above definition
4011 /// implies that this function returns `false` if any two consecutive items are not
4012 /// comparable.
4013 ///
4014 /// # Examples
4015 ///
4016 /// ```
4017 /// assert!([1, 2, 2, 9].iter().is_sorted());
4018 /// assert!(![1, 3, 2, 4].iter().is_sorted());
4019 /// assert!([0].iter().is_sorted());
4020 /// assert!(std::iter::empty::<i32>().is_sorted());
4021 /// assert!(![0.0, 1.0, f32::NAN].iter().is_sorted());
4022 /// ```
4023 #[inline]
4024 #[stable(feature = "is_sorted", since = "1.82.0")]
4025 #[cfg(not(feature = "ferrocene_certified"))]
4026 fn is_sorted(self) -> bool
4027 where
4028 Self: Sized,
4029 Self::Item: PartialOrd,
4030 {
4031 self.is_sorted_by(|a, b| a <= b)
4032 }
4033
4034 /// Checks if the elements of this iterator are sorted using the given comparator function.
4035 ///
4036 /// Instead of using `PartialOrd::partial_cmp`, this function uses the given `compare`
4037 /// function to determine whether two elements are to be considered in sorted order.
4038 ///
4039 /// # Examples
4040 ///
4041 /// ```
4042 /// assert!([1, 2, 2, 9].iter().is_sorted_by(|a, b| a <= b));
4043 /// assert!(![1, 2, 2, 9].iter().is_sorted_by(|a, b| a < b));
4044 ///
4045 /// assert!([0].iter().is_sorted_by(|a, b| true));
4046 /// assert!([0].iter().is_sorted_by(|a, b| false));
4047 ///
4048 /// assert!(std::iter::empty::<i32>().is_sorted_by(|a, b| false));
4049 /// assert!(std::iter::empty::<i32>().is_sorted_by(|a, b| true));
4050 /// ```
4051 #[stable(feature = "is_sorted", since = "1.82.0")]
4052 #[cfg(not(feature = "ferrocene_certified"))]
4053 fn is_sorted_by<F>(mut self, compare: F) -> bool
4054 where
4055 Self: Sized,
4056 F: FnMut(&Self::Item, &Self::Item) -> bool,
4057 {
4058 #[inline]
4059 fn check<'a, T>(
4060 last: &'a mut T,
4061 mut compare: impl FnMut(&T, &T) -> bool + 'a,
4062 ) -> impl FnMut(T) -> bool + 'a {
4063 move |curr| {
4064 if !compare(&last, &curr) {
4065 return false;
4066 }
4067 *last = curr;
4068 true
4069 }
4070 }
4071
4072 let mut last = match self.next() {
4073 Some(e) => e,
4074 None => return true,
4075 };
4076
4077 self.all(check(&mut last, compare))
4078 }
4079
4080 /// Checks if the elements of this iterator are sorted using the given key extraction
4081 /// function.
4082 ///
4083 /// Instead of comparing the iterator's elements directly, this function compares the keys of
4084 /// the elements, as determined by `f`. Apart from that, it's equivalent to [`is_sorted`]; see
4085 /// its documentation for more information.
4086 ///
4087 /// [`is_sorted`]: Iterator::is_sorted
4088 ///
4089 /// # Examples
4090 ///
4091 /// ```
4092 /// assert!(["c", "bb", "aaa"].iter().is_sorted_by_key(|s| s.len()));
4093 /// assert!(![-2i32, -1, 0, 3].iter().is_sorted_by_key(|n| n.abs()));
4094 /// ```
4095 #[inline]
4096 #[stable(feature = "is_sorted", since = "1.82.0")]
4097 #[cfg(not(feature = "ferrocene_certified"))]
4098 fn is_sorted_by_key<F, K>(self, f: F) -> bool
4099 where
4100 Self: Sized,
4101 F: FnMut(Self::Item) -> K,
4102 K: PartialOrd,
4103 {
4104 self.map(f).is_sorted()
4105 }
4106
4107 /// See [TrustedRandomAccess][super::super::TrustedRandomAccess]
4108 // The unusual name is to avoid name collisions in method resolution
4109 // see #76479.
4110 #[inline]
4111 #[doc(hidden)]
4112 #[unstable(feature = "trusted_random_access", issue = "none")]
4113 #[cfg(not(feature = "ferrocene_certified"))]
4114 unsafe fn __iterator_get_unchecked(&mut self, _idx: usize) -> Self::Item
4115 where
4116 Self: TrustedRandomAccessNoCoerce,
4117 {
4118 unreachable!("Always specialized");
4119 }
4120}
4121
4122#[cfg(not(feature = "ferrocene_certified"))]
4123trait SpecIterEq<B: Iterator>: Iterator {
4124 fn spec_iter_eq<F>(self, b: B, f: F) -> bool
4125 where
4126 F: FnMut(Self::Item, <B as Iterator>::Item) -> ControlFlow<()>;
4127}
4128
4129#[cfg(not(feature = "ferrocene_certified"))]
4130impl<A: Iterator, B: Iterator> SpecIterEq<B> for A {
4131 #[inline]
4132 default fn spec_iter_eq<F>(self, b: B, f: F) -> bool
4133 where
4134 F: FnMut(Self::Item, <B as Iterator>::Item) -> ControlFlow<()>,
4135 {
4136 iter_eq(self, b, f)
4137 }
4138}
4139
4140#[cfg(not(feature = "ferrocene_certified"))]
4141impl<A: Iterator + TrustedLen, B: Iterator + TrustedLen> SpecIterEq<B> for A {
4142 #[inline]
4143 fn spec_iter_eq<F>(self, b: B, f: F) -> bool
4144 where
4145 F: FnMut(Self::Item, <B as Iterator>::Item) -> ControlFlow<()>,
4146 {
4147 // we *can't* short-circuit if:
4148 match (self.size_hint(), b.size_hint()) {
4149 // ... both iterators have the same length
4150 ((_, Some(a)), (_, Some(b))) if a == b => {}
4151 // ... or both of them are longer than `usize::MAX` (i.e. have an unknown length).
4152 ((_, None), (_, None)) => {}
4153 // otherwise, we can ascertain that they are unequal without actually comparing items
4154 _ => return false,
4155 }
4156
4157 iter_eq(self, b, f)
4158 }
4159}
4160
4161/// Compares two iterators element-wise using the given function.
4162///
4163/// If `ControlFlow::Continue(())` is returned from the function, the comparison moves on to the next
4164/// elements of both iterators. Returning `ControlFlow::Break(x)` short-circuits the iteration and
4165/// returns `ControlFlow::Break(x)`. If one of the iterators runs out of elements,
4166/// `ControlFlow::Continue(ord)` is returned where `ord` is the result of comparing the lengths of
4167/// the iterators.
4168///
4169/// Isolates the logic shared by ['cmp_by'](Iterator::cmp_by),
4170/// ['partial_cmp_by'](Iterator::partial_cmp_by), and ['eq_by'](Iterator::eq_by).
4171#[inline]
4172#[cfg(not(feature = "ferrocene_certified"))]
4173fn iter_compare<A, B, F, T>(mut a: A, mut b: B, f: F) -> ControlFlow<T, Ordering>
4174where
4175 A: Iterator,
4176 B: Iterator,
4177 F: FnMut(A::Item, B::Item) -> ControlFlow<T>,
4178{
4179 #[inline]
4180 fn compare<'a, B, X, T>(
4181 b: &'a mut B,
4182 mut f: impl FnMut(X, B::Item) -> ControlFlow<T> + 'a,
4183 ) -> impl FnMut(X) -> ControlFlow<ControlFlow<T, Ordering>> + 'a
4184 where
4185 B: Iterator,
4186 {
4187 move |x| match b.next() {
4188 None => ControlFlow::Break(ControlFlow::Continue(Ordering::Greater)),
4189 Some(y) => f(x, y).map_break(ControlFlow::Break),
4190 }
4191 }
4192
4193 match a.try_for_each(compare(&mut b, f)) {
4194 ControlFlow::Continue(()) => ControlFlow::Continue(match b.next() {
4195 None => Ordering::Equal,
4196 Some(_) => Ordering::Less,
4197 }),
4198 ControlFlow::Break(x) => x,
4199 }
4200}
4201
4202#[inline]
4203#[cfg(not(feature = "ferrocene_certified"))]
4204fn iter_eq<A, B, F>(a: A, b: B, f: F) -> bool
4205where
4206 A: Iterator,
4207 B: Iterator,
4208 F: FnMut(A::Item, B::Item) -> ControlFlow<()>,
4209{
4210 iter_compare(a, b, f).continue_value().is_some_and(|ord| ord == Ordering::Equal)
4211}
4212
4213/// Implements `Iterator` for mutable references to iterators, such as those produced by [`Iterator::by_ref`].
4214///
4215/// This implementation passes all method calls on to the original iterator.
4216#[stable(feature = "rust1", since = "1.0.0")]
4217#[cfg(not(feature = "ferrocene_certified"))]
4218impl<I: Iterator + ?Sized> Iterator for &mut I {
4219 type Item = I::Item;
4220 #[inline]
4221 fn next(&mut self) -> Option<I::Item> {
4222 (**self).next()
4223 }
4224 fn size_hint(&self) -> (usize, Option<usize>) {
4225 (**self).size_hint()
4226 }
4227 fn advance_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
4228 (**self).advance_by(n)
4229 }
4230 fn nth(&mut self, n: usize) -> Option<Self::Item> {
4231 (**self).nth(n)
4232 }
4233 fn fold<B, F>(self, init: B, f: F) -> B
4234 where
4235 F: FnMut(B, Self::Item) -> B,
4236 {
4237 self.spec_fold(init, f)
4238 }
4239 fn try_fold<B, F, R>(&mut self, init: B, f: F) -> R
4240 where
4241 F: FnMut(B, Self::Item) -> R,
4242 R: Try<Output = B>,
4243 {
4244 self.spec_try_fold(init, f)
4245 }
4246}
4247
4248/// Helper trait to specialize `fold` and `try_fold` for `&mut I where I: Sized`
4249#[cfg(not(feature = "ferrocene_certified"))]
4250trait IteratorRefSpec: Iterator {
4251 fn spec_fold<B, F>(self, init: B, f: F) -> B
4252 where
4253 F: FnMut(B, Self::Item) -> B;
4254
4255 fn spec_try_fold<B, F, R>(&mut self, init: B, f: F) -> R
4256 where
4257 F: FnMut(B, Self::Item) -> R,
4258 R: Try<Output = B>;
4259}
4260
4261#[cfg(not(feature = "ferrocene_certified"))]
4262impl<I: Iterator + ?Sized> IteratorRefSpec for &mut I {
4263 default fn spec_fold<B, F>(self, init: B, mut f: F) -> B
4264 where
4265 F: FnMut(B, Self::Item) -> B,
4266 {
4267 let mut accum = init;
4268 while let Some(x) = self.next() {
4269 accum = f(accum, x);
4270 }
4271 accum
4272 }
4273
4274 default fn spec_try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
4275 where
4276 F: FnMut(B, Self::Item) -> R,
4277 R: Try<Output = B>,
4278 {
4279 let mut accum = init;
4280 while let Some(x) = self.next() {
4281 accum = f(accum, x)?;
4282 }
4283 try { accum }
4284 }
4285}
4286
4287#[cfg(not(feature = "ferrocene_certified"))]
4288impl<I: Iterator> IteratorRefSpec for &mut I {
4289 impl_fold_via_try_fold! { spec_fold -> spec_try_fold }
4290
4291 fn spec_try_fold<B, F, R>(&mut self, init: B, f: F) -> R
4292 where
4293 F: FnMut(B, Self::Item) -> R,
4294 R: Try<Output = B>,
4295 {
4296 (**self).try_fold(init, f)
4297 }
4298}