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.
14 use super::{AlwaysOk, LoopState};
15 use super::{Chain, Cycle, Cloned, Enumerate, Filter, FilterMap, FlatMap, Fuse};
16 use super::{Inspect, Map, Peekable, Scan, Skip, SkipWhile, StepBy, Take, TakeWhile, Rev};
17 use super::{Zip, Sum, Product};
18 use super::{ChainState, FromIterator, ZipImpl};
20 fn _assert_is_object_safe(_: &Iterator<Item=()>) {}
22 /// An interface for dealing with iterators.
24 /// This is the main iterator trait. For more about the concept of iterators
25 /// generally, please see the [module-level documentation]. In particular, you
26 /// may want to know how to [implement `Iterator`][impl].
28 /// [module-level documentation]: index.html
29 /// [impl]: index.html#implementing-iterator
30 #[stable(feature = "rust1", since = "1.0.0")]
31 #[rustc_on_unimplemented(
34 label="`{Self}` is not an iterator; try calling `.chars()` or `.bytes()`"
36 label="`{Self}` is not an iterator; maybe try calling `.iter()` or a similar method"
40 /// The type of the elements being iterated over.
41 #[stable(feature = "rust1", since = "1.0.0")]
44 /// Advances the iterator and returns the next value.
46 /// Returns [`None`] when iteration is finished. Individual iterator
47 /// implementations may choose to resume iteration, and so calling `next()`
48 /// again may or may not eventually start returning [`Some(Item)`] again at some
51 /// [`None`]: ../../std/option/enum.Option.html#variant.None
52 /// [`Some(Item)`]: ../../std/option/enum.Option.html#variant.Some
59 /// let a = [1, 2, 3];
61 /// let mut iter = a.iter();
63 /// // A call to next() returns the next value...
64 /// assert_eq!(Some(&1), iter.next());
65 /// assert_eq!(Some(&2), iter.next());
66 /// assert_eq!(Some(&3), iter.next());
68 /// // ... and then None once it's over.
69 /// assert_eq!(None, iter.next());
71 /// // More calls may or may not return None. Here, they always will.
72 /// assert_eq!(None, iter.next());
73 /// assert_eq!(None, iter.next());
75 #[stable(feature = "rust1", since = "1.0.0")]
76 fn next(&mut self) -> Option<Self::Item>;
78 /// Returns the bounds on the remaining length of the iterator.
80 /// Specifically, `size_hint()` returns a tuple where the first element
81 /// is the lower bound, and the second element is the upper bound.
83 /// The second half of the tuple that is returned is an [`Option`]`<`[`usize`]`>`.
84 /// A [`None`] here means that either there is no known upper bound, or the
85 /// upper bound is larger than [`usize`].
87 /// # Implementation notes
89 /// It is not enforced that an iterator implementation yields the declared
90 /// number of elements. A buggy iterator may yield less than the lower bound
91 /// or more than the upper bound of elements.
93 /// `size_hint()` is primarily intended to be used for optimizations such as
94 /// reserving space for the elements of the iterator, but must not be
95 /// trusted to e.g. omit bounds checks in unsafe code. An incorrect
96 /// implementation of `size_hint()` should not lead to memory safety
99 /// That said, the implementation should provide a correct estimation,
100 /// because otherwise it would be a violation of the trait's protocol.
102 /// The default implementation returns `(0, None)` which is correct for any
105 /// [`usize`]: ../../std/primitive.usize.html
106 /// [`Option`]: ../../std/option/enum.Option.html
107 /// [`None`]: ../../std/option/enum.Option.html#variant.None
114 /// let a = [1, 2, 3];
115 /// let iter = a.iter();
117 /// assert_eq!((3, Some(3)), iter.size_hint());
120 /// A more complex example:
123 /// // The even numbers from zero to ten.
124 /// let iter = (0..10).filter(|x| x % 2 == 0);
126 /// // We might iterate from zero to ten times. Knowing that it's five
127 /// // exactly wouldn't be possible without executing filter().
128 /// assert_eq!((0, Some(10)), iter.size_hint());
130 /// // Let's add five more numbers with chain()
131 /// let iter = (0..10).filter(|x| x % 2 == 0).chain(15..20);
133 /// // now both bounds are increased by five
134 /// assert_eq!((5, Some(15)), iter.size_hint());
137 /// Returning `None` for an upper bound:
140 /// // an infinite iterator has no upper bound
141 /// // and the maximum possible lower bound
144 /// assert_eq!((usize::max_value(), None), iter.size_hint());
147 #[stable(feature = "rust1", since = "1.0.0")]
148 fn size_hint(&self) -> (usize, Option<usize>) { (0, None) }
150 /// Consumes the iterator, counting the number of iterations and returning it.
152 /// This method will evaluate the iterator until its [`next`] returns
153 /// [`None`]. Once [`None`] is encountered, `count()` returns the number of
154 /// times it called [`next`].
156 /// [`next`]: #tymethod.next
157 /// [`None`]: ../../std/option/enum.Option.html#variant.None
159 /// # Overflow Behavior
161 /// The method does no guarding against overflows, so counting elements of
162 /// an iterator with more than [`usize::MAX`] elements either produces the
163 /// wrong result or panics. If debug assertions are enabled, a panic is
168 /// This function might panic if the iterator has more than [`usize::MAX`]
171 /// [`usize::MAX`]: ../../std/isize/constant.MAX.html
178 /// let a = [1, 2, 3];
179 /// assert_eq!(a.iter().count(), 3);
181 /// let a = [1, 2, 3, 4, 5];
182 /// assert_eq!(a.iter().count(), 5);
185 #[rustc_inherit_overflow_checks]
186 #[stable(feature = "rust1", since = "1.0.0")]
187 fn count(self) -> usize where Self: Sized {
189 self.fold(0, |cnt, _| cnt + 1)
192 /// Consumes the iterator, returning the last element.
194 /// This method will evaluate the iterator until it returns [`None`]. While
195 /// doing so, it keeps track of the current element. After [`None`] is
196 /// returned, `last()` will then return the last element it saw.
198 /// [`None`]: ../../std/option/enum.Option.html#variant.None
205 /// let a = [1, 2, 3];
206 /// assert_eq!(a.iter().last(), Some(&3));
208 /// let a = [1, 2, 3, 4, 5];
209 /// assert_eq!(a.iter().last(), Some(&5));
212 #[stable(feature = "rust1", since = "1.0.0")]
213 fn last(self) -> Option<Self::Item> where Self: Sized {
215 for x in self { last = Some(x); }
219 /// Returns the `n`th element of the iterator.
221 /// Like most indexing operations, the count starts from zero, so `nth(0)`
222 /// returns the first value, `nth(1)` the second, and so on.
224 /// Note that all preceding elements, as well as the returned element, will be
225 /// consumed from the iterator. That means that the preceding elements will be
226 /// discarded, and also that calling `nth(0)` multiple times on the same iterator
227 /// will return different elements.
229 /// `nth()` will return [`None`] if `n` is greater than or equal to the length of the
232 /// [`None`]: ../../std/option/enum.Option.html#variant.None
239 /// let a = [1, 2, 3];
240 /// assert_eq!(a.iter().nth(1), Some(&2));
243 /// Calling `nth()` multiple times doesn't rewind the iterator:
246 /// let a = [1, 2, 3];
248 /// let mut iter = a.iter();
250 /// assert_eq!(iter.nth(1), Some(&2));
251 /// assert_eq!(iter.nth(1), None);
254 /// Returning `None` if there are less than `n + 1` elements:
257 /// let a = [1, 2, 3];
258 /// assert_eq!(a.iter().nth(10), None);
261 #[stable(feature = "rust1", since = "1.0.0")]
262 fn nth(&mut self, mut n: usize) -> Option<Self::Item> {
264 if n == 0 { return Some(x) }
270 /// Creates an iterator starting at the same point, but stepping by
271 /// the given amount at each iteration.
273 /// Note that it will always return the first element of the iterator,
274 /// regardless of the step given.
278 /// The method will panic if the given step is `0`.
285 /// #![feature(iterator_step_by)]
286 /// let a = [0, 1, 2, 3, 4, 5];
287 /// let mut iter = a.into_iter().step_by(2);
289 /// assert_eq!(iter.next(), Some(&0));
290 /// assert_eq!(iter.next(), Some(&2));
291 /// assert_eq!(iter.next(), Some(&4));
292 /// assert_eq!(iter.next(), None);
295 #[unstable(feature = "iterator_step_by",
296 reason = "unstable replacement of Range::step_by",
298 fn step_by(self, step: usize) -> StepBy<Self> where Self: Sized {
300 StepBy{iter: self, step: step - 1, first_take: true}
303 /// Takes two iterators and creates a new iterator over both in sequence.
305 /// `chain()` will return a new iterator which will first iterate over
306 /// values from the first iterator and then over values from the second
309 /// In other words, it links two iterators together, in a chain. 🔗
316 /// let a1 = [1, 2, 3];
317 /// let a2 = [4, 5, 6];
319 /// let mut iter = a1.iter().chain(a2.iter());
321 /// assert_eq!(iter.next(), Some(&1));
322 /// assert_eq!(iter.next(), Some(&2));
323 /// assert_eq!(iter.next(), Some(&3));
324 /// assert_eq!(iter.next(), Some(&4));
325 /// assert_eq!(iter.next(), Some(&5));
326 /// assert_eq!(iter.next(), Some(&6));
327 /// assert_eq!(iter.next(), None);
330 /// Since the argument to `chain()` uses [`IntoIterator`], we can pass
331 /// anything that can be converted into an [`Iterator`], not just an
332 /// [`Iterator`] itself. For example, slices (`&[T]`) implement
333 /// [`IntoIterator`], and so can be passed to `chain()` directly:
335 /// [`IntoIterator`]: trait.IntoIterator.html
336 /// [`Iterator`]: trait.Iterator.html
339 /// let s1 = &[1, 2, 3];
340 /// let s2 = &[4, 5, 6];
342 /// let mut iter = s1.iter().chain(s2);
344 /// assert_eq!(iter.next(), Some(&1));
345 /// assert_eq!(iter.next(), Some(&2));
346 /// assert_eq!(iter.next(), Some(&3));
347 /// assert_eq!(iter.next(), Some(&4));
348 /// assert_eq!(iter.next(), Some(&5));
349 /// assert_eq!(iter.next(), Some(&6));
350 /// assert_eq!(iter.next(), None);
353 #[stable(feature = "rust1", since = "1.0.0")]
354 fn chain<U>(self, other: U) -> Chain<Self, U::IntoIter> where
355 Self: Sized, U: IntoIterator<Item=Self::Item>,
357 Chain{a: self, b: other.into_iter(), state: ChainState::Both}
360 /// 'Zips up' two iterators into a single iterator of pairs.
362 /// `zip()` returns a new iterator that will iterate over two other
363 /// iterators, returning a tuple where the first element comes from the
364 /// first iterator, and the second element comes from the second iterator.
366 /// In other words, it zips two iterators together, into a single one.
368 /// When either iterator returns [`None`], all further calls to [`next`]
369 /// will return [`None`].
376 /// let a1 = [1, 2, 3];
377 /// let a2 = [4, 5, 6];
379 /// let mut iter = a1.iter().zip(a2.iter());
381 /// assert_eq!(iter.next(), Some((&1, &4)));
382 /// assert_eq!(iter.next(), Some((&2, &5)));
383 /// assert_eq!(iter.next(), Some((&3, &6)));
384 /// assert_eq!(iter.next(), None);
387 /// Since the argument to `zip()` uses [`IntoIterator`], we can pass
388 /// anything that can be converted into an [`Iterator`], not just an
389 /// [`Iterator`] itself. For example, slices (`&[T]`) implement
390 /// [`IntoIterator`], and so can be passed to `zip()` directly:
392 /// [`IntoIterator`]: trait.IntoIterator.html
393 /// [`Iterator`]: trait.Iterator.html
396 /// let s1 = &[1, 2, 3];
397 /// let s2 = &[4, 5, 6];
399 /// let mut iter = s1.iter().zip(s2);
401 /// assert_eq!(iter.next(), Some((&1, &4)));
402 /// assert_eq!(iter.next(), Some((&2, &5)));
403 /// assert_eq!(iter.next(), Some((&3, &6)));
404 /// assert_eq!(iter.next(), None);
407 /// `zip()` is often used to zip an infinite iterator to a finite one.
408 /// This works because the finite iterator will eventually return [`None`],
409 /// ending the zipper. Zipping with `(0..)` can look a lot like [`enumerate`]:
412 /// let enumerate: Vec<_> = "foo".chars().enumerate().collect();
414 /// let zipper: Vec<_> = (0..).zip("foo".chars()).collect();
416 /// assert_eq!((0, 'f'), enumerate[0]);
417 /// assert_eq!((0, 'f'), zipper[0]);
419 /// assert_eq!((1, 'o'), enumerate[1]);
420 /// assert_eq!((1, 'o'), zipper[1]);
422 /// assert_eq!((2, 'o'), enumerate[2]);
423 /// assert_eq!((2, 'o'), zipper[2]);
426 /// [`enumerate`]: trait.Iterator.html#method.enumerate
427 /// [`next`]: ../../std/iter/trait.Iterator.html#tymethod.next
428 /// [`None`]: ../../std/option/enum.Option.html#variant.None
430 #[stable(feature = "rust1", since = "1.0.0")]
431 fn zip<U>(self, other: U) -> Zip<Self, U::IntoIter> where
432 Self: Sized, U: IntoIterator
434 Zip::new(self, other.into_iter())
437 /// Takes a closure and creates an iterator which calls that closure on each
440 /// `map()` transforms one iterator into another, by means of its argument:
441 /// something that implements `FnMut`. It produces a new iterator which
442 /// calls this closure on each element of the original iterator.
444 /// If you are good at thinking in types, you can think of `map()` like this:
445 /// If you have an iterator that gives you elements of some type `A`, and
446 /// you want an iterator of some other type `B`, you can use `map()`,
447 /// passing a closure that takes an `A` and returns a `B`.
449 /// `map()` is conceptually similar to a [`for`] loop. However, as `map()` is
450 /// lazy, it is best used when you're already working with other iterators.
451 /// If you're doing some sort of looping for a side effect, it's considered
452 /// more idiomatic to use [`for`] than `map()`.
454 /// [`for`]: ../../book/first-edition/loops.html#for
461 /// let a = [1, 2, 3];
463 /// let mut iter = a.into_iter().map(|x| 2 * x);
465 /// assert_eq!(iter.next(), Some(2));
466 /// assert_eq!(iter.next(), Some(4));
467 /// assert_eq!(iter.next(), Some(6));
468 /// assert_eq!(iter.next(), None);
471 /// If you're doing some sort of side effect, prefer [`for`] to `map()`:
474 /// # #![allow(unused_must_use)]
475 /// // don't do this:
476 /// (0..5).map(|x| println!("{}", x));
478 /// // it won't even execute, as it is lazy. Rust will warn you about this.
480 /// // Instead, use for:
482 /// println!("{}", x);
486 #[stable(feature = "rust1", since = "1.0.0")]
487 fn map<B, F>(self, f: F) -> Map<Self, F> where
488 Self: Sized, F: FnMut(Self::Item) -> B,
490 Map{iter: self, f: f}
493 /// Calls a closure on each element of an iterator.
495 /// This is equivalent to using a [`for`] loop on the iterator, although
496 /// `break` and `continue` are not possible from a closure. It's generally
497 /// more idiomatic to use a `for` loop, but `for_each` may be more legible
498 /// when processing items at the end of longer iterator chains. In some
499 /// cases `for_each` may also be faster than a loop, because it will use
500 /// internal iteration on adaptors like `Chain`.
502 /// [`for`]: ../../book/first-edition/loops.html#for
509 /// use std::sync::mpsc::channel;
511 /// let (tx, rx) = channel();
512 /// (0..5).map(|x| x * 2 + 1)
513 /// .for_each(move |x| tx.send(x).unwrap());
515 /// let v: Vec<_> = rx.iter().collect();
516 /// assert_eq!(v, vec![1, 3, 5, 7, 9]);
519 /// For such a small example, a `for` loop may be cleaner, but `for_each`
520 /// might be preferable to keep a functional style with longer iterators:
523 /// (0..5).flat_map(|x| x * 100 .. x * 110)
525 /// .filter(|&(i, x)| (i + x) % 3 == 0)
526 /// .for_each(|(i, x)| println!("{}:{}", i, x));
529 #[stable(feature = "iterator_for_each", since = "1.21.0")]
530 fn for_each<F>(self, mut f: F) where
531 Self: Sized, F: FnMut(Self::Item),
533 self.fold((), move |(), item| f(item));
536 /// Creates an iterator which uses a closure to determine if an element
537 /// should be yielded.
539 /// The closure must return `true` or `false`. `filter()` creates an
540 /// iterator which calls this closure on each element. If the closure
541 /// returns `true`, then the element is returned. If the closure returns
542 /// `false`, it will try again, and call the closure on the next element,
543 /// seeing if it passes the test.
550 /// let a = [0i32, 1, 2];
552 /// let mut iter = a.into_iter().filter(|x| x.is_positive());
554 /// assert_eq!(iter.next(), Some(&1));
555 /// assert_eq!(iter.next(), Some(&2));
556 /// assert_eq!(iter.next(), None);
559 /// Because the closure passed to `filter()` takes a reference, and many
560 /// iterators iterate over references, this leads to a possibly confusing
561 /// situation, where the type of the closure is a double reference:
564 /// let a = [0, 1, 2];
566 /// let mut iter = a.into_iter().filter(|x| **x > 1); // need two *s!
568 /// assert_eq!(iter.next(), Some(&2));
569 /// assert_eq!(iter.next(), None);
572 /// It's common to instead use destructuring on the argument to strip away
576 /// let a = [0, 1, 2];
578 /// let mut iter = a.into_iter().filter(|&x| *x > 1); // both & and *
580 /// assert_eq!(iter.next(), Some(&2));
581 /// assert_eq!(iter.next(), None);
587 /// let a = [0, 1, 2];
589 /// let mut iter = a.into_iter().filter(|&&x| x > 1); // two &s
591 /// assert_eq!(iter.next(), Some(&2));
592 /// assert_eq!(iter.next(), None);
597 #[stable(feature = "rust1", since = "1.0.0")]
598 fn filter<P>(self, predicate: P) -> Filter<Self, P> where
599 Self: Sized, P: FnMut(&Self::Item) -> bool,
601 Filter{iter: self, predicate: predicate}
604 /// Creates an iterator that both filters and maps.
606 /// The closure must return an [`Option<T>`]. `filter_map` creates an
607 /// iterator which calls this closure on each element. If the closure
608 /// returns [`Some(element)`][`Some`], then that element is returned. If the
609 /// closure returns [`None`], it will try again, and call the closure on the
610 /// next element, seeing if it will return [`Some`].
612 /// Why `filter_map` and not just [`filter`] and [`map`]? The key is in this
615 /// [`filter`]: #method.filter
616 /// [`map`]: #method.map
618 /// > If the closure returns [`Some(element)`][`Some`], then that element is returned.
620 /// In other words, it removes the [`Option<T>`] layer automatically. If your
621 /// mapping is already returning an [`Option<T>`] and you want to skip over
622 /// [`None`]s, then `filter_map` is much, much nicer to use.
629 /// let a = ["1", "lol", "3", "NaN", "5"];
631 /// let mut iter = a.iter().filter_map(|s| s.parse().ok());
633 /// assert_eq!(iter.next(), Some(1));
634 /// assert_eq!(iter.next(), Some(3));
635 /// assert_eq!(iter.next(), Some(5));
636 /// assert_eq!(iter.next(), None);
639 /// Here's the same example, but with [`filter`] and [`map`]:
642 /// let a = ["1", "lol", "3", "NaN", "5"];
643 /// let mut iter = a.iter().map(|s| s.parse()).filter(|s| s.is_ok()).map(|s| s.unwrap());
644 /// assert_eq!(iter.next(), Some(1));
645 /// assert_eq!(iter.next(), Some(3));
646 /// assert_eq!(iter.next(), Some(5));
647 /// assert_eq!(iter.next(), None);
650 /// [`Option<T>`]: ../../std/option/enum.Option.html
651 /// [`Some`]: ../../std/option/enum.Option.html#variant.Some
652 /// [`None`]: ../../std/option/enum.Option.html#variant.None
654 #[stable(feature = "rust1", since = "1.0.0")]
655 fn filter_map<B, F>(self, f: F) -> FilterMap<Self, F> where
656 Self: Sized, F: FnMut(Self::Item) -> Option<B>,
658 FilterMap { iter: self, f: f }
661 /// Creates an iterator which gives the current iteration count as well as
664 /// The iterator returned yields pairs `(i, val)`, where `i` is the
665 /// current index of iteration and `val` is the value returned by the
668 /// `enumerate()` keeps its count as a [`usize`]. If you want to count by a
669 /// different sized integer, the [`zip`] function provides similar
672 /// # Overflow Behavior
674 /// The method does no guarding against overflows, so enumerating more than
675 /// [`usize::MAX`] elements either produces the wrong result or panics. If
676 /// debug assertions are enabled, a panic is guaranteed.
680 /// The returned iterator might panic if the to-be-returned index would
681 /// overflow a [`usize`].
683 /// [`usize::MAX`]: ../../std/usize/constant.MAX.html
684 /// [`usize`]: ../../std/primitive.usize.html
685 /// [`zip`]: #method.zip
690 /// let a = ['a', 'b', 'c'];
692 /// let mut iter = a.iter().enumerate();
694 /// assert_eq!(iter.next(), Some((0, &'a')));
695 /// assert_eq!(iter.next(), Some((1, &'b')));
696 /// assert_eq!(iter.next(), Some((2, &'c')));
697 /// assert_eq!(iter.next(), None);
700 #[stable(feature = "rust1", since = "1.0.0")]
701 fn enumerate(self) -> Enumerate<Self> where Self: Sized {
702 Enumerate { iter: self, count: 0 }
705 /// Creates an iterator which can use `peek` to look at the next element of
706 /// the iterator without consuming it.
708 /// Adds a [`peek`] method to an iterator. See its documentation for
709 /// more information.
711 /// Note that the underlying iterator is still advanced when [`peek`] is
712 /// called for the first time: In order to retrieve the next element,
713 /// [`next`] is called on the underlying iterator, hence any side effects (i.e.
714 /// anything other than fetching the next value) of the [`next`] method
717 /// [`peek`]: struct.Peekable.html#method.peek
718 /// [`next`]: ../../std/iter/trait.Iterator.html#tymethod.next
725 /// let xs = [1, 2, 3];
727 /// let mut iter = xs.iter().peekable();
729 /// // peek() lets us see into the future
730 /// assert_eq!(iter.peek(), Some(&&1));
731 /// assert_eq!(iter.next(), Some(&1));
733 /// assert_eq!(iter.next(), Some(&2));
735 /// // we can peek() multiple times, the iterator won't advance
736 /// assert_eq!(iter.peek(), Some(&&3));
737 /// assert_eq!(iter.peek(), Some(&&3));
739 /// assert_eq!(iter.next(), Some(&3));
741 /// // after the iterator is finished, so is peek()
742 /// assert_eq!(iter.peek(), None);
743 /// assert_eq!(iter.next(), None);
746 #[stable(feature = "rust1", since = "1.0.0")]
747 fn peekable(self) -> Peekable<Self> where Self: Sized {
748 Peekable{iter: self, peeked: None}
751 /// Creates an iterator that [`skip`]s elements based on a predicate.
753 /// [`skip`]: #method.skip
755 /// `skip_while()` takes a closure as an argument. It will call this
756 /// closure on each element of the iterator, and ignore elements
757 /// until it returns `false`.
759 /// After `false` is returned, `skip_while()`'s job is over, and the
760 /// rest of the elements are yielded.
767 /// let a = [-1i32, 0, 1];
769 /// let mut iter = a.into_iter().skip_while(|x| x.is_negative());
771 /// assert_eq!(iter.next(), Some(&0));
772 /// assert_eq!(iter.next(), Some(&1));
773 /// assert_eq!(iter.next(), None);
776 /// Because the closure passed to `skip_while()` takes a reference, and many
777 /// iterators iterate over references, this leads to a possibly confusing
778 /// situation, where the type of the closure is a double reference:
781 /// let a = [-1, 0, 1];
783 /// let mut iter = a.into_iter().skip_while(|x| **x < 0); // need two *s!
785 /// assert_eq!(iter.next(), Some(&0));
786 /// assert_eq!(iter.next(), Some(&1));
787 /// assert_eq!(iter.next(), None);
790 /// Stopping after an initial `false`:
793 /// let a = [-1, 0, 1, -2];
795 /// let mut iter = a.into_iter().skip_while(|x| **x < 0);
797 /// assert_eq!(iter.next(), Some(&0));
798 /// assert_eq!(iter.next(), Some(&1));
800 /// // while this would have been false, since we already got a false,
801 /// // skip_while() isn't used any more
802 /// assert_eq!(iter.next(), Some(&-2));
804 /// assert_eq!(iter.next(), None);
807 #[stable(feature = "rust1", since = "1.0.0")]
808 fn skip_while<P>(self, predicate: P) -> SkipWhile<Self, P> where
809 Self: Sized, P: FnMut(&Self::Item) -> bool,
811 SkipWhile{iter: self, flag: false, predicate: predicate}
814 /// Creates an iterator that yields elements based on a predicate.
816 /// `take_while()` takes a closure as an argument. It will call this
817 /// closure on each element of the iterator, and yield elements
818 /// while it returns `true`.
820 /// After `false` is returned, `take_while()`'s job is over, and the
821 /// rest of the elements are ignored.
828 /// let a = [-1i32, 0, 1];
830 /// let mut iter = a.into_iter().take_while(|x| x.is_negative());
832 /// assert_eq!(iter.next(), Some(&-1));
833 /// assert_eq!(iter.next(), None);
836 /// Because the closure passed to `take_while()` takes a reference, and many
837 /// iterators iterate over references, this leads to a possibly confusing
838 /// situation, where the type of the closure is a double reference:
841 /// let a = [-1, 0, 1];
843 /// let mut iter = a.into_iter().take_while(|x| **x < 0); // need two *s!
845 /// assert_eq!(iter.next(), Some(&-1));
846 /// assert_eq!(iter.next(), None);
849 /// Stopping after an initial `false`:
852 /// let a = [-1, 0, 1, -2];
854 /// let mut iter = a.into_iter().take_while(|x| **x < 0);
856 /// assert_eq!(iter.next(), Some(&-1));
858 /// // We have more elements that are less than zero, but since we already
859 /// // got a false, take_while() isn't used any more
860 /// assert_eq!(iter.next(), None);
863 /// Because `take_while()` needs to look at the value in order to see if it
864 /// should be included or not, consuming iterators will see that it is
868 /// let a = [1, 2, 3, 4];
869 /// let mut iter = a.into_iter();
871 /// let result: Vec<i32> = iter.by_ref()
872 /// .take_while(|n| **n != 3)
876 /// assert_eq!(result, &[1, 2]);
878 /// let result: Vec<i32> = iter.cloned().collect();
880 /// assert_eq!(result, &[4]);
883 /// The `3` is no longer there, because it was consumed in order to see if
884 /// the iteration should stop, but wasn't placed back into the iterator or
885 /// some similar thing.
887 #[stable(feature = "rust1", since = "1.0.0")]
888 fn take_while<P>(self, predicate: P) -> TakeWhile<Self, P> where
889 Self: Sized, P: FnMut(&Self::Item) -> bool,
891 TakeWhile{iter: self, flag: false, predicate: predicate}
894 /// Creates an iterator that skips the first `n` elements.
896 /// After they have been consumed, the rest of the elements are yielded.
903 /// let a = [1, 2, 3];
905 /// let mut iter = a.iter().skip(2);
907 /// assert_eq!(iter.next(), Some(&3));
908 /// assert_eq!(iter.next(), None);
911 #[stable(feature = "rust1", since = "1.0.0")]
912 fn skip(self, n: usize) -> Skip<Self> where Self: Sized {
913 Skip{iter: self, n: n}
916 /// Creates an iterator that yields its first `n` elements.
923 /// let a = [1, 2, 3];
925 /// let mut iter = a.iter().take(2);
927 /// assert_eq!(iter.next(), Some(&1));
928 /// assert_eq!(iter.next(), Some(&2));
929 /// assert_eq!(iter.next(), None);
932 /// `take()` is often used with an infinite iterator, to make it finite:
935 /// let mut iter = (0..).take(3);
937 /// assert_eq!(iter.next(), Some(0));
938 /// assert_eq!(iter.next(), Some(1));
939 /// assert_eq!(iter.next(), Some(2));
940 /// assert_eq!(iter.next(), None);
943 #[stable(feature = "rust1", since = "1.0.0")]
944 fn take(self, n: usize) -> Take<Self> where Self: Sized, {
945 Take{iter: self, n: n}
948 /// An iterator adaptor similar to [`fold`] that holds internal state and
949 /// produces a new iterator.
951 /// [`fold`]: #method.fold
953 /// `scan()` takes two arguments: an initial value which seeds the internal
954 /// state, and a closure with two arguments, the first being a mutable
955 /// reference to the internal state and the second an iterator element.
956 /// The closure can assign to the internal state to share state between
959 /// On iteration, the closure will be applied to each element of the
960 /// iterator and the return value from the closure, an [`Option`], is
961 /// yielded by the iterator.
963 /// [`Option`]: ../../std/option/enum.Option.html
970 /// let a = [1, 2, 3];
972 /// let mut iter = a.iter().scan(1, |state, &x| {
973 /// // each iteration, we'll multiply the state by the element
974 /// *state = *state * x;
976 /// // the value passed on to the next iteration
980 /// assert_eq!(iter.next(), Some(1));
981 /// assert_eq!(iter.next(), Some(2));
982 /// assert_eq!(iter.next(), Some(6));
983 /// assert_eq!(iter.next(), None);
986 #[stable(feature = "rust1", since = "1.0.0")]
987 fn scan<St, B, F>(self, initial_state: St, f: F) -> Scan<Self, St, F>
988 where Self: Sized, F: FnMut(&mut St, Self::Item) -> Option<B>,
990 Scan{iter: self, f: f, state: initial_state}
993 /// Creates an iterator that works like map, but flattens nested structure.
995 /// The [`map`] adapter is very useful, but only when the closure
996 /// argument produces values. If it produces an iterator instead, there's
997 /// an extra layer of indirection. `flat_map()` will remove this extra layer
1000 /// Another way of thinking about `flat_map()`: [`map`]'s closure returns
1001 /// one item for each element, and `flat_map()`'s closure returns an
1002 /// iterator for each element.
1004 /// [`map`]: #method.map
1011 /// let words = ["alpha", "beta", "gamma"];
1013 /// // chars() returns an iterator
1014 /// let merged: String = words.iter()
1015 /// .flat_map(|s| s.chars())
1017 /// assert_eq!(merged, "alphabetagamma");
1020 #[stable(feature = "rust1", since = "1.0.0")]
1021 fn flat_map<U, F>(self, f: F) -> FlatMap<Self, U, F>
1022 where Self: Sized, U: IntoIterator, F: FnMut(Self::Item) -> U,
1024 FlatMap{iter: self, f: f, frontiter: None, backiter: None }
1027 /// Creates an iterator which ends after the first [`None`].
1029 /// After an iterator returns [`None`], future calls may or may not yield
1030 /// [`Some(T)`] again. `fuse()` adapts an iterator, ensuring that after a
1031 /// [`None`] is given, it will always return [`None`] forever.
1033 /// [`None`]: ../../std/option/enum.Option.html#variant.None
1034 /// [`Some(T)`]: ../../std/option/enum.Option.html#variant.Some
1041 /// // an iterator which alternates between Some and None
1042 /// struct Alternate {
1046 /// impl Iterator for Alternate {
1047 /// type Item = i32;
1049 /// fn next(&mut self) -> Option<i32> {
1050 /// let val = self.state;
1051 /// self.state = self.state + 1;
1053 /// // if it's even, Some(i32), else None
1054 /// if val % 2 == 0 {
1062 /// let mut iter = Alternate { state: 0 };
1064 /// // we can see our iterator going back and forth
1065 /// assert_eq!(iter.next(), Some(0));
1066 /// assert_eq!(iter.next(), None);
1067 /// assert_eq!(iter.next(), Some(2));
1068 /// assert_eq!(iter.next(), None);
1070 /// // however, once we fuse it...
1071 /// let mut iter = iter.fuse();
1073 /// assert_eq!(iter.next(), Some(4));
1074 /// assert_eq!(iter.next(), None);
1076 /// // it will always return None after the first time.
1077 /// assert_eq!(iter.next(), None);
1078 /// assert_eq!(iter.next(), None);
1079 /// assert_eq!(iter.next(), None);
1082 #[stable(feature = "rust1", since = "1.0.0")]
1083 fn fuse(self) -> Fuse<Self> where Self: Sized {
1084 Fuse{iter: self, done: false}
1087 /// Do something with each element of an iterator, passing the value on.
1089 /// When using iterators, you'll often chain several of them together.
1090 /// While working on such code, you might want to check out what's
1091 /// happening at various parts in the pipeline. To do that, insert
1092 /// a call to `inspect()`.
1094 /// It's much more common for `inspect()` to be used as a debugging tool
1095 /// than to exist in your final code, but never say never.
1102 /// let a = [1, 4, 2, 3];
1104 /// // this iterator sequence is complex.
1105 /// let sum = a.iter()
1107 /// .filter(|&x| x % 2 == 0)
1108 /// .fold(0, |sum, i| sum + i);
1110 /// println!("{}", sum);
1112 /// // let's add some inspect() calls to investigate what's happening
1113 /// let sum = a.iter()
1115 /// .inspect(|x| println!("about to filter: {}", x))
1116 /// .filter(|&x| x % 2 == 0)
1117 /// .inspect(|x| println!("made it through filter: {}", x))
1118 /// .fold(0, |sum, i| sum + i);
1120 /// println!("{}", sum);
1123 /// This will print:
1126 /// about to filter: 1
1127 /// about to filter: 4
1128 /// made it through filter: 4
1129 /// about to filter: 2
1130 /// made it through filter: 2
1131 /// about to filter: 3
1135 #[stable(feature = "rust1", since = "1.0.0")]
1136 fn inspect<F>(self, f: F) -> Inspect<Self, F> where
1137 Self: Sized, F: FnMut(&Self::Item),
1139 Inspect{iter: self, f: f}
1142 /// Borrows an iterator, rather than consuming it.
1144 /// This is useful to allow applying iterator adaptors while still
1145 /// retaining ownership of the original iterator.
1152 /// let a = [1, 2, 3];
1154 /// let iter = a.into_iter();
1156 /// let sum: i32 = iter.take(5)
1157 /// .fold(0, |acc, &i| acc + i );
1159 /// assert_eq!(sum, 6);
1161 /// // if we try to use iter again, it won't work. The following line
1162 /// // gives "error: use of moved value: `iter`
1163 /// // assert_eq!(iter.next(), None);
1165 /// // let's try that again
1166 /// let a = [1, 2, 3];
1168 /// let mut iter = a.into_iter();
1170 /// // instead, we add in a .by_ref()
1171 /// let sum: i32 = iter.by_ref()
1173 /// .fold(0, |acc, &i| acc + i );
1175 /// assert_eq!(sum, 3);
1177 /// // now this is just fine:
1178 /// assert_eq!(iter.next(), Some(&3));
1179 /// assert_eq!(iter.next(), None);
1181 #[stable(feature = "rust1", since = "1.0.0")]
1182 fn by_ref(&mut self) -> &mut Self where Self: Sized { self }
1184 /// Transforms an iterator into a collection.
1186 /// `collect()` can take anything iterable, and turn it into a relevant
1187 /// collection. This is one of the more powerful methods in the standard
1188 /// library, used in a variety of contexts.
1190 /// The most basic pattern in which `collect()` is used is to turn one
1191 /// collection into another. You take a collection, call [`iter`] on it,
1192 /// do a bunch of transformations, and then `collect()` at the end.
1194 /// One of the keys to `collect()`'s power is that many things you might
1195 /// not think of as 'collections' actually are. For example, a [`String`]
1196 /// is a collection of [`char`]s. And a collection of
1197 /// [`Result<T, E>`][`Result`] can be thought of as single
1198 /// [`Result`]`<Collection<T>, E>`. See the examples below for more.
1200 /// Because `collect()` is so general, it can cause problems with type
1201 /// inference. As such, `collect()` is one of the few times you'll see
1202 /// the syntax affectionately known as the 'turbofish': `::<>`. This
1203 /// helps the inference algorithm understand specifically which collection
1204 /// you're trying to collect into.
1211 /// let a = [1, 2, 3];
1213 /// let doubled: Vec<i32> = a.iter()
1214 /// .map(|&x| x * 2)
1217 /// assert_eq!(vec![2, 4, 6], doubled);
1220 /// Note that we needed the `: Vec<i32>` on the left-hand side. This is because
1221 /// we could collect into, for example, a [`VecDeque<T>`] instead:
1223 /// [`VecDeque<T>`]: ../../std/collections/struct.VecDeque.html
1226 /// use std::collections::VecDeque;
1228 /// let a = [1, 2, 3];
1230 /// let doubled: VecDeque<i32> = a.iter()
1231 /// .map(|&x| x * 2)
1234 /// assert_eq!(2, doubled[0]);
1235 /// assert_eq!(4, doubled[1]);
1236 /// assert_eq!(6, doubled[2]);
1239 /// Using the 'turbofish' instead of annotating `doubled`:
1242 /// let a = [1, 2, 3];
1244 /// let doubled = a.iter()
1245 /// .map(|&x| x * 2)
1246 /// .collect::<Vec<i32>>();
1248 /// assert_eq!(vec![2, 4, 6], doubled);
1251 /// Because `collect()` only cares about what you're collecting into, you can
1252 /// still use a partial type hint, `_`, with the turbofish:
1255 /// let a = [1, 2, 3];
1257 /// let doubled = a.iter()
1258 /// .map(|&x| x * 2)
1259 /// .collect::<Vec<_>>();
1261 /// assert_eq!(vec![2, 4, 6], doubled);
1264 /// Using `collect()` to make a [`String`]:
1267 /// let chars = ['g', 'd', 'k', 'k', 'n'];
1269 /// let hello: String = chars.iter()
1270 /// .map(|&x| x as u8)
1271 /// .map(|x| (x + 1) as char)
1274 /// assert_eq!("hello", hello);
1277 /// If you have a list of [`Result<T, E>`][`Result`]s, you can use `collect()` to
1278 /// see if any of them failed:
1281 /// let results = [Ok(1), Err("nope"), Ok(3), Err("bad")];
1283 /// let result: Result<Vec<_>, &str> = results.iter().cloned().collect();
1285 /// // gives us the first error
1286 /// assert_eq!(Err("nope"), result);
1288 /// let results = [Ok(1), Ok(3)];
1290 /// let result: Result<Vec<_>, &str> = results.iter().cloned().collect();
1292 /// // gives us the list of answers
1293 /// assert_eq!(Ok(vec![1, 3]), result);
1296 /// [`iter`]: ../../std/iter/trait.Iterator.html#tymethod.next
1297 /// [`String`]: ../../std/string/struct.String.html
1298 /// [`char`]: ../../std/primitive.char.html
1299 /// [`Result`]: ../../std/result/enum.Result.html
1301 #[stable(feature = "rust1", since = "1.0.0")]
1302 fn collect<B: FromIterator<Self::Item>>(self) -> B where Self: Sized {
1303 FromIterator::from_iter(self)
1306 /// Consumes an iterator, creating two collections from it.
1308 /// The predicate passed to `partition()` can return `true`, or `false`.
1309 /// `partition()` returns a pair, all of the elements for which it returned
1310 /// `true`, and all of the elements for which it returned `false`.
1317 /// let a = [1, 2, 3];
1319 /// let (even, odd): (Vec<i32>, Vec<i32>) = a.into_iter()
1320 /// .partition(|&n| n % 2 == 0);
1322 /// assert_eq!(even, vec![2]);
1323 /// assert_eq!(odd, vec![1, 3]);
1325 #[stable(feature = "rust1", since = "1.0.0")]
1326 fn partition<B, F>(self, mut f: F) -> (B, B) where
1328 B: Default + Extend<Self::Item>,
1329 F: FnMut(&Self::Item) -> bool
1331 let mut left: B = Default::default();
1332 let mut right: B = Default::default();
1336 left.extend(Some(x))
1338 right.extend(Some(x))
1345 /// An iterator method that applies a function as long as it returns
1346 /// successfully, producing a single, final value.
1348 /// `try_fold()` takes two arguments: an initial value, and a closure with
1349 /// two arguments: an 'accumulator', and an element. The closure either
1350 /// returns successfully, with the value that the accumulator should have
1351 /// for the next iteration, or it returns failure, with an error value that
1352 /// is propagated back to the caller immediately (short-circuiting).
1354 /// The initial value is the value the accumulator will have on the first
1355 /// call. If applying the closure succeeded against every element of the
1356 /// iterator, `try_fold()` returns the final accumulator as success.
1358 /// Folding is useful whenever you have a collection of something, and want
1359 /// to produce a single value from it.
1361 /// # Note to Implementors
1363 /// Most of the other (forward) methods have default implementations in
1364 /// terms of this one, so try to implement this explicitly if it can
1365 /// do something better than the default `for` loop implementation.
1367 /// In particular, try to have this call `try_fold()` on the internal parts
1368 /// from which this iterator is composed. If multiple calls are needed,
1369 /// the `?` operator be convenient for chaining the accumulator value along,
1370 /// but beware any invariants that need to be upheld before those early
1371 /// returns. This is a `&mut self` method, so iteration needs to be
1372 /// resumable after hitting an error here.
1379 /// #![feature(iterator_try_fold)]
1380 /// let a = [1, 2, 3];
1382 /// // the checked sum of all of the elements of the array
1383 /// let sum = a.iter()
1384 /// .try_fold(0i8, |acc, &x| acc.checked_add(x));
1386 /// assert_eq!(sum, Some(6));
1389 /// Short-circuiting:
1392 /// #![feature(iterator_try_fold)]
1393 /// let a = [10, 20, 30, 100, 40, 50];
1394 /// let mut it = a.iter();
1396 /// // This sum overflows when adding the 100 element
1397 /// let sum = it.try_fold(0i8, |acc, &x| acc.checked_add(x));
1398 /// assert_eq!(sum, None);
1400 /// // Because it short-circuited, the remaining elements are still
1401 /// // available through the iterator.
1402 /// assert_eq!(it.len(), 2);
1403 /// assert_eq!(it.next(), Some(&40));
1406 #[unstable(feature = "iterator_try_fold", issue = "45594")]
1407 fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R where
1408 Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
1410 let mut accum = init;
1411 while let Some(x) = self.next() {
1412 accum = f(accum, x)?;
1417 /// An iterator method that applies a function, producing a single, final value.
1419 /// `fold()` takes two arguments: an initial value, and a closure with two
1420 /// arguments: an 'accumulator', and an element. The closure returns the value that
1421 /// the accumulator should have for the next iteration.
1423 /// The initial value is the value the accumulator will have on the first
1426 /// After applying this closure to every element of the iterator, `fold()`
1427 /// returns the accumulator.
1429 /// This operation is sometimes called 'reduce' or 'inject'.
1431 /// Folding is useful whenever you have a collection of something, and want
1432 /// to produce a single value from it.
1434 /// Note: `fold()`, and similar methods that traverse the entire iterator,
1435 /// may not terminate for infinite iterators, even on traits for which a
1436 /// result is determinable in finite time.
1443 /// let a = [1, 2, 3];
1445 /// // the sum of all of the elements of the array
1446 /// let sum = a.iter()
1447 /// .fold(0, |acc, &x| acc + x);
1449 /// assert_eq!(sum, 6);
1452 /// Let's walk through each step of the iteration here:
1454 /// | element | acc | x | result |
1455 /// |---------|-----|---|--------|
1457 /// | 1 | 0 | 1 | 1 |
1458 /// | 2 | 1 | 2 | 3 |
1459 /// | 3 | 3 | 3 | 6 |
1461 /// And so, our final result, `6`.
1463 /// It's common for people who haven't used iterators a lot to
1464 /// use a `for` loop with a list of things to build up a result. Those
1465 /// can be turned into `fold()`s:
1467 /// [`for`]: ../../book/first-edition/loops.html#for
1470 /// let numbers = [1, 2, 3, 4, 5];
1472 /// let mut result = 0;
1475 /// for i in &numbers {
1476 /// result = result + i;
1480 /// let result2 = numbers.iter().fold(0, |acc, &x| acc + x);
1482 /// // they're the same
1483 /// assert_eq!(result, result2);
1486 #[stable(feature = "rust1", since = "1.0.0")]
1487 fn fold<B, F>(mut self, init: B, mut f: F) -> B where
1488 Self: Sized, F: FnMut(B, Self::Item) -> B,
1490 self.try_fold(init, move |acc, x| AlwaysOk(f(acc, x))).0
1493 /// Tests if every element of the iterator matches a predicate.
1495 /// `all()` takes a closure that returns `true` or `false`. It applies
1496 /// this closure to each element of the iterator, and if they all return
1497 /// `true`, then so does `all()`. If any of them return `false`, it
1498 /// returns `false`.
1500 /// `all()` is short-circuiting; in other words, it will stop processing
1501 /// as soon as it finds a `false`, given that no matter what else happens,
1502 /// the result will also be `false`.
1504 /// An empty iterator returns `true`.
1511 /// let a = [1, 2, 3];
1513 /// assert!(a.iter().all(|&x| x > 0));
1515 /// assert!(!a.iter().all(|&x| x > 2));
1518 /// Stopping at the first `false`:
1521 /// let a = [1, 2, 3];
1523 /// let mut iter = a.iter();
1525 /// assert!(!iter.all(|&x| x != 2));
1527 /// // we can still use `iter`, as there are more elements.
1528 /// assert_eq!(iter.next(), Some(&3));
1531 #[stable(feature = "rust1", since = "1.0.0")]
1532 fn all<F>(&mut self, mut f: F) -> bool where
1533 Self: Sized, F: FnMut(Self::Item) -> bool
1535 self.try_fold((), move |(), x| {
1536 if f(x) { LoopState::Continue(()) }
1537 else { LoopState::Break(()) }
1538 }) == LoopState::Continue(())
1541 /// Tests if any element of the iterator matches a predicate.
1543 /// `any()` takes a closure that returns `true` or `false`. It applies
1544 /// this closure to each element of the iterator, and if any of them return
1545 /// `true`, then so does `any()`. If they all return `false`, it
1546 /// returns `false`.
1548 /// `any()` is short-circuiting; in other words, it will stop processing
1549 /// as soon as it finds a `true`, given that no matter what else happens,
1550 /// the result will also be `true`.
1552 /// An empty iterator returns `false`.
1559 /// let a = [1, 2, 3];
1561 /// assert!(a.iter().any(|&x| x > 0));
1563 /// assert!(!a.iter().any(|&x| x > 5));
1566 /// Stopping at the first `true`:
1569 /// let a = [1, 2, 3];
1571 /// let mut iter = a.iter();
1573 /// assert!(iter.any(|&x| x != 2));
1575 /// // we can still use `iter`, as there are more elements.
1576 /// assert_eq!(iter.next(), Some(&2));
1579 #[stable(feature = "rust1", since = "1.0.0")]
1580 fn any<F>(&mut self, mut f: F) -> bool where
1582 F: FnMut(Self::Item) -> bool
1584 self.try_fold((), move |(), x| {
1585 if f(x) { LoopState::Break(()) }
1586 else { LoopState::Continue(()) }
1587 }) == LoopState::Break(())
1590 /// Searches for an element of an iterator that satisfies a predicate.
1592 /// `find()` takes a closure that returns `true` or `false`. It applies
1593 /// this closure to each element of the iterator, and if any of them return
1594 /// `true`, then `find()` returns [`Some(element)`]. If they all return
1595 /// `false`, it returns [`None`].
1597 /// `find()` is short-circuiting; in other words, it will stop processing
1598 /// as soon as the closure returns `true`.
1600 /// Because `find()` takes a reference, and many iterators iterate over
1601 /// references, this leads to a possibly confusing situation where the
1602 /// argument is a double reference. You can see this effect in the
1603 /// examples below, with `&&x`.
1605 /// [`Some(element)`]: ../../std/option/enum.Option.html#variant.Some
1606 /// [`None`]: ../../std/option/enum.Option.html#variant.None
1613 /// let a = [1, 2, 3];
1615 /// assert_eq!(a.iter().find(|&&x| x == 2), Some(&2));
1617 /// assert_eq!(a.iter().find(|&&x| x == 5), None);
1620 /// Stopping at the first `true`:
1623 /// let a = [1, 2, 3];
1625 /// let mut iter = a.iter();
1627 /// assert_eq!(iter.find(|&&x| x == 2), Some(&2));
1629 /// // we can still use `iter`, as there are more elements.
1630 /// assert_eq!(iter.next(), Some(&3));
1633 #[stable(feature = "rust1", since = "1.0.0")]
1634 fn find<P>(&mut self, mut predicate: P) -> Option<Self::Item> where
1636 P: FnMut(&Self::Item) -> bool,
1638 self.try_fold((), move |(), x| {
1639 if predicate(&x) { LoopState::Break(x) }
1640 else { LoopState::Continue(()) }
1644 /// Searches for an element in an iterator, returning its index.
1646 /// `position()` takes a closure that returns `true` or `false`. It applies
1647 /// this closure to each element of the iterator, and if one of them
1648 /// returns `true`, then `position()` returns [`Some(index)`]. If all of
1649 /// them return `false`, it returns [`None`].
1651 /// `position()` is short-circuiting; in other words, it will stop
1652 /// processing as soon as it finds a `true`.
1654 /// # Overflow Behavior
1656 /// The method does no guarding against overflows, so if there are more
1657 /// than [`usize::MAX`] non-matching elements, it either produces the wrong
1658 /// result or panics. If debug assertions are enabled, a panic is
1663 /// This function might panic if the iterator has more than `usize::MAX`
1664 /// non-matching elements.
1666 /// [`Some(index)`]: ../../std/option/enum.Option.html#variant.Some
1667 /// [`None`]: ../../std/option/enum.Option.html#variant.None
1668 /// [`usize::MAX`]: ../../std/usize/constant.MAX.html
1675 /// let a = [1, 2, 3];
1677 /// assert_eq!(a.iter().position(|&x| x == 2), Some(1));
1679 /// assert_eq!(a.iter().position(|&x| x == 5), None);
1682 /// Stopping at the first `true`:
1685 /// let a = [1, 2, 3, 4];
1687 /// let mut iter = a.iter();
1689 /// assert_eq!(iter.position(|&x| x >= 2), Some(1));
1691 /// // we can still use `iter`, as there are more elements.
1692 /// assert_eq!(iter.next(), Some(&3));
1694 /// // The returned index depends on iterator state
1695 /// assert_eq!(iter.position(|&x| x == 4), Some(0));
1699 #[rustc_inherit_overflow_checks]
1700 #[stable(feature = "rust1", since = "1.0.0")]
1701 fn position<P>(&mut self, mut predicate: P) -> Option<usize> where
1703 P: FnMut(Self::Item) -> bool,
1705 // The addition might panic on overflow
1706 self.try_fold(0, move |i, x| {
1707 if predicate(x) { LoopState::Break(i) }
1708 else { LoopState::Continue(i + 1) }
1712 /// Searches for an element in an iterator from the right, returning its
1715 /// `rposition()` takes a closure that returns `true` or `false`. It applies
1716 /// this closure to each element of the iterator, starting from the end,
1717 /// and if one of them returns `true`, then `rposition()` returns
1718 /// [`Some(index)`]. If all of them return `false`, it returns [`None`].
1720 /// `rposition()` is short-circuiting; in other words, it will stop
1721 /// processing as soon as it finds a `true`.
1723 /// [`Some(index)`]: ../../std/option/enum.Option.html#variant.Some
1724 /// [`None`]: ../../std/option/enum.Option.html#variant.None
1731 /// let a = [1, 2, 3];
1733 /// assert_eq!(a.iter().rposition(|&x| x == 3), Some(2));
1735 /// assert_eq!(a.iter().rposition(|&x| x == 5), None);
1738 /// Stopping at the first `true`:
1741 /// let a = [1, 2, 3];
1743 /// let mut iter = a.iter();
1745 /// assert_eq!(iter.rposition(|&x| x == 2), Some(1));
1747 /// // we can still use `iter`, as there are more elements.
1748 /// assert_eq!(iter.next(), Some(&1));
1751 #[stable(feature = "rust1", since = "1.0.0")]
1752 fn rposition<P>(&mut self, mut predicate: P) -> Option<usize> where
1753 P: FnMut(Self::Item) -> bool,
1754 Self: Sized + ExactSizeIterator + DoubleEndedIterator
1756 // No need for an overflow check here, because `ExactSizeIterator`
1757 // implies that the number of elements fits into a `usize`.
1759 self.try_rfold(n, move |i, x| {
1761 if predicate(x) { LoopState::Break(i) }
1762 else { LoopState::Continue(i) }
1766 /// Returns the maximum element of an iterator.
1768 /// If several elements are equally maximum, the last element is
1769 /// returned. If the iterator is empty, [`None`] is returned.
1771 /// [`None`]: ../../std/option/enum.Option.html#variant.None
1778 /// let a = [1, 2, 3];
1779 /// let b: Vec<u32> = Vec::new();
1781 /// assert_eq!(a.iter().max(), Some(&3));
1782 /// assert_eq!(b.iter().max(), None);
1785 #[stable(feature = "rust1", since = "1.0.0")]
1786 fn max(self) -> Option<Self::Item> where Self: Sized, Self::Item: Ord
1790 // switch to y even if it is only equal, to preserve
1792 |_, x, _, y| *x <= *y)
1796 /// Returns the minimum element of an iterator.
1798 /// If several elements are equally minimum, the first element is
1799 /// returned. If the iterator is empty, [`None`] is returned.
1801 /// [`None`]: ../../std/option/enum.Option.html#variant.None
1808 /// let a = [1, 2, 3];
1809 /// let b: Vec<u32> = Vec::new();
1811 /// assert_eq!(a.iter().min(), Some(&1));
1812 /// assert_eq!(b.iter().min(), None);
1815 #[stable(feature = "rust1", since = "1.0.0")]
1816 fn min(self) -> Option<Self::Item> where Self: Sized, Self::Item: Ord
1820 // only switch to y if it is strictly smaller, to
1821 // preserve stability.
1822 |_, x, _, y| *x > *y)
1826 /// Returns the element that gives the maximum value from the
1827 /// specified function.
1829 /// If several elements are equally maximum, the last element is
1830 /// returned. If the iterator is empty, [`None`] is returned.
1832 /// [`None`]: ../../std/option/enum.Option.html#variant.None
1837 /// let a = [-3_i32, 0, 1, 5, -10];
1838 /// assert_eq!(*a.iter().max_by_key(|x| x.abs()).unwrap(), -10);
1841 #[stable(feature = "iter_cmp_by_key", since = "1.6.0")]
1842 fn max_by_key<B: Ord, F>(self, f: F) -> Option<Self::Item>
1843 where Self: Sized, F: FnMut(&Self::Item) -> B,
1847 // switch to y even if it is only equal, to preserve
1849 |x_p, _, y_p, _| x_p <= y_p)
1853 /// Returns the element that gives the maximum value with respect to the
1854 /// specified comparison function.
1856 /// If several elements are equally maximum, the last element is
1857 /// returned. If the iterator is empty, [`None`] is returned.
1859 /// [`None`]: ../../std/option/enum.Option.html#variant.None
1864 /// let a = [-3_i32, 0, 1, 5, -10];
1865 /// assert_eq!(*a.iter().max_by(|x, y| x.cmp(y)).unwrap(), 5);
1868 #[stable(feature = "iter_max_by", since = "1.15.0")]
1869 fn max_by<F>(self, mut compare: F) -> Option<Self::Item>
1870 where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering,
1874 // switch to y even if it is only equal, to preserve
1876 |_, x, _, y| Ordering::Greater != compare(x, y))
1880 /// Returns the element that gives the minimum value from the
1881 /// specified function.
1883 /// If several elements are equally minimum, the first element is
1884 /// returned. If the iterator is empty, [`None`] is returned.
1886 /// [`None`]: ../../std/option/enum.Option.html#variant.None
1891 /// let a = [-3_i32, 0, 1, 5, -10];
1892 /// assert_eq!(*a.iter().min_by_key(|x| x.abs()).unwrap(), 0);
1894 #[stable(feature = "iter_cmp_by_key", since = "1.6.0")]
1895 fn min_by_key<B: Ord, F>(self, f: F) -> Option<Self::Item>
1896 where Self: Sized, F: FnMut(&Self::Item) -> B,
1900 // only switch to y if it is strictly smaller, to
1901 // preserve stability.
1902 |x_p, _, y_p, _| x_p > y_p)
1906 /// Returns the element that gives the minimum value with respect to the
1907 /// specified comparison function.
1909 /// If several elements are equally minimum, the first element is
1910 /// returned. If the iterator is empty, [`None`] is returned.
1912 /// [`None`]: ../../std/option/enum.Option.html#variant.None
1917 /// let a = [-3_i32, 0, 1, 5, -10];
1918 /// assert_eq!(*a.iter().min_by(|x, y| x.cmp(y)).unwrap(), -10);
1921 #[stable(feature = "iter_min_by", since = "1.15.0")]
1922 fn min_by<F>(self, mut compare: F) -> Option<Self::Item>
1923 where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering,
1927 // switch to y even if it is strictly smaller, to
1928 // preserve stability.
1929 |_, x, _, y| Ordering::Greater == compare(x, y))
1934 /// Reverses an iterator's direction.
1936 /// Usually, iterators iterate from left to right. After using `rev()`,
1937 /// an iterator will instead iterate from right to left.
1939 /// This is only possible if the iterator has an end, so `rev()` only
1940 /// works on [`DoubleEndedIterator`]s.
1942 /// [`DoubleEndedIterator`]: trait.DoubleEndedIterator.html
1947 /// let a = [1, 2, 3];
1949 /// let mut iter = a.iter().rev();
1951 /// assert_eq!(iter.next(), Some(&3));
1952 /// assert_eq!(iter.next(), Some(&2));
1953 /// assert_eq!(iter.next(), Some(&1));
1955 /// assert_eq!(iter.next(), None);
1958 #[stable(feature = "rust1", since = "1.0.0")]
1959 fn rev(self) -> Rev<Self> where Self: Sized + DoubleEndedIterator {
1963 /// Converts an iterator of pairs into a pair of containers.
1965 /// `unzip()` consumes an entire iterator of pairs, producing two
1966 /// collections: one from the left elements of the pairs, and one
1967 /// from the right elements.
1969 /// This function is, in some sense, the opposite of [`zip`].
1971 /// [`zip`]: #method.zip
1978 /// let a = [(1, 2), (3, 4)];
1980 /// let (left, right): (Vec<_>, Vec<_>) = a.iter().cloned().unzip();
1982 /// assert_eq!(left, [1, 3]);
1983 /// assert_eq!(right, [2, 4]);
1985 #[stable(feature = "rust1", since = "1.0.0")]
1986 fn unzip<A, B, FromA, FromB>(self) -> (FromA, FromB) where
1987 FromA: Default + Extend<A>,
1988 FromB: Default + Extend<B>,
1989 Self: Sized + Iterator<Item=(A, B)>,
1991 let mut ts: FromA = Default::default();
1992 let mut us: FromB = Default::default();
1994 self.for_each(|(t, u)| {
2002 /// Creates an iterator which [`clone`]s all of its elements.
2004 /// This is useful when you have an iterator over `&T`, but you need an
2005 /// iterator over `T`.
2007 /// [`clone`]: ../../std/clone/trait.Clone.html#tymethod.clone
2014 /// let a = [1, 2, 3];
2016 /// let v_cloned: Vec<_> = a.iter().cloned().collect();
2018 /// // cloned is the same as .map(|&x| x), for integers
2019 /// let v_map: Vec<_> = a.iter().map(|&x| x).collect();
2021 /// assert_eq!(v_cloned, vec![1, 2, 3]);
2022 /// assert_eq!(v_map, vec![1, 2, 3]);
2024 #[stable(feature = "rust1", since = "1.0.0")]
2025 fn cloned<'a, T: 'a>(self) -> Cloned<Self>
2026 where Self: Sized + Iterator<Item=&'a T>, T: Clone
2031 /// Repeats an iterator endlessly.
2033 /// Instead of stopping at [`None`], the iterator will instead start again,
2034 /// from the beginning. After iterating again, it will start at the
2035 /// beginning again. And again. And again. Forever.
2037 /// [`None`]: ../../std/option/enum.Option.html#variant.None
2044 /// let a = [1, 2, 3];
2046 /// let mut it = a.iter().cycle();
2048 /// assert_eq!(it.next(), Some(&1));
2049 /// assert_eq!(it.next(), Some(&2));
2050 /// assert_eq!(it.next(), Some(&3));
2051 /// assert_eq!(it.next(), Some(&1));
2052 /// assert_eq!(it.next(), Some(&2));
2053 /// assert_eq!(it.next(), Some(&3));
2054 /// assert_eq!(it.next(), Some(&1));
2056 #[stable(feature = "rust1", since = "1.0.0")]
2058 fn cycle(self) -> Cycle<Self> where Self: Sized + Clone {
2059 Cycle{orig: self.clone(), iter: self}
2062 /// Sums the elements of an iterator.
2064 /// Takes each element, adds them together, and returns the result.
2066 /// An empty iterator returns the zero value of the type.
2070 /// When calling `sum()` and a primitive integer type is being returned, this
2071 /// method will panic if the computation overflows and debug assertions are
2079 /// let a = [1, 2, 3];
2080 /// let sum: i32 = a.iter().sum();
2082 /// assert_eq!(sum, 6);
2084 #[stable(feature = "iter_arith", since = "1.11.0")]
2085 fn sum<S>(self) -> S
2092 /// Iterates over the entire iterator, multiplying all the elements
2094 /// An empty iterator returns the one value of the type.
2098 /// When calling `product()` and a primitive integer type is being returned,
2099 /// method will panic if the computation overflows and debug assertions are
2105 /// fn factorial(n: u32) -> u32 {
2106 /// (1..).take_while(|&i| i <= n).product()
2108 /// assert_eq!(factorial(0), 1);
2109 /// assert_eq!(factorial(1), 1);
2110 /// assert_eq!(factorial(5), 120);
2112 #[stable(feature = "iter_arith", since = "1.11.0")]
2113 fn product<P>(self) -> P
2115 P: Product<Self::Item>,
2117 Product::product(self)
2120 /// Lexicographically compares the elements of this `Iterator` with those
2122 #[stable(feature = "iter_order", since = "1.5.0")]
2123 fn cmp<I>(mut self, other: I) -> Ordering where
2124 I: IntoIterator<Item = Self::Item>,
2128 let mut other = other.into_iter();
2131 let x = match self.next() {
2132 None => if other.next().is_none() {
2133 return Ordering::Equal
2135 return Ordering::Less
2140 let y = match other.next() {
2141 None => return Ordering::Greater,
2146 Ordering::Equal => (),
2147 non_eq => return non_eq,
2152 /// Lexicographically compares the elements of this `Iterator` with those
2154 #[stable(feature = "iter_order", since = "1.5.0")]
2155 fn partial_cmp<I>(mut self, other: I) -> Option<Ordering> where
2157 Self::Item: PartialOrd<I::Item>,
2160 let mut other = other.into_iter();
2163 let x = match self.next() {
2164 None => if other.next().is_none() {
2165 return Some(Ordering::Equal)
2167 return Some(Ordering::Less)
2172 let y = match other.next() {
2173 None => return Some(Ordering::Greater),
2177 match x.partial_cmp(&y) {
2178 Some(Ordering::Equal) => (),
2179 non_eq => return non_eq,
2184 /// Determines if the elements of this `Iterator` are equal to those of
2186 #[stable(feature = "iter_order", since = "1.5.0")]
2187 fn eq<I>(mut self, other: I) -> bool where
2189 Self::Item: PartialEq<I::Item>,
2192 let mut other = other.into_iter();
2195 let x = match self.next() {
2196 None => return other.next().is_none(),
2200 let y = match other.next() {
2201 None => return false,
2205 if x != y { return false }
2209 /// Determines if the elements of this `Iterator` are unequal to those of
2211 #[stable(feature = "iter_order", since = "1.5.0")]
2212 fn ne<I>(mut self, other: I) -> bool where
2214 Self::Item: PartialEq<I::Item>,
2217 let mut other = other.into_iter();
2220 let x = match self.next() {
2221 None => return other.next().is_some(),
2225 let y = match other.next() {
2226 None => return true,
2230 if x != y { return true }
2234 /// Determines if the elements of this `Iterator` are lexicographically
2235 /// less than those of another.
2236 #[stable(feature = "iter_order", since = "1.5.0")]
2237 fn lt<I>(mut self, other: I) -> bool where
2239 Self::Item: PartialOrd<I::Item>,
2242 let mut other = other.into_iter();
2245 let x = match self.next() {
2246 None => return other.next().is_some(),
2250 let y = match other.next() {
2251 None => return false,
2255 match x.partial_cmp(&y) {
2256 Some(Ordering::Less) => return true,
2257 Some(Ordering::Equal) => (),
2258 Some(Ordering::Greater) => return false,
2259 None => return false,
2264 /// Determines if the elements of this `Iterator` are lexicographically
2265 /// less or equal to those of another.
2266 #[stable(feature = "iter_order", since = "1.5.0")]
2267 fn le<I>(mut self, other: I) -> bool where
2269 Self::Item: PartialOrd<I::Item>,
2272 let mut other = other.into_iter();
2275 let x = match self.next() {
2276 None => { other.next(); return true; },
2280 let y = match other.next() {
2281 None => return false,
2285 match x.partial_cmp(&y) {
2286 Some(Ordering::Less) => return true,
2287 Some(Ordering::Equal) => (),
2288 Some(Ordering::Greater) => return false,
2289 None => return false,
2294 /// Determines if the elements of this `Iterator` are lexicographically
2295 /// greater than those of another.
2296 #[stable(feature = "iter_order", since = "1.5.0")]
2297 fn gt<I>(mut self, other: I) -> bool where
2299 Self::Item: PartialOrd<I::Item>,
2302 let mut other = other.into_iter();
2305 let x = match self.next() {
2306 None => { other.next(); return false; },
2310 let y = match other.next() {
2311 None => return true,
2315 match x.partial_cmp(&y) {
2316 Some(Ordering::Less) => return false,
2317 Some(Ordering::Equal) => (),
2318 Some(Ordering::Greater) => return true,
2319 None => return false,
2324 /// Determines if the elements of this `Iterator` are lexicographically
2325 /// greater than or equal to those of another.
2326 #[stable(feature = "iter_order", since = "1.5.0")]
2327 fn ge<I>(mut self, other: I) -> bool where
2329 Self::Item: PartialOrd<I::Item>,
2332 let mut other = other.into_iter();
2335 let x = match self.next() {
2336 None => return other.next().is_none(),
2340 let y = match other.next() {
2341 None => return true,
2345 match x.partial_cmp(&y) {
2346 Some(Ordering::Less) => return false,
2347 Some(Ordering::Equal) => (),
2348 Some(Ordering::Greater) => return true,
2349 None => return false,
2355 /// Select an element from an iterator based on the given "projection"
2356 /// and "comparison" function.
2358 /// This is an idiosyncratic helper to try to factor out the
2359 /// commonalities of {max,min}{,_by}. In particular, this avoids
2360 /// having to implement optimizations several times.
2362 fn select_fold1<I, B, FProj, FCmp>(mut it: I,
2364 mut f_cmp: FCmp) -> Option<(B, I::Item)>
2366 FProj: FnMut(&I::Item) -> B,
2367 FCmp: FnMut(&B, &I::Item, &B, &I::Item) -> bool
2369 // start with the first element as our selection. This avoids
2370 // having to use `Option`s inside the loop, translating to a
2371 // sizeable performance gain (6x in one case).
2372 it.next().map(|first| {
2373 let first_p = f_proj(&first);
2375 it.fold((first_p, first), |(sel_p, sel), x| {
2376 let x_p = f_proj(&x);
2377 if f_cmp(&sel_p, &sel, &x_p, &x) {
2386 #[stable(feature = "rust1", since = "1.0.0")]
2387 impl<'a, I: Iterator + ?Sized> Iterator for &'a mut I {
2388 type Item = I::Item;
2389 fn next(&mut self) -> Option<I::Item> { (**self).next() }
2390 fn size_hint(&self) -> (usize, Option<usize>) { (**self).size_hint() }
2391 fn nth(&mut self, n: usize) -> Option<Self::Item> {