core/iter/traits/
iterator.rs

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