vendor/hashbrown/src/set.rs

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