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 //! [`take`]: trait.Iterator.html#method.take
303 #![stable(feature = "rust1", since = "1.0.0")]
307 use iter_private
::TrustedRandomAccess
;
310 #[stable(feature = "rust1", since = "1.0.0")]
311 pub use self::iterator
::Iterator
;
313 #[unstable(feature = "step_trait",
314 reason
= "likely to be replaced by finer-grained traits",
316 pub use self::range
::Step
;
318 #[stable(feature = "rust1", since = "1.0.0")]
319 pub use self::sources
::{Repeat, repeat}
;
320 #[stable(feature = "iter_empty", since = "1.2.0")]
321 pub use self::sources
::{Empty, empty}
;
322 #[stable(feature = "iter_once", since = "1.2.0")]
323 pub use self::sources
::{Once, once}
;
325 #[stable(feature = "rust1", since = "1.0.0")]
326 pub use self::traits
::{FromIterator, IntoIterator, DoubleEndedIterator, Extend}
;
327 #[stable(feature = "rust1", since = "1.0.0")]
328 pub use self::traits
::{ExactSizeIterator, Sum, Product}
;
329 #[unstable(feature = "fused", issue = "35602")]
330 pub use self::traits
::FusedIterator
;
331 #[unstable(feature = "trusted_len", issue = "37572")]
332 pub use self::traits
::TrustedLen
;
339 /// A double-ended iterator with the direction inverted.
341 /// This `struct` is created by the [`rev`] method on [`Iterator`]. See its
342 /// documentation for more.
344 /// [`rev`]: trait.Iterator.html#method.rev
345 /// [`Iterator`]: trait.Iterator.html
346 #[derive(Clone, Debug)]
347 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
348 #[stable(feature = "rust1", since = "1.0.0")]
353 #[stable(feature = "rust1", since = "1.0.0")]
354 impl<I
> Iterator
for Rev
<I
> where I
: DoubleEndedIterator
{
355 type Item
= <I
as Iterator
>::Item
;
358 fn next(&mut self) -> Option
<<I
as Iterator
>::Item
> { self.iter.next_back() }
360 fn size_hint(&self) -> (usize, Option
<usize>) { self.iter.size_hint() }
363 fn find
<P
>(&mut self, predicate
: P
) -> Option
<Self::Item
>
364 where P
: FnMut(&Self::Item
) -> bool
366 self.iter
.rfind(predicate
)
370 fn rposition
<P
>(&mut self, predicate
: P
) -> Option
<usize> where
371 P
: FnMut(Self::Item
) -> bool
373 self.iter
.position(predicate
)
377 #[stable(feature = "rust1", since = "1.0.0")]
378 impl<I
> DoubleEndedIterator
for Rev
<I
> where I
: DoubleEndedIterator
{
380 fn next_back(&mut self) -> Option
<<I
as Iterator
>::Item
> { self.iter.next() }
382 fn rfind
<P
>(&mut self, predicate
: P
) -> Option
<Self::Item
>
383 where P
: FnMut(&Self::Item
) -> bool
385 self.iter
.find(predicate
)
389 #[stable(feature = "rust1", since = "1.0.0")]
390 impl<I
> ExactSizeIterator
for Rev
<I
>
391 where I
: ExactSizeIterator
+ DoubleEndedIterator
393 fn len(&self) -> usize {
397 fn is_empty(&self) -> bool
{
402 #[unstable(feature = "fused", issue = "35602")]
403 impl<I
> FusedIterator
for Rev
<I
>
404 where I
: FusedIterator
+ DoubleEndedIterator {}
406 #[unstable(feature = "trusted_len", issue = "37572")]
407 unsafe impl<I
> TrustedLen
for Rev
<I
>
408 where I
: TrustedLen
+ DoubleEndedIterator {}
410 /// An iterator that clones the elements of an underlying iterator.
412 /// This `struct` is created by the [`cloned`] method on [`Iterator`]. See its
413 /// documentation for more.
415 /// [`cloned`]: trait.Iterator.html#method.cloned
416 /// [`Iterator`]: trait.Iterator.html
417 #[stable(feature = "iter_cloned", since = "1.1.0")]
418 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
419 #[derive(Clone, Debug)]
420 pub struct Cloned
<I
> {
424 #[stable(feature = "iter_cloned", since = "1.1.0")]
425 impl<'a
, I
, T
: 'a
> Iterator
for Cloned
<I
>
426 where I
: Iterator
<Item
=&'a T
>, T
: Clone
430 fn next(&mut self) -> Option
<T
> {
431 self.it
.next().cloned()
434 fn size_hint(&self) -> (usize, Option
<usize>) {
438 fn fold
<Acc
, F
>(self, init
: Acc
, mut f
: F
) -> Acc
439 where F
: FnMut(Acc
, Self::Item
) -> Acc
,
441 self.it
.fold(init
, move |acc
, elt
| f(acc
, elt
.clone()))
445 #[stable(feature = "iter_cloned", since = "1.1.0")]
446 impl<'a
, I
, T
: 'a
> DoubleEndedIterator
for Cloned
<I
>
447 where I
: DoubleEndedIterator
<Item
=&'a T
>, T
: Clone
449 fn next_back(&mut self) -> Option
<T
> {
450 self.it
.next_back().cloned()
454 #[stable(feature = "iter_cloned", since = "1.1.0")]
455 impl<'a
, I
, T
: 'a
> ExactSizeIterator
for Cloned
<I
>
456 where I
: ExactSizeIterator
<Item
=&'a T
>, T
: Clone
458 fn len(&self) -> usize {
462 fn is_empty(&self) -> bool
{
467 #[unstable(feature = "fused", issue = "35602")]
468 impl<'a
, I
, T
: 'a
> FusedIterator
for Cloned
<I
>
469 where I
: FusedIterator
<Item
=&'a T
>, T
: Clone
473 unsafe impl<'a
, I
, T
: 'a
> TrustedRandomAccess
for Cloned
<I
>
474 where I
: TrustedRandomAccess
<Item
=&'a T
>, T
: Clone
476 unsafe fn get_unchecked(&mut self, i
: usize) -> Self::Item
{
477 self.it
.get_unchecked(i
).clone()
481 fn may_have_side_effect() -> bool { true }
484 #[unstable(feature = "trusted_len", issue = "37572")]
485 unsafe impl<'a
, I
, T
: 'a
> TrustedLen
for Cloned
<I
>
486 where I
: TrustedLen
<Item
=&'a T
>,
490 /// An iterator that repeats endlessly.
492 /// This `struct` is created by the [`cycle`] method on [`Iterator`]. See its
493 /// documentation for more.
495 /// [`cycle`]: trait.Iterator.html#method.cycle
496 /// [`Iterator`]: trait.Iterator.html
497 #[derive(Clone, Debug)]
498 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
499 #[stable(feature = "rust1", since = "1.0.0")]
500 pub struct Cycle
<I
> {
505 #[stable(feature = "rust1", since = "1.0.0")]
506 impl<I
> Iterator
for Cycle
<I
> where I
: Clone
+ Iterator
{
507 type Item
= <I
as Iterator
>::Item
;
510 fn next(&mut self) -> Option
<<I
as Iterator
>::Item
> {
511 match self.iter
.next() {
512 None
=> { self.iter = self.orig.clone(); self.iter.next() }
518 fn size_hint(&self) -> (usize, Option
<usize>) {
519 // the cycle iterator is either empty or infinite
520 match self.orig
.size_hint() {
521 sz @
(0, Some(0)) => sz
,
523 _
=> (usize::MAX
, None
)
528 #[unstable(feature = "fused", issue = "35602")]
529 impl<I
> FusedIterator
for Cycle
<I
> where I
: Clone
+ Iterator {}
531 /// An adapter for stepping iterators by a custom amount.
533 /// This `struct` is created by the [`step_by`] method on [`Iterator`]. See
534 /// its documentation for more.
536 /// [`step_by`]: trait.Iterator.html#method.step_by
537 /// [`Iterator`]: trait.Iterator.html
538 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
539 #[unstable(feature = "iterator_step_by",
540 reason
= "unstable replacement of Range::step_by",
542 #[derive(Clone, Debug)]
543 pub struct StepBy
<I
> {
549 #[unstable(feature = "iterator_step_by",
550 reason
= "unstable replacement of Range::step_by",
552 impl<I
> Iterator
for StepBy
<I
> where I
: Iterator
{
556 fn next(&mut self) -> Option
<Self::Item
> {
558 self.first_take
= false;
561 self.iter
.nth(self.step
)
566 fn size_hint(&self) -> (usize, Option
<usize>) {
567 let inner_hint
= self.iter
.size_hint();
570 let f
= |n
| if n
== 0 { 0 }
else { 1 + (n-1)/(self.step+1) }
;
571 (f(inner_hint
.0), inner_hint
.1.map(f
))
573 let f
= |n
| n
/ (self.step
+1);
574 (f(inner_hint
.0), inner_hint
.1.map(f
))
579 // StepBy can only make the iterator shorter, so the len will still fit.
580 #[unstable(feature = "iterator_step_by",
581 reason
= "unstable replacement of Range::step_by",
583 impl<I
> ExactSizeIterator
for StepBy
<I
> where I
: ExactSizeIterator {}
585 /// An iterator that strings two iterators together.
587 /// This `struct` is created by the [`chain`] method on [`Iterator`]. See its
588 /// documentation for more.
590 /// [`chain`]: trait.Iterator.html#method.chain
591 /// [`Iterator`]: trait.Iterator.html
592 #[derive(Clone, Debug)]
593 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
594 #[stable(feature = "rust1", since = "1.0.0")]
595 pub struct Chain
<A
, B
> {
601 // The iterator protocol specifies that iteration ends with the return value
602 // `None` from `.next()` (or `.next_back()`) and it is unspecified what
603 // further calls return. The chain adaptor must account for this since it uses
606 // It uses three states:
608 // - Both: `a` and `b` are remaining
609 // - Front: `a` remaining
610 // - Back: `b` remaining
612 // The fourth state (neither iterator is remaining) only occurs after Chain has
613 // returned None once, so we don't need to store this state.
614 #[derive(Clone, Debug)]
616 // both front and back iterator are remaining
618 // only front is remaining
620 // only back is remaining
624 #[stable(feature = "rust1", since = "1.0.0")]
625 impl<A
, B
> Iterator
for Chain
<A
, B
> where
627 B
: Iterator
<Item
= A
::Item
>
632 fn next(&mut self) -> Option
<A
::Item
> {
634 ChainState
::Both
=> match self.a
.next() {
635 elt @
Some(..) => elt
,
637 self.state
= ChainState
::Back
;
641 ChainState
::Front
=> self.a
.next(),
642 ChainState
::Back
=> self.b
.next(),
647 #[rustc_inherit_overflow_checks]
648 fn count(self) -> usize {
650 ChainState
::Both
=> self.a
.count() + self.b
.count(),
651 ChainState
::Front
=> self.a
.count(),
652 ChainState
::Back
=> self.b
.count(),
656 fn fold
<Acc
, F
>(self, init
: Acc
, mut f
: F
) -> Acc
657 where F
: FnMut(Acc
, Self::Item
) -> Acc
,
659 let mut accum
= init
;
661 ChainState
::Both
| ChainState
::Front
=> {
662 accum
= self.a
.fold(accum
, &mut f
);
667 ChainState
::Both
| ChainState
::Back
=> {
668 accum
= self.b
.fold(accum
, &mut f
);
676 fn nth(&mut self, mut n
: usize) -> Option
<A
::Item
> {
678 ChainState
::Both
| ChainState
::Front
=> {
679 for x
in self.a
.by_ref() {
685 if let ChainState
::Both
= self.state
{
686 self.state
= ChainState
::Back
;
689 ChainState
::Back
=> {}
691 if let ChainState
::Back
= self.state
{
699 fn find
<P
>(&mut self, mut predicate
: P
) -> Option
<Self::Item
> where
700 P
: FnMut(&Self::Item
) -> bool
,
703 ChainState
::Both
=> match self.a
.find(&mut predicate
) {
705 self.state
= ChainState
::Back
;
706 self.b
.find(predicate
)
710 ChainState
::Front
=> self.a
.find(predicate
),
711 ChainState
::Back
=> self.b
.find(predicate
),
716 fn last(self) -> Option
<A
::Item
> {
718 ChainState
::Both
=> {
719 // Must exhaust a before b.
720 let a_last
= self.a
.last();
721 let b_last
= self.b
.last();
724 ChainState
::Front
=> self.a
.last(),
725 ChainState
::Back
=> self.b
.last()
730 fn size_hint(&self) -> (usize, Option
<usize>) {
731 let (a_lower
, a_upper
) = self.a
.size_hint();
732 let (b_lower
, b_upper
) = self.b
.size_hint();
734 let lower
= a_lower
.saturating_add(b_lower
);
736 let upper
= match (a_upper
, b_upper
) {
737 (Some(x
), Some(y
)) => x
.checked_add(y
),
745 #[stable(feature = "rust1", since = "1.0.0")]
746 impl<A
, B
> DoubleEndedIterator
for Chain
<A
, B
> where
747 A
: DoubleEndedIterator
,
748 B
: DoubleEndedIterator
<Item
=A
::Item
>,
751 fn next_back(&mut self) -> Option
<A
::Item
> {
753 ChainState
::Both
=> match self.b
.next_back() {
754 elt @
Some(..) => elt
,
756 self.state
= ChainState
::Front
;
760 ChainState
::Front
=> self.a
.next_back(),
761 ChainState
::Back
=> self.b
.next_back(),
766 // Note: *both* must be fused to handle double-ended iterators.
767 #[unstable(feature = "fused", issue = "35602")]
768 impl<A
, B
> FusedIterator
for Chain
<A
, B
>
769 where A
: FusedIterator
,
770 B
: FusedIterator
<Item
=A
::Item
>,
773 #[unstable(feature = "trusted_len", issue = "37572")]
774 unsafe impl<A
, B
> TrustedLen
for Chain
<A
, B
>
775 where A
: TrustedLen
, B
: TrustedLen
<Item
=A
::Item
>,
778 /// An iterator that iterates two other iterators simultaneously.
780 /// This `struct` is created by the [`zip`] method on [`Iterator`]. See its
781 /// documentation for more.
783 /// [`zip`]: trait.Iterator.html#method.zip
784 /// [`Iterator`]: trait.Iterator.html
785 #[derive(Clone, Debug)]
786 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
787 #[stable(feature = "rust1", since = "1.0.0")]
788 pub struct Zip
<A
, B
> {
791 // index and len are only used by the specialized version of zip
796 #[stable(feature = "rust1", since = "1.0.0")]
797 impl<A
, B
> Iterator
for Zip
<A
, B
> where A
: Iterator
, B
: Iterator
799 type Item
= (A
::Item
, B
::Item
);
802 fn next(&mut self) -> Option
<Self::Item
> {
807 fn size_hint(&self) -> (usize, Option
<usize>) {
808 ZipImpl
::size_hint(self)
812 #[stable(feature = "rust1", since = "1.0.0")]
813 impl<A
, B
> DoubleEndedIterator
for Zip
<A
, B
> where
814 A
: DoubleEndedIterator
+ ExactSizeIterator
,
815 B
: DoubleEndedIterator
+ ExactSizeIterator
,
818 fn next_back(&mut self) -> Option
<(A
::Item
, B
::Item
)> {
819 ZipImpl
::next_back(self)
823 // Zip specialization trait
825 trait ZipImpl
<A
, B
> {
827 fn new(a
: A
, b
: B
) -> Self;
828 fn next(&mut self) -> Option
<Self::Item
>;
829 fn size_hint(&self) -> (usize, Option
<usize>);
830 fn next_back(&mut self) -> Option
<Self::Item
>
831 where A
: DoubleEndedIterator
+ ExactSizeIterator
,
832 B
: DoubleEndedIterator
+ ExactSizeIterator
;
837 impl<A
, B
> ZipImpl
<A
, B
> for Zip
<A
, B
>
838 where A
: Iterator
, B
: Iterator
840 type Item
= (A
::Item
, B
::Item
);
841 default fn new(a
: A
, b
: B
) -> Self {
851 default fn next(&mut self) -> Option
<(A
::Item
, B
::Item
)> {
852 self.a
.next().and_then(|x
| {
853 self.b
.next().and_then(|y
| {
860 default fn next_back(&mut self) -> Option
<(A
::Item
, B
::Item
)>
861 where A
: DoubleEndedIterator
+ ExactSizeIterator
,
862 B
: DoubleEndedIterator
+ ExactSizeIterator
864 let a_sz
= self.a
.len();
865 let b_sz
= self.b
.len();
867 // Adjust a, b to equal length
869 for _
in 0..a_sz
- b_sz { self.a.next_back(); }
871 for _
in 0..b_sz
- a_sz { self.b.next_back(); }
874 match (self.a
.next_back(), self.b
.next_back()) {
875 (Some(x
), Some(y
)) => Some((x
, y
)),
876 (None
, None
) => None
,
882 default fn size_hint(&self) -> (usize, Option
<usize>) {
883 let (a_lower
, a_upper
) = self.a
.size_hint();
884 let (b_lower
, b_upper
) = self.b
.size_hint();
886 let lower
= cmp
::min(a_lower
, b_lower
);
888 let upper
= match (a_upper
, b_upper
) {
889 (Some(x
), Some(y
)) => Some(cmp
::min(x
,y
)),
890 (Some(x
), None
) => Some(x
),
891 (None
, Some(y
)) => Some(y
),
900 impl<A
, B
> ZipImpl
<A
, B
> for Zip
<A
, B
>
901 where A
: TrustedRandomAccess
, B
: TrustedRandomAccess
903 fn new(a
: A
, b
: B
) -> Self {
904 let len
= cmp
::min(a
.len(), b
.len());
914 fn next(&mut self) -> Option
<(A
::Item
, B
::Item
)> {
915 if self.index
< self.len
{
919 Some((self.a
.get_unchecked(i
), self.b
.get_unchecked(i
)))
921 } else if A
::may_have_side_effect() && self.index
< self.a
.len() {
922 // match the base implementation's potential side effects
924 self.a
.get_unchecked(self.index
);
934 fn size_hint(&self) -> (usize, Option
<usize>) {
935 let len
= self.len
- self.index
;
940 fn next_back(&mut self) -> Option
<(A
::Item
, B
::Item
)>
941 where A
: DoubleEndedIterator
+ ExactSizeIterator
,
942 B
: DoubleEndedIterator
+ ExactSizeIterator
944 // Adjust a, b to equal length
945 if A
::may_have_side_effect() {
946 let sz
= self.a
.len();
948 for _
in 0..sz
- cmp
::max(self.len
, self.index
) {
953 if B
::may_have_side_effect() {
954 let sz
= self.b
.len();
956 for _
in 0..sz
- self.len
{
961 if self.index
< self.len
{
965 Some((self.a
.get_unchecked(i
), self.b
.get_unchecked(i
)))
973 #[stable(feature = "rust1", since = "1.0.0")]
974 impl<A
, B
> ExactSizeIterator
for Zip
<A
, B
>
975 where A
: ExactSizeIterator
, B
: ExactSizeIterator {}
978 unsafe impl<A
, B
> TrustedRandomAccess
for Zip
<A
, B
>
979 where A
: TrustedRandomAccess
,
980 B
: TrustedRandomAccess
,
982 unsafe fn get_unchecked(&mut self, i
: usize) -> (A
::Item
, B
::Item
) {
983 (self.a
.get_unchecked(i
), self.b
.get_unchecked(i
))
986 fn may_have_side_effect() -> bool
{
987 A
::may_have_side_effect() || B
::may_have_side_effect()
991 #[unstable(feature = "fused", issue = "35602")]
992 impl<A
, B
> FusedIterator
for Zip
<A
, B
>
993 where A
: FusedIterator
, B
: FusedIterator
, {}
995 #[unstable(feature = "trusted_len", issue = "37572")]
996 unsafe impl<A
, B
> TrustedLen
for Zip
<A
, B
>
997 where A
: TrustedLen
, B
: TrustedLen
,
1000 /// An iterator that maps the values of `iter` with `f`.
1002 /// This `struct` is created by the [`map`] method on [`Iterator`]. See its
1003 /// documentation for more.
1005 /// [`map`]: trait.Iterator.html#method.map
1006 /// [`Iterator`]: trait.Iterator.html
1008 /// # Notes about side effects
1010 /// The [`map`] iterator implements [`DoubleEndedIterator`], meaning that
1011 /// you can also [`map`] backwards:
1014 /// let v: Vec<i32> = vec![1, 2, 3].into_iter().map(|x| x + 1).rev().collect();
1016 /// assert_eq!(v, [4, 3, 2]);
1019 /// [`DoubleEndedIterator`]: trait.DoubleEndedIterator.html
1021 /// But if your closure has state, iterating backwards may act in a way you do
1022 /// not expect. Let's go through an example. First, in the forward direction:
1027 /// for pair in vec!['a', 'b', 'c'].into_iter()
1028 /// .map(|letter| { c += 1; (letter, c) }) {
1029 /// println!("{:?}", pair);
1033 /// This will print "('a', 1), ('b', 2), ('c', 3)".
1035 /// Now consider this twist where we add a call to `rev`. This version will
1036 /// print `('c', 1), ('b', 2), ('a', 3)`. Note that the letters are reversed,
1037 /// but the values of the counter still go in order. This is because `map()` is
1038 /// still being called lazilly on each item, but we are popping items off the
1039 /// back of the vector now, instead of shifting them from the front.
1044 /// for pair in vec!['a', 'b', 'c'].into_iter()
1045 /// .map(|letter| { c += 1; (letter, c) })
1047 /// println!("{:?}", pair);
1050 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1051 #[stable(feature = "rust1", since = "1.0.0")]
1053 pub struct Map
<I
, F
> {
1058 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1059 impl<I
: fmt
::Debug
, F
> fmt
::Debug
for Map
<I
, F
> {
1060 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
1061 f
.debug_struct("Map")
1062 .field("iter", &self.iter
)
1067 #[stable(feature = "rust1", since = "1.0.0")]
1068 impl<B
, I
: Iterator
, F
> Iterator
for Map
<I
, F
> where F
: FnMut(I
::Item
) -> B
{
1072 fn next(&mut self) -> Option
<B
> {
1073 self.iter
.next().map(&mut self.f
)
1077 fn size_hint(&self) -> (usize, Option
<usize>) {
1078 self.iter
.size_hint()
1081 fn fold
<Acc
, G
>(self, init
: Acc
, mut g
: G
) -> Acc
1082 where G
: FnMut(Acc
, Self::Item
) -> Acc
,
1085 self.iter
.fold(init
, move |acc
, elt
| g(acc
, f(elt
)))
1089 #[stable(feature = "rust1", since = "1.0.0")]
1090 impl<B
, I
: DoubleEndedIterator
, F
> DoubleEndedIterator
for Map
<I
, F
> where
1091 F
: FnMut(I
::Item
) -> B
,
1094 fn next_back(&mut self) -> Option
<B
> {
1095 self.iter
.next_back().map(&mut self.f
)
1099 #[stable(feature = "rust1", since = "1.0.0")]
1100 impl<B
, I
: ExactSizeIterator
, F
> ExactSizeIterator
for Map
<I
, F
>
1101 where F
: FnMut(I
::Item
) -> B
1103 fn len(&self) -> usize {
1107 fn is_empty(&self) -> bool
{
1108 self.iter
.is_empty()
1112 #[unstable(feature = "fused", issue = "35602")]
1113 impl<B
, I
: FusedIterator
, F
> FusedIterator
for Map
<I
, F
>
1114 where F
: FnMut(I
::Item
) -> B {}
1116 #[unstable(feature = "trusted_len", issue = "37572")]
1117 unsafe impl<B
, I
, F
> TrustedLen
for Map
<I
, F
>
1118 where I
: TrustedLen
,
1119 F
: FnMut(I
::Item
) -> B {}
1122 unsafe impl<B
, I
, F
> TrustedRandomAccess
for Map
<I
, F
>
1123 where I
: TrustedRandomAccess
,
1124 F
: FnMut(I
::Item
) -> B
,
1126 unsafe fn get_unchecked(&mut self, i
: usize) -> Self::Item
{
1127 (self.f
)(self.iter
.get_unchecked(i
))
1130 fn may_have_side_effect() -> bool { true }
1133 /// An iterator that filters the elements of `iter` with `predicate`.
1135 /// This `struct` is created by the [`filter`] method on [`Iterator`]. See its
1136 /// documentation for more.
1138 /// [`filter`]: trait.Iterator.html#method.filter
1139 /// [`Iterator`]: trait.Iterator.html
1140 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1141 #[stable(feature = "rust1", since = "1.0.0")]
1143 pub struct Filter
<I
, P
> {
1148 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1149 impl<I
: fmt
::Debug
, P
> fmt
::Debug
for Filter
<I
, P
> {
1150 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
1151 f
.debug_struct("Filter")
1152 .field("iter", &self.iter
)
1157 #[stable(feature = "rust1", since = "1.0.0")]
1158 impl<I
: Iterator
, P
> Iterator
for Filter
<I
, P
> where P
: FnMut(&I
::Item
) -> bool
{
1159 type Item
= I
::Item
;
1162 fn next(&mut self) -> Option
<I
::Item
> {
1163 for x
in &mut self.iter
{
1164 if (self.predicate
)(&x
) {
1172 fn size_hint(&self) -> (usize, Option
<usize>) {
1173 let (_
, upper
) = self.iter
.size_hint();
1174 (0, upper
) // can't know a lower bound, due to the predicate
1177 // this special case allows the compiler to make `.filter(_).count()`
1178 // branchless. Barring perfect branch prediction (which is unattainable in
1179 // the general case), this will be much faster in >90% of cases (containing
1180 // virtually all real workloads) and only a tiny bit slower in the rest.
1182 // Having this specialization thus allows us to write `.filter(p).count()`
1183 // where we would otherwise write `.map(|x| p(x) as usize).sum()`, which is
1184 // less readable and also less backwards-compatible to Rust before 1.10.
1186 // Using the branchless version will also simplify the LLVM byte code, thus
1187 // leaving more budget for LLVM optimizations.
1189 fn count(mut self) -> usize {
1191 for x
in &mut self.iter
{
1192 count
+= (self.predicate
)(&x
) as usize;
1198 #[stable(feature = "rust1", since = "1.0.0")]
1199 impl<I
: DoubleEndedIterator
, P
> DoubleEndedIterator
for Filter
<I
, P
>
1200 where P
: FnMut(&I
::Item
) -> bool
,
1203 fn next_back(&mut self) -> Option
<I
::Item
> {
1204 for x
in self.iter
.by_ref().rev() {
1205 if (self.predicate
)(&x
) {
1213 #[unstable(feature = "fused", issue = "35602")]
1214 impl<I
: FusedIterator
, P
> FusedIterator
for Filter
<I
, P
>
1215 where P
: FnMut(&I
::Item
) -> bool {}
1217 /// An iterator that uses `f` to both filter and map elements from `iter`.
1219 /// This `struct` is created by the [`filter_map`] method on [`Iterator`]. See its
1220 /// documentation for more.
1222 /// [`filter_map`]: trait.Iterator.html#method.filter_map
1223 /// [`Iterator`]: trait.Iterator.html
1224 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1225 #[stable(feature = "rust1", since = "1.0.0")]
1227 pub struct FilterMap
<I
, F
> {
1232 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1233 impl<I
: fmt
::Debug
, F
> fmt
::Debug
for FilterMap
<I
, F
> {
1234 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
1235 f
.debug_struct("FilterMap")
1236 .field("iter", &self.iter
)
1241 #[stable(feature = "rust1", since = "1.0.0")]
1242 impl<B
, I
: Iterator
, F
> Iterator
for FilterMap
<I
, F
>
1243 where F
: FnMut(I
::Item
) -> Option
<B
>,
1248 fn next(&mut self) -> Option
<B
> {
1249 for x
in self.iter
.by_ref() {
1250 if let Some(y
) = (self.f
)(x
) {
1258 fn size_hint(&self) -> (usize, Option
<usize>) {
1259 let (_
, upper
) = self.iter
.size_hint();
1260 (0, upper
) // can't know a lower bound, due to the predicate
1264 #[stable(feature = "rust1", since = "1.0.0")]
1265 impl<B
, I
: DoubleEndedIterator
, F
> DoubleEndedIterator
for FilterMap
<I
, F
>
1266 where F
: FnMut(I
::Item
) -> Option
<B
>,
1269 fn next_back(&mut self) -> Option
<B
> {
1270 for x
in self.iter
.by_ref().rev() {
1271 if let Some(y
) = (self.f
)(x
) {
1279 #[unstable(feature = "fused", issue = "35602")]
1280 impl<B
, I
: FusedIterator
, F
> FusedIterator
for FilterMap
<I
, F
>
1281 where F
: FnMut(I
::Item
) -> Option
<B
> {}
1283 /// An iterator that yields the current count and the element during iteration.
1285 /// This `struct` is created by the [`enumerate`] method on [`Iterator`]. See its
1286 /// documentation for more.
1288 /// [`enumerate`]: trait.Iterator.html#method.enumerate
1289 /// [`Iterator`]: trait.Iterator.html
1290 #[derive(Clone, Debug)]
1291 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1292 #[stable(feature = "rust1", since = "1.0.0")]
1293 pub struct Enumerate
<I
> {
1298 #[stable(feature = "rust1", since = "1.0.0")]
1299 impl<I
> Iterator
for Enumerate
<I
> where I
: Iterator
{
1300 type Item
= (usize, <I
as Iterator
>::Item
);
1302 /// # Overflow Behavior
1304 /// The method does no guarding against overflows, so enumerating more than
1305 /// `usize::MAX` elements either produces the wrong result or panics. If
1306 /// debug assertions are enabled, a panic is guaranteed.
1310 /// Might panic if the index of the element overflows a `usize`.
1312 #[rustc_inherit_overflow_checks]
1313 fn next(&mut self) -> Option
<(usize, <I
as Iterator
>::Item
)> {
1314 self.iter
.next().map(|a
| {
1315 let ret
= (self.count
, a
);
1316 // Possible undefined overflow.
1323 fn size_hint(&self) -> (usize, Option
<usize>) {
1324 self.iter
.size_hint()
1328 #[rustc_inherit_overflow_checks]
1329 fn nth(&mut self, n
: usize) -> Option
<(usize, I
::Item
)> {
1330 self.iter
.nth(n
).map(|a
| {
1331 let i
= self.count
+ n
;
1338 fn count(self) -> usize {
1343 #[stable(feature = "rust1", since = "1.0.0")]
1344 impl<I
> DoubleEndedIterator
for Enumerate
<I
> where
1345 I
: ExactSizeIterator
+ DoubleEndedIterator
1348 fn next_back(&mut self) -> Option
<(usize, <I
as Iterator
>::Item
)> {
1349 self.iter
.next_back().map(|a
| {
1350 let len
= self.iter
.len();
1351 // Can safely add, `ExactSizeIterator` promises that the number of
1352 // elements fits into a `usize`.
1353 (self.count
+ len
, a
)
1358 #[stable(feature = "rust1", since = "1.0.0")]
1359 impl<I
> ExactSizeIterator
for Enumerate
<I
> where I
: ExactSizeIterator
{
1360 fn len(&self) -> usize {
1364 fn is_empty(&self) -> bool
{
1365 self.iter
.is_empty()
1370 unsafe impl<I
> TrustedRandomAccess
for Enumerate
<I
>
1371 where I
: TrustedRandomAccess
1373 unsafe fn get_unchecked(&mut self, i
: usize) -> (usize, I
::Item
) {
1374 (self.count
+ i
, self.iter
.get_unchecked(i
))
1377 fn may_have_side_effect() -> bool
{
1378 I
::may_have_side_effect()
1382 #[unstable(feature = "fused", issue = "35602")]
1383 impl<I
> FusedIterator
for Enumerate
<I
> where I
: FusedIterator {}
1385 #[unstable(feature = "trusted_len", issue = "37572")]
1386 unsafe impl<I
> TrustedLen
for Enumerate
<I
>
1387 where I
: TrustedLen
,
1391 /// An iterator with a `peek()` that returns an optional reference to the next
1394 /// This `struct` is created by the [`peekable`] method on [`Iterator`]. See its
1395 /// documentation for more.
1397 /// [`peekable`]: trait.Iterator.html#method.peekable
1398 /// [`Iterator`]: trait.Iterator.html
1399 #[derive(Clone, Debug)]
1400 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1401 #[stable(feature = "rust1", since = "1.0.0")]
1402 pub struct Peekable
<I
: Iterator
> {
1404 /// Remember a peeked value, even if it was None.
1405 peeked
: Option
<Option
<I
::Item
>>,
1408 // Peekable must remember if a None has been seen in the `.peek()` method.
1409 // It ensures that `.peek(); .peek();` or `.peek(); .next();` only advances the
1410 // underlying iterator at most once. This does not by itself make the iterator
1412 #[stable(feature = "rust1", since = "1.0.0")]
1413 impl<I
: Iterator
> Iterator
for Peekable
<I
> {
1414 type Item
= I
::Item
;
1417 fn next(&mut self) -> Option
<I
::Item
> {
1418 match self.peeked
.take() {
1420 None
=> self.iter
.next(),
1425 #[rustc_inherit_overflow_checks]
1426 fn count(mut self) -> usize {
1427 match self.peeked
.take() {
1429 Some(Some(_
)) => 1 + self.iter
.count(),
1430 None
=> self.iter
.count(),
1435 fn nth(&mut self, n
: usize) -> Option
<I
::Item
> {
1436 match self.peeked
.take() {
1437 // the .take() below is just to avoid "move into pattern guard"
1438 Some(ref mut v
) if n
== 0 => v
.take(),
1440 Some(Some(_
)) => self.iter
.nth(n
- 1),
1441 None
=> self.iter
.nth(n
),
1446 fn last(mut self) -> Option
<I
::Item
> {
1447 let peek_opt
= match self.peeked
.take() {
1448 Some(None
) => return None
,
1452 self.iter
.last().or(peek_opt
)
1456 fn size_hint(&self) -> (usize, Option
<usize>) {
1457 let peek_len
= match self.peeked
{
1458 Some(None
) => return (0, Some(0)),
1462 let (lo
, hi
) = self.iter
.size_hint();
1463 let lo
= lo
.saturating_add(peek_len
);
1464 let hi
= hi
.and_then(|x
| x
.checked_add(peek_len
));
1469 #[stable(feature = "rust1", since = "1.0.0")]
1470 impl<I
: ExactSizeIterator
> ExactSizeIterator
for Peekable
<I
> {}
1472 #[unstable(feature = "fused", issue = "35602")]
1473 impl<I
: FusedIterator
> FusedIterator
for Peekable
<I
> {}
1475 impl<I
: Iterator
> Peekable
<I
> {
1476 /// Returns a reference to the next() value without advancing the iterator.
1478 /// Like [`next`], if there is a value, it is wrapped in a `Some(T)`.
1479 /// But if the iteration is over, `None` is returned.
1481 /// [`next`]: trait.Iterator.html#tymethod.next
1483 /// Because `peek()` returns a reference, and many iterators iterate over
1484 /// references, there can be a possibly confusing situation where the
1485 /// return value is a double reference. You can see this effect in the
1493 /// let xs = [1, 2, 3];
1495 /// let mut iter = xs.iter().peekable();
1497 /// // peek() lets us see into the future
1498 /// assert_eq!(iter.peek(), Some(&&1));
1499 /// assert_eq!(iter.next(), Some(&1));
1501 /// assert_eq!(iter.next(), Some(&2));
1503 /// // The iterator does not advance even if we `peek` multiple times
1504 /// assert_eq!(iter.peek(), Some(&&3));
1505 /// assert_eq!(iter.peek(), Some(&&3));
1507 /// assert_eq!(iter.next(), Some(&3));
1509 /// // After the iterator is finished, so is `peek()`
1510 /// assert_eq!(iter.peek(), None);
1511 /// assert_eq!(iter.next(), None);
1514 #[stable(feature = "rust1", since = "1.0.0")]
1515 pub fn peek(&mut self) -> Option
<&I
::Item
> {
1516 if self.peeked
.is_none() {
1517 self.peeked
= Some(self.iter
.next());
1520 Some(Some(ref value
)) => Some(value
),
1522 _
=> unreachable
!(),
1527 /// An iterator that rejects elements while `predicate` is true.
1529 /// This `struct` is created by the [`skip_while`] method on [`Iterator`]. See its
1530 /// documentation for more.
1532 /// [`skip_while`]: trait.Iterator.html#method.skip_while
1533 /// [`Iterator`]: trait.Iterator.html
1534 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1535 #[stable(feature = "rust1", since = "1.0.0")]
1537 pub struct SkipWhile
<I
, P
> {
1543 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1544 impl<I
: fmt
::Debug
, P
> fmt
::Debug
for SkipWhile
<I
, P
> {
1545 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
1546 f
.debug_struct("SkipWhile")
1547 .field("iter", &self.iter
)
1548 .field("flag", &self.flag
)
1553 #[stable(feature = "rust1", since = "1.0.0")]
1554 impl<I
: Iterator
, P
> Iterator
for SkipWhile
<I
, P
>
1555 where P
: FnMut(&I
::Item
) -> bool
1557 type Item
= I
::Item
;
1560 fn next(&mut self) -> Option
<I
::Item
> {
1561 for x
in self.iter
.by_ref() {
1562 if self.flag
|| !(self.predicate
)(&x
) {
1571 fn size_hint(&self) -> (usize, Option
<usize>) {
1572 let (_
, upper
) = self.iter
.size_hint();
1573 (0, upper
) // can't know a lower bound, due to the predicate
1577 #[unstable(feature = "fused", issue = "35602")]
1578 impl<I
, P
> FusedIterator
for SkipWhile
<I
, P
>
1579 where I
: FusedIterator
, P
: FnMut(&I
::Item
) -> bool {}
1581 /// An iterator that only accepts elements while `predicate` is true.
1583 /// This `struct` is created by the [`take_while`] method on [`Iterator`]. See its
1584 /// documentation for more.
1586 /// [`take_while`]: trait.Iterator.html#method.take_while
1587 /// [`Iterator`]: trait.Iterator.html
1588 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1589 #[stable(feature = "rust1", since = "1.0.0")]
1591 pub struct TakeWhile
<I
, P
> {
1597 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1598 impl<I
: fmt
::Debug
, P
> fmt
::Debug
for TakeWhile
<I
, P
> {
1599 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
1600 f
.debug_struct("TakeWhile")
1601 .field("iter", &self.iter
)
1602 .field("flag", &self.flag
)
1607 #[stable(feature = "rust1", since = "1.0.0")]
1608 impl<I
: Iterator
, P
> Iterator
for TakeWhile
<I
, P
>
1609 where P
: FnMut(&I
::Item
) -> bool
1611 type Item
= I
::Item
;
1614 fn next(&mut self) -> Option
<I
::Item
> {
1618 self.iter
.next().and_then(|x
| {
1619 if (self.predicate
)(&x
) {
1630 fn size_hint(&self) -> (usize, Option
<usize>) {
1631 let (_
, upper
) = self.iter
.size_hint();
1632 (0, upper
) // can't know a lower bound, due to the predicate
1636 #[unstable(feature = "fused", issue = "35602")]
1637 impl<I
, P
> FusedIterator
for TakeWhile
<I
, P
>
1638 where I
: FusedIterator
, P
: FnMut(&I
::Item
) -> bool {}
1640 /// An iterator that skips over `n` elements of `iter`.
1642 /// This `struct` is created by the [`skip`] method on [`Iterator`]. See its
1643 /// documentation for more.
1645 /// [`skip`]: trait.Iterator.html#method.skip
1646 /// [`Iterator`]: trait.Iterator.html
1647 #[derive(Clone, Debug)]
1648 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1649 #[stable(feature = "rust1", since = "1.0.0")]
1650 pub struct Skip
<I
> {
1655 #[stable(feature = "rust1", since = "1.0.0")]
1656 impl<I
> Iterator
for Skip
<I
> where I
: Iterator
{
1657 type Item
= <I
as Iterator
>::Item
;
1660 fn next(&mut self) -> Option
<I
::Item
> {
1666 self.iter
.nth(old_n
)
1671 fn nth(&mut self, n
: usize) -> Option
<I
::Item
> {
1672 // Can't just add n + self.n due to overflow.
1676 let to_skip
= self.n
;
1679 if self.iter
.nth(to_skip
-1).is_none() {
1687 fn count(self) -> usize {
1688 self.iter
.count().saturating_sub(self.n
)
1692 fn last(mut self) -> Option
<I
::Item
> {
1696 let next
= self.next();
1698 // recurse. n should be 0.
1699 self.last().or(next
)
1707 fn size_hint(&self) -> (usize, Option
<usize>) {
1708 let (lower
, upper
) = self.iter
.size_hint();
1710 let lower
= lower
.saturating_sub(self.n
);
1711 let upper
= upper
.map(|x
| x
.saturating_sub(self.n
));
1717 #[stable(feature = "rust1", since = "1.0.0")]
1718 impl<I
> ExactSizeIterator
for Skip
<I
> where I
: ExactSizeIterator {}
1720 #[stable(feature = "double_ended_skip_iterator", since = "1.9.0")]
1721 impl<I
> DoubleEndedIterator
for Skip
<I
> where I
: DoubleEndedIterator
+ ExactSizeIterator
{
1722 fn next_back(&mut self) -> Option
<Self::Item
> {
1724 self.iter
.next_back()
1731 #[unstable(feature = "fused", issue = "35602")]
1732 impl<I
> FusedIterator
for Skip
<I
> where I
: FusedIterator {}
1734 /// An iterator that only iterates over the first `n` iterations of `iter`.
1736 /// This `struct` is created by the [`take`] method on [`Iterator`]. See its
1737 /// documentation for more.
1739 /// [`take`]: trait.Iterator.html#method.take
1740 /// [`Iterator`]: trait.Iterator.html
1741 #[derive(Clone, Debug)]
1742 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1743 #[stable(feature = "rust1", since = "1.0.0")]
1744 pub struct Take
<I
> {
1749 #[stable(feature = "rust1", since = "1.0.0")]
1750 impl<I
> Iterator
for Take
<I
> where I
: Iterator
{
1751 type Item
= <I
as Iterator
>::Item
;
1754 fn next(&mut self) -> Option
<<I
as Iterator
>::Item
> {
1764 fn nth(&mut self, n
: usize) -> Option
<I
::Item
> {
1770 self.iter
.nth(self.n
- 1);
1778 fn size_hint(&self) -> (usize, Option
<usize>) {
1779 let (lower
, upper
) = self.iter
.size_hint();
1781 let lower
= cmp
::min(lower
, self.n
);
1783 let upper
= match upper
{
1784 Some(x
) if x
< self.n
=> Some(x
),
1792 #[stable(feature = "rust1", since = "1.0.0")]
1793 impl<I
> ExactSizeIterator
for Take
<I
> where I
: ExactSizeIterator {}
1795 #[unstable(feature = "fused", issue = "35602")]
1796 impl<I
> FusedIterator
for Take
<I
> where I
: FusedIterator {}
1798 /// An iterator to maintain state while iterating another iterator.
1800 /// This `struct` is created by the [`scan`] method on [`Iterator`]. See its
1801 /// documentation for more.
1803 /// [`scan`]: trait.Iterator.html#method.scan
1804 /// [`Iterator`]: trait.Iterator.html
1805 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1806 #[stable(feature = "rust1", since = "1.0.0")]
1808 pub struct Scan
<I
, St
, F
> {
1814 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1815 impl<I
: fmt
::Debug
, St
: fmt
::Debug
, F
> fmt
::Debug
for Scan
<I
, St
, F
> {
1816 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
1817 f
.debug_struct("Scan")
1818 .field("iter", &self.iter
)
1819 .field("state", &self.state
)
1824 #[stable(feature = "rust1", since = "1.0.0")]
1825 impl<B
, I
, St
, F
> Iterator
for Scan
<I
, St
, F
> where
1827 F
: FnMut(&mut St
, I
::Item
) -> Option
<B
>,
1832 fn next(&mut self) -> Option
<B
> {
1833 self.iter
.next().and_then(|a
| (self.f
)(&mut self.state
, a
))
1837 fn size_hint(&self) -> (usize, Option
<usize>) {
1838 let (_
, upper
) = self.iter
.size_hint();
1839 (0, upper
) // can't know a lower bound, due to the scan function
1843 /// An iterator that maps each element to an iterator, and yields the elements
1844 /// of the produced iterators.
1846 /// This `struct` is created by the [`flat_map`] method on [`Iterator`]. See its
1847 /// documentation for more.
1849 /// [`flat_map`]: trait.Iterator.html#method.flat_map
1850 /// [`Iterator`]: trait.Iterator.html
1851 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1852 #[stable(feature = "rust1", since = "1.0.0")]
1854 pub struct FlatMap
<I
, U
: IntoIterator
, F
> {
1857 frontiter
: Option
<U
::IntoIter
>,
1858 backiter
: Option
<U
::IntoIter
>,
1861 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1862 impl<I
: fmt
::Debug
, U
: IntoIterator
, F
> fmt
::Debug
for FlatMap
<I
, U
, F
>
1863 where U
::IntoIter
: fmt
::Debug
1865 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
1866 f
.debug_struct("FlatMap")
1867 .field("iter", &self.iter
)
1868 .field("frontiter", &self.frontiter
)
1869 .field("backiter", &self.backiter
)
1874 #[stable(feature = "rust1", since = "1.0.0")]
1875 impl<I
: Iterator
, U
: IntoIterator
, F
> Iterator
for FlatMap
<I
, U
, F
>
1876 where F
: FnMut(I
::Item
) -> U
,
1878 type Item
= U
::Item
;
1881 fn next(&mut self) -> Option
<U
::Item
> {
1883 if let Some(ref mut inner
) = self.frontiter
{
1884 if let Some(x
) = inner
.by_ref().next() {
1888 match self.iter
.next().map(&mut self.f
) {
1889 None
=> return self.backiter
.as_mut().and_then(|it
| it
.next()),
1890 next
=> self.frontiter
= next
.map(IntoIterator
::into_iter
),
1896 fn size_hint(&self) -> (usize, Option
<usize>) {
1897 let (flo
, fhi
) = self.frontiter
.as_ref().map_or((0, Some(0)), |it
| it
.size_hint());
1898 let (blo
, bhi
) = self.backiter
.as_ref().map_or((0, Some(0)), |it
| it
.size_hint());
1899 let lo
= flo
.saturating_add(blo
);
1900 match (self.iter
.size_hint(), fhi
, bhi
) {
1901 ((0, Some(0)), Some(a
), Some(b
)) => (lo
, a
.checked_add(b
)),
1907 #[stable(feature = "rust1", since = "1.0.0")]
1908 impl<I
: DoubleEndedIterator
, U
, F
> DoubleEndedIterator
for FlatMap
<I
, U
, F
> where
1909 F
: FnMut(I
::Item
) -> U
,
1911 U
::IntoIter
: DoubleEndedIterator
1914 fn next_back(&mut self) -> Option
<U
::Item
> {
1916 if let Some(ref mut inner
) = self.backiter
{
1917 if let Some(y
) = inner
.next_back() {
1921 match self.iter
.next_back().map(&mut self.f
) {
1922 None
=> return self.frontiter
.as_mut().and_then(|it
| it
.next_back()),
1923 next
=> self.backiter
= next
.map(IntoIterator
::into_iter
),
1929 #[unstable(feature = "fused", issue = "35602")]
1930 impl<I
, U
, F
> FusedIterator
for FlatMap
<I
, U
, F
>
1931 where I
: FusedIterator
, U
: IntoIterator
, F
: FnMut(I
::Item
) -> U {}
1933 /// An iterator that yields `None` forever after the underlying iterator
1934 /// yields `None` once.
1936 /// This `struct` is created by the [`fuse`] method on [`Iterator`]. See its
1937 /// documentation for more.
1939 /// [`fuse`]: trait.Iterator.html#method.fuse
1940 /// [`Iterator`]: trait.Iterator.html
1941 #[derive(Clone, Debug)]
1942 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1943 #[stable(feature = "rust1", since = "1.0.0")]
1944 pub struct Fuse
<I
> {
1949 #[unstable(feature = "fused", issue = "35602")]
1950 impl<I
> FusedIterator
for Fuse
<I
> where I
: Iterator {}
1952 #[stable(feature = "rust1", since = "1.0.0")]
1953 impl<I
> Iterator
for Fuse
<I
> where I
: Iterator
{
1954 type Item
= <I
as Iterator
>::Item
;
1957 default fn next(&mut self) -> Option
<<I
as Iterator
>::Item
> {
1961 let next
= self.iter
.next();
1962 self.done
= next
.is_none();
1968 default fn nth(&mut self, n
: usize) -> Option
<I
::Item
> {
1972 let nth
= self.iter
.nth(n
);
1973 self.done
= nth
.is_none();
1979 default fn last(self) -> Option
<I
::Item
> {
1988 default fn count(self) -> usize {
1997 default fn size_hint(&self) -> (usize, Option
<usize>) {
2001 self.iter
.size_hint()
2006 #[stable(feature = "rust1", since = "1.0.0")]
2007 impl<I
> DoubleEndedIterator
for Fuse
<I
> where I
: DoubleEndedIterator
{
2009 default fn next_back(&mut self) -> Option
<<I
as Iterator
>::Item
> {
2013 let next
= self.iter
.next_back();
2014 self.done
= next
.is_none();
2020 unsafe impl<I
> TrustedRandomAccess
for Fuse
<I
>
2021 where I
: TrustedRandomAccess
,
2023 unsafe fn get_unchecked(&mut self, i
: usize) -> I
::Item
{
2024 self.iter
.get_unchecked(i
)
2027 fn may_have_side_effect() -> bool
{
2028 I
::may_have_side_effect()
2032 #[unstable(feature = "fused", issue = "35602")]
2033 impl<I
> Iterator
for Fuse
<I
> where I
: FusedIterator
{
2035 fn next(&mut self) -> Option
<<I
as Iterator
>::Item
> {
2040 fn nth(&mut self, n
: usize) -> Option
<I
::Item
> {
2045 fn last(self) -> Option
<I
::Item
> {
2050 fn count(self) -> usize {
2055 fn size_hint(&self) -> (usize, Option
<usize>) {
2056 self.iter
.size_hint()
2060 #[unstable(feature = "fused", reason = "recently added", issue = "35602")]
2061 impl<I
> DoubleEndedIterator
for Fuse
<I
>
2062 where I
: DoubleEndedIterator
+ FusedIterator
2065 fn next_back(&mut self) -> Option
<<I
as Iterator
>::Item
> {
2066 self.iter
.next_back()
2071 #[stable(feature = "rust1", since = "1.0.0")]
2072 impl<I
> ExactSizeIterator
for Fuse
<I
> where I
: ExactSizeIterator
{
2073 fn len(&self) -> usize {
2077 fn is_empty(&self) -> bool
{
2078 self.iter
.is_empty()
2082 /// An iterator that calls a function with a reference to each element before
2085 /// This `struct` is created by the [`inspect`] method on [`Iterator`]. See its
2086 /// documentation for more.
2088 /// [`inspect`]: trait.Iterator.html#method.inspect
2089 /// [`Iterator`]: trait.Iterator.html
2090 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2091 #[stable(feature = "rust1", since = "1.0.0")]
2093 pub struct Inspect
<I
, F
> {
2098 #[stable(feature = "core_impl_debug", since = "1.9.0")]
2099 impl<I
: fmt
::Debug
, F
> fmt
::Debug
for Inspect
<I
, F
> {
2100 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
2101 f
.debug_struct("Inspect")
2102 .field("iter", &self.iter
)
2107 impl<I
: Iterator
, F
> Inspect
<I
, F
> where F
: FnMut(&I
::Item
) {
2109 fn do_inspect(&mut self, elt
: Option
<I
::Item
>) -> Option
<I
::Item
> {
2110 if let Some(ref a
) = elt
{
2118 #[stable(feature = "rust1", since = "1.0.0")]
2119 impl<I
: Iterator
, F
> Iterator
for Inspect
<I
, F
> where F
: FnMut(&I
::Item
) {
2120 type Item
= I
::Item
;
2123 fn next(&mut self) -> Option
<I
::Item
> {
2124 let next
= self.iter
.next();
2125 self.do_inspect(next
)
2129 fn size_hint(&self) -> (usize, Option
<usize>) {
2130 self.iter
.size_hint()
2134 #[stable(feature = "rust1", since = "1.0.0")]
2135 impl<I
: DoubleEndedIterator
, F
> DoubleEndedIterator
for Inspect
<I
, F
>
2136 where F
: FnMut(&I
::Item
),
2139 fn next_back(&mut self) -> Option
<I
::Item
> {
2140 let next
= self.iter
.next_back();
2141 self.do_inspect(next
)
2145 #[stable(feature = "rust1", since = "1.0.0")]
2146 impl<I
: ExactSizeIterator
, F
> ExactSizeIterator
for Inspect
<I
, F
>
2147 where F
: FnMut(&I
::Item
)
2149 fn len(&self) -> usize {
2153 fn is_empty(&self) -> bool
{
2154 self.iter
.is_empty()
2158 #[unstable(feature = "fused", issue = "35602")]
2159 impl<I
: FusedIterator
, F
> FusedIterator
for Inspect
<I
, F
>
2160 where F
: FnMut(&I
::Item
) {}