1 // Copyright 2013-2014 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`]: ../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 values.into_iter() {
193 //! mut iter => loop {
194 //! match iter.next() {
195 //! Some(x) => { println!("{}", x); },
204 //! First, we call `into_iter()` on the value. Then, we match on the iterator
205 //! that returns, calling [`next()`] over and over until we see a `None`. At
206 //! that point, we `break` out of the loop, and we're done iterating.
208 //! There's one more subtle bit here: the standard library contains an
209 //! interesting implementation of [`IntoIterator`]:
212 //! impl<I: Iterator> IntoIterator for I
215 //! In other words, all [`Iterator`]s implement [`IntoIterator`], by just
216 //! returning themselves. This means two things:
218 //! 1. If you're writing an [`Iterator`], you can use it with a `for` loop.
219 //! 2. If you're creating a collection, implementing [`IntoIterator`] for it
220 //! will allow your collection to be used with the `for` loop.
224 //! Functions which take an [`Iterator`] and return another [`Iterator`] are
225 //! often called 'iterator adapters', as they're a form of the 'adapter
228 //! Common iterator adapters include [`map()`], [`take()`], and [`collect()`].
229 //! For more, see their documentation.
231 //! [`map()`]: trait.Iterator.html#method.map
232 //! [`take()`]: trait.Iterator.html#method.take
233 //! [`collect()`]: trait.Iterator.html#method.collect
237 //! Iterators (and iterator [adapters](#adapters)) are *lazy*. This means that
238 //! just creating an iterator doesn't _do_ a whole lot. Nothing really happens
239 //! until you call [`next()`]. This is sometimes a source of confusion when
240 //! creating an iterator solely for its side effects. For example, the [`map()`]
241 //! method calls a closure on each element it iterates over:
244 //! let v = vec![1, 2, 3, 4, 5];
245 //! v.iter().map(|x| println!("{}", x));
248 //! This will not print any values, as we only created an iterator, rather than
249 //! using it. The compiler will warn us about this kind of behavior:
252 //! warning: unused result which must be used: iterator adaptors are lazy and
253 //! do nothing unless consumed
256 //! The idiomatic way to write a [`map()`] for its side effects is to use a
257 //! `for` loop instead:
260 //! let v = vec![1, 2, 3, 4, 5];
263 //! println!("{}", x);
267 //! [`map()`]: trait.Iterator.html#method.map
269 //! The two most common ways to evaluate an iterator are to use a `for` loop
270 //! like this, or using the [`collect()`] adapter to produce a new collection.
272 //! [`collect()`]: trait.Iterator.html#method.collect
276 //! Iterators do not have to be finite. As an example, an open-ended range is
277 //! an infinite iterator:
280 //! let numbers = 0..;
283 //! It is common to use the [`take()`] iterator adapter to turn an infinite
284 //! iterator into a finite one:
287 //! let numbers = 0..;
288 //! let five_numbers = numbers.take(5);
290 //! for number in five_numbers {
291 //! println!("{}", number);
295 //! This will print the numbers `0` through `4`, each on their own line.
297 //! [`take()`]: trait.Iterator.html#method.take
299 #![stable(feature = "rust1", since = "1.0.0")]
303 use cmp::{Ord, PartialOrd, PartialEq, Ordering};
304 use default::Default;
307 use num::{Zero, One};
308 use ops::{self, Add, Sub, FnMut, Mul, RangeFrom};
309 use option::Option::{self, Some, None};
313 fn _assert_is_object_safe(_: &Iterator<Item=()>) {}
315 /// An interface for dealing with "external iterators". These types of iterators
316 /// can be resumed at any time as all state is stored internally as opposed to
317 /// being located on the call stack.
319 /// The Iterator protocol states that an iterator yields a (potentially-empty,
320 /// potentially-infinite) sequence of values, and returns `None` to signal that
321 /// it's finished. The Iterator protocol does not define behavior after `None`
322 /// is returned. A concrete Iterator implementation may choose to behave however
323 /// it wishes, either by returning `None` infinitely, or by doing something
326 #[stable(feature = "rust1", since = "1.0.0")]
327 #[rustc_on_unimplemented = "`{Self}` is not an iterator; maybe try calling \
328 `.iter()` or a similar method"]
330 /// The type of the elements being iterated
331 #[stable(feature = "rust1", since = "1.0.0")]
334 /// Advances the iterator and returns the next value. Returns `None` when the
336 #[stable(feature = "rust1", since = "1.0.0")]
337 fn next(&mut self) -> Option<Self::Item>;
339 /// Returns a lower and upper bound on the remaining length of the iterator.
341 /// An upper bound of `None` means either there is no known upper bound, or
342 /// the upper bound does not fit within a `usize`.
347 /// let it = (0..10).filter(|x| x % 2 == 0).chain(15..20);
348 /// assert_eq!((5, Some(15)), it.size_hint());
351 #[stable(feature = "rust1", since = "1.0.0")]
352 fn size_hint(&self) -> (usize, Option<usize>) { (0, None) }
354 /// Counts the number of elements in this iterator.
356 /// # Overflow Behavior
358 /// The method does no guarding against overflows, so counting elements of
359 /// an iterator with more than `usize::MAX` elements either produces the
360 /// wrong result or panics. If debug assertions are enabled, a panic is
365 /// This functions might panic if the iterator has more than `usize::MAX`
371 /// let a = [1, 2, 3, 4, 5];
372 /// assert_eq!(a.iter().count(), 5);
375 #[stable(feature = "rust1", since = "1.0.0")]
376 fn count(self) -> usize where Self: Sized {
378 self.fold(0, |cnt, _| cnt + 1)
381 /// Loops through the entire iterator, returning the last element.
386 /// let a = [1, 2, 3, 4, 5];
387 /// assert_eq!(a.iter().last(), Some(&5));
390 #[stable(feature = "rust1", since = "1.0.0")]
391 fn last(self) -> Option<Self::Item> where Self: Sized {
393 for x in self { last = Some(x); }
397 /// Skips the `n` first elements of the iterator and returns the next one.
402 /// let a = [1, 2, 3, 4, 5];
403 /// let mut it = a.iter();
404 /// assert_eq!(it.nth(2), Some(&3));
405 /// assert_eq!(it.nth(2), None);
408 #[stable(feature = "rust1", since = "1.0.0")]
409 fn nth(&mut self, mut n: usize) -> Option<Self::Item> where Self: Sized {
411 if n == 0 { return Some(x) }
417 /// Chain this iterator with another, returning a new iterator that will
418 /// finish iterating over the current iterator, and then iterate
419 /// over the other specified iterator.
426 /// let mut it = a.iter().chain(&b);
427 /// assert_eq!(it.next(), Some(&0));
428 /// assert_eq!(it.next(), Some(&1));
429 /// assert!(it.next().is_none());
432 #[stable(feature = "rust1", since = "1.0.0")]
433 fn chain<U>(self, other: U) -> Chain<Self, U::IntoIter> where
434 Self: Sized, U: IntoIterator<Item=Self::Item>,
436 Chain{a: self, b: other.into_iter(), state: ChainState::Both}
439 /// Creates an iterator that iterates over both this and the specified
440 /// iterators simultaneously, yielding the two elements as pairs. When
441 /// either iterator returns `None`, all further invocations of `next()`
442 /// will return `None`.
449 /// let mut it = a.iter().zip(&b);
450 /// assert_eq!(it.next(), Some((&0, &1)));
451 /// assert!(it.next().is_none());
454 /// `zip` can provide similar functionality to `enumerate`:
457 /// for pair in "foo".chars().enumerate() {
458 /// println!("{:?}", pair);
461 /// for pair in (0..).zip("foo".chars()) {
462 /// println!("{:?}", pair);
466 /// both produce the same output.
468 #[stable(feature = "rust1", since = "1.0.0")]
469 fn zip<U>(self, other: U) -> Zip<Self, U::IntoIter> where
470 Self: Sized, U: IntoIterator
472 Zip{a: self, b: other.into_iter()}
475 /// Creates a new iterator that will apply the specified function to each
476 /// element returned by the first, yielding the mapped element instead.
482 /// let mut it = a.iter().map(|&x| 2 * x);
483 /// assert_eq!(it.next(), Some(2));
484 /// assert_eq!(it.next(), Some(4));
485 /// assert!(it.next().is_none());
488 #[stable(feature = "rust1", since = "1.0.0")]
489 fn map<B, F>(self, f: F) -> Map<Self, F> where
490 Self: Sized, F: FnMut(Self::Item) -> B,
492 Map{iter: self, f: f}
495 /// Creates an iterator that applies the predicate to each element returned
496 /// by this iterator. The only elements that will be yielded are those that
497 /// make the predicate evaluate to `true`.
503 /// let mut it = a.iter().filter(|&x| *x > 1);
504 /// assert_eq!(it.next(), Some(&2));
505 /// assert!(it.next().is_none());
508 #[stable(feature = "rust1", since = "1.0.0")]
509 fn filter<P>(self, predicate: P) -> Filter<Self, P> where
510 Self: Sized, P: FnMut(&Self::Item) -> bool,
512 Filter{iter: self, predicate: predicate}
515 /// Creates an iterator that both filters and maps elements.
516 /// If the specified function returns `None`, the element is skipped.
517 /// Otherwise the option is unwrapped and the new value is yielded.
523 /// let mut it = a.iter().filter_map(|&x| if x > 1 {Some(2 * x)} else {None});
524 /// assert_eq!(it.next(), Some(4));
525 /// assert!(it.next().is_none());
528 #[stable(feature = "rust1", since = "1.0.0")]
529 fn filter_map<B, F>(self, f: F) -> FilterMap<Self, F> where
530 Self: Sized, F: FnMut(Self::Item) -> Option<B>,
532 FilterMap { iter: self, f: f }
535 /// Creates an iterator that yields pairs `(i, val)` where `i` is the
536 /// current index of iteration and `val` is the value returned by the
539 /// `enumerate` keeps its count as a `usize`. If you want to count by a
540 /// different sized integer, the `zip` function provides similar
543 /// # Overflow Behavior
545 /// The method does no guarding against overflows, so enumerating more than
546 /// `usize::MAX` elements either produces the wrong result or panics. If
547 /// debug assertions are enabled, a panic is guaranteed.
551 /// The returned iterator might panic if the to-be-returned index would
552 /// overflow a `usize`.
557 /// let a = [100, 200];
558 /// let mut it = a.iter().enumerate();
559 /// assert_eq!(it.next(), Some((0, &100)));
560 /// assert_eq!(it.next(), Some((1, &200)));
561 /// assert!(it.next().is_none());
564 #[stable(feature = "rust1", since = "1.0.0")]
565 fn enumerate(self) -> Enumerate<Self> where Self: Sized {
566 Enumerate { iter: self, count: 0 }
569 /// Creates an iterator that has a `.peek()` method
570 /// that returns an optional reference to the next element.
575 /// let xs = [100, 200, 300];
576 /// let mut it = xs.iter().cloned().peekable();
577 /// assert_eq!(*it.peek().unwrap(), 100);
578 /// assert_eq!(it.next().unwrap(), 100);
579 /// assert_eq!(it.next().unwrap(), 200);
580 /// assert_eq!(*it.peek().unwrap(), 300);
581 /// assert_eq!(*it.peek().unwrap(), 300);
582 /// assert_eq!(it.next().unwrap(), 300);
583 /// assert!(it.peek().is_none());
584 /// assert!(it.next().is_none());
587 #[stable(feature = "rust1", since = "1.0.0")]
588 fn peekable(self) -> Peekable<Self> where Self: Sized {
589 Peekable{iter: self, peeked: None}
592 /// Creates an iterator that invokes the predicate on elements
593 /// until it returns false. Once the predicate returns false, that
594 /// element and all further elements are yielded.
599 /// let a = [1, 2, 3, 4, 5];
600 /// let mut it = a.iter().skip_while(|&a| *a < 3);
601 /// assert_eq!(it.next(), Some(&3));
602 /// assert_eq!(it.next(), Some(&4));
603 /// assert_eq!(it.next(), Some(&5));
604 /// assert!(it.next().is_none());
607 #[stable(feature = "rust1", since = "1.0.0")]
608 fn skip_while<P>(self, predicate: P) -> SkipWhile<Self, P> where
609 Self: Sized, P: FnMut(&Self::Item) -> bool,
611 SkipWhile{iter: self, flag: false, predicate: predicate}
614 /// Creates an iterator that yields elements so long as the predicate
615 /// returns true. After the predicate returns false for the first time, no
616 /// further elements will be yielded.
621 /// let a = [1, 2, 3, 4, 5];
622 /// let mut it = a.iter().take_while(|&a| *a < 3);
623 /// assert_eq!(it.next(), Some(&1));
624 /// assert_eq!(it.next(), Some(&2));
625 /// assert!(it.next().is_none());
628 #[stable(feature = "rust1", since = "1.0.0")]
629 fn take_while<P>(self, predicate: P) -> TakeWhile<Self, P> where
630 Self: Sized, P: FnMut(&Self::Item) -> bool,
632 TakeWhile{iter: self, flag: false, predicate: predicate}
635 /// Creates an iterator that skips the first `n` elements of this iterator,
636 /// and then yields all further items.
641 /// let a = [1, 2, 3, 4, 5];
642 /// let mut it = a.iter().skip(3);
643 /// assert_eq!(it.next(), Some(&4));
644 /// assert_eq!(it.next(), Some(&5));
645 /// assert!(it.next().is_none());
648 #[stable(feature = "rust1", since = "1.0.0")]
649 fn skip(self, n: usize) -> Skip<Self> where Self: Sized {
650 Skip{iter: self, n: n}
653 /// Creates an iterator that yields the first `n` elements of this
659 /// let a = [1, 2, 3, 4, 5];
660 /// let mut it = a.iter().take(3);
661 /// assert_eq!(it.next(), Some(&1));
662 /// assert_eq!(it.next(), Some(&2));
663 /// assert_eq!(it.next(), Some(&3));
664 /// assert!(it.next().is_none());
667 #[stable(feature = "rust1", since = "1.0.0")]
668 fn take(self, n: usize) -> Take<Self> where Self: Sized, {
669 Take{iter: self, n: n}
672 /// Creates a new iterator that behaves in a similar fashion to fold.
673 /// There is a state which is passed between each iteration and can be
674 /// mutated as necessary. The yielded values from the closure are yielded
675 /// from the Scan instance when not `None`.
680 /// let a = [1, 2, 3, 4, 5];
681 /// let mut it = a.iter().scan(1, |fac, &x| {
685 /// assert_eq!(it.next(), Some(1));
686 /// assert_eq!(it.next(), Some(2));
687 /// assert_eq!(it.next(), Some(6));
688 /// assert_eq!(it.next(), Some(24));
689 /// assert_eq!(it.next(), Some(120));
690 /// assert!(it.next().is_none());
693 #[stable(feature = "rust1", since = "1.0.0")]
694 fn scan<St, B, F>(self, initial_state: St, f: F) -> Scan<Self, St, F>
695 where Self: Sized, F: FnMut(&mut St, Self::Item) -> Option<B>,
697 Scan{iter: self, f: f, state: initial_state}
700 /// Takes a function that maps each element to a new iterator and yields
701 /// all the elements of the produced iterators.
703 /// This is useful for unraveling nested structures.
708 /// let words = ["alpha", "beta", "gamma"];
709 /// let merged: String = words.iter()
710 /// .flat_map(|s| s.chars())
712 /// assert_eq!(merged, "alphabetagamma");
715 #[stable(feature = "rust1", since = "1.0.0")]
716 fn flat_map<U, F>(self, f: F) -> FlatMap<Self, U, F>
717 where Self: Sized, U: IntoIterator, F: FnMut(Self::Item) -> U,
719 FlatMap{iter: self, f: f, frontiter: None, backiter: None }
722 /// Creates an iterator that yields `None` forever after the underlying
723 /// iterator yields `None`. Random-access iterator behavior is not
724 /// affected, only single and double-ended iterator behavior.
729 /// fn process<U: Iterator<Item=i32>>(it: U) -> i32 {
730 /// let mut it = it.fuse();
732 /// for x in it.by_ref() {
738 /// // did we exhaust the iterator?
739 /// if it.next().is_none() {
744 /// let x = vec![1, 2, 3, 7, 8, 9];
745 /// assert_eq!(process(x.into_iter()), 6);
746 /// let x = vec![1, 2, 3];
747 /// assert_eq!(process(x.into_iter()), 1006);
750 #[stable(feature = "rust1", since = "1.0.0")]
751 fn fuse(self) -> Fuse<Self> where Self: Sized {
752 Fuse{iter: self, done: false}
755 /// Creates an iterator that calls a function with a reference to each
756 /// element before yielding it. This is often useful for debugging an
757 /// iterator pipeline.
762 /// let a = [1, 4, 2, 3, 8, 9, 6];
763 /// let sum: i32 = a.iter()
765 /// .inspect(|&x| println!("filtering {}", x))
766 /// .filter(|&x| x % 2 == 0)
767 /// .inspect(|&x| println!("{} made it through", x))
768 /// .fold(0, |sum, i| sum + i);
769 /// println!("{}", sum);
772 #[stable(feature = "rust1", since = "1.0.0")]
773 fn inspect<F>(self, f: F) -> Inspect<Self, F> where
774 Self: Sized, F: FnMut(&Self::Item),
776 Inspect{iter: self, f: f}
779 /// Creates a wrapper around a mutable reference to the iterator.
781 /// This is useful to allow applying iterator adaptors while still
782 /// retaining ownership of the original iterator value.
787 /// let mut it = 0..10;
788 /// // sum the first five values
789 /// let partial_sum = it.by_ref().take(5).fold(0, |a, b| a + b);
790 /// assert_eq!(partial_sum, 10);
791 /// assert_eq!(it.next(), Some(5));
793 #[stable(feature = "rust1", since = "1.0.0")]
794 fn by_ref(&mut self) -> &mut Self where Self: Sized { self }
796 /// Loops through the entire iterator, collecting all of the elements into
797 /// a container implementing `FromIterator`.
802 /// let expected = [1, 2, 3, 4, 5];
803 /// let actual: Vec<_> = expected.iter().cloned().collect();
804 /// assert_eq!(actual, expected);
807 #[stable(feature = "rust1", since = "1.0.0")]
808 fn collect<B: FromIterator<Self::Item>>(self) -> B where Self: Sized {
809 FromIterator::from_iter(self)
812 /// Loops through the entire iterator, collecting all of the elements into
813 /// one of two containers, depending on a predicate. The elements of the
814 /// first container satisfy the predicate, while the elements of the second
818 /// let vec = vec![1, 2, 3, 4];
819 /// let (even, odd): (Vec<_>, Vec<_>) = vec.into_iter().partition(|&n| n % 2 == 0);
820 /// assert_eq!(even, [2, 4]);
821 /// assert_eq!(odd, [1, 3]);
823 #[stable(feature = "rust1", since = "1.0.0")]
824 fn partition<B, F>(self, mut f: F) -> (B, B) where
826 B: Default + Extend<Self::Item>,
827 F: FnMut(&Self::Item) -> bool
829 let mut left: B = Default::default();
830 let mut right: B = Default::default();
836 right.extend(Some(x))
843 /// Performs a fold operation over the entire iterator, returning the
844 /// eventual state at the end of the iteration.
846 /// This operation is sometimes called 'reduce' or 'inject'.
851 /// let a = [1, 2, 3, 4, 5];
852 /// assert_eq!(a.iter().fold(0, |acc, &item| acc + item), 15);
855 #[stable(feature = "rust1", since = "1.0.0")]
856 fn fold<B, F>(self, init: B, mut f: F) -> B where
857 Self: Sized, F: FnMut(B, Self::Item) -> B,
859 let mut accum = init;
866 /// Tests whether the predicate holds true for all elements in the iterator.
868 /// Does not consume the iterator past the first non-matching element.
873 /// let a = [1, 2, 3, 4, 5];
874 /// assert!(a.iter().all(|x| *x > 0));
875 /// assert!(!a.iter().all(|x| *x > 2));
878 #[stable(feature = "rust1", since = "1.0.0")]
879 fn all<F>(&mut self, mut f: F) -> bool where
880 Self: Sized, F: FnMut(Self::Item) -> bool
890 /// Tests whether any element of an iterator satisfies the specified
893 /// Does not consume the iterator past the first found element.
898 /// let a = [1, 2, 3, 4, 5];
899 /// let mut it = a.iter();
900 /// assert!(it.any(|x| *x == 3));
901 /// assert_eq!(it.collect::<Vec<_>>(), [&4, &5]);
904 #[stable(feature = "rust1", since = "1.0.0")]
905 fn any<F>(&mut self, mut f: F) -> bool where
907 F: FnMut(Self::Item) -> bool
917 /// Returns the first element satisfying the specified predicate.
919 /// Does not consume the iterator past the first found element.
924 /// let a = [1, 2, 3, 4, 5];
925 /// let mut it = a.iter();
926 /// assert_eq!(it.find(|&x| *x == 3), Some(&3));
927 /// assert_eq!(it.collect::<Vec<_>>(), [&4, &5]);
929 #[stable(feature = "rust1", since = "1.0.0")]
930 fn find<P>(&mut self, mut predicate: P) -> Option<Self::Item> where
932 P: FnMut(&Self::Item) -> bool,
935 if predicate(&x) { return Some(x) }
940 /// Returns the index of the first element satisfying the specified predicate
942 /// Does not consume the iterator past the first found element.
944 /// # Overflow Behavior
946 /// The method does no guarding against overflows, so if there are more
947 /// than `usize::MAX` non-matching elements, it either produces the wrong
948 /// result or panics. If debug assertions are enabled, a panic is
953 /// This functions might panic if the iterator has more than `usize::MAX`
954 /// non-matching elements.
959 /// let a = [1, 2, 3, 4, 5];
960 /// let mut it = a.iter();
961 /// assert_eq!(it.position(|x| *x == 3), Some(2));
962 /// assert_eq!(it.collect::<Vec<_>>(), [&4, &5]);
964 #[stable(feature = "rust1", since = "1.0.0")]
965 fn position<P>(&mut self, mut predicate: P) -> Option<usize> where
967 P: FnMut(Self::Item) -> bool,
969 // `enumerate` might overflow.
970 for (i, x) in self.enumerate() {
978 /// Returns the index of the last element satisfying the specified predicate
980 /// If no element matches, `None` is returned.
982 /// Does not consume the iterator *before* the first found element.
987 /// let a = [1, 2, 2, 4, 5];
988 /// let mut it = a.iter();
989 /// assert_eq!(it.rposition(|x| *x == 2), Some(2));
990 /// assert_eq!(it.collect::<Vec<_>>(), [&1, &2]);
992 #[stable(feature = "rust1", since = "1.0.0")]
993 fn rposition<P>(&mut self, mut predicate: P) -> Option<usize> where
994 P: FnMut(Self::Item) -> bool,
995 Self: Sized + ExactSizeIterator + DoubleEndedIterator
997 let mut i = self.len();
999 while let Some(v) = self.next_back() {
1003 // No need for an overflow check here, because `ExactSizeIterator`
1004 // implies that the number of elements fits into a `usize`.
1010 /// Consumes the entire iterator to return the maximum element.
1012 /// Returns the rightmost element if the comparison determines two elements
1013 /// to be equally maximum.
1018 /// let a = [1, 2, 3, 4, 5];
1019 /// assert_eq!(a.iter().max(), Some(&5));
1022 #[stable(feature = "rust1", since = "1.0.0")]
1023 fn max(self) -> Option<Self::Item> where Self: Sized, Self::Item: Ord
1027 // switch to y even if it is only equal, to preserve
1029 |_, x, _, y| *x <= *y)
1033 /// Consumes the entire iterator to return the minimum element.
1035 /// Returns the leftmost element if the comparison determines two elements
1036 /// to be equally minimum.
1041 /// let a = [1, 2, 3, 4, 5];
1042 /// assert_eq!(a.iter().min(), Some(&1));
1045 #[stable(feature = "rust1", since = "1.0.0")]
1046 fn min(self) -> Option<Self::Item> where Self: Sized, Self::Item: Ord
1050 // only switch to y if it is strictly smaller, to
1051 // preserve stability.
1052 |_, x, _, y| *x > *y)
1056 /// Returns the element that gives the maximum value from the
1057 /// specified function.
1059 /// Returns the rightmost element if the comparison determines two elements
1060 /// to be equally maximum.
1065 /// #![feature(iter_cmp)]
1067 /// let a = [-3_i32, 0, 1, 5, -10];
1068 /// assert_eq!(*a.iter().max_by(|x| x.abs()).unwrap(), -10);
1071 #[unstable(feature = "iter_cmp",
1072 reason = "may want to produce an Ordering directly; see #15311",
1074 fn max_by<B: Ord, F>(self, f: F) -> Option<Self::Item> where
1076 F: FnMut(&Self::Item) -> B,
1080 // switch to y even if it is only equal, to preserve
1082 |x_p, _, y_p, _| x_p <= y_p)
1086 /// Returns the element that gives the minimum value from the
1087 /// specified function.
1089 /// Returns the leftmost element if the comparison determines two elements
1090 /// to be equally minimum.
1095 /// #![feature(iter_cmp)]
1097 /// let a = [-3_i32, 0, 1, 5, -10];
1098 /// assert_eq!(*a.iter().min_by(|x| x.abs()).unwrap(), 0);
1101 #[unstable(feature = "iter_cmp",
1102 reason = "may want to produce an Ordering directly; see #15311",
1104 fn min_by<B: Ord, F>(self, f: F) -> Option<Self::Item> where
1106 F: FnMut(&Self::Item) -> B,
1110 // only switch to y if it is strictly smaller, to
1111 // preserve stability.
1112 |x_p, _, y_p, _| x_p > y_p)
1116 /// Change the direction of the iterator
1118 /// The flipped iterator swaps the ends on an iterator that can already
1119 /// be iterated from the front and from the back.
1122 /// If the iterator also implements RandomAccessIterator, the flipped
1123 /// iterator is also random access, with the indices starting at the back
1124 /// of the original iterator.
1126 /// Note: Random access with flipped indices still only applies to the first
1127 /// `std::usize::MAX` elements of the original iterator.
1129 #[stable(feature = "rust1", since = "1.0.0")]
1130 fn rev(self) -> Rev<Self> where Self: Sized + DoubleEndedIterator {
1134 /// Converts an iterator of pairs into a pair of containers.
1136 /// Loops through the entire iterator, collecting the first component of
1137 /// each item into one new container, and the second component into another.
1142 /// let a = [(1, 2), (3, 4)];
1143 /// let (left, right): (Vec<_>, Vec<_>) = a.iter().cloned().unzip();
1144 /// assert_eq!(left, [1, 3]);
1145 /// assert_eq!(right, [2, 4]);
1147 #[stable(feature = "rust1", since = "1.0.0")]
1148 fn unzip<A, B, FromA, FromB>(self) -> (FromA, FromB) where
1149 FromA: Default + Extend<A>,
1150 FromB: Default + Extend<B>,
1151 Self: Sized + Iterator<Item=(A, B)>,
1153 struct SizeHint<A>(usize, Option<usize>, marker::PhantomData<A>);
1154 impl<A> Iterator for SizeHint<A> {
1157 fn next(&mut self) -> Option<A> { None }
1158 fn size_hint(&self) -> (usize, Option<usize>) {
1163 let (lo, hi) = self.size_hint();
1164 let mut ts: FromA = Default::default();
1165 let mut us: FromB = Default::default();
1167 ts.extend(SizeHint(lo, hi, marker::PhantomData));
1168 us.extend(SizeHint(lo, hi, marker::PhantomData));
1170 for (t, u) in self {
1178 /// Creates an iterator that clones the elements it yields.
1180 /// This is useful for converting an `Iterator<&T>` to an`Iterator<T>`,
1181 /// so it's a more convenient form of `map(|&x| x)`.
1186 /// let a = [0, 1, 2];
1187 /// let v_cloned: Vec<_> = a.iter().cloned().collect();
1188 /// let v_map: Vec<_> = a.iter().map(|&x| x).collect();
1189 /// assert_eq!(v_cloned, v_map);
1191 #[stable(feature = "rust1", since = "1.0.0")]
1192 fn cloned<'a, T: 'a>(self) -> Cloned<Self>
1193 where Self: Sized + Iterator<Item=&'a T>, T: Clone
1198 /// Repeats an iterator endlessly
1204 /// let mut it = a.iter().cycle();
1205 /// assert_eq!(it.next(), Some(&1));
1206 /// assert_eq!(it.next(), Some(&2));
1207 /// assert_eq!(it.next(), Some(&1));
1209 #[stable(feature = "rust1", since = "1.0.0")]
1211 fn cycle(self) -> Cycle<Self> where Self: Sized + Clone {
1212 Cycle{orig: self.clone(), iter: self}
1215 /// Iterates over the entire iterator, summing up all the elements
1220 /// #![feature(iter_arith)]
1222 /// let a = [1, 2, 3, 4, 5];
1223 /// let it = a.iter();
1224 /// assert_eq!(it.sum::<i32>(), 15);
1226 #[unstable(feature = "iter_arith", reason = "bounds recently changed",
1228 fn sum<S=<Self as Iterator>::Item>(self) -> S where
1229 S: Add<Self::Item, Output=S> + Zero,
1232 self.fold(Zero::zero(), |s, e| s + e)
1235 /// Iterates over the entire iterator, multiplying all the elements
1240 /// #![feature(iter_arith)]
1242 /// fn factorial(n: u32) -> u32 {
1243 /// (1..).take_while(|&i| i <= n).product()
1245 /// assert_eq!(factorial(0), 1);
1246 /// assert_eq!(factorial(1), 1);
1247 /// assert_eq!(factorial(5), 120);
1249 #[unstable(feature="iter_arith", reason = "bounds recently changed",
1251 fn product<P=<Self as Iterator>::Item>(self) -> P where
1252 P: Mul<Self::Item, Output=P> + One,
1255 self.fold(One::one(), |p, e| p * e)
1258 /// Lexicographically compares the elements of this `Iterator` with those
1260 #[unstable(feature = "iter_order", reason = "needs review and revision", issue = "27737")]
1261 fn cmp<I>(mut self, other: I) -> Ordering where
1262 I: IntoIterator<Item = Self::Item>,
1266 let mut other = other.into_iter();
1269 match (self.next(), other.next()) {
1270 (None, None) => return Ordering::Equal,
1271 (None, _ ) => return Ordering::Less,
1272 (_ , None) => return Ordering::Greater,
1273 (Some(x), Some(y)) => match x.cmp(&y) {
1274 Ordering::Equal => (),
1275 non_eq => return non_eq,
1281 /// Lexicographically compares the elements of this `Iterator` with those
1283 #[unstable(feature = "iter_order", reason = "needs review and revision", issue = "27737")]
1284 fn partial_cmp<I>(mut self, other: I) -> Option<Ordering> where
1286 Self::Item: PartialOrd<I::Item>,
1289 let mut other = other.into_iter();
1292 match (self.next(), other.next()) {
1293 (None, None) => return Some(Ordering::Equal),
1294 (None, _ ) => return Some(Ordering::Less),
1295 (_ , None) => return Some(Ordering::Greater),
1296 (Some(x), Some(y)) => match x.partial_cmp(&y) {
1297 Some(Ordering::Equal) => (),
1298 non_eq => return non_eq,
1304 /// Determines if the elements of this `Iterator` are equal to those of
1306 #[unstable(feature = "iter_order", reason = "needs review and revision", issue = "27737")]
1307 fn eq<I>(mut self, other: I) -> bool where
1309 Self::Item: PartialEq<I::Item>,
1312 let mut other = other.into_iter();
1315 match (self.next(), other.next()) {
1316 (None, None) => return true,
1317 (None, _) | (_, None) => return false,
1318 (Some(x), Some(y)) => if x != y { return false },
1323 /// Determines if the elements of this `Iterator` are unequal to those of
1325 #[unstable(feature = "iter_order", reason = "needs review and revision", issue = "27737")]
1326 fn ne<I>(mut self, other: I) -> bool where
1328 Self::Item: PartialEq<I::Item>,
1331 let mut other = other.into_iter();
1334 match (self.next(), other.next()) {
1335 (None, None) => return false,
1336 (None, _) | (_, None) => return true,
1337 (Some(x), Some(y)) => if x.ne(&y) { return true },
1342 /// Determines if the elements of this `Iterator` are lexicographically
1343 /// less than those of another.
1344 #[unstable(feature = "iter_order", reason = "needs review and revision", issue = "27737")]
1345 fn lt<I>(mut self, other: I) -> bool where
1347 Self::Item: PartialOrd<I::Item>,
1350 let mut other = other.into_iter();
1353 match (self.next(), other.next()) {
1354 (None, None) => return false,
1355 (None, _ ) => return true,
1356 (_ , None) => return false,
1357 (Some(x), Some(y)) => {
1358 match x.partial_cmp(&y) {
1359 Some(Ordering::Less) => return true,
1360 Some(Ordering::Equal) => {}
1361 Some(Ordering::Greater) => return false,
1362 None => return false,
1369 /// Determines if the elements of this `Iterator` are lexicographically
1370 /// less or equal to those of another.
1371 #[unstable(feature = "iter_order", reason = "needs review and revision", issue = "27737")]
1372 fn le<I>(mut self, other: I) -> bool where
1374 Self::Item: PartialOrd<I::Item>,
1377 let mut other = other.into_iter();
1380 match (self.next(), other.next()) {
1381 (None, None) => return true,
1382 (None, _ ) => return true,
1383 (_ , None) => return false,
1384 (Some(x), Some(y)) => {
1385 match x.partial_cmp(&y) {
1386 Some(Ordering::Less) => return true,
1387 Some(Ordering::Equal) => {}
1388 Some(Ordering::Greater) => return false,
1389 None => return false,
1396 /// Determines if the elements of this `Iterator` are lexicographically
1397 /// greater than those of another.
1398 #[unstable(feature = "iter_order", reason = "needs review and revision", issue = "27737")]
1399 fn gt<I>(mut self, other: I) -> bool where
1401 Self::Item: PartialOrd<I::Item>,
1404 let mut other = other.into_iter();
1407 match (self.next(), other.next()) {
1408 (None, None) => return false,
1409 (None, _ ) => return false,
1410 (_ , None) => return true,
1411 (Some(x), Some(y)) => {
1412 match x.partial_cmp(&y) {
1413 Some(Ordering::Less) => return false,
1414 Some(Ordering::Equal) => {}
1415 Some(Ordering::Greater) => return true,
1416 None => return false,
1423 /// Determines if the elements of this `Iterator` are lexicographically
1424 /// greater than or equal to those of another.
1425 #[unstable(feature = "iter_order", reason = "needs review and revision", issue = "27737")]
1426 fn ge<I>(mut self, other: I) -> bool where
1428 Self::Item: PartialOrd<I::Item>,
1431 let mut other = other.into_iter();
1434 match (self.next(), other.next()) {
1435 (None, None) => return true,
1436 (None, _ ) => return false,
1437 (_ , None) => return true,
1438 (Some(x), Some(y)) => {
1439 match x.partial_cmp(&y) {
1440 Some(Ordering::Less) => return false,
1441 Some(Ordering::Equal) => {}
1442 Some(Ordering::Greater) => return true,
1443 None => return false,
1451 /// Select an element from an iterator based on the given projection
1452 /// and "comparison" function.
1454 /// This is an idiosyncratic helper to try to factor out the
1455 /// commonalities of {max,min}{,_by}. In particular, this avoids
1456 /// having to implement optimizations several times.
1458 fn select_fold1<I,B, FProj, FCmp>(mut it: I,
1460 mut f_cmp: FCmp) -> Option<(B, I::Item)>
1462 FProj: FnMut(&I::Item) -> B,
1463 FCmp: FnMut(&B, &I::Item, &B, &I::Item) -> bool
1465 // start with the first element as our selection. This avoids
1466 // having to use `Option`s inside the loop, translating to a
1467 // sizeable performance gain (6x in one case).
1468 it.next().map(|mut sel| {
1469 let mut sel_p = f_proj(&sel);
1472 let x_p = f_proj(&x);
1473 if f_cmp(&sel_p, &sel, &x_p, &x) {
1482 #[stable(feature = "rust1", since = "1.0.0")]
1483 impl<'a, I: Iterator + ?Sized> Iterator for &'a mut I {
1484 type Item = I::Item;
1485 fn next(&mut self) -> Option<I::Item> { (**self).next() }
1486 fn size_hint(&self) -> (usize, Option<usize>) { (**self).size_hint() }
1489 /// Conversion from an `Iterator`.
1490 #[stable(feature = "rust1", since = "1.0.0")]
1491 #[rustc_on_unimplemented="a collection of type `{Self}` cannot be \
1492 built from an iterator over elements of type `{A}`"]
1493 pub trait FromIterator<A> {
1494 /// Builds a container with elements from something iterable.
1499 /// use std::collections::HashSet;
1500 /// use std::iter::FromIterator;
1502 /// let colors_vec = vec!["red", "red", "yellow", "blue"];
1503 /// let colors_set = HashSet::<&str>::from_iter(colors_vec);
1504 /// assert_eq!(colors_set.len(), 3);
1507 /// `FromIterator` is more commonly used implicitly via the
1508 /// `Iterator::collect` method:
1511 /// use std::collections::HashSet;
1513 /// let colors_vec = vec!["red", "red", "yellow", "blue"];
1514 /// let colors_set = colors_vec.into_iter().collect::<HashSet<&str>>();
1515 /// assert_eq!(colors_set.len(), 3);
1517 #[stable(feature = "rust1", since = "1.0.0")]
1518 fn from_iter<T: IntoIterator<Item=A>>(iterator: T) -> Self;
1521 /// Conversion into an `Iterator`.
1523 /// By implementing `IntoIterator` for a type, you define how it will be
1524 /// converted to an iterator. This is common for types which describe a
1525 /// collection of some kind.
1527 /// One benefit of implementing `IntoIterator` is that your type will [work
1528 /// with Rust's `for` loop syntax](index.html#for-loops-and-intoiterator).
1532 /// Vectors implement `IntoIterator`:
1535 /// let v = vec![1, 2, 3];
1537 /// let mut iter = v.into_iter();
1539 /// let n = iter.next();
1540 /// assert_eq!(Some(1), n);
1542 /// let n = iter.next();
1543 /// assert_eq!(Some(2), n);
1545 /// let n = iter.next();
1546 /// assert_eq!(Some(3), n);
1548 /// let n = iter.next();
1549 /// assert_eq!(None, n);
1552 /// Implementing `IntoIterator` for your type:
1555 /// // A sample collection, that's just a wrapper over Vec<T>
1556 /// #[derive(Debug)]
1557 /// struct MyCollection(Vec<i32>);
1559 /// // Let's give it some methods so we can create one and add things
1561 /// impl MyCollection {
1562 /// fn new() -> MyCollection {
1563 /// MyCollection(Vec::new())
1566 /// fn add(&mut self, elem: i32) {
1567 /// self.0.push(elem);
1571 /// // and we'll implement IntoIterator
1572 /// impl IntoIterator for MyCollection {
1573 /// type Item = i32;
1574 /// type IntoIter = ::std::vec::IntoIter<i32>;
1576 /// fn into_iter(self) -> Self::IntoIter {
1577 /// self.0.into_iter()
1581 /// // Now we can make a new collection...
1582 /// let mut c = MyCollection::new();
1584 /// // ... add some stuff to it ...
1589 /// // ... and then turn it into an Iterator:
1590 /// for (i, n) in c.into_iter().enumerate() {
1591 /// assert_eq!(i as i32, n);
1594 #[stable(feature = "rust1", since = "1.0.0")]
1595 pub trait IntoIterator {
1596 /// The type of the elements being iterated over.
1597 #[stable(feature = "rust1", since = "1.0.0")]
1600 /// Which kind of iterator are we turning this into?
1601 #[stable(feature = "rust1", since = "1.0.0")]
1602 type IntoIter: Iterator<Item=Self::Item>;
1604 /// Consumes `Self` and returns an iterator over it.
1605 #[stable(feature = "rust1", since = "1.0.0")]
1606 fn into_iter(self) -> Self::IntoIter;
1609 #[stable(feature = "rust1", since = "1.0.0")]
1610 impl<I: Iterator> IntoIterator for I {
1611 type Item = I::Item;
1614 fn into_iter(self) -> I {
1619 /// Extend a collection with the contents of an iterator.
1621 /// Iterators produce a series of values, and collections can also be thought
1622 /// of as a series of values. The `Extend` trait bridges this gap, allowing you
1623 /// to extend a collection by including the contents of that iterator.
1630 /// // You can extend a String with some chars:
1631 /// let mut message = String::from("The first three letters are: ");
1633 /// message.extend(&['a', 'b', 'c']);
1635 /// assert_eq!("abc", &message[29..32]);
1638 /// Implementing `Extend`:
1641 /// // A sample collection, that's just a wrapper over Vec<T>
1642 /// #[derive(Debug)]
1643 /// struct MyCollection(Vec<i32>);
1645 /// // Let's give it some methods so we can create one and add things
1647 /// impl MyCollection {
1648 /// fn new() -> MyCollection {
1649 /// MyCollection(Vec::new())
1652 /// fn add(&mut self, elem: i32) {
1653 /// self.0.push(elem);
1657 /// // since MyCollection has a list of i32s, we implement Extend for i32
1658 /// impl Extend<i32> for MyCollection {
1660 /// // This is a bit simpler with the concrete type signature: we can call
1661 /// // extend on anything which can be turned into an Iterator which gives
1662 /// // us i32s. Because we need i32s to put into MyCollection.
1663 /// fn extend<T: IntoIterator<Item=i32>>(&mut self, iterable: T) {
1665 /// // The implementation is very straightforward: loop through the
1666 /// // iterator, and add() each element to ourselves.
1667 /// for elem in iterable {
1673 /// let mut c = MyCollection::new();
1679 /// // let's extend our collection with three more numbers
1680 /// c.extend(vec![1, 2, 3]);
1682 /// // we've added these elements onto the end
1683 /// assert_eq!("MyCollection([5, 6, 7, 1, 2, 3])", format!("{:?}", c));
1685 #[stable(feature = "rust1", since = "1.0.0")]
1686 pub trait Extend<A> {
1687 /// Extends a collection with the contents of an iterator.
1689 /// As this is the only method for this trait, the [trait-level] docs
1690 /// contain more details.
1692 /// [trait-level]: trait.Extend.html
1699 /// // You can extend a String with some chars:
1700 /// let mut message = String::from("The first three letters are: ");
1702 /// message.extend(['a', 'b', 'c'].iter());
1704 /// assert_eq!("abc", &message[29..32]);
1706 #[stable(feature = "rust1", since = "1.0.0")]
1707 fn extend<T: IntoIterator<Item=A>>(&mut self, iterable: T);
1710 /// An iterator able to yield elements from both ends.
1712 /// Something that implements `DoubleEndedIterator` has one extra capability
1713 /// over something that implements [`Iterator`]: the ability to also take
1714 /// `Item`s from the back, as well as the front.
1716 /// It is important to note that both back and forth work on the same range,
1717 /// and do not cross: iteration is over when they meet in the middle.
1719 /// [`Iterator`]: trait.Iterator.html
1725 /// let numbers = vec![1, 2, 3];
1727 /// let mut iter = numbers.iter();
1729 /// let n = iter.next();
1730 /// assert_eq!(Some(&1), n);
1732 /// let n = iter.next_back();
1733 /// assert_eq!(Some(&3), n);
1735 /// let n = iter.next_back();
1736 /// assert_eq!(Some(&2), n);
1738 /// let n = iter.next();
1739 /// assert_eq!(None, n);
1741 /// let n = iter.next_back();
1742 /// assert_eq!(None, n);
1744 #[stable(feature = "rust1", since = "1.0.0")]
1745 pub trait DoubleEndedIterator: Iterator {
1746 /// An iterator able to yield elements from both ends.
1748 /// As this is the only method for this trait, the [trait-level] docs
1749 /// contain more details.
1751 /// [trait-level]: trait.DoubleEndedIterator.html
1758 /// let numbers = vec![1, 2, 3];
1760 /// let mut iter = numbers.iter();
1762 /// let n = iter.next();
1763 /// assert_eq!(Some(&1), n);
1765 /// let n = iter.next_back();
1766 /// assert_eq!(Some(&3), n);
1768 /// let n = iter.next_back();
1769 /// assert_eq!(Some(&2), n);
1771 /// let n = iter.next();
1772 /// assert_eq!(None, n);
1774 /// let n = iter.next_back();
1775 /// assert_eq!(None, n);
1777 #[stable(feature = "rust1", since = "1.0.0")]
1778 fn next_back(&mut self) -> Option<Self::Item>;
1781 #[stable(feature = "rust1", since = "1.0.0")]
1782 impl<'a, I: DoubleEndedIterator + ?Sized> DoubleEndedIterator for &'a mut I {
1783 fn next_back(&mut self) -> Option<I::Item> { (**self).next_back() }
1786 /// An iterator that knows its exact length.
1788 /// Many [`Iterator`]s don't know how many times they will iterate, but some do.
1789 /// If an iterator knows how many times it can iterate, providing access to
1790 /// that information can be useful. For example, if you want to iterate
1791 /// backwards, a good start is to know where the end is.
1793 /// When implementing an `ExactSizeIterator`, You must also implement
1794 /// [`Iterator`]. When doing so, the implementation of [`size_hint()`] *must*
1795 /// return the exact size of the iterator.
1797 /// [`Iterator`]: trait.Iterator.html
1798 /// [`size_hint()`]: trait.Iterator.html#method.size_hint
1800 /// The [`len()`] method has a default implementation, so you usually shouldn't
1801 /// implement it. However, you may be able to provide a more performant
1802 /// implementation than the default, so overriding it in this case makes sense.
1804 /// [`len()`]: #method.len
1811 /// // a finite range knows exactly how many times it will iterate
1812 /// let five = (0..5);
1814 /// assert_eq!(5, five.len());
1817 /// In the [module level docs][moddocs], we implemented an [`Iterator`],
1818 /// `Counter`. Let's implement `ExactSizeIterator` for it as well:
1820 /// [moddocs]: index.html
1823 /// # struct Counter {
1826 /// # impl Counter {
1827 /// # fn new() -> Counter {
1828 /// # Counter { count: 0 }
1831 /// # impl Iterator for Counter {
1832 /// # type Item = usize;
1833 /// # fn next(&mut self) -> Option<usize> {
1834 /// # self.count += 1;
1835 /// # if self.count < 6 {
1836 /// # Some(self.count)
1842 /// impl ExactSizeIterator for Counter {
1843 /// // We already have the number of iterations, so we can use it directly.
1844 /// fn len(&self) -> usize {
1849 /// // And now we can use it!
1851 /// let counter = Counter::new();
1853 /// assert_eq!(0, counter.len());
1855 #[stable(feature = "rust1", since = "1.0.0")]
1856 pub trait ExactSizeIterator: Iterator {
1858 #[stable(feature = "rust1", since = "1.0.0")]
1859 /// Returns the exact number of times the iterator will iterate.
1861 /// This method has a default implementation, so you usually should not
1862 /// implement it directly. However, if you can provide a more efficient
1863 /// implementation, you can do so. See the [trait-level] docs for an
1866 /// [trait-level]: trait.ExactSizeIterator.html
1873 /// // a finite range knows exactly how many times it will iterate
1874 /// let five = (0..5);
1876 /// assert_eq!(5, five.len());
1878 fn len(&self) -> usize {
1879 let (lower, upper) = self.size_hint();
1880 // Note: This assertion is overly defensive, but it checks the invariant
1881 // guaranteed by the trait. If this trait were rust-internal,
1882 // we could use debug_assert!; assert_eq! will check all Rust user
1883 // implementations too.
1884 assert_eq!(upper, Some(lower));
1889 #[stable(feature = "rust1", since = "1.0.0")]
1890 impl<'a, I: ExactSizeIterator + ?Sized> ExactSizeIterator for &'a mut I {}
1892 // All adaptors that preserve the size of the wrapped iterator are fine
1893 // Adaptors that may overflow in `size_hint` are not, i.e. `Chain`.
1894 #[stable(feature = "rust1", since = "1.0.0")]
1895 impl<I> ExactSizeIterator for Enumerate<I> where I: ExactSizeIterator {}
1896 #[stable(feature = "rust1", since = "1.0.0")]
1897 impl<I: ExactSizeIterator, F> ExactSizeIterator for Inspect<I, F> where
1900 #[stable(feature = "rust1", since = "1.0.0")]
1901 impl<I> ExactSizeIterator for Rev<I>
1902 where I: ExactSizeIterator + DoubleEndedIterator {}
1903 #[stable(feature = "rust1", since = "1.0.0")]
1904 impl<B, I: ExactSizeIterator, F> ExactSizeIterator for Map<I, F> where
1905 F: FnMut(I::Item) -> B,
1907 #[stable(feature = "rust1", since = "1.0.0")]
1908 impl<A, B> ExactSizeIterator for Zip<A, B>
1909 where A: ExactSizeIterator, B: ExactSizeIterator {}
1911 /// An double-ended iterator with the direction inverted.
1913 /// This `struct` is created by the [`rev()`] method on [`Iterator`]. See its
1914 /// documentation for more.
1916 /// [`rev()`]: trait.Iterator.html#method.rev
1917 /// [`Iterator`]: trait.Iterator.html
1919 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1920 #[stable(feature = "rust1", since = "1.0.0")]
1925 #[stable(feature = "rust1", since = "1.0.0")]
1926 impl<I> Iterator for Rev<I> where I: DoubleEndedIterator {
1927 type Item = <I as Iterator>::Item;
1930 fn next(&mut self) -> Option<<I as Iterator>::Item> { self.iter.next_back() }
1932 fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
1935 #[stable(feature = "rust1", since = "1.0.0")]
1936 impl<I> DoubleEndedIterator for Rev<I> where I: DoubleEndedIterator {
1938 fn next_back(&mut self) -> Option<<I as Iterator>::Item> { self.iter.next() }
1941 /// An iterator that clones the elements of an underlying iterator.
1943 /// This `struct` is created by the [`cloned()`] method on [`Iterator`]. See its
1944 /// documentation for more.
1946 /// [`cloned()`]: trait.Iterator.html#method.cloned
1947 /// [`Iterator`]: trait.Iterator.html
1948 #[stable(feature = "iter_cloned", since = "1.1.0")]
1949 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1951 pub struct Cloned<I> {
1955 #[stable(feature = "rust1", since = "1.0.0")]
1956 impl<'a, I, T: 'a> Iterator for Cloned<I>
1957 where I: Iterator<Item=&'a T>, T: Clone
1961 fn next(&mut self) -> Option<T> {
1962 self.it.next().cloned()
1965 fn size_hint(&self) -> (usize, Option<usize>) {
1970 #[stable(feature = "rust1", since = "1.0.0")]
1971 impl<'a, I, T: 'a> DoubleEndedIterator for Cloned<I>
1972 where I: DoubleEndedIterator<Item=&'a T>, T: Clone
1974 fn next_back(&mut self) -> Option<T> {
1975 self.it.next_back().cloned()
1979 #[stable(feature = "rust1", since = "1.0.0")]
1980 impl<'a, I, T: 'a> ExactSizeIterator for Cloned<I>
1981 where I: ExactSizeIterator<Item=&'a T>, T: Clone
1984 /// An iterator that repeats endlessly.
1986 /// This `struct` is created by the [`cycle()`] method on [`Iterator`]. See its
1987 /// documentation for more.
1989 /// [`cycle()`]: trait.Iterator.html#method.cycle
1990 /// [`Iterator`]: trait.Iterator.html
1992 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1993 #[stable(feature = "rust1", since = "1.0.0")]
1994 pub struct Cycle<I> {
1999 #[stable(feature = "rust1", since = "1.0.0")]
2000 impl<I> Iterator for Cycle<I> where I: Clone + Iterator {
2001 type Item = <I as Iterator>::Item;
2004 fn next(&mut self) -> Option<<I as Iterator>::Item> {
2005 match self.iter.next() {
2006 None => { self.iter = self.orig.clone(); self.iter.next() }
2012 fn size_hint(&self) -> (usize, Option<usize>) {
2013 // the cycle iterator is either empty or infinite
2014 match self.orig.size_hint() {
2015 sz @ (0, Some(0)) => sz,
2016 (0, _) => (0, None),
2017 _ => (usize::MAX, None)
2022 /// An iterator that strings two iterators together.
2024 /// This `struct` is created by the [`chain()`] method on [`Iterator`]. See its
2025 /// documentation for more.
2027 /// [`chain()`]: trait.Iterator.html#method.chain
2028 /// [`Iterator`]: trait.Iterator.html
2030 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2031 #[stable(feature = "rust1", since = "1.0.0")]
2032 pub struct Chain<A, B> {
2038 // The iterator protocol specifies that iteration ends with the return value
2039 // `None` from `.next()` (or `.next_back()`) and it is unspecified what
2040 // further calls return. The chain adaptor must account for this since it uses
2041 // two subiterators.
2043 // It uses three states:
2045 // - Both: `a` and `b` are remaining
2046 // - Front: `a` remaining
2047 // - Back: `b` remaining
2049 // The fourth state (neither iterator is remaining) only occurs after Chain has
2050 // returned None once, so we don't need to store this state.
2053 // both front and back iterator are remaining
2055 // only front is remaining
2057 // only back is remaining
2061 #[stable(feature = "rust1", since = "1.0.0")]
2062 impl<A, B> Iterator for Chain<A, B> where
2064 B: Iterator<Item = A::Item>
2066 type Item = A::Item;
2069 fn next(&mut self) -> Option<A::Item> {
2071 ChainState::Both => match self.a.next() {
2072 elt @ Some(..) => elt,
2074 self.state = ChainState::Back;
2078 ChainState::Front => self.a.next(),
2079 ChainState::Back => self.b.next(),
2084 fn count(self) -> usize {
2086 ChainState::Both => self.a.count() + self.b.count(),
2087 ChainState::Front => self.a.count(),
2088 ChainState::Back => self.b.count(),
2093 fn nth(&mut self, mut n: usize) -> Option<A::Item> {
2095 ChainState::Both | ChainState::Front => {
2096 for x in self.a.by_ref() {
2102 if let ChainState::Both = self.state {
2103 self.state = ChainState::Back;
2106 ChainState::Back => {}
2108 if let ChainState::Back = self.state {
2116 fn last(self) -> Option<A::Item> {
2118 ChainState::Both => {
2119 // Must exhaust a before b.
2120 let a_last = self.a.last();
2121 let b_last = self.b.last();
2124 ChainState::Front => self.a.last(),
2125 ChainState::Back => self.b.last()
2130 fn size_hint(&self) -> (usize, Option<usize>) {
2131 let (a_lower, a_upper) = self.a.size_hint();
2132 let (b_lower, b_upper) = self.b.size_hint();
2134 let lower = a_lower.saturating_add(b_lower);
2136 let upper = match (a_upper, b_upper) {
2137 (Some(x), Some(y)) => x.checked_add(y),
2145 #[stable(feature = "rust1", since = "1.0.0")]
2146 impl<A, B> DoubleEndedIterator for Chain<A, B> where
2147 A: DoubleEndedIterator,
2148 B: DoubleEndedIterator<Item=A::Item>,
2151 fn next_back(&mut self) -> Option<A::Item> {
2153 ChainState::Both => match self.b.next_back() {
2154 elt @ Some(..) => elt,
2156 self.state = ChainState::Front;
2160 ChainState::Front => self.a.next_back(),
2161 ChainState::Back => self.b.next_back(),
2166 /// An iterator that iterates two other iterators simultaneously.
2168 /// This `struct` is created by the [`zip()`] method on [`Iterator`]. See its
2169 /// documentation for more.
2171 /// [`zip()`]: trait.Iterator.html#method.zip
2172 /// [`Iterator`]: trait.Iterator.html
2174 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2175 #[stable(feature = "rust1", since = "1.0.0")]
2176 pub struct Zip<A, B> {
2181 #[stable(feature = "rust1", since = "1.0.0")]
2182 impl<A, B> Iterator for Zip<A, B> where A: Iterator, B: Iterator
2184 type Item = (A::Item, B::Item);
2187 fn next(&mut self) -> Option<(A::Item, B::Item)> {
2188 self.a.next().and_then(|x| {
2189 self.b.next().and_then(|y| {
2196 fn size_hint(&self) -> (usize, Option<usize>) {
2197 let (a_lower, a_upper) = self.a.size_hint();
2198 let (b_lower, b_upper) = self.b.size_hint();
2200 let lower = cmp::min(a_lower, b_lower);
2202 let upper = match (a_upper, b_upper) {
2203 (Some(x), Some(y)) => Some(cmp::min(x,y)),
2204 (Some(x), None) => Some(x),
2205 (None, Some(y)) => Some(y),
2206 (None, None) => None
2213 #[stable(feature = "rust1", since = "1.0.0")]
2214 impl<A, B> DoubleEndedIterator for Zip<A, B> where
2215 A: DoubleEndedIterator + ExactSizeIterator,
2216 B: DoubleEndedIterator + ExactSizeIterator,
2219 fn next_back(&mut self) -> Option<(A::Item, B::Item)> {
2220 let a_sz = self.a.len();
2221 let b_sz = self.b.len();
2223 // Adjust a, b to equal length
2225 for _ in 0..a_sz - b_sz { self.a.next_back(); }
2227 for _ in 0..b_sz - a_sz { self.b.next_back(); }
2230 match (self.a.next_back(), self.b.next_back()) {
2231 (Some(x), Some(y)) => Some((x, y)),
2232 (None, None) => None,
2233 _ => unreachable!(),
2238 /// An iterator that maps the values of `iter` with `f`.
2240 /// This `struct` is created by the [`map()`] method on [`Iterator`]. See its
2241 /// documentation for more.
2243 /// [`map()`]: trait.Iterator.html#method.map
2244 /// [`Iterator`]: trait.Iterator.html
2245 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2246 #[stable(feature = "rust1", since = "1.0.0")]
2248 pub struct Map<I, F> {
2253 #[stable(feature = "rust1", since = "1.0.0")]
2254 impl<B, I: Iterator, F> Iterator for Map<I, F> where F: FnMut(I::Item) -> B {
2258 fn next(&mut self) -> Option<B> {
2259 self.iter.next().map(&mut self.f)
2263 fn size_hint(&self) -> (usize, Option<usize>) {
2264 self.iter.size_hint()
2268 #[stable(feature = "rust1", since = "1.0.0")]
2269 impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for Map<I, F> where
2270 F: FnMut(I::Item) -> B,
2273 fn next_back(&mut self) -> Option<B> {
2274 self.iter.next_back().map(&mut self.f)
2278 /// An iterator that filters the elements of `iter` with `predicate`.
2280 /// This `struct` is created by the [`filter()`] method on [`Iterator`]. See its
2281 /// documentation for more.
2283 /// [`filter()`]: trait.Iterator.html#method.filter
2284 /// [`Iterator`]: trait.Iterator.html
2285 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2286 #[stable(feature = "rust1", since = "1.0.0")]
2288 pub struct Filter<I, P> {
2293 #[stable(feature = "rust1", since = "1.0.0")]
2294 impl<I: Iterator, P> Iterator for Filter<I, P> where P: FnMut(&I::Item) -> bool {
2295 type Item = I::Item;
2298 fn next(&mut self) -> Option<I::Item> {
2299 for x in self.iter.by_ref() {
2300 if (self.predicate)(&x) {
2308 fn size_hint(&self) -> (usize, Option<usize>) {
2309 let (_, upper) = self.iter.size_hint();
2310 (0, upper) // can't know a lower bound, due to the predicate
2314 #[stable(feature = "rust1", since = "1.0.0")]
2315 impl<I: DoubleEndedIterator, P> DoubleEndedIterator for Filter<I, P>
2316 where P: FnMut(&I::Item) -> bool,
2319 fn next_back(&mut self) -> Option<I::Item> {
2320 for x in self.iter.by_ref().rev() {
2321 if (self.predicate)(&x) {
2329 /// An iterator that uses `f` to both filter and map elements from `iter`.
2331 /// This `struct` is created by the [`filter_map()`] method on [`Iterator`]. See its
2332 /// documentation for more.
2334 /// [`filter_map()`]: trait.Iterator.html#method.filter_map
2335 /// [`Iterator`]: trait.Iterator.html
2336 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2337 #[stable(feature = "rust1", since = "1.0.0")]
2339 pub struct FilterMap<I, F> {
2344 #[stable(feature = "rust1", since = "1.0.0")]
2345 impl<B, I: Iterator, F> Iterator for FilterMap<I, F>
2346 where F: FnMut(I::Item) -> Option<B>,
2351 fn next(&mut self) -> Option<B> {
2352 for x in self.iter.by_ref() {
2353 if let Some(y) = (self.f)(x) {
2361 fn size_hint(&self) -> (usize, Option<usize>) {
2362 let (_, upper) = self.iter.size_hint();
2363 (0, upper) // can't know a lower bound, due to the predicate
2367 #[stable(feature = "rust1", since = "1.0.0")]
2368 impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for FilterMap<I, F>
2369 where F: FnMut(I::Item) -> Option<B>,
2372 fn next_back(&mut self) -> Option<B> {
2373 for x in self.iter.by_ref().rev() {
2374 if let Some(y) = (self.f)(x) {
2382 /// An iterator that yields the current count and the element during iteration.
2384 /// This `struct` is created by the [`enumerate()`] method on [`Iterator`]. See its
2385 /// documentation for more.
2387 /// [`enumerate()`]: trait.Iterator.html#method.enumerate
2388 /// [`Iterator`]: trait.Iterator.html
2390 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2391 #[stable(feature = "rust1", since = "1.0.0")]
2392 pub struct Enumerate<I> {
2397 #[stable(feature = "rust1", since = "1.0.0")]
2398 impl<I> Iterator for Enumerate<I> where I: Iterator {
2399 type Item = (usize, <I as Iterator>::Item);
2401 /// # Overflow Behavior
2403 /// The method does no guarding against overflows, so enumerating more than
2404 /// `usize::MAX` elements either produces the wrong result or panics. If
2405 /// debug assertions are enabled, a panic is guaranteed.
2409 /// Might panic if the index of the element overflows a `usize`.
2411 fn next(&mut self) -> Option<(usize, <I as Iterator>::Item)> {
2412 self.iter.next().map(|a| {
2413 let ret = (self.count, a);
2414 // Possible undefined overflow.
2421 fn size_hint(&self) -> (usize, Option<usize>) {
2422 self.iter.size_hint()
2426 fn nth(&mut self, n: usize) -> Option<(usize, I::Item)> {
2427 self.iter.nth(n).map(|a| {
2428 let i = self.count + n;
2435 fn count(self) -> usize {
2440 #[stable(feature = "rust1", since = "1.0.0")]
2441 impl<I> DoubleEndedIterator for Enumerate<I> where
2442 I: ExactSizeIterator + DoubleEndedIterator
2445 fn next_back(&mut self) -> Option<(usize, <I as Iterator>::Item)> {
2446 self.iter.next_back().map(|a| {
2447 let len = self.iter.len();
2448 // Can safely add, `ExactSizeIterator` promises that the number of
2449 // elements fits into a `usize`.
2450 (self.count + len, a)
2455 /// An iterator with a `peek()` that returns an optional reference to the next
2458 /// This `struct` is created by the [`peekable()`] method on [`Iterator`]. See its
2459 /// documentation for more.
2461 /// [`peekable()`]: trait.Iterator.html#method.peekable
2462 /// [`Iterator`]: trait.Iterator.html
2464 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2465 #[stable(feature = "rust1", since = "1.0.0")]
2466 pub struct Peekable<I: Iterator> {
2468 peeked: Option<I::Item>,
2471 #[stable(feature = "rust1", since = "1.0.0")]
2472 impl<I: Iterator> Iterator for Peekable<I> {
2473 type Item = I::Item;
2476 fn next(&mut self) -> Option<I::Item> {
2478 Some(_) => self.peeked.take(),
2479 None => self.iter.next(),
2484 fn count(self) -> usize {
2485 (if self.peeked.is_some() { 1 } else { 0 }) + self.iter.count()
2489 fn nth(&mut self, n: usize) -> Option<I::Item> {
2491 Some(_) if n == 0 => self.peeked.take(),
2496 None => self.iter.nth(n)
2501 fn last(self) -> Option<I::Item> {
2502 self.iter.last().or(self.peeked)
2506 fn size_hint(&self) -> (usize, Option<usize>) {
2507 let (lo, hi) = self.iter.size_hint();
2508 if self.peeked.is_some() {
2509 let lo = lo.saturating_add(1);
2510 let hi = hi.and_then(|x| x.checked_add(1));
2518 #[stable(feature = "rust1", since = "1.0.0")]
2519 impl<I: ExactSizeIterator> ExactSizeIterator for Peekable<I> {}
2521 #[stable(feature = "rust1", since = "1.0.0")]
2522 impl<I: Iterator> Peekable<I> {
2523 /// Returns a reference to the next element of the iterator with out
2524 /// advancing it, or None if the iterator is exhausted.
2526 #[stable(feature = "rust1", since = "1.0.0")]
2527 pub fn peek(&mut self) -> Option<&I::Item> {
2528 if self.peeked.is_none() {
2529 self.peeked = self.iter.next();
2532 Some(ref value) => Some(value),
2537 /// Checks whether peekable iterator is empty or not.
2539 pub fn is_empty(&mut self) -> bool {
2540 self.peek().is_none()
2544 /// An iterator that rejects elements while `predicate` is true.
2546 /// This `struct` is created by the [`skip_while()`] method on [`Iterator`]. See its
2547 /// documentation for more.
2549 /// [`skip_while()`]: trait.Iterator.html#method.skip_while
2550 /// [`Iterator`]: trait.Iterator.html
2551 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2552 #[stable(feature = "rust1", since = "1.0.0")]
2554 pub struct SkipWhile<I, P> {
2560 #[stable(feature = "rust1", since = "1.0.0")]
2561 impl<I: Iterator, P> Iterator for SkipWhile<I, P>
2562 where P: FnMut(&I::Item) -> bool
2564 type Item = I::Item;
2567 fn next(&mut self) -> Option<I::Item> {
2568 for x in self.iter.by_ref() {
2569 if self.flag || !(self.predicate)(&x) {
2578 fn size_hint(&self) -> (usize, Option<usize>) {
2579 let (_, upper) = self.iter.size_hint();
2580 (0, upper) // can't know a lower bound, due to the predicate
2584 /// An iterator that only accepts elements while `predicate` is true.
2586 /// This `struct` is created by the [`take_while()`] method on [`Iterator`]. See its
2587 /// documentation for more.
2589 /// [`take_while()`]: trait.Iterator.html#method.take_while
2590 /// [`Iterator`]: trait.Iterator.html
2591 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2592 #[stable(feature = "rust1", since = "1.0.0")]
2594 pub struct TakeWhile<I, P> {
2600 #[stable(feature = "rust1", since = "1.0.0")]
2601 impl<I: Iterator, P> Iterator for TakeWhile<I, P>
2602 where P: FnMut(&I::Item) -> bool
2604 type Item = I::Item;
2607 fn next(&mut self) -> Option<I::Item> {
2611 self.iter.next().and_then(|x| {
2612 if (self.predicate)(&x) {
2623 fn size_hint(&self) -> (usize, Option<usize>) {
2624 let (_, upper) = self.iter.size_hint();
2625 (0, upper) // can't know a lower bound, due to the predicate
2629 /// An iterator that skips over `n` elements of `iter`.
2631 /// This `struct` is created by the [`skip()`] method on [`Iterator`]. See its
2632 /// documentation for more.
2634 /// [`skip()`]: trait.Iterator.html#method.skip
2635 /// [`Iterator`]: trait.Iterator.html
2637 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2638 #[stable(feature = "rust1", since = "1.0.0")]
2639 pub struct Skip<I> {
2644 #[stable(feature = "rust1", since = "1.0.0")]
2645 impl<I> Iterator for Skip<I> where I: Iterator {
2646 type Item = <I as Iterator>::Item;
2649 fn next(&mut self) -> Option<I::Item> {
2655 self.iter.nth(old_n)
2660 fn nth(&mut self, n: usize) -> Option<I::Item> {
2661 // Can't just add n + self.n due to overflow.
2665 let to_skip = self.n;
2668 if self.iter.nth(to_skip-1).is_none() {
2676 fn count(self) -> usize {
2677 self.iter.count().saturating_sub(self.n)
2681 fn last(mut self) -> Option<I::Item> {
2685 let next = self.next();
2687 // recurse. n should be 0.
2688 self.last().or(next)
2696 fn size_hint(&self) -> (usize, Option<usize>) {
2697 let (lower, upper) = self.iter.size_hint();
2699 let lower = lower.saturating_sub(self.n);
2700 let upper = upper.map(|x| x.saturating_sub(self.n));
2706 #[stable(feature = "rust1", since = "1.0.0")]
2707 impl<I> ExactSizeIterator for Skip<I> where I: ExactSizeIterator {}
2709 /// An iterator that only iterates over the first `n` iterations of `iter`.
2711 /// This `struct` is created by the [`take()`] method on [`Iterator`]. See its
2712 /// documentation for more.
2714 /// [`take()`]: trait.Iterator.html#method.take
2715 /// [`Iterator`]: trait.Iterator.html
2717 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2718 #[stable(feature = "rust1", since = "1.0.0")]
2719 pub struct Take<I> {
2724 #[stable(feature = "rust1", since = "1.0.0")]
2725 impl<I> Iterator for Take<I> where I: Iterator{
2726 type Item = <I as Iterator>::Item;
2729 fn next(&mut self) -> Option<<I as Iterator>::Item> {
2739 fn nth(&mut self, n: usize) -> Option<I::Item> {
2745 self.iter.nth(self.n - 1);
2753 fn size_hint(&self) -> (usize, Option<usize>) {
2754 let (lower, upper) = self.iter.size_hint();
2756 let lower = cmp::min(lower, self.n);
2758 let upper = match upper {
2759 Some(x) if x < self.n => Some(x),
2767 #[stable(feature = "rust1", since = "1.0.0")]
2768 impl<I> ExactSizeIterator for Take<I> where I: ExactSizeIterator {}
2771 /// An iterator to maintain state while iterating another iterator.
2773 /// This `struct` is created by the [`scan()`] method on [`Iterator`]. See its
2774 /// documentation for more.
2776 /// [`scan()`]: trait.Iterator.html#method.scan
2777 /// [`Iterator`]: trait.Iterator.html
2778 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2779 #[stable(feature = "rust1", since = "1.0.0")]
2781 pub struct Scan<I, St, F> {
2787 #[stable(feature = "rust1", since = "1.0.0")]
2788 impl<B, I, St, F> Iterator for Scan<I, St, F> where
2790 F: FnMut(&mut St, I::Item) -> Option<B>,
2795 fn next(&mut self) -> Option<B> {
2796 self.iter.next().and_then(|a| (self.f)(&mut self.state, a))
2800 fn size_hint(&self) -> (usize, Option<usize>) {
2801 let (_, upper) = self.iter.size_hint();
2802 (0, upper) // can't know a lower bound, due to the scan function
2806 /// An iterator that maps each element to an iterator, and yields the elements
2807 /// of the produced iterators.
2809 /// This `struct` is created by the [`flat_map()`] method on [`Iterator`]. See its
2810 /// documentation for more.
2812 /// [`flat_map()`]: trait.Iterator.html#method.flat_map
2813 /// [`Iterator`]: trait.Iterator.html
2814 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2815 #[stable(feature = "rust1", since = "1.0.0")]
2817 pub struct FlatMap<I, U: IntoIterator, F> {
2820 frontiter: Option<U::IntoIter>,
2821 backiter: Option<U::IntoIter>,
2824 #[stable(feature = "rust1", since = "1.0.0")]
2825 impl<I: Iterator, U: IntoIterator, F> Iterator for FlatMap<I, U, F>
2826 where F: FnMut(I::Item) -> U,
2828 type Item = U::Item;
2831 fn next(&mut self) -> Option<U::Item> {
2833 if let Some(ref mut inner) = self.frontiter {
2834 if let Some(x) = inner.by_ref().next() {
2838 match self.iter.next().map(&mut self.f) {
2839 None => return self.backiter.as_mut().and_then(|it| it.next()),
2840 next => self.frontiter = next.map(IntoIterator::into_iter),
2846 fn size_hint(&self) -> (usize, Option<usize>) {
2847 let (flo, fhi) = self.frontiter.as_ref().map_or((0, Some(0)), |it| it.size_hint());
2848 let (blo, bhi) = self.backiter.as_ref().map_or((0, Some(0)), |it| it.size_hint());
2849 let lo = flo.saturating_add(blo);
2850 match (self.iter.size_hint(), fhi, bhi) {
2851 ((0, Some(0)), Some(a), Some(b)) => (lo, a.checked_add(b)),
2857 #[stable(feature = "rust1", since = "1.0.0")]
2858 impl<I: DoubleEndedIterator, U, F> DoubleEndedIterator for FlatMap<I, U, F> where
2859 F: FnMut(I::Item) -> U,
2861 U::IntoIter: DoubleEndedIterator
2864 fn next_back(&mut self) -> Option<U::Item> {
2866 if let Some(ref mut inner) = self.backiter {
2867 if let Some(y) = inner.next_back() {
2871 match self.iter.next_back().map(&mut self.f) {
2872 None => return self.frontiter.as_mut().and_then(|it| it.next_back()),
2873 next => self.backiter = next.map(IntoIterator::into_iter),
2879 /// An iterator that yields `None` forever after the underlying iterator
2880 /// yields `None` once.
2882 /// This `struct` is created by the [`fuse()`] method on [`Iterator`]. See its
2883 /// documentation for more.
2885 /// [`fuse()`]: trait.Iterator.html#method.fuse
2886 /// [`Iterator`]: trait.Iterator.html
2888 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2889 #[stable(feature = "rust1", since = "1.0.0")]
2890 pub struct Fuse<I> {
2895 #[stable(feature = "rust1", since = "1.0.0")]
2896 impl<I> Iterator for Fuse<I> where I: Iterator {
2897 type Item = <I as Iterator>::Item;
2900 fn next(&mut self) -> Option<<I as Iterator>::Item> {
2904 let next = self.iter.next();
2905 self.done = next.is_none();
2911 fn nth(&mut self, n: usize) -> Option<I::Item> {
2915 let nth = self.iter.nth(n);
2916 self.done = nth.is_none();
2922 fn last(self) -> Option<I::Item> {
2931 fn count(self) -> usize {
2940 fn size_hint(&self) -> (usize, Option<usize>) {
2944 self.iter.size_hint()
2949 #[stable(feature = "rust1", since = "1.0.0")]
2950 impl<I> DoubleEndedIterator for Fuse<I> where I: DoubleEndedIterator {
2952 fn next_back(&mut self) -> Option<<I as Iterator>::Item> {
2956 let next = self.iter.next_back();
2957 self.done = next.is_none();
2963 #[stable(feature = "rust1", since = "1.0.0")]
2964 impl<I> ExactSizeIterator for Fuse<I> where I: ExactSizeIterator {}
2966 /// An iterator that calls a function with a reference to each element before
2969 /// This `struct` is created by the [`inspect()`] method on [`Iterator`]. See its
2970 /// documentation for more.
2972 /// [`inspect()`]: trait.Iterator.html#method.inspect
2973 /// [`Iterator`]: trait.Iterator.html
2974 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2975 #[stable(feature = "rust1", since = "1.0.0")]
2977 pub struct Inspect<I, F> {
2982 impl<I: Iterator, F> Inspect<I, F> where F: FnMut(&I::Item) {
2984 fn do_inspect(&mut self, elt: Option<I::Item>) -> Option<I::Item> {
2985 if let Some(ref a) = elt {
2993 #[stable(feature = "rust1", since = "1.0.0")]
2994 impl<I: Iterator, F> Iterator for Inspect<I, F> where F: FnMut(&I::Item) {
2995 type Item = I::Item;
2998 fn next(&mut self) -> Option<I::Item> {
2999 let next = self.iter.next();
3000 self.do_inspect(next)
3004 fn size_hint(&self) -> (usize, Option<usize>) {
3005 self.iter.size_hint()
3009 #[stable(feature = "rust1", since = "1.0.0")]
3010 impl<I: DoubleEndedIterator, F> DoubleEndedIterator for Inspect<I, F>
3011 where F: FnMut(&I::Item),
3014 fn next_back(&mut self) -> Option<I::Item> {
3015 let next = self.iter.next_back();
3016 self.do_inspect(next)
3020 /// Objects that can be stepped over in both directions.
3022 /// The `steps_between` function provides a way to efficiently compare
3023 /// two `Step` objects.
3024 #[unstable(feature = "step_trait",
3025 reason = "likely to be replaced by finer-grained traits",
3027 pub trait Step: PartialOrd + Sized {
3028 /// Steps `self` if possible.
3029 fn step(&self, by: &Self) -> Option<Self>;
3031 /// Returns the number of steps between two step objects. The count is
3032 /// inclusive of `start` and exclusive of `end`.
3034 /// Returns `None` if it is not possible to calculate `steps_between`
3035 /// without overflow.
3036 fn steps_between(start: &Self, end: &Self, by: &Self) -> Option<usize>;
3039 macro_rules! step_impl_unsigned {
3043 fn step(&self, by: &$t) -> Option<$t> {
3044 (*self).checked_add(*by)
3047 #[allow(trivial_numeric_casts)]
3048 fn steps_between(start: &$t, end: &$t, by: &$t) -> Option<usize> {
3049 if *by == 0 { return None; }
3051 // Note: We assume $t <= usize here
3052 let diff = (*end - *start) as usize;
3053 let by = *by as usize;
3066 macro_rules! step_impl_signed {
3070 fn step(&self, by: &$t) -> Option<$t> {
3071 (*self).checked_add(*by)
3074 #[allow(trivial_numeric_casts)]
3075 fn steps_between(start: &$t, end: &$t, by: &$t) -> Option<usize> {
3076 if *by == 0 { return None; }
3083 // Note: We assume $t <= isize here
3084 // Use .wrapping_sub and cast to usize to compute the
3085 // difference that may not fit inside the range of isize.
3086 diff = (*end as isize).wrapping_sub(*start as isize) as usize;
3087 by_u = *by as usize;
3092 diff = (*start as isize).wrapping_sub(*end as isize) as usize;
3093 by_u = (*by as isize).wrapping_mul(-1) as usize;
3095 if diff % by_u > 0 {
3096 Some(diff / by_u + 1)
3105 macro_rules! step_impl_no_between {
3109 fn step(&self, by: &$t) -> Option<$t> {
3110 (*self).checked_add(*by)
3113 fn steps_between(_a: &$t, _b: &$t, _by: &$t) -> Option<usize> {
3120 step_impl_unsigned!(usize u8 u16 u32);
3121 step_impl_signed!(isize i8 i16 i32);
3122 #[cfg(target_pointer_width = "64")]
3123 step_impl_unsigned!(u64);
3124 #[cfg(target_pointer_width = "64")]
3125 step_impl_signed!(i64);
3126 // If the target pointer width is not 64-bits, we
3127 // assume here that it is less than 64-bits.
3128 #[cfg(not(target_pointer_width = "64"))]
3129 step_impl_no_between!(u64 i64);
3131 /// An adapter for stepping range iterators by a custom amount.
3133 /// The resulting iterator handles overflow by stopping. The `A`
3134 /// parameter is the type being iterated over, while `R` is the range
3135 /// type (usually one of `std::ops::{Range, RangeFrom}`.
3137 #[unstable(feature = "step_by", reason = "recent addition",
3139 pub struct StepBy<A, R> {
3144 impl<A: Step> RangeFrom<A> {
3145 /// Creates an iterator starting at the same point, but stepping by
3146 /// the given amount at each iteration.
3151 /// for i in (0u8..).step_by(2) {
3152 /// println!("{}", i);
3156 /// This prints all even `u8` values.
3157 #[unstable(feature = "step_by", reason = "recent addition",
3159 pub fn step_by(self, by: A) -> StepBy<A, Self> {
3167 impl<A: Step> ops::Range<A> {
3168 /// Creates an iterator with the same range, but stepping by the
3169 /// given amount at each iteration.
3171 /// The resulting iterator handles overflow by stopping.
3176 /// #![feature(step_by)]
3178 /// for i in (0..10).step_by(2) {
3179 /// println!("{}", i);
3192 #[unstable(feature = "step_by", reason = "recent addition",
3194 pub fn step_by(self, by: A) -> StepBy<A, Self> {
3202 #[stable(feature = "rust1", since = "1.0.0")]
3203 impl<A> Iterator for StepBy<A, RangeFrom<A>> where
3205 for<'a> &'a A: Add<&'a A, Output = A>
3210 fn next(&mut self) -> Option<A> {
3211 let mut n = &self.range.start + &self.step_by;
3212 mem::swap(&mut n, &mut self.range.start);
3217 fn size_hint(&self) -> (usize, Option<usize>) {
3218 (usize::MAX, None) // Too bad we can't specify an infinite lower bound
3222 /// An iterator over the range [start, stop]
3224 #[unstable(feature = "range_inclusive",
3225 reason = "likely to be replaced by range notation and adapters",
3227 pub struct RangeInclusive<A> {
3228 range: ops::Range<A>,
3232 /// Returns an iterator over the range [start, stop].
3234 #[unstable(feature = "range_inclusive",
3235 reason = "likely to be replaced by range notation and adapters",
3237 pub fn range_inclusive<A>(start: A, stop: A) -> RangeInclusive<A>
3238 where A: Step + One + Clone
3246 #[unstable(feature = "range_inclusive",
3247 reason = "likely to be replaced by range notation and adapters",
3249 impl<A> Iterator for RangeInclusive<A> where
3250 A: PartialEq + Step + One + Clone,
3251 for<'a> &'a A: Add<&'a A, Output = A>
3256 fn next(&mut self) -> Option<A> {
3257 self.range.next().or_else(|| {
3258 if !self.done && self.range.start == self.range.end {
3260 Some(self.range.end.clone())
3268 fn size_hint(&self) -> (usize, Option<usize>) {
3269 let (lo, hi) = self.range.size_hint();
3273 let lo = lo.saturating_add(1);
3274 let hi = hi.and_then(|x| x.checked_add(1));
3280 #[unstable(feature = "range_inclusive",
3281 reason = "likely to be replaced by range notation and adapters",
3283 impl<A> DoubleEndedIterator for RangeInclusive<A> where
3284 A: PartialEq + Step + One + Clone,
3285 for<'a> &'a A: Add<&'a A, Output = A>,
3286 for<'a> &'a A: Sub<Output=A>
3289 fn next_back(&mut self) -> Option<A> {
3290 if self.range.end > self.range.start {
3291 let result = self.range.end.clone();
3292 self.range.end = &self.range.end - &A::one();
3294 } else if !self.done && self.range.start == self.range.end {
3296 Some(self.range.end.clone())
3303 #[stable(feature = "rust1", since = "1.0.0")]
3304 impl<A: Step + Zero + Clone> Iterator for StepBy<A, ops::Range<A>> {
3308 fn next(&mut self) -> Option<A> {
3309 let rev = self.step_by < A::zero();
3310 if (rev && self.range.start > self.range.end) ||
3311 (!rev && self.range.start < self.range.end)
3313 match self.range.start.step(&self.step_by) {
3315 mem::swap(&mut self.range.start, &mut n);
3319 let mut n = self.range.end.clone();
3320 mem::swap(&mut self.range.start, &mut n);
3330 fn size_hint(&self) -> (usize, Option<usize>) {
3331 match Step::steps_between(&self.range.start,
3334 Some(hint) => (hint, Some(hint)),
3340 macro_rules! range_exact_iter_impl {
3342 #[stable(feature = "rust1", since = "1.0.0")]
3343 impl ExactSizeIterator for ops::Range<$t> { }
3347 #[stable(feature = "rust1", since = "1.0.0")]
3348 impl<A: Step + One> Iterator for ops::Range<A> where
3349 for<'a> &'a A: Add<&'a A, Output = A>
3354 fn next(&mut self) -> Option<A> {
3355 if self.start < self.end {
3356 let mut n = &self.start + &A::one();
3357 mem::swap(&mut n, &mut self.start);
3365 fn size_hint(&self) -> (usize, Option<usize>) {
3366 match Step::steps_between(&self.start, &self.end, &A::one()) {
3367 Some(hint) => (hint, Some(hint)),
3373 // Ranges of u64 and i64 are excluded because they cannot guarantee having
3374 // a length <= usize::MAX, which is required by ExactSizeIterator.
3375 range_exact_iter_impl!(usize u8 u16 u32 isize i8 i16 i32);
3377 #[stable(feature = "rust1", since = "1.0.0")]
3378 impl<A: Step + One + Clone> DoubleEndedIterator for ops::Range<A> where
3379 for<'a> &'a A: Add<&'a A, Output = A>,
3380 for<'a> &'a A: Sub<&'a A, Output = A>
3383 fn next_back(&mut self) -> Option<A> {
3384 if self.start < self.end {
3385 self.end = &self.end - &A::one();
3386 Some(self.end.clone())
3393 #[stable(feature = "rust1", since = "1.0.0")]
3394 impl<A: Step + One> Iterator for ops::RangeFrom<A> where
3395 for<'a> &'a A: Add<&'a A, Output = A>
3400 fn next(&mut self) -> Option<A> {
3401 let mut n = &self.start + &A::one();
3402 mem::swap(&mut n, &mut self.start);
3407 /// An iterator that repeats an element endlessly.
3409 /// This `struct` is created by the [`repeat()`] function. See its documentation for more.
3411 /// [`repeat()`]: fn.repeat.html
3413 #[stable(feature = "rust1", since = "1.0.0")]
3414 pub struct Repeat<A> {
3418 #[stable(feature = "rust1", since = "1.0.0")]
3419 impl<A: Clone> Iterator for Repeat<A> {
3423 fn next(&mut self) -> Option<A> { Some(self.element.clone()) }
3425 fn size_hint(&self) -> (usize, Option<usize>) { (usize::MAX, None) }
3428 #[stable(feature = "rust1", since = "1.0.0")]
3429 impl<A: Clone> DoubleEndedIterator for Repeat<A> {
3431 fn next_back(&mut self) -> Option<A> { Some(self.element.clone()) }
3434 /// Creates a new iterator that endlessly repeats a single element.
3436 /// The `repeat()` function repeats a single value over and over and over and
3437 /// over and over and 🔁.
3439 /// Infinite iterators like `repeat()` are often used with adapters like
3440 /// [`take()`], in order to make them finite.
3442 /// [`take()`]: trait.Iterator.html#method.take
3451 /// // the number four 4ever:
3452 /// let mut fours = iter::repeat(4);
3454 /// assert_eq!(Some(4), fours.next());
3455 /// assert_eq!(Some(4), fours.next());
3456 /// assert_eq!(Some(4), fours.next());
3457 /// assert_eq!(Some(4), fours.next());
3458 /// assert_eq!(Some(4), fours.next());
3460 /// // yup, still four
3461 /// assert_eq!(Some(4), fours.next());
3464 /// Going finite with [`take()`]:
3469 /// // that last example was too many fours. Let's only have four fours.
3470 /// let mut four_fours = iter::repeat(4).take(4);
3472 /// assert_eq!(Some(4), four_fours.next());
3473 /// assert_eq!(Some(4), four_fours.next());
3474 /// assert_eq!(Some(4), four_fours.next());
3475 /// assert_eq!(Some(4), four_fours.next());
3477 /// // ... and now we're done
3478 /// assert_eq!(None, four_fours.next());
3481 #[stable(feature = "rust1", since = "1.0.0")]
3482 pub fn repeat<T: Clone>(elt: T) -> Repeat<T> {
3483 Repeat{element: elt}
3486 /// An iterator that yields nothing.
3488 /// This `struct` is created by the [`empty()`] function. See its documentation for more.
3490 /// [`empty()`]: fn.empty.html
3491 #[stable(feature = "iter_empty", since = "1.2.0")]
3492 pub struct Empty<T>(marker::PhantomData<T>);
3494 #[stable(feature = "iter_empty", since = "1.2.0")]
3495 impl<T> Iterator for Empty<T> {
3498 fn next(&mut self) -> Option<T> {
3502 fn size_hint(&self) -> (usize, Option<usize>){
3507 #[stable(feature = "iter_empty", since = "1.2.0")]
3508 impl<T> DoubleEndedIterator for Empty<T> {
3509 fn next_back(&mut self) -> Option<T> {
3514 #[stable(feature = "iter_empty", since = "1.2.0")]
3515 impl<T> ExactSizeIterator for Empty<T> {
3516 fn len(&self) -> usize {
3521 // not #[derive] because that adds a Clone bound on T,
3522 // which isn't necessary.
3523 #[stable(feature = "iter_empty", since = "1.2.0")]
3524 impl<T> Clone for Empty<T> {
3525 fn clone(&self) -> Empty<T> {
3526 Empty(marker::PhantomData)
3530 // not #[derive] because that adds a Default bound on T,
3531 // which isn't necessary.
3532 #[stable(feature = "iter_empty", since = "1.2.0")]
3533 impl<T> Default for Empty<T> {
3534 fn default() -> Empty<T> {
3535 Empty(marker::PhantomData)
3539 /// Creates an iterator that yields nothing.
3548 /// // this could have been an iterator over i32, but alas, it's just not.
3549 /// let mut nope = iter::empty::<i32>();
3551 /// assert_eq!(None, nope.next());
3553 #[stable(feature = "iter_empty", since = "1.2.0")]
3554 pub fn empty<T>() -> Empty<T> {
3555 Empty(marker::PhantomData)
3558 /// An iterator that yields an element exactly once.
3560 /// This `struct` is created by the [`once()`] function. See its documentation for more.
3562 /// [`once()`]: fn.once.html
3564 #[stable(feature = "iter_once", since = "1.2.0")]
3565 pub struct Once<T> {
3566 inner: ::option::IntoIter<T>
3569 #[stable(feature = "iter_once", since = "1.2.0")]
3570 impl<T> Iterator for Once<T> {
3573 fn next(&mut self) -> Option<T> {
3577 fn size_hint(&self) -> (usize, Option<usize>) {
3578 self.inner.size_hint()
3582 #[stable(feature = "iter_once", since = "1.2.0")]
3583 impl<T> DoubleEndedIterator for Once<T> {
3584 fn next_back(&mut self) -> Option<T> {
3585 self.inner.next_back()
3589 #[stable(feature = "iter_once", since = "1.2.0")]
3590 impl<T> ExactSizeIterator for Once<T> {
3591 fn len(&self) -> usize {
3596 /// Creates an iterator that yields an element exactly once.
3598 /// This is commonly used to adapt a single value into a [`chain()`] of other
3599 /// kinds of iteration. Maybe you have an iterator that covers almost
3600 /// everything, but you need an extra special case. Maybe you have a function
3601 /// which works on iterators, but you only need to process one value.
3603 /// [`chain()`]: trait.Iterator.html#method.chain
3612 /// // one is the loneliest number
3613 /// let mut one = iter::once(1);
3615 /// assert_eq!(Some(1), one.next());
3617 /// // just one, that's all we get
3618 /// assert_eq!(None, one.next());
3621 /// Chaining together with another iterator. Let's say that we want to iterate
3622 /// over each file of the `.foo` directory, but also a configuration file,
3628 /// use std::path::PathBuf;
3630 /// let dirs = fs::read_dir(".foo").unwrap();
3632 /// // we need to convert from an iterator of DirEntry-s to an iterator of
3633 /// // PathBufs, so we use map
3634 /// let dirs = dirs.map(|file| file.unwrap().path());
3636 /// // now, our iterator just for our config file
3637 /// let config = iter::once(PathBuf::from(".foorc"));
3639 /// // chain the two iterators together into one big iterator
3640 /// let files = dirs.chain(config);
3642 /// // this will give us all of the files in .foo as well as .foorc
3643 /// for f in files {
3644 /// println!("{:?}", f);
3647 #[stable(feature = "iter_once", since = "1.2.0")]
3648 pub fn once<T>(value: T) -> Once<T> {
3649 Once { inner: Some(value).into_iter() }
3652 /// Functions for lexicographical ordering of sequences.
3654 /// Lexicographical ordering through `<`, `<=`, `>=`, `>` requires
3655 /// that the elements implement both `PartialEq` and `PartialOrd`.
3657 /// If two sequences are equal up until the point where one ends,
3658 /// the shorter sequence compares less.
3659 #[deprecated(since = "1.4.0", reason = "use the equivalent methods on `Iterator` instead")]
3660 #[unstable(feature = "iter_order", reason = "needs review and revision",
3664 use cmp::{Eq, Ord, PartialOrd, PartialEq};
3666 use super::Iterator;
3668 /// Compare `a` and `b` for equality using `Eq`
3669 pub fn equals<A, L, R>(a: L, b: R) -> bool where
3671 L: Iterator<Item=A>,
3672 R: Iterator<Item=A>,
3677 /// Order `a` and `b` lexicographically using `Ord`
3678 pub fn cmp<A, L, R>(a: L, b: R) -> cmp::Ordering where
3680 L: Iterator<Item=A>,
3681 R: Iterator<Item=A>,
3686 /// Order `a` and `b` lexicographically using `PartialOrd`
3687 pub fn partial_cmp<L: Iterator, R: Iterator>(a: L, b: R) -> Option<cmp::Ordering> where
3688 L::Item: PartialOrd<R::Item>
3693 /// Compare `a` and `b` for equality (Using partial equality, `PartialEq`)
3694 pub fn eq<L: Iterator, R: Iterator>(a: L, b: R) -> bool where
3695 L::Item: PartialEq<R::Item>,
3700 /// Compares `a` and `b` for nonequality (Using partial equality, `PartialEq`)
3701 pub fn ne<L: Iterator, R: Iterator>(a: L, b: R) -> bool where
3702 L::Item: PartialEq<R::Item>,
3707 /// Returns `a` < `b` lexicographically (Using partial order, `PartialOrd`)
3708 pub fn lt<L: Iterator, R: Iterator>(a: L, b: R) -> bool where
3709 L::Item: PartialOrd<R::Item>,
3714 /// Returns `a` <= `b` lexicographically (Using partial order, `PartialOrd`)
3715 pub fn le<L: Iterator, R: Iterator>(a: L, b: R) -> bool where
3716 L::Item: PartialOrd<R::Item>,
3721 /// Returns `a` > `b` lexicographically (Using partial order, `PartialOrd`)
3722 pub fn gt<L: Iterator, R: Iterator>(a: L, b: R) -> bool where
3723 L::Item: PartialOrd<R::Item>,
3728 /// Returns `a` >= `b` lexicographically (Using partial order, `PartialOrd`)
3729 pub fn ge<L: Iterator, R: Iterator>(a: L, b: R) -> bool where
3730 L::Item: PartialOrd<R::Item>,