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: OccupiedEntry<'_, K, V>) => Entry::Occupied(OccupiedEntry { base }),
1002 base::Entry::Vacant(base: VacantEntry<'_, K, V>) => 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: &T| 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 = 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: T: &'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(name:"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: &VacantEntry<'_, T, S>) => f.debug_tuple(name:"Entry").field(v).finish(),
2023 Entry::Occupied(ref o: &OccupiedEntry<'_, T, S>) => f.debug_tuple(name:"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(name:"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(name:"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}
2376