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/// Conversion into an [`Iterator`].
154///
155/// By implementing `IntoIterator` for a type, you define how it will be
156/// converted to an iterator. This is common for types which describe a
157/// collection of some kind.
158///
159/// One benefit of implementing `IntoIterator` is that your type will [work
160/// with Rust's `for` loop syntax](crate::iter#for-loops-and-intoiterator).
161///
162/// See also: [`FromIterator`].
163///
164/// # Examples
165///
166/// Basic usage:
167///
168/// ```
169/// let v = [1, 2, 3];
170/// let mut iter = v.into_iter();
171///
172/// assert_eq!(Some(1), iter.next());
173/// assert_eq!(Some(2), iter.next());
174/// assert_eq!(Some(3), iter.next());
175/// assert_eq!(None, iter.next());
176/// ```
177/// Implementing `IntoIterator` for your type:
178///
179/// ```
180/// // A sample collection, that's just a wrapper over Vec<T>
181/// #[derive(Debug)]
182/// struct MyCollection(Vec<i32>);
183///
184/// // Let's give it some methods so we can create one and add things
185/// // to it.
186/// impl MyCollection {
187/// fn new() -> MyCollection {
188/// MyCollection(Vec::new())
189/// }
190///
191/// fn add(&mut self, elem: i32) {
192/// self.0.push(elem);
193/// }
194/// }
195///
196/// // and we'll implement IntoIterator
197/// impl IntoIterator for MyCollection {
198/// type Item = i32;
199/// type IntoIter = std::vec::IntoIter<Self::Item>;
200///
201/// fn into_iter(self) -> Self::IntoIter {
202/// self.0.into_iter()
203/// }
204/// }
205///
206/// // Now we can make a new collection...
207/// let mut c = MyCollection::new();
208///
209/// // ... add some stuff to it ...
210/// c.add(0);
211/// c.add(1);
212/// c.add(2);
213///
214/// // ... and then turn it into an Iterator:
215/// for (i, n) in c.into_iter().enumerate() {
216/// assert_eq!(i as i32, n);
217/// }
218/// ```
219///
220/// It is common to use `IntoIterator` as a trait bound. This allows
221/// the input collection type to change, so long as it is still an
222/// iterator. Additional bounds can be specified by restricting on
223/// `Item`:
224///
225/// ```rust
226/// fn collect_as_strings<T>(collection: T) -> Vec<String>
227/// where
228/// T: IntoIterator,
229/// T::Item: std::fmt::Debug,
230/// {
231/// collection
232/// .into_iter()
233/// .map(|item| format!("{item:?}"))
234/// .collect()
235/// }
236/// ```
237#[rustc_diagnostic_item = "IntoIterator"]
238#[rustc_skip_array_during_method_dispatch]
239#[stable(feature = "rust1", since = "1.0.0")]
240pub trait IntoIterator {
241 /// The type of the elements being iterated over.
242 #[stable(feature = "rust1", since = "1.0.0")]
243 type Item;
244
245 /// Which kind of iterator are we turning this into?
246 #[stable(feature = "rust1", since = "1.0.0")]
247 type IntoIter: Iterator<Item = Self::Item>;
248
249 /// Creates an iterator from a value.
250 ///
251 /// See the [module-level documentation] for more.
252 ///
253 /// [module-level documentation]: crate::iter
254 ///
255 /// # Examples
256 ///
257 /// ```
258 /// let v = [1, 2, 3];
259 /// let mut iter = v.into_iter();
260 ///
261 /// assert_eq!(Some(1), iter.next());
262 /// assert_eq!(Some(2), iter.next());
263 /// assert_eq!(Some(3), iter.next());
264 /// assert_eq!(None, iter.next());
265 /// ```
266 #[lang = "into_iter"]
267 #[stable(feature = "rust1", since = "1.0.0")]
268 fn into_iter(self) -> Self::IntoIter;
269}
270
271#[rustc_const_unstable(feature = "const_intoiterator_identity", issue = "90603")]
272#[stable(feature = "rust1", since = "1.0.0")]
273impl<I: Iterator> IntoIterator for I {
274 type Item = I::Item;
275 type IntoIter = I;
276
277 #[inline]
278 fn into_iter(self) -> I {
279 self
280 }
281}
282
283/// Extend a collection with the contents of an iterator.
284///
285/// Iterators produce a series of values, and collections can also be thought
286/// of as a series of values. The `Extend` trait bridges this gap, allowing you
287/// to extend a collection by including the contents of that iterator. When
288/// extending a collection with an already existing key, that entry is updated
289/// or, in the case of collections that permit multiple entries with equal
290/// keys, that entry is inserted.
291///
292/// # Examples
293///
294/// Basic usage:
295///
296/// ```
297/// // You can extend a String with some chars:
298/// let mut message = String::from("The first three letters are: ");
299///
300/// message.extend(&['a', 'b', 'c']);
301///
302/// assert_eq!("abc", &message[29..32]);
303/// ```
304///
305/// Implementing `Extend`:
306///
307/// ```
308/// // A sample collection, that's just a wrapper over Vec<T>
309/// #[derive(Debug)]
310/// struct MyCollection(Vec<i32>);
311///
312/// // Let's give it some methods so we can create one and add things
313/// // to it.
314/// impl MyCollection {
315/// fn new() -> MyCollection {
316/// MyCollection(Vec::new())
317/// }
318///
319/// fn add(&mut self, elem: i32) {
320/// self.0.push(elem);
321/// }
322/// }
323///
324/// // since MyCollection has a list of i32s, we implement Extend for i32
325/// impl Extend<i32> for MyCollection {
326///
327/// // This is a bit simpler with the concrete type signature: we can call
328/// // extend on anything which can be turned into an Iterator which gives
329/// // us i32s. Because we need i32s to put into MyCollection.
330/// fn extend<T: IntoIterator<Item=i32>>(&mut self, iter: T) {
331///
332/// // The implementation is very straightforward: loop through the
333/// // iterator, and add() each element to ourselves.
334/// for elem in iter {
335/// self.add(elem);
336/// }
337/// }
338/// }
339///
340/// let mut c = MyCollection::new();
341///
342/// c.add(5);
343/// c.add(6);
344/// c.add(7);
345///
346/// // let's extend our collection with three more numbers
347/// c.extend(vec![1, 2, 3]);
348///
349/// // we've added these elements onto the end
350/// assert_eq!("MyCollection([5, 6, 7, 1, 2, 3])", format!("{c:?}"));
351/// ```
352#[stable(feature = "rust1", since = "1.0.0")]
353pub trait Extend<A> {
354 /// Extends a collection with the contents of an iterator.
355 ///
356 /// As this is the only required method for this trait, the [trait-level] docs
357 /// contain more details.
358 ///
359 /// [trait-level]: Extend
360 ///
361 /// # Examples
362 ///
363 /// ```
364 /// // You can extend a String with some chars:
365 /// let mut message = String::from("abc");
366 ///
367 /// message.extend(['d', 'e', 'f'].iter());
368 ///
369 /// assert_eq!("abcdef", &message);
370 /// ```
371 #[stable(feature = "rust1", since = "1.0.0")]
372 fn extend<T: IntoIterator<Item = A>>(&mut self, iter: T);
373
374 /// Extends a collection with exactly one element.
375 #[unstable(feature = "extend_one", issue = "72631")]
376 fn extend_one(&mut self, item: A) {
377 self.extend(Some(item));
378 }
379
380 /// Reserves capacity in a collection for the given number of additional elements.
381 ///
382 /// The default implementation does nothing.
383 #[unstable(feature = "extend_one", issue = "72631")]
384 fn extend_reserve(&mut self, additional: usize) {
385 let _ = additional;
386 }
387}
388
389#[stable(feature = "extend_for_unit", since = "1.28.0")]
390impl Extend<()> for () {
391 fn extend<T: IntoIterator<Item = ()>>(&mut self, iter: T) {
392 iter.into_iter().for_each(drop)
393 }
394 fn extend_one(&mut self, _item: ()) {}
395}
396
397#[stable(feature = "extend_for_tuple", since = "1.56.0")]
398impl<A, B, ExtendA, ExtendB> Extend<(A, B)> for (ExtendA, ExtendB)
399where
400 ExtendA: Extend<A>,
401 ExtendB: Extend<B>,
402{
403 /// Allows to `extend` a tuple of collections that also implement `Extend`.
404 ///
405 /// See also: [`Iterator::unzip`]
406 ///
407 /// # Examples
408 /// ```
409 /// let mut tuple = (vec![0], vec![1]);
410 /// tuple.extend([(2, 3), (4, 5), (6, 7)]);
411 /// assert_eq!(tuple.0, [0, 2, 4, 6]);
412 /// assert_eq!(tuple.1, [1, 3, 5, 7]);
413 ///
414 /// // also allows for arbitrarily nested tuples as elements
415 /// let mut nested_tuple = (vec![1], (vec![2], vec![3]));
416 /// nested_tuple.extend([(4, (5, 6)), (7, (8, 9))]);
417 ///
418 /// let (a, (b, c)) = nested_tuple;
419 /// assert_eq!(a, [1, 4, 7]);
420 /// assert_eq!(b, [2, 5, 8]);
421 /// assert_eq!(c, [3, 6, 9]);
422 /// ```
423 fn extend<T: IntoIterator<Item = (A, B)>>(&mut self, into_iter: T) {
424 let (a, b) = self;
425 let iter = into_iter.into_iter();
426
427 fn extend<'a, A, B>(
428 a: &'a mut impl Extend<A>,
429 b: &'a mut impl Extend<B>,
430 ) -> impl FnMut((), (A, B)) + 'a {
431 move |(), (t, u)| {
432 a.extend_one(t);
433 b.extend_one(u);
434 }
435 }
436
437 let (lower_bound, _) = iter.size_hint();
438 if lower_bound > 0 {
439 a.extend_reserve(lower_bound);
440 b.extend_reserve(lower_bound);
441 }
442
443 iter.fold((), extend(a, b));
444 }
445
446 fn extend_one(&mut self, item: (A, B)) {
447 self.0.extend_one(item.0);
448 self.1.extend_one(item.1);
449 }
450
451 fn extend_reserve(&mut self, additional: usize) {
452 self.0.extend_reserve(additional);
453 self.1.extend_reserve(additional);
454 }
455}
456