1 // Copyright 2013-2016 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 //! Composable external iteration.
13 //! If you've found yourself with a collection of some kind, and needed to
14 //! perform an operation on the elements of said collection, you'll quickly run
15 //! into 'iterators'. Iterators are heavily used in idiomatic Rust code, so
16 //! it's worth becoming familiar with them.
18 //! Before explaining more, let's talk about how this module is structured:
22 //! This module is largely organized by type:
24 //! * [Traits] are the core portion: these traits define what kind of iterators
25 //! exist and what you can do with them. The methods of these traits are worth
26 //! putting some extra study time into.
27 //! * [Functions] provide some helpful ways to create some basic iterators.
28 //! * [Structs] are often the return types of the various methods on this
29 //! module's traits. You'll usually want to look at the method that creates
30 //! the `struct`, rather than the `struct` itself. For more detail about why,
31 //! see '[Implementing Iterator](#implementing-iterator)'.
34 //! [Functions]: #functions
35 //! [Structs]: #structs
37 //! That's it! Let's dig into iterators.
41 //! The heart and soul of this module is the [`Iterator`] trait. The core of
42 //! [`Iterator`] looks like this:
47 //! fn next(&mut self) -> Option<Self::Item>;
51 //! An iterator has a method, [`next`], which when called, returns an
52 //! [`Option`]`<Item>`. [`next`] will return `Some(Item)` as long as there
53 //! are elements, and once they've all been exhausted, will return `None` to
54 //! indicate that iteration is finished. Individual iterators may choose to
55 //! resume iteration, and so calling [`next`] again may or may not eventually
56 //! start returning `Some(Item)` again at some point.
58 //! [`Iterator`]'s full definition includes a number of other methods as well,
59 //! but they are default methods, built on top of [`next`], and so you get
62 //! Iterators are also composable, and it's common to chain them together to do
63 //! more complex forms of processing. See the [Adapters](#adapters) section
64 //! below for more details.
66 //! [`Iterator`]: trait.Iterator.html
67 //! [`next`]: trait.Iterator.html#tymethod.next
68 //! [`Option`]: ../../std/option/enum.Option.html
70 //! # The three forms of iteration
72 //! There are three common methods which can create iterators from a collection:
74 //! * `iter()`, which iterates over `&T`.
75 //! * `iter_mut()`, which iterates over `&mut T`.
76 //! * `into_iter()`, which iterates over `T`.
78 //! Various things in the standard library may implement one or more of the
79 //! three, where appropriate.
81 //! # Implementing Iterator
83 //! Creating an iterator of your own involves two steps: creating a `struct` to
84 //! hold the iterator's state, and then `impl`ementing [`Iterator`] for that
85 //! `struct`. This is why there are so many `struct`s in this module: there is
86 //! one for each iterator and iterator adapter.
88 //! Let's make an iterator named `Counter` which counts from `1` to `5`:
91 //! // First, the struct:
93 //! /// An iterator which counts from one to five
98 //! // we want our count to start at one, so let's add a new() method to help.
99 //! // This isn't strictly necessary, but is convenient. Note that we start
100 //! // `count` at zero, we'll see why in `next()`'s implementation below.
102 //! fn new() -> Counter {
103 //! Counter { count: 0 }
107 //! // Then, we implement `Iterator` for our `Counter`:
109 //! impl Iterator for Counter {
110 //! // we will be counting with usize
111 //! type Item = usize;
113 //! // next() is the only required method
114 //! fn next(&mut self) -> Option<usize> {
115 //! // increment our count. This is why we started at zero.
118 //! // check to see if we've finished counting or not.
119 //! if self.count < 6 {
127 //! // And now we can use it!
129 //! let mut counter = Counter::new();
131 //! let x = counter.next().unwrap();
132 //! println!("{}", x);
134 //! let x = counter.next().unwrap();
135 //! println!("{}", x);
137 //! let x = counter.next().unwrap();
138 //! println!("{}", x);
140 //! let x = counter.next().unwrap();
141 //! println!("{}", x);
143 //! let x = counter.next().unwrap();
144 //! println!("{}", x);
147 //! This will print `1` through `5`, each on their own line.
149 //! Calling `next()` this way gets repetitive. Rust has a construct which can
150 //! call `next()` on your iterator, until it reaches `None`. Let's go over that
153 //! # for Loops and IntoIterator
155 //! Rust's `for` loop syntax is actually sugar for iterators. Here's a basic
156 //! example of `for`:
159 //! let values = vec![1, 2, 3, 4, 5];
161 //! for x in values {
162 //! println!("{}", x);
166 //! This will print the numbers one through five, each on their own line. But
167 //! you'll notice something here: we never called anything on our vector to
168 //! produce an iterator. What gives?
170 //! There's a trait in the standard library for converting something into an
171 //! iterator: [`IntoIterator`]. This trait has one method, [`into_iter`],
172 //! which converts the thing implementing [`IntoIterator`] into an iterator.
173 //! Let's take a look at that `for` loop again, and what the compiler converts
176 //! [`IntoIterator`]: trait.IntoIterator.html
177 //! [`into_iter`]: trait.IntoIterator.html#tymethod.into_iter
180 //! let values = vec![1, 2, 3, 4, 5];
182 //! for x in values {
183 //! println!("{}", x);
187 //! Rust de-sugars this into:
190 //! let values = vec![1, 2, 3, 4, 5];
192 //! let result = match IntoIterator::into_iter(values) {
193 //! mut iter => loop {
195 //! match iter.next() {
196 //! Some(val) => next = val,
200 //! let () = { println!("{}", x); };
207 //! First, we call `into_iter()` on the value. Then, we match on the iterator
208 //! that returns, calling [`next`] over and over until we see a `None`. At
209 //! that point, we `break` out of the loop, and we're done iterating.
211 //! There's one more subtle bit here: the standard library contains an
212 //! interesting implementation of [`IntoIterator`]:
214 //! ```ignore (only-for-syntax-highlight)
215 //! impl<I: Iterator> IntoIterator for I
218 //! In other words, all [`Iterator`]s implement [`IntoIterator`], by just
219 //! returning themselves. This means two things:
221 //! 1. If you're writing an [`Iterator`], you can use it with a `for` loop.
222 //! 2. If you're creating a collection, implementing [`IntoIterator`] for it
223 //! will allow your collection to be used with the `for` loop.
227 //! Functions which take an [`Iterator`] and return another [`Iterator`] are
228 //! often called 'iterator adapters', as they're a form of the 'adapter
231 //! Common iterator adapters include [`map`], [`take`], and [`filter`].
232 //! For more, see their documentation.
234 //! [`map`]: trait.Iterator.html#method.map
235 //! [`take`]: trait.Iterator.html#method.take
236 //! [`filter`]: trait.Iterator.html#method.filter
240 //! Iterators (and iterator [adapters](#adapters)) are *lazy*. This means that
241 //! just creating an iterator doesn't _do_ a whole lot. Nothing really happens
242 //! until you call [`next`]. This is sometimes a source of confusion when
243 //! creating an iterator solely for its side effects. For example, the [`map`]
244 //! method calls a closure on each element it iterates over:
247 //! # #![allow(unused_must_use)]
248 //! let v = vec![1, 2, 3, 4, 5];
249 //! v.iter().map(|x| println!("{}", x));
252 //! This will not print any values, as we only created an iterator, rather than
253 //! using it. The compiler will warn us about this kind of behavior:
256 //! warning: unused result which must be used: iterator adaptors are lazy and
257 //! do nothing unless consumed
260 //! The idiomatic way to write a [`map`] for its side effects is to use a
261 //! `for` loop instead:
264 //! let v = vec![1, 2, 3, 4, 5];
267 //! println!("{}", x);
271 //! [`map`]: trait.Iterator.html#method.map
273 //! The two most common ways to evaluate an iterator are to use a `for` loop
274 //! like this, or using the [`collect`] method to produce a new collection.
276 //! [`collect`]: trait.Iterator.html#method.collect
280 //! Iterators do not have to be finite. As an example, an open-ended range is
281 //! an infinite iterator:
284 //! let numbers = 0..;
287 //! It is common to use the [`take`] iterator adapter to turn an infinite
288 //! iterator into a finite one:
291 //! let numbers = 0..;
292 //! let five_numbers = numbers.take(5);
294 //! for number in five_numbers {
295 //! println!("{}", number);
299 //! This will print the numbers `0` through `4`, each on their own line.
301 //! Bear in mind that methods on infinite iterators, even those for which a
302 //! result can be determined mathematically in finite time, may not terminate.
303 //! Specifically, methods such as [`min`], which in the general case require
304 //! traversing every element in the iterator, are likely not to return
305 //! successfully for any infinite iterators.
308 //! let ones = std::iter::repeat(1);
309 //! let least = ones.min().unwrap(); // Oh no! An infinite loop!
310 //! // `ones.min()` causes an infinite loop, so we won't reach this point!
311 //! println!("The smallest number one is {}.", least);
314 //! [`take`]: trait.Iterator.html#method.take
315 //! [`min`]: trait.Iterator.html#method.min
317 #![stable(feature = "rust1", since = "1.0.0")]
321 use iter_private::TrustedRandomAccess;
322 use ops::{self, Try};
327 #[stable(feature = "rust1", since = "1.0.0")]
328 pub use self::iterator::Iterator;
330 #[unstable(feature = "step_trait",
331 reason = "likely to be replaced by finer-grained traits",
333 pub use self::range::Step;
335 #[stable(feature = "rust1", since = "1.0.0")]
336 pub use self::sources::{Repeat, repeat};
337 #[stable(feature = "iterator_repeat_with", since = "1.28.0")]
338 pub use self::sources::{RepeatWith, repeat_with};
339 #[stable(feature = "iter_empty", since = "1.2.0")]
340 pub use self::sources::{Empty, empty};
341 #[stable(feature = "iter_once", since = "1.2.0")]
342 pub use self::sources::{Once, once};
344 #[stable(feature = "rust1", since = "1.0.0")]
345 pub use self::traits::{FromIterator, IntoIterator, DoubleEndedIterator, Extend};
346 #[stable(feature = "rust1", since = "1.0.0")]
347 pub use self::traits::{ExactSizeIterator, Sum, Product};
348 #[stable(feature = "fused", since = "1.26.0")]
349 pub use self::traits::FusedIterator;
350 #[unstable(feature = "trusted_len", issue = "37572")]
351 pub use self::traits::TrustedLen;
358 /// Used to make try_fold closures more like normal loops
360 enum LoopState<C, B> {
365 impl<C, B> Try for LoopState<C, B> {
369 fn into_result(self) -> Result<Self::Ok, Self::Error> {
371 LoopState::Continue(y) => Ok(y),
372 LoopState::Break(x) => Err(x),
376 fn from_error(v: Self::Error) -> Self { LoopState::Break(v) }
378 fn from_ok(v: Self::Ok) -> Self { LoopState::Continue(v) }
381 impl<C, B> LoopState<C, B> {
383 fn break_value(self) -> Option<B> {
385 LoopState::Continue(..) => None,
386 LoopState::Break(x) => Some(x),
391 impl<R: Try> LoopState<R::Ok, R> {
393 fn from_try(r: R) -> Self {
394 match Try::into_result(r) {
395 Ok(v) => LoopState::Continue(v),
396 Err(v) => LoopState::Break(Try::from_error(v)),
400 fn into_try(self) -> R {
402 LoopState::Continue(v) => Try::from_ok(v),
403 LoopState::Break(v) => v,
408 /// A double-ended iterator with the direction inverted.
410 /// This `struct` is created by the [`rev`] method on [`Iterator`]. See its
411 /// documentation for more.
413 /// [`rev`]: trait.Iterator.html#method.rev
414 /// [`Iterator`]: trait.Iterator.html
415 #[derive(Clone, Debug)]
416 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
417 #[stable(feature = "rust1", since = "1.0.0")]
422 #[stable(feature = "rust1", since = "1.0.0")]
423 impl<I> Iterator for Rev<I> where I: DoubleEndedIterator {
424 type Item = <I as Iterator>::Item;
427 fn next(&mut self) -> Option<<I as Iterator>::Item> { self.iter.next_back() }
429 fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
431 fn try_fold<B, F, R>(&mut self, init: B, f: F) -> R where
432 Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
434 self.iter.try_rfold(init, f)
437 fn fold<Acc, F>(self, init: Acc, f: F) -> Acc
438 where F: FnMut(Acc, Self::Item) -> Acc,
440 self.iter.rfold(init, f)
444 fn find<P>(&mut self, predicate: P) -> Option<Self::Item>
445 where P: FnMut(&Self::Item) -> bool
447 self.iter.rfind(predicate)
451 fn rposition<P>(&mut self, predicate: P) -> Option<usize> where
452 P: FnMut(Self::Item) -> bool
454 self.iter.position(predicate)
458 #[stable(feature = "rust1", since = "1.0.0")]
459 impl<I> DoubleEndedIterator for Rev<I> where I: DoubleEndedIterator {
461 fn next_back(&mut self) -> Option<<I as Iterator>::Item> { self.iter.next() }
463 fn try_rfold<B, F, R>(&mut self, init: B, f: F) -> R where
464 Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
466 self.iter.try_fold(init, f)
469 fn rfold<Acc, F>(self, init: Acc, f: F) -> Acc
470 where F: FnMut(Acc, Self::Item) -> Acc,
472 self.iter.fold(init, f)
475 fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item>
476 where P: FnMut(&Self::Item) -> bool
478 self.iter.find(predicate)
482 #[stable(feature = "rust1", since = "1.0.0")]
483 impl<I> ExactSizeIterator for Rev<I>
484 where I: ExactSizeIterator + DoubleEndedIterator
486 fn len(&self) -> usize {
490 fn is_empty(&self) -> bool {
495 #[stable(feature = "fused", since = "1.26.0")]
496 impl<I> FusedIterator for Rev<I>
497 where I: FusedIterator + DoubleEndedIterator {}
499 #[unstable(feature = "trusted_len", issue = "37572")]
500 unsafe impl<I> TrustedLen for Rev<I>
501 where I: TrustedLen + DoubleEndedIterator {}
503 /// An iterator that clones the elements of an underlying iterator.
505 /// This `struct` is created by the [`cloned`] method on [`Iterator`]. See its
506 /// documentation for more.
508 /// [`cloned`]: trait.Iterator.html#method.cloned
509 /// [`Iterator`]: trait.Iterator.html
510 #[stable(feature = "iter_cloned", since = "1.1.0")]
511 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
512 #[derive(Clone, Debug)]
513 pub struct Cloned<I> {
517 #[stable(feature = "iter_cloned", since = "1.1.0")]
518 impl<'a, I, T: 'a> Iterator for Cloned<I>
519 where I: Iterator<Item=&'a T>, T: Clone
523 fn next(&mut self) -> Option<T> {
524 self.it.next().cloned()
527 fn size_hint(&self) -> (usize, Option<usize>) {
531 fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R where
532 Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
534 self.it.try_fold(init, move |acc, elt| f(acc, elt.clone()))
537 fn fold<Acc, F>(self, init: Acc, mut f: F) -> Acc
538 where F: FnMut(Acc, Self::Item) -> Acc,
540 self.it.fold(init, move |acc, elt| f(acc, elt.clone()))
544 #[stable(feature = "iter_cloned", since = "1.1.0")]
545 impl<'a, I, T: 'a> DoubleEndedIterator for Cloned<I>
546 where I: DoubleEndedIterator<Item=&'a T>, T: Clone
548 fn next_back(&mut self) -> Option<T> {
549 self.it.next_back().cloned()
552 fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R where
553 Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
555 self.it.try_rfold(init, move |acc, elt| f(acc, elt.clone()))
558 fn rfold<Acc, F>(self, init: Acc, mut f: F) -> Acc
559 where F: FnMut(Acc, Self::Item) -> Acc,
561 self.it.rfold(init, move |acc, elt| f(acc, elt.clone()))
565 #[stable(feature = "iter_cloned", since = "1.1.0")]
566 impl<'a, I, T: 'a> ExactSizeIterator for Cloned<I>
567 where I: ExactSizeIterator<Item=&'a T>, T: Clone
569 fn len(&self) -> usize {
573 fn is_empty(&self) -> bool {
578 #[stable(feature = "fused", since = "1.26.0")]
579 impl<'a, I, T: 'a> FusedIterator for Cloned<I>
580 where I: FusedIterator<Item=&'a T>, T: Clone
584 unsafe impl<'a, I, T: 'a> TrustedRandomAccess for Cloned<I>
585 where I: TrustedRandomAccess<Item=&'a T>, T: Clone
587 default unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item {
588 self.it.get_unchecked(i).clone()
592 default fn may_have_side_effect() -> bool { true }
596 unsafe impl<'a, I, T: 'a> TrustedRandomAccess for Cloned<I>
597 where I: TrustedRandomAccess<Item=&'a T>, T: Copy
599 unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item {
600 *self.it.get_unchecked(i)
604 fn may_have_side_effect() -> bool { false }
607 #[unstable(feature = "trusted_len", issue = "37572")]
608 unsafe impl<'a, I, T: 'a> TrustedLen for Cloned<I>
609 where I: TrustedLen<Item=&'a T>,
613 /// An iterator that repeats endlessly.
615 /// This `struct` is created by the [`cycle`] method on [`Iterator`]. See its
616 /// documentation for more.
618 /// [`cycle`]: trait.Iterator.html#method.cycle
619 /// [`Iterator`]: trait.Iterator.html
620 #[derive(Clone, Debug)]
621 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
622 #[stable(feature = "rust1", since = "1.0.0")]
623 pub struct Cycle<I> {
628 #[stable(feature = "rust1", since = "1.0.0")]
629 impl<I> Iterator for Cycle<I> where I: Clone + Iterator {
630 type Item = <I as Iterator>::Item;
633 fn next(&mut self) -> Option<<I as Iterator>::Item> {
634 match self.iter.next() {
635 None => { self.iter = self.orig.clone(); self.iter.next() }
641 fn size_hint(&self) -> (usize, Option<usize>) {
642 // the cycle iterator is either empty or infinite
643 match self.orig.size_hint() {
644 sz @ (0, Some(0)) => sz,
646 _ => (usize::MAX, None)
651 #[stable(feature = "fused", since = "1.26.0")]
652 impl<I> FusedIterator for Cycle<I> where I: Clone + Iterator {}
654 /// An iterator for stepping iterators by a custom amount.
656 /// This `struct` is created by the [`step_by`] method on [`Iterator`]. See
657 /// its documentation for more.
659 /// [`step_by`]: trait.Iterator.html#method.step_by
660 /// [`Iterator`]: trait.Iterator.html
661 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
662 #[stable(feature = "iterator_step_by", since = "1.28.0")]
663 #[derive(Clone, Debug)]
664 pub struct StepBy<I> {
670 #[stable(feature = "iterator_step_by", since = "1.28.0")]
671 impl<I> Iterator for StepBy<I> where I: Iterator {
675 fn next(&mut self) -> Option<Self::Item> {
676 <Self as StepBySpecIterator>::spec_next(self)
680 fn size_hint(&self) -> (usize, Option<usize>) {
681 let inner_hint = self.iter.size_hint();
684 let f = |n| if n == 0 { 0 } else { 1 + (n-1)/(self.step+1) };
685 (f(inner_hint.0), inner_hint.1.map(f))
687 let f = |n| n / (self.step+1);
688 (f(inner_hint.0), inner_hint.1.map(f))
693 fn nth(&mut self, mut n: usize) -> Option<Self::Item> {
695 self.first_take = false;
696 let first = self.iter.next();
702 // n and self.step are indices, we need to add 1 to get the amount of elements
703 // When calling `.nth`, we need to subtract 1 again to convert back to an index
704 // step + 1 can't overflow because `.step_by` sets `self.step` to `step - 1`
705 let mut step = self.step + 1;
706 // n + 1 could overflow
707 // thus, if n is usize::MAX, instead of adding one, we call .nth(step)
709 self.iter.nth(step - 1);
716 let mul = n.checked_mul(step);
717 if unsafe { intrinsics::likely(mul.is_some()) } {
718 return self.iter.nth(mul.unwrap() - 1);
720 let div_n = usize::MAX / n;
721 let div_step = usize::MAX / step;
722 let nth_n = div_n * n;
723 let nth_step = div_step * step;
724 let nth = if nth_n > nth_step {
731 self.iter.nth(nth - 1);
736 // hidden trait for specializing iterator methods
737 // could be generalized but is currently only used for StepBy
738 trait StepBySpecIterator {
740 fn spec_next(&mut self) -> Option<Self::Item>;
743 impl<I> StepBySpecIterator for StepBy<I>
750 default fn spec_next(&mut self) -> Option<I::Item> {
752 self.first_take = false;
755 self.iter.nth(self.step)
760 impl<T> StepBySpecIterator for StepBy<ops::Range<T>>
765 fn spec_next(&mut self) -> Option<Self::Item> {
766 self.first_take = false;
767 if !(self.iter.start < self.iter.end) {
770 // add 1 to self.step to get original step size back
771 // it was decremented for the general case on construction
772 if let Some(n) = self.iter.start.add_usize(self.step+1) {
773 let next = mem::replace(&mut self.iter.start, n);
776 let last = self.iter.start.clone();
777 self.iter.start = self.iter.end.clone();
783 impl<T> StepBySpecIterator for StepBy<ops::RangeInclusive<T>>
788 fn spec_next(&mut self) -> Option<Self::Item> {
789 self.first_take = false;
790 if self.iter.is_empty() {
791 self.iter.is_iterating = Some(false);
794 // add 1 to self.step to get original step size back
795 // it was decremented for the general case on construction
796 if let Some(n) = self.iter.start.add_usize(self.step+1) {
797 self.iter.is_iterating = Some(n <= self.iter.end);
798 let next = mem::replace(&mut self.iter.start, n);
801 let last = self.iter.start.clone();
802 self.iter.is_iterating = Some(false);
808 // StepBy can only make the iterator shorter, so the len will still fit.
809 #[stable(feature = "iterator_step_by", since = "1.28.0")]
810 impl<I> ExactSizeIterator for StepBy<I> where I: ExactSizeIterator {}
812 /// An iterator that strings two iterators together.
814 /// This `struct` is created by the [`chain`] method on [`Iterator`]. See its
815 /// documentation for more.
817 /// [`chain`]: trait.Iterator.html#method.chain
818 /// [`Iterator`]: trait.Iterator.html
819 #[derive(Clone, Debug)]
820 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
821 #[stable(feature = "rust1", since = "1.0.0")]
822 pub struct Chain<A, B> {
828 // The iterator protocol specifies that iteration ends with the return value
829 // `None` from `.next()` (or `.next_back()`) and it is unspecified what
830 // further calls return. The chain adaptor must account for this since it uses
833 // It uses three states:
835 // - Both: `a` and `b` are remaining
836 // - Front: `a` remaining
837 // - Back: `b` remaining
839 // The fourth state (neither iterator is remaining) only occurs after Chain has
840 // returned None once, so we don't need to store this state.
841 #[derive(Clone, Debug)]
843 // both front and back iterator are remaining
845 // only front is remaining
847 // only back is remaining
851 #[stable(feature = "rust1", since = "1.0.0")]
852 impl<A, B> Iterator for Chain<A, B> where
854 B: Iterator<Item = A::Item>
859 fn next(&mut self) -> Option<A::Item> {
861 ChainState::Both => match self.a.next() {
862 elt @ Some(..) => elt,
864 self.state = ChainState::Back;
868 ChainState::Front => self.a.next(),
869 ChainState::Back => self.b.next(),
874 #[rustc_inherit_overflow_checks]
875 fn count(self) -> usize {
877 ChainState::Both => self.a.count() + self.b.count(),
878 ChainState::Front => self.a.count(),
879 ChainState::Back => self.b.count(),
883 fn try_fold<Acc, F, R>(&mut self, init: Acc, mut f: F) -> R where
884 Self: Sized, F: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
886 let mut accum = init;
888 ChainState::Both | ChainState::Front => {
889 accum = self.a.try_fold(accum, &mut f)?;
890 if let ChainState::Both = self.state {
891 self.state = ChainState::Back;
896 if let ChainState::Back = self.state {
897 accum = self.b.try_fold(accum, &mut f)?;
902 fn fold<Acc, F>(self, init: Acc, mut f: F) -> Acc
903 where F: FnMut(Acc, Self::Item) -> Acc,
905 let mut accum = init;
907 ChainState::Both | ChainState::Front => {
908 accum = self.a.fold(accum, &mut f);
913 ChainState::Both | ChainState::Back => {
914 accum = self.b.fold(accum, &mut f);
922 fn nth(&mut self, mut n: usize) -> Option<A::Item> {
924 ChainState::Both | ChainState::Front => {
925 for x in self.a.by_ref() {
931 if let ChainState::Both = self.state {
932 self.state = ChainState::Back;
935 ChainState::Back => {}
937 if let ChainState::Back = self.state {
945 fn find<P>(&mut self, mut predicate: P) -> Option<Self::Item> where
946 P: FnMut(&Self::Item) -> bool,
949 ChainState::Both => match self.a.find(&mut predicate) {
951 self.state = ChainState::Back;
952 self.b.find(predicate)
956 ChainState::Front => self.a.find(predicate),
957 ChainState::Back => self.b.find(predicate),
962 fn last(self) -> Option<A::Item> {
964 ChainState::Both => {
965 // Must exhaust a before b.
966 let a_last = self.a.last();
967 let b_last = self.b.last();
970 ChainState::Front => self.a.last(),
971 ChainState::Back => self.b.last()
976 fn size_hint(&self) -> (usize, Option<usize>) {
977 let (a_lower, a_upper) = self.a.size_hint();
978 let (b_lower, b_upper) = self.b.size_hint();
980 let lower = a_lower.saturating_add(b_lower);
982 let upper = match (a_upper, b_upper) {
983 (Some(x), Some(y)) => x.checked_add(y),
991 #[stable(feature = "rust1", since = "1.0.0")]
992 impl<A, B> DoubleEndedIterator for Chain<A, B> where
993 A: DoubleEndedIterator,
994 B: DoubleEndedIterator<Item=A::Item>,
997 fn next_back(&mut self) -> Option<A::Item> {
999 ChainState::Both => match self.b.next_back() {
1000 elt @ Some(..) => elt,
1002 self.state = ChainState::Front;
1006 ChainState::Front => self.a.next_back(),
1007 ChainState::Back => self.b.next_back(),
1011 fn try_rfold<Acc, F, R>(&mut self, init: Acc, mut f: F) -> R where
1012 Self: Sized, F: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
1014 let mut accum = init;
1016 ChainState::Both | ChainState::Back => {
1017 accum = self.b.try_rfold(accum, &mut f)?;
1018 if let ChainState::Both = self.state {
1019 self.state = ChainState::Front;
1024 if let ChainState::Front = self.state {
1025 accum = self.a.try_rfold(accum, &mut f)?;
1030 fn rfold<Acc, F>(self, init: Acc, mut f: F) -> Acc
1031 where F: FnMut(Acc, Self::Item) -> Acc,
1033 let mut accum = init;
1035 ChainState::Both | ChainState::Back => {
1036 accum = self.b.rfold(accum, &mut f);
1041 ChainState::Both | ChainState::Front => {
1042 accum = self.a.rfold(accum, &mut f);
1051 // Note: *both* must be fused to handle double-ended iterators.
1052 #[stable(feature = "fused", since = "1.26.0")]
1053 impl<A, B> FusedIterator for Chain<A, B>
1054 where A: FusedIterator,
1055 B: FusedIterator<Item=A::Item>,
1058 #[unstable(feature = "trusted_len", issue = "37572")]
1059 unsafe impl<A, B> TrustedLen for Chain<A, B>
1060 where A: TrustedLen, B: TrustedLen<Item=A::Item>,
1063 /// An iterator that iterates two other iterators simultaneously.
1065 /// This `struct` is created by the [`zip`] method on [`Iterator`]. See its
1066 /// documentation for more.
1068 /// [`zip`]: trait.Iterator.html#method.zip
1069 /// [`Iterator`]: trait.Iterator.html
1070 #[derive(Clone, Debug)]
1071 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1072 #[stable(feature = "rust1", since = "1.0.0")]
1073 pub struct Zip<A, B> {
1076 // index and len are only used by the specialized version of zip
1081 #[stable(feature = "rust1", since = "1.0.0")]
1082 impl<A, B> Iterator for Zip<A, B> where A: Iterator, B: Iterator
1084 type Item = (A::Item, B::Item);
1087 fn next(&mut self) -> Option<Self::Item> {
1092 fn size_hint(&self) -> (usize, Option<usize>) {
1093 ZipImpl::size_hint(self)
1097 fn nth(&mut self, n: usize) -> Option<Self::Item> {
1098 ZipImpl::nth(self, n)
1102 #[stable(feature = "rust1", since = "1.0.0")]
1103 impl<A, B> DoubleEndedIterator for Zip<A, B> where
1104 A: DoubleEndedIterator + ExactSizeIterator,
1105 B: DoubleEndedIterator + ExactSizeIterator,
1108 fn next_back(&mut self) -> Option<(A::Item, B::Item)> {
1109 ZipImpl::next_back(self)
1113 // Zip specialization trait
1115 trait ZipImpl<A, B> {
1117 fn new(a: A, b: B) -> Self;
1118 fn next(&mut self) -> Option<Self::Item>;
1119 fn size_hint(&self) -> (usize, Option<usize>);
1120 fn nth(&mut self, n: usize) -> Option<Self::Item>;
1121 fn super_nth(&mut self, mut n: usize) -> Option<Self::Item> {
1122 while let Some(x) = self.next() {
1123 if n == 0 { return Some(x) }
1128 fn next_back(&mut self) -> Option<Self::Item>
1129 where A: DoubleEndedIterator + ExactSizeIterator,
1130 B: DoubleEndedIterator + ExactSizeIterator;
1135 impl<A, B> ZipImpl<A, B> for Zip<A, B>
1136 where A: Iterator, B: Iterator
1138 type Item = (A::Item, B::Item);
1139 default fn new(a: A, b: B) -> Self {
1149 default fn next(&mut self) -> Option<(A::Item, B::Item)> {
1150 self.a.next().and_then(|x| {
1151 self.b.next().and_then(|y| {
1158 default fn nth(&mut self, n: usize) -> Option<Self::Item> {
1163 default fn next_back(&mut self) -> Option<(A::Item, B::Item)>
1164 where A: DoubleEndedIterator + ExactSizeIterator,
1165 B: DoubleEndedIterator + ExactSizeIterator
1167 let a_sz = self.a.len();
1168 let b_sz = self.b.len();
1170 // Adjust a, b to equal length
1172 for _ in 0..a_sz - b_sz { self.a.next_back(); }
1174 for _ in 0..b_sz - a_sz { self.b.next_back(); }
1177 match (self.a.next_back(), self.b.next_back()) {
1178 (Some(x), Some(y)) => Some((x, y)),
1179 (None, None) => None,
1180 _ => unreachable!(),
1185 default fn size_hint(&self) -> (usize, Option<usize>) {
1186 let (a_lower, a_upper) = self.a.size_hint();
1187 let (b_lower, b_upper) = self.b.size_hint();
1189 let lower = cmp::min(a_lower, b_lower);
1191 let upper = match (a_upper, b_upper) {
1192 (Some(x), Some(y)) => Some(cmp::min(x,y)),
1193 (Some(x), None) => Some(x),
1194 (None, Some(y)) => Some(y),
1195 (None, None) => None
1203 impl<A, B> ZipImpl<A, B> for Zip<A, B>
1204 where A: TrustedRandomAccess, B: TrustedRandomAccess
1206 fn new(a: A, b: B) -> Self {
1207 let len = cmp::min(a.len(), b.len());
1217 fn next(&mut self) -> Option<(A::Item, B::Item)> {
1218 if self.index < self.len {
1222 Some((self.a.get_unchecked(i), self.b.get_unchecked(i)))
1224 } else if A::may_have_side_effect() && self.index < self.a.len() {
1225 // match the base implementation's potential side effects
1227 self.a.get_unchecked(self.index);
1237 fn size_hint(&self) -> (usize, Option<usize>) {
1238 let len = self.len - self.index;
1243 fn nth(&mut self, n: usize) -> Option<Self::Item> {
1244 let delta = cmp::min(n, self.len - self.index);
1245 let end = self.index + delta;
1246 while self.index < end {
1249 if A::may_have_side_effect() {
1250 unsafe { self.a.get_unchecked(i); }
1252 if B::may_have_side_effect() {
1253 unsafe { self.b.get_unchecked(i); }
1257 self.super_nth(n - delta)
1261 fn next_back(&mut self) -> Option<(A::Item, B::Item)>
1262 where A: DoubleEndedIterator + ExactSizeIterator,
1263 B: DoubleEndedIterator + ExactSizeIterator
1265 // Adjust a, b to equal length
1266 if A::may_have_side_effect() {
1267 let sz = self.a.len();
1269 for _ in 0..sz - cmp::max(self.len, self.index) {
1274 if B::may_have_side_effect() {
1275 let sz = self.b.len();
1277 for _ in 0..sz - self.len {
1282 if self.index < self.len {
1286 Some((self.a.get_unchecked(i), self.b.get_unchecked(i)))
1294 #[stable(feature = "rust1", since = "1.0.0")]
1295 impl<A, B> ExactSizeIterator for Zip<A, B>
1296 where A: ExactSizeIterator, B: ExactSizeIterator {}
1299 unsafe impl<A, B> TrustedRandomAccess for Zip<A, B>
1300 where A: TrustedRandomAccess,
1301 B: TrustedRandomAccess,
1303 unsafe fn get_unchecked(&mut self, i: usize) -> (A::Item, B::Item) {
1304 (self.a.get_unchecked(i), self.b.get_unchecked(i))
1307 fn may_have_side_effect() -> bool {
1308 A::may_have_side_effect() || B::may_have_side_effect()
1312 #[stable(feature = "fused", since = "1.26.0")]
1313 impl<A, B> FusedIterator for Zip<A, B>
1314 where A: FusedIterator, B: FusedIterator, {}
1316 #[unstable(feature = "trusted_len", issue = "37572")]
1317 unsafe impl<A, B> TrustedLen for Zip<A, B>
1318 where A: TrustedLen, B: TrustedLen,
1321 /// An iterator that maps the values of `iter` with `f`.
1323 /// This `struct` is created by the [`map`] method on [`Iterator`]. See its
1324 /// documentation for more.
1326 /// [`map`]: trait.Iterator.html#method.map
1327 /// [`Iterator`]: trait.Iterator.html
1329 /// # Notes about side effects
1331 /// The [`map`] iterator implements [`DoubleEndedIterator`], meaning that
1332 /// you can also [`map`] backwards:
1335 /// let v: Vec<i32> = vec![1, 2, 3].into_iter().map(|x| x + 1).rev().collect();
1337 /// assert_eq!(v, [4, 3, 2]);
1340 /// [`DoubleEndedIterator`]: trait.DoubleEndedIterator.html
1342 /// But if your closure has state, iterating backwards may act in a way you do
1343 /// not expect. Let's go through an example. First, in the forward direction:
1348 /// for pair in vec!['a', 'b', 'c'].into_iter()
1349 /// .map(|letter| { c += 1; (letter, c) }) {
1350 /// println!("{:?}", pair);
1354 /// This will print "('a', 1), ('b', 2), ('c', 3)".
1356 /// Now consider this twist where we add a call to `rev`. This version will
1357 /// print `('c', 1), ('b', 2), ('a', 3)`. Note that the letters are reversed,
1358 /// but the values of the counter still go in order. This is because `map()` is
1359 /// still being called lazily on each item, but we are popping items off the
1360 /// back of the vector now, instead of shifting them from the front.
1365 /// for pair in vec!['a', 'b', 'c'].into_iter()
1366 /// .map(|letter| { c += 1; (letter, c) })
1368 /// println!("{:?}", pair);
1371 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1372 #[stable(feature = "rust1", since = "1.0.0")]
1374 pub struct Map<I, F> {
1379 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1380 impl<I: fmt::Debug, F> fmt::Debug for Map<I, F> {
1381 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1382 f.debug_struct("Map")
1383 .field("iter", &self.iter)
1388 #[stable(feature = "rust1", since = "1.0.0")]
1389 impl<B, I: Iterator, F> Iterator for Map<I, F> where F: FnMut(I::Item) -> B {
1393 fn next(&mut self) -> Option<B> {
1394 self.iter.next().map(&mut self.f)
1398 fn size_hint(&self) -> (usize, Option<usize>) {
1399 self.iter.size_hint()
1402 fn try_fold<Acc, G, R>(&mut self, init: Acc, mut g: G) -> R where
1403 Self: Sized, G: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
1405 let f = &mut self.f;
1406 self.iter.try_fold(init, move |acc, elt| g(acc, f(elt)))
1409 fn fold<Acc, G>(self, init: Acc, mut g: G) -> Acc
1410 where G: FnMut(Acc, Self::Item) -> Acc,
1413 self.iter.fold(init, move |acc, elt| g(acc, f(elt)))
1417 #[stable(feature = "rust1", since = "1.0.0")]
1418 impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for Map<I, F> where
1419 F: FnMut(I::Item) -> B,
1422 fn next_back(&mut self) -> Option<B> {
1423 self.iter.next_back().map(&mut self.f)
1426 fn try_rfold<Acc, G, R>(&mut self, init: Acc, mut g: G) -> R where
1427 Self: Sized, G: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
1429 let f = &mut self.f;
1430 self.iter.try_rfold(init, move |acc, elt| g(acc, f(elt)))
1433 fn rfold<Acc, G>(self, init: Acc, mut g: G) -> Acc
1434 where G: FnMut(Acc, Self::Item) -> Acc,
1437 self.iter.rfold(init, move |acc, elt| g(acc, f(elt)))
1441 #[stable(feature = "rust1", since = "1.0.0")]
1442 impl<B, I: ExactSizeIterator, F> ExactSizeIterator for Map<I, F>
1443 where F: FnMut(I::Item) -> B
1445 fn len(&self) -> usize {
1449 fn is_empty(&self) -> bool {
1450 self.iter.is_empty()
1454 #[stable(feature = "fused", since = "1.26.0")]
1455 impl<B, I: FusedIterator, F> FusedIterator for Map<I, F>
1456 where F: FnMut(I::Item) -> B {}
1458 #[unstable(feature = "trusted_len", issue = "37572")]
1459 unsafe impl<B, I, F> TrustedLen for Map<I, F>
1460 where I: TrustedLen,
1461 F: FnMut(I::Item) -> B {}
1464 unsafe impl<B, I, F> TrustedRandomAccess for Map<I, F>
1465 where I: TrustedRandomAccess,
1466 F: FnMut(I::Item) -> B,
1468 unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item {
1469 (self.f)(self.iter.get_unchecked(i))
1472 fn may_have_side_effect() -> bool { true }
1475 /// An iterator that filters the elements of `iter` with `predicate`.
1477 /// This `struct` is created by the [`filter`] method on [`Iterator`]. See its
1478 /// documentation for more.
1480 /// [`filter`]: trait.Iterator.html#method.filter
1481 /// [`Iterator`]: trait.Iterator.html
1482 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1483 #[stable(feature = "rust1", since = "1.0.0")]
1485 pub struct Filter<I, P> {
1490 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1491 impl<I: fmt::Debug, P> fmt::Debug for Filter<I, P> {
1492 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1493 f.debug_struct("Filter")
1494 .field("iter", &self.iter)
1499 #[stable(feature = "rust1", since = "1.0.0")]
1500 impl<I: Iterator, P> Iterator for Filter<I, P> where P: FnMut(&I::Item) -> bool {
1501 type Item = I::Item;
1504 fn next(&mut self) -> Option<I::Item> {
1505 for x in &mut self.iter {
1506 if (self.predicate)(&x) {
1514 fn size_hint(&self) -> (usize, Option<usize>) {
1515 let (_, upper) = self.iter.size_hint();
1516 (0, upper) // can't know a lower bound, due to the predicate
1519 // this special case allows the compiler to make `.filter(_).count()`
1520 // branchless. Barring perfect branch prediction (which is unattainable in
1521 // the general case), this will be much faster in >90% of cases (containing
1522 // virtually all real workloads) and only a tiny bit slower in the rest.
1524 // Having this specialization thus allows us to write `.filter(p).count()`
1525 // where we would otherwise write `.map(|x| p(x) as usize).sum()`, which is
1526 // less readable and also less backwards-compatible to Rust before 1.10.
1528 // Using the branchless version will also simplify the LLVM byte code, thus
1529 // leaving more budget for LLVM optimizations.
1531 fn count(mut self) -> usize {
1533 for x in &mut self.iter {
1534 count += (self.predicate)(&x) as usize;
1540 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
1541 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
1543 let predicate = &mut self.predicate;
1544 self.iter.try_fold(init, move |acc, item| if predicate(&item) {
1552 fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
1553 where Fold: FnMut(Acc, Self::Item) -> Acc,
1555 let mut predicate = self.predicate;
1556 self.iter.fold(init, move |acc, item| if predicate(&item) {
1564 #[stable(feature = "rust1", since = "1.0.0")]
1565 impl<I: DoubleEndedIterator, P> DoubleEndedIterator for Filter<I, P>
1566 where P: FnMut(&I::Item) -> bool,
1569 fn next_back(&mut self) -> Option<I::Item> {
1570 for x in self.iter.by_ref().rev() {
1571 if (self.predicate)(&x) {
1579 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
1580 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
1582 let predicate = &mut self.predicate;
1583 self.iter.try_rfold(init, move |acc, item| if predicate(&item) {
1591 fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
1592 where Fold: FnMut(Acc, Self::Item) -> Acc,
1594 let mut predicate = self.predicate;
1595 self.iter.rfold(init, move |acc, item| if predicate(&item) {
1603 #[stable(feature = "fused", since = "1.26.0")]
1604 impl<I: FusedIterator, P> FusedIterator for Filter<I, P>
1605 where P: FnMut(&I::Item) -> bool {}
1607 /// An iterator that uses `f` to both filter and map elements from `iter`.
1609 /// This `struct` is created by the [`filter_map`] method on [`Iterator`]. See its
1610 /// documentation for more.
1612 /// [`filter_map`]: trait.Iterator.html#method.filter_map
1613 /// [`Iterator`]: trait.Iterator.html
1614 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1615 #[stable(feature = "rust1", since = "1.0.0")]
1617 pub struct FilterMap<I, F> {
1622 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1623 impl<I: fmt::Debug, F> fmt::Debug for FilterMap<I, F> {
1624 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1625 f.debug_struct("FilterMap")
1626 .field("iter", &self.iter)
1631 #[stable(feature = "rust1", since = "1.0.0")]
1632 impl<B, I: Iterator, F> Iterator for FilterMap<I, F>
1633 where F: FnMut(I::Item) -> Option<B>,
1638 fn next(&mut self) -> Option<B> {
1639 for x in self.iter.by_ref() {
1640 if let Some(y) = (self.f)(x) {
1648 fn size_hint(&self) -> (usize, Option<usize>) {
1649 let (_, upper) = self.iter.size_hint();
1650 (0, upper) // can't know a lower bound, due to the predicate
1654 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
1655 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
1657 let f = &mut self.f;
1658 self.iter.try_fold(init, move |acc, item| match f(item) {
1659 Some(x) => fold(acc, x),
1660 None => Try::from_ok(acc),
1665 fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
1666 where Fold: FnMut(Acc, Self::Item) -> Acc,
1669 self.iter.fold(init, move |acc, item| match f(item) {
1670 Some(x) => fold(acc, x),
1676 #[stable(feature = "rust1", since = "1.0.0")]
1677 impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for FilterMap<I, F>
1678 where F: FnMut(I::Item) -> Option<B>,
1681 fn next_back(&mut self) -> Option<B> {
1682 for x in self.iter.by_ref().rev() {
1683 if let Some(y) = (self.f)(x) {
1691 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
1692 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
1694 let f = &mut self.f;
1695 self.iter.try_rfold(init, move |acc, item| match f(item) {
1696 Some(x) => fold(acc, x),
1697 None => Try::from_ok(acc),
1702 fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
1703 where Fold: FnMut(Acc, Self::Item) -> Acc,
1706 self.iter.rfold(init, move |acc, item| match f(item) {
1707 Some(x) => fold(acc, x),
1713 #[stable(feature = "fused", since = "1.26.0")]
1714 impl<B, I: FusedIterator, F> FusedIterator for FilterMap<I, F>
1715 where F: FnMut(I::Item) -> Option<B> {}
1717 /// An iterator that yields the current count and the element during iteration.
1719 /// This `struct` is created by the [`enumerate`] method on [`Iterator`]. See its
1720 /// documentation for more.
1722 /// [`enumerate`]: trait.Iterator.html#method.enumerate
1723 /// [`Iterator`]: trait.Iterator.html
1724 #[derive(Clone, Debug)]
1725 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1726 #[stable(feature = "rust1", since = "1.0.0")]
1727 pub struct Enumerate<I> {
1732 #[stable(feature = "rust1", since = "1.0.0")]
1733 impl<I> Iterator for Enumerate<I> where I: Iterator {
1734 type Item = (usize, <I as Iterator>::Item);
1736 /// # Overflow Behavior
1738 /// The method does no guarding against overflows, so enumerating more than
1739 /// `usize::MAX` elements either produces the wrong result or panics. If
1740 /// debug assertions are enabled, a panic is guaranteed.
1744 /// Might panic if the index of the element overflows a `usize`.
1746 #[rustc_inherit_overflow_checks]
1747 fn next(&mut self) -> Option<(usize, <I as Iterator>::Item)> {
1748 self.iter.next().map(|a| {
1749 let ret = (self.count, a);
1750 // Possible undefined overflow.
1757 fn size_hint(&self) -> (usize, Option<usize>) {
1758 self.iter.size_hint()
1762 #[rustc_inherit_overflow_checks]
1763 fn nth(&mut self, n: usize) -> Option<(usize, I::Item)> {
1764 self.iter.nth(n).map(|a| {
1765 let i = self.count + n;
1772 fn count(self) -> usize {
1777 #[rustc_inherit_overflow_checks]
1778 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
1779 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
1781 let count = &mut self.count;
1782 self.iter.try_fold(init, move |acc, item| {
1783 let acc = fold(acc, (*count, item));
1790 #[rustc_inherit_overflow_checks]
1791 fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
1792 where Fold: FnMut(Acc, Self::Item) -> Acc,
1794 let mut count = self.count;
1795 self.iter.fold(init, move |acc, item| {
1796 let acc = fold(acc, (count, item));
1803 #[stable(feature = "rust1", since = "1.0.0")]
1804 impl<I> DoubleEndedIterator for Enumerate<I> where
1805 I: ExactSizeIterator + DoubleEndedIterator
1808 fn next_back(&mut self) -> Option<(usize, <I as Iterator>::Item)> {
1809 self.iter.next_back().map(|a| {
1810 let len = self.iter.len();
1811 // Can safely add, `ExactSizeIterator` promises that the number of
1812 // elements fits into a `usize`.
1813 (self.count + len, a)
1818 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
1819 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
1821 // Can safely add and subtract the count, as `ExactSizeIterator` promises
1822 // that the number of elements fits into a `usize`.
1823 let mut count = self.count + self.iter.len();
1824 self.iter.try_rfold(init, move |acc, item| {
1826 fold(acc, (count, item))
1831 fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
1832 where Fold: FnMut(Acc, Self::Item) -> Acc,
1834 // Can safely add and subtract the count, as `ExactSizeIterator` promises
1835 // that the number of elements fits into a `usize`.
1836 let mut count = self.count + self.iter.len();
1837 self.iter.rfold(init, move |acc, item| {
1839 fold(acc, (count, item))
1844 #[stable(feature = "rust1", since = "1.0.0")]
1845 impl<I> ExactSizeIterator for Enumerate<I> where I: ExactSizeIterator {
1846 fn len(&self) -> usize {
1850 fn is_empty(&self) -> bool {
1851 self.iter.is_empty()
1856 unsafe impl<I> TrustedRandomAccess for Enumerate<I>
1857 where I: TrustedRandomAccess
1859 unsafe fn get_unchecked(&mut self, i: usize) -> (usize, I::Item) {
1860 (self.count + i, self.iter.get_unchecked(i))
1863 fn may_have_side_effect() -> bool {
1864 I::may_have_side_effect()
1868 #[stable(feature = "fused", since = "1.26.0")]
1869 impl<I> FusedIterator for Enumerate<I> where I: FusedIterator {}
1871 #[unstable(feature = "trusted_len", issue = "37572")]
1872 unsafe impl<I> TrustedLen for Enumerate<I>
1873 where I: TrustedLen,
1877 /// An iterator with a `peek()` that returns an optional reference to the next
1880 /// This `struct` is created by the [`peekable`] method on [`Iterator`]. See its
1881 /// documentation for more.
1883 /// [`peekable`]: trait.Iterator.html#method.peekable
1884 /// [`Iterator`]: trait.Iterator.html
1885 #[derive(Clone, Debug)]
1886 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1887 #[stable(feature = "rust1", since = "1.0.0")]
1888 pub struct Peekable<I: Iterator> {
1890 /// Remember a peeked value, even if it was None.
1891 peeked: Option<Option<I::Item>>,
1894 // Peekable must remember if a None has been seen in the `.peek()` method.
1895 // It ensures that `.peek(); .peek();` or `.peek(); .next();` only advances the
1896 // underlying iterator at most once. This does not by itself make the iterator
1898 #[stable(feature = "rust1", since = "1.0.0")]
1899 impl<I: Iterator> Iterator for Peekable<I> {
1900 type Item = I::Item;
1903 fn next(&mut self) -> Option<I::Item> {
1904 match self.peeked.take() {
1906 None => self.iter.next(),
1911 #[rustc_inherit_overflow_checks]
1912 fn count(mut self) -> usize {
1913 match self.peeked.take() {
1915 Some(Some(_)) => 1 + self.iter.count(),
1916 None => self.iter.count(),
1921 fn nth(&mut self, n: usize) -> Option<I::Item> {
1922 // FIXME(#43234): merge these when borrow-checking gets better.
1924 match self.peeked.take() {
1926 None => self.iter.nth(n),
1929 match self.peeked.take() {
1931 Some(Some(_)) => self.iter.nth(n - 1),
1932 None => self.iter.nth(n),
1938 fn last(mut self) -> Option<I::Item> {
1939 let peek_opt = match self.peeked.take() {
1940 Some(None) => return None,
1944 self.iter.last().or(peek_opt)
1948 fn size_hint(&self) -> (usize, Option<usize>) {
1949 let peek_len = match self.peeked {
1950 Some(None) => return (0, Some(0)),
1954 let (lo, hi) = self.iter.size_hint();
1955 let lo = lo.saturating_add(peek_len);
1956 let hi = hi.and_then(|x| x.checked_add(peek_len));
1961 fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R where
1962 Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
1964 let acc = match self.peeked.take() {
1965 Some(None) => return Try::from_ok(init),
1966 Some(Some(v)) => f(init, v)?,
1969 self.iter.try_fold(acc, f)
1973 fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
1974 where Fold: FnMut(Acc, Self::Item) -> Acc,
1976 let acc = match self.peeked {
1977 Some(None) => return init,
1978 Some(Some(v)) => fold(init, v),
1981 self.iter.fold(acc, fold)
1985 #[stable(feature = "rust1", since = "1.0.0")]
1986 impl<I: ExactSizeIterator> ExactSizeIterator for Peekable<I> {}
1988 #[stable(feature = "fused", since = "1.26.0")]
1989 impl<I: FusedIterator> FusedIterator for Peekable<I> {}
1991 impl<I: Iterator> Peekable<I> {
1992 /// Returns a reference to the next() value without advancing the iterator.
1994 /// Like [`next`], if there is a value, it is wrapped in a `Some(T)`.
1995 /// But if the iteration is over, `None` is returned.
1997 /// [`next`]: trait.Iterator.html#tymethod.next
1999 /// Because `peek()` returns a reference, and many iterators iterate over
2000 /// references, there can be a possibly confusing situation where the
2001 /// return value is a double reference. You can see this effect in the
2009 /// let xs = [1, 2, 3];
2011 /// let mut iter = xs.iter().peekable();
2013 /// // peek() lets us see into the future
2014 /// assert_eq!(iter.peek(), Some(&&1));
2015 /// assert_eq!(iter.next(), Some(&1));
2017 /// assert_eq!(iter.next(), Some(&2));
2019 /// // The iterator does not advance even if we `peek` multiple times
2020 /// assert_eq!(iter.peek(), Some(&&3));
2021 /// assert_eq!(iter.peek(), Some(&&3));
2023 /// assert_eq!(iter.next(), Some(&3));
2025 /// // After the iterator is finished, so is `peek()`
2026 /// assert_eq!(iter.peek(), None);
2027 /// assert_eq!(iter.next(), None);
2030 #[stable(feature = "rust1", since = "1.0.0")]
2031 pub fn peek(&mut self) -> Option<&I::Item> {
2032 if self.peeked.is_none() {
2033 self.peeked = Some(self.iter.next());
2036 Some(Some(ref value)) => Some(value),
2038 _ => unreachable!(),
2043 /// An iterator that rejects elements while `predicate` is true.
2045 /// This `struct` is created by the [`skip_while`] method on [`Iterator`]. See its
2046 /// documentation for more.
2048 /// [`skip_while`]: trait.Iterator.html#method.skip_while
2049 /// [`Iterator`]: trait.Iterator.html
2050 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2051 #[stable(feature = "rust1", since = "1.0.0")]
2053 pub struct SkipWhile<I, P> {
2059 #[stable(feature = "core_impl_debug", since = "1.9.0")]
2060 impl<I: fmt::Debug, P> fmt::Debug for SkipWhile<I, P> {
2061 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2062 f.debug_struct("SkipWhile")
2063 .field("iter", &self.iter)
2064 .field("flag", &self.flag)
2069 #[stable(feature = "rust1", since = "1.0.0")]
2070 impl<I: Iterator, P> Iterator for SkipWhile<I, P>
2071 where P: FnMut(&I::Item) -> bool
2073 type Item = I::Item;
2076 fn next(&mut self) -> Option<I::Item> {
2077 let flag = &mut self.flag;
2078 let pred = &mut self.predicate;
2079 self.iter.find(move |x| {
2080 if *flag || !pred(x) {
2090 fn size_hint(&self) -> (usize, Option<usize>) {
2091 let (_, upper) = self.iter.size_hint();
2092 (0, upper) // can't know a lower bound, due to the predicate
2096 fn try_fold<Acc, Fold, R>(&mut self, mut init: Acc, mut fold: Fold) -> R where
2097 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
2101 Some(v) => init = fold(init, v)?,
2102 None => return Try::from_ok(init),
2105 self.iter.try_fold(init, fold)
2109 fn fold<Acc, Fold>(mut self, mut init: Acc, mut fold: Fold) -> Acc
2110 where Fold: FnMut(Acc, Self::Item) -> Acc,
2114 Some(v) => init = fold(init, v),
2115 None => return init,
2118 self.iter.fold(init, fold)
2122 #[stable(feature = "fused", since = "1.26.0")]
2123 impl<I, P> FusedIterator for SkipWhile<I, P>
2124 where I: FusedIterator, P: FnMut(&I::Item) -> bool {}
2126 /// An iterator that only accepts elements while `predicate` is true.
2128 /// This `struct` is created by the [`take_while`] method on [`Iterator`]. See its
2129 /// documentation for more.
2131 /// [`take_while`]: trait.Iterator.html#method.take_while
2132 /// [`Iterator`]: trait.Iterator.html
2133 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2134 #[stable(feature = "rust1", since = "1.0.0")]
2136 pub struct TakeWhile<I, P> {
2142 #[stable(feature = "core_impl_debug", since = "1.9.0")]
2143 impl<I: fmt::Debug, P> fmt::Debug for TakeWhile<I, P> {
2144 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2145 f.debug_struct("TakeWhile")
2146 .field("iter", &self.iter)
2147 .field("flag", &self.flag)
2152 #[stable(feature = "rust1", since = "1.0.0")]
2153 impl<I: Iterator, P> Iterator for TakeWhile<I, P>
2154 where P: FnMut(&I::Item) -> bool
2156 type Item = I::Item;
2159 fn next(&mut self) -> Option<I::Item> {
2163 self.iter.next().and_then(|x| {
2164 if (self.predicate)(&x) {
2175 fn size_hint(&self) -> (usize, Option<usize>) {
2176 let (_, upper) = self.iter.size_hint();
2177 (0, upper) // can't know a lower bound, due to the predicate
2181 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
2182 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
2187 let flag = &mut self.flag;
2188 let p = &mut self.predicate;
2189 self.iter.try_fold(init, move |acc, x|{
2191 LoopState::from_try(fold(acc, x))
2194 LoopState::Break(Try::from_ok(acc))
2201 #[stable(feature = "fused", since = "1.26.0")]
2202 impl<I, P> FusedIterator for TakeWhile<I, P>
2203 where I: FusedIterator, P: FnMut(&I::Item) -> bool {}
2205 /// An iterator that skips over `n` elements of `iter`.
2207 /// This `struct` is created by the [`skip`] method on [`Iterator`]. See its
2208 /// documentation for more.
2210 /// [`skip`]: trait.Iterator.html#method.skip
2211 /// [`Iterator`]: trait.Iterator.html
2212 #[derive(Clone, Debug)]
2213 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2214 #[stable(feature = "rust1", since = "1.0.0")]
2215 pub struct Skip<I> {
2220 #[stable(feature = "rust1", since = "1.0.0")]
2221 impl<I> Iterator for Skip<I> where I: Iterator {
2222 type Item = <I as Iterator>::Item;
2225 fn next(&mut self) -> Option<I::Item> {
2231 self.iter.nth(old_n)
2236 fn nth(&mut self, n: usize) -> Option<I::Item> {
2237 // Can't just add n + self.n due to overflow.
2241 let to_skip = self.n;
2244 if self.iter.nth(to_skip-1).is_none() {
2252 fn count(self) -> usize {
2253 self.iter.count().saturating_sub(self.n)
2257 fn last(mut self) -> Option<I::Item> {
2261 let next = self.next();
2263 // recurse. n should be 0.
2264 self.last().or(next)
2272 fn size_hint(&self) -> (usize, Option<usize>) {
2273 let (lower, upper) = self.iter.size_hint();
2275 let lower = lower.saturating_sub(self.n);
2276 let upper = upper.map(|x| x.saturating_sub(self.n));
2282 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
2283 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
2289 if self.iter.nth(n - 1).is_none() {
2290 return Try::from_ok(init);
2293 self.iter.try_fold(init, fold)
2297 fn fold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
2298 where Fold: FnMut(Acc, Self::Item) -> Acc,
2302 if self.iter.nth(self.n - 1).is_none() {
2306 self.iter.fold(init, fold)
2310 #[stable(feature = "rust1", since = "1.0.0")]
2311 impl<I> ExactSizeIterator for Skip<I> where I: ExactSizeIterator {}
2313 #[stable(feature = "double_ended_skip_iterator", since = "1.9.0")]
2314 impl<I> DoubleEndedIterator for Skip<I> where I: DoubleEndedIterator + ExactSizeIterator {
2315 fn next_back(&mut self) -> Option<Self::Item> {
2317 self.iter.next_back()
2323 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
2324 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
2326 let mut n = self.len();
2330 self.iter.try_rfold(init, move |acc, x| {
2332 let r = fold(acc, x);
2333 if n == 0 { LoopState::Break(r) }
2334 else { LoopState::from_try(r) }
2340 #[stable(feature = "fused", since = "1.26.0")]
2341 impl<I> FusedIterator for Skip<I> where I: FusedIterator {}
2343 /// An iterator that only iterates over the first `n` iterations of `iter`.
2345 /// This `struct` is created by the [`take`] method on [`Iterator`]. See its
2346 /// documentation for more.
2348 /// [`take`]: trait.Iterator.html#method.take
2349 /// [`Iterator`]: trait.Iterator.html
2350 #[derive(Clone, Debug)]
2351 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2352 #[stable(feature = "rust1", since = "1.0.0")]
2353 pub struct Take<I> {
2358 #[stable(feature = "rust1", since = "1.0.0")]
2359 impl<I> Iterator for Take<I> where I: Iterator{
2360 type Item = <I as Iterator>::Item;
2363 fn next(&mut self) -> Option<<I as Iterator>::Item> {
2373 fn nth(&mut self, n: usize) -> Option<I::Item> {
2379 self.iter.nth(self.n - 1);
2387 fn size_hint(&self) -> (usize, Option<usize>) {
2388 let (lower, upper) = self.iter.size_hint();
2390 let lower = cmp::min(lower, self.n);
2392 let upper = match upper {
2393 Some(x) if x < self.n => Some(x),
2401 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
2402 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
2407 let n = &mut self.n;
2408 self.iter.try_fold(init, move |acc, x| {
2410 let r = fold(acc, x);
2411 if *n == 0 { LoopState::Break(r) }
2412 else { LoopState::from_try(r) }
2418 #[stable(feature = "rust1", since = "1.0.0")]
2419 impl<I> ExactSizeIterator for Take<I> where I: ExactSizeIterator {}
2421 #[stable(feature = "fused", since = "1.26.0")]
2422 impl<I> FusedIterator for Take<I> where I: FusedIterator {}
2424 #[unstable(feature = "trusted_len", issue = "37572")]
2425 unsafe impl<I: TrustedLen> TrustedLen for Take<I> {}
2427 /// An iterator to maintain state while iterating another iterator.
2429 /// This `struct` is created by the [`scan`] method on [`Iterator`]. See its
2430 /// documentation for more.
2432 /// [`scan`]: trait.Iterator.html#method.scan
2433 /// [`Iterator`]: trait.Iterator.html
2434 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2435 #[stable(feature = "rust1", since = "1.0.0")]
2437 pub struct Scan<I, St, F> {
2443 #[stable(feature = "core_impl_debug", since = "1.9.0")]
2444 impl<I: fmt::Debug, St: fmt::Debug, F> fmt::Debug for Scan<I, St, F> {
2445 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2446 f.debug_struct("Scan")
2447 .field("iter", &self.iter)
2448 .field("state", &self.state)
2453 #[stable(feature = "rust1", since = "1.0.0")]
2454 impl<B, I, St, F> Iterator for Scan<I, St, F> where
2456 F: FnMut(&mut St, I::Item) -> Option<B>,
2461 fn next(&mut self) -> Option<B> {
2462 self.iter.next().and_then(|a| (self.f)(&mut self.state, a))
2466 fn size_hint(&self) -> (usize, Option<usize>) {
2467 let (_, upper) = self.iter.size_hint();
2468 (0, upper) // can't know a lower bound, due to the scan function
2472 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
2473 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
2475 let state = &mut self.state;
2476 let f = &mut self.f;
2477 self.iter.try_fold(init, move |acc, x| {
2479 None => LoopState::Break(Try::from_ok(acc)),
2480 Some(x) => LoopState::from_try(fold(acc, x)),
2486 /// An iterator that maps each element to an iterator, and yields the elements
2487 /// of the produced iterators.
2489 /// This `struct` is created by the [`flat_map`] method on [`Iterator`]. See its
2490 /// documentation for more.
2492 /// [`flat_map`]: trait.Iterator.html#method.flat_map
2493 /// [`Iterator`]: trait.Iterator.html
2494 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2495 #[stable(feature = "rust1", since = "1.0.0")]
2496 pub struct FlatMap<I, U: IntoIterator, F> {
2497 inner: FlattenCompat<Map<I, F>, <U as IntoIterator>::IntoIter>
2500 #[stable(feature = "rust1", since = "1.0.0")]
2501 impl<I: Clone, U: Clone + IntoIterator, F: Clone> Clone for FlatMap<I, U, F>
2502 where <U as IntoIterator>::IntoIter: Clone
2504 fn clone(&self) -> Self { FlatMap { inner: self.inner.clone() } }
2507 #[stable(feature = "core_impl_debug", since = "1.9.0")]
2508 impl<I: fmt::Debug, U: IntoIterator, F> fmt::Debug for FlatMap<I, U, F>
2509 where U::IntoIter: fmt::Debug
2511 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2512 f.debug_struct("FlatMap").field("inner", &self.inner).finish()
2516 #[stable(feature = "rust1", since = "1.0.0")]
2517 impl<I: Iterator, U: IntoIterator, F> Iterator for FlatMap<I, U, F>
2518 where F: FnMut(I::Item) -> U,
2520 type Item = U::Item;
2523 fn next(&mut self) -> Option<U::Item> { self.inner.next() }
2526 fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
2529 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
2530 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
2532 self.inner.try_fold(init, fold)
2536 fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
2537 where Fold: FnMut(Acc, Self::Item) -> Acc,
2539 self.inner.fold(init, fold)
2543 #[stable(feature = "rust1", since = "1.0.0")]
2544 impl<I: DoubleEndedIterator, U, F> DoubleEndedIterator for FlatMap<I, U, F>
2545 where F: FnMut(I::Item) -> U,
2547 U::IntoIter: DoubleEndedIterator
2550 fn next_back(&mut self) -> Option<U::Item> { self.inner.next_back() }
2553 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
2554 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
2556 self.inner.try_rfold(init, fold)
2560 fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
2561 where Fold: FnMut(Acc, Self::Item) -> Acc,
2563 self.inner.rfold(init, fold)
2567 #[stable(feature = "fused", since = "1.26.0")]
2568 impl<I, U, F> FusedIterator for FlatMap<I, U, F>
2569 where I: FusedIterator, U: IntoIterator, F: FnMut(I::Item) -> U {}
2571 /// An iterator that flattens one level of nesting in an iterator of things
2572 /// that can be turned into iterators.
2574 /// This `struct` is created by the [`flatten`] method on [`Iterator`]. See its
2575 /// documentation for more.
2577 /// [`flatten`]: trait.Iterator.html#method.flatten
2578 /// [`Iterator`]: trait.Iterator.html
2579 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2580 #[stable(feature = "iterator_flatten", since = "1.29")]
2581 pub struct Flatten<I: Iterator>
2582 where I::Item: IntoIterator {
2583 inner: FlattenCompat<I, <I::Item as IntoIterator>::IntoIter>,
2586 #[stable(feature = "iterator_flatten", since = "1.29")]
2587 impl<I, U> fmt::Debug for Flatten<I>
2588 where I: Iterator + fmt::Debug, U: Iterator + fmt::Debug,
2589 I::Item: IntoIterator<IntoIter = U, Item = U::Item>,
2591 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2592 f.debug_struct("Flatten").field("inner", &self.inner).finish()
2596 #[stable(feature = "iterator_flatten", since = "1.29")]
2597 impl<I, U> Clone for Flatten<I>
2598 where I: Iterator + Clone, U: Iterator + Clone,
2599 I::Item: IntoIterator<IntoIter = U, Item = U::Item>,
2601 fn clone(&self) -> Self { Flatten { inner: self.inner.clone() } }
2604 #[stable(feature = "iterator_flatten", since = "1.29")]
2605 impl<I, U> Iterator for Flatten<I>
2606 where I: Iterator, U: Iterator,
2607 I::Item: IntoIterator<IntoIter = U, Item = U::Item>
2609 type Item = U::Item;
2612 fn next(&mut self) -> Option<U::Item> { self.inner.next() }
2615 fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
2618 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
2619 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
2621 self.inner.try_fold(init, fold)
2625 fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
2626 where Fold: FnMut(Acc, Self::Item) -> Acc,
2628 self.inner.fold(init, fold)
2632 #[stable(feature = "iterator_flatten", since = "1.29")]
2633 impl<I, U> DoubleEndedIterator for Flatten<I>
2634 where I: DoubleEndedIterator, U: DoubleEndedIterator,
2635 I::Item: IntoIterator<IntoIter = U, Item = U::Item>
2638 fn next_back(&mut self) -> Option<U::Item> { self.inner.next_back() }
2641 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
2642 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
2644 self.inner.try_rfold(init, fold)
2648 fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
2649 where Fold: FnMut(Acc, Self::Item) -> Acc,
2651 self.inner.rfold(init, fold)
2655 #[stable(feature = "iterator_flatten", since = "1.29")]
2656 impl<I, U> FusedIterator for Flatten<I>
2657 where I: FusedIterator, U: Iterator,
2658 I::Item: IntoIterator<IntoIter = U, Item = U::Item> {}
2660 /// Adapts an iterator by flattening it, for use in `flatten()` and `flat_map()`.
2661 fn flatten_compat<I, U>(iter: I) -> FlattenCompat<I, U> {
2662 FlattenCompat { iter, frontiter: None, backiter: None }
2665 /// Real logic of both `Flatten` and `FlatMap` which simply delegate to
2667 #[derive(Clone, Debug)]
2668 struct FlattenCompat<I, U> {
2670 frontiter: Option<U>,
2671 backiter: Option<U>,
2674 impl<I, U> Iterator for FlattenCompat<I, U>
2675 where I: Iterator, U: Iterator,
2676 I::Item: IntoIterator<IntoIter = U, Item = U::Item>
2678 type Item = U::Item;
2681 fn next(&mut self) -> Option<U::Item> {
2683 if let Some(ref mut inner) = self.frontiter {
2684 if let elt@Some(_) = inner.next() { return elt }
2686 match self.iter.next() {
2687 None => return self.backiter.as_mut().and_then(|it| it.next()),
2688 Some(inner) => self.frontiter = Some(inner.into_iter()),
2694 fn size_hint(&self) -> (usize, Option<usize>) {
2695 let (flo, fhi) = self.frontiter.as_ref().map_or((0, Some(0)), |it| it.size_hint());
2696 let (blo, bhi) = self.backiter.as_ref().map_or((0, Some(0)), |it| it.size_hint());
2697 let lo = flo.saturating_add(blo);
2698 match (self.iter.size_hint(), fhi, bhi) {
2699 ((0, Some(0)), Some(a), Some(b)) => (lo, a.checked_add(b)),
2705 fn try_fold<Acc, Fold, R>(&mut self, mut init: Acc, mut fold: Fold) -> R where
2706 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
2708 if let Some(ref mut front) = self.frontiter {
2709 init = front.try_fold(init, &mut fold)?;
2711 self.frontiter = None;
2714 let frontiter = &mut self.frontiter;
2715 init = self.iter.try_fold(init, |acc, x| {
2716 let mut mid = x.into_iter();
2717 let r = mid.try_fold(acc, &mut fold);
2718 *frontiter = Some(mid);
2722 self.frontiter = None;
2724 if let Some(ref mut back) = self.backiter {
2725 init = back.try_fold(init, &mut fold)?;
2727 self.backiter = None;
2733 fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
2734 where Fold: FnMut(Acc, Self::Item) -> Acc,
2736 self.frontiter.into_iter()
2737 .chain(self.iter.map(IntoIterator::into_iter))
2738 .chain(self.backiter)
2739 .fold(init, |acc, iter| iter.fold(acc, &mut fold))
2743 impl<I, U> DoubleEndedIterator for FlattenCompat<I, U>
2744 where I: DoubleEndedIterator, U: DoubleEndedIterator,
2745 I::Item: IntoIterator<IntoIter = U, Item = U::Item>
2748 fn next_back(&mut self) -> Option<U::Item> {
2750 if let Some(ref mut inner) = self.backiter {
2751 if let elt@Some(_) = inner.next_back() { return elt }
2753 match self.iter.next_back() {
2754 None => return self.frontiter.as_mut().and_then(|it| it.next_back()),
2755 next => self.backiter = next.map(IntoIterator::into_iter),
2761 fn try_rfold<Acc, Fold, R>(&mut self, mut init: Acc, mut fold: Fold) -> R where
2762 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
2764 if let Some(ref mut back) = self.backiter {
2765 init = back.try_rfold(init, &mut fold)?;
2767 self.backiter = None;
2770 let backiter = &mut self.backiter;
2771 init = self.iter.try_rfold(init, |acc, x| {
2772 let mut mid = x.into_iter();
2773 let r = mid.try_rfold(acc, &mut fold);
2774 *backiter = Some(mid);
2778 self.backiter = None;
2780 if let Some(ref mut front) = self.frontiter {
2781 init = front.try_rfold(init, &mut fold)?;
2783 self.frontiter = None;
2789 fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
2790 where Fold: FnMut(Acc, Self::Item) -> Acc,
2792 self.frontiter.into_iter()
2793 .chain(self.iter.map(IntoIterator::into_iter))
2794 .chain(self.backiter)
2795 .rfold(init, |acc, iter| iter.rfold(acc, &mut fold))
2799 /// An iterator that yields `None` forever after the underlying iterator
2800 /// yields `None` once.
2802 /// This `struct` is created by the [`fuse`] method on [`Iterator`]. See its
2803 /// documentation for more.
2805 /// [`fuse`]: trait.Iterator.html#method.fuse
2806 /// [`Iterator`]: trait.Iterator.html
2807 #[derive(Clone, Debug)]
2808 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2809 #[stable(feature = "rust1", since = "1.0.0")]
2810 pub struct Fuse<I> {
2815 #[stable(feature = "fused", since = "1.26.0")]
2816 impl<I> FusedIterator for Fuse<I> where I: Iterator {}
2818 #[stable(feature = "rust1", since = "1.0.0")]
2819 impl<I> Iterator for Fuse<I> where I: Iterator {
2820 type Item = <I as Iterator>::Item;
2823 default fn next(&mut self) -> Option<<I as Iterator>::Item> {
2827 let next = self.iter.next();
2828 self.done = next.is_none();
2834 default fn nth(&mut self, n: usize) -> Option<I::Item> {
2838 let nth = self.iter.nth(n);
2839 self.done = nth.is_none();
2845 default fn last(self) -> Option<I::Item> {
2854 default fn count(self) -> usize {
2863 default fn size_hint(&self) -> (usize, Option<usize>) {
2867 self.iter.size_hint()
2872 default fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
2873 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
2878 let acc = self.iter.try_fold(init, fold)?;
2885 default fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
2886 where Fold: FnMut(Acc, Self::Item) -> Acc,
2891 self.iter.fold(init, fold)
2896 #[stable(feature = "rust1", since = "1.0.0")]
2897 impl<I> DoubleEndedIterator for Fuse<I> where I: DoubleEndedIterator {
2899 default fn next_back(&mut self) -> Option<<I as Iterator>::Item> {
2903 let next = self.iter.next_back();
2904 self.done = next.is_none();
2910 default fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
2911 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
2916 let acc = self.iter.try_rfold(init, fold)?;
2923 default fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
2924 where Fold: FnMut(Acc, Self::Item) -> Acc,
2929 self.iter.rfold(init, fold)
2934 unsafe impl<I> TrustedRandomAccess for Fuse<I>
2935 where I: TrustedRandomAccess,
2937 unsafe fn get_unchecked(&mut self, i: usize) -> I::Item {
2938 self.iter.get_unchecked(i)
2941 fn may_have_side_effect() -> bool {
2942 I::may_have_side_effect()
2946 #[stable(feature = "fused", since = "1.26.0")]
2947 impl<I> Iterator for Fuse<I> where I: FusedIterator {
2949 fn next(&mut self) -> Option<<I as Iterator>::Item> {
2954 fn nth(&mut self, n: usize) -> Option<I::Item> {
2959 fn last(self) -> Option<I::Item> {
2964 fn count(self) -> usize {
2969 fn size_hint(&self) -> (usize, Option<usize>) {
2970 self.iter.size_hint()
2974 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
2975 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
2977 self.iter.try_fold(init, fold)
2981 fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
2982 where Fold: FnMut(Acc, Self::Item) -> Acc,
2984 self.iter.fold(init, fold)
2988 #[stable(feature = "fused", since = "1.26.0")]
2989 impl<I> DoubleEndedIterator for Fuse<I>
2990 where I: DoubleEndedIterator + FusedIterator
2993 fn next_back(&mut self) -> Option<<I as Iterator>::Item> {
2994 self.iter.next_back()
2998 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
2999 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
3001 self.iter.try_rfold(init, fold)
3005 fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
3006 where Fold: FnMut(Acc, Self::Item) -> Acc,
3008 self.iter.rfold(init, fold)
3013 #[stable(feature = "rust1", since = "1.0.0")]
3014 impl<I> ExactSizeIterator for Fuse<I> where I: ExactSizeIterator {
3015 fn len(&self) -> usize {
3019 fn is_empty(&self) -> bool {
3020 self.iter.is_empty()
3024 /// An iterator that calls a function with a reference to each element before
3027 /// This `struct` is created by the [`inspect`] method on [`Iterator`]. See its
3028 /// documentation for more.
3030 /// [`inspect`]: trait.Iterator.html#method.inspect
3031 /// [`Iterator`]: trait.Iterator.html
3032 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
3033 #[stable(feature = "rust1", since = "1.0.0")]
3035 pub struct Inspect<I, F> {
3040 #[stable(feature = "core_impl_debug", since = "1.9.0")]
3041 impl<I: fmt::Debug, F> fmt::Debug for Inspect<I, F> {
3042 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
3043 f.debug_struct("Inspect")
3044 .field("iter", &self.iter)
3049 impl<I: Iterator, F> Inspect<I, F> where F: FnMut(&I::Item) {
3051 fn do_inspect(&mut self, elt: Option<I::Item>) -> Option<I::Item> {
3052 if let Some(ref a) = elt {
3060 #[stable(feature = "rust1", since = "1.0.0")]
3061 impl<I: Iterator, F> Iterator for Inspect<I, F> where F: FnMut(&I::Item) {
3062 type Item = I::Item;
3065 fn next(&mut self) -> Option<I::Item> {
3066 let next = self.iter.next();
3067 self.do_inspect(next)
3071 fn size_hint(&self) -> (usize, Option<usize>) {
3072 self.iter.size_hint()
3076 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
3077 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
3079 let f = &mut self.f;
3080 self.iter.try_fold(init, move |acc, item| { f(&item); fold(acc, item) })
3084 fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
3085 where Fold: FnMut(Acc, Self::Item) -> Acc,
3088 self.iter.fold(init, move |acc, item| { f(&item); fold(acc, item) })
3092 #[stable(feature = "rust1", since = "1.0.0")]
3093 impl<I: DoubleEndedIterator, F> DoubleEndedIterator for Inspect<I, F>
3094 where F: FnMut(&I::Item),
3097 fn next_back(&mut self) -> Option<I::Item> {
3098 let next = self.iter.next_back();
3099 self.do_inspect(next)
3103 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
3104 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
3106 let f = &mut self.f;
3107 self.iter.try_rfold(init, move |acc, item| { f(&item); fold(acc, item) })
3111 fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
3112 where Fold: FnMut(Acc, Self::Item) -> Acc,
3115 self.iter.rfold(init, move |acc, item| { f(&item); fold(acc, item) })
3119 #[stable(feature = "rust1", since = "1.0.0")]
3120 impl<I: ExactSizeIterator, F> ExactSizeIterator for Inspect<I, F>
3121 where F: FnMut(&I::Item)
3123 fn len(&self) -> usize {
3127 fn is_empty(&self) -> bool {
3128 self.iter.is_empty()
3132 #[stable(feature = "fused", since = "1.26.0")]
3133 impl<I: FusedIterator, F> FusedIterator for Inspect<I, F>
3134 where F: FnMut(&I::Item) {}