library/std/src/collections/hash/set.rs

   1 #[cfg(test)]
   2 mod tests;
   3
   4 use hashbrown::hash_set as base;
   5
   6 use crate::borrow::Borrow;
   7 use crate::collections::TryReserveError;
   8 use crate::fmt;
   9 use crate::hash::{BuildHasher, Hash};
  10 use crate::iter::{Chain, FusedIterator};
  11 use crate::ops::{BitAnd, BitOr, BitXor, Sub};
  12
  13 use super::map::{map_try_reserve_error, RandomState};
  14
  15 // Future Optimization (FIXME!)
  16 // ============================
  17 //
  18 // Iteration over zero sized values is a noop. There is no need
  19 // for `bucket.val` in the case of HashSet. I suppose we would need HKT
  20 // to get rid of it properly.
  21
  22 /// A [hash set] implemented as a `HashMap` where the value is `()`.
  23 ///
  24 /// As with the [`HashMap`] type, a `HashSet` requires that the elements
  25 /// implement the [`Eq`] and [`Hash`] traits. This can frequently be achieved by
  26 /// using `#[derive(PartialEq, Eq, Hash)]`. If you implement these yourself,
  27 /// it is important that the following property holds:
  28 ///
  29 /// ```text
  30 /// k1 == k2 -> hash(k1) == hash(k2)
  31 /// ```
  32 ///
  33 /// In other words, if two keys are equal, their hashes must be equal.
  34 ///
  35 ///
  36 /// It is a logic error for a key to be modified in such a way that the key's
  37 /// hash, as determined by the [`Hash`] trait, or its equality, as determined by
  38 /// the [`Eq`] trait, changes while it is in the map. This is normally only
  39 /// possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code.
  40 /// The behavior resulting from such a logic error is not specified, but will
  41 /// be encapsulated to the `HashSet` that observed the logic error and not
  42 /// result in undefined behavior. This could include panics, incorrect results,
  43 /// aborts, memory leaks, and non-termination.
  44 ///
  45 /// # Examples
  46 ///
  47 /// ```
  48 /// use std::collections::HashSet;
  49 /// // Type inference lets us omit an explicit type signature (which
  50 /// // would be `HashSet<String>` in this example).
  51 /// let mut books = HashSet::new();
  52 ///
  53 /// // Add some books.
  54 /// books.insert("A Dance With Dragons".to_string());
  55 /// books.insert("To Kill a Mockingbird".to_string());
  56 /// books.insert("The Odyssey".to_string());
  57 /// books.insert("The Great Gatsby".to_string());
  58 ///
  59 /// // Check for a specific one.
  60 /// if !books.contains("The Winds of Winter") {
  61 ///     println!("We have {} books, but The Winds of Winter ain't one.",
  62 ///              books.len());
  63 /// }
  64 ///
  65 /// // Remove a book.
  66 /// books.remove("The Odyssey");
  67 ///
  68 /// // Iterate over everything.
  69 /// for book in &books {
  70 ///     println!("{book}");
  71 /// }
  72 /// ```
  73 ///
  74 /// The easiest way to use `HashSet` with a custom type is to derive
  75 /// [`Eq`] and [`Hash`]. We must also derive [`PartialEq`], this will in the
  76 /// future be implied by [`Eq`].
  77 ///
  78 /// ```
  79 /// use std::collections::HashSet;
  80 /// #[derive(Hash, Eq, PartialEq, Debug)]
  81 /// struct Viking {
  82 ///     name: String,
  83 ///     power: usize,
  84 /// }
  85 ///
  86 /// let mut vikings = HashSet::new();
  87 ///
  88 /// vikings.insert(Viking { name: "Einar".to_string(), power: 9 });
  89 /// vikings.insert(Viking { name: "Einar".to_string(), power: 9 });
  90 /// vikings.insert(Viking { name: "Olaf".to_string(), power: 4 });
  91 /// vikings.insert(Viking { name: "Harald".to_string(), power: 8 });
  92 ///
  93 /// // Use derived implementation to print the vikings.
  94 /// for x in &vikings {
  95 ///     println!("{x:?}");
  96 /// }
  97 /// ```
  98 ///
  99 /// A `HashSet` with a known list of items can be initialized from an array:
 100 ///
 101 /// ```
 102 /// use std::collections::HashSet;
 103 ///
 104 /// let viking_names = HashSet::from(["Einar", "Olaf", "Harald"]);
 105 /// ```
 106 ///
 107 /// [hash set]: crate::collections#use-the-set-variant-of-any-of-these-maps-when
 108 /// [`HashMap`]: crate::collections::HashMap
 109 /// [`RefCell`]: crate::cell::RefCell
 110 /// [`Cell`]: crate::cell::Cell
 111 #[cfg_attr(not(test), rustc_diagnostic_item = "HashSet")]
 112 #[stable(feature = "rust1", since = "1.0.0")]
 113 pub struct HashSet<T, S = RandomState> {
 114     base: base::HashSet<T, S>,
 115 }
 116
 117 impl<T> HashSet<T, RandomState> {
 118     /// Creates an empty `HashSet`.
 119     ///
 120     /// The hash set is initially created with a capacity of 0, so it will not allocate until it
 121     /// is first inserted into.
 122     ///
 123     /// # Examples
 124     ///
 125     /// ```
 126     /// use std::collections::HashSet;
 127     /// let set: HashSet<i32> = HashSet::new();
 128     /// ```
 129     #[inline]
 130     #[must_use]
 131     #[stable(feature = "rust1", since = "1.0.0")]
 132     pub fn new() -> HashSet<T, RandomState> {
 133         Default::default()
 134     }
 135
 136     /// Creates an empty `HashSet` with at least the specified capacity.
 137     ///
 138     /// The hash set will be able to hold at least `capacity` elements without
 139     /// reallocating. This method is allowed to allocate for more elements than
 140     /// `capacity`. If `capacity` is 0, the hash set will not allocate.
 141     ///
 142     /// # Examples
 143     ///
 144     /// ```
 145     /// use std::collections::HashSet;
 146     /// let set: HashSet<i32> = HashSet::with_capacity(10);
 147     /// assert!(set.capacity() >= 10);
 148     /// ```
 149     #[inline]
 150     #[must_use]
 151     #[stable(feature = "rust1", since = "1.0.0")]
 152     pub fn with_capacity(capacity: usize) -> HashSet<T, RandomState> {
 153         HashSet { base: base::HashSet::with_capacity_and_hasher(capacity, Default::default()) }
 154     }
 155 }
 156
 157 impl<T, S> HashSet<T, S> {
 158     /// Returns the number of elements the set can hold without reallocating.
 159     ///
 160     /// # Examples
 161     ///
 162     /// ```
 163     /// use std::collections::HashSet;
 164     /// let set: HashSet<i32> = HashSet::with_capacity(100);
 165     /// assert!(set.capacity() >= 100);
 166     /// ```
 167     #[inline]
 168     #[stable(feature = "rust1", since = "1.0.0")]
 169     pub fn capacity(&self) -> usize {
 170         self.base.capacity()
 171     }
 172
 173     /// An iterator visiting all elements in arbitrary order.
 174     /// The iterator element type is `&'a T`.
 175     ///
 176     /// # Examples
 177     ///
 178     /// ```
 179     /// use std::collections::HashSet;
 180     /// let mut set = HashSet::new();
 181     /// set.insert("a");
 182     /// set.insert("b");
 183     ///
 184     /// // Will print in an arbitrary order.
 185     /// for x in set.iter() {
 186     ///     println!("{x}");
 187     /// }
 188     /// ```
 189     ///
 190     /// # Performance
 191     ///
 192     /// In the current implementation, iterating over set takes O(capacity) time
 193     /// instead of O(len) because it internally visits empty buckets too.
 194     #[inline]
 195     #[rustc_lint_query_instability]
 196     #[stable(feature = "rust1", since = "1.0.0")]
 197     pub fn iter(&self) -> Iter<'_, T> {
 198         Iter { base: self.base.iter() }
 199     }
 200
 201     /// Returns the number of elements in the set.
 202     ///
 203     /// # Examples
 204     ///
 205     /// ```
 206     /// use std::collections::HashSet;
 207     ///
 208     /// let mut v = HashSet::new();
 209     /// assert_eq!(v.len(), 0);
 210     /// v.insert(1);
 211     /// assert_eq!(v.len(), 1);
 212     /// ```
 213     #[inline]
 214     #[stable(feature = "rust1", since = "1.0.0")]
 215     pub fn len(&self) -> usize {
 216         self.base.len()
 217     }
 218
 219     /// Returns `true` if the set contains no elements.
 220     ///
 221     /// # Examples
 222     ///
 223     /// ```
 224     /// use std::collections::HashSet;
 225     ///
 226     /// let mut v = HashSet::new();
 227     /// assert!(v.is_empty());
 228     /// v.insert(1);
 229     /// assert!(!v.is_empty());
 230     /// ```
 231     #[inline]
 232     #[stable(feature = "rust1", since = "1.0.0")]
 233     pub fn is_empty(&self) -> bool {
 234         self.base.is_empty()
 235     }
 236
 237     /// Clears the set, returning all elements as an iterator. Keeps the
 238     /// allocated memory for reuse.
 239     ///
 240     /// If the returned iterator is dropped before being fully consumed, it
 241     /// drops the remaining elements. The returned iterator keeps a mutable
 242     /// borrow on the set to optimize its implementation.
 243     ///
 244     /// # Examples
 245     ///
 246     /// ```
 247     /// use std::collections::HashSet;
 248     ///
 249     /// let mut set = HashSet::from([1, 2, 3]);
 250     /// assert!(!set.is_empty());
 251     ///
 252     /// // print 1, 2, 3 in an arbitrary order
 253     /// for i in set.drain() {
 254     ///     println!("{i}");
 255     /// }
 256     ///
 257     /// assert!(set.is_empty());
 258     /// ```
 259     #[inline]
 260     #[rustc_lint_query_instability]
 261     #[stable(feature = "drain", since = "1.6.0")]
 262     pub fn drain(&mut self) -> Drain<'_, T> {
 263         Drain { base: self.base.drain() }
 264     }
 265
 266     /// Creates an iterator which uses a closure to determine if a value should be removed.
 267     ///
 268     /// If the closure returns true, then the value is removed and yielded.
 269     /// If the closure returns false, the value will remain in the list and will not be yielded
 270     /// by the iterator.
 271     ///
 272     /// If the iterator is only partially consumed or not consumed at all, each of the remaining
 273     /// values will still be subjected to the closure and removed and dropped if it returns true.
 274     ///
 275     /// It is unspecified how many more values will be subjected to the closure
 276     /// if a panic occurs in the closure, or if a panic occurs while dropping a value, or if the
 277     /// `DrainFilter` itself is leaked.
 278     ///
 279     /// # Examples
 280     ///
 281     /// Splitting a set into even and odd values, reusing the original set:
 282     ///
 283     /// ```
 284     /// #![feature(hash_drain_filter)]
 285     /// use std::collections::HashSet;
 286     ///
 287     /// let mut set: HashSet<i32> = (0..8).collect();
 288     /// let drained: HashSet<i32> = set.drain_filter(|v| v % 2 == 0).collect();
 289     ///
 290     /// let mut evens = drained.into_iter().collect::<Vec<_>>();
 291     /// let mut odds = set.into_iter().collect::<Vec<_>>();
 292     /// evens.sort();
 293     /// odds.sort();
 294     ///
 295     /// assert_eq!(evens, vec![0, 2, 4, 6]);
 296     /// assert_eq!(odds, vec![1, 3, 5, 7]);
 297     /// ```
 298     #[inline]
 299     #[rustc_lint_query_instability]
 300     #[unstable(feature = "hash_drain_filter", issue = "59618")]
 301     pub fn drain_filter<F>(&mut self, pred: F) -> DrainFilter<'_, T, F>
 302     where
 303         F: FnMut(&T) -> bool,
 304     {
 305         DrainFilter { base: self.base.drain_filter(pred) }
 306     }
 307
 308     /// Retains only the elements specified by the predicate.
 309     ///
 310     /// In other words, remove all elements `e` for which `f(&e)` returns `false`.
 311     /// The elements are visited in unsorted (and unspecified) order.
 312     ///
 313     /// # Examples
 314     ///
 315     /// ```
 316     /// use std::collections::HashSet;
 317     ///
 318     /// let mut set = HashSet::from([1, 2, 3, 4, 5, 6]);
 319     /// set.retain(|&k| k % 2 == 0);
 320     /// assert_eq!(set.len(), 3);
 321     /// ```
 322     ///
 323     /// # Performance
 324     ///
 325     /// In the current implementation, this operation takes O(capacity) time
 326     /// instead of O(len) because it internally visits empty buckets too.
 327     #[rustc_lint_query_instability]
 328     #[stable(feature = "retain_hash_collection", since = "1.18.0")]
 329     pub fn retain<F>(&mut self, f: F)
 330     where
 331         F: FnMut(&T) -> bool,
 332     {
 333         self.base.retain(f)
 334     }
 335
 336     /// Clears the set, removing all values.
 337     ///
 338     /// # Examples
 339     ///
 340     /// ```
 341     /// use std::collections::HashSet;
 342     ///
 343     /// let mut v = HashSet::new();
 344     /// v.insert(1);
 345     /// v.clear();
 346     /// assert!(v.is_empty());
 347     /// ```
 348     #[inline]
 349     #[stable(feature = "rust1", since = "1.0.0")]
 350     pub fn clear(&mut self) {
 351         self.base.clear()
 352     }
 353
 354     /// Creates a new empty hash set which will use the given hasher to hash
 355     /// keys.
 356     ///
 357     /// The hash set is also created with the default initial capacity.
 358     ///
 359     /// Warning: `hasher` is normally randomly generated, and
 360     /// is designed to allow `HashSet`s to be resistant to attacks that
 361     /// cause many collisions and very poor performance. Setting it
 362     /// manually using this function can expose a DoS attack vector.
 363     ///
 364     /// The `hash_builder` passed should implement the [`BuildHasher`] trait for
 365     /// the HashMap to be useful, see its documentation for details.
 366     ///
 367     /// # Examples
 368     ///
 369     /// ```
 370     /// use std::collections::HashSet;
 371     /// use std::collections::hash_map::RandomState;
 372     ///
 373     /// let s = RandomState::new();
 374     /// let mut set = HashSet::with_hasher(s);
 375     /// set.insert(2);
 376     /// ```
 377     #[inline]
 378     #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
 379     #[rustc_const_unstable(feature = "const_collections_with_hasher", issue = "102575")]
 380     pub const fn with_hasher(hasher: S) -> HashSet<T, S> {
 381         HashSet { base: base::HashSet::with_hasher(hasher) }
 382     }
 383
 384     /// Creates an empty `HashSet` with at least the specified capacity, using
 385     /// `hasher` to hash the keys.
 386     ///
 387     /// The hash set will be able to hold at least `capacity` elements without
 388     /// reallocating. This method is allowed to allocate for more elements than
 389     /// `capacity`. If `capacity` is 0, the hash set will not allocate.
 390     ///
 391     /// Warning: `hasher` is normally randomly generated, and
 392     /// is designed to allow `HashSet`s to be resistant to attacks that
 393     /// cause many collisions and very poor performance. Setting it
 394     /// manually using this function can expose a DoS attack vector.
 395     ///
 396     /// The `hash_builder` passed should implement the [`BuildHasher`] trait for
 397     /// the HashMap to be useful, see its documentation for details.
 398     ///
 399     /// # Examples
 400     ///
 401     /// ```
 402     /// use std::collections::HashSet;
 403     /// use std::collections::hash_map::RandomState;
 404     ///
 405     /// let s = RandomState::new();
 406     /// let mut set = HashSet::with_capacity_and_hasher(10, s);
 407     /// set.insert(1);
 408     /// ```
 409     #[inline]
 410     #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
 411     pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> HashSet<T, S> {
 412         HashSet { base: base::HashSet::with_capacity_and_hasher(capacity, hasher) }
 413     }
 414
 415     /// Returns a reference to the set's [`BuildHasher`].
 416     ///
 417     /// # Examples
 418     ///
 419     /// ```
 420     /// use std::collections::HashSet;
 421     /// use std::collections::hash_map::RandomState;
 422     ///
 423     /// let hasher = RandomState::new();
 424     /// let set: HashSet<i32> = HashSet::with_hasher(hasher);
 425     /// let hasher: &RandomState = set.hasher();
 426     /// ```
 427     #[inline]
 428     #[stable(feature = "hashmap_public_hasher", since = "1.9.0")]
 429     pub fn hasher(&self) -> &S {
 430         self.base.hasher()
 431     }
 432 }
 433
 434 impl<T, S> HashSet<T, S>
 435 where
 436     T: Eq + Hash,
 437     S: BuildHasher,
 438 {
 439     /// Reserves capacity for at least `additional` more elements to be inserted
 440     /// in the `HashSet`. The collection may reserve more space to speculatively
 441     /// avoid frequent reallocations. After calling `reserve`,
 442     /// capacity will be greater than or equal to `self.len() + additional`.
 443     /// Does nothing if capacity is already sufficient.
 444     ///
 445     /// # Panics
 446     ///
 447     /// Panics if the new allocation size overflows `usize`.
 448     ///
 449     /// # Examples
 450     ///
 451     /// ```
 452     /// use std::collections::HashSet;
 453     /// let mut set: HashSet<i32> = HashSet::new();
 454     /// set.reserve(10);
 455     /// assert!(set.capacity() >= 10);
 456     /// ```
 457     #[inline]
 458     #[stable(feature = "rust1", since = "1.0.0")]
 459     pub fn reserve(&mut self, additional: usize) {
 460         self.base.reserve(additional)
 461     }
 462
 463     /// Tries to reserve capacity for at least `additional` more elements to be inserted
 464     /// in the `HashSet`. The collection may reserve more space to speculatively
 465     /// avoid frequent reallocations. After calling `try_reserve`,
 466     /// capacity will be greater than or equal to `self.len() + additional` if
 467     /// it returns `Ok(())`.
 468     /// Does nothing if capacity is already sufficient.
 469     ///
 470     /// # Errors
 471     ///
 472     /// If the capacity overflows, or the allocator reports a failure, then an error
 473     /// is returned.
 474     ///
 475     /// # Examples
 476     ///
 477     /// ```
 478     /// use std::collections::HashSet;
 479     /// let mut set: HashSet<i32> = HashSet::new();
 480     /// set.try_reserve(10).expect("why is the test harness OOMing on a handful of bytes?");
 481     /// ```
 482     #[inline]
 483     #[stable(feature = "try_reserve", since = "1.57.0")]
 484     pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
 485         self.base.try_reserve(additional).map_err(map_try_reserve_error)
 486     }
 487
 488     /// Shrinks the capacity of the set as much as possible. It will drop
 489     /// down as much as possible while maintaining the internal rules
 490     /// and possibly leaving some space in accordance with the resize policy.
 491     ///
 492     /// # Examples
 493     ///
 494     /// ```
 495     /// use std::collections::HashSet;
 496     ///
 497     /// let mut set = HashSet::with_capacity(100);
 498     /// set.insert(1);
 499     /// set.insert(2);
 500     /// assert!(set.capacity() >= 100);
 501     /// set.shrink_to_fit();
 502     /// assert!(set.capacity() >= 2);
 503     /// ```
 504     #[inline]
 505     #[stable(feature = "rust1", since = "1.0.0")]
 506     pub fn shrink_to_fit(&mut self) {
 507         self.base.shrink_to_fit()
 508     }
 509
 510     /// Shrinks the capacity of the set with a lower limit. It will drop
 511     /// down no lower than the supplied limit while maintaining the internal rules
 512     /// and possibly leaving some space in accordance with the resize policy.
 513     ///
 514     /// If the current capacity is less than the lower limit, this is a no-op.
 515     /// # Examples
 516     ///
 517     /// ```
 518     /// use std::collections::HashSet;
 519     ///
 520     /// let mut set = HashSet::with_capacity(100);
 521     /// set.insert(1);
 522     /// set.insert(2);
 523     /// assert!(set.capacity() >= 100);
 524     /// set.shrink_to(10);
 525     /// assert!(set.capacity() >= 10);
 526     /// set.shrink_to(0);
 527     /// assert!(set.capacity() >= 2);
 528     /// ```
 529     #[inline]
 530     #[stable(feature = "shrink_to", since = "1.56.0")]
 531     pub fn shrink_to(&mut self, min_capacity: usize) {
 532         self.base.shrink_to(min_capacity)
 533     }
 534
 535     /// Visits the values representing the difference,
 536     /// i.e., the values that are in `self` but not in `other`.
 537     ///
 538     /// # Examples
 539     ///
 540     /// ```
 541     /// use std::collections::HashSet;
 542     /// let a = HashSet::from([1, 2, 3]);
 543     /// let b = HashSet::from([4, 2, 3, 4]);
 544     ///
 545     /// // Can be seen as `a - b`.
 546     /// for x in a.difference(&b) {
 547     ///     println!("{x}"); // Print 1
 548     /// }
 549     ///
 550     /// let diff: HashSet<_> = a.difference(&b).collect();
 551     /// assert_eq!(diff, [1].iter().collect());
 552     ///
 553     /// // Note that difference is not symmetric,
 554     /// // and `b - a` means something else:
 555     /// let diff: HashSet<_> = b.difference(&a).collect();
 556     /// assert_eq!(diff, [4].iter().collect());
 557     /// ```
 558     #[inline]
 559     #[rustc_lint_query_instability]
 560     #[stable(feature = "rust1", since = "1.0.0")]
 561     pub fn difference<'a>(&'a self, other: &'a HashSet<T, S>) -> Difference<'a, T, S> {
 562         Difference { iter: self.iter(), other }
 563     }
 564
 565     /// Visits the values representing the symmetric difference,
 566     /// i.e., the values that are in `self` or in `other` but not in both.
 567     ///
 568     /// # Examples
 569     ///
 570     /// ```
 571     /// use std::collections::HashSet;
 572     /// let a = HashSet::from([1, 2, 3]);
 573     /// let b = HashSet::from([4, 2, 3, 4]);
 574     ///
 575     /// // Print 1, 4 in arbitrary order.
 576     /// for x in a.symmetric_difference(&b) {
 577     ///     println!("{x}");
 578     /// }
 579     ///
 580     /// let diff1: HashSet<_> = a.symmetric_difference(&b).collect();
 581     /// let diff2: HashSet<_> = b.symmetric_difference(&a).collect();
 582     ///
 583     /// assert_eq!(diff1, diff2);
 584     /// assert_eq!(diff1, [1, 4].iter().collect());
 585     /// ```
 586     #[inline]
 587     #[rustc_lint_query_instability]
 588     #[stable(feature = "rust1", since = "1.0.0")]
 589     pub fn symmetric_difference<'a>(
 590         &'a self,
 591         other: &'a HashSet<T, S>,
 592     ) -> SymmetricDifference<'a, T, S> {
 593         SymmetricDifference { iter: self.difference(other).chain(other.difference(self)) }
 594     }
 595
 596     /// Visits the values representing the intersection,
 597     /// i.e., the values that are both in `self` and `other`.
 598     ///
 599     /// When an equal element is present in `self` and `other`
 600     /// then the resulting `Intersection` may yield references to
 601     /// one or the other. This can be relevant if `T` contains fields which
 602     /// are not compared by its `Eq` implementation, and may hold different
 603     /// value between the two equal copies of `T` in the two sets.
 604     ///
 605     /// # Examples
 606     ///
 607     /// ```
 608     /// use std::collections::HashSet;
 609     /// let a = HashSet::from([1, 2, 3]);
 610     /// let b = HashSet::from([4, 2, 3, 4]);
 611     ///
 612     /// // Print 2, 3 in arbitrary order.
 613     /// for x in a.intersection(&b) {
 614     ///     println!("{x}");
 615     /// }
 616     ///
 617     /// let intersection: HashSet<_> = a.intersection(&b).collect();
 618     /// assert_eq!(intersection, [2, 3].iter().collect());
 619     /// ```
 620     #[inline]
 621     #[rustc_lint_query_instability]
 622     #[stable(feature = "rust1", since = "1.0.0")]
 623     pub fn intersection<'a>(&'a self, other: &'a HashSet<T, S>) -> Intersection<'a, T, S> {
 624         if self.len() <= other.len() {
 625             Intersection { iter: self.iter(), other }
 626         } else {
 627             Intersection { iter: other.iter(), other: self }
 628         }
 629     }
 630
 631     /// Visits the values representing the union,
 632     /// i.e., all the values in `self` or `other`, without duplicates.
 633     ///
 634     /// # Examples
 635     ///
 636     /// ```
 637     /// use std::collections::HashSet;
 638     /// let a = HashSet::from([1, 2, 3]);
 639     /// let b = HashSet::from([4, 2, 3, 4]);
 640     ///
 641     /// // Print 1, 2, 3, 4 in arbitrary order.
 642     /// for x in a.union(&b) {
 643     ///     println!("{x}");
 644     /// }
 645     ///
 646     /// let union: HashSet<_> = a.union(&b).collect();
 647     /// assert_eq!(union, [1, 2, 3, 4].iter().collect());
 648     /// ```
 649     #[inline]
 650     #[rustc_lint_query_instability]
 651     #[stable(feature = "rust1", since = "1.0.0")]
 652     pub fn union<'a>(&'a self, other: &'a HashSet<T, S>) -> Union<'a, T, S> {
 653         if self.len() >= other.len() {
 654             Union { iter: self.iter().chain(other.difference(self)) }
 655         } else {
 656             Union { iter: other.iter().chain(self.difference(other)) }
 657         }
 658     }
 659
 660     /// Returns `true` if the set contains a value.
 661     ///
 662     /// The value may be any borrowed form of the set's value type, but
 663     /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
 664     /// the value type.
 665     ///
 666     /// # Examples
 667     ///
 668     /// ```
 669     /// use std::collections::HashSet;
 670     ///
 671     /// let set = HashSet::from([1, 2, 3]);
 672     /// assert_eq!(set.contains(&1), true);
 673     /// assert_eq!(set.contains(&4), false);
 674     /// ```
 675     #[inline]
 676     #[stable(feature = "rust1", since = "1.0.0")]
 677     pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool
 678     where
 679         T: Borrow<Q>,
 680         Q: Hash + Eq,
 681     {
 682         self.base.contains(value)
 683     }
 684
 685     /// Returns a reference to the value in the set, if any, that is equal to the given value.
 686     ///
 687     /// The value may be any borrowed form of the set's value type, but
 688     /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
 689     /// the value type.
 690     ///
 691     /// # Examples
 692     ///
 693     /// ```
 694     /// use std::collections::HashSet;
 695     ///
 696     /// let set = HashSet::from([1, 2, 3]);
 697     /// assert_eq!(set.get(&2), Some(&2));
 698     /// assert_eq!(set.get(&4), None);
 699     /// ```
 700     #[inline]
 701     #[stable(feature = "set_recovery", since = "1.9.0")]
 702     pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T>
 703     where
 704         T: Borrow<Q>,
 705         Q: Hash + Eq,
 706     {
 707         self.base.get(value)
 708     }
 709
 710     /// Inserts the given `value` into the set if it is not present, then
 711     /// returns a reference to the value in the set.
 712     ///
 713     /// # Examples
 714     ///
 715     /// ```
 716     /// #![feature(hash_set_entry)]
 717     ///
 718     /// use std::collections::HashSet;
 719     ///
 720     /// let mut set = HashSet::from([1, 2, 3]);
 721     /// assert_eq!(set.len(), 3);
 722     /// assert_eq!(set.get_or_insert(2), &2);
 723     /// assert_eq!(set.get_or_insert(100), &100);
 724     /// assert_eq!(set.len(), 4); // 100 was inserted
 725     /// ```
 726     #[inline]
 727     #[unstable(feature = "hash_set_entry", issue = "60896")]
 728     pub fn get_or_insert(&mut self, value: T) -> &T {
 729         // Although the raw entry gives us `&mut T`, we only return `&T` to be consistent with
 730         // `get`. Key mutation is "raw" because you're not supposed to affect `Eq` or `Hash`.
 731         self.base.get_or_insert(value)
 732     }
 733
 734     /// Inserts an owned copy of the given `value` into the set if it is not
 735     /// present, then returns a reference to the value in the set.
 736     ///
 737     /// # Examples
 738     ///
 739     /// ```
 740     /// #![feature(hash_set_entry)]
 741     ///
 742     /// use std::collections::HashSet;
 743     ///
 744     /// let mut set: HashSet<String> = ["cat", "dog", "horse"]
 745     ///     .iter().map(|&pet| pet.to_owned()).collect();
 746     ///
 747     /// assert_eq!(set.len(), 3);
 748     /// for &pet in &["cat", "dog", "fish"] {
 749     ///     let value = set.get_or_insert_owned(pet);
 750     ///     assert_eq!(value, pet);
 751     /// }
 752     /// assert_eq!(set.len(), 4); // a new "fish" was inserted
 753     /// ```
 754     #[inline]
 755     #[unstable(feature = "hash_set_entry", issue = "60896")]
 756     pub fn get_or_insert_owned<Q: ?Sized>(&mut self, value: &Q) -> &T
 757     where
 758         T: Borrow<Q>,
 759         Q: Hash + Eq + ToOwned<Owned = T>,
 760     {
 761         // Although the raw entry gives us `&mut T`, we only return `&T` to be consistent with
 762         // `get`. Key mutation is "raw" because you're not supposed to affect `Eq` or `Hash`.
 763         self.base.get_or_insert_owned(value)
 764     }
 765
 766     /// Inserts a value computed from `f` into the set if the given `value` is
 767     /// not present, then returns a reference to the value in the set.
 768     ///
 769     /// # Examples
 770     ///
 771     /// ```
 772     /// #![feature(hash_set_entry)]
 773     ///
 774     /// use std::collections::HashSet;
 775     ///
 776     /// let mut set: HashSet<String> = ["cat", "dog", "horse"]
 777     ///     .iter().map(|&pet| pet.to_owned()).collect();
 778     ///
 779     /// assert_eq!(set.len(), 3);
 780     /// for &pet in &["cat", "dog", "fish"] {
 781     ///     let value = set.get_or_insert_with(pet, str::to_owned);
 782     ///     assert_eq!(value, pet);
 783     /// }
 784     /// assert_eq!(set.len(), 4); // a new "fish" was inserted
 785     /// ```
 786     #[inline]
 787     #[unstable(feature = "hash_set_entry", issue = "60896")]
 788     pub fn get_or_insert_with<Q: ?Sized, F>(&mut self, value: &Q, f: F) -> &T
 789     where
 790         T: Borrow<Q>,
 791         Q: Hash + Eq,
 792         F: FnOnce(&Q) -> T,
 793     {
 794         // Although the raw entry gives us `&mut T`, we only return `&T` to be consistent with
 795         // `get`. Key mutation is "raw" because you're not supposed to affect `Eq` or `Hash`.
 796         self.base.get_or_insert_with(value, f)
 797     }
 798
 799     /// Returns `true` if `self` has no elements in common with `other`.
 800     /// This is equivalent to checking for an empty intersection.
 801     ///
 802     /// # Examples
 803     ///
 804     /// ```
 805     /// use std::collections::HashSet;
 806     ///
 807     /// let a = HashSet::from([1, 2, 3]);
 808     /// let mut b = HashSet::new();
 809     ///
 810     /// assert_eq!(a.is_disjoint(&b), true);
 811     /// b.insert(4);
 812     /// assert_eq!(a.is_disjoint(&b), true);
 813     /// b.insert(1);
 814     /// assert_eq!(a.is_disjoint(&b), false);
 815     /// ```
 816     #[stable(feature = "rust1", since = "1.0.0")]
 817     pub fn is_disjoint(&self, other: &HashSet<T, S>) -> bool {
 818         if self.len() <= other.len() {
 819             self.iter().all(|v| !other.contains(v))
 820         } else {
 821             other.iter().all(|v| !self.contains(v))
 822         }
 823     }
 824
 825     /// Returns `true` if the set is a subset of another,
 826     /// i.e., `other` contains at least all the values in `self`.
 827     ///
 828     /// # Examples
 829     ///
 830     /// ```
 831     /// use std::collections::HashSet;
 832     ///
 833     /// let sup = HashSet::from([1, 2, 3]);
 834     /// let mut set = HashSet::new();
 835     ///
 836     /// assert_eq!(set.is_subset(&sup), true);
 837     /// set.insert(2);
 838     /// assert_eq!(set.is_subset(&sup), true);
 839     /// set.insert(4);
 840     /// assert_eq!(set.is_subset(&sup), false);
 841     /// ```
 842     #[stable(feature = "rust1", since = "1.0.0")]
 843     pub fn is_subset(&self, other: &HashSet<T, S>) -> bool {
 844         if self.len() <= other.len() { self.iter().all(|v| other.contains(v)) } else { false }
 845     }
 846
 847     /// Returns `true` if the set is a superset of another,
 848     /// i.e., `self` contains at least all the values in `other`.
 849     ///
 850     /// # Examples
 851     ///
 852     /// ```
 853     /// use std::collections::HashSet;
 854     ///
 855     /// let sub = HashSet::from([1, 2]);
 856     /// let mut set = HashSet::new();
 857     ///
 858     /// assert_eq!(set.is_superset(&sub), false);
 859     ///
 860     /// set.insert(0);
 861     /// set.insert(1);
 862     /// assert_eq!(set.is_superset(&sub), false);
 863     ///
 864     /// set.insert(2);
 865     /// assert_eq!(set.is_superset(&sub), true);
 866     /// ```
 867     #[inline]
 868     #[stable(feature = "rust1", since = "1.0.0")]
 869     pub fn is_superset(&self, other: &HashSet<T, S>) -> bool {
 870         other.is_subset(self)
 871     }
 872
 873     /// Adds a value to the set.
 874     ///
 875     /// Returns whether the value was newly inserted. That is:
 876     ///
 877     /// - If the set did not previously contain this value, `true` is returned.
 878     /// - If the set already contained this value, `false` is returned.
 879     ///
 880     /// # Examples
 881     ///
 882     /// ```
 883     /// use std::collections::HashSet;
 884     ///
 885     /// let mut set = HashSet::new();
 886     ///
 887     /// assert_eq!(set.insert(2), true);
 888     /// assert_eq!(set.insert(2), false);
 889     /// assert_eq!(set.len(), 1);
 890     /// ```
 891     #[inline]
 892     #[stable(feature = "rust1", since = "1.0.0")]
 893     pub fn insert(&mut self, value: T) -> bool {
 894         self.base.insert(value)
 895     }
 896
 897     /// Adds a value to the set, replacing the existing value, if any, that is equal to the given
 898     /// one. Returns the replaced value.
 899     ///
 900     /// # Examples
 901     ///
 902     /// ```
 903     /// use std::collections::HashSet;
 904     ///
 905     /// let mut set = HashSet::new();
 906     /// set.insert(Vec::<i32>::new());
 907     ///
 908     /// assert_eq!(set.get(&[][..]).unwrap().capacity(), 0);
 909     /// set.replace(Vec::with_capacity(10));
 910     /// assert_eq!(set.get(&[][..]).unwrap().capacity(), 10);
 911     /// ```
 912     #[inline]
 913     #[stable(feature = "set_recovery", since = "1.9.0")]
 914     pub fn replace(&mut self, value: T) -> Option<T> {
 915         self.base.replace(value)
 916     }
 917
 918     /// Removes a value from the set. Returns whether the value was
 919     /// present in the set.
 920     ///
 921     /// The value may be any borrowed form of the set's value type, but
 922     /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
 923     /// the value type.
 924     ///
 925     /// # Examples
 926     ///
 927     /// ```
 928     /// use std::collections::HashSet;
 929     ///
 930     /// let mut set = HashSet::new();
 931     ///
 932     /// set.insert(2);
 933     /// assert_eq!(set.remove(&2), true);
 934     /// assert_eq!(set.remove(&2), false);
 935     /// ```
 936     #[inline]
 937     #[stable(feature = "rust1", since = "1.0.0")]
 938     pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool
 939     where
 940         T: Borrow<Q>,
 941         Q: Hash + Eq,
 942     {
 943         self.base.remove(value)
 944     }
 945
 946     /// Removes and returns the value in the set, if any, that is equal to the given one.
 947     ///
 948     /// The value may be any borrowed form of the set's value type, but
 949     /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
 950     /// the value type.
 951     ///
 952     /// # Examples
 953     ///
 954     /// ```
 955     /// use std::collections::HashSet;
 956     ///
 957     /// let mut set = HashSet::from([1, 2, 3]);
 958     /// assert_eq!(set.take(&2), Some(2));
 959     /// assert_eq!(set.take(&2), None);
 960     /// ```
 961     #[inline]
 962     #[stable(feature = "set_recovery", since = "1.9.0")]
 963     pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T>
 964     where
 965         T: Borrow<Q>,
 966         Q: Hash + Eq,
 967     {
 968         self.base.take(value)
 969     }
 970 }
 971
 972 #[stable(feature = "rust1", since = "1.0.0")]
 973 impl<T, S> Clone for HashSet<T, S>
 974 where
 975     T: Clone,
 976     S: Clone,
 977 {
 978     #[inline]
 979     fn clone(&self) -> Self {
 980         Self { base: self.base.clone() }
 981     }
 982
 983     #[inline]
 984     fn clone_from(&mut self, other: &Self) {
 985         self.base.clone_from(&other.base);
 986     }
 987 }
 988
 989 #[stable(feature = "rust1", since = "1.0.0")]
 990 impl<T, S> PartialEq for HashSet<T, S>
 991 where
 992     T: Eq + Hash,
 993     S: BuildHasher,
 994 {
 995     fn eq(&self, other: &HashSet<T, S>) -> bool {
 996         if self.len() != other.len() {
 997             return false;
 998         }
 999
1000         self.iter().all(|key| other.contains(key))
1001     }
1002 }
1003
1004 #[stable(feature = "rust1", since = "1.0.0")]
1005 impl<T, S> Eq for HashSet<T, S>
1006 where
1007     T: Eq + Hash,
1008     S: BuildHasher,
1009 {
1010 }
1011
1012 #[stable(feature = "rust1", since = "1.0.0")]
1013 impl<T, S> fmt::Debug for HashSet<T, S>
1014 where
1015     T: fmt::Debug,
1016 {
1017     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1018         f.debug_set().entries(self.iter()).finish()
1019     }
1020 }
1021
1022 #[stable(feature = "rust1", since = "1.0.0")]
1023 impl<T, S> FromIterator<T> for HashSet<T, S>
1024 where
1025     T: Eq + Hash,
1026     S: BuildHasher + Default,
1027 {
1028     #[inline]
1029     fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> HashSet<T, S> {
1030         let mut set = HashSet::with_hasher(Default::default());
1031         set.extend(iter);
1032         set
1033     }
1034 }
1035
1036 #[stable(feature = "std_collections_from_array", since = "1.56.0")]
1037 // Note: as what is currently the most convenient built-in way to construct
1038 // a HashSet, a simple usage of this function must not *require* the user
1039 // to provide a type annotation in order to infer the third type parameter
1040 // (the hasher parameter, conventionally "S").
1041 // To that end, this impl is defined using RandomState as the concrete
1042 // type of S, rather than being generic over `S: BuildHasher + Default`.
1043 // It is expected that users who want to specify a hasher will manually use
1044 // `with_capacity_and_hasher`.
1045 // If type parameter defaults worked on impls, and if type parameter
1046 // defaults could be mixed with const generics, then perhaps
1047 // this could be generalized.
1048 // See also the equivalent impl on HashMap.
1049 impl<T, const N: usize> From<[T; N]> for HashSet<T, RandomState>
1050 where
1051     T: Eq + Hash,
1052 {
1053     /// # Examples
1054     ///
1055     /// ```
1056     /// use std::collections::HashSet;
1057     ///
1058     /// let set1 = HashSet::from([1, 2, 3, 4]);
1059     /// let set2: HashSet<_> = [1, 2, 3, 4].into();
1060     /// assert_eq!(set1, set2);
1061     /// ```
1062     fn from(arr: [T; N]) -> Self {
1063         Self::from_iter(arr)
1064     }
1065 }
1066
1067 #[stable(feature = "rust1", since = "1.0.0")]
1068 impl<T, S> Extend<T> for HashSet<T, S>
1069 where
1070     T: Eq + Hash,
1071     S: BuildHasher,
1072 {
1073     #[inline]
1074     fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
1075         self.base.extend(iter);
1076     }
1077
1078     #[inline]
1079     fn extend_one(&mut self, item: T) {
1080         self.base.insert(item);
1081     }
1082
1083     #[inline]
1084     fn extend_reserve(&mut self, additional: usize) {
1085         self.base.extend_reserve(additional);
1086     }
1087 }
1088
1089 #[stable(feature = "hash_extend_copy", since = "1.4.0")]
1090 impl<'a, T, S> Extend<&'a T> for HashSet<T, S>
1091 where
1092     T: 'a + Eq + Hash + Copy,
1093     S: BuildHasher,
1094 {
1095     #[inline]
1096     fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
1097         self.extend(iter.into_iter().cloned());
1098     }
1099
1100     #[inline]
1101     fn extend_one(&mut self, &item: &'a T) {
1102         self.base.insert(item);
1103     }
1104
1105     #[inline]
1106     fn extend_reserve(&mut self, additional: usize) {
1107         Extend::<T>::extend_reserve(self, additional)
1108     }
1109 }
1110
1111 #[stable(feature = "rust1", since = "1.0.0")]
1112 impl<T, S> Default for HashSet<T, S>
1113 where
1114     S: Default,
1115 {
1116     /// Creates an empty `HashSet<T, S>` with the `Default` value for the hasher.
1117     #[inline]
1118     fn default() -> HashSet<T, S> {
1119         HashSet { base: Default::default() }
1120     }
1121 }
1122
1123 #[stable(feature = "rust1", since = "1.0.0")]
1124 impl<T, S> BitOr<&HashSet<T, S>> for &HashSet<T, S>
1125 where
1126     T: Eq + Hash + Clone,
1127     S: BuildHasher + Default,
1128 {
1129     type Output = HashSet<T, S>;
1130
1131     /// Returns the union of `self` and `rhs` as a new `HashSet<T, S>`.
1132     ///
1133     /// # Examples
1134     ///
1135     /// ```
1136     /// use std::collections::HashSet;
1137     ///
1138     /// let a = HashSet::from([1, 2, 3]);
1139     /// let b = HashSet::from([3, 4, 5]);
1140     ///
1141     /// let set = &a | &b;
1142     ///
1143     /// let mut i = 0;
1144     /// let expected = [1, 2, 3, 4, 5];
1145     /// for x in &set {
1146     ///     assert!(expected.contains(x));
1147     ///     i += 1;
1148     /// }
1149     /// assert_eq!(i, expected.len());
1150     /// ```
1151     fn bitor(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
1152         self.union(rhs).cloned().collect()
1153     }
1154 }
1155
1156 #[stable(feature = "rust1", since = "1.0.0")]
1157 impl<T, S> BitAnd<&HashSet<T, S>> for &HashSet<T, S>
1158 where
1159     T: Eq + Hash + Clone,
1160     S: BuildHasher + Default,
1161 {
1162     type Output = HashSet<T, S>;
1163
1164     /// Returns the intersection of `self` and `rhs` as a new `HashSet<T, S>`.
1165     ///
1166     /// # Examples
1167     ///
1168     /// ```
1169     /// use std::collections::HashSet;
1170     ///
1171     /// let a = HashSet::from([1, 2, 3]);
1172     /// let b = HashSet::from([2, 3, 4]);
1173     ///
1174     /// let set = &a & &b;
1175     ///
1176     /// let mut i = 0;
1177     /// let expected = [2, 3];
1178     /// for x in &set {
1179     ///     assert!(expected.contains(x));
1180     ///     i += 1;
1181     /// }
1182     /// assert_eq!(i, expected.len());
1183     /// ```
1184     fn bitand(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
1185         self.intersection(rhs).cloned().collect()
1186     }
1187 }
1188
1189 #[stable(feature = "rust1", since = "1.0.0")]
1190 impl<T, S> BitXor<&HashSet<T, S>> for &HashSet<T, S>
1191 where
1192     T: Eq + Hash + Clone,
1193     S: BuildHasher + Default,
1194 {
1195     type Output = HashSet<T, S>;
1196
1197     /// Returns the symmetric difference of `self` and `rhs` as a new `HashSet<T, S>`.
1198     ///
1199     /// # Examples
1200     ///
1201     /// ```
1202     /// use std::collections::HashSet;
1203     ///
1204     /// let a = HashSet::from([1, 2, 3]);
1205     /// let b = HashSet::from([3, 4, 5]);
1206     ///
1207     /// let set = &a ^ &b;
1208     ///
1209     /// let mut i = 0;
1210     /// let expected = [1, 2, 4, 5];
1211     /// for x in &set {
1212     ///     assert!(expected.contains(x));
1213     ///     i += 1;
1214     /// }
1215     /// assert_eq!(i, expected.len());
1216     /// ```
1217     fn bitxor(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
1218         self.symmetric_difference(rhs).cloned().collect()
1219     }
1220 }
1221
1222 #[stable(feature = "rust1", since = "1.0.0")]
1223 impl<T, S> Sub<&HashSet<T, S>> for &HashSet<T, S>
1224 where
1225     T: Eq + Hash + Clone,
1226     S: BuildHasher + Default,
1227 {
1228     type Output = HashSet<T, S>;
1229
1230     /// Returns the difference of `self` and `rhs` as a new `HashSet<T, S>`.
1231     ///
1232     /// # Examples
1233     ///
1234     /// ```
1235     /// use std::collections::HashSet;
1236     ///
1237     /// let a = HashSet::from([1, 2, 3]);
1238     /// let b = HashSet::from([3, 4, 5]);
1239     ///
1240     /// let set = &a - &b;
1241     ///
1242     /// let mut i = 0;
1243     /// let expected = [1, 2];
1244     /// for x in &set {
1245     ///     assert!(expected.contains(x));
1246     ///     i += 1;
1247     /// }
1248     /// assert_eq!(i, expected.len());
1249     /// ```
1250     fn sub(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
1251         self.difference(rhs).cloned().collect()
1252     }
1253 }
1254
1255 /// An iterator over the items of a `HashSet`.
1256 ///
1257 /// This `struct` is created by the [`iter`] method on [`HashSet`].
1258 /// See its documentation for more.
1259 ///
1260 /// [`iter`]: HashSet::iter
1261 ///
1262 /// # Examples
1263 ///
1264 /// ```
1265 /// use std::collections::HashSet;
1266 ///
1267 /// let a = HashSet::from([1, 2, 3]);
1268 ///
1269 /// let mut iter = a.iter();
1270 /// ```
1271 #[stable(feature = "rust1", since = "1.0.0")]
1272 pub struct Iter<'a, K: 'a> {
1273     base: base::Iter<'a, K>,
1274 }
1275
1276 /// An owning iterator over the items of a `HashSet`.
1277 ///
1278 /// This `struct` is created by the [`into_iter`] method on [`HashSet`]
1279 /// (provided by the [`IntoIterator`] trait). See its documentation for more.
1280 ///
1281 /// [`into_iter`]: IntoIterator::into_iter
1282 /// [`IntoIterator`]: crate::iter::IntoIterator
1283 ///
1284 /// # Examples
1285 ///
1286 /// ```
1287 /// use std::collections::HashSet;
1288 ///
1289 /// let a = HashSet::from([1, 2, 3]);
1290 ///
1291 /// let mut iter = a.into_iter();
1292 /// ```
1293 #[stable(feature = "rust1", since = "1.0.0")]
1294 pub struct IntoIter<K> {
1295     base: base::IntoIter<K>,
1296 }
1297
1298 /// A draining iterator over the items of a `HashSet`.
1299 ///
1300 /// This `struct` is created by the [`drain`] method on [`HashSet`].
1301 /// See its documentation for more.
1302 ///
1303 /// [`drain`]: HashSet::drain
1304 ///
1305 /// # Examples
1306 ///
1307 /// ```
1308 /// use std::collections::HashSet;
1309 ///
1310 /// let mut a = HashSet::from([1, 2, 3]);
1311 ///
1312 /// let mut drain = a.drain();
1313 /// ```
1314 #[stable(feature = "rust1", since = "1.0.0")]
1315 pub struct Drain<'a, K: 'a> {
1316     base: base::Drain<'a, K>,
1317 }
1318
1319 /// A draining, filtering iterator over the items of a `HashSet`.
1320 ///
1321 /// This `struct` is created by the [`drain_filter`] method on [`HashSet`].
1322 ///
1323 /// [`drain_filter`]: HashSet::drain_filter
1324 ///
1325 /// # Examples
1326 ///
1327 /// ```
1328 /// #![feature(hash_drain_filter)]
1329 ///
1330 /// use std::collections::HashSet;
1331 ///
1332 /// let mut a = HashSet::from([1, 2, 3]);
1333 ///
1334 /// let mut drain_filtered = a.drain_filter(|v| v % 2 == 0);
1335 /// ```
1336 #[unstable(feature = "hash_drain_filter", issue = "59618")]
1337 pub struct DrainFilter<'a, K, F>
1338 where
1339     F: FnMut(&K) -> bool,
1340 {
1341     base: base::DrainFilter<'a, K, F>,
1342 }
1343
1344 /// A lazy iterator producing elements in the intersection of `HashSet`s.
1345 ///
1346 /// This `struct` is created by the [`intersection`] method on [`HashSet`].
1347 /// See its documentation for more.
1348 ///
1349 /// [`intersection`]: HashSet::intersection
1350 ///
1351 /// # Examples
1352 ///
1353 /// ```
1354 /// use std::collections::HashSet;
1355 ///
1356 /// let a = HashSet::from([1, 2, 3]);
1357 /// let b = HashSet::from([4, 2, 3, 4]);
1358 ///
1359 /// let mut intersection = a.intersection(&b);
1360 /// ```
1361 #[must_use = "this returns the intersection as an iterator, \
1362               without modifying either input set"]
1363 #[stable(feature = "rust1", since = "1.0.0")]
1364 pub struct Intersection<'a, T: 'a, S: 'a> {
1365     // iterator of the first set
1366     iter: Iter<'a, T>,
1367     // the second set
1368     other: &'a HashSet<T, S>,
1369 }
1370
1371 /// A lazy iterator producing elements in the difference of `HashSet`s.
1372 ///
1373 /// This `struct` is created by the [`difference`] method on [`HashSet`].
1374 /// See its documentation for more.
1375 ///
1376 /// [`difference`]: HashSet::difference
1377 ///
1378 /// # Examples
1379 ///
1380 /// ```
1381 /// use std::collections::HashSet;
1382 ///
1383 /// let a = HashSet::from([1, 2, 3]);
1384 /// let b = HashSet::from([4, 2, 3, 4]);
1385 ///
1386 /// let mut difference = a.difference(&b);
1387 /// ```
1388 #[must_use = "this returns the difference as an iterator, \
1389               without modifying either input set"]
1390 #[stable(feature = "rust1", since = "1.0.0")]
1391 pub struct Difference<'a, T: 'a, S: 'a> {
1392     // iterator of the first set
1393     iter: Iter<'a, T>,
1394     // the second set
1395     other: &'a HashSet<T, S>,
1396 }
1397
1398 /// A lazy iterator producing elements in the symmetric difference of `HashSet`s.
1399 ///
1400 /// This `struct` is created by the [`symmetric_difference`] method on
1401 /// [`HashSet`]. See its documentation for more.
1402 ///
1403 /// [`symmetric_difference`]: HashSet::symmetric_difference
1404 ///
1405 /// # Examples
1406 ///
1407 /// ```
1408 /// use std::collections::HashSet;
1409 ///
1410 /// let a = HashSet::from([1, 2, 3]);
1411 /// let b = HashSet::from([4, 2, 3, 4]);
1412 ///
1413 /// let mut intersection = a.symmetric_difference(&b);
1414 /// ```
1415 #[must_use = "this returns the difference as an iterator, \
1416               without modifying either input set"]
1417 #[stable(feature = "rust1", since = "1.0.0")]
1418 pub struct SymmetricDifference<'a, T: 'a, S: 'a> {
1419     iter: Chain<Difference<'a, T, S>, Difference<'a, T, S>>,
1420 }
1421
1422 /// A lazy iterator producing elements in the union of `HashSet`s.
1423 ///
1424 /// This `struct` is created by the [`union`] method on [`HashSet`].
1425 /// See its documentation for more.
1426 ///
1427 /// [`union`]: HashSet::union
1428 ///
1429 /// # Examples
1430 ///
1431 /// ```
1432 /// use std::collections::HashSet;
1433 ///
1434 /// let a = HashSet::from([1, 2, 3]);
1435 /// let b = HashSet::from([4, 2, 3, 4]);
1436 ///
1437 /// let mut union_iter = a.union(&b);
1438 /// ```
1439 #[must_use = "this returns the union as an iterator, \
1440               without modifying either input set"]
1441 #[stable(feature = "rust1", since = "1.0.0")]
1442 pub struct Union<'a, T: 'a, S: 'a> {
1443     iter: Chain<Iter<'a, T>, Difference<'a, T, S>>,
1444 }
1445
1446 #[stable(feature = "rust1", since = "1.0.0")]
1447 impl<'a, T, S> IntoIterator for &'a HashSet<T, S> {
1448     type Item = &'a T;
1449     type IntoIter = Iter<'a, T>;
1450
1451     #[inline]
1452     #[rustc_lint_query_instability]
1453     fn into_iter(self) -> Iter<'a, T> {
1454         self.iter()
1455     }
1456 }
1457
1458 #[stable(feature = "rust1", since = "1.0.0")]
1459 impl<T, S> IntoIterator for HashSet<T, S> {
1460     type Item = T;
1461     type IntoIter = IntoIter<T>;
1462
1463     /// Creates a consuming iterator, that is, one that moves each value out
1464     /// of the set in arbitrary order. The set cannot be used after calling
1465     /// this.
1466     ///
1467     /// # Examples
1468     ///
1469     /// ```
1470     /// use std::collections::HashSet;
1471     /// let mut set = HashSet::new();
1472     /// set.insert("a".to_string());
1473     /// set.insert("b".to_string());
1474     ///
1475     /// // Not possible to collect to a Vec<String> with a regular `.iter()`.
1476     /// let v: Vec<String> = set.into_iter().collect();
1477     ///
1478     /// // Will print in an arbitrary order.
1479     /// for x in &v {
1480     ///     println!("{x}");
1481     /// }
1482     /// ```
1483     #[inline]
1484     #[rustc_lint_query_instability]
1485     fn into_iter(self) -> IntoIter<T> {
1486         IntoIter { base: self.base.into_iter() }
1487     }
1488 }
1489
1490 #[stable(feature = "rust1", since = "1.0.0")]
1491 impl<K> Clone for Iter<'_, K> {
1492     #[inline]
1493     fn clone(&self) -> Self {
1494         Iter { base: self.base.clone() }
1495     }
1496 }
1497 #[stable(feature = "rust1", since = "1.0.0")]
1498 impl<'a, K> Iterator for Iter<'a, K> {
1499     type Item = &'a K;
1500
1501     #[inline]
1502     fn next(&mut self) -> Option<&'a K> {
1503         self.base.next()
1504     }
1505     #[inline]
1506     fn size_hint(&self) -> (usize, Option<usize>) {
1507         self.base.size_hint()
1508     }
1509 }
1510 #[stable(feature = "rust1", since = "1.0.0")]
1511 impl<K> ExactSizeIterator for Iter<'_, K> {
1512     #[inline]
1513     fn len(&self) -> usize {
1514         self.base.len()
1515     }
1516 }
1517 #[stable(feature = "fused", since = "1.26.0")]
1518 impl<K> FusedIterator for Iter<'_, K> {}
1519
1520 #[stable(feature = "std_debug", since = "1.16.0")]
1521 impl<K: fmt::Debug> fmt::Debug for Iter<'_, K> {
1522     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1523         f.debug_list().entries(self.clone()).finish()
1524     }
1525 }
1526
1527 #[stable(feature = "rust1", since = "1.0.0")]
1528 impl<K> Iterator for IntoIter<K> {
1529     type Item = K;
1530
1531     #[inline]
1532     fn next(&mut self) -> Option<K> {
1533         self.base.next()
1534     }
1535     #[inline]
1536     fn size_hint(&self) -> (usize, Option<usize>) {
1537         self.base.size_hint()
1538     }
1539 }
1540 #[stable(feature = "rust1", since = "1.0.0")]
1541 impl<K> ExactSizeIterator for IntoIter<K> {
1542     #[inline]
1543     fn len(&self) -> usize {
1544         self.base.len()
1545     }
1546 }
1547 #[stable(feature = "fused", since = "1.26.0")]
1548 impl<K> FusedIterator for IntoIter<K> {}
1549
1550 #[stable(feature = "std_debug", since = "1.16.0")]
1551 impl<K: fmt::Debug> fmt::Debug for IntoIter<K> {
1552     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1553         fmt::Debug::fmt(&self.base, f)
1554     }
1555 }
1556
1557 #[stable(feature = "rust1", since = "1.0.0")]
1558 impl<'a, K> Iterator for Drain<'a, K> {
1559     type Item = K;
1560
1561     #[inline]
1562     fn next(&mut self) -> Option<K> {
1563         self.base.next()
1564     }
1565     #[inline]
1566     fn size_hint(&self) -> (usize, Option<usize>) {
1567         self.base.size_hint()
1568     }
1569 }
1570 #[stable(feature = "rust1", since = "1.0.0")]
1571 impl<K> ExactSizeIterator for Drain<'_, K> {
1572     #[inline]
1573     fn len(&self) -> usize {
1574         self.base.len()
1575     }
1576 }
1577 #[stable(feature = "fused", since = "1.26.0")]
1578 impl<K> FusedIterator for Drain<'_, K> {}
1579
1580 #[stable(feature = "std_debug", since = "1.16.0")]
1581 impl<K: fmt::Debug> fmt::Debug for Drain<'_, K> {
1582     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1583         fmt::Debug::fmt(&self.base, f)
1584     }
1585 }
1586
1587 #[unstable(feature = "hash_drain_filter", issue = "59618")]
1588 impl<K, F> Iterator for DrainFilter<'_, K, F>
1589 where
1590     F: FnMut(&K) -> bool,
1591 {
1592     type Item = K;
1593
1594     #[inline]
1595     fn next(&mut self) -> Option<K> {
1596         self.base.next()
1597     }
1598     #[inline]
1599     fn size_hint(&self) -> (usize, Option<usize>) {
1600         self.base.size_hint()
1601     }
1602 }
1603
1604 #[unstable(feature = "hash_drain_filter", issue = "59618")]
1605 impl<K, F> FusedIterator for DrainFilter<'_, K, F> where F: FnMut(&K) -> bool {}
1606
1607 #[unstable(feature = "hash_drain_filter", issue = "59618")]
1608 impl<'a, K, F> fmt::Debug for DrainFilter<'a, K, F>
1609 where
1610     F: FnMut(&K) -> bool,
1611 {
1612     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1613         f.debug_struct("DrainFilter").finish_non_exhaustive()
1614     }
1615 }
1616
1617 #[stable(feature = "rust1", since = "1.0.0")]
1618 impl<T, S> Clone for Intersection<'_, T, S> {
1619     #[inline]
1620     fn clone(&self) -> Self {
1621         Intersection { iter: self.iter.clone(), ..*self }
1622     }
1623 }
1624
1625 #[stable(feature = "rust1", since = "1.0.0")]
1626 impl<'a, T, S> Iterator for Intersection<'a, T, S>
1627 where
1628     T: Eq + Hash,
1629     S: BuildHasher,
1630 {
1631     type Item = &'a T;
1632
1633     #[inline]
1634     fn next(&mut self) -> Option<&'a T> {
1635         loop {
1636             let elt = self.iter.next()?;
1637             if self.other.contains(elt) {
1638                 return Some(elt);
1639             }
1640         }
1641     }
1642
1643     #[inline]
1644     fn size_hint(&self) -> (usize, Option<usize>) {
1645         let (_, upper) = self.iter.size_hint();
1646         (0, upper)
1647     }
1648 }
1649
1650 #[stable(feature = "std_debug", since = "1.16.0")]
1651 impl<T, S> fmt::Debug for Intersection<'_, T, S>
1652 where
1653     T: fmt::Debug + Eq + Hash,
1654     S: BuildHasher,
1655 {
1656     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1657         f.debug_list().entries(self.clone()).finish()
1658     }
1659 }
1660
1661 #[stable(feature = "fused", since = "1.26.0")]
1662 impl<T, S> FusedIterator for Intersection<'_, T, S>
1663 where
1664     T: Eq + Hash,
1665     S: BuildHasher,
1666 {
1667 }
1668
1669 #[stable(feature = "rust1", since = "1.0.0")]
1670 impl<T, S> Clone for Difference<'_, T, S> {
1671     #[inline]
1672     fn clone(&self) -> Self {
1673         Difference { iter: self.iter.clone(), ..*self }
1674     }
1675 }
1676
1677 #[stable(feature = "rust1", since = "1.0.0")]
1678 impl<'a, T, S> Iterator for Difference<'a, T, S>
1679 where
1680     T: Eq + Hash,
1681     S: BuildHasher,
1682 {
1683     type Item = &'a T;
1684
1685     #[inline]
1686     fn next(&mut self) -> Option<&'a T> {
1687         loop {
1688             let elt = self.iter.next()?;
1689             if !self.other.contains(elt) {
1690                 return Some(elt);
1691             }
1692         }
1693     }
1694
1695     #[inline]
1696     fn size_hint(&self) -> (usize, Option<usize>) {
1697         let (_, upper) = self.iter.size_hint();
1698         (0, upper)
1699     }
1700 }
1701
1702 #[stable(feature = "fused", since = "1.26.0")]
1703 impl<T, S> FusedIterator for Difference<'_, T, S>
1704 where
1705     T: Eq + Hash,
1706     S: BuildHasher,
1707 {
1708 }
1709
1710 #[stable(feature = "std_debug", since = "1.16.0")]
1711 impl<T, S> fmt::Debug for Difference<'_, T, S>
1712 where
1713     T: fmt::Debug + Eq + Hash,
1714     S: BuildHasher,
1715 {
1716     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1717         f.debug_list().entries(self.clone()).finish()
1718     }
1719 }
1720
1721 #[stable(feature = "rust1", since = "1.0.0")]
1722 impl<T, S> Clone for SymmetricDifference<'_, T, S> {
1723     #[inline]
1724     fn clone(&self) -> Self {
1725         SymmetricDifference { iter: self.iter.clone() }
1726     }
1727 }
1728
1729 #[stable(feature = "rust1", since = "1.0.0")]
1730 impl<'a, T, S> Iterator for SymmetricDifference<'a, T, S>
1731 where
1732     T: Eq + Hash,
1733     S: BuildHasher,
1734 {
1735     type Item = &'a T;
1736
1737     #[inline]
1738     fn next(&mut self) -> Option<&'a T> {
1739         self.iter.next()
1740     }
1741     #[inline]
1742     fn size_hint(&self) -> (usize, Option<usize>) {
1743         self.iter.size_hint()
1744     }
1745 }
1746
1747 #[stable(feature = "fused", since = "1.26.0")]
1748 impl<T, S> FusedIterator for SymmetricDifference<'_, T, S>
1749 where
1750     T: Eq + Hash,
1751     S: BuildHasher,
1752 {
1753 }
1754
1755 #[stable(feature = "std_debug", since = "1.16.0")]
1756 impl<T, S> fmt::Debug for SymmetricDifference<'_, T, S>
1757 where
1758     T: fmt::Debug + Eq + Hash,
1759     S: BuildHasher,
1760 {
1761     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1762         f.debug_list().entries(self.clone()).finish()
1763     }
1764 }
1765
1766 #[stable(feature = "rust1", since = "1.0.0")]
1767 impl<T, S> Clone for Union<'_, T, S> {
1768     #[inline]
1769     fn clone(&self) -> Self {
1770         Union { iter: self.iter.clone() }
1771     }
1772 }
1773
1774 #[stable(feature = "fused", since = "1.26.0")]
1775 impl<T, S> FusedIterator for Union<'_, T, S>
1776 where
1777     T: Eq + Hash,
1778     S: BuildHasher,
1779 {
1780 }
1781
1782 #[stable(feature = "std_debug", since = "1.16.0")]
1783 impl<T, S> fmt::Debug for Union<'_, T, S>
1784 where
1785     T: fmt::Debug + Eq + Hash,
1786     S: BuildHasher,
1787 {
1788     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1789         f.debug_list().entries(self.clone()).finish()
1790     }
1791 }
1792
1793 #[stable(feature = "rust1", since = "1.0.0")]
1794 impl<'a, T, S> Iterator for Union<'a, T, S>
1795 where
1796     T: Eq + Hash,
1797     S: BuildHasher,
1798 {
1799     type Item = &'a T;
1800
1801     #[inline]
1802     fn next(&mut self) -> Option<&'a T> {
1803         self.iter.next()
1804     }
1805     #[inline]
1806     fn size_hint(&self) -> (usize, Option<usize>) {
1807         self.iter.size_hint()
1808     }
1809 }
1810
1811 #[allow(dead_code)]
1812 fn assert_covariance() {
1813     fn set<'new>(v: HashSet<&'static str>) -> HashSet<&'new str> {
1814         v
1815     }
1816     fn iter<'a, 'new>(v: Iter<'a, &'static str>) -> Iter<'a, &'new str> {
1817         v
1818     }
1819     fn into_iter<'new>(v: IntoIter<&'static str>) -> IntoIter<&'new str> {
1820         v
1821     }
1822     fn difference<'a, 'new>(
1823         v: Difference<'a, &'static str, RandomState>,
1824     ) -> Difference<'a, &'new str, RandomState> {
1825         v
1826     }
1827     fn symmetric_difference<'a, 'new>(
1828         v: SymmetricDifference<'a, &'static str, RandomState>,
1829     ) -> SymmetricDifference<'a, &'new str, RandomState> {
1830         v
1831     }
1832     fn intersection<'a, 'new>(
1833         v: Intersection<'a, &'static str, RandomState>,
1834     ) -> Intersection<'a, &'new str, RandomState> {
1835         v
1836     }
1837     fn union<'a, 'new>(
1838         v: Union<'a, &'static str, RandomState>,
1839     ) -> Union<'a, &'new str, RandomState> {
1840         v
1841     }
1842     fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
1843         d
1844     }
1845 }