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