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