src/libstd/collections/hash/set.rs

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