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;
326 #[stable(feature = "rust1", since = "1.0.0")]
327 pub use self::iterator::Iterator;
329 #[unstable(feature = "step_trait",
330 reason = "likely to be replaced by finer-grained traits",
332 pub use self::range::Step;
334 #[stable(feature = "rust1", since = "1.0.0")]
335 pub use self::sources::{Repeat, repeat};
336 #[stable(feature = "iter_empty", since = "1.2.0")]
337 pub use self::sources::{Empty, empty};
338 #[stable(feature = "iter_once", since = "1.2.0")]
339 pub use self::sources::{Once, once};
341 #[stable(feature = "rust1", since = "1.0.0")]
342 pub use self::traits::{FromIterator, IntoIterator, DoubleEndedIterator, Extend};
343 #[stable(feature = "rust1", since = "1.0.0")]
344 pub use self::traits::{ExactSizeIterator, Sum, Product};
345 #[unstable(feature = "fused", issue = "35602")]
346 pub use self::traits::FusedIterator;
347 #[unstable(feature = "trusted_len", issue = "37572")]
348 pub use self::traits::TrustedLen;
355 /// Transparent newtype used to implement foo methods in terms of try_foo.
356 /// Important until #43278 is fixed; might be better as `Result<T, !>` later.
357 struct AlwaysOk<T>(pub T);
359 impl<T> Try for AlwaysOk<T> {
363 fn into_result(self) -> Result<Self::Ok, Self::Error> { Ok(self.0) }
365 fn from_error(v: Self::Error) -> Self { v }
367 fn from_ok(v: Self::Ok) -> Self { AlwaysOk(v) }
370 /// Used to make try_fold closures more like normal loops
372 enum LoopState<C, B> {
377 impl<C, B> Try for LoopState<C, B> {
381 fn into_result(self) -> Result<Self::Ok, Self::Error> {
383 LoopState::Continue(y) => Ok(y),
384 LoopState::Break(x) => Err(x),
388 fn from_error(v: Self::Error) -> Self { LoopState::Break(v) }
390 fn from_ok(v: Self::Ok) -> Self { LoopState::Continue(v) }
393 impl<C, B> LoopState<C, B> {
395 fn break_value(self) -> Option<B> {
397 LoopState::Continue(..) => None,
398 LoopState::Break(x) => Some(x),
403 impl<R: Try> LoopState<R::Ok, R> {
405 fn from_try(r: R) -> Self {
406 match Try::into_result(r) {
407 Ok(v) => LoopState::Continue(v),
408 Err(v) => LoopState::Break(Try::from_error(v)),
412 fn into_try(self) -> R {
414 LoopState::Continue(v) => Try::from_ok(v),
415 LoopState::Break(v) => v,
420 /// A double-ended iterator with the direction inverted.
422 /// This `struct` is created by the [`rev`] method on [`Iterator`]. See its
423 /// documentation for more.
425 /// [`rev`]: trait.Iterator.html#method.rev
426 /// [`Iterator`]: trait.Iterator.html
427 #[derive(Clone, Debug)]
428 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
429 #[stable(feature = "rust1", since = "1.0.0")]
434 #[stable(feature = "rust1", since = "1.0.0")]
435 impl<I> Iterator for Rev<I> where I: DoubleEndedIterator {
436 type Item = <I as Iterator>::Item;
439 fn next(&mut self) -> Option<<I as Iterator>::Item> { self.iter.next_back() }
441 fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
443 fn try_fold<B, F, R>(&mut self, init: B, f: F) -> R where
444 Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
446 self.iter.try_rfold(init, f)
449 fn fold<Acc, F>(self, init: Acc, f: F) -> Acc
450 where F: FnMut(Acc, Self::Item) -> Acc,
452 self.iter.rfold(init, f)
456 fn find<P>(&mut self, predicate: P) -> Option<Self::Item>
457 where P: FnMut(&Self::Item) -> bool
459 self.iter.rfind(predicate)
463 fn rposition<P>(&mut self, predicate: P) -> Option<usize> where
464 P: FnMut(Self::Item) -> bool
466 self.iter.position(predicate)
470 #[stable(feature = "rust1", since = "1.0.0")]
471 impl<I> DoubleEndedIterator for Rev<I> where I: DoubleEndedIterator {
473 fn next_back(&mut self) -> Option<<I as Iterator>::Item> { self.iter.next() }
475 fn try_rfold<B, F, R>(&mut self, init: B, f: F) -> R where
476 Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
478 self.iter.try_fold(init, f)
481 fn rfold<Acc, F>(self, init: Acc, f: F) -> Acc
482 where F: FnMut(Acc, Self::Item) -> Acc,
484 self.iter.fold(init, f)
487 fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item>
488 where P: FnMut(&Self::Item) -> bool
490 self.iter.find(predicate)
494 #[stable(feature = "rust1", since = "1.0.0")]
495 impl<I> ExactSizeIterator for Rev<I>
496 where I: ExactSizeIterator + DoubleEndedIterator
498 fn len(&self) -> usize {
502 fn is_empty(&self) -> bool {
507 #[unstable(feature = "fused", issue = "35602")]
508 impl<I> FusedIterator for Rev<I>
509 where I: FusedIterator + DoubleEndedIterator {}
511 #[unstable(feature = "trusted_len", issue = "37572")]
512 unsafe impl<I> TrustedLen for Rev<I>
513 where I: TrustedLen + DoubleEndedIterator {}
515 /// An iterator that clones the elements of an underlying iterator.
517 /// This `struct` is created by the [`cloned`] method on [`Iterator`]. See its
518 /// documentation for more.
520 /// [`cloned`]: trait.Iterator.html#method.cloned
521 /// [`Iterator`]: trait.Iterator.html
522 #[stable(feature = "iter_cloned", since = "1.1.0")]
523 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
524 #[derive(Clone, Debug)]
525 pub struct Cloned<I> {
529 #[stable(feature = "iter_cloned", since = "1.1.0")]
530 impl<'a, I, T: 'a> Iterator for Cloned<I>
531 where I: Iterator<Item=&'a T>, T: Clone
535 fn next(&mut self) -> Option<T> {
536 self.it.next().cloned()
539 fn size_hint(&self) -> (usize, Option<usize>) {
543 fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R where
544 Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
546 self.it.try_fold(init, move |acc, elt| f(acc, elt.clone()))
549 fn fold<Acc, F>(self, init: Acc, mut f: F) -> Acc
550 where F: FnMut(Acc, Self::Item) -> Acc,
552 self.it.fold(init, move |acc, elt| f(acc, elt.clone()))
556 #[stable(feature = "iter_cloned", since = "1.1.0")]
557 impl<'a, I, T: 'a> DoubleEndedIterator for Cloned<I>
558 where I: DoubleEndedIterator<Item=&'a T>, T: Clone
560 fn next_back(&mut self) -> Option<T> {
561 self.it.next_back().cloned()
564 fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R where
565 Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
567 self.it.try_rfold(init, move |acc, elt| f(acc, elt.clone()))
570 fn rfold<Acc, F>(self, init: Acc, mut f: F) -> Acc
571 where F: FnMut(Acc, Self::Item) -> Acc,
573 self.it.rfold(init, move |acc, elt| f(acc, elt.clone()))
577 #[stable(feature = "iter_cloned", since = "1.1.0")]
578 impl<'a, I, T: 'a> ExactSizeIterator for Cloned<I>
579 where I: ExactSizeIterator<Item=&'a T>, T: Clone
581 fn len(&self) -> usize {
585 fn is_empty(&self) -> bool {
590 #[unstable(feature = "fused", issue = "35602")]
591 impl<'a, I, T: 'a> FusedIterator for Cloned<I>
592 where I: FusedIterator<Item=&'a T>, T: Clone
596 default unsafe impl<'a, I, T: 'a> TrustedRandomAccess for Cloned<I>
597 where I: TrustedRandomAccess<Item=&'a T>, T: Clone
599 unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item {
600 self.it.get_unchecked(i).clone()
604 fn may_have_side_effect() -> bool { true }
608 unsafe impl<'a, I, T: 'a> TrustedRandomAccess for Cloned<I>
609 where I: TrustedRandomAccess<Item=&'a T>, T: Copy
611 unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item {
612 *self.it.get_unchecked(i)
616 fn may_have_side_effect() -> bool { false }
619 #[unstable(feature = "trusted_len", issue = "37572")]
620 unsafe impl<'a, I, T: 'a> TrustedLen for Cloned<I>
621 where I: TrustedLen<Item=&'a T>,
625 /// An iterator that repeats endlessly.
627 /// This `struct` is created by the [`cycle`] method on [`Iterator`]. See its
628 /// documentation for more.
630 /// [`cycle`]: trait.Iterator.html#method.cycle
631 /// [`Iterator`]: trait.Iterator.html
632 #[derive(Clone, Debug)]
633 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
634 #[stable(feature = "rust1", since = "1.0.0")]
635 pub struct Cycle<I> {
640 #[stable(feature = "rust1", since = "1.0.0")]
641 impl<I> Iterator for Cycle<I> where I: Clone + Iterator {
642 type Item = <I as Iterator>::Item;
645 fn next(&mut self) -> Option<<I as Iterator>::Item> {
646 match self.iter.next() {
647 None => { self.iter = self.orig.clone(); self.iter.next() }
653 fn size_hint(&self) -> (usize, Option<usize>) {
654 // the cycle iterator is either empty or infinite
655 match self.orig.size_hint() {
656 sz @ (0, Some(0)) => sz,
658 _ => (usize::MAX, None)
663 #[unstable(feature = "fused", issue = "35602")]
664 impl<I> FusedIterator for Cycle<I> where I: Clone + Iterator {}
666 /// An iterator for stepping iterators by a custom amount.
668 /// This `struct` is created by the [`step_by`] method on [`Iterator`]. See
669 /// its documentation for more.
671 /// [`step_by`]: trait.Iterator.html#method.step_by
672 /// [`Iterator`]: trait.Iterator.html
673 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
674 #[unstable(feature = "iterator_step_by",
675 reason = "unstable replacement of Range::step_by",
677 #[derive(Clone, Debug)]
678 pub struct StepBy<I> {
684 #[unstable(feature = "iterator_step_by",
685 reason = "unstable replacement of Range::step_by",
687 impl<I> Iterator for StepBy<I> where I: Iterator {
691 fn next(&mut self) -> Option<Self::Item> {
693 self.first_take = false;
696 self.iter.nth(self.step)
701 fn size_hint(&self) -> (usize, Option<usize>) {
702 let inner_hint = self.iter.size_hint();
705 let f = |n| if n == 0 { 0 } else { 1 + (n-1)/(self.step+1) };
706 (f(inner_hint.0), inner_hint.1.map(f))
708 let f = |n| n / (self.step+1);
709 (f(inner_hint.0), inner_hint.1.map(f))
714 fn nth(&mut self, mut n: usize) -> Option<Self::Item> {
716 self.first_take = false;
717 let first = self.iter.next();
723 // n and self.step are indices, we need to add 1 to get the amount of elements
724 // When calling `.nth`, we need to subtract 1 again to convert back to an index
725 // step + 1 can't overflow because `.step_by` sets `self.step` to `step - 1`
726 let mut step = self.step + 1;
727 // n + 1 could overflow
728 // thus, if n is usize::MAX, instead of adding one, we call .nth(step)
730 self.iter.nth(step - 1);
737 let mul = n.checked_mul(step);
738 if unsafe { intrinsics::likely(mul.is_some()) } {
739 return self.iter.nth(mul.unwrap() - 1);
741 let div_n = usize::MAX / n;
742 let div_step = usize::MAX / step;
743 let nth_n = div_n * n;
744 let nth_step = div_step * step;
745 let nth = if nth_n > nth_step {
752 self.iter.nth(nth - 1);
757 // StepBy can only make the iterator shorter, so the len will still fit.
758 #[unstable(feature = "iterator_step_by",
759 reason = "unstable replacement of Range::step_by",
761 impl<I> ExactSizeIterator for StepBy<I> where I: ExactSizeIterator {}
763 /// An iterator that strings two iterators together.
765 /// This `struct` is created by the [`chain`] method on [`Iterator`]. See its
766 /// documentation for more.
768 /// [`chain`]: trait.Iterator.html#method.chain
769 /// [`Iterator`]: trait.Iterator.html
770 #[derive(Clone, Debug)]
771 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
772 #[stable(feature = "rust1", since = "1.0.0")]
773 pub struct Chain<A, B> {
779 // The iterator protocol specifies that iteration ends with the return value
780 // `None` from `.next()` (or `.next_back()`) and it is unspecified what
781 // further calls return. The chain adaptor must account for this since it uses
784 // It uses three states:
786 // - Both: `a` and `b` are remaining
787 // - Front: `a` remaining
788 // - Back: `b` remaining
790 // The fourth state (neither iterator is remaining) only occurs after Chain has
791 // returned None once, so we don't need to store this state.
792 #[derive(Clone, Debug)]
794 // both front and back iterator are remaining
796 // only front is remaining
798 // only back is remaining
802 #[stable(feature = "rust1", since = "1.0.0")]
803 impl<A, B> Iterator for Chain<A, B> where
805 B: Iterator<Item = A::Item>
810 fn next(&mut self) -> Option<A::Item> {
812 ChainState::Both => match self.a.next() {
813 elt @ Some(..) => elt,
815 self.state = ChainState::Back;
819 ChainState::Front => self.a.next(),
820 ChainState::Back => self.b.next(),
825 #[rustc_inherit_overflow_checks]
826 fn count(self) -> usize {
828 ChainState::Both => self.a.count() + self.b.count(),
829 ChainState::Front => self.a.count(),
830 ChainState::Back => self.b.count(),
834 fn try_fold<Acc, F, R>(&mut self, init: Acc, mut f: F) -> R where
835 Self: Sized, F: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
837 let mut accum = init;
839 ChainState::Both | ChainState::Front => {
840 accum = self.a.try_fold(accum, &mut f)?;
841 if let ChainState::Both = self.state {
842 self.state = ChainState::Back;
847 if let ChainState::Back = self.state {
848 accum = self.b.try_fold(accum, &mut f)?;
853 fn fold<Acc, F>(self, init: Acc, mut f: F) -> Acc
854 where F: FnMut(Acc, Self::Item) -> Acc,
856 let mut accum = init;
858 ChainState::Both | ChainState::Front => {
859 accum = self.a.fold(accum, &mut f);
864 ChainState::Both | ChainState::Back => {
865 accum = self.b.fold(accum, &mut f);
873 fn nth(&mut self, mut n: usize) -> Option<A::Item> {
875 ChainState::Both | ChainState::Front => {
876 for x in self.a.by_ref() {
882 if let ChainState::Both = self.state {
883 self.state = ChainState::Back;
886 ChainState::Back => {}
888 if let ChainState::Back = self.state {
896 fn find<P>(&mut self, mut predicate: P) -> Option<Self::Item> where
897 P: FnMut(&Self::Item) -> bool,
900 ChainState::Both => match self.a.find(&mut predicate) {
902 self.state = ChainState::Back;
903 self.b.find(predicate)
907 ChainState::Front => self.a.find(predicate),
908 ChainState::Back => self.b.find(predicate),
913 fn last(self) -> Option<A::Item> {
915 ChainState::Both => {
916 // Must exhaust a before b.
917 let a_last = self.a.last();
918 let b_last = self.b.last();
921 ChainState::Front => self.a.last(),
922 ChainState::Back => self.b.last()
927 fn size_hint(&self) -> (usize, Option<usize>) {
928 let (a_lower, a_upper) = self.a.size_hint();
929 let (b_lower, b_upper) = self.b.size_hint();
931 let lower = a_lower.saturating_add(b_lower);
933 let upper = match (a_upper, b_upper) {
934 (Some(x), Some(y)) => x.checked_add(y),
942 #[stable(feature = "rust1", since = "1.0.0")]
943 impl<A, B> DoubleEndedIterator for Chain<A, B> where
944 A: DoubleEndedIterator,
945 B: DoubleEndedIterator<Item=A::Item>,
948 fn next_back(&mut self) -> Option<A::Item> {
950 ChainState::Both => match self.b.next_back() {
951 elt @ Some(..) => elt,
953 self.state = ChainState::Front;
957 ChainState::Front => self.a.next_back(),
958 ChainState::Back => self.b.next_back(),
962 fn try_rfold<Acc, F, R>(&mut self, init: Acc, mut f: F) -> R where
963 Self: Sized, F: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
965 let mut accum = init;
967 ChainState::Both | ChainState::Back => {
968 accum = self.b.try_rfold(accum, &mut f)?;
969 if let ChainState::Both = self.state {
970 self.state = ChainState::Front;
975 if let ChainState::Front = self.state {
976 accum = self.a.try_rfold(accum, &mut f)?;
981 fn rfold<Acc, F>(self, init: Acc, mut f: F) -> Acc
982 where F: FnMut(Acc, Self::Item) -> Acc,
984 let mut accum = init;
986 ChainState::Both | ChainState::Back => {
987 accum = self.b.rfold(accum, &mut f);
992 ChainState::Both | ChainState::Front => {
993 accum = self.a.rfold(accum, &mut f);
1002 // Note: *both* must be fused to handle double-ended iterators.
1003 #[unstable(feature = "fused", issue = "35602")]
1004 impl<A, B> FusedIterator for Chain<A, B>
1005 where A: FusedIterator,
1006 B: FusedIterator<Item=A::Item>,
1009 #[unstable(feature = "trusted_len", issue = "37572")]
1010 unsafe impl<A, B> TrustedLen for Chain<A, B>
1011 where A: TrustedLen, B: TrustedLen<Item=A::Item>,
1014 /// An iterator that iterates two other iterators simultaneously.
1016 /// This `struct` is created by the [`zip`] method on [`Iterator`]. See its
1017 /// documentation for more.
1019 /// [`zip`]: trait.Iterator.html#method.zip
1020 /// [`Iterator`]: trait.Iterator.html
1021 #[derive(Clone, Debug)]
1022 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1023 #[stable(feature = "rust1", since = "1.0.0")]
1024 pub struct Zip<A, B> {
1027 // index and len are only used by the specialized version of zip
1032 #[stable(feature = "rust1", since = "1.0.0")]
1033 impl<A, B> Iterator for Zip<A, B> where A: Iterator, B: Iterator
1035 type Item = (A::Item, B::Item);
1038 fn next(&mut self) -> Option<Self::Item> {
1043 fn size_hint(&self) -> (usize, Option<usize>) {
1044 ZipImpl::size_hint(self)
1048 #[stable(feature = "rust1", since = "1.0.0")]
1049 impl<A, B> DoubleEndedIterator for Zip<A, B> where
1050 A: DoubleEndedIterator + ExactSizeIterator,
1051 B: DoubleEndedIterator + ExactSizeIterator,
1054 fn next_back(&mut self) -> Option<(A::Item, B::Item)> {
1055 ZipImpl::next_back(self)
1059 // Zip specialization trait
1061 trait ZipImpl<A, B> {
1063 fn new(a: A, b: B) -> Self;
1064 fn next(&mut self) -> Option<Self::Item>;
1065 fn size_hint(&self) -> (usize, Option<usize>);
1066 fn next_back(&mut self) -> Option<Self::Item>
1067 where A: DoubleEndedIterator + ExactSizeIterator,
1068 B: DoubleEndedIterator + ExactSizeIterator;
1073 impl<A, B> ZipImpl<A, B> for Zip<A, B>
1074 where A: Iterator, B: Iterator
1076 type Item = (A::Item, B::Item);
1077 default fn new(a: A, b: B) -> Self {
1087 default fn next(&mut self) -> Option<(A::Item, B::Item)> {
1088 self.a.next().and_then(|x| {
1089 self.b.next().and_then(|y| {
1096 default fn next_back(&mut self) -> Option<(A::Item, B::Item)>
1097 where A: DoubleEndedIterator + ExactSizeIterator,
1098 B: DoubleEndedIterator + ExactSizeIterator
1100 let a_sz = self.a.len();
1101 let b_sz = self.b.len();
1103 // Adjust a, b to equal length
1105 for _ in 0..a_sz - b_sz { self.a.next_back(); }
1107 for _ in 0..b_sz - a_sz { self.b.next_back(); }
1110 match (self.a.next_back(), self.b.next_back()) {
1111 (Some(x), Some(y)) => Some((x, y)),
1112 (None, None) => None,
1113 _ => unreachable!(),
1118 default fn size_hint(&self) -> (usize, Option<usize>) {
1119 let (a_lower, a_upper) = self.a.size_hint();
1120 let (b_lower, b_upper) = self.b.size_hint();
1122 let lower = cmp::min(a_lower, b_lower);
1124 let upper = match (a_upper, b_upper) {
1125 (Some(x), Some(y)) => Some(cmp::min(x,y)),
1126 (Some(x), None) => Some(x),
1127 (None, Some(y)) => Some(y),
1128 (None, None) => None
1136 impl<A, B> ZipImpl<A, B> for Zip<A, B>
1137 where A: TrustedRandomAccess, B: TrustedRandomAccess
1139 fn new(a: A, b: B) -> Self {
1140 let len = cmp::min(a.len(), b.len());
1150 fn next(&mut self) -> Option<(A::Item, B::Item)> {
1151 if self.index < self.len {
1155 Some((self.a.get_unchecked(i), self.b.get_unchecked(i)))
1157 } else if A::may_have_side_effect() && self.index < self.a.len() {
1158 // match the base implementation's potential side effects
1160 self.a.get_unchecked(self.index);
1170 fn size_hint(&self) -> (usize, Option<usize>) {
1171 let len = self.len - self.index;
1176 fn next_back(&mut self) -> Option<(A::Item, B::Item)>
1177 where A: DoubleEndedIterator + ExactSizeIterator,
1178 B: DoubleEndedIterator + ExactSizeIterator
1180 // Adjust a, b to equal length
1181 if A::may_have_side_effect() {
1182 let sz = self.a.len();
1184 for _ in 0..sz - cmp::max(self.len, self.index) {
1189 if B::may_have_side_effect() {
1190 let sz = self.b.len();
1192 for _ in 0..sz - self.len {
1197 if self.index < self.len {
1201 Some((self.a.get_unchecked(i), self.b.get_unchecked(i)))
1209 #[stable(feature = "rust1", since = "1.0.0")]
1210 impl<A, B> ExactSizeIterator for Zip<A, B>
1211 where A: ExactSizeIterator, B: ExactSizeIterator {}
1214 unsafe impl<A, B> TrustedRandomAccess for Zip<A, B>
1215 where A: TrustedRandomAccess,
1216 B: TrustedRandomAccess,
1218 unsafe fn get_unchecked(&mut self, i: usize) -> (A::Item, B::Item) {
1219 (self.a.get_unchecked(i), self.b.get_unchecked(i))
1222 fn may_have_side_effect() -> bool {
1223 A::may_have_side_effect() || B::may_have_side_effect()
1227 #[unstable(feature = "fused", issue = "35602")]
1228 impl<A, B> FusedIterator for Zip<A, B>
1229 where A: FusedIterator, B: FusedIterator, {}
1231 #[unstable(feature = "trusted_len", issue = "37572")]
1232 unsafe impl<A, B> TrustedLen for Zip<A, B>
1233 where A: TrustedLen, B: TrustedLen,
1236 /// An iterator that maps the values of `iter` with `f`.
1238 /// This `struct` is created by the [`map`] method on [`Iterator`]. See its
1239 /// documentation for more.
1241 /// [`map`]: trait.Iterator.html#method.map
1242 /// [`Iterator`]: trait.Iterator.html
1244 /// # Notes about side effects
1246 /// The [`map`] iterator implements [`DoubleEndedIterator`], meaning that
1247 /// you can also [`map`] backwards:
1250 /// let v: Vec<i32> = vec![1, 2, 3].into_iter().map(|x| x + 1).rev().collect();
1252 /// assert_eq!(v, [4, 3, 2]);
1255 /// [`DoubleEndedIterator`]: trait.DoubleEndedIterator.html
1257 /// But if your closure has state, iterating backwards may act in a way you do
1258 /// not expect. Let's go through an example. First, in the forward direction:
1263 /// for pair in vec!['a', 'b', 'c'].into_iter()
1264 /// .map(|letter| { c += 1; (letter, c) }) {
1265 /// println!("{:?}", pair);
1269 /// This will print "('a', 1), ('b', 2), ('c', 3)".
1271 /// Now consider this twist where we add a call to `rev`. This version will
1272 /// print `('c', 1), ('b', 2), ('a', 3)`. Note that the letters are reversed,
1273 /// but the values of the counter still go in order. This is because `map()` is
1274 /// still being called lazily on each item, but we are popping items off the
1275 /// back of the vector now, instead of shifting them from the front.
1280 /// for pair in vec!['a', 'b', 'c'].into_iter()
1281 /// .map(|letter| { c += 1; (letter, c) })
1283 /// println!("{:?}", pair);
1286 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1287 #[stable(feature = "rust1", since = "1.0.0")]
1289 pub struct Map<I, F> {
1294 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1295 impl<I: fmt::Debug, F> fmt::Debug for Map<I, F> {
1296 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1297 f.debug_struct("Map")
1298 .field("iter", &self.iter)
1303 #[stable(feature = "rust1", since = "1.0.0")]
1304 impl<B, I: Iterator, F> Iterator for Map<I, F> where F: FnMut(I::Item) -> B {
1308 fn next(&mut self) -> Option<B> {
1309 self.iter.next().map(&mut self.f)
1313 fn size_hint(&self) -> (usize, Option<usize>) {
1314 self.iter.size_hint()
1317 fn try_fold<Acc, G, R>(&mut self, init: Acc, mut g: G) -> R where
1318 Self: Sized, G: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
1320 let f = &mut self.f;
1321 self.iter.try_fold(init, move |acc, elt| g(acc, f(elt)))
1324 fn fold<Acc, G>(self, init: Acc, mut g: G) -> Acc
1325 where G: FnMut(Acc, Self::Item) -> Acc,
1328 self.iter.fold(init, move |acc, elt| g(acc, f(elt)))
1332 #[stable(feature = "rust1", since = "1.0.0")]
1333 impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for Map<I, F> where
1334 F: FnMut(I::Item) -> B,
1337 fn next_back(&mut self) -> Option<B> {
1338 self.iter.next_back().map(&mut self.f)
1341 fn try_rfold<Acc, G, R>(&mut self, init: Acc, mut g: G) -> R where
1342 Self: Sized, G: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
1344 let f = &mut self.f;
1345 self.iter.try_rfold(init, move |acc, elt| g(acc, f(elt)))
1348 fn rfold<Acc, G>(self, init: Acc, mut g: G) -> Acc
1349 where G: FnMut(Acc, Self::Item) -> Acc,
1352 self.iter.rfold(init, move |acc, elt| g(acc, f(elt)))
1356 #[stable(feature = "rust1", since = "1.0.0")]
1357 impl<B, I: ExactSizeIterator, F> ExactSizeIterator for Map<I, F>
1358 where F: FnMut(I::Item) -> B
1360 fn len(&self) -> usize {
1364 fn is_empty(&self) -> bool {
1365 self.iter.is_empty()
1369 #[unstable(feature = "fused", issue = "35602")]
1370 impl<B, I: FusedIterator, F> FusedIterator for Map<I, F>
1371 where F: FnMut(I::Item) -> B {}
1373 #[unstable(feature = "trusted_len", issue = "37572")]
1374 unsafe impl<B, I, F> TrustedLen for Map<I, F>
1375 where I: TrustedLen,
1376 F: FnMut(I::Item) -> B {}
1379 unsafe impl<B, I, F> TrustedRandomAccess for Map<I, F>
1380 where I: TrustedRandomAccess,
1381 F: FnMut(I::Item) -> B,
1383 unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item {
1384 (self.f)(self.iter.get_unchecked(i))
1387 fn may_have_side_effect() -> bool { true }
1390 /// An iterator that filters the elements of `iter` with `predicate`.
1392 /// This `struct` is created by the [`filter`] method on [`Iterator`]. See its
1393 /// documentation for more.
1395 /// [`filter`]: trait.Iterator.html#method.filter
1396 /// [`Iterator`]: trait.Iterator.html
1397 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1398 #[stable(feature = "rust1", since = "1.0.0")]
1400 pub struct Filter<I, P> {
1405 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1406 impl<I: fmt::Debug, P> fmt::Debug for Filter<I, P> {
1407 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1408 f.debug_struct("Filter")
1409 .field("iter", &self.iter)
1414 #[stable(feature = "rust1", since = "1.0.0")]
1415 impl<I: Iterator, P> Iterator for Filter<I, P> where P: FnMut(&I::Item) -> bool {
1416 type Item = I::Item;
1419 fn next(&mut self) -> Option<I::Item> {
1420 for x in &mut self.iter {
1421 if (self.predicate)(&x) {
1429 fn size_hint(&self) -> (usize, Option<usize>) {
1430 let (_, upper) = self.iter.size_hint();
1431 (0, upper) // can't know a lower bound, due to the predicate
1434 // this special case allows the compiler to make `.filter(_).count()`
1435 // branchless. Barring perfect branch prediction (which is unattainable in
1436 // the general case), this will be much faster in >90% of cases (containing
1437 // virtually all real workloads) and only a tiny bit slower in the rest.
1439 // Having this specialization thus allows us to write `.filter(p).count()`
1440 // where we would otherwise write `.map(|x| p(x) as usize).sum()`, which is
1441 // less readable and also less backwards-compatible to Rust before 1.10.
1443 // Using the branchless version will also simplify the LLVM byte code, thus
1444 // leaving more budget for LLVM optimizations.
1446 fn count(mut self) -> usize {
1448 for x in &mut self.iter {
1449 count += (self.predicate)(&x) as usize;
1455 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
1456 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
1458 let predicate = &mut self.predicate;
1459 self.iter.try_fold(init, move |acc, item| if predicate(&item) {
1467 fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
1468 where Fold: FnMut(Acc, Self::Item) -> Acc,
1470 let mut predicate = self.predicate;
1471 self.iter.fold(init, move |acc, item| if predicate(&item) {
1479 #[stable(feature = "rust1", since = "1.0.0")]
1480 impl<I: DoubleEndedIterator, P> DoubleEndedIterator for Filter<I, P>
1481 where P: FnMut(&I::Item) -> bool,
1484 fn next_back(&mut self) -> Option<I::Item> {
1485 for x in self.iter.by_ref().rev() {
1486 if (self.predicate)(&x) {
1494 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
1495 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
1497 let predicate = &mut self.predicate;
1498 self.iter.try_rfold(init, move |acc, item| if predicate(&item) {
1506 fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
1507 where Fold: FnMut(Acc, Self::Item) -> Acc,
1509 let mut predicate = self.predicate;
1510 self.iter.rfold(init, move |acc, item| if predicate(&item) {
1518 #[unstable(feature = "fused", issue = "35602")]
1519 impl<I: FusedIterator, P> FusedIterator for Filter<I, P>
1520 where P: FnMut(&I::Item) -> bool {}
1522 /// An iterator that uses `f` to both filter and map elements from `iter`.
1524 /// This `struct` is created by the [`filter_map`] method on [`Iterator`]. See its
1525 /// documentation for more.
1527 /// [`filter_map`]: trait.Iterator.html#method.filter_map
1528 /// [`Iterator`]: trait.Iterator.html
1529 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1530 #[stable(feature = "rust1", since = "1.0.0")]
1532 pub struct FilterMap<I, F> {
1537 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1538 impl<I: fmt::Debug, F> fmt::Debug for FilterMap<I, F> {
1539 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1540 f.debug_struct("FilterMap")
1541 .field("iter", &self.iter)
1546 #[stable(feature = "rust1", since = "1.0.0")]
1547 impl<B, I: Iterator, F> Iterator for FilterMap<I, F>
1548 where F: FnMut(I::Item) -> Option<B>,
1553 fn next(&mut self) -> Option<B> {
1554 for x in self.iter.by_ref() {
1555 if let Some(y) = (self.f)(x) {
1563 fn size_hint(&self) -> (usize, Option<usize>) {
1564 let (_, upper) = self.iter.size_hint();
1565 (0, upper) // can't know a lower bound, due to the predicate
1569 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
1570 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
1572 let f = &mut self.f;
1573 self.iter.try_fold(init, move |acc, item| match f(item) {
1574 Some(x) => fold(acc, x),
1575 None => Try::from_ok(acc),
1580 fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
1581 where Fold: FnMut(Acc, Self::Item) -> Acc,
1584 self.iter.fold(init, move |acc, item| match f(item) {
1585 Some(x) => fold(acc, x),
1591 #[stable(feature = "rust1", since = "1.0.0")]
1592 impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for FilterMap<I, F>
1593 where F: FnMut(I::Item) -> Option<B>,
1596 fn next_back(&mut self) -> Option<B> {
1597 for x in self.iter.by_ref().rev() {
1598 if let Some(y) = (self.f)(x) {
1606 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
1607 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
1609 let f = &mut self.f;
1610 self.iter.try_rfold(init, move |acc, item| match f(item) {
1611 Some(x) => fold(acc, x),
1612 None => Try::from_ok(acc),
1617 fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
1618 where Fold: FnMut(Acc, Self::Item) -> Acc,
1621 self.iter.rfold(init, move |acc, item| match f(item) {
1622 Some(x) => fold(acc, x),
1628 #[unstable(feature = "fused", issue = "35602")]
1629 impl<B, I: FusedIterator, F> FusedIterator for FilterMap<I, F>
1630 where F: FnMut(I::Item) -> Option<B> {}
1632 /// An iterator that yields the current count and the element during iteration.
1634 /// This `struct` is created by the [`enumerate`] method on [`Iterator`]. See its
1635 /// documentation for more.
1637 /// [`enumerate`]: trait.Iterator.html#method.enumerate
1638 /// [`Iterator`]: trait.Iterator.html
1639 #[derive(Clone, Debug)]
1640 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1641 #[stable(feature = "rust1", since = "1.0.0")]
1642 pub struct Enumerate<I> {
1647 #[stable(feature = "rust1", since = "1.0.0")]
1648 impl<I> Iterator for Enumerate<I> where I: Iterator {
1649 type Item = (usize, <I as Iterator>::Item);
1651 /// # Overflow Behavior
1653 /// The method does no guarding against overflows, so enumerating more than
1654 /// `usize::MAX` elements either produces the wrong result or panics. If
1655 /// debug assertions are enabled, a panic is guaranteed.
1659 /// Might panic if the index of the element overflows a `usize`.
1661 #[rustc_inherit_overflow_checks]
1662 fn next(&mut self) -> Option<(usize, <I as Iterator>::Item)> {
1663 self.iter.next().map(|a| {
1664 let ret = (self.count, a);
1665 // Possible undefined overflow.
1672 fn size_hint(&self) -> (usize, Option<usize>) {
1673 self.iter.size_hint()
1677 #[rustc_inherit_overflow_checks]
1678 fn nth(&mut self, n: usize) -> Option<(usize, I::Item)> {
1679 self.iter.nth(n).map(|a| {
1680 let i = self.count + n;
1687 fn count(self) -> usize {
1692 #[rustc_inherit_overflow_checks]
1693 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
1694 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
1696 let count = &mut self.count;
1697 self.iter.try_fold(init, move |acc, item| {
1698 let acc = fold(acc, (*count, item));
1705 #[rustc_inherit_overflow_checks]
1706 fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
1707 where Fold: FnMut(Acc, Self::Item) -> Acc,
1709 let mut count = self.count;
1710 self.iter.fold(init, move |acc, item| {
1711 let acc = fold(acc, (count, item));
1718 #[stable(feature = "rust1", since = "1.0.0")]
1719 impl<I> DoubleEndedIterator for Enumerate<I> where
1720 I: ExactSizeIterator + DoubleEndedIterator
1723 fn next_back(&mut self) -> Option<(usize, <I as Iterator>::Item)> {
1724 self.iter.next_back().map(|a| {
1725 let len = self.iter.len();
1726 // Can safely add, `ExactSizeIterator` promises that the number of
1727 // elements fits into a `usize`.
1728 (self.count + len, a)
1733 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
1734 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
1736 // Can safely add and subtract the count, as `ExactSizeIterator` promises
1737 // that the number of elements fits into a `usize`.
1738 let mut count = self.count + self.iter.len();
1739 self.iter.try_rfold(init, move |acc, item| {
1741 fold(acc, (count, item))
1746 fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
1747 where Fold: FnMut(Acc, Self::Item) -> Acc,
1749 // Can safely add and subtract the count, as `ExactSizeIterator` promises
1750 // that the number of elements fits into a `usize`.
1751 let mut count = self.count + self.iter.len();
1752 self.iter.rfold(init, move |acc, item| {
1754 fold(acc, (count, item))
1759 #[stable(feature = "rust1", since = "1.0.0")]
1760 impl<I> ExactSizeIterator for Enumerate<I> where I: ExactSizeIterator {
1761 fn len(&self) -> usize {
1765 fn is_empty(&self) -> bool {
1766 self.iter.is_empty()
1771 unsafe impl<I> TrustedRandomAccess for Enumerate<I>
1772 where I: TrustedRandomAccess
1774 unsafe fn get_unchecked(&mut self, i: usize) -> (usize, I::Item) {
1775 (self.count + i, self.iter.get_unchecked(i))
1778 fn may_have_side_effect() -> bool {
1779 I::may_have_side_effect()
1783 #[unstable(feature = "fused", issue = "35602")]
1784 impl<I> FusedIterator for Enumerate<I> where I: FusedIterator {}
1786 #[unstable(feature = "trusted_len", issue = "37572")]
1787 unsafe impl<I> TrustedLen for Enumerate<I>
1788 where I: TrustedLen,
1792 /// An iterator with a `peek()` that returns an optional reference to the next
1795 /// This `struct` is created by the [`peekable`] method on [`Iterator`]. See its
1796 /// documentation for more.
1798 /// [`peekable`]: trait.Iterator.html#method.peekable
1799 /// [`Iterator`]: trait.Iterator.html
1800 #[derive(Clone, Debug)]
1801 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1802 #[stable(feature = "rust1", since = "1.0.0")]
1803 pub struct Peekable<I: Iterator> {
1805 /// Remember a peeked value, even if it was None.
1806 peeked: Option<Option<I::Item>>,
1809 // Peekable must remember if a None has been seen in the `.peek()` method.
1810 // It ensures that `.peek(); .peek();` or `.peek(); .next();` only advances the
1811 // underlying iterator at most once. This does not by itself make the iterator
1813 #[stable(feature = "rust1", since = "1.0.0")]
1814 impl<I: Iterator> Iterator for Peekable<I> {
1815 type Item = I::Item;
1818 fn next(&mut self) -> Option<I::Item> {
1819 match self.peeked.take() {
1821 None => self.iter.next(),
1826 #[rustc_inherit_overflow_checks]
1827 fn count(mut self) -> usize {
1828 match self.peeked.take() {
1830 Some(Some(_)) => 1 + self.iter.count(),
1831 None => self.iter.count(),
1836 fn nth(&mut self, n: usize) -> Option<I::Item> {
1837 // FIXME(#6393): merge these when borrow-checking gets better.
1839 match self.peeked.take() {
1841 None => self.iter.nth(n),
1844 match self.peeked.take() {
1846 Some(Some(_)) => self.iter.nth(n - 1),
1847 None => self.iter.nth(n),
1853 fn last(mut self) -> Option<I::Item> {
1854 let peek_opt = match self.peeked.take() {
1855 Some(None) => return None,
1859 self.iter.last().or(peek_opt)
1863 fn size_hint(&self) -> (usize, Option<usize>) {
1864 let peek_len = match self.peeked {
1865 Some(None) => return (0, Some(0)),
1869 let (lo, hi) = self.iter.size_hint();
1870 let lo = lo.saturating_add(peek_len);
1871 let hi = hi.and_then(|x| x.checked_add(peek_len));
1876 fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R where
1877 Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
1879 let acc = match self.peeked.take() {
1880 Some(None) => return Try::from_ok(init),
1881 Some(Some(v)) => f(init, v)?,
1884 self.iter.try_fold(acc, f)
1888 fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
1889 where Fold: FnMut(Acc, Self::Item) -> Acc,
1891 let acc = match self.peeked {
1892 Some(None) => return init,
1893 Some(Some(v)) => fold(init, v),
1896 self.iter.fold(acc, fold)
1900 #[stable(feature = "rust1", since = "1.0.0")]
1901 impl<I: ExactSizeIterator> ExactSizeIterator for Peekable<I> {}
1903 #[unstable(feature = "fused", issue = "35602")]
1904 impl<I: FusedIterator> FusedIterator for Peekable<I> {}
1906 impl<I: Iterator> Peekable<I> {
1907 /// Returns a reference to the next() value without advancing the iterator.
1909 /// Like [`next`], if there is a value, it is wrapped in a `Some(T)`.
1910 /// But if the iteration is over, `None` is returned.
1912 /// [`next`]: trait.Iterator.html#tymethod.next
1914 /// Because `peek()` returns a reference, and many iterators iterate over
1915 /// references, there can be a possibly confusing situation where the
1916 /// return value is a double reference. You can see this effect in the
1924 /// let xs = [1, 2, 3];
1926 /// let mut iter = xs.iter().peekable();
1928 /// // peek() lets us see into the future
1929 /// assert_eq!(iter.peek(), Some(&&1));
1930 /// assert_eq!(iter.next(), Some(&1));
1932 /// assert_eq!(iter.next(), Some(&2));
1934 /// // The iterator does not advance even if we `peek` multiple times
1935 /// assert_eq!(iter.peek(), Some(&&3));
1936 /// assert_eq!(iter.peek(), Some(&&3));
1938 /// assert_eq!(iter.next(), Some(&3));
1940 /// // After the iterator is finished, so is `peek()`
1941 /// assert_eq!(iter.peek(), None);
1942 /// assert_eq!(iter.next(), None);
1945 #[stable(feature = "rust1", since = "1.0.0")]
1946 pub fn peek(&mut self) -> Option<&I::Item> {
1947 if self.peeked.is_none() {
1948 self.peeked = Some(self.iter.next());
1951 Some(Some(ref value)) => Some(value),
1953 _ => unreachable!(),
1958 /// An iterator that rejects elements while `predicate` is true.
1960 /// This `struct` is created by the [`skip_while`] method on [`Iterator`]. See its
1961 /// documentation for more.
1963 /// [`skip_while`]: trait.Iterator.html#method.skip_while
1964 /// [`Iterator`]: trait.Iterator.html
1965 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1966 #[stable(feature = "rust1", since = "1.0.0")]
1968 pub struct SkipWhile<I, P> {
1974 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1975 impl<I: fmt::Debug, P> fmt::Debug for SkipWhile<I, P> {
1976 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1977 f.debug_struct("SkipWhile")
1978 .field("iter", &self.iter)
1979 .field("flag", &self.flag)
1984 #[stable(feature = "rust1", since = "1.0.0")]
1985 impl<I: Iterator, P> Iterator for SkipWhile<I, P>
1986 where P: FnMut(&I::Item) -> bool
1988 type Item = I::Item;
1991 fn next(&mut self) -> Option<I::Item> {
1992 let flag = &mut self.flag;
1993 let pred = &mut self.predicate;
1994 self.iter.find(move |x| {
1995 if *flag || !pred(x) {
2005 fn size_hint(&self) -> (usize, Option<usize>) {
2006 let (_, upper) = self.iter.size_hint();
2007 (0, upper) // can't know a lower bound, due to the predicate
2011 fn try_fold<Acc, Fold, R>(&mut self, mut init: Acc, mut fold: Fold) -> R where
2012 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
2016 Some(v) => init = fold(init, v)?,
2017 None => return Try::from_ok(init),
2020 self.iter.try_fold(init, fold)
2024 fn fold<Acc, Fold>(mut self, mut init: Acc, mut fold: Fold) -> Acc
2025 where Fold: FnMut(Acc, Self::Item) -> Acc,
2029 Some(v) => init = fold(init, v),
2030 None => return init,
2033 self.iter.fold(init, fold)
2037 #[unstable(feature = "fused", issue = "35602")]
2038 impl<I, P> FusedIterator for SkipWhile<I, P>
2039 where I: FusedIterator, P: FnMut(&I::Item) -> bool {}
2041 /// An iterator that only accepts elements while `predicate` is true.
2043 /// This `struct` is created by the [`take_while`] method on [`Iterator`]. See its
2044 /// documentation for more.
2046 /// [`take_while`]: trait.Iterator.html#method.take_while
2047 /// [`Iterator`]: trait.Iterator.html
2048 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2049 #[stable(feature = "rust1", since = "1.0.0")]
2051 pub struct TakeWhile<I, P> {
2057 #[stable(feature = "core_impl_debug", since = "1.9.0")]
2058 impl<I: fmt::Debug, P> fmt::Debug for TakeWhile<I, P> {
2059 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2060 f.debug_struct("TakeWhile")
2061 .field("iter", &self.iter)
2062 .field("flag", &self.flag)
2067 #[stable(feature = "rust1", since = "1.0.0")]
2068 impl<I: Iterator, P> Iterator for TakeWhile<I, P>
2069 where P: FnMut(&I::Item) -> bool
2071 type Item = I::Item;
2074 fn next(&mut self) -> Option<I::Item> {
2078 self.iter.next().and_then(|x| {
2079 if (self.predicate)(&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, init: Acc, mut fold: Fold) -> R where
2097 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
2102 let flag = &mut self.flag;
2103 let p = &mut self.predicate;
2104 self.iter.try_fold(init, move |acc, x|{
2106 LoopState::from_try(fold(acc, x))
2109 LoopState::Break(Try::from_ok(acc))
2116 #[unstable(feature = "fused", issue = "35602")]
2117 impl<I, P> FusedIterator for TakeWhile<I, P>
2118 where I: FusedIterator, P: FnMut(&I::Item) -> bool {}
2120 /// An iterator that skips over `n` elements of `iter`.
2122 /// This `struct` is created by the [`skip`] method on [`Iterator`]. See its
2123 /// documentation for more.
2125 /// [`skip`]: trait.Iterator.html#method.skip
2126 /// [`Iterator`]: trait.Iterator.html
2127 #[derive(Clone, Debug)]
2128 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2129 #[stable(feature = "rust1", since = "1.0.0")]
2130 pub struct Skip<I> {
2135 #[stable(feature = "rust1", since = "1.0.0")]
2136 impl<I> Iterator for Skip<I> where I: Iterator {
2137 type Item = <I as Iterator>::Item;
2140 fn next(&mut self) -> Option<I::Item> {
2146 self.iter.nth(old_n)
2151 fn nth(&mut self, n: usize) -> Option<I::Item> {
2152 // Can't just add n + self.n due to overflow.
2156 let to_skip = self.n;
2159 if self.iter.nth(to_skip-1).is_none() {
2167 fn count(self) -> usize {
2168 self.iter.count().saturating_sub(self.n)
2172 fn last(mut self) -> Option<I::Item> {
2176 let next = self.next();
2178 // recurse. n should be 0.
2179 self.last().or(next)
2187 fn size_hint(&self) -> (usize, Option<usize>) {
2188 let (lower, upper) = self.iter.size_hint();
2190 let lower = lower.saturating_sub(self.n);
2191 let upper = upper.map(|x| x.saturating_sub(self.n));
2197 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
2198 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
2204 if self.iter.nth(n - 1).is_none() {
2205 return Try::from_ok(init);
2208 self.iter.try_fold(init, fold)
2212 fn fold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
2213 where Fold: FnMut(Acc, Self::Item) -> Acc,
2217 if self.iter.nth(self.n - 1).is_none() {
2221 self.iter.fold(init, fold)
2225 #[stable(feature = "rust1", since = "1.0.0")]
2226 impl<I> ExactSizeIterator for Skip<I> where I: ExactSizeIterator {}
2228 #[stable(feature = "double_ended_skip_iterator", since = "1.9.0")]
2229 impl<I> DoubleEndedIterator for Skip<I> where I: DoubleEndedIterator + ExactSizeIterator {
2230 fn next_back(&mut self) -> Option<Self::Item> {
2232 self.iter.next_back()
2238 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
2239 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
2241 let mut n = self.len();
2245 self.iter.try_rfold(init, move |acc, x| {
2247 let r = fold(acc, x);
2248 if n == 0 { LoopState::Break(r) }
2249 else { LoopState::from_try(r) }
2255 #[unstable(feature = "fused", issue = "35602")]
2256 impl<I> FusedIterator for Skip<I> where I: FusedIterator {}
2258 /// An iterator that only iterates over the first `n` iterations of `iter`.
2260 /// This `struct` is created by the [`take`] method on [`Iterator`]. See its
2261 /// documentation for more.
2263 /// [`take`]: trait.Iterator.html#method.take
2264 /// [`Iterator`]: trait.Iterator.html
2265 #[derive(Clone, Debug)]
2266 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2267 #[stable(feature = "rust1", since = "1.0.0")]
2268 pub struct Take<I> {
2273 #[stable(feature = "rust1", since = "1.0.0")]
2274 impl<I> Iterator for Take<I> where I: Iterator{
2275 type Item = <I as Iterator>::Item;
2278 fn next(&mut self) -> Option<<I as Iterator>::Item> {
2288 fn nth(&mut self, n: usize) -> Option<I::Item> {
2294 self.iter.nth(self.n - 1);
2302 fn size_hint(&self) -> (usize, Option<usize>) {
2303 let (lower, upper) = self.iter.size_hint();
2305 let lower = cmp::min(lower, self.n);
2307 let upper = match upper {
2308 Some(x) if x < self.n => Some(x),
2316 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
2317 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
2322 let n = &mut self.n;
2323 self.iter.try_fold(init, move |acc, x| {
2325 let r = fold(acc, x);
2326 if *n == 0 { LoopState::Break(r) }
2327 else { LoopState::from_try(r) }
2333 #[stable(feature = "rust1", since = "1.0.0")]
2334 impl<I> ExactSizeIterator for Take<I> where I: ExactSizeIterator {}
2336 #[unstable(feature = "fused", issue = "35602")]
2337 impl<I> FusedIterator for Take<I> where I: FusedIterator {}
2339 #[unstable(feature = "trusted_len", issue = "37572")]
2340 unsafe impl<I: TrustedLen> TrustedLen for Take<I> {}
2342 /// An iterator to maintain state while iterating another iterator.
2344 /// This `struct` is created by the [`scan`] method on [`Iterator`]. See its
2345 /// documentation for more.
2347 /// [`scan`]: trait.Iterator.html#method.scan
2348 /// [`Iterator`]: trait.Iterator.html
2349 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2350 #[stable(feature = "rust1", since = "1.0.0")]
2352 pub struct Scan<I, St, F> {
2358 #[stable(feature = "core_impl_debug", since = "1.9.0")]
2359 impl<I: fmt::Debug, St: fmt::Debug, F> fmt::Debug for Scan<I, St, F> {
2360 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2361 f.debug_struct("Scan")
2362 .field("iter", &self.iter)
2363 .field("state", &self.state)
2368 #[stable(feature = "rust1", since = "1.0.0")]
2369 impl<B, I, St, F> Iterator for Scan<I, St, F> where
2371 F: FnMut(&mut St, I::Item) -> Option<B>,
2376 fn next(&mut self) -> Option<B> {
2377 self.iter.next().and_then(|a| (self.f)(&mut self.state, a))
2381 fn size_hint(&self) -> (usize, Option<usize>) {
2382 let (_, upper) = self.iter.size_hint();
2383 (0, upper) // can't know a lower bound, due to the scan function
2387 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
2388 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
2390 let state = &mut self.state;
2391 let f = &mut self.f;
2392 self.iter.try_fold(init, move |acc, x| {
2394 None => LoopState::Break(Try::from_ok(acc)),
2395 Some(x) => LoopState::from_try(fold(acc, x)),
2401 /// An iterator that maps each element to an iterator, and yields the elements
2402 /// of the produced iterators.
2404 /// This `struct` is created by the [`flat_map`] method on [`Iterator`]. See its
2405 /// documentation for more.
2407 /// [`flat_map`]: trait.Iterator.html#method.flat_map
2408 /// [`Iterator`]: trait.Iterator.html
2409 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2410 #[stable(feature = "rust1", since = "1.0.0")]
2412 pub struct FlatMap<I, U: IntoIterator, F> {
2415 frontiter: Option<U::IntoIter>,
2416 backiter: Option<U::IntoIter>,
2419 #[stable(feature = "core_impl_debug", since = "1.9.0")]
2420 impl<I: fmt::Debug, U: IntoIterator, F> fmt::Debug for FlatMap<I, U, F>
2421 where U::IntoIter: fmt::Debug
2423 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2424 f.debug_struct("FlatMap")
2425 .field("iter", &self.iter)
2426 .field("frontiter", &self.frontiter)
2427 .field("backiter", &self.backiter)
2432 #[stable(feature = "rust1", since = "1.0.0")]
2433 impl<I: Iterator, U: IntoIterator, F> Iterator for FlatMap<I, U, F>
2434 where F: FnMut(I::Item) -> U,
2436 type Item = U::Item;
2439 fn next(&mut self) -> Option<U::Item> {
2441 if let Some(ref mut inner) = self.frontiter {
2442 if let Some(x) = inner.by_ref().next() {
2446 match self.iter.next().map(&mut self.f) {
2447 None => return self.backiter.as_mut().and_then(|it| it.next()),
2448 next => self.frontiter = next.map(IntoIterator::into_iter),
2454 fn size_hint(&self) -> (usize, Option<usize>) {
2455 let (flo, fhi) = self.frontiter.as_ref().map_or((0, Some(0)), |it| it.size_hint());
2456 let (blo, bhi) = self.backiter.as_ref().map_or((0, Some(0)), |it| it.size_hint());
2457 let lo = flo.saturating_add(blo);
2458 match (self.iter.size_hint(), fhi, bhi) {
2459 ((0, Some(0)), Some(a), Some(b)) => (lo, a.checked_add(b)),
2465 fn try_fold<Acc, Fold, R>(&mut self, mut init: Acc, mut fold: Fold) -> R where
2466 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
2468 if let Some(ref mut front) = self.frontiter {
2469 init = front.try_fold(init, &mut fold)?;
2471 self.frontiter = None;
2474 let f = &mut self.f;
2475 let frontiter = &mut self.frontiter;
2476 init = self.iter.try_fold(init, |acc, x| {
2477 let mut mid = f(x).into_iter();
2478 let r = mid.try_fold(acc, &mut fold);
2479 *frontiter = Some(mid);
2483 self.frontiter = None;
2485 if let Some(ref mut back) = self.backiter {
2486 init = back.try_fold(init, &mut fold)?;
2488 self.backiter = None;
2494 fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
2495 where Fold: FnMut(Acc, Self::Item) -> Acc,
2497 self.frontiter.into_iter()
2498 .chain(self.iter.map(self.f).map(U::into_iter))
2499 .chain(self.backiter)
2500 .fold(init, |acc, iter| iter.fold(acc, &mut fold))
2504 #[stable(feature = "rust1", since = "1.0.0")]
2505 impl<I: DoubleEndedIterator, U, F> DoubleEndedIterator for FlatMap<I, U, F> where
2506 F: FnMut(I::Item) -> U,
2508 U::IntoIter: DoubleEndedIterator
2511 fn next_back(&mut self) -> Option<U::Item> {
2513 if let Some(ref mut inner) = self.backiter {
2514 if let Some(y) = inner.next_back() {
2518 match self.iter.next_back().map(&mut self.f) {
2519 None => return self.frontiter.as_mut().and_then(|it| it.next_back()),
2520 next => self.backiter = next.map(IntoIterator::into_iter),
2526 fn try_rfold<Acc, Fold, R>(&mut self, mut init: Acc, mut fold: Fold) -> R where
2527 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
2529 if let Some(ref mut back) = self.backiter {
2530 init = back.try_rfold(init, &mut fold)?;
2532 self.backiter = None;
2535 let f = &mut self.f;
2536 let backiter = &mut self.backiter;
2537 init = self.iter.try_rfold(init, |acc, x| {
2538 let mut mid = f(x).into_iter();
2539 let r = mid.try_rfold(acc, &mut fold);
2540 *backiter = Some(mid);
2544 self.backiter = None;
2546 if let Some(ref mut front) = self.frontiter {
2547 init = front.try_rfold(init, &mut fold)?;
2549 self.frontiter = None;
2555 fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
2556 where Fold: FnMut(Acc, Self::Item) -> Acc,
2558 self.frontiter.into_iter()
2559 .chain(self.iter.map(self.f).map(U::into_iter))
2560 .chain(self.backiter)
2561 .rfold(init, |acc, iter| iter.rfold(acc, &mut fold))
2565 #[unstable(feature = "fused", issue = "35602")]
2566 impl<I, U, F> FusedIterator for FlatMap<I, U, F>
2567 where I: FusedIterator, U: IntoIterator, F: FnMut(I::Item) -> U {}
2569 /// An iterator that yields `None` forever after the underlying iterator
2570 /// yields `None` once.
2572 /// This `struct` is created by the [`fuse`] method on [`Iterator`]. See its
2573 /// documentation for more.
2575 /// [`fuse`]: trait.Iterator.html#method.fuse
2576 /// [`Iterator`]: trait.Iterator.html
2577 #[derive(Clone, Debug)]
2578 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2579 #[stable(feature = "rust1", since = "1.0.0")]
2580 pub struct Fuse<I> {
2585 #[unstable(feature = "fused", issue = "35602")]
2586 impl<I> FusedIterator for Fuse<I> where I: Iterator {}
2588 #[stable(feature = "rust1", since = "1.0.0")]
2589 impl<I> Iterator for Fuse<I> where I: Iterator {
2590 type Item = <I as Iterator>::Item;
2593 default fn next(&mut self) -> Option<<I as Iterator>::Item> {
2597 let next = self.iter.next();
2598 self.done = next.is_none();
2604 default fn nth(&mut self, n: usize) -> Option<I::Item> {
2608 let nth = self.iter.nth(n);
2609 self.done = nth.is_none();
2615 default fn last(self) -> Option<I::Item> {
2624 default fn count(self) -> usize {
2633 default fn size_hint(&self) -> (usize, Option<usize>) {
2637 self.iter.size_hint()
2642 default fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
2643 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
2648 let acc = self.iter.try_fold(init, fold)?;
2655 default fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
2656 where Fold: FnMut(Acc, Self::Item) -> Acc,
2661 self.iter.fold(init, fold)
2666 #[stable(feature = "rust1", since = "1.0.0")]
2667 impl<I> DoubleEndedIterator for Fuse<I> where I: DoubleEndedIterator {
2669 default fn next_back(&mut self) -> Option<<I as Iterator>::Item> {
2673 let next = self.iter.next_back();
2674 self.done = next.is_none();
2680 default fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
2681 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
2686 let acc = self.iter.try_rfold(init, fold)?;
2693 default fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
2694 where Fold: FnMut(Acc, Self::Item) -> Acc,
2699 self.iter.rfold(init, fold)
2704 unsafe impl<I> TrustedRandomAccess for Fuse<I>
2705 where I: TrustedRandomAccess,
2707 unsafe fn get_unchecked(&mut self, i: usize) -> I::Item {
2708 self.iter.get_unchecked(i)
2711 fn may_have_side_effect() -> bool {
2712 I::may_have_side_effect()
2716 #[unstable(feature = "fused", issue = "35602")]
2717 impl<I> Iterator for Fuse<I> where I: FusedIterator {
2719 fn next(&mut self) -> Option<<I as Iterator>::Item> {
2724 fn nth(&mut self, n: usize) -> Option<I::Item> {
2729 fn last(self) -> Option<I::Item> {
2734 fn count(self) -> usize {
2739 fn size_hint(&self) -> (usize, Option<usize>) {
2740 self.iter.size_hint()
2744 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
2745 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
2747 self.iter.try_fold(init, fold)
2751 fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
2752 where Fold: FnMut(Acc, Self::Item) -> Acc,
2754 self.iter.fold(init, fold)
2758 #[unstable(feature = "fused", reason = "recently added", issue = "35602")]
2759 impl<I> DoubleEndedIterator for Fuse<I>
2760 where I: DoubleEndedIterator + FusedIterator
2763 fn next_back(&mut self) -> Option<<I as Iterator>::Item> {
2764 self.iter.next_back()
2768 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
2769 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
2771 self.iter.try_rfold(init, fold)
2775 fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
2776 where Fold: FnMut(Acc, Self::Item) -> Acc,
2778 self.iter.rfold(init, fold)
2783 #[stable(feature = "rust1", since = "1.0.0")]
2784 impl<I> ExactSizeIterator for Fuse<I> where I: ExactSizeIterator {
2785 fn len(&self) -> usize {
2789 fn is_empty(&self) -> bool {
2790 self.iter.is_empty()
2794 /// An iterator that calls a function with a reference to each element before
2797 /// This `struct` is created by the [`inspect`] method on [`Iterator`]. See its
2798 /// documentation for more.
2800 /// [`inspect`]: trait.Iterator.html#method.inspect
2801 /// [`Iterator`]: trait.Iterator.html
2802 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2803 #[stable(feature = "rust1", since = "1.0.0")]
2805 pub struct Inspect<I, F> {
2810 #[stable(feature = "core_impl_debug", since = "1.9.0")]
2811 impl<I: fmt::Debug, F> fmt::Debug for Inspect<I, F> {
2812 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2813 f.debug_struct("Inspect")
2814 .field("iter", &self.iter)
2819 impl<I: Iterator, F> Inspect<I, F> where F: FnMut(&I::Item) {
2821 fn do_inspect(&mut self, elt: Option<I::Item>) -> Option<I::Item> {
2822 if let Some(ref a) = elt {
2830 #[stable(feature = "rust1", since = "1.0.0")]
2831 impl<I: Iterator, F> Iterator for Inspect<I, F> where F: FnMut(&I::Item) {
2832 type Item = I::Item;
2835 fn next(&mut self) -> Option<I::Item> {
2836 let next = self.iter.next();
2837 self.do_inspect(next)
2841 fn size_hint(&self) -> (usize, Option<usize>) {
2842 self.iter.size_hint()
2846 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
2847 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
2849 let f = &mut self.f;
2850 self.iter.try_fold(init, move |acc, item| { f(&item); fold(acc, item) })
2854 fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
2855 where Fold: FnMut(Acc, Self::Item) -> Acc,
2858 self.iter.fold(init, move |acc, item| { f(&item); fold(acc, item) })
2862 #[stable(feature = "rust1", since = "1.0.0")]
2863 impl<I: DoubleEndedIterator, F> DoubleEndedIterator for Inspect<I, F>
2864 where F: FnMut(&I::Item),
2867 fn next_back(&mut self) -> Option<I::Item> {
2868 let next = self.iter.next_back();
2869 self.do_inspect(next)
2873 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
2874 Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
2876 let f = &mut self.f;
2877 self.iter.try_rfold(init, move |acc, item| { f(&item); fold(acc, item) })
2881 fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
2882 where Fold: FnMut(Acc, Self::Item) -> Acc,
2885 self.iter.rfold(init, move |acc, item| { f(&item); fold(acc, item) })
2889 #[stable(feature = "rust1", since = "1.0.0")]
2890 impl<I: ExactSizeIterator, F> ExactSizeIterator for Inspect<I, F>
2891 where F: FnMut(&I::Item)
2893 fn len(&self) -> usize {
2897 fn is_empty(&self) -> bool {
2898 self.iter.is_empty()
2902 #[unstable(feature = "fused", issue = "35602")]
2903 impl<I: FusedIterator, F> FusedIterator for Inspect<I, F>
2904 where F: FnMut(&I::Item) {}