std/collections/hash/
set.rs

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