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 use crate::raw::{Allocator, Global};
12 
13 // Future Optimization (FIXME!)
14 // =============================
15 //
16 // Iteration over zero sized values is a noop. There is no need
17 // for `bucket.val` in the case of HashSet. I suppose we would need HKT
18 // to get rid of it properly.
19 
20 /// A hash set implemented as a `HashMap` where the value is `()`.
21 ///
22 /// As with the [`HashMap`] type, a `HashSet` requires that the elements
23 /// implement the [`Eq`] and [`Hash`] traits. This can frequently be achieved by
24 /// using `#[derive(PartialEq, Eq, Hash)]`. If you implement these yourself,
25 /// it is important that the following property holds:
26 ///
27 /// ```text
28 /// k1 == k2 -> hash(k1) == hash(k2)
29 /// ```
30 ///
31 /// In other words, if two keys are equal, their hashes must be equal.
32 ///
33 ///
34 /// It is a logic error for an item to be modified in such a way that the
35 /// item's hash, as determined by the [`Hash`] trait, or its equality, as
36 /// determined by the [`Eq`] trait, changes while it is in the set. This is
37 /// normally only possible through [`Cell`], [`RefCell`], global state, I/O, or
38 /// unsafe code.
39 ///
40 /// It is also a logic error for the [`Hash`] implementation of a key to panic.
41 /// This is generally only possible if the trait is implemented manually. If a
42 /// panic does occur then the contents of the `HashSet` may become corrupted and
43 /// some items may be dropped from the table.
44 ///
45 /// # Examples
46 ///
47 /// ```
48 /// use hashbrown::HashSet;
49 /// // Type inference lets us omit an explicit type signature (which
50 /// // would be `HashSet<String>` in this example).
51 /// let mut books = HashSet::new();
52 ///
53 /// // Add some books.
54 /// books.insert("A Dance With Dragons".to_string());
55 /// books.insert("To Kill a Mockingbird".to_string());
56 /// books.insert("The Odyssey".to_string());
57 /// books.insert("The Great Gatsby".to_string());
58 ///
59 /// // Check for a specific one.
60 /// if !books.contains("The Winds of Winter") {
61 ///     println!("We have {} books, but The Winds of Winter ain't one.",
62 ///              books.len());
63 /// }
64 ///
65 /// // Remove a book.
66 /// books.remove("The Odyssey");
67 ///
68 /// // Iterate over everything.
69 /// for book in &books {
70 ///     println!("{}", book);
71 /// }
72 /// ```
73 ///
74 /// The easiest way to use `HashSet` with a custom type is to derive
75 /// [`Eq`] and [`Hash`]. We must also derive [`PartialEq`]. This will in the
76 /// future be implied by [`Eq`].
77 ///
78 /// ```
79 /// use hashbrown::HashSet;
80 /// #[derive(Hash, Eq, PartialEq, Debug)]
81 /// struct Viking {
82 ///     name: String,
83 ///     power: usize,
84 /// }
85 ///
86 /// let mut vikings = HashSet::new();
87 ///
88 /// vikings.insert(Viking { name: "Einar".to_string(), power: 9 });
89 /// vikings.insert(Viking { name: "Einar".to_string(), power: 9 });
90 /// vikings.insert(Viking { name: "Olaf".to_string(), power: 4 });
91 /// vikings.insert(Viking { name: "Harald".to_string(), power: 8 });
92 ///
93 /// // Use derived implementation to print the vikings.
94 /// for x in &vikings {
95 ///     println!("{:?}", x);
96 /// }
97 /// ```
98 ///
99 /// A `HashSet` with fixed list of elements can be initialized from an array:
100 ///
101 /// ```
102 /// use hashbrown::HashSet;
103 ///
104 /// let viking_names: HashSet<&'static str> =
105 ///     [ "Einar", "Olaf", "Harald" ].iter().cloned().collect();
106 /// // use the values stored in the set
107 /// ```
108 ///
109 /// [`Cell`]: https://doc.rust-lang.org/std/cell/struct.Cell.html
110 /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
111 /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
112 /// [`HashMap`]: struct.HashMap.html
113 /// [`PartialEq`]: https://doc.rust-lang.org/std/cmp/trait.PartialEq.html
114 /// [`RefCell`]: https://doc.rust-lang.org/std/cell/struct.RefCell.html
115 pub struct HashSet<T, S = DefaultHashBuilder, A: Allocator + Clone = Global> {
116     pub(crate) map: HashMap<T, (), S, A>,
117 }
118 
119 impl<T: Clone, S: Clone, A: Allocator + Clone> Clone for HashSet<T, S, A> {
clone(&self) -> Self120     fn clone(&self) -> Self {
121         HashSet {
122             map: self.map.clone(),
123         }
124     }
125 
clone_from(&mut self, source: &Self)126     fn clone_from(&mut self, source: &Self) {
127         self.map.clone_from(&source.map);
128     }
129 }
130 
131 #[cfg(feature = "ahash")]
132 impl<T> HashSet<T, DefaultHashBuilder> {
133     /// Creates an empty `HashSet`.
134     ///
135     /// The hash set is initially created with a capacity of 0, so it will not allocate until it
136     /// is first inserted into.
137     ///
138     /// # Examples
139     ///
140     /// ```
141     /// use hashbrown::HashSet;
142     /// let set: HashSet<i32> = HashSet::new();
143     /// ```
144     #[cfg_attr(feature = "inline-more", inline)]
new() -> Self145     pub fn new() -> Self {
146         Self {
147             map: HashMap::new(),
148         }
149     }
150 
151     /// Creates an empty `HashSet` with the specified capacity.
152     ///
153     /// The hash set will be able to hold at least `capacity` elements without
154     /// reallocating. If `capacity` is 0, the hash set will not allocate.
155     ///
156     /// # Examples
157     ///
158     /// ```
159     /// use hashbrown::HashSet;
160     /// let set: HashSet<i32> = HashSet::with_capacity(10);
161     /// assert!(set.capacity() >= 10);
162     /// ```
163     #[cfg_attr(feature = "inline-more", inline)]
with_capacity(capacity: usize) -> Self164     pub fn with_capacity(capacity: usize) -> Self {
165         Self {
166             map: HashMap::with_capacity(capacity),
167         }
168     }
169 }
170 
171 #[cfg(feature = "ahash")]
172 impl<T: Hash + Eq, A: Allocator + Clone> HashSet<T, DefaultHashBuilder, A> {
173     /// Creates an empty `HashSet`.
174     ///
175     /// The hash set is initially created with a capacity of 0, so it will not allocate until it
176     /// is first inserted into.
177     ///
178     /// # Examples
179     ///
180     /// ```
181     /// use hashbrown::HashSet;
182     /// let set: HashSet<i32> = HashSet::new();
183     /// ```
184     #[cfg_attr(feature = "inline-more", inline)]
new_in(alloc: A) -> Self185     pub fn new_in(alloc: A) -> Self {
186         Self {
187             map: HashMap::new_in(alloc),
188         }
189     }
190 
191     /// Creates an empty `HashSet` with the specified capacity.
192     ///
193     /// The hash set will be able to hold at least `capacity` elements without
194     /// reallocating. If `capacity` is 0, the hash set will not allocate.
195     ///
196     /// # Examples
197     ///
198     /// ```
199     /// use hashbrown::HashSet;
200     /// let set: HashSet<i32> = HashSet::with_capacity(10);
201     /// assert!(set.capacity() >= 10);
202     /// ```
203     #[cfg_attr(feature = "inline-more", inline)]
with_capacity_in(capacity: usize, alloc: A) -> Self204     pub fn with_capacity_in(capacity: usize, alloc: A) -> Self {
205         Self {
206             map: HashMap::with_capacity_in(capacity, alloc),
207         }
208     }
209 }
210 
211 impl<T, S, A: Allocator + Clone> HashSet<T, S, A> {
212     /// Returns the number of elements the set can hold without reallocating.
213     ///
214     /// # Examples
215     ///
216     /// ```
217     /// use hashbrown::HashSet;
218     /// let set: HashSet<i32> = HashSet::with_capacity(100);
219     /// assert!(set.capacity() >= 100);
220     /// ```
221     #[cfg_attr(feature = "inline-more", inline)]
capacity(&self) -> usize222     pub fn capacity(&self) -> usize {
223         self.map.capacity()
224     }
225 
226     /// An iterator visiting all elements in arbitrary order.
227     /// The iterator element type is `&'a T`.
228     ///
229     /// # Examples
230     ///
231     /// ```
232     /// use hashbrown::HashSet;
233     /// let mut set = HashSet::new();
234     /// set.insert("a");
235     /// set.insert("b");
236     ///
237     /// // Will print in an arbitrary order.
238     /// for x in set.iter() {
239     ///     println!("{}", x);
240     /// }
241     /// ```
242     #[cfg_attr(feature = "inline-more", inline)]
iter(&self) -> Iter<'_, T>243     pub fn iter(&self) -> Iter<'_, T> {
244         Iter {
245             iter: self.map.keys(),
246         }
247     }
248 
249     /// Returns the number of elements in the set.
250     ///
251     /// # Examples
252     ///
253     /// ```
254     /// use hashbrown::HashSet;
255     ///
256     /// let mut v = HashSet::new();
257     /// assert_eq!(v.len(), 0);
258     /// v.insert(1);
259     /// assert_eq!(v.len(), 1);
260     /// ```
261     #[cfg_attr(feature = "inline-more", inline)]
len(&self) -> usize262     pub fn len(&self) -> usize {
263         self.map.len()
264     }
265 
266     /// Returns `true` if the set contains no elements.
267     ///
268     /// # Examples
269     ///
270     /// ```
271     /// use hashbrown::HashSet;
272     ///
273     /// let mut v = HashSet::new();
274     /// assert!(v.is_empty());
275     /// v.insert(1);
276     /// assert!(!v.is_empty());
277     /// ```
278     #[cfg_attr(feature = "inline-more", inline)]
is_empty(&self) -> bool279     pub fn is_empty(&self) -> bool {
280         self.map.is_empty()
281     }
282 
283     /// Clears the set, returning all elements in an iterator.
284     ///
285     /// # Examples
286     ///
287     /// ```
288     /// use hashbrown::HashSet;
289     ///
290     /// let mut set: HashSet<_> = [1, 2, 3].iter().cloned().collect();
291     /// assert!(!set.is_empty());
292     ///
293     /// // print 1, 2, 3 in an arbitrary order
294     /// for i in set.drain() {
295     ///     println!("{}", i);
296     /// }
297     ///
298     /// assert!(set.is_empty());
299     /// ```
300     #[cfg_attr(feature = "inline-more", inline)]
drain(&mut self) -> Drain<'_, T, A>301     pub fn drain(&mut self) -> Drain<'_, T, A> {
302         Drain {
303             iter: self.map.drain(),
304         }
305     }
306 
307     /// Retains only the elements specified by the predicate.
308     ///
309     /// In other words, remove all elements `e` such that `f(&e)` returns `false`.
310     ///
311     /// # Examples
312     ///
313     /// ```
314     /// use hashbrown::HashSet;
315     ///
316     /// let xs = [1,2,3,4,5,6];
317     /// let mut set: HashSet<i32> = xs.iter().cloned().collect();
318     /// set.retain(|&k| k % 2 == 0);
319     /// assert_eq!(set.len(), 3);
320     /// ```
retain<F>(&mut self, mut f: F) where F: FnMut(&T) -> bool,321     pub fn retain<F>(&mut self, mut f: F)
322     where
323         F: FnMut(&T) -> bool,
324     {
325         self.map.retain(|k, _| f(k));
326     }
327 
328     /// Drains elements which are true under the given predicate,
329     /// and returns an iterator over the removed items.
330     ///
331     /// In other words, move all elements `e` such that `f(&e)` returns `true` out
332     /// into another iterator.
333     ///
334     /// When the returned DrainedFilter is dropped, any remaining elements that satisfy
335     /// the predicate are dropped from the set.
336     ///
337     /// # Examples
338     ///
339     /// ```
340     /// use hashbrown::HashSet;
341     ///
342     /// let mut set: HashSet<i32> = (0..8).collect();
343     /// let drained: HashSet<i32> = set.drain_filter(|v| v % 2 == 0).collect();
344     ///
345     /// let mut evens = drained.into_iter().collect::<Vec<_>>();
346     /// let mut odds = set.into_iter().collect::<Vec<_>>();
347     /// evens.sort();
348     /// odds.sort();
349     ///
350     /// assert_eq!(evens, vec![0, 2, 4, 6]);
351     /// assert_eq!(odds, vec![1, 3, 5, 7]);
352     /// ```
353     #[cfg_attr(feature = "inline-more", inline)]
drain_filter<F>(&mut self, f: F) -> DrainFilter<'_, T, F, A> where F: FnMut(&T) -> bool,354     pub fn drain_filter<F>(&mut self, f: F) -> DrainFilter<'_, T, F, A>
355     where
356         F: FnMut(&T) -> bool,
357     {
358         DrainFilter {
359             f,
360             inner: DrainFilterInner {
361                 iter: unsafe { self.map.table.iter() },
362                 table: &mut self.map.table,
363             },
364         }
365     }
366 
367     /// Clears the set, removing all values.
368     ///
369     /// # Examples
370     ///
371     /// ```
372     /// use hashbrown::HashSet;
373     ///
374     /// let mut v = HashSet::new();
375     /// v.insert(1);
376     /// v.clear();
377     /// assert!(v.is_empty());
378     /// ```
379     #[cfg_attr(feature = "inline-more", inline)]
clear(&mut self)380     pub fn clear(&mut self) {
381         self.map.clear();
382     }
383 }
384 
385 impl<T, S> HashSet<T, S, Global> {
386     /// Creates a new empty hash set which will use the given hasher to hash
387     /// keys.
388     ///
389     /// The hash set is also created with the default initial capacity.
390     ///
391     /// Warning: `hasher` is normally randomly generated, and
392     /// is designed to allow `HashSet`s to be resistant to attacks that
393     /// cause many collisions and very poor performance. Setting it
394     /// manually using this function can expose a DoS attack vector.
395     ///
396     /// The `hash_builder` passed should implement the [`BuildHasher`] trait for
397     /// the HashMap to be useful, see its documentation for details.
398     ///
399     ///
400     /// # Examples
401     ///
402     /// ```
403     /// use hashbrown::HashSet;
404     /// use hashbrown::hash_map::DefaultHashBuilder;
405     ///
406     /// let s = DefaultHashBuilder::default();
407     /// let mut set = HashSet::with_hasher(s);
408     /// set.insert(2);
409     /// ```
410     ///
411     /// [`BuildHasher`]: ../../std/hash/trait.BuildHasher.html
412     #[cfg_attr(feature = "inline-more", inline)]
with_hasher(hasher: S) -> Self413     pub const fn with_hasher(hasher: S) -> Self {
414         Self {
415             map: HashMap::with_hasher(hasher),
416         }
417     }
418 
419     /// Creates an empty `HashSet` with the specified capacity, using
420     /// `hasher` to hash the keys.
421     ///
422     /// The hash set will be able to hold at least `capacity` elements without
423     /// reallocating. If `capacity` is 0, the hash set will not allocate.
424     ///
425     /// Warning: `hasher` is normally randomly generated, and
426     /// is designed to allow `HashSet`s to be resistant to attacks that
427     /// cause many collisions and very poor performance. Setting it
428     /// manually using this function can expose a DoS attack vector.
429     ///
430     /// The `hash_builder` passed should implement the [`BuildHasher`] trait for
431     /// the HashMap to be useful, see its documentation for details.
432     ///
433     /// # Examples
434     ///
435     /// ```
436     /// use hashbrown::HashSet;
437     /// use hashbrown::hash_map::DefaultHashBuilder;
438     ///
439     /// let s = DefaultHashBuilder::default();
440     /// let mut set = HashSet::with_capacity_and_hasher(10, s);
441     /// set.insert(1);
442     /// ```
443     ///
444     /// [`BuildHasher`]: ../../std/hash/trait.BuildHasher.html
445     #[cfg_attr(feature = "inline-more", inline)]
with_capacity_and_hasher(capacity: usize, hasher: S) -> Self446     pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> Self {
447         Self {
448             map: HashMap::with_capacity_and_hasher(capacity, hasher),
449         }
450     }
451 }
452 
453 impl<T, S, A> HashSet<T, S, A>
454 where
455     A: Allocator + Clone,
456 {
457     /// Returns a reference to the underlying allocator.
458     #[inline]
allocator(&self) -> &A459     pub fn allocator(&self) -> &A {
460         self.map.allocator()
461     }
462 
463     /// Creates a new empty hash set which will use the given hasher to hash
464     /// keys.
465     ///
466     /// The hash set is also created with the default initial capacity.
467     ///
468     /// Warning: `hasher` is normally randomly generated, and
469     /// is designed to allow `HashSet`s to be resistant to attacks that
470     /// cause many collisions and very poor performance. Setting it
471     /// manually using this function can expose a DoS attack vector.
472     ///
473     /// # Examples
474     ///
475     /// ```
476     /// use hashbrown::HashSet;
477     /// use hashbrown::hash_map::DefaultHashBuilder;
478     ///
479     /// let s = DefaultHashBuilder::default();
480     /// let mut set = HashSet::with_hasher(s);
481     /// set.insert(2);
482     /// ```
483     #[cfg_attr(feature = "inline-more", inline)]
with_hasher_in(hasher: S, alloc: A) -> Self484     pub fn with_hasher_in(hasher: S, alloc: A) -> Self {
485         Self {
486             map: HashMap::with_hasher_in(hasher, alloc),
487         }
488     }
489 
490     /// Creates an empty `HashSet` with the specified capacity, using
491     /// `hasher` to hash the keys.
492     ///
493     /// The hash set will be able to hold at least `capacity` elements without
494     /// reallocating. If `capacity` is 0, the hash set will not allocate.
495     ///
496     /// Warning: `hasher` is normally randomly generated, and
497     /// is designed to allow `HashSet`s to be resistant to attacks that
498     /// cause many collisions and very poor performance. Setting it
499     /// manually using this function can expose a DoS attack vector.
500     ///
501     /// # Examples
502     ///
503     /// ```
504     /// use hashbrown::HashSet;
505     /// use hashbrown::hash_map::DefaultHashBuilder;
506     ///
507     /// let s = DefaultHashBuilder::default();
508     /// let mut set = HashSet::with_capacity_and_hasher(10, s);
509     /// set.insert(1);
510     /// ```
511     #[cfg_attr(feature = "inline-more", inline)]
with_capacity_and_hasher_in(capacity: usize, hasher: S, alloc: A) -> Self512     pub fn with_capacity_and_hasher_in(capacity: usize, hasher: S, alloc: A) -> Self {
513         Self {
514             map: HashMap::with_capacity_and_hasher_in(capacity, hasher, alloc),
515         }
516     }
517 
518     /// Returns a reference to the set's [`BuildHasher`].
519     ///
520     /// [`BuildHasher`]: https://doc.rust-lang.org/std/hash/trait.BuildHasher.html
521     ///
522     /// # Examples
523     ///
524     /// ```
525     /// use hashbrown::HashSet;
526     /// use hashbrown::hash_map::DefaultHashBuilder;
527     ///
528     /// let hasher = DefaultHashBuilder::default();
529     /// let set: HashSet<i32> = HashSet::with_hasher(hasher);
530     /// let hasher: &DefaultHashBuilder = set.hasher();
531     /// ```
532     #[cfg_attr(feature = "inline-more", inline)]
hasher(&self) -> &S533     pub fn hasher(&self) -> &S {
534         self.map.hasher()
535     }
536 }
537 
538 impl<T, S, A> HashSet<T, S, A>
539 where
540     T: Eq + Hash,
541     S: BuildHasher,
542     A: Allocator + Clone,
543 {
544     /// Reserves capacity for at least `additional` more elements to be inserted
545     /// in the `HashSet`. The collection may reserve more space to avoid
546     /// frequent reallocations.
547     ///
548     /// # Panics
549     ///
550     /// Panics if the new allocation size overflows `usize`.
551     ///
552     /// # Examples
553     ///
554     /// ```
555     /// use hashbrown::HashSet;
556     /// let mut set: HashSet<i32> = HashSet::new();
557     /// set.reserve(10);
558     /// assert!(set.capacity() >= 10);
559     /// ```
560     #[cfg_attr(feature = "inline-more", inline)]
reserve(&mut self, additional: usize)561     pub fn reserve(&mut self, additional: usize) {
562         self.map.reserve(additional);
563     }
564 
565     /// Tries to reserve capacity for at least `additional` more elements to be inserted
566     /// in the given `HashSet<K,V>`. The collection may reserve more space to avoid
567     /// frequent reallocations.
568     ///
569     /// # Errors
570     ///
571     /// If the capacity overflows, or the allocator reports a failure, then an error
572     /// is returned.
573     ///
574     /// # Examples
575     ///
576     /// ```
577     /// use hashbrown::HashSet;
578     /// let mut set: HashSet<i32> = HashSet::new();
579     /// set.try_reserve(10).expect("why is the test harness OOMing on 10 bytes?");
580     /// ```
581     #[cfg_attr(feature = "inline-more", inline)]
try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError>582     pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
583         self.map.try_reserve(additional)
584     }
585 
586     /// Shrinks the capacity of the set as much as possible. It will drop
587     /// down as much as possible while maintaining the internal rules
588     /// and possibly leaving some space in accordance with the resize policy.
589     ///
590     /// # Examples
591     ///
592     /// ```
593     /// use hashbrown::HashSet;
594     ///
595     /// let mut set = HashSet::with_capacity(100);
596     /// set.insert(1);
597     /// set.insert(2);
598     /// assert!(set.capacity() >= 100);
599     /// set.shrink_to_fit();
600     /// assert!(set.capacity() >= 2);
601     /// ```
602     #[cfg_attr(feature = "inline-more", inline)]
shrink_to_fit(&mut self)603     pub fn shrink_to_fit(&mut self) {
604         self.map.shrink_to_fit();
605     }
606 
607     /// Shrinks the capacity of the set with a lower limit. It will drop
608     /// down no lower than the supplied limit while maintaining the internal rules
609     /// and possibly leaving some space in accordance with the resize policy.
610     ///
611     /// Panics if the current capacity is smaller than the supplied
612     /// minimum capacity.
613     ///
614     /// # Examples
615     ///
616     /// ```
617     /// use hashbrown::HashSet;
618     ///
619     /// let mut set = HashSet::with_capacity(100);
620     /// set.insert(1);
621     /// set.insert(2);
622     /// assert!(set.capacity() >= 100);
623     /// set.shrink_to(10);
624     /// assert!(set.capacity() >= 10);
625     /// set.shrink_to(0);
626     /// assert!(set.capacity() >= 2);
627     /// ```
628     #[cfg_attr(feature = "inline-more", inline)]
shrink_to(&mut self, min_capacity: usize)629     pub fn shrink_to(&mut self, min_capacity: usize) {
630         self.map.shrink_to(min_capacity);
631     }
632 
633     /// Visits the values representing the difference,
634     /// i.e., the values that are in `self` but not in `other`.
635     ///
636     /// # Examples
637     ///
638     /// ```
639     /// use hashbrown::HashSet;
640     /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
641     /// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect();
642     ///
643     /// // Can be seen as `a - b`.
644     /// for x in a.difference(&b) {
645     ///     println!("{}", x); // Print 1
646     /// }
647     ///
648     /// let diff: HashSet<_> = a.difference(&b).collect();
649     /// assert_eq!(diff, [1].iter().collect());
650     ///
651     /// // Note that difference is not symmetric,
652     /// // and `b - a` means something else:
653     /// let diff: HashSet<_> = b.difference(&a).collect();
654     /// assert_eq!(diff, [4].iter().collect());
655     /// ```
656     #[cfg_attr(feature = "inline-more", inline)]
difference<'a>(&'a self, other: &'a Self) -> Difference<'a, T, S, A>657     pub fn difference<'a>(&'a self, other: &'a Self) -> Difference<'a, T, S, A> {
658         Difference {
659             iter: self.iter(),
660             other,
661         }
662     }
663 
664     /// Visits the values representing the symmetric difference,
665     /// i.e., the values that are in `self` or in `other` but not in both.
666     ///
667     /// # Examples
668     ///
669     /// ```
670     /// use hashbrown::HashSet;
671     /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
672     /// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect();
673     ///
674     /// // Print 1, 4 in arbitrary order.
675     /// for x in a.symmetric_difference(&b) {
676     ///     println!("{}", x);
677     /// }
678     ///
679     /// let diff1: HashSet<_> = a.symmetric_difference(&b).collect();
680     /// let diff2: HashSet<_> = b.symmetric_difference(&a).collect();
681     ///
682     /// assert_eq!(diff1, diff2);
683     /// assert_eq!(diff1, [1, 4].iter().collect());
684     /// ```
685     #[cfg_attr(feature = "inline-more", inline)]
symmetric_difference<'a>(&'a self, other: &'a Self) -> SymmetricDifference<'a, T, S, A>686     pub fn symmetric_difference<'a>(&'a self, other: &'a Self) -> SymmetricDifference<'a, T, S, A> {
687         SymmetricDifference {
688             iter: self.difference(other).chain(other.difference(self)),
689         }
690     }
691 
692     /// Visits the values representing the intersection,
693     /// i.e., the values that are both in `self` and `other`.
694     ///
695     /// # Examples
696     ///
697     /// ```
698     /// use hashbrown::HashSet;
699     /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
700     /// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect();
701     ///
702     /// // Print 2, 3 in arbitrary order.
703     /// for x in a.intersection(&b) {
704     ///     println!("{}", x);
705     /// }
706     ///
707     /// let intersection: HashSet<_> = a.intersection(&b).collect();
708     /// assert_eq!(intersection, [2, 3].iter().collect());
709     /// ```
710     #[cfg_attr(feature = "inline-more", inline)]
intersection<'a>(&'a self, other: &'a Self) -> Intersection<'a, T, S, A>711     pub fn intersection<'a>(&'a self, other: &'a Self) -> Intersection<'a, T, S, A> {
712         let (smaller, larger) = if self.len() <= other.len() {
713             (self, other)
714         } else {
715             (other, self)
716         };
717         Intersection {
718             iter: smaller.iter(),
719             other: larger,
720         }
721     }
722 
723     /// Visits the values representing the union,
724     /// i.e., all the values in `self` or `other`, without duplicates.
725     ///
726     /// # Examples
727     ///
728     /// ```
729     /// use hashbrown::HashSet;
730     /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
731     /// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect();
732     ///
733     /// // Print 1, 2, 3, 4 in arbitrary order.
734     /// for x in a.union(&b) {
735     ///     println!("{}", x);
736     /// }
737     ///
738     /// let union: HashSet<_> = a.union(&b).collect();
739     /// assert_eq!(union, [1, 2, 3, 4].iter().collect());
740     /// ```
741     #[cfg_attr(feature = "inline-more", inline)]
union<'a>(&'a self, other: &'a Self) -> Union<'a, T, S, A>742     pub fn union<'a>(&'a self, other: &'a Self) -> Union<'a, T, S, A> {
743         // We'll iterate one set in full, and only the remaining difference from the other.
744         // Use the smaller set for the difference in order to reduce hash lookups.
745         let (smaller, larger) = if self.len() <= other.len() {
746             (self, other)
747         } else {
748             (other, self)
749         };
750         Union {
751             iter: larger.iter().chain(smaller.difference(larger)),
752         }
753     }
754 
755     /// Returns `true` if the set contains a value.
756     ///
757     /// The value may be any borrowed form of the set's value type, but
758     /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
759     /// the value type.
760     ///
761     /// # Examples
762     ///
763     /// ```
764     /// use hashbrown::HashSet;
765     ///
766     /// let set: HashSet<_> = [1, 2, 3].iter().cloned().collect();
767     /// assert_eq!(set.contains(&1), true);
768     /// assert_eq!(set.contains(&4), false);
769     /// ```
770     ///
771     /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
772     /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
773     #[cfg_attr(feature = "inline-more", inline)]
contains<Q: ?Sized>(&self, value: &Q) -> bool where T: Borrow<Q>, Q: Hash + Eq,774     pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool
775     where
776         T: Borrow<Q>,
777         Q: Hash + Eq,
778     {
779         self.map.contains_key(value)
780     }
781 
782     /// Returns a reference to the value in the set, if any, that is equal to the given value.
783     ///
784     /// The value may be any borrowed form of the set's value type, but
785     /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
786     /// the value type.
787     ///
788     /// # Examples
789     ///
790     /// ```
791     /// use hashbrown::HashSet;
792     ///
793     /// let set: HashSet<_> = [1, 2, 3].iter().cloned().collect();
794     /// assert_eq!(set.get(&2), Some(&2));
795     /// assert_eq!(set.get(&4), None);
796     /// ```
797     ///
798     /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
799     /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
800     #[cfg_attr(feature = "inline-more", inline)]
get<Q: ?Sized>(&self, value: &Q) -> Option<&T> where T: Borrow<Q>, Q: Hash + Eq,801     pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T>
802     where
803         T: Borrow<Q>,
804         Q: Hash + Eq,
805     {
806         // Avoid `Option::map` because it bloats LLVM IR.
807         match self.map.get_key_value(value) {
808             Some((k, _)) => Some(k),
809             None => None,
810         }
811     }
812 
813     /// Inserts the given `value` into the set if it is not present, then
814     /// returns a reference to the value in the set.
815     ///
816     /// # Examples
817     ///
818     /// ```
819     /// use hashbrown::HashSet;
820     ///
821     /// let mut set: HashSet<_> = [1, 2, 3].iter().cloned().collect();
822     /// assert_eq!(set.len(), 3);
823     /// assert_eq!(set.get_or_insert(2), &2);
824     /// assert_eq!(set.get_or_insert(100), &100);
825     /// assert_eq!(set.len(), 4); // 100 was inserted
826     /// ```
827     #[cfg_attr(feature = "inline-more", inline)]
get_or_insert(&mut self, value: T) -> &T828     pub fn get_or_insert(&mut self, value: T) -> &T {
829         // Although the raw entry gives us `&mut T`, we only return `&T` to be consistent with
830         // `get`. Key mutation is "raw" because you're not supposed to affect `Eq` or `Hash`.
831         self.map
832             .raw_entry_mut()
833             .from_key(&value)
834             .or_insert(value, ())
835             .0
836     }
837 
838     /// Inserts an owned copy of the given `value` into the set if it is not
839     /// present, then returns a reference to the value in the set.
840     ///
841     /// # Examples
842     ///
843     /// ```
844     /// use hashbrown::HashSet;
845     ///
846     /// let mut set: HashSet<String> = ["cat", "dog", "horse"]
847     ///     .iter().map(|&pet| pet.to_owned()).collect();
848     ///
849     /// assert_eq!(set.len(), 3);
850     /// for &pet in &["cat", "dog", "fish"] {
851     ///     let value = set.get_or_insert_owned(pet);
852     ///     assert_eq!(value, pet);
853     /// }
854     /// assert_eq!(set.len(), 4); // a new "fish" was inserted
855     /// ```
856     #[inline]
get_or_insert_owned<Q: ?Sized>(&mut self, value: &Q) -> &T where T: Borrow<Q>, Q: Hash + Eq + ToOwned<Owned = T>,857     pub fn get_or_insert_owned<Q: ?Sized>(&mut self, value: &Q) -> &T
858     where
859         T: Borrow<Q>,
860         Q: Hash + Eq + ToOwned<Owned = T>,
861     {
862         // Although the raw entry gives us `&mut T`, we only return `&T` to be consistent with
863         // `get`. Key mutation is "raw" because you're not supposed to affect `Eq` or `Hash`.
864         self.map
865             .raw_entry_mut()
866             .from_key(value)
867             .or_insert_with(|| (value.to_owned(), ()))
868             .0
869     }
870 
871     /// Inserts a value computed from `f` into the set if the given `value` is
872     /// not present, then returns a reference to the value in the set.
873     ///
874     /// # Examples
875     ///
876     /// ```
877     /// use hashbrown::HashSet;
878     ///
879     /// let mut set: HashSet<String> = ["cat", "dog", "horse"]
880     ///     .iter().map(|&pet| pet.to_owned()).collect();
881     ///
882     /// assert_eq!(set.len(), 3);
883     /// for &pet in &["cat", "dog", "fish"] {
884     ///     let value = set.get_or_insert_with(pet, str::to_owned);
885     ///     assert_eq!(value, pet);
886     /// }
887     /// assert_eq!(set.len(), 4); // a new "fish" was inserted
888     /// ```
889     #[cfg_attr(feature = "inline-more", inline)]
get_or_insert_with<Q: ?Sized, F>(&mut self, value: &Q, f: F) -> &T where T: Borrow<Q>, Q: Hash + Eq, F: FnOnce(&Q) -> T,890     pub fn get_or_insert_with<Q: ?Sized, F>(&mut self, value: &Q, f: F) -> &T
891     where
892         T: Borrow<Q>,
893         Q: Hash + Eq,
894         F: FnOnce(&Q) -> T,
895     {
896         // Although the raw entry gives us `&mut T`, we only return `&T` to be consistent with
897         // `get`. Key mutation is "raw" because you're not supposed to affect `Eq` or `Hash`.
898         self.map
899             .raw_entry_mut()
900             .from_key(value)
901             .or_insert_with(|| (f(value), ()))
902             .0
903     }
904 
905     /// Gets the given value's corresponding entry in the set for in-place manipulation.
906     ///
907     /// # Examples
908     ///
909     /// ```
910     /// use hashbrown::HashSet;
911     /// use hashbrown::hash_set::Entry::*;
912     ///
913     /// let mut singles = HashSet::new();
914     /// let mut dupes = HashSet::new();
915     ///
916     /// for ch in "a short treatise on fungi".chars() {
917     ///     if let Vacant(dupe_entry) = dupes.entry(ch) {
918     ///         // We haven't already seen a duplicate, so
919     ///         // check if we've at least seen it once.
920     ///         match singles.entry(ch) {
921     ///             Vacant(single_entry) => {
922     ///                 // We found a new character for the first time.
923     ///                 single_entry.insert()
924     ///             }
925     ///             Occupied(single_entry) => {
926     ///                 // We've already seen this once, "move" it to dupes.
927     ///                 single_entry.remove();
928     ///                 dupe_entry.insert();
929     ///             }
930     ///         }
931     ///     }
932     /// }
933     ///
934     /// assert!(!singles.contains(&'t') && dupes.contains(&'t'));
935     /// assert!(singles.contains(&'u') && !dupes.contains(&'u'));
936     /// assert!(!singles.contains(&'v') && !dupes.contains(&'v'));
937     /// ```
938     #[cfg_attr(feature = "inline-more", inline)]
entry(&mut self, value: T) -> Entry<'_, T, S, A>939     pub fn entry(&mut self, value: T) -> Entry<'_, T, S, A> {
940         match self.map.entry(value) {
941             map::Entry::Occupied(entry) => Entry::Occupied(OccupiedEntry { inner: entry }),
942             map::Entry::Vacant(entry) => Entry::Vacant(VacantEntry { inner: entry }),
943         }
944     }
945 
946     /// Returns `true` if `self` has no elements in common with `other`.
947     /// This is equivalent to checking for an empty intersection.
948     ///
949     /// # Examples
950     ///
951     /// ```
952     /// use hashbrown::HashSet;
953     ///
954     /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
955     /// let mut b = HashSet::new();
956     ///
957     /// assert_eq!(a.is_disjoint(&b), true);
958     /// b.insert(4);
959     /// assert_eq!(a.is_disjoint(&b), true);
960     /// b.insert(1);
961     /// assert_eq!(a.is_disjoint(&b), false);
962     /// ```
is_disjoint(&self, other: &Self) -> bool963     pub fn is_disjoint(&self, other: &Self) -> bool {
964         self.iter().all(|v| !other.contains(v))
965     }
966 
967     /// Returns `true` if the set is a subset of another,
968     /// i.e., `other` contains at least all the values in `self`.
969     ///
970     /// # Examples
971     ///
972     /// ```
973     /// use hashbrown::HashSet;
974     ///
975     /// let sup: HashSet<_> = [1, 2, 3].iter().cloned().collect();
976     /// let mut set = HashSet::new();
977     ///
978     /// assert_eq!(set.is_subset(&sup), true);
979     /// set.insert(2);
980     /// assert_eq!(set.is_subset(&sup), true);
981     /// set.insert(4);
982     /// assert_eq!(set.is_subset(&sup), false);
983     /// ```
is_subset(&self, other: &Self) -> bool984     pub fn is_subset(&self, other: &Self) -> bool {
985         self.len() <= other.len() && self.iter().all(|v| other.contains(v))
986     }
987 
988     /// Returns `true` if the set is a superset of another,
989     /// i.e., `self` contains at least all the values in `other`.
990     ///
991     /// # Examples
992     ///
993     /// ```
994     /// use hashbrown::HashSet;
995     ///
996     /// let sub: HashSet<_> = [1, 2].iter().cloned().collect();
997     /// let mut set = HashSet::new();
998     ///
999     /// assert_eq!(set.is_superset(&sub), false);
1000     ///
1001     /// set.insert(0);
1002     /// set.insert(1);
1003     /// assert_eq!(set.is_superset(&sub), false);
1004     ///
1005     /// set.insert(2);
1006     /// assert_eq!(set.is_superset(&sub), true);
1007     /// ```
1008     #[cfg_attr(feature = "inline-more", inline)]
is_superset(&self, other: &Self) -> bool1009     pub fn is_superset(&self, other: &Self) -> bool {
1010         other.is_subset(self)
1011     }
1012 
1013     /// Adds a value to the set.
1014     ///
1015     /// If the set did not have this value present, `true` is returned.
1016     ///
1017     /// If the set did have this value present, `false` is returned.
1018     ///
1019     /// # Examples
1020     ///
1021     /// ```
1022     /// use hashbrown::HashSet;
1023     ///
1024     /// let mut set = HashSet::new();
1025     ///
1026     /// assert_eq!(set.insert(2), true);
1027     /// assert_eq!(set.insert(2), false);
1028     /// assert_eq!(set.len(), 1);
1029     /// ```
1030     #[cfg_attr(feature = "inline-more", inline)]
insert(&mut self, value: T) -> bool1031     pub fn insert(&mut self, value: T) -> bool {
1032         self.map.insert(value, ()).is_none()
1033     }
1034 
1035     /// Insert a value the set without checking if the value already exists in the set.
1036     ///
1037     /// Returns a reference to the value just inserted.
1038     ///
1039     /// This operation is safe if a value does not exist in the set.
1040     ///
1041     /// However, if a value exists in the set already, the behavior is unspecified:
1042     /// this operation may panic, loop forever, or any following operation with the set
1043     /// may panic, loop forever or return arbitrary result.
1044     ///
1045     /// That said, this operation (and following operations) are guaranteed to
1046     /// not violate memory safety.
1047     ///
1048     /// This operation is faster than regular insert, because it does not perform
1049     /// lookup before insertion.
1050     ///
1051     /// This operation is useful during initial population of the set.
1052     /// For example, when constructing a set from another set, we know
1053     /// that values are unique.
1054     #[cfg_attr(feature = "inline-more", inline)]
insert_unique_unchecked(&mut self, value: T) -> &T1055     pub fn insert_unique_unchecked(&mut self, value: T) -> &T {
1056         self.map.insert_unique_unchecked(value, ()).0
1057     }
1058 
1059     /// Adds a value to the set, replacing the existing value, if any, that is equal to the given
1060     /// one. Returns the replaced value.
1061     ///
1062     /// # Examples
1063     ///
1064     /// ```
1065     /// use hashbrown::HashSet;
1066     ///
1067     /// let mut set = HashSet::new();
1068     /// set.insert(Vec::<i32>::new());
1069     ///
1070     /// assert_eq!(set.get(&[][..]).unwrap().capacity(), 0);
1071     /// set.replace(Vec::with_capacity(10));
1072     /// assert_eq!(set.get(&[][..]).unwrap().capacity(), 10);
1073     /// ```
1074     #[cfg_attr(feature = "inline-more", inline)]
replace(&mut self, value: T) -> Option<T>1075     pub fn replace(&mut self, value: T) -> Option<T> {
1076         match self.map.entry(value) {
1077             map::Entry::Occupied(occupied) => Some(occupied.replace_key()),
1078             map::Entry::Vacant(vacant) => {
1079                 vacant.insert(());
1080                 None
1081             }
1082         }
1083     }
1084 
1085     /// Removes a value from the set. Returns whether the value was
1086     /// present in the set.
1087     ///
1088     /// The value may be any borrowed form of the set's value type, but
1089     /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
1090     /// the value type.
1091     ///
1092     /// # Examples
1093     ///
1094     /// ```
1095     /// use hashbrown::HashSet;
1096     ///
1097     /// let mut set = HashSet::new();
1098     ///
1099     /// set.insert(2);
1100     /// assert_eq!(set.remove(&2), true);
1101     /// assert_eq!(set.remove(&2), false);
1102     /// ```
1103     ///
1104     /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
1105     /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
1106     #[cfg_attr(feature = "inline-more", inline)]
remove<Q: ?Sized>(&mut self, value: &Q) -> bool where T: Borrow<Q>, Q: Hash + Eq,1107     pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool
1108     where
1109         T: Borrow<Q>,
1110         Q: Hash + Eq,
1111     {
1112         self.map.remove(value).is_some()
1113     }
1114 
1115     /// Removes and returns the value in the set, if any, that is equal to the given one.
1116     ///
1117     /// The value may be any borrowed form of the set's value type, but
1118     /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
1119     /// the value type.
1120     ///
1121     /// # Examples
1122     ///
1123     /// ```
1124     /// use hashbrown::HashSet;
1125     ///
1126     /// let mut set: HashSet<_> = [1, 2, 3].iter().cloned().collect();
1127     /// assert_eq!(set.take(&2), Some(2));
1128     /// assert_eq!(set.take(&2), None);
1129     /// ```
1130     ///
1131     /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
1132     /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
1133     #[cfg_attr(feature = "inline-more", inline)]
take<Q: ?Sized>(&mut self, value: &Q) -> Option<T> where T: Borrow<Q>, Q: Hash + Eq,1134     pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T>
1135     where
1136         T: Borrow<Q>,
1137         Q: Hash + Eq,
1138     {
1139         // Avoid `Option::map` because it bloats LLVM IR.
1140         match self.map.remove_entry(value) {
1141             Some((k, _)) => Some(k),
1142             None => None,
1143         }
1144     }
1145 }
1146 
1147 impl<T, S, A> PartialEq for HashSet<T, S, A>
1148 where
1149     T: Eq + Hash,
1150     S: BuildHasher,
1151     A: Allocator + Clone,
1152 {
eq(&self, other: &Self) -> bool1153     fn eq(&self, other: &Self) -> bool {
1154         if self.len() != other.len() {
1155             return false;
1156         }
1157 
1158         self.iter().all(|key| other.contains(key))
1159     }
1160 }
1161 
1162 impl<T, S, A> Eq for HashSet<T, S, A>
1163 where
1164     T: Eq + Hash,
1165     S: BuildHasher,
1166     A: Allocator + Clone,
1167 {
1168 }
1169 
1170 impl<T, S, A> fmt::Debug for HashSet<T, S, A>
1171 where
1172     T: fmt::Debug,
1173     A: Allocator + Clone,
1174 {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1175     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1176         f.debug_set().entries(self.iter()).finish()
1177     }
1178 }
1179 
1180 impl<T, S, A> From<HashMap<T, (), S, A>> for HashSet<T, S, A>
1181 where
1182     A: Allocator + Clone,
1183 {
from(map: HashMap<T, (), S, A>) -> Self1184     fn from(map: HashMap<T, (), S, A>) -> Self {
1185         Self { map }
1186     }
1187 }
1188 
1189 impl<T, S, A> FromIterator<T> for HashSet<T, S, A>
1190 where
1191     T: Eq + Hash,
1192     S: BuildHasher + Default,
1193     A: Default + Allocator + Clone,
1194 {
1195     #[cfg_attr(feature = "inline-more", inline)]
from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self1196     fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
1197         let mut set = Self::with_hasher_in(Default::default(), Default::default());
1198         set.extend(iter);
1199         set
1200     }
1201 }
1202 
1203 // The default hasher is used to match the std implementation signature
1204 #[cfg(feature = "ahash")]
1205 impl<T, A, const N: usize> From<[T; N]> for HashSet<T, DefaultHashBuilder, A>
1206 where
1207     T: Eq + Hash,
1208     A: Default + Allocator + Clone,
1209 {
1210     /// # Examples
1211     ///
1212     /// ```
1213     /// use hashbrown::HashSet;
1214     ///
1215     /// let set1 = HashSet::from([1, 2, 3, 4]);
1216     /// let set2: HashSet<_> = [1, 2, 3, 4].into();
1217     /// assert_eq!(set1, set2);
1218     /// ```
from(arr: [T; N]) -> Self1219     fn from(arr: [T; N]) -> Self {
1220         arr.into_iter().collect()
1221     }
1222 }
1223 
1224 impl<T, S, A> Extend<T> for HashSet<T, S, A>
1225 where
1226     T: Eq + Hash,
1227     S: BuildHasher,
1228     A: Allocator + Clone,
1229 {
1230     #[cfg_attr(feature = "inline-more", inline)]
extend<I: IntoIterator<Item = T>>(&mut self, iter: I)1231     fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
1232         self.map.extend(iter.into_iter().map(|k| (k, ())));
1233     }
1234 
1235     #[inline]
1236     #[cfg(feature = "nightly")]
extend_one(&mut self, k: T)1237     fn extend_one(&mut self, k: T) {
1238         self.map.insert(k, ());
1239     }
1240 
1241     #[inline]
1242     #[cfg(feature = "nightly")]
extend_reserve(&mut self, additional: usize)1243     fn extend_reserve(&mut self, additional: usize) {
1244         Extend::<(T, ())>::extend_reserve(&mut self.map, additional);
1245     }
1246 }
1247 
1248 impl<'a, T, S, A> Extend<&'a T> for HashSet<T, S, A>
1249 where
1250     T: 'a + Eq + Hash + Copy,
1251     S: BuildHasher,
1252     A: Allocator + Clone,
1253 {
1254     #[cfg_attr(feature = "inline-more", inline)]
extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I)1255     fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
1256         self.extend(iter.into_iter().copied());
1257     }
1258 
1259     #[inline]
1260     #[cfg(feature = "nightly")]
extend_one(&mut self, k: &'a T)1261     fn extend_one(&mut self, k: &'a T) {
1262         self.map.insert(*k, ());
1263     }
1264 
1265     #[inline]
1266     #[cfg(feature = "nightly")]
extend_reserve(&mut self, additional: usize)1267     fn extend_reserve(&mut self, additional: usize) {
1268         Extend::<(T, ())>::extend_reserve(&mut self.map, additional);
1269     }
1270 }
1271 
1272 impl<T, S, A> Default for HashSet<T, S, A>
1273 where
1274     S: Default,
1275     A: Default + Allocator + Clone,
1276 {
1277     /// Creates an empty `HashSet<T, S>` with the `Default` value for the hasher.
1278     #[cfg_attr(feature = "inline-more", inline)]
default() -> Self1279     fn default() -> Self {
1280         Self {
1281             map: HashMap::default(),
1282         }
1283     }
1284 }
1285 
1286 impl<T, S, A> BitOr<&HashSet<T, S, A>> for &HashSet<T, S, A>
1287 where
1288     T: Eq + Hash + Clone,
1289     S: BuildHasher + Default,
1290     A: Allocator + Clone,
1291 {
1292     type Output = HashSet<T, S>;
1293 
1294     /// Returns the union of `self` and `rhs` as a new `HashSet<T, S>`.
1295     ///
1296     /// # Examples
1297     ///
1298     /// ```
1299     /// use hashbrown::HashSet;
1300     ///
1301     /// let a: HashSet<_> = vec![1, 2, 3].into_iter().collect();
1302     /// let b: HashSet<_> = vec![3, 4, 5].into_iter().collect();
1303     ///
1304     /// let set = &a | &b;
1305     ///
1306     /// let mut i = 0;
1307     /// let expected = [1, 2, 3, 4, 5];
1308     /// for x in &set {
1309     ///     assert!(expected.contains(x));
1310     ///     i += 1;
1311     /// }
1312     /// assert_eq!(i, expected.len());
1313     /// ```
bitor(self, rhs: &HashSet<T, S, A>) -> HashSet<T, S>1314     fn bitor(self, rhs: &HashSet<T, S, A>) -> HashSet<T, S> {
1315         self.union(rhs).cloned().collect()
1316     }
1317 }
1318 
1319 impl<T, S, A> BitAnd<&HashSet<T, S, A>> for &HashSet<T, S, A>
1320 where
1321     T: Eq + Hash + Clone,
1322     S: BuildHasher + Default,
1323     A: Allocator + Clone,
1324 {
1325     type Output = HashSet<T, S>;
1326 
1327     /// Returns the intersection of `self` and `rhs` as a new `HashSet<T, S>`.
1328     ///
1329     /// # Examples
1330     ///
1331     /// ```
1332     /// use hashbrown::HashSet;
1333     ///
1334     /// let a: HashSet<_> = vec![1, 2, 3].into_iter().collect();
1335     /// let b: HashSet<_> = vec![2, 3, 4].into_iter().collect();
1336     ///
1337     /// let set = &a & &b;
1338     ///
1339     /// let mut i = 0;
1340     /// let expected = [2, 3];
1341     /// for x in &set {
1342     ///     assert!(expected.contains(x));
1343     ///     i += 1;
1344     /// }
1345     /// assert_eq!(i, expected.len());
1346     /// ```
bitand(self, rhs: &HashSet<T, S, A>) -> HashSet<T, S>1347     fn bitand(self, rhs: &HashSet<T, S, A>) -> HashSet<T, S> {
1348         self.intersection(rhs).cloned().collect()
1349     }
1350 }
1351 
1352 impl<T, S> BitXor<&HashSet<T, S>> for &HashSet<T, S>
1353 where
1354     T: Eq + Hash + Clone,
1355     S: BuildHasher + Default,
1356 {
1357     type Output = HashSet<T, S>;
1358 
1359     /// Returns the symmetric difference of `self` and `rhs` as a new `HashSet<T, S>`.
1360     ///
1361     /// # Examples
1362     ///
1363     /// ```
1364     /// use hashbrown::HashSet;
1365     ///
1366     /// let a: HashSet<_> = vec![1, 2, 3].into_iter().collect();
1367     /// let b: HashSet<_> = vec![3, 4, 5].into_iter().collect();
1368     ///
1369     /// let set = &a ^ &b;
1370     ///
1371     /// let mut i = 0;
1372     /// let expected = [1, 2, 4, 5];
1373     /// for x in &set {
1374     ///     assert!(expected.contains(x));
1375     ///     i += 1;
1376     /// }
1377     /// assert_eq!(i, expected.len());
1378     /// ```
bitxor(self, rhs: &HashSet<T, S>) -> HashSet<T, S>1379     fn bitxor(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
1380         self.symmetric_difference(rhs).cloned().collect()
1381     }
1382 }
1383 
1384 impl<T, S> Sub<&HashSet<T, S>> for &HashSet<T, S>
1385 where
1386     T: Eq + Hash + Clone,
1387     S: BuildHasher + Default,
1388 {
1389     type Output = HashSet<T, S>;
1390 
1391     /// Returns the difference of `self` and `rhs` as a new `HashSet<T, S>`.
1392     ///
1393     /// # Examples
1394     ///
1395     /// ```
1396     /// use hashbrown::HashSet;
1397     ///
1398     /// let a: HashSet<_> = vec![1, 2, 3].into_iter().collect();
1399     /// let b: HashSet<_> = vec![3, 4, 5].into_iter().collect();
1400     ///
1401     /// let set = &a - &b;
1402     ///
1403     /// let mut i = 0;
1404     /// let expected = [1, 2];
1405     /// for x in &set {
1406     ///     assert!(expected.contains(x));
1407     ///     i += 1;
1408     /// }
1409     /// assert_eq!(i, expected.len());
1410     /// ```
sub(self, rhs: &HashSet<T, S>) -> HashSet<T, S>1411     fn sub(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
1412         self.difference(rhs).cloned().collect()
1413     }
1414 }
1415 
1416 /// An iterator over the items of a `HashSet`.
1417 ///
1418 /// This `struct` is created by the [`iter`] method on [`HashSet`].
1419 /// See its documentation for more.
1420 ///
1421 /// [`HashSet`]: struct.HashSet.html
1422 /// [`iter`]: struct.HashSet.html#method.iter
1423 pub struct Iter<'a, K> {
1424     iter: Keys<'a, K, ()>,
1425 }
1426 
1427 /// An owning iterator over the items of a `HashSet`.
1428 ///
1429 /// This `struct` is created by the [`into_iter`] method on [`HashSet`]
1430 /// (provided by the `IntoIterator` trait). See its documentation for more.
1431 ///
1432 /// [`HashSet`]: struct.HashSet.html
1433 /// [`into_iter`]: struct.HashSet.html#method.into_iter
1434 pub struct IntoIter<K, A: Allocator + Clone = Global> {
1435     iter: map::IntoIter<K, (), A>,
1436 }
1437 
1438 /// A draining iterator over the items of a `HashSet`.
1439 ///
1440 /// This `struct` is created by the [`drain`] method on [`HashSet`].
1441 /// See its documentation for more.
1442 ///
1443 /// [`HashSet`]: struct.HashSet.html
1444 /// [`drain`]: struct.HashSet.html#method.drain
1445 pub struct Drain<'a, K, A: Allocator + Clone = Global> {
1446     iter: map::Drain<'a, K, (), A>,
1447 }
1448 
1449 /// A draining iterator over entries of a `HashSet` which don't satisfy the predicate `f`.
1450 ///
1451 /// This `struct` is created by the [`drain_filter`] method on [`HashSet`]. See its
1452 /// documentation for more.
1453 ///
1454 /// [`drain_filter`]: struct.HashSet.html#method.drain_filter
1455 /// [`HashSet`]: struct.HashSet.html
1456 pub struct DrainFilter<'a, K, F, A: Allocator + Clone = Global>
1457 where
1458     F: FnMut(&K) -> bool,
1459 {
1460     f: F,
1461     inner: DrainFilterInner<'a, K, (), A>,
1462 }
1463 
1464 /// A lazy iterator producing elements in the intersection of `HashSet`s.
1465 ///
1466 /// This `struct` is created by the [`intersection`] method on [`HashSet`].
1467 /// See its documentation for more.
1468 ///
1469 /// [`HashSet`]: struct.HashSet.html
1470 /// [`intersection`]: struct.HashSet.html#method.intersection
1471 pub struct Intersection<'a, T, S, A: Allocator + Clone = Global> {
1472     // iterator of the first set
1473     iter: Iter<'a, T>,
1474     // the second set
1475     other: &'a HashSet<T, S, A>,
1476 }
1477 
1478 /// A lazy iterator producing elements in the difference of `HashSet`s.
1479 ///
1480 /// This `struct` is created by the [`difference`] method on [`HashSet`].
1481 /// See its documentation for more.
1482 ///
1483 /// [`HashSet`]: struct.HashSet.html
1484 /// [`difference`]: struct.HashSet.html#method.difference
1485 pub struct Difference<'a, T, S, A: Allocator + Clone = Global> {
1486     // iterator of the first set
1487     iter: Iter<'a, T>,
1488     // the second set
1489     other: &'a HashSet<T, S, A>,
1490 }
1491 
1492 /// A lazy iterator producing elements in the symmetric difference of `HashSet`s.
1493 ///
1494 /// This `struct` is created by the [`symmetric_difference`] method on
1495 /// [`HashSet`]. See its documentation for more.
1496 ///
1497 /// [`HashSet`]: struct.HashSet.html
1498 /// [`symmetric_difference`]: struct.HashSet.html#method.symmetric_difference
1499 pub struct SymmetricDifference<'a, T, S, A: Allocator + Clone = Global> {
1500     iter: Chain<Difference<'a, T, S, A>, Difference<'a, T, S, A>>,
1501 }
1502 
1503 /// A lazy iterator producing elements in the union of `HashSet`s.
1504 ///
1505 /// This `struct` is created by the [`union`] method on [`HashSet`].
1506 /// See its documentation for more.
1507 ///
1508 /// [`HashSet`]: struct.HashSet.html
1509 /// [`union`]: struct.HashSet.html#method.union
1510 pub struct Union<'a, T, S, A: Allocator + Clone = Global> {
1511     iter: Chain<Iter<'a, T>, Difference<'a, T, S, A>>,
1512 }
1513 
1514 impl<'a, T, S, A: Allocator + Clone> IntoIterator for &'a HashSet<T, S, A> {
1515     type Item = &'a T;
1516     type IntoIter = Iter<'a, T>;
1517 
1518     #[cfg_attr(feature = "inline-more", inline)]
into_iter(self) -> Iter<'a, T>1519     fn into_iter(self) -> Iter<'a, T> {
1520         self.iter()
1521     }
1522 }
1523 
1524 impl<T, S, A: Allocator + Clone> IntoIterator for HashSet<T, S, A> {
1525     type Item = T;
1526     type IntoIter = IntoIter<T, A>;
1527 
1528     /// Creates a consuming iterator, that is, one that moves each value out
1529     /// of the set in arbitrary order. The set cannot be used after calling
1530     /// this.
1531     ///
1532     /// # Examples
1533     ///
1534     /// ```
1535     /// use hashbrown::HashSet;
1536     /// let mut set = HashSet::new();
1537     /// set.insert("a".to_string());
1538     /// set.insert("b".to_string());
1539     ///
1540     /// // Not possible to collect to a Vec<String> with a regular `.iter()`.
1541     /// let v: Vec<String> = set.into_iter().collect();
1542     ///
1543     /// // Will print in an arbitrary order.
1544     /// for x in &v {
1545     ///     println!("{}", x);
1546     /// }
1547     /// ```
1548     #[cfg_attr(feature = "inline-more", inline)]
into_iter(self) -> IntoIter<T, A>1549     fn into_iter(self) -> IntoIter<T, A> {
1550         IntoIter {
1551             iter: self.map.into_iter(),
1552         }
1553     }
1554 }
1555 
1556 impl<K> Clone for Iter<'_, K> {
1557     #[cfg_attr(feature = "inline-more", inline)]
clone(&self) -> Self1558     fn clone(&self) -> Self {
1559         Iter {
1560             iter: self.iter.clone(),
1561         }
1562     }
1563 }
1564 impl<'a, K> Iterator for Iter<'a, K> {
1565     type Item = &'a K;
1566 
1567     #[cfg_attr(feature = "inline-more", inline)]
next(&mut self) -> Option<&'a K>1568     fn next(&mut self) -> Option<&'a K> {
1569         self.iter.next()
1570     }
1571     #[cfg_attr(feature = "inline-more", inline)]
size_hint(&self) -> (usize, Option<usize>)1572     fn size_hint(&self) -> (usize, Option<usize>) {
1573         self.iter.size_hint()
1574     }
1575 }
1576 impl<'a, K> ExactSizeIterator for Iter<'a, K> {
1577     #[cfg_attr(feature = "inline-more", inline)]
len(&self) -> usize1578     fn len(&self) -> usize {
1579         self.iter.len()
1580     }
1581 }
1582 impl<K> FusedIterator for Iter<'_, K> {}
1583 
1584 impl<K: fmt::Debug> fmt::Debug for Iter<'_, K> {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1585     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1586         f.debug_list().entries(self.clone()).finish()
1587     }
1588 }
1589 
1590 impl<K, A: Allocator + Clone> Iterator for IntoIter<K, A> {
1591     type Item = K;
1592 
1593     #[cfg_attr(feature = "inline-more", inline)]
next(&mut self) -> Option<K>1594     fn next(&mut self) -> Option<K> {
1595         // Avoid `Option::map` because it bloats LLVM IR.
1596         match self.iter.next() {
1597             Some((k, _)) => Some(k),
1598             None => None,
1599         }
1600     }
1601     #[cfg_attr(feature = "inline-more", inline)]
size_hint(&self) -> (usize, Option<usize>)1602     fn size_hint(&self) -> (usize, Option<usize>) {
1603         self.iter.size_hint()
1604     }
1605 }
1606 impl<K, A: Allocator + Clone> ExactSizeIterator for IntoIter<K, A> {
1607     #[cfg_attr(feature = "inline-more", inline)]
len(&self) -> usize1608     fn len(&self) -> usize {
1609         self.iter.len()
1610     }
1611 }
1612 impl<K, A: Allocator + Clone> FusedIterator for IntoIter<K, A> {}
1613 
1614 impl<K: fmt::Debug, A: Allocator + Clone> fmt::Debug for IntoIter<K, A> {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1615     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1616         let entries_iter = self.iter.iter().map(|(k, _)| k);
1617         f.debug_list().entries(entries_iter).finish()
1618     }
1619 }
1620 
1621 impl<K, A: Allocator + Clone> Iterator for Drain<'_, K, A> {
1622     type Item = K;
1623 
1624     #[cfg_attr(feature = "inline-more", inline)]
next(&mut self) -> Option<K>1625     fn next(&mut self) -> Option<K> {
1626         // Avoid `Option::map` because it bloats LLVM IR.
1627         match self.iter.next() {
1628             Some((k, _)) => Some(k),
1629             None => None,
1630         }
1631     }
1632     #[cfg_attr(feature = "inline-more", inline)]
size_hint(&self) -> (usize, Option<usize>)1633     fn size_hint(&self) -> (usize, Option<usize>) {
1634         self.iter.size_hint()
1635     }
1636 }
1637 impl<K, A: Allocator + Clone> ExactSizeIterator for Drain<'_, K, A> {
1638     #[cfg_attr(feature = "inline-more", inline)]
len(&self) -> usize1639     fn len(&self) -> usize {
1640         self.iter.len()
1641     }
1642 }
1643 impl<K, A: Allocator + Clone> FusedIterator for Drain<'_, K, A> {}
1644 
1645 impl<K: fmt::Debug, A: Allocator + Clone> fmt::Debug for Drain<'_, K, A> {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1646     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1647         let entries_iter = self.iter.iter().map(|(k, _)| k);
1648         f.debug_list().entries(entries_iter).finish()
1649     }
1650 }
1651 
1652 impl<'a, K, F, A: Allocator + Clone> Drop for DrainFilter<'a, K, F, A>
1653 where
1654     F: FnMut(&K) -> bool,
1655 {
1656     #[cfg_attr(feature = "inline-more", inline)]
drop(&mut self)1657     fn drop(&mut self) {
1658         while let Some(item) = self.next() {
1659             let guard = ConsumeAllOnDrop(self);
1660             drop(item);
1661             mem::forget(guard);
1662         }
1663     }
1664 }
1665 
1666 impl<K, F, A: Allocator + Clone> Iterator for DrainFilter<'_, K, F, A>
1667 where
1668     F: FnMut(&K) -> bool,
1669 {
1670     type Item = K;
1671 
1672     #[cfg_attr(feature = "inline-more", inline)]
next(&mut self) -> Option<Self::Item>1673     fn next(&mut self) -> Option<Self::Item> {
1674         let f = &mut self.f;
1675         let (k, _) = self.inner.next(&mut |k, _| f(k))?;
1676         Some(k)
1677     }
1678 
1679     #[inline]
size_hint(&self) -> (usize, Option<usize>)1680     fn size_hint(&self) -> (usize, Option<usize>) {
1681         (0, self.inner.iter.size_hint().1)
1682     }
1683 }
1684 
1685 impl<K, F, A: Allocator + Clone> FusedIterator for DrainFilter<'_, K, F, A> where
1686     F: FnMut(&K) -> bool
1687 {
1688 }
1689 
1690 impl<T, S, A: Allocator + Clone> Clone for Intersection<'_, T, S, A> {
1691     #[cfg_attr(feature = "inline-more", inline)]
clone(&self) -> Self1692     fn clone(&self) -> Self {
1693         Intersection {
1694             iter: self.iter.clone(),
1695             ..*self
1696         }
1697     }
1698 }
1699 
1700 impl<'a, T, S, A> Iterator for Intersection<'a, T, S, A>
1701 where
1702     T: Eq + Hash,
1703     S: BuildHasher,
1704     A: Allocator + Clone,
1705 {
1706     type Item = &'a T;
1707 
1708     #[cfg_attr(feature = "inline-more", inline)]
next(&mut self) -> Option<&'a T>1709     fn next(&mut self) -> Option<&'a T> {
1710         loop {
1711             let elt = self.iter.next()?;
1712             if self.other.contains(elt) {
1713                 return Some(elt);
1714             }
1715         }
1716     }
1717 
1718     #[cfg_attr(feature = "inline-more", inline)]
size_hint(&self) -> (usize, Option<usize>)1719     fn size_hint(&self) -> (usize, Option<usize>) {
1720         let (_, upper) = self.iter.size_hint();
1721         (0, upper)
1722     }
1723 }
1724 
1725 impl<T, S, A> fmt::Debug for Intersection<'_, T, S, A>
1726 where
1727     T: fmt::Debug + Eq + Hash,
1728     S: BuildHasher,
1729     A: Allocator + Clone,
1730 {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1731     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1732         f.debug_list().entries(self.clone()).finish()
1733     }
1734 }
1735 
1736 impl<T, S, A> FusedIterator for Intersection<'_, T, S, A>
1737 where
1738     T: Eq + Hash,
1739     S: BuildHasher,
1740     A: Allocator + Clone,
1741 {
1742 }
1743 
1744 impl<T, S, A: Allocator + Clone> Clone for Difference<'_, T, S, A> {
1745     #[cfg_attr(feature = "inline-more", inline)]
clone(&self) -> Self1746     fn clone(&self) -> Self {
1747         Difference {
1748             iter: self.iter.clone(),
1749             ..*self
1750         }
1751     }
1752 }
1753 
1754 impl<'a, T, S, A> Iterator for Difference<'a, T, S, A>
1755 where
1756     T: Eq + Hash,
1757     S: BuildHasher,
1758     A: Allocator + Clone,
1759 {
1760     type Item = &'a T;
1761 
1762     #[cfg_attr(feature = "inline-more", inline)]
next(&mut self) -> Option<&'a T>1763     fn next(&mut self) -> Option<&'a T> {
1764         loop {
1765             let elt = self.iter.next()?;
1766             if !self.other.contains(elt) {
1767                 return Some(elt);
1768             }
1769         }
1770     }
1771 
1772     #[cfg_attr(feature = "inline-more", inline)]
size_hint(&self) -> (usize, Option<usize>)1773     fn size_hint(&self) -> (usize, Option<usize>) {
1774         let (_, upper) = self.iter.size_hint();
1775         (0, upper)
1776     }
1777 }
1778 
1779 impl<T, S, A> FusedIterator for Difference<'_, T, S, A>
1780 where
1781     T: Eq + Hash,
1782     S: BuildHasher,
1783     A: Allocator + Clone,
1784 {
1785 }
1786 
1787 impl<T, S, A> fmt::Debug for Difference<'_, T, S, A>
1788 where
1789     T: fmt::Debug + Eq + Hash,
1790     S: BuildHasher,
1791     A: Allocator + Clone,
1792 {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1793     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1794         f.debug_list().entries(self.clone()).finish()
1795     }
1796 }
1797 
1798 impl<T, S, A: Allocator + Clone> Clone for SymmetricDifference<'_, T, S, A> {
1799     #[cfg_attr(feature = "inline-more", inline)]
clone(&self) -> Self1800     fn clone(&self) -> Self {
1801         SymmetricDifference {
1802             iter: self.iter.clone(),
1803         }
1804     }
1805 }
1806 
1807 impl<'a, T, S, A> Iterator for SymmetricDifference<'a, T, S, A>
1808 where
1809     T: Eq + Hash,
1810     S: BuildHasher,
1811     A: Allocator + Clone,
1812 {
1813     type Item = &'a T;
1814 
1815     #[cfg_attr(feature = "inline-more", inline)]
next(&mut self) -> Option<&'a T>1816     fn next(&mut self) -> Option<&'a T> {
1817         self.iter.next()
1818     }
1819     #[cfg_attr(feature = "inline-more", inline)]
size_hint(&self) -> (usize, Option<usize>)1820     fn size_hint(&self) -> (usize, Option<usize>) {
1821         self.iter.size_hint()
1822     }
1823 }
1824 
1825 impl<T, S, A> FusedIterator for SymmetricDifference<'_, T, S, A>
1826 where
1827     T: Eq + Hash,
1828     S: BuildHasher,
1829     A: Allocator + Clone,
1830 {
1831 }
1832 
1833 impl<T, S, A> fmt::Debug for SymmetricDifference<'_, T, S, A>
1834 where
1835     T: fmt::Debug + Eq + Hash,
1836     S: BuildHasher,
1837     A: Allocator + Clone,
1838 {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1839     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1840         f.debug_list().entries(self.clone()).finish()
1841     }
1842 }
1843 
1844 impl<T, S, A: Allocator + Clone> Clone for Union<'_, T, S, A> {
1845     #[cfg_attr(feature = "inline-more", inline)]
clone(&self) -> Self1846     fn clone(&self) -> Self {
1847         Union {
1848             iter: self.iter.clone(),
1849         }
1850     }
1851 }
1852 
1853 impl<T, S, A> FusedIterator for Union<'_, T, S, A>
1854 where
1855     T: Eq + Hash,
1856     S: BuildHasher,
1857     A: Allocator + Clone,
1858 {
1859 }
1860 
1861 impl<T, S, A> fmt::Debug for Union<'_, T, S, A>
1862 where
1863     T: fmt::Debug + Eq + Hash,
1864     S: BuildHasher,
1865     A: Allocator + Clone,
1866 {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1867     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1868         f.debug_list().entries(self.clone()).finish()
1869     }
1870 }
1871 
1872 impl<'a, T, S, A> Iterator for Union<'a, T, S, A>
1873 where
1874     T: Eq + Hash,
1875     S: BuildHasher,
1876     A: Allocator + Clone,
1877 {
1878     type Item = &'a T;
1879 
1880     #[cfg_attr(feature = "inline-more", inline)]
next(&mut self) -> Option<&'a T>1881     fn next(&mut self) -> Option<&'a T> {
1882         self.iter.next()
1883     }
1884     #[cfg_attr(feature = "inline-more", inline)]
size_hint(&self) -> (usize, Option<usize>)1885     fn size_hint(&self) -> (usize, Option<usize>) {
1886         self.iter.size_hint()
1887     }
1888 }
1889 
1890 /// A view into a single entry in a set, which may either be vacant or occupied.
1891 ///
1892 /// This `enum` is constructed from the [`entry`] method on [`HashSet`].
1893 ///
1894 /// [`HashSet`]: struct.HashSet.html
1895 /// [`entry`]: struct.HashSet.html#method.entry
1896 ///
1897 /// # Examples
1898 ///
1899 /// ```
1900 /// use hashbrown::hash_set::{Entry, HashSet, OccupiedEntry};
1901 ///
1902 /// let mut set = HashSet::new();
1903 /// set.extend(["a", "b", "c"]);
1904 /// assert_eq!(set.len(), 3);
1905 ///
1906 /// // Existing value (insert)
1907 /// let entry: Entry<_, _> = set.entry("a");
1908 /// let _raw_o: OccupiedEntry<_, _> = entry.insert();
1909 /// assert_eq!(set.len(), 3);
1910 /// // Nonexistent value (insert)
1911 /// set.entry("d").insert();
1912 ///
1913 /// // Existing value (or_insert)
1914 /// set.entry("b").or_insert();
1915 /// // Nonexistent value (or_insert)
1916 /// set.entry("e").or_insert();
1917 ///
1918 /// println!("Our HashSet: {:?}", set);
1919 ///
1920 /// let mut vec: Vec<_> = set.iter().copied().collect();
1921 /// // The `Iter` iterator produces items in arbitrary order, so the
1922 /// // items must be sorted to test them against a sorted array.
1923 /// vec.sort_unstable();
1924 /// assert_eq!(vec, ["a", "b", "c", "d", "e"]);
1925 /// ```
1926 pub enum Entry<'a, T, S, A = Global>
1927 where
1928     A: Allocator + Clone,
1929 {
1930     /// An occupied entry.
1931     ///
1932     /// # Examples
1933     ///
1934     /// ```
1935     /// use hashbrown::hash_set::{Entry, HashSet};
1936     /// let mut set: HashSet<_> = ["a", "b"].into();
1937     ///
1938     /// match set.entry("a") {
1939     ///     Entry::Vacant(_) => unreachable!(),
1940     ///     Entry::Occupied(_) => { }
1941     /// }
1942     /// ```
1943     Occupied(OccupiedEntry<'a, T, S, A>),
1944 
1945     /// A vacant entry.
1946     ///
1947     /// # Examples
1948     ///
1949     /// ```
1950     /// use hashbrown::hash_set::{Entry, HashSet};
1951     /// let mut set: HashSet<&str> = HashSet::new();
1952     ///
1953     /// match set.entry("a") {
1954     ///     Entry::Occupied(_) => unreachable!(),
1955     ///     Entry::Vacant(_) => { }
1956     /// }
1957     /// ```
1958     Vacant(VacantEntry<'a, T, S, A>),
1959 }
1960 
1961 impl<T: fmt::Debug, S, A: Allocator + Clone> fmt::Debug for Entry<'_, T, S, A> {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1962     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1963         match *self {
1964             Entry::Vacant(ref v) => f.debug_tuple("Entry").field(v).finish(),
1965             Entry::Occupied(ref o) => f.debug_tuple("Entry").field(o).finish(),
1966         }
1967     }
1968 }
1969 
1970 /// A view into an occupied entry in a `HashSet`.
1971 /// It is part of the [`Entry`] enum.
1972 ///
1973 /// [`Entry`]: enum.Entry.html
1974 ///
1975 /// # Examples
1976 ///
1977 /// ```
1978 /// use hashbrown::hash_set::{Entry, HashSet, OccupiedEntry};
1979 ///
1980 /// let mut set = HashSet::new();
1981 /// set.extend(["a", "b", "c"]);
1982 ///
1983 /// let _entry_o: OccupiedEntry<_, _> = set.entry("a").insert();
1984 /// assert_eq!(set.len(), 3);
1985 ///
1986 /// // Existing key
1987 /// match set.entry("a") {
1988 ///     Entry::Vacant(_) => unreachable!(),
1989 ///     Entry::Occupied(view) => {
1990 ///         assert_eq!(view.get(), &"a");
1991 ///     }
1992 /// }
1993 ///
1994 /// assert_eq!(set.len(), 3);
1995 ///
1996 /// // Existing key (take)
1997 /// match set.entry("c") {
1998 ///     Entry::Vacant(_) => unreachable!(),
1999 ///     Entry::Occupied(view) => {
2000 ///         assert_eq!(view.remove(), "c");
2001 ///     }
2002 /// }
2003 /// assert_eq!(set.get(&"c"), None);
2004 /// assert_eq!(set.len(), 2);
2005 /// ```
2006 pub struct OccupiedEntry<'a, T, S, A: Allocator + Clone = Global> {
2007     inner: map::OccupiedEntry<'a, T, (), S, A>,
2008 }
2009 
2010 impl<T: fmt::Debug, S, A: Allocator + Clone> fmt::Debug for OccupiedEntry<'_, T, S, A> {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result2011     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2012         f.debug_struct("OccupiedEntry")
2013             .field("value", self.get())
2014             .finish()
2015     }
2016 }
2017 
2018 /// A view into a vacant entry in a `HashSet`.
2019 /// It is part of the [`Entry`] enum.
2020 ///
2021 /// [`Entry`]: enum.Entry.html
2022 ///
2023 /// # Examples
2024 ///
2025 /// ```
2026 /// use hashbrown::hash_set::{Entry, HashSet, VacantEntry};
2027 ///
2028 /// let mut set = HashSet::<&str>::new();
2029 ///
2030 /// let entry_v: VacantEntry<_, _> = match set.entry("a") {
2031 ///     Entry::Vacant(view) => view,
2032 ///     Entry::Occupied(_) => unreachable!(),
2033 /// };
2034 /// entry_v.insert();
2035 /// assert!(set.contains("a") && set.len() == 1);
2036 ///
2037 /// // Nonexistent key (insert)
2038 /// match set.entry("b") {
2039 ///     Entry::Vacant(view) => view.insert(),
2040 ///     Entry::Occupied(_) => unreachable!(),
2041 /// }
2042 /// assert!(set.contains("b") && set.len() == 2);
2043 /// ```
2044 pub struct VacantEntry<'a, T, S, A: Allocator + Clone = Global> {
2045     inner: map::VacantEntry<'a, T, (), S, A>,
2046 }
2047 
2048 impl<T: fmt::Debug, S, A: Allocator + Clone> fmt::Debug for VacantEntry<'_, T, S, A> {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result2049     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2050         f.debug_tuple("VacantEntry").field(self.get()).finish()
2051     }
2052 }
2053 
2054 impl<'a, T, S, A: Allocator + Clone> Entry<'a, T, S, A> {
2055     /// Sets the value of the entry, and returns an OccupiedEntry.
2056     ///
2057     /// # Examples
2058     ///
2059     /// ```
2060     /// use hashbrown::HashSet;
2061     ///
2062     /// let mut set: HashSet<&str> = HashSet::new();
2063     /// let entry = set.entry("horseyland").insert();
2064     ///
2065     /// assert_eq!(entry.get(), &"horseyland");
2066     /// ```
2067     #[cfg_attr(feature = "inline-more", inline)]
insert(self) -> OccupiedEntry<'a, T, S, A> where T: Hash, S: BuildHasher,2068     pub fn insert(self) -> OccupiedEntry<'a, T, S, A>
2069     where
2070         T: Hash,
2071         S: BuildHasher,
2072     {
2073         match self {
2074             Entry::Occupied(entry) => entry,
2075             Entry::Vacant(entry) => entry.insert_entry(),
2076         }
2077     }
2078 
2079     /// Ensures a value is in the entry by inserting if it was vacant.
2080     ///
2081     /// # Examples
2082     ///
2083     /// ```
2084     /// use hashbrown::HashSet;
2085     ///
2086     /// let mut set: HashSet<&str> = HashSet::new();
2087     ///
2088     /// // nonexistent key
2089     /// set.entry("poneyland").or_insert();
2090     /// assert!(set.contains("poneyland"));
2091     ///
2092     /// // existing key
2093     /// set.entry("poneyland").or_insert();
2094     /// assert!(set.contains("poneyland"));
2095     /// assert_eq!(set.len(), 1);
2096     /// ```
2097     #[cfg_attr(feature = "inline-more", inline)]
or_insert(self) where T: Hash, S: BuildHasher,2098     pub fn or_insert(self)
2099     where
2100         T: Hash,
2101         S: BuildHasher,
2102     {
2103         if let Entry::Vacant(entry) = self {
2104             entry.insert();
2105         }
2106     }
2107 
2108     /// Returns a reference to this entry's value.
2109     ///
2110     /// # Examples
2111     ///
2112     /// ```
2113     /// use hashbrown::HashSet;
2114     ///
2115     /// let mut set: HashSet<&str> = HashSet::new();
2116     /// set.entry("poneyland").or_insert();
2117     /// // existing key
2118     /// assert_eq!(set.entry("poneyland").get(), &"poneyland");
2119     /// // nonexistent key
2120     /// assert_eq!(set.entry("horseland").get(), &"horseland");
2121     /// ```
2122     #[cfg_attr(feature = "inline-more", inline)]
get(&self) -> &T2123     pub fn get(&self) -> &T {
2124         match *self {
2125             Entry::Occupied(ref entry) => entry.get(),
2126             Entry::Vacant(ref entry) => entry.get(),
2127         }
2128     }
2129 }
2130 
2131 impl<T, S, A: Allocator + Clone> OccupiedEntry<'_, T, S, A> {
2132     /// Gets a reference to the value in the entry.
2133     ///
2134     /// # Examples
2135     ///
2136     /// ```
2137     /// use hashbrown::hash_set::{Entry, HashSet};
2138     ///
2139     /// let mut set: HashSet<&str> = HashSet::new();
2140     /// set.entry("poneyland").or_insert();
2141     ///
2142     /// match set.entry("poneyland") {
2143     ///     Entry::Vacant(_) => panic!(),
2144     ///     Entry::Occupied(entry) => assert_eq!(entry.get(), &"poneyland"),
2145     /// }
2146     /// ```
2147     #[cfg_attr(feature = "inline-more", inline)]
get(&self) -> &T2148     pub fn get(&self) -> &T {
2149         self.inner.key()
2150     }
2151 
2152     /// Takes the value out of the entry, and returns it.
2153     /// Keeps the allocated memory for reuse.
2154     ///
2155     /// # Examples
2156     ///
2157     /// ```
2158     /// use hashbrown::HashSet;
2159     /// use hashbrown::hash_set::Entry;
2160     ///
2161     /// let mut set: HashSet<&str> = HashSet::new();
2162     /// // The set is empty
2163     /// assert!(set.is_empty() && set.capacity() == 0);
2164     ///
2165     /// set.entry("poneyland").or_insert();
2166     /// let capacity_before_remove = set.capacity();
2167     ///
2168     /// if let Entry::Occupied(o) = set.entry("poneyland") {
2169     ///     assert_eq!(o.remove(), "poneyland");
2170     /// }
2171     ///
2172     /// assert_eq!(set.contains("poneyland"), false);
2173     /// // Now set hold none elements but capacity is equal to the old one
2174     /// assert!(set.len() == 0 && set.capacity() == capacity_before_remove);
2175     /// ```
2176     #[cfg_attr(feature = "inline-more", inline)]
remove(self) -> T2177     pub fn remove(self) -> T {
2178         self.inner.remove_entry().0
2179     }
2180 
2181     /// Replaces the entry, returning the old value. The new value in the hash map will be
2182     /// the value used to create this entry.
2183     ///
2184     /// # Panics
2185     ///
2186     /// Will panic if this OccupiedEntry was created through [`Entry::insert`].
2187     ///
2188     /// # Examples
2189     ///
2190     /// ```
2191     ///  use hashbrown::hash_set::{Entry, HashSet};
2192     ///  use std::rc::Rc;
2193     ///
2194     ///  let mut set: HashSet<Rc<String>> = HashSet::new();
2195     ///  let key_one = Rc::new("Stringthing".to_string());
2196     ///  let key_two = Rc::new("Stringthing".to_string());
2197     ///
2198     ///  set.insert(key_one.clone());
2199     ///  assert!(Rc::strong_count(&key_one) == 2 && Rc::strong_count(&key_two) == 1);
2200     ///
2201     ///  match set.entry(key_two.clone()) {
2202     ///      Entry::Occupied(entry) => {
2203     ///          let old_key: Rc<String> = entry.replace();
2204     ///          assert!(Rc::ptr_eq(&key_one, &old_key));
2205     ///      }
2206     ///      Entry::Vacant(_) => panic!(),
2207     ///  }
2208     ///
2209     ///  assert!(Rc::strong_count(&key_one) == 1 && Rc::strong_count(&key_two) == 2);
2210     ///  assert!(set.contains(&"Stringthing".to_owned()));
2211     /// ```
2212     #[cfg_attr(feature = "inline-more", inline)]
replace(self) -> T2213     pub fn replace(self) -> T {
2214         self.inner.replace_key()
2215     }
2216 }
2217 
2218 impl<'a, T, S, A: Allocator + Clone> VacantEntry<'a, T, S, A> {
2219     /// Gets a reference to the value that would be used when inserting
2220     /// through the `VacantEntry`.
2221     ///
2222     /// # Examples
2223     ///
2224     /// ```
2225     /// use hashbrown::HashSet;
2226     ///
2227     /// let mut set: HashSet<&str> = HashSet::new();
2228     /// assert_eq!(set.entry("poneyland").get(), &"poneyland");
2229     /// ```
2230     #[cfg_attr(feature = "inline-more", inline)]
get(&self) -> &T2231     pub fn get(&self) -> &T {
2232         self.inner.key()
2233     }
2234 
2235     /// Take ownership of the value.
2236     ///
2237     /// # Examples
2238     ///
2239     /// ```
2240     /// use hashbrown::hash_set::{Entry, HashSet};
2241     ///
2242     /// let mut set: HashSet<&str> = HashSet::new();
2243     ///
2244     /// match set.entry("poneyland") {
2245     ///     Entry::Occupied(_) => panic!(),
2246     ///     Entry::Vacant(v) => assert_eq!(v.into_value(), "poneyland"),
2247     /// }
2248     /// ```
2249     #[cfg_attr(feature = "inline-more", inline)]
into_value(self) -> T2250     pub fn into_value(self) -> T {
2251         self.inner.into_key()
2252     }
2253 
2254     /// Sets the value of the entry with the VacantEntry's value.
2255     ///
2256     /// # Examples
2257     ///
2258     /// ```
2259     /// use hashbrown::HashSet;
2260     /// use hashbrown::hash_set::Entry;
2261     ///
2262     /// let mut set: HashSet<&str> = HashSet::new();
2263     ///
2264     /// if let Entry::Vacant(o) = set.entry("poneyland") {
2265     ///     o.insert();
2266     /// }
2267     /// assert!(set.contains("poneyland"));
2268     /// ```
2269     #[cfg_attr(feature = "inline-more", inline)]
insert(self) where T: Hash, S: BuildHasher,2270     pub fn insert(self)
2271     where
2272         T: Hash,
2273         S: BuildHasher,
2274     {
2275         self.inner.insert(());
2276     }
2277 
2278     #[cfg_attr(feature = "inline-more", inline)]
insert_entry(self) -> OccupiedEntry<'a, T, S, A> where T: Hash, S: BuildHasher,2279     fn insert_entry(self) -> OccupiedEntry<'a, T, S, A>
2280     where
2281         T: Hash,
2282         S: BuildHasher,
2283     {
2284         OccupiedEntry {
2285             inner: self.inner.insert_entry(()),
2286         }
2287     }
2288 }
2289 
2290 #[allow(dead_code)]
assert_covariance()2291 fn assert_covariance() {
2292     fn set<'new>(v: HashSet<&'static str>) -> HashSet<&'new str> {
2293         v
2294     }
2295     fn iter<'a, 'new>(v: Iter<'a, &'static str>) -> Iter<'a, &'new str> {
2296         v
2297     }
2298     fn into_iter<'new, A: Allocator + Clone>(
2299         v: IntoIter<&'static str, A>,
2300     ) -> IntoIter<&'new str, A> {
2301         v
2302     }
2303     fn difference<'a, 'new, A: Allocator + Clone>(
2304         v: Difference<'a, &'static str, DefaultHashBuilder, A>,
2305     ) -> Difference<'a, &'new str, DefaultHashBuilder, A> {
2306         v
2307     }
2308     fn symmetric_difference<'a, 'new, A: Allocator + Clone>(
2309         v: SymmetricDifference<'a, &'static str, DefaultHashBuilder, A>,
2310     ) -> SymmetricDifference<'a, &'new str, DefaultHashBuilder, A> {
2311         v
2312     }
2313     fn intersection<'a, 'new, A: Allocator + Clone>(
2314         v: Intersection<'a, &'static str, DefaultHashBuilder, A>,
2315     ) -> Intersection<'a, &'new str, DefaultHashBuilder, A> {
2316         v
2317     }
2318     fn union<'a, 'new, A: Allocator + Clone>(
2319         v: Union<'a, &'static str, DefaultHashBuilder, A>,
2320     ) -> Union<'a, &'new str, DefaultHashBuilder, A> {
2321         v
2322     }
2323     fn drain<'new, A: Allocator + Clone>(
2324         d: Drain<'static, &'static str, A>,
2325     ) -> Drain<'new, &'new str, A> {
2326         d
2327     }
2328 }
2329 
2330 #[cfg(test)]
2331 mod test_set {
2332     use super::super::map::DefaultHashBuilder;
2333     use super::HashSet;
2334     use std::vec::Vec;
2335 
2336     #[test]
test_zero_capacities()2337     fn test_zero_capacities() {
2338         type HS = HashSet<i32>;
2339 
2340         let s = HS::new();
2341         assert_eq!(s.capacity(), 0);
2342 
2343         let s = HS::default();
2344         assert_eq!(s.capacity(), 0);
2345 
2346         let s = HS::with_hasher(DefaultHashBuilder::default());
2347         assert_eq!(s.capacity(), 0);
2348 
2349         let s = HS::with_capacity(0);
2350         assert_eq!(s.capacity(), 0);
2351 
2352         let s = HS::with_capacity_and_hasher(0, DefaultHashBuilder::default());
2353         assert_eq!(s.capacity(), 0);
2354 
2355         let mut s = HS::new();
2356         s.insert(1);
2357         s.insert(2);
2358         s.remove(&1);
2359         s.remove(&2);
2360         s.shrink_to_fit();
2361         assert_eq!(s.capacity(), 0);
2362 
2363         let mut s = HS::new();
2364         s.reserve(0);
2365         assert_eq!(s.capacity(), 0);
2366     }
2367 
2368     #[test]
test_disjoint()2369     fn test_disjoint() {
2370         let mut xs = HashSet::new();
2371         let mut ys = HashSet::new();
2372         assert!(xs.is_disjoint(&ys));
2373         assert!(ys.is_disjoint(&xs));
2374         assert!(xs.insert(5));
2375         assert!(ys.insert(11));
2376         assert!(xs.is_disjoint(&ys));
2377         assert!(ys.is_disjoint(&xs));
2378         assert!(xs.insert(7));
2379         assert!(xs.insert(19));
2380         assert!(xs.insert(4));
2381         assert!(ys.insert(2));
2382         assert!(ys.insert(-11));
2383         assert!(xs.is_disjoint(&ys));
2384         assert!(ys.is_disjoint(&xs));
2385         assert!(ys.insert(7));
2386         assert!(!xs.is_disjoint(&ys));
2387         assert!(!ys.is_disjoint(&xs));
2388     }
2389 
2390     #[test]
test_subset_and_superset()2391     fn test_subset_and_superset() {
2392         let mut a = HashSet::new();
2393         assert!(a.insert(0));
2394         assert!(a.insert(5));
2395         assert!(a.insert(11));
2396         assert!(a.insert(7));
2397 
2398         let mut b = HashSet::new();
2399         assert!(b.insert(0));
2400         assert!(b.insert(7));
2401         assert!(b.insert(19));
2402         assert!(b.insert(250));
2403         assert!(b.insert(11));
2404         assert!(b.insert(200));
2405 
2406         assert!(!a.is_subset(&b));
2407         assert!(!a.is_superset(&b));
2408         assert!(!b.is_subset(&a));
2409         assert!(!b.is_superset(&a));
2410 
2411         assert!(b.insert(5));
2412 
2413         assert!(a.is_subset(&b));
2414         assert!(!a.is_superset(&b));
2415         assert!(!b.is_subset(&a));
2416         assert!(b.is_superset(&a));
2417     }
2418 
2419     #[test]
test_iterate()2420     fn test_iterate() {
2421         let mut a = HashSet::new();
2422         for i in 0..32 {
2423             assert!(a.insert(i));
2424         }
2425         let mut observed: u32 = 0;
2426         for k in &a {
2427             observed |= 1 << *k;
2428         }
2429         assert_eq!(observed, 0xFFFF_FFFF);
2430     }
2431 
2432     #[test]
test_intersection()2433     fn test_intersection() {
2434         let mut a = HashSet::new();
2435         let mut b = HashSet::new();
2436 
2437         assert!(a.insert(11));
2438         assert!(a.insert(1));
2439         assert!(a.insert(3));
2440         assert!(a.insert(77));
2441         assert!(a.insert(103));
2442         assert!(a.insert(5));
2443         assert!(a.insert(-5));
2444 
2445         assert!(b.insert(2));
2446         assert!(b.insert(11));
2447         assert!(b.insert(77));
2448         assert!(b.insert(-9));
2449         assert!(b.insert(-42));
2450         assert!(b.insert(5));
2451         assert!(b.insert(3));
2452 
2453         let mut i = 0;
2454         let expected = [3, 5, 11, 77];
2455         for x in a.intersection(&b) {
2456             assert!(expected.contains(x));
2457             i += 1;
2458         }
2459         assert_eq!(i, expected.len());
2460     }
2461 
2462     #[test]
test_difference()2463     fn test_difference() {
2464         let mut a = HashSet::new();
2465         let mut b = HashSet::new();
2466 
2467         assert!(a.insert(1));
2468         assert!(a.insert(3));
2469         assert!(a.insert(5));
2470         assert!(a.insert(9));
2471         assert!(a.insert(11));
2472 
2473         assert!(b.insert(3));
2474         assert!(b.insert(9));
2475 
2476         let mut i = 0;
2477         let expected = [1, 5, 11];
2478         for x in a.difference(&b) {
2479             assert!(expected.contains(x));
2480             i += 1;
2481         }
2482         assert_eq!(i, expected.len());
2483     }
2484 
2485     #[test]
test_symmetric_difference()2486     fn test_symmetric_difference() {
2487         let mut a = HashSet::new();
2488         let mut b = HashSet::new();
2489 
2490         assert!(a.insert(1));
2491         assert!(a.insert(3));
2492         assert!(a.insert(5));
2493         assert!(a.insert(9));
2494         assert!(a.insert(11));
2495 
2496         assert!(b.insert(-2));
2497         assert!(b.insert(3));
2498         assert!(b.insert(9));
2499         assert!(b.insert(14));
2500         assert!(b.insert(22));
2501 
2502         let mut i = 0;
2503         let expected = [-2, 1, 5, 11, 14, 22];
2504         for x in a.symmetric_difference(&b) {
2505             assert!(expected.contains(x));
2506             i += 1;
2507         }
2508         assert_eq!(i, expected.len());
2509     }
2510 
2511     #[test]
test_union()2512     fn test_union() {
2513         let mut a = HashSet::new();
2514         let mut b = HashSet::new();
2515 
2516         assert!(a.insert(1));
2517         assert!(a.insert(3));
2518         assert!(a.insert(5));
2519         assert!(a.insert(9));
2520         assert!(a.insert(11));
2521         assert!(a.insert(16));
2522         assert!(a.insert(19));
2523         assert!(a.insert(24));
2524 
2525         assert!(b.insert(-2));
2526         assert!(b.insert(1));
2527         assert!(b.insert(5));
2528         assert!(b.insert(9));
2529         assert!(b.insert(13));
2530         assert!(b.insert(19));
2531 
2532         let mut i = 0;
2533         let expected = [-2, 1, 3, 5, 9, 11, 13, 16, 19, 24];
2534         for x in a.union(&b) {
2535             assert!(expected.contains(x));
2536             i += 1;
2537         }
2538         assert_eq!(i, expected.len());
2539     }
2540 
2541     #[test]
test_from_map()2542     fn test_from_map() {
2543         let mut a = crate::HashMap::new();
2544         a.insert(1, ());
2545         a.insert(2, ());
2546         a.insert(3, ());
2547         a.insert(4, ());
2548 
2549         let a: HashSet<_> = a.into();
2550 
2551         assert_eq!(a.len(), 4);
2552         assert!(a.contains(&1));
2553         assert!(a.contains(&2));
2554         assert!(a.contains(&3));
2555         assert!(a.contains(&4));
2556     }
2557 
2558     #[test]
test_from_iter()2559     fn test_from_iter() {
2560         let xs = [1, 2, 2, 3, 4, 5, 6, 7, 8, 9];
2561 
2562         let set: HashSet<_> = xs.iter().copied().collect();
2563 
2564         for x in &xs {
2565             assert!(set.contains(x));
2566         }
2567 
2568         assert_eq!(set.iter().len(), xs.len() - 1);
2569     }
2570 
2571     #[test]
test_move_iter()2572     fn test_move_iter() {
2573         let hs = {
2574             let mut hs = HashSet::new();
2575 
2576             hs.insert('a');
2577             hs.insert('b');
2578 
2579             hs
2580         };
2581 
2582         let v = hs.into_iter().collect::<Vec<char>>();
2583         assert!(v == ['a', 'b'] || v == ['b', 'a']);
2584     }
2585 
2586     #[test]
test_eq()2587     fn test_eq() {
2588         // These constants once happened to expose a bug in insert().
2589         // I'm keeping them around to prevent a regression.
2590         let mut s1 = HashSet::new();
2591 
2592         s1.insert(1);
2593         s1.insert(2);
2594         s1.insert(3);
2595 
2596         let mut s2 = HashSet::new();
2597 
2598         s2.insert(1);
2599         s2.insert(2);
2600 
2601         assert!(s1 != s2);
2602 
2603         s2.insert(3);
2604 
2605         assert_eq!(s1, s2);
2606     }
2607 
2608     #[test]
test_show()2609     fn test_show() {
2610         let mut set = HashSet::new();
2611         let empty = HashSet::<i32>::new();
2612 
2613         set.insert(1);
2614         set.insert(2);
2615 
2616         let set_str = format!("{:?}", set);
2617 
2618         assert!(set_str == "{1, 2}" || set_str == "{2, 1}");
2619         assert_eq!(format!("{:?}", empty), "{}");
2620     }
2621 
2622     #[test]
test_trivial_drain()2623     fn test_trivial_drain() {
2624         let mut s = HashSet::<i32>::new();
2625         for _ in s.drain() {}
2626         assert!(s.is_empty());
2627         drop(s);
2628 
2629         let mut s = HashSet::<i32>::new();
2630         drop(s.drain());
2631         assert!(s.is_empty());
2632     }
2633 
2634     #[test]
test_drain()2635     fn test_drain() {
2636         let mut s: HashSet<_> = (1..100).collect();
2637 
2638         // try this a bunch of times to make sure we don't screw up internal state.
2639         for _ in 0..20 {
2640             assert_eq!(s.len(), 99);
2641 
2642             {
2643                 let mut last_i = 0;
2644                 let mut d = s.drain();
2645                 for (i, x) in d.by_ref().take(50).enumerate() {
2646                     last_i = i;
2647                     assert!(x != 0);
2648                 }
2649                 assert_eq!(last_i, 49);
2650             }
2651 
2652             for _ in &s {
2653                 panic!("s should be empty!");
2654             }
2655 
2656             // reset to try again.
2657             s.extend(1..100);
2658         }
2659     }
2660 
2661     #[test]
test_replace()2662     fn test_replace() {
2663         use core::hash;
2664 
2665         #[derive(Debug)]
2666         struct Foo(&'static str, i32);
2667 
2668         impl PartialEq for Foo {
2669             fn eq(&self, other: &Self) -> bool {
2670                 self.0 == other.0
2671             }
2672         }
2673 
2674         impl Eq for Foo {}
2675 
2676         impl hash::Hash for Foo {
2677             fn hash<H: hash::Hasher>(&self, h: &mut H) {
2678                 self.0.hash(h);
2679             }
2680         }
2681 
2682         let mut s = HashSet::new();
2683         assert_eq!(s.replace(Foo("a", 1)), None);
2684         assert_eq!(s.len(), 1);
2685         assert_eq!(s.replace(Foo("a", 2)), Some(Foo("a", 1)));
2686         assert_eq!(s.len(), 1);
2687 
2688         let mut it = s.iter();
2689         assert_eq!(it.next(), Some(&Foo("a", 2)));
2690         assert_eq!(it.next(), None);
2691     }
2692 
2693     #[test]
test_extend_ref()2694     fn test_extend_ref() {
2695         let mut a = HashSet::new();
2696         a.insert(1);
2697 
2698         a.extend(&[2, 3, 4]);
2699 
2700         assert_eq!(a.len(), 4);
2701         assert!(a.contains(&1));
2702         assert!(a.contains(&2));
2703         assert!(a.contains(&3));
2704         assert!(a.contains(&4));
2705 
2706         let mut b = HashSet::new();
2707         b.insert(5);
2708         b.insert(6);
2709 
2710         a.extend(&b);
2711 
2712         assert_eq!(a.len(), 6);
2713         assert!(a.contains(&1));
2714         assert!(a.contains(&2));
2715         assert!(a.contains(&3));
2716         assert!(a.contains(&4));
2717         assert!(a.contains(&5));
2718         assert!(a.contains(&6));
2719     }
2720 
2721     #[test]
test_retain()2722     fn test_retain() {
2723         let xs = [1, 2, 3, 4, 5, 6];
2724         let mut set: HashSet<i32> = xs.iter().copied().collect();
2725         set.retain(|&k| k % 2 == 0);
2726         assert_eq!(set.len(), 3);
2727         assert!(set.contains(&2));
2728         assert!(set.contains(&4));
2729         assert!(set.contains(&6));
2730     }
2731 
2732     #[test]
test_drain_filter()2733     fn test_drain_filter() {
2734         {
2735             let mut set: HashSet<i32> = (0..8).collect();
2736             let drained = set.drain_filter(|&k| k % 2 == 0);
2737             let mut out = drained.collect::<Vec<_>>();
2738             out.sort_unstable();
2739             assert_eq!(vec![0, 2, 4, 6], out);
2740             assert_eq!(set.len(), 4);
2741         }
2742         {
2743             let mut set: HashSet<i32> = (0..8).collect();
2744             drop(set.drain_filter(|&k| k % 2 == 0));
2745             assert_eq!(set.len(), 4, "Removes non-matching items on drop");
2746         }
2747     }
2748 
2749     #[test]
test_const_with_hasher()2750     fn test_const_with_hasher() {
2751         use core::hash::BuildHasher;
2752         use std::collections::hash_map::DefaultHasher;
2753 
2754         #[derive(Clone)]
2755         struct MyHasher;
2756         impl BuildHasher for MyHasher {
2757             type Hasher = DefaultHasher;
2758 
2759             fn build_hasher(&self) -> DefaultHasher {
2760                 DefaultHasher::new()
2761             }
2762         }
2763 
2764         const EMPTY_SET: HashSet<u32, MyHasher> = HashSet::with_hasher(MyHasher);
2765 
2766         let mut set = EMPTY_SET;
2767         set.insert(19);
2768         assert!(set.contains(&19));
2769     }
2770 
2771     #[test]
rehash_in_place()2772     fn rehash_in_place() {
2773         let mut set = HashSet::new();
2774 
2775         for i in 0..224 {
2776             set.insert(i);
2777         }
2778 
2779         assert_eq!(
2780             set.capacity(),
2781             224,
2782             "The set must be at or close to capacity to trigger a re hashing"
2783         );
2784 
2785         for i in 100..1400 {
2786             set.remove(&(i - 100));
2787             set.insert(i);
2788         }
2789     }
2790 }
2791