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}