1use crate::TryReserveError;
2use alloc::borrow::ToOwned;
3use core::borrow::Borrow;
4use core::fmt;
5use core::hash::{BuildHasher, Hash};
6use core::iter::{Chain, FromIterator, FusedIterator};
7use core::mem;
8use core::ops::{BitAnd, BitOr, BitXor, Sub};
9
10use super::map::{self, ConsumeAllOnDrop, DefaultHashBuilder, DrainFilterInner, HashMap, Keys};
11use 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
115pub struct HashSet<T, S = DefaultHashBuilder, A: Allocator + Clone = Global> {
116 pub(crate) map: HashMap<T, (), S, A>,
117}
118
119impl<T: Clone, S: Clone, A: Allocator + Clone> Clone for HashSet<T, S, A> {
120 fn clone(&self) -> Self {
121 HashSet {
122 map: self.map.clone(),
123 }
124 }
125
126 fn clone_from(&mut self, source: &Self) {
127 self.map.clone_from(&source.map);
128 }
129}
130
131#[cfg(feature = "ahash")]
132impl<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)]
145 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)]
164 pub fn with_capacity(capacity: usize) -> Self {
165 Self {
166 map: HashMap::with_capacity(capacity),
167 }
168 }
169}
170
171#[cfg(feature = "ahash")]
172impl<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)]
185 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)]
204 pub fn with_capacity_in(capacity: usize, alloc: A) -> Self {
205 Self {
206 map: HashMap::with_capacity_in(capacity, alloc),
207 }
208 }
209}
210
211impl<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)]
222 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)]
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)]
262 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)]
279 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)]
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 /// ```
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)]
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)]
380 pub fn clear(&mut self) {
381 self.map.clear();
382 }
383}
384
385impl<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)]
413 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)]
446 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
453impl<T, S, A> HashSet<T, S, A>
454where
455 A: Allocator + Clone,
456{
457 /// Returns a reference to the underlying allocator.
458 #[inline]
459 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)]
484 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)]
512 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)]
533 pub fn hasher(&self) -> &S {
534 self.map.hasher()
535 }
536}
537
538impl<T, S, A> HashSet<T, S, A>
539where
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)]
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)]
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)]
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)]
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)]
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)]
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)]
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)]
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)]
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)]
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)]
828 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]
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)]
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)]
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 /// ```
963 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 /// ```
984 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)]
1009 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)]
1031 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)]
1055 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)]
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)]
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)]
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
1147impl<T, S, A> PartialEq for HashSet<T, S, A>
1148where
1149 T: Eq + Hash,
1150 S: BuildHasher,
1151 A: Allocator + Clone,
1152{
1153 fn eq(&self, other: &Self) -> bool {
1154 if self.len() != other.len() {
1155 return false;
1156 }
1157
1158 self.iter().all(|key: &T| other.contains(key))
1159 }
1160}
1161
1162impl<T, S, A> Eq for HashSet<T, S, A>
1163where
1164 T: Eq + Hash,
1165 S: BuildHasher,
1166 A: Allocator + Clone,
1167{
1168}
1169
1170impl<T, S, A> fmt::Debug for HashSet<T, S, A>
1171where
1172 T: fmt::Debug,
1173 A: Allocator + Clone,
1174{
1175 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1176 f.debug_set().entries(self.iter()).finish()
1177 }
1178}
1179
1180impl<T, S, A> From<HashMap<T, (), S, A>> for HashSet<T, S, A>
1181where
1182 A: Allocator + Clone,
1183{
1184 fn from(map: HashMap<T, (), S, A>) -> Self {
1185 Self { map }
1186 }
1187}
1188
1189impl<T, S, A> FromIterator<T> for HashSet<T, S, A>
1190where
1191 T: Eq + Hash,
1192 S: BuildHasher + Default,
1193 A: Default + Allocator + Clone,
1194{
1195 #[cfg_attr(feature = "inline-more", inline)]
1196 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
1197 let mut set: HashSet = Self::with_hasher_in(hasher:Default::default(), alloc: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")]
1205impl<T, A, const N: usize> From<[T; N]> for HashSet<T, DefaultHashBuilder, A>
1206where
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 /// ```
1219 fn from(arr: [T; N]) -> Self {
1220 arr.into_iter().collect()
1221 }
1222}
1223
1224impl<T, S, A> Extend<T> for HashSet<T, S, A>
1225where
1226 T: Eq + Hash,
1227 S: BuildHasher,
1228 A: Allocator + Clone,
1229{
1230 #[cfg_attr(feature = "inline-more", inline)]
1231 fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
1232 self.map.extend(iter.into_iter().map(|k: T| (k, ())));
1233 }
1234
1235 #[inline]
1236 #[cfg(feature = "nightly")]
1237 fn extend_one(&mut self, k: T) {
1238 self.map.insert(k, ());
1239 }
1240
1241 #[inline]
1242 #[cfg(feature = "nightly")]
1243 fn extend_reserve(&mut self, additional: usize) {
1244 Extend::<(T, ())>::extend_reserve(&mut self.map, additional);
1245 }
1246}
1247
1248impl<'a, T, S, A> Extend<&'a T> for HashSet<T, S, A>
1249where
1250 T: 'a + Eq + Hash + Copy,
1251 S: BuildHasher,
1252 A: Allocator + Clone,
1253{
1254 #[cfg_attr(feature = "inline-more", inline)]
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")]
1261 fn extend_one(&mut self, k: &'a T) {
1262 self.map.insert(*k, ());
1263 }
1264
1265 #[inline]
1266 #[cfg(feature = "nightly")]
1267 fn extend_reserve(&mut self, additional: usize) {
1268 Extend::<(T, ())>::extend_reserve(&mut self.map, additional);
1269 }
1270}
1271
1272impl<T, S, A> Default for HashSet<T, S, A>
1273where
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)]
1279 fn default() -> Self {
1280 Self {
1281 map: HashMap::default(),
1282 }
1283 }
1284}
1285
1286impl<T, S, A> BitOr<&HashSet<T, S, A>> for &HashSet<T, S, A>
1287where
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 /// ```
1314 fn bitor(self, rhs: &HashSet<T, S, A>) -> HashSet<T, S> {
1315 self.union(rhs).cloned().collect()
1316 }
1317}
1318
1319impl<T, S, A> BitAnd<&HashSet<T, S, A>> for &HashSet<T, S, A>
1320where
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 /// ```
1347 fn bitand(self, rhs: &HashSet<T, S, A>) -> HashSet<T, S> {
1348 self.intersection(rhs).cloned().collect()
1349 }
1350}
1351
1352impl<T, S> BitXor<&HashSet<T, S>> for &HashSet<T, S>
1353where
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 /// ```
1379 fn bitxor(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
1380 self.symmetric_difference(rhs).cloned().collect()
1381 }
1382}
1383
1384impl<T, S> Sub<&HashSet<T, S>> for &HashSet<T, S>
1385where
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 /// ```
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
1423pub 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
1434pub 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
1445pub 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
1456pub struct DrainFilter<'a, K, F, A: Allocator + Clone = Global>
1457where
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
1471pub 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
1485pub 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
1499pub 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
1510pub struct Union<'a, T, S, A: Allocator + Clone = Global> {
1511 iter: Chain<Iter<'a, T>, Difference<'a, T, S, A>>,
1512}
1513
1514impl<'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)]
1519 fn into_iter(self) -> Iter<'a, T> {
1520 self.iter()
1521 }
1522}
1523
1524impl<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)]
1549 fn into_iter(self) -> IntoIter<T, A> {
1550 IntoIter {
1551 iter: self.map.into_iter(),
1552 }
1553 }
1554}
1555
1556impl<K> Clone for Iter<'_, K> {
1557 #[cfg_attr(feature = "inline-more", inline)]
1558 fn clone(&self) -> Self {
1559 Iter {
1560 iter: self.iter.clone(),
1561 }
1562 }
1563}
1564impl<'a, K> Iterator for Iter<'a, K> {
1565 type Item = &'a K;
1566
1567 #[cfg_attr(feature = "inline-more", inline)]
1568 fn next(&mut self) -> Option<&'a K> {
1569 self.iter.next()
1570 }
1571 #[cfg_attr(feature = "inline-more", inline)]
1572 fn size_hint(&self) -> (usize, Option<usize>) {
1573 self.iter.size_hint()
1574 }
1575}
1576impl<'a, K> ExactSizeIterator for Iter<'a, K> {
1577 #[cfg_attr(feature = "inline-more", inline)]
1578 fn len(&self) -> usize {
1579 self.iter.len()
1580 }
1581}
1582impl<K> FusedIterator for Iter<'_, K> {}
1583
1584impl<K: fmt::Debug> fmt::Debug for Iter<'_, K> {
1585 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1586 f.debug_list().entries(self.clone()).finish()
1587 }
1588}
1589
1590impl<K, A: Allocator + Clone> Iterator for IntoIter<K, A> {
1591 type Item = K;
1592
1593 #[cfg_attr(feature = "inline-more", inline)]
1594 fn next(&mut self) -> Option<K> {
1595 // Avoid `Option::map` because it bloats LLVM IR.
1596 match self.iter.next() {
1597 Some((k: K, _)) => Some(k),
1598 None => None,
1599 }
1600 }
1601 #[cfg_attr(feature = "inline-more", inline)]
1602 fn size_hint(&self) -> (usize, Option<usize>) {
1603 self.iter.size_hint()
1604 }
1605}
1606impl<K, A: Allocator + Clone> ExactSizeIterator for IntoIter<K, A> {
1607 #[cfg_attr(feature = "inline-more", inline)]
1608 fn len(&self) -> usize {
1609 self.iter.len()
1610 }
1611}
1612impl<K, A: Allocator + Clone> FusedIterator for IntoIter<K, A> {}
1613
1614impl<K: fmt::Debug, A: Allocator + Clone> fmt::Debug for IntoIter<K, A> {
1615 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1616 let entries_iter: impl Iterator = self.iter.iter().map(|(k: &K, _)| k);
1617 f.debug_list().entries(entries_iter).finish()
1618 }
1619}
1620
1621impl<K, A: Allocator + Clone> Iterator for Drain<'_, K, A> {
1622 type Item = K;
1623
1624 #[cfg_attr(feature = "inline-more", inline)]
1625 fn next(&mut self) -> Option<K> {
1626 // Avoid `Option::map` because it bloats LLVM IR.
1627 match self.iter.next() {
1628 Some((k: K, _)) => Some(k),
1629 None => None,
1630 }
1631 }
1632 #[cfg_attr(feature = "inline-more", inline)]
1633 fn size_hint(&self) -> (usize, Option<usize>) {
1634 self.iter.size_hint()
1635 }
1636}
1637impl<K, A: Allocator + Clone> ExactSizeIterator for Drain<'_, K, A> {
1638 #[cfg_attr(feature = "inline-more", inline)]
1639 fn len(&self) -> usize {
1640 self.iter.len()
1641 }
1642}
1643impl<K, A: Allocator + Clone> FusedIterator for Drain<'_, K, A> {}
1644
1645impl<K: fmt::Debug, A: Allocator + Clone> fmt::Debug for Drain<'_, K, A> {
1646 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1647 let entries_iter: impl Iterator = self.iter.iter().map(|(k: &K, _)| k);
1648 f.debug_list().entries(entries_iter).finish()
1649 }
1650}
1651
1652impl<'a, K, F, A: Allocator + Clone> Drop for DrainFilter<'a, K, F, A>
1653where
1654 F: FnMut(&K) -> bool,
1655{
1656 #[cfg_attr(feature = "inline-more", inline)]
1657 fn drop(&mut self) {
1658 while let Some(item: K) = self.next() {
1659 let guard: ConsumeAllOnDrop<'_, DrainFilter<'a, …, …, …>> = ConsumeAllOnDrop(self);
1660 drop(item);
1661 mem::forget(guard);
1662 }
1663 }
1664}
1665
1666impl<K, F, A: Allocator + Clone> Iterator for DrainFilter<'_, K, F, A>
1667where
1668 F: FnMut(&K) -> bool,
1669{
1670 type Item = K;
1671
1672 #[cfg_attr(feature = "inline-more", inline)]
1673 fn next(&mut self) -> Option<Self::Item> {
1674 let f: &mut F = &mut self.f;
1675 let (k: K, _) = self.inner.next(&mut |k: &K, _| f(k))?;
1676 Some(k)
1677 }
1678
1679 #[inline]
1680 fn size_hint(&self) -> (usize, Option<usize>) {
1681 (0, self.inner.iter.size_hint().1)
1682 }
1683}
1684
1685impl<K, F, A: Allocator + Clone> FusedIterator for DrainFilter<'_, K, F, A> where
1686 F: FnMut(&K) -> bool
1687{
1688}
1689
1690impl<T, S, A: Allocator + Clone> Clone for Intersection<'_, T, S, A> {
1691 #[cfg_attr(feature = "inline-more", inline)]
1692 fn clone(&self) -> Self {
1693 Intersection {
1694 iter: self.iter.clone(),
1695 ..*self
1696 }
1697 }
1698}
1699
1700impl<'a, T, S, A> Iterator for Intersection<'a, T, S, A>
1701where
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)]
1709 fn next(&mut self) -> Option<&'a T> {
1710 loop {
1711 let elt: &'a T = self.iter.next()?;
1712 if self.other.contains(elt) {
1713 return Some(elt);
1714 }
1715 }
1716 }
1717
1718 #[cfg_attr(feature = "inline-more", inline)]
1719 fn size_hint(&self) -> (usize, Option<usize>) {
1720 let (_, upper: Option) = self.iter.size_hint();
1721 (0, upper)
1722 }
1723}
1724
1725impl<T, S, A> fmt::Debug for Intersection<'_, T, S, A>
1726where
1727 T: fmt::Debug + Eq + Hash,
1728 S: BuildHasher,
1729 A: Allocator + Clone,
1730{
1731 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1732 f.debug_list().entries(self.clone()).finish()
1733 }
1734}
1735
1736impl<T, S, A> FusedIterator for Intersection<'_, T, S, A>
1737where
1738 T: Eq + Hash,
1739 S: BuildHasher,
1740 A: Allocator + Clone,
1741{
1742}
1743
1744impl<T, S, A: Allocator + Clone> Clone for Difference<'_, T, S, A> {
1745 #[cfg_attr(feature = "inline-more", inline)]
1746 fn clone(&self) -> Self {
1747 Difference {
1748 iter: self.iter.clone(),
1749 ..*self
1750 }
1751 }
1752}
1753
1754impl<'a, T, S, A> Iterator for Difference<'a, T, S, A>
1755where
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)]
1763 fn next(&mut self) -> Option<&'a T> {
1764 loop {
1765 let elt: &'a T = self.iter.next()?;
1766 if !self.other.contains(elt) {
1767 return Some(elt);
1768 }
1769 }
1770 }
1771
1772 #[cfg_attr(feature = "inline-more", inline)]
1773 fn size_hint(&self) -> (usize, Option<usize>) {
1774 let (_, upper: Option) = self.iter.size_hint();
1775 (0, upper)
1776 }
1777}
1778
1779impl<T, S, A> FusedIterator for Difference<'_, T, S, A>
1780where
1781 T: Eq + Hash,
1782 S: BuildHasher,
1783 A: Allocator + Clone,
1784{
1785}
1786
1787impl<T, S, A> fmt::Debug for Difference<'_, T, S, A>
1788where
1789 T: fmt::Debug + Eq + Hash,
1790 S: BuildHasher,
1791 A: Allocator + Clone,
1792{
1793 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1794 f.debug_list().entries(self.clone()).finish()
1795 }
1796}
1797
1798impl<T, S, A: Allocator + Clone> Clone for SymmetricDifference<'_, T, S, A> {
1799 #[cfg_attr(feature = "inline-more", inline)]
1800 fn clone(&self) -> Self {
1801 SymmetricDifference {
1802 iter: self.iter.clone(),
1803 }
1804 }
1805}
1806
1807impl<'a, T, S, A> Iterator for SymmetricDifference<'a, T, S, A>
1808where
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)]
1816 fn next(&mut self) -> Option<&'a T> {
1817 self.iter.next()
1818 }
1819 #[cfg_attr(feature = "inline-more", inline)]
1820 fn size_hint(&self) -> (usize, Option<usize>) {
1821 self.iter.size_hint()
1822 }
1823}
1824
1825impl<T, S, A> FusedIterator for SymmetricDifference<'_, T, S, A>
1826where
1827 T: Eq + Hash,
1828 S: BuildHasher,
1829 A: Allocator + Clone,
1830{
1831}
1832
1833impl<T, S, A> fmt::Debug for SymmetricDifference<'_, T, S, A>
1834where
1835 T: fmt::Debug + Eq + Hash,
1836 S: BuildHasher,
1837 A: Allocator + Clone,
1838{
1839 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1840 f.debug_list().entries(self.clone()).finish()
1841 }
1842}
1843
1844impl<T, S, A: Allocator + Clone> Clone for Union<'_, T, S, A> {
1845 #[cfg_attr(feature = "inline-more", inline)]
1846 fn clone(&self) -> Self {
1847 Union {
1848 iter: self.iter.clone(),
1849 }
1850 }
1851}
1852
1853impl<T, S, A> FusedIterator for Union<'_, T, S, A>
1854where
1855 T: Eq + Hash,
1856 S: BuildHasher,
1857 A: Allocator + Clone,
1858{
1859}
1860
1861impl<T, S, A> fmt::Debug for Union<'_, T, S, A>
1862where
1863 T: fmt::Debug + Eq + Hash,
1864 S: BuildHasher,
1865 A: Allocator + Clone,
1866{
1867 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1868 f.debug_list().entries(self.clone()).finish()
1869 }
1870}
1871
1872impl<'a, T, S, A> Iterator for Union<'a, T, S, A>
1873where
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)]
1881 fn next(&mut self) -> Option<&'a T> {
1882 self.iter.next()
1883 }
1884 #[cfg_attr(feature = "inline-more", inline)]
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/// ```
1926pub enum Entry<'a, T, S, A = Global>
1927where
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
1961impl<T: fmt::Debug, S, A: Allocator + Clone> fmt::Debug for Entry<'_, T, S, A> {
1962 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1963 match *self {
1964 Entry::Vacant(ref v: &VacantEntry<'_, T, S, A>) => f.debug_tuple(name:"Entry").field(v).finish(),
1965 Entry::Occupied(ref o: &OccupiedEntry<'_, T, S, A>) => f.debug_tuple(name:"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/// ```
2006pub struct OccupiedEntry<'a, T, S, A: Allocator + Clone = Global> {
2007 inner: map::OccupiedEntry<'a, T, (), S, A>,
2008}
2009
2010impl<T: fmt::Debug, S, A: Allocator + Clone> fmt::Debug for OccupiedEntry<'_, T, S, A> {
2011 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2012 f&mut DebugStruct<'_, '_>.debug_struct("OccupiedEntry")
2013 .field(name:"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/// ```
2044pub struct VacantEntry<'a, T, S, A: Allocator + Clone = Global> {
2045 inner: map::VacantEntry<'a, T, (), S, A>,
2046}
2047
2048impl<T: fmt::Debug, S, A: Allocator + Clone> fmt::Debug for VacantEntry<'_, T, S, A> {
2049 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2050 f.debug_tuple(name:"VacantEntry").field(self.get()).finish()
2051 }
2052}
2053
2054impl<'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)]
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)]
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)]
2123 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
2131impl<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)]
2148 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)]
2177 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)]
2213 pub fn replace(self) -> T {
2214 self.inner.replace_key()
2215 }
2216}
2217
2218impl<'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)]
2231 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)]
2250 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)]
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)]
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)]
2291fn 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)]
2331mod test_set {
2332 use super::super::map::DefaultHashBuilder;
2333 use super::HashSet;
2334 use std::vec::Vec;
2335
2336 #[test]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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