library/core/src/iter/traits/collect.rs

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