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