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 pub fn insert(&mut self, value: T) -> bool {
889 self.base.insert(value)
890 }
891
892 /// Adds a value to the set, replacing the existing value, if any, that is equal to the given
893 /// one. Returns the replaced value.
894 ///
895 /// # Examples
896 ///
897 /// ```
898 /// use std::collections::HashSet;
899 ///
900 /// let mut set = HashSet::new();
901 /// set.insert(Vec::<i32>::new());
902 ///
903 /// assert_eq!(set.get(&[][..]).unwrap().capacity(), 0);
904 /// set.replace(Vec::with_capacity(10));
905 /// assert_eq!(set.get(&[][..]).unwrap().capacity(), 10);
906 /// ```
907 #[inline]
908 #[stable(feature = "set_recovery", since = "1.9.0")]
909 pub fn replace(&mut self, value: T) -> Option<T> {
910 self.base.replace(value)
911 }
912
913 /// Removes a value from the set. Returns whether the value was
914 /// present in the set.
915 ///
916 /// The value may be any borrowed form of the set's value type, but
917 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
918 /// the value type.
919 ///
920 /// # Examples
921 ///
922 /// ```
923 /// use std::collections::HashSet;
924 ///
925 /// let mut set = HashSet::new();
926 ///
927 /// set.insert(2);
928 /// assert_eq!(set.remove(&2), true);
929 /// assert_eq!(set.remove(&2), false);
930 /// ```
931 #[inline]
932 #[stable(feature = "rust1", since = "1.0.0")]
933 pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool
934 where
935 T: Borrow<Q>,
936 Q: Hash + Eq,
937 {
938 self.base.remove(value)
939 }
940
941 /// Removes and returns the value in the set, if any, that is equal to the given one.
942 ///
943 /// The value may be any borrowed form of the set's value type, but
944 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
945 /// the value type.
946 ///
947 /// # Examples
948 ///
949 /// ```
950 /// use std::collections::HashSet;
951 ///
952 /// let mut set = HashSet::from([1, 2, 3]);
953 /// assert_eq!(set.take(&2), Some(2));
954 /// assert_eq!(set.take(&2), None);
955 /// ```
956 #[inline]
957 #[stable(feature = "set_recovery", since = "1.9.0")]
958 pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T>
959 where
960 T: Borrow<Q>,
961 Q: Hash + Eq,
962 {
963 self.base.take(value)
964 }
965}
966
967#[stable(feature = "rust1", since = "1.0.0")]
968impl<T, S> Clone for HashSet<T, S>
969where
970 T: Clone,
971 S: Clone,
972{
973 #[inline]
974 fn clone(&self) -> Self {
975 Self { base: self.base.clone() }
976 }
977
978 #[inline]
979 fn clone_from(&mut self, other: &Self) {
980 self.base.clone_from(&other.base);
981 }
982}
983
984#[stable(feature = "rust1", since = "1.0.0")]
985impl<T, S> PartialEq for HashSet<T, S>
986where
987 T: Eq + Hash,
988 S: BuildHasher,
989{
990 fn eq(&self, other: &HashSet<T, S>) -> bool {
991 if self.len() != other.len() {
992 return false;
993 }
994
995 self.iter().all(|key: &T| other.contains(key))
996 }
997}
998
999#[stable(feature = "rust1", since = "1.0.0")]
1000impl<T, S> Eq for HashSet<T, S>
1001where
1002 T: Eq + Hash,
1003 S: BuildHasher,
1004{
1005}
1006
1007#[stable(feature = "rust1", since = "1.0.0")]
1008impl<T, S> fmt::Debug for HashSet<T, S>
1009where
1010 T: fmt::Debug,
1011{
1012 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1013 f.debug_set().entries(self.iter()).finish()
1014 }
1015}
1016
1017#[stable(feature = "rust1", since = "1.0.0")]
1018impl<T, S> FromIterator<T> for HashSet<T, S>
1019where
1020 T: Eq + Hash,
1021 S: BuildHasher + Default,
1022{
1023 #[inline]
1024 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> HashSet<T, S> {
1025 let mut set: HashSet = HashSet::with_hasher(Default::default());
1026 set.extend(iter);
1027 set
1028 }
1029}
1030
1031#[stable(feature = "std_collections_from_array", since = "1.56.0")]
1032// Note: as what is currently the most convenient built-in way to construct
1033// a HashSet, a simple usage of this function must not *require* the user
1034// to provide a type annotation in order to infer the third type parameter
1035// (the hasher parameter, conventionally "S").
1036// To that end, this impl is defined using RandomState as the concrete
1037// type of S, rather than being generic over `S: BuildHasher + Default`.
1038// It is expected that users who want to specify a hasher will manually use
1039// `with_capacity_and_hasher`.
1040// If type parameter defaults worked on impls, and if type parameter
1041// defaults could be mixed with const generics, then perhaps
1042// this could be generalized.
1043// See also the equivalent impl on HashMap.
1044impl<T, const N: usize> From<[T; N]> for HashSet<T, RandomState>
1045where
1046 T: Eq + Hash,
1047{
1048 /// # Examples
1049 ///
1050 /// ```
1051 /// use std::collections::HashSet;
1052 ///
1053 /// let set1 = HashSet::from([1, 2, 3, 4]);
1054 /// let set2: HashSet<_> = [1, 2, 3, 4].into();
1055 /// assert_eq!(set1, set2);
1056 /// ```
1057 fn from(arr: [T; N]) -> Self {
1058 Self::from_iter(arr)
1059 }
1060}
1061
1062#[stable(feature = "rust1", since = "1.0.0")]
1063impl<T, S> Extend<T> for HashSet<T, S>
1064where
1065 T: Eq + Hash,
1066 S: BuildHasher,
1067{
1068 #[inline]
1069 fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
1070 self.base.extend(iter);
1071 }
1072
1073 #[inline]
1074 fn extend_one(&mut self, item: T) {
1075 self.base.insert(item);
1076 }
1077
1078 #[inline]
1079 fn extend_reserve(&mut self, additional: usize) {
1080 self.base.extend_reserve(additional);
1081 }
1082}
1083
1084#[stable(feature = "hash_extend_copy", since = "1.4.0")]
1085impl<'a, T, S> Extend<&'a T> for HashSet<T, S>
1086where
1087 T: 'a + Eq + Hash + Copy,
1088 S: BuildHasher,
1089{
1090 #[inline]
1091 fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
1092 self.extend(iter:iter.into_iter().cloned());
1093 }
1094
1095 #[inline]
1096 fn extend_one(&mut self, &item: T: &'a T) {
1097 self.base.insert(item);
1098 }
1099
1100 #[inline]
1101 fn extend_reserve(&mut self, additional: usize) {
1102 Extend::<T>::extend_reserve(self, additional)
1103 }
1104}
1105
1106#[stable(feature = "rust1", since = "1.0.0")]
1107impl<T, S> Default for HashSet<T, S>
1108where
1109 S: Default,
1110{
1111 /// Creates an empty `HashSet<T, S>` with the `Default` value for the hasher.
1112 #[inline]
1113 fn default() -> HashSet<T, S> {
1114 HashSet { base: Default::default() }
1115 }
1116}
1117
1118#[stable(feature = "rust1", since = "1.0.0")]
1119impl<T, S> BitOr<&HashSet<T, S>> for &HashSet<T, S>
1120where
1121 T: Eq + Hash + Clone,
1122 S: BuildHasher + Default,
1123{
1124 type Output = HashSet<T, S>;
1125
1126 /// Returns the union of `self` and `rhs` as a new `HashSet<T, S>`.
1127 ///
1128 /// # Examples
1129 ///
1130 /// ```
1131 /// use std::collections::HashSet;
1132 ///
1133 /// let a = HashSet::from([1, 2, 3]);
1134 /// let b = HashSet::from([3, 4, 5]);
1135 ///
1136 /// let set = &a | &b;
1137 ///
1138 /// let mut i = 0;
1139 /// let expected = [1, 2, 3, 4, 5];
1140 /// for x in &set {
1141 /// assert!(expected.contains(x));
1142 /// i += 1;
1143 /// }
1144 /// assert_eq!(i, expected.len());
1145 /// ```
1146 fn bitor(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
1147 self.union(rhs).cloned().collect()
1148 }
1149}
1150
1151#[stable(feature = "rust1", since = "1.0.0")]
1152impl<T, S> BitAnd<&HashSet<T, S>> for &HashSet<T, S>
1153where
1154 T: Eq + Hash + Clone,
1155 S: BuildHasher + Default,
1156{
1157 type Output = HashSet<T, S>;
1158
1159 /// Returns the intersection of `self` and `rhs` as a new `HashSet<T, S>`.
1160 ///
1161 /// # Examples
1162 ///
1163 /// ```
1164 /// use std::collections::HashSet;
1165 ///
1166 /// let a = HashSet::from([1, 2, 3]);
1167 /// let b = HashSet::from([2, 3, 4]);
1168 ///
1169 /// let set = &a & &b;
1170 ///
1171 /// let mut i = 0;
1172 /// let expected = [2, 3];
1173 /// for x in &set {
1174 /// assert!(expected.contains(x));
1175 /// i += 1;
1176 /// }
1177 /// assert_eq!(i, expected.len());
1178 /// ```
1179 fn bitand(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
1180 self.intersection(rhs).cloned().collect()
1181 }
1182}
1183
1184#[stable(feature = "rust1", since = "1.0.0")]
1185impl<T, S> BitXor<&HashSet<T, S>> for &HashSet<T, S>
1186where
1187 T: Eq + Hash + Clone,
1188 S: BuildHasher + Default,
1189{
1190 type Output = HashSet<T, S>;
1191
1192 /// Returns the symmetric difference of `self` and `rhs` as a new `HashSet<T, S>`.
1193 ///
1194 /// # Examples
1195 ///
1196 /// ```
1197 /// use std::collections::HashSet;
1198 ///
1199 /// let a = HashSet::from([1, 2, 3]);
1200 /// let b = HashSet::from([3, 4, 5]);
1201 ///
1202 /// let set = &a ^ &b;
1203 ///
1204 /// let mut i = 0;
1205 /// let expected = [1, 2, 4, 5];
1206 /// for x in &set {
1207 /// assert!(expected.contains(x));
1208 /// i += 1;
1209 /// }
1210 /// assert_eq!(i, expected.len());
1211 /// ```
1212 fn bitxor(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
1213 self.symmetric_difference(rhs).cloned().collect()
1214 }
1215}
1216
1217#[stable(feature = "rust1", since = "1.0.0")]
1218impl<T, S> Sub<&HashSet<T, S>> for &HashSet<T, S>
1219where
1220 T: Eq + Hash + Clone,
1221 S: BuildHasher + Default,
1222{
1223 type Output = HashSet<T, S>;
1224
1225 /// Returns the difference of `self` and `rhs` as a new `HashSet<T, S>`.
1226 ///
1227 /// # Examples
1228 ///
1229 /// ```
1230 /// use std::collections::HashSet;
1231 ///
1232 /// let a = HashSet::from([1, 2, 3]);
1233 /// let b = HashSet::from([3, 4, 5]);
1234 ///
1235 /// let set = &a - &b;
1236 ///
1237 /// let mut i = 0;
1238 /// let expected = [1, 2];
1239 /// for x in &set {
1240 /// assert!(expected.contains(x));
1241 /// i += 1;
1242 /// }
1243 /// assert_eq!(i, expected.len());
1244 /// ```
1245 fn sub(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
1246 self.difference(rhs).cloned().collect()
1247 }
1248}
1249
1250/// An iterator over the items of a `HashSet`.
1251///
1252/// This `struct` is created by the [`iter`] method on [`HashSet`].
1253/// See its documentation for more.
1254///
1255/// [`iter`]: HashSet::iter
1256///
1257/// # Examples
1258///
1259/// ```
1260/// use std::collections::HashSet;
1261///
1262/// let a = HashSet::from([1, 2, 3]);
1263///
1264/// let mut iter = a.iter();
1265/// ```
1266#[stable(feature = "rust1", since = "1.0.0")]
1267pub struct Iter<'a, K: 'a> {
1268 base: base::Iter<'a, K>,
1269}
1270
1271/// An owning iterator over the items of a `HashSet`.
1272///
1273/// This `struct` is created by the [`into_iter`] method on [`HashSet`]
1274/// (provided by the [`IntoIterator`] trait). See its documentation for more.
1275///
1276/// [`into_iter`]: IntoIterator::into_iter
1277///
1278/// # Examples
1279///
1280/// ```
1281/// use std::collections::HashSet;
1282///
1283/// let a = HashSet::from([1, 2, 3]);
1284///
1285/// let mut iter = a.into_iter();
1286/// ```
1287#[stable(feature = "rust1", since = "1.0.0")]
1288pub struct IntoIter<K> {
1289 base: base::IntoIter<K>,
1290}
1291
1292/// A draining iterator over the items of a `HashSet`.
1293///
1294/// This `struct` is created by the [`drain`] method on [`HashSet`].
1295/// See its documentation for more.
1296///
1297/// [`drain`]: HashSet::drain
1298///
1299/// # Examples
1300///
1301/// ```
1302/// use std::collections::HashSet;
1303///
1304/// let mut a = HashSet::from([1, 2, 3]);
1305///
1306/// let mut drain = a.drain();
1307/// ```
1308#[stable(feature = "rust1", since = "1.0.0")]
1309pub struct Drain<'a, K: 'a> {
1310 base: base::Drain<'a, K>,
1311}
1312
1313/// A draining, filtering iterator over the items of a `HashSet`.
1314///
1315/// This `struct` is created by the [`extract_if`] method on [`HashSet`].
1316///
1317/// [`extract_if`]: HashSet::extract_if
1318///
1319/// # Examples
1320///
1321/// ```
1322/// #![feature(hash_extract_if)]
1323///
1324/// use std::collections::HashSet;
1325///
1326/// let mut a = HashSet::from([1, 2, 3]);
1327///
1328/// let mut extract_ifed = a.extract_if(|v| v % 2 == 0);
1329/// ```
1330#[unstable(feature = "hash_extract_if", issue = "59618")]
1331pub struct ExtractIf<'a, K, F>
1332where
1333 F: FnMut(&K) -> bool,
1334{
1335 base: base::ExtractIf<'a, K, F>,
1336}
1337
1338/// A lazy iterator producing elements in the intersection of `HashSet`s.
1339///
1340/// This `struct` is created by the [`intersection`] method on [`HashSet`].
1341/// See its documentation for more.
1342///
1343/// [`intersection`]: HashSet::intersection
1344///
1345/// # Examples
1346///
1347/// ```
1348/// use std::collections::HashSet;
1349///
1350/// let a = HashSet::from([1, 2, 3]);
1351/// let b = HashSet::from([4, 2, 3, 4]);
1352///
1353/// let mut intersection = a.intersection(&b);
1354/// ```
1355#[must_use = "this returns the intersection as an iterator, \
1356 without modifying either input set"]
1357#[stable(feature = "rust1", since = "1.0.0")]
1358pub struct Intersection<'a, T: 'a, S: 'a> {
1359 // iterator of the first set
1360 iter: Iter<'a, T>,
1361 // the second set
1362 other: &'a HashSet<T, S>,
1363}
1364
1365/// A lazy iterator producing elements in the difference of `HashSet`s.
1366///
1367/// This `struct` is created by the [`difference`] method on [`HashSet`].
1368/// See its documentation for more.
1369///
1370/// [`difference`]: HashSet::difference
1371///
1372/// # Examples
1373///
1374/// ```
1375/// use std::collections::HashSet;
1376///
1377/// let a = HashSet::from([1, 2, 3]);
1378/// let b = HashSet::from([4, 2, 3, 4]);
1379///
1380/// let mut difference = a.difference(&b);
1381/// ```
1382#[must_use = "this returns the difference as an iterator, \
1383 without modifying either input set"]
1384#[stable(feature = "rust1", since = "1.0.0")]
1385pub struct Difference<'a, T: 'a, S: 'a> {
1386 // iterator of the first set
1387 iter: Iter<'a, T>,
1388 // the second set
1389 other: &'a HashSet<T, S>,
1390}
1391
1392/// A lazy iterator producing elements in the symmetric difference of `HashSet`s.
1393///
1394/// This `struct` is created by the [`symmetric_difference`] method on
1395/// [`HashSet`]. See its documentation for more.
1396///
1397/// [`symmetric_difference`]: HashSet::symmetric_difference
1398///
1399/// # Examples
1400///
1401/// ```
1402/// use std::collections::HashSet;
1403///
1404/// let a = HashSet::from([1, 2, 3]);
1405/// let b = HashSet::from([4, 2, 3, 4]);
1406///
1407/// let mut intersection = a.symmetric_difference(&b);
1408/// ```
1409#[must_use = "this returns the difference as an iterator, \
1410 without modifying either input set"]
1411#[stable(feature = "rust1", since = "1.0.0")]
1412pub struct SymmetricDifference<'a, T: 'a, S: 'a> {
1413 iter: Chain<Difference<'a, T, S>, Difference<'a, T, S>>,
1414}
1415
1416/// A lazy iterator producing elements in the union of `HashSet`s.
1417///
1418/// This `struct` is created by the [`union`] method on [`HashSet`].
1419/// See its documentation for more.
1420///
1421/// [`union`]: HashSet::union
1422///
1423/// # Examples
1424///
1425/// ```
1426/// use std::collections::HashSet;
1427///
1428/// let a = HashSet::from([1, 2, 3]);
1429/// let b = HashSet::from([4, 2, 3, 4]);
1430///
1431/// let mut union_iter = a.union(&b);
1432/// ```
1433#[must_use = "this returns the union as an iterator, \
1434 without modifying either input set"]
1435#[stable(feature = "rust1", since = "1.0.0")]
1436pub struct Union<'a, T: 'a, S: 'a> {
1437 iter: Chain<Iter<'a, T>, Difference<'a, T, S>>,
1438}
1439
1440#[stable(feature = "rust1", since = "1.0.0")]
1441impl<'a, T, S> IntoIterator for &'a HashSet<T, S> {
1442 type Item = &'a T;
1443 type IntoIter = Iter<'a, T>;
1444
1445 #[inline]
1446 #[rustc_lint_query_instability]
1447 fn into_iter(self) -> Iter<'a, T> {
1448 self.iter()
1449 }
1450}
1451
1452#[stable(feature = "rust1", since = "1.0.0")]
1453impl<T, S> IntoIterator for HashSet<T, S> {
1454 type Item = T;
1455 type IntoIter = IntoIter<T>;
1456
1457 /// Creates a consuming iterator, that is, one that moves each value out
1458 /// of the set in arbitrary order. The set cannot be used after calling
1459 /// this.
1460 ///
1461 /// # Examples
1462 ///
1463 /// ```
1464 /// use std::collections::HashSet;
1465 /// let mut set = HashSet::new();
1466 /// set.insert("a".to_string());
1467 /// set.insert("b".to_string());
1468 ///
1469 /// // Not possible to collect to a Vec<String> with a regular `.iter()`.
1470 /// let v: Vec<String> = set.into_iter().collect();
1471 ///
1472 /// // Will print in an arbitrary order.
1473 /// for x in &v {
1474 /// println!("{x}");
1475 /// }
1476 /// ```
1477 #[inline]
1478 #[rustc_lint_query_instability]
1479 fn into_iter(self) -> IntoIter<T> {
1480 IntoIter { base: self.base.into_iter() }
1481 }
1482}
1483
1484#[stable(feature = "rust1", since = "1.0.0")]
1485impl<K> Clone for Iter<'_, K> {
1486 #[inline]
1487 fn clone(&self) -> Self {
1488 Iter { base: self.base.clone() }
1489 }
1490}
1491#[stable(feature = "rust1", since = "1.0.0")]
1492impl<'a, K> Iterator for Iter<'a, K> {
1493 type Item = &'a K;
1494
1495 #[inline]
1496 fn next(&mut self) -> Option<&'a K> {
1497 self.base.next()
1498 }
1499 #[inline]
1500 fn size_hint(&self) -> (usize, Option<usize>) {
1501 self.base.size_hint()
1502 }
1503 #[inline]
1504 fn count(self) -> usize {
1505 self.base.len()
1506 }
1507 #[inline]
1508 fn fold<B, F>(self, init: B, f: F) -> B
1509 where
1510 Self: Sized,
1511 F: FnMut(B, Self::Item) -> B,
1512 {
1513 self.base.fold(init, f)
1514 }
1515}
1516#[stable(feature = "rust1", since = "1.0.0")]
1517impl<K> ExactSizeIterator for Iter<'_, K> {
1518 #[inline]
1519 fn len(&self) -> usize {
1520 self.base.len()
1521 }
1522}
1523#[stable(feature = "fused", since = "1.26.0")]
1524impl<K> FusedIterator for Iter<'_, K> {}
1525
1526#[stable(feature = "std_debug", since = "1.16.0")]
1527impl<K: fmt::Debug> fmt::Debug for Iter<'_, K> {
1528 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1529 f.debug_list().entries(self.clone()).finish()
1530 }
1531}
1532
1533#[stable(feature = "rust1", since = "1.0.0")]
1534impl<K> Iterator for IntoIter<K> {
1535 type Item = K;
1536
1537 #[inline]
1538 fn next(&mut self) -> Option<K> {
1539 self.base.next()
1540 }
1541 #[inline]
1542 fn size_hint(&self) -> (usize, Option<usize>) {
1543 self.base.size_hint()
1544 }
1545 #[inline]
1546 fn count(self) -> usize {
1547 self.base.len()
1548 }
1549 #[inline]
1550 fn fold<B, F>(self, init: B, f: F) -> B
1551 where
1552 Self: Sized,
1553 F: FnMut(B, Self::Item) -> B,
1554 {
1555 self.base.fold(init, f)
1556 }
1557}
1558#[stable(feature = "rust1", since = "1.0.0")]
1559impl<K> ExactSizeIterator for IntoIter<K> {
1560 #[inline]
1561 fn len(&self) -> usize {
1562 self.base.len()
1563 }
1564}
1565#[stable(feature = "fused", since = "1.26.0")]
1566impl<K> FusedIterator for IntoIter<K> {}
1567
1568#[stable(feature = "std_debug", since = "1.16.0")]
1569impl<K: fmt::Debug> fmt::Debug for IntoIter<K> {
1570 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1571 fmt::Debug::fmt(&self.base, f)
1572 }
1573}
1574
1575#[stable(feature = "rust1", since = "1.0.0")]
1576impl<'a, K> Iterator for Drain<'a, K> {
1577 type Item = K;
1578
1579 #[inline]
1580 fn next(&mut self) -> Option<K> {
1581 self.base.next()
1582 }
1583 #[inline]
1584 fn size_hint(&self) -> (usize, Option<usize>) {
1585 self.base.size_hint()
1586 }
1587 #[inline]
1588 fn fold<B, F>(self, init: B, f: F) -> B
1589 where
1590 Self: Sized,
1591 F: FnMut(B, Self::Item) -> B,
1592 {
1593 self.base.fold(init, f)
1594 }
1595}
1596#[stable(feature = "rust1", since = "1.0.0")]
1597impl<K> ExactSizeIterator for Drain<'_, K> {
1598 #[inline]
1599 fn len(&self) -> usize {
1600 self.base.len()
1601 }
1602}
1603#[stable(feature = "fused", since = "1.26.0")]
1604impl<K> FusedIterator for Drain<'_, K> {}
1605
1606#[stable(feature = "std_debug", since = "1.16.0")]
1607impl<K: fmt::Debug> fmt::Debug for Drain<'_, K> {
1608 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1609 fmt::Debug::fmt(&self.base, f)
1610 }
1611}
1612
1613#[unstable(feature = "hash_extract_if", issue = "59618")]
1614impl<K, F> Iterator for ExtractIf<'_, K, F>
1615where
1616 F: FnMut(&K) -> bool,
1617{
1618 type Item = K;
1619
1620 #[inline]
1621 fn next(&mut self) -> Option<K> {
1622 self.base.next()
1623 }
1624 #[inline]
1625 fn size_hint(&self) -> (usize, Option<usize>) {
1626 self.base.size_hint()
1627 }
1628}
1629
1630#[unstable(feature = "hash_extract_if", issue = "59618")]
1631impl<K, F> FusedIterator for ExtractIf<'_, K, F> where F: FnMut(&K) -> bool {}
1632
1633#[unstable(feature = "hash_extract_if", issue = "59618")]
1634impl<'a, K, F> fmt::Debug for ExtractIf<'a, K, F>
1635where
1636 F: FnMut(&K) -> bool,
1637{
1638 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1639 f.debug_struct(name:"ExtractIf").finish_non_exhaustive()
1640 }
1641}
1642
1643#[stable(feature = "rust1", since = "1.0.0")]
1644impl<T, S> Clone for Intersection<'_, T, S> {
1645 #[inline]
1646 fn clone(&self) -> Self {
1647 Intersection { iter: self.iter.clone(), ..*self }
1648 }
1649}
1650
1651#[stable(feature = "rust1", since = "1.0.0")]
1652impl<'a, T, S> Iterator for Intersection<'a, T, S>
1653where
1654 T: Eq + Hash,
1655 S: BuildHasher,
1656{
1657 type Item = &'a T;
1658
1659 #[inline]
1660 fn next(&mut self) -> Option<&'a T> {
1661 loop {
1662 let elt = self.iter.next()?;
1663 if self.other.contains(elt) {
1664 return Some(elt);
1665 }
1666 }
1667 }
1668
1669 #[inline]
1670 fn size_hint(&self) -> (usize, Option<usize>) {
1671 let (_, upper) = self.iter.size_hint();
1672 (0, upper)
1673 }
1674
1675 #[inline]
1676 fn fold<B, F>(self, init: B, mut f: F) -> B
1677 where
1678 Self: Sized,
1679 F: FnMut(B, Self::Item) -> B,
1680 {
1681 self.iter.fold(init, |acc, elt| if self.other.contains(elt) { f(acc, elt) } else { acc })
1682 }
1683}
1684
1685#[stable(feature = "std_debug", since = "1.16.0")]
1686impl<T, S> fmt::Debug for Intersection<'_, T, S>
1687where
1688 T: fmt::Debug + Eq + Hash,
1689 S: BuildHasher,
1690{
1691 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1692 f.debug_list().entries(self.clone()).finish()
1693 }
1694}
1695
1696#[stable(feature = "fused", since = "1.26.0")]
1697impl<T, S> FusedIterator for Intersection<'_, T, S>
1698where
1699 T: Eq + Hash,
1700 S: BuildHasher,
1701{
1702}
1703
1704#[stable(feature = "rust1", since = "1.0.0")]
1705impl<T, S> Clone for Difference<'_, T, S> {
1706 #[inline]
1707 fn clone(&self) -> Self {
1708 Difference { iter: self.iter.clone(), ..*self }
1709 }
1710}
1711
1712#[stable(feature = "rust1", since = "1.0.0")]
1713impl<'a, T, S> Iterator for Difference<'a, T, S>
1714where
1715 T: Eq + Hash,
1716 S: BuildHasher,
1717{
1718 type Item = &'a T;
1719
1720 #[inline]
1721 fn next(&mut self) -> Option<&'a T> {
1722 loop {
1723 let elt = self.iter.next()?;
1724 if !self.other.contains(elt) {
1725 return Some(elt);
1726 }
1727 }
1728 }
1729
1730 #[inline]
1731 fn size_hint(&self) -> (usize, Option<usize>) {
1732 let (_, upper) = self.iter.size_hint();
1733 (0, upper)
1734 }
1735
1736 #[inline]
1737 fn fold<B, F>(self, init: B, mut f: F) -> B
1738 where
1739 Self: Sized,
1740 F: FnMut(B, Self::Item) -> B,
1741 {
1742 self.iter.fold(init, |acc, elt| if self.other.contains(elt) { acc } else { f(acc, elt) })
1743 }
1744}
1745
1746#[stable(feature = "fused", since = "1.26.0")]
1747impl<T, S> FusedIterator for Difference<'_, T, S>
1748where
1749 T: Eq + Hash,
1750 S: BuildHasher,
1751{
1752}
1753
1754#[stable(feature = "std_debug", since = "1.16.0")]
1755impl<T, S> fmt::Debug for Difference<'_, T, S>
1756where
1757 T: fmt::Debug + Eq + Hash,
1758 S: BuildHasher,
1759{
1760 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1761 f.debug_list().entries(self.clone()).finish()
1762 }
1763}
1764
1765#[stable(feature = "rust1", since = "1.0.0")]
1766impl<T, S> Clone for SymmetricDifference<'_, T, S> {
1767 #[inline]
1768 fn clone(&self) -> Self {
1769 SymmetricDifference { iter: self.iter.clone() }
1770 }
1771}
1772
1773#[stable(feature = "rust1", since = "1.0.0")]
1774impl<'a, T, S> Iterator for SymmetricDifference<'a, T, S>
1775where
1776 T: Eq + Hash,
1777 S: BuildHasher,
1778{
1779 type Item = &'a T;
1780
1781 #[inline]
1782 fn next(&mut self) -> Option<&'a T> {
1783 self.iter.next()
1784 }
1785 #[inline]
1786 fn size_hint(&self) -> (usize, Option<usize>) {
1787 self.iter.size_hint()
1788 }
1789 #[inline]
1790 fn fold<B, F>(self, init: B, f: F) -> B
1791 where
1792 Self: Sized,
1793 F: FnMut(B, Self::Item) -> B,
1794 {
1795 self.iter.fold(init, f)
1796 }
1797}
1798
1799#[stable(feature = "fused", since = "1.26.0")]
1800impl<T, S> FusedIterator for SymmetricDifference<'_, T, S>
1801where
1802 T: Eq + Hash,
1803 S: BuildHasher,
1804{
1805}
1806
1807#[stable(feature = "std_debug", since = "1.16.0")]
1808impl<T, S> fmt::Debug for SymmetricDifference<'_, T, S>
1809where
1810 T: fmt::Debug + Eq + Hash,
1811 S: BuildHasher,
1812{
1813 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1814 f.debug_list().entries(self.clone()).finish()
1815 }
1816}
1817
1818#[stable(feature = "rust1", since = "1.0.0")]
1819impl<T, S> Clone for Union<'_, T, S> {
1820 #[inline]
1821 fn clone(&self) -> Self {
1822 Union { iter: self.iter.clone() }
1823 }
1824}
1825
1826#[stable(feature = "fused", since = "1.26.0")]
1827impl<T, S> FusedIterator for Union<'_, T, S>
1828where
1829 T: Eq + Hash,
1830 S: BuildHasher,
1831{
1832}
1833
1834#[stable(feature = "std_debug", since = "1.16.0")]
1835impl<T, S> fmt::Debug for Union<'_, T, S>
1836where
1837 T: fmt::Debug + Eq + Hash,
1838 S: BuildHasher,
1839{
1840 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1841 f.debug_list().entries(self.clone()).finish()
1842 }
1843}
1844
1845#[stable(feature = "rust1", since = "1.0.0")]
1846impl<'a, T, S> Iterator for Union<'a, T, S>
1847where
1848 T: Eq + Hash,
1849 S: BuildHasher,
1850{
1851 type Item = &'a T;
1852
1853 #[inline]
1854 fn next(&mut self) -> Option<&'a T> {
1855 self.iter.next()
1856 }
1857 #[inline]
1858 fn size_hint(&self) -> (usize, Option<usize>) {
1859 self.iter.size_hint()
1860 }
1861 #[inline]
1862 fn count(self) -> usize {
1863 self.iter.count()
1864 }
1865 #[inline]
1866 fn fold<B, F>(self, init: B, f: F) -> B
1867 where
1868 Self: Sized,
1869 F: FnMut(B, Self::Item) -> B,
1870 {
1871 self.iter.fold(init, f)
1872 }
1873}
1874
1875#[allow(dead_code)]
1876fn assert_covariance() {
1877 fn set<'new>(v: HashSet<&'static str>) -> HashSet<&'new str> {
1878 v
1879 }
1880 fn iter<'a, 'new>(v: Iter<'a, &'static str>) -> Iter<'a, &'new str> {
1881 v
1882 }
1883 fn into_iter<'new>(v: IntoIter<&'static str>) -> IntoIter<&'new str> {
1884 v
1885 }
1886 fn difference<'a, 'new>(
1887 v: Difference<'a, &'static str, RandomState>,
1888 ) -> Difference<'a, &'new str, RandomState> {
1889 v
1890 }
1891 fn symmetric_difference<'a, 'new>(
1892 v: SymmetricDifference<'a, &'static str, RandomState>,
1893 ) -> SymmetricDifference<'a, &'new str, RandomState> {
1894 v
1895 }
1896 fn intersection<'a, 'new>(
1897 v: Intersection<'a, &'static str, RandomState>,
1898 ) -> Intersection<'a, &'new str, RandomState> {
1899 v
1900 }
1901 fn union<'a, 'new>(
1902 v: Union<'a, &'static str, RandomState>,
1903 ) -> Union<'a, &'new str, RandomState> {
1904 v
1905 }
1906 fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
1907 d
1908 }
1909}
1910