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