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