1/// Conversion from an [`Iterator`].
2///
3/// By implementing `FromIterator` for a type, you define how it will be
4/// created from an iterator. This is common for types which describe a
5/// collection of some kind.
6///
7/// If you want to create a collection from the contents of an iterator, the
8/// [`Iterator::collect()`] method is preferred. However, when you need to
9/// specify the container type, [`FromIterator::from_iter()`] can be more
10/// readable than using a turbofish (e.g. `::<Vec<_>>()`). See the
11/// [`Iterator::collect()`] documentation for more examples of its use.
12///
13/// See also: [`IntoIterator`].
14///
15/// # Examples
16///
17/// Basic usage:
18///
19/// ```
20/// let five_fives = std::iter::repeat(5).take(5);
21///
22/// let v = Vec::from_iter(five_fives);
23///
24/// assert_eq!(v, vec![5, 5, 5, 5, 5]);
25/// ```
26///
27/// Using [`Iterator::collect()`] to implicitly use `FromIterator`:
28///
29/// ```
30/// let five_fives = std::iter::repeat(5).take(5);
31///
32/// let v: Vec<i32> = five_fives.collect();
33///
34/// assert_eq!(v, vec![5, 5, 5, 5, 5]);
35/// ```
36///
37/// Using [`FromIterator::from_iter()`] as a more readable alternative to
38/// [`Iterator::collect()`]:
39///
40/// ```
41/// use std::collections::VecDeque;
42/// let first = (0..10).collect::<VecDeque<i32>>();
43/// let second = VecDeque::from_iter(0..10);
44///
45/// assert_eq!(first, second);
46/// ```
47///
48/// Implementing `FromIterator` for your type:
49///
50/// ```
51/// // A sample collection, that's just a wrapper over Vec<T>
52/// #[derive(Debug)]
53/// struct MyCollection(Vec<i32>);
54///
55/// // Let's give it some methods so we can create one and add things
56/// // to it.
57/// impl MyCollection {
58/// fn new() -> MyCollection {
59/// MyCollection(Vec::new())
60/// }
61///
62/// fn add(&mut self, elem: i32) {
63/// self.0.push(elem);
64/// }
65/// }
66///
67/// // and we'll implement FromIterator
68/// impl FromIterator<i32> for MyCollection {
69/// fn from_iter<I: IntoIterator<Item=i32>>(iter: I) -> Self {
70/// let mut c = MyCollection::new();
71///
72/// for i in iter {
73/// c.add(i);
74/// }
75///
76/// c
77/// }
78/// }
79///
80/// // Now we can make a new iterator...
81/// let iter = (0..5).into_iter();
82///
83/// // ... and make a MyCollection out of it
84/// let c = MyCollection::from_iter(iter);
85///
86/// assert_eq!(c.0, vec![0, 1, 2, 3, 4]);
87///
88/// // collect works too!
89///
90/// let iter = (0..5).into_iter();
91/// let c: MyCollection = iter.collect();
92///
93/// assert_eq!(c.0, vec![0, 1, 2, 3, 4]);
94/// ```
95#[stable(feature = "rust1", since = "1.0.0")]
96#[rustc_on_unimplemented(
97 on(
98 _Self = "&[{A}]",
99 message = "a slice of type `{Self}` cannot be built since we need to store the elements somewhere",
100 label = "try explicitly collecting into a `Vec<{A}>`",
101 ),
102 on(
103 all(A = "{integer}", any(_Self = "&[{integral}]",)),
104 message = "a slice of type `{Self}` cannot be built since we need to store the elements somewhere",
105 label = "try explicitly collecting into a `Vec<{A}>`",
106 ),
107 on(
108 _Self = "[{A}]",
109 message = "a slice of type `{Self}` cannot be built since `{Self}` has no definite size",
110 label = "try explicitly collecting into a `Vec<{A}>`",
111 ),
112 on(
113 all(A = "{integer}", any(_Self = "[{integral}]",)),
114 message = "a slice of type `{Self}` cannot be built since `{Self}` has no definite size",
115 label = "try explicitly collecting into a `Vec<{A}>`",
116 ),
117 on(
118 _Self = "[{A}; _]",
119 message = "an array of type `{Self}` cannot be built directly from an iterator",
120 label = "try collecting into a `Vec<{A}>`, then using `.try_into()`",
121 ),
122 on(
123 all(A = "{integer}", any(_Self = "[{integral}; _]",)),
124 message = "an array of type `{Self}` cannot be built directly from an iterator",
125 label = "try collecting into a `Vec<{A}>`, then using `.try_into()`",
126 ),
127 message = "a value of type `{Self}` cannot be built from an iterator \
128 over elements of type `{A}`",
129 label = "value of type `{Self}` cannot be built from `std::iter::Iterator<Item={A}>`"
130)]
131#[rustc_diagnostic_item = "FromIterator"]
132pub trait FromIterator<A>: Sized {
133 /// Creates a value from an iterator.
134 ///
135 /// See the [module-level documentation] for more.
136 ///
137 /// [module-level documentation]: crate::iter
138 ///
139 /// # Examples
140 ///
141 /// ```
142 /// let five_fives = std::iter::repeat(5).take(5);
143 ///
144 /// let v = Vec::from_iter(five_fives);
145 ///
146 /// assert_eq!(v, vec![5, 5, 5, 5, 5]);
147 /// ```
148 #[stable(feature = "rust1", since = "1.0.0")]
149 #[rustc_diagnostic_item = "from_iter_fn"]
150 fn from_iter<T: IntoIterator<Item = A>>(iter: T) -> Self;
151}
152
153/// This implementation turns an iterator of tuples into a tuple of types which implement
154/// [`Default`] and [`Extend`].
155///
156/// This is similar to [`Iterator::unzip`], but is also composable with other [`FromIterator`]
157/// implementations:
158///
159/// ```rust
160/// # fn main() -> Result<(), core::num::ParseIntError> {
161/// let string = "1,2,123,4";
162///
163/// let (numbers, lengths): (Vec<_>, Vec<_>) = string
164/// .split(',')
165/// .map(|s| s.parse().map(|n: u32| (n, s.len())))
166/// .collect::<Result<_, _>>()?;
167///
168/// assert_eq!(numbers, [1, 2, 123, 4]);
169/// assert_eq!(lengths, [1, 1, 3, 1]);
170/// # Ok(()) }
171/// ```
172#[stable(feature = "from_iterator_for_tuple", since = "CURRENT_RUSTC_VERSION")]
173impl<A, B, AE, BE> FromIterator<(AE, BE)> for (A, B)
174where
175 A: Default + Extend<AE>,
176 B: Default + Extend<BE>,
177{
178 fn from_iter<I: IntoIterator<Item = (AE, BE)>>(iter: I) -> Self {
179 let mut res: (A, B) = <(A, B)>::default();
180 res.extend(iter);
181
182 res
183 }
184}
185
186/// Conversion into an [`Iterator`].
187///
188/// By implementing `IntoIterator` for a type, you define how it will be
189/// converted to an iterator. This is common for types which describe a
190/// collection of some kind.
191///
192/// One benefit of implementing `IntoIterator` is that your type will [work
193/// with Rust's `for` loop syntax](crate::iter#for-loops-and-intoiterator).
194///
195/// See also: [`FromIterator`].
196///
197/// # Examples
198///
199/// Basic usage:
200///
201/// ```
202/// let v = [1, 2, 3];
203/// let mut iter = v.into_iter();
204///
205/// assert_eq!(Some(1), iter.next());
206/// assert_eq!(Some(2), iter.next());
207/// assert_eq!(Some(3), iter.next());
208/// assert_eq!(None, iter.next());
209/// ```
210/// Implementing `IntoIterator` for your type:
211///
212/// ```
213/// // A sample collection, that's just a wrapper over Vec<T>
214/// #[derive(Debug)]
215/// struct MyCollection(Vec<i32>);
216///
217/// // Let's give it some methods so we can create one and add things
218/// // to it.
219/// impl MyCollection {
220/// fn new() -> MyCollection {
221/// MyCollection(Vec::new())
222/// }
223///
224/// fn add(&mut self, elem: i32) {
225/// self.0.push(elem);
226/// }
227/// }
228///
229/// // and we'll implement IntoIterator
230/// impl IntoIterator for MyCollection {
231/// type Item = i32;
232/// type IntoIter = std::vec::IntoIter<Self::Item>;
233///
234/// fn into_iter(self) -> Self::IntoIter {
235/// self.0.into_iter()
236/// }
237/// }
238///
239/// // Now we can make a new collection...
240/// let mut c = MyCollection::new();
241///
242/// // ... add some stuff to it ...
243/// c.add(0);
244/// c.add(1);
245/// c.add(2);
246///
247/// // ... and then turn it into an Iterator:
248/// for (i, n) in c.into_iter().enumerate() {
249/// assert_eq!(i as i32, n);
250/// }
251/// ```
252///
253/// It is common to use `IntoIterator` as a trait bound. This allows
254/// the input collection type to change, so long as it is still an
255/// iterator. Additional bounds can be specified by restricting on
256/// `Item`:
257///
258/// ```rust
259/// fn collect_as_strings<T>(collection: T) -> Vec<String>
260/// where
261/// T: IntoIterator,
262/// T::Item: std::fmt::Debug,
263/// {
264/// collection
265/// .into_iter()
266/// .map(|item| format!("{item:?}"))
267/// .collect()
268/// }
269/// ```
270#[rustc_diagnostic_item = "IntoIterator"]
271#[rustc_skip_array_during_method_dispatch]
272#[rustc_on_unimplemented(
273 on(
274 _Self = "core::ops::range::RangeTo<Idx>",
275 label = "if you meant to iterate until a value, add a starting value",
276 note = "`..end` is a `RangeTo`, which cannot be iterated on; you might have meant to have a \
277 bounded `Range`: `0..end`"
278 ),
279 on(
280 _Self = "core::ops::range::RangeToInclusive<Idx>",
281 label = "if you meant to iterate until a value (including it), add a starting value",
282 note = "`..=end` is a `RangeToInclusive`, which cannot be iterated on; you might have meant \
283 to have a bounded `RangeInclusive`: `0..=end`"
284 ),
285 on(
286 _Self = "[]",
287 label = "`{Self}` is not an iterator; try calling `.into_iter()` or `.iter()`"
288 ),
289 on(_Self = "&[]", label = "`{Self}` is not an iterator; try calling `.iter()`"),
290 on(
291 _Self = "alloc::vec::Vec<T, A>",
292 label = "`{Self}` is not an iterator; try calling `.into_iter()` or `.iter()`"
293 ),
294 on(
295 _Self = "&str",
296 label = "`{Self}` is not an iterator; try calling `.chars()` or `.bytes()`"
297 ),
298 on(
299 _Self = "alloc::string::String",
300 label = "`{Self}` is not an iterator; try calling `.chars()` or `.bytes()`"
301 ),
302 on(
303 _Self = "{integral}",
304 note = "if you want to iterate between `start` until a value `end`, use the exclusive range \
305 syntax `start..end` or the inclusive range syntax `start..=end`"
306 ),
307 on(
308 _Self = "{float}",
309 note = "if you want to iterate between `start` until a value `end`, use the exclusive range \
310 syntax `start..end` or the inclusive range syntax `start..=end`"
311 ),
312 label = "`{Self}` is not an iterator",
313 message = "`{Self}` is not an iterator"
314)]
315#[stable(feature = "rust1", since = "1.0.0")]
316pub trait IntoIterator {
317 /// The type of the elements being iterated over.
318 #[stable(feature = "rust1", since = "1.0.0")]
319 type Item;
320
321 /// Which kind of iterator are we turning this into?
322 #[stable(feature = "rust1", since = "1.0.0")]
323 type IntoIter: Iterator<Item = Self::Item>;
324
325 /// Creates an iterator from a value.
326 ///
327 /// See the [module-level documentation] for more.
328 ///
329 /// [module-level documentation]: crate::iter
330 ///
331 /// # Examples
332 ///
333 /// ```
334 /// let v = [1, 2, 3];
335 /// let mut iter = v.into_iter();
336 ///
337 /// assert_eq!(Some(1), iter.next());
338 /// assert_eq!(Some(2), iter.next());
339 /// assert_eq!(Some(3), iter.next());
340 /// assert_eq!(None, iter.next());
341 /// ```
342 #[lang = "into_iter"]
343 #[stable(feature = "rust1", since = "1.0.0")]
344 fn into_iter(self) -> Self::IntoIter;
345}
346
347#[rustc_const_unstable(feature = "const_intoiterator_identity", issue = "90603")]
348#[stable(feature = "rust1", since = "1.0.0")]
349impl<I: Iterator> IntoIterator for I {
350 type Item = I::Item;
351 type IntoIter = I;
352
353 #[inline]
354 fn into_iter(self) -> I {
355 self
356 }
357}
358
359/// Extend a collection with the contents of an iterator.
360///
361/// Iterators produce a series of values, and collections can also be thought
362/// of as a series of values. The `Extend` trait bridges this gap, allowing you
363/// to extend a collection by including the contents of that iterator. When
364/// extending a collection with an already existing key, that entry is updated
365/// or, in the case of collections that permit multiple entries with equal
366/// keys, that entry is inserted.
367///
368/// # Examples
369///
370/// Basic usage:
371///
372/// ```
373/// // You can extend a String with some chars:
374/// let mut message = String::from("The first three letters are: ");
375///
376/// message.extend(&['a', 'b', 'c']);
377///
378/// assert_eq!("abc", &message[29..32]);
379/// ```
380///
381/// Implementing `Extend`:
382///
383/// ```
384/// // A sample collection, that's just a wrapper over Vec<T>
385/// #[derive(Debug)]
386/// struct MyCollection(Vec<i32>);
387///
388/// // Let's give it some methods so we can create one and add things
389/// // to it.
390/// impl MyCollection {
391/// fn new() -> MyCollection {
392/// MyCollection(Vec::new())
393/// }
394///
395/// fn add(&mut self, elem: i32) {
396/// self.0.push(elem);
397/// }
398/// }
399///
400/// // since MyCollection has a list of i32s, we implement Extend for i32
401/// impl Extend<i32> for MyCollection {
402///
403/// // This is a bit simpler with the concrete type signature: we can call
404/// // extend on anything which can be turned into an Iterator which gives
405/// // us i32s. Because we need i32s to put into MyCollection.
406/// fn extend<T: IntoIterator<Item=i32>>(&mut self, iter: T) {
407///
408/// // The implementation is very straightforward: loop through the
409/// // iterator, and add() each element to ourselves.
410/// for elem in iter {
411/// self.add(elem);
412/// }
413/// }
414/// }
415///
416/// let mut c = MyCollection::new();
417///
418/// c.add(5);
419/// c.add(6);
420/// c.add(7);
421///
422/// // let's extend our collection with three more numbers
423/// c.extend(vec![1, 2, 3]);
424///
425/// // we've added these elements onto the end
426/// assert_eq!("MyCollection([5, 6, 7, 1, 2, 3])", format!("{c:?}"));
427/// ```
428#[stable(feature = "rust1", since = "1.0.0")]
429pub trait Extend<A> {
430 /// Extends a collection with the contents of an iterator.
431 ///
432 /// As this is the only required method for this trait, the [trait-level] docs
433 /// contain more details.
434 ///
435 /// [trait-level]: Extend
436 ///
437 /// # Examples
438 ///
439 /// ```
440 /// // You can extend a String with some chars:
441 /// let mut message = String::from("abc");
442 ///
443 /// message.extend(['d', 'e', 'f'].iter());
444 ///
445 /// assert_eq!("abcdef", &message);
446 /// ```
447 #[stable(feature = "rust1", since = "1.0.0")]
448 fn extend<T: IntoIterator<Item = A>>(&mut self, iter: T);
449
450 /// Extends a collection with exactly one element.
451 #[unstable(feature = "extend_one", issue = "72631")]
452 fn extend_one(&mut self, item: A) {
453 self.extend(Some(item));
454 }
455
456 /// Reserves capacity in a collection for the given number of additional elements.
457 ///
458 /// The default implementation does nothing.
459 #[unstable(feature = "extend_one", issue = "72631")]
460 fn extend_reserve(&mut self, additional: usize) {
461 let _ = additional;
462 }
463}
464
465#[stable(feature = "extend_for_unit", since = "1.28.0")]
466impl Extend<()> for () {
467 fn extend<T: IntoIterator<Item = ()>>(&mut self, iter: T) {
468 iter.into_iter().for_each(drop)
469 }
470 fn extend_one(&mut self, _item: ()) {}
471}
472
473#[stable(feature = "extend_for_tuple", since = "1.56.0")]
474impl<A, B, ExtendA, ExtendB> Extend<(A, B)> for (ExtendA, ExtendB)
475where
476 ExtendA: Extend<A>,
477 ExtendB: Extend<B>,
478{
479 /// Allows to `extend` a tuple of collections that also implement `Extend`.
480 ///
481 /// See also: [`Iterator::unzip`]
482 ///
483 /// # Examples
484 /// ```
485 /// let mut tuple = (vec![0], vec![1]);
486 /// tuple.extend([(2, 3), (4, 5), (6, 7)]);
487 /// assert_eq!(tuple.0, [0, 2, 4, 6]);
488 /// assert_eq!(tuple.1, [1, 3, 5, 7]);
489 ///
490 /// // also allows for arbitrarily nested tuples as elements
491 /// let mut nested_tuple = (vec![1], (vec![2], vec![3]));
492 /// nested_tuple.extend([(4, (5, 6)), (7, (8, 9))]);
493 ///
494 /// let (a, (b, c)) = nested_tuple;
495 /// assert_eq!(a, [1, 4, 7]);
496 /// assert_eq!(b, [2, 5, 8]);
497 /// assert_eq!(c, [3, 6, 9]);
498 /// ```
499 fn extend<T: IntoIterator<Item = (A, B)>>(&mut self, into_iter: T) {
500 let (a, b) = self;
501 let iter = into_iter.into_iter();
502
503 fn extend<'a, A, B>(
504 a: &'a mut impl Extend<A>,
505 b: &'a mut impl Extend<B>,
506 ) -> impl FnMut((), (A, B)) + 'a {
507 move |(), (t, u)| {
508 a.extend_one(t);
509 b.extend_one(u);
510 }
511 }
512
513 let (lower_bound, _) = iter.size_hint();
514 if lower_bound > 0 {
515 a.extend_reserve(lower_bound);
516 b.extend_reserve(lower_bound);
517 }
518
519 iter.fold((), extend(a, b));
520 }
521
522 fn extend_one(&mut self, item: (A, B)) {
523 self.0.extend_one(item.0);
524 self.1.extend_one(item.1);
525 }
526
527 fn extend_reserve(&mut self, additional: usize) {
528 self.0.extend_reserve(additional);
529 self.1.extend_reserve(additional);
530 }
531}
532