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