src/libstd/collections/hash/set.rs

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