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