4 use hashbrown
::hash_set
as base
;
6 use crate::borrow
::Borrow
;
7 use crate::collections
::TryReserveError
;
9 use crate::hash
::{BuildHasher, Hash}
;
10 use crate::iter
::{Chain, FusedIterator}
;
11 use crate::ops
::{BitAnd, BitOr, BitXor, Sub}
;
13 use super::map
::{map_try_reserve_error, RandomState}
;
15 // Future Optimization (FIXME!)
16 // ============================
18 // Iteration over zero sized values is a noop. There is no need
19 // for `bucket.val` in the case of HashSet. I suppose we would need HKT
20 // to get rid of it properly.
22 /// A [hash set] implemented as a `HashMap` where the value is `()`.
24 /// As with the [`HashMap`] type, a `HashSet` requires that the elements
25 /// implement the [`Eq`] and [`Hash`] traits. This can frequently be achieved by
26 /// using `#[derive(PartialEq, Eq, Hash)]`. If you implement these yourself,
27 /// it is important that the following property holds:
30 /// k1 == k2 -> hash(k1) == hash(k2)
33 /// In other words, if two keys are equal, their hashes must be equal.
36 /// It is a logic error for a key to be modified in such a way that the key's
37 /// hash, as determined by the [`Hash`] trait, or its equality, as determined by
38 /// the [`Eq`] trait, changes while it is in the map. This is normally only
39 /// possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code.
40 /// The behavior resulting from such a logic error is not specified, but will
41 /// be encapsulated to the `HashSet` that observed the logic error and not
42 /// result in undefined behavior. This could include panics, incorrect results,
43 /// aborts, memory leaks, and non-termination.
48 /// use std::collections::HashSet;
49 /// // Type inference lets us omit an explicit type signature (which
50 /// // would be `HashSet<String>` in this example).
51 /// let mut books = HashSet::new();
53 /// // Add some books.
54 /// books.insert("A Dance With Dragons".to_string());
55 /// books.insert("To Kill a Mockingbird".to_string());
56 /// books.insert("The Odyssey".to_string());
57 /// books.insert("The Great Gatsby".to_string());
59 /// // Check for a specific one.
60 /// if !books.contains("The Winds of Winter") {
61 /// println!("We have {} books, but The Winds of Winter ain't one.",
66 /// books.remove("The Odyssey");
68 /// // Iterate over everything.
69 /// for book in &books {
70 /// println!("{book}");
74 /// The easiest way to use `HashSet` with a custom type is to derive
75 /// [`Eq`] and [`Hash`]. We must also derive [`PartialEq`], this will in the
76 /// future be implied by [`Eq`].
79 /// use std::collections::HashSet;
80 /// #[derive(Hash, Eq, PartialEq, Debug)]
86 /// let mut vikings = HashSet::new();
88 /// vikings.insert(Viking { name: "Einar".to_string(), power: 9 });
89 /// vikings.insert(Viking { name: "Einar".to_string(), power: 9 });
90 /// vikings.insert(Viking { name: "Olaf".to_string(), power: 4 });
91 /// vikings.insert(Viking { name: "Harald".to_string(), power: 8 });
93 /// // Use derived implementation to print the vikings.
94 /// for x in &vikings {
95 /// println!("{x:?}");
99 /// A `HashSet` with a known list of items can be initialized from an array:
102 /// use std::collections::HashSet;
104 /// let viking_names = HashSet::from(["Einar", "Olaf", "Harald"]);
107 /// [hash set]: crate::collections#use-the-set-variant-of-any-of-these-maps-when
108 /// [`HashMap`]: crate::collections::HashMap
109 /// [`RefCell`]: crate::cell::RefCell
110 /// [`Cell`]: crate::cell::Cell
111 #[cfg_attr(not(test), rustc_diagnostic_item = "HashSet")]
112 #[stable(feature = "rust1", since = "1.0.0")]
113 pub struct HashSet
<T
, S
= RandomState
> {
114 base
: base
::HashSet
<T
, S
>,
117 impl<T
> HashSet
<T
, RandomState
> {
118 /// Creates an empty `HashSet`.
120 /// The hash set is initially created with a capacity of 0, so it will not allocate until it
121 /// is first inserted into.
126 /// use std::collections::HashSet;
127 /// let set: HashSet<i32> = HashSet::new();
131 #[stable(feature = "rust1", since = "1.0.0")]
132 pub fn new() -> HashSet
<T
, RandomState
> {
136 /// Creates an empty `HashSet` with at least the specified capacity.
138 /// The hash set will be able to hold at least `capacity` elements without
139 /// reallocating. This method is allowed to allocate for more elements than
140 /// `capacity`. If `capacity` is 0, the hash set will not allocate.
145 /// use std::collections::HashSet;
146 /// let set: HashSet<i32> = HashSet::with_capacity(10);
147 /// assert!(set.capacity() >= 10);
151 #[stable(feature = "rust1", since = "1.0.0")]
152 pub fn with_capacity(capacity
: usize) -> HashSet
<T
, RandomState
> {
153 HashSet { base: base::HashSet::with_capacity_and_hasher(capacity, Default::default()) }
157 impl<T
, S
> HashSet
<T
, S
> {
158 /// Returns the number of elements the set can hold without reallocating.
163 /// use std::collections::HashSet;
164 /// let set: HashSet<i32> = HashSet::with_capacity(100);
165 /// assert!(set.capacity() >= 100);
168 #[stable(feature = "rust1", since = "1.0.0")]
169 pub fn capacity(&self) -> usize {
173 /// An iterator visiting all elements in arbitrary order.
174 /// The iterator element type is `&'a T`.
179 /// use std::collections::HashSet;
180 /// let mut set = HashSet::new();
184 /// // Will print in an arbitrary order.
185 /// for x in set.iter() {
192 /// In the current implementation, iterating over set takes O(capacity) time
193 /// instead of O(len) because it internally visits empty buckets too.
195 #[rustc_lint_query_instability]
196 #[stable(feature = "rust1", since = "1.0.0")]
197 pub fn iter(&self) -> Iter
<'_
, T
> {
198 Iter { base: self.base.iter() }
201 /// Returns the number of elements in the set.
206 /// use std::collections::HashSet;
208 /// let mut v = HashSet::new();
209 /// assert_eq!(v.len(), 0);
211 /// assert_eq!(v.len(), 1);
214 #[stable(feature = "rust1", since = "1.0.0")]
215 pub fn len(&self) -> usize {
219 /// Returns `true` if the set contains no elements.
224 /// use std::collections::HashSet;
226 /// let mut v = HashSet::new();
227 /// assert!(v.is_empty());
229 /// assert!(!v.is_empty());
232 #[stable(feature = "rust1", since = "1.0.0")]
233 pub fn is_empty(&self) -> bool
{
237 /// Clears the set, returning all elements as an iterator. Keeps the
238 /// allocated memory for reuse.
240 /// If the returned iterator is dropped before being fully consumed, it
241 /// drops the remaining elements. The returned iterator keeps a mutable
242 /// borrow on the set to optimize its implementation.
247 /// use std::collections::HashSet;
249 /// let mut set = HashSet::from([1, 2, 3]);
250 /// assert!(!set.is_empty());
252 /// // print 1, 2, 3 in an arbitrary order
253 /// for i in set.drain() {
257 /// assert!(set.is_empty());
260 #[rustc_lint_query_instability]
261 #[stable(feature = "drain", since = "1.6.0")]
262 pub fn drain(&mut self) -> Drain
<'_
, T
> {
263 Drain { base: self.base.drain() }
266 /// Creates an iterator which uses a closure to determine if a value should be removed.
268 /// If the closure returns true, then the value is removed and yielded.
269 /// If the closure returns false, the value will remain in the list and will not be yielded
272 /// If the iterator is only partially consumed or not consumed at all, each of the remaining
273 /// values will still be subjected to the closure and removed and dropped if it returns true.
275 /// It is unspecified how many more values will be subjected to the closure
276 /// if a panic occurs in the closure, or if a panic occurs while dropping a value, or if the
277 /// `DrainFilter` itself is leaked.
281 /// Splitting a set into even and odd values, reusing the original set:
284 /// #![feature(hash_drain_filter)]
285 /// use std::collections::HashSet;
287 /// let mut set: HashSet<i32> = (0..8).collect();
288 /// let drained: HashSet<i32> = set.drain_filter(|v| v % 2 == 0).collect();
290 /// let mut evens = drained.into_iter().collect::<Vec<_>>();
291 /// let mut odds = set.into_iter().collect::<Vec<_>>();
295 /// assert_eq!(evens, vec![0, 2, 4, 6]);
296 /// assert_eq!(odds, vec![1, 3, 5, 7]);
299 #[rustc_lint_query_instability]
300 #[unstable(feature = "hash_drain_filter", issue = "59618")]
301 pub fn drain_filter
<F
>(&mut self, pred
: F
) -> DrainFilter
<'_
, T
, F
>
303 F
: FnMut(&T
) -> bool
,
305 DrainFilter { base: self.base.drain_filter(pred) }
308 /// Retains only the elements specified by the predicate.
310 /// In other words, remove all elements `e` for which `f(&e)` returns `false`.
311 /// The elements are visited in unsorted (and unspecified) order.
316 /// use std::collections::HashSet;
318 /// let mut set = HashSet::from([1, 2, 3, 4, 5, 6]);
319 /// set.retain(|&k| k % 2 == 0);
320 /// assert_eq!(set.len(), 3);
325 /// In the current implementation, this operation takes O(capacity) time
326 /// instead of O(len) because it internally visits empty buckets too.
327 #[rustc_lint_query_instability]
328 #[stable(feature = "retain_hash_collection", since = "1.18.0")]
329 pub fn retain
<F
>(&mut self, f
: F
)
331 F
: FnMut(&T
) -> bool
,
336 /// Clears the set, removing all values.
341 /// use std::collections::HashSet;
343 /// let mut v = HashSet::new();
346 /// assert!(v.is_empty());
349 #[stable(feature = "rust1", since = "1.0.0")]
350 pub fn clear(&mut self) {
354 /// Creates a new empty hash set which will use the given hasher to hash
357 /// The hash set is also created with the default initial capacity.
359 /// Warning: `hasher` is normally randomly generated, and
360 /// is designed to allow `HashSet`s to be resistant to attacks that
361 /// cause many collisions and very poor performance. Setting it
362 /// manually using this function can expose a DoS attack vector.
364 /// The `hash_builder` passed should implement the [`BuildHasher`] trait for
365 /// the HashMap to be useful, see its documentation for details.
370 /// use std::collections::HashSet;
371 /// use std::collections::hash_map::RandomState;
373 /// let s = RandomState::new();
374 /// let mut set = HashSet::with_hasher(s);
378 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
379 #[rustc_const_unstable(feature = "const_collections_with_hasher", issue = "102575")]
380 pub const fn with_hasher(hasher
: S
) -> HashSet
<T
, S
> {
381 HashSet { base: base::HashSet::with_hasher(hasher) }
384 /// Creates an empty `HashSet` with at least the specified capacity, using
385 /// `hasher` to hash the keys.
387 /// The hash set will be able to hold at least `capacity` elements without
388 /// reallocating. This method is allowed to allocate for more elements than
389 /// `capacity`. If `capacity` is 0, the hash set will not allocate.
391 /// Warning: `hasher` is normally randomly generated, and
392 /// is designed to allow `HashSet`s to be resistant to attacks that
393 /// cause many collisions and very poor performance. Setting it
394 /// manually using this function can expose a DoS attack vector.
396 /// The `hash_builder` passed should implement the [`BuildHasher`] trait for
397 /// the HashMap to be useful, see its documentation for details.
402 /// use std::collections::HashSet;
403 /// use std::collections::hash_map::RandomState;
405 /// let s = RandomState::new();
406 /// let mut set = HashSet::with_capacity_and_hasher(10, s);
410 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
411 pub fn with_capacity_and_hasher(capacity
: usize, hasher
: S
) -> HashSet
<T
, S
> {
412 HashSet { base: base::HashSet::with_capacity_and_hasher(capacity, hasher) }
415 /// Returns a reference to the set's [`BuildHasher`].
420 /// use std::collections::HashSet;
421 /// use std::collections::hash_map::RandomState;
423 /// let hasher = RandomState::new();
424 /// let set: HashSet<i32> = HashSet::with_hasher(hasher);
425 /// let hasher: &RandomState = set.hasher();
428 #[stable(feature = "hashmap_public_hasher", since = "1.9.0")]
429 pub fn hasher(&self) -> &S
{
434 impl<T
, S
> HashSet
<T
, S
>
439 /// Reserves capacity for at least `additional` more elements to be inserted
440 /// in the `HashSet`. The collection may reserve more space to speculatively
441 /// avoid frequent reallocations. After calling `reserve`,
442 /// capacity will be greater than or equal to `self.len() + additional`.
443 /// Does nothing if capacity is already sufficient.
447 /// Panics if the new allocation size overflows `usize`.
452 /// use std::collections::HashSet;
453 /// let mut set: HashSet<i32> = HashSet::new();
455 /// assert!(set.capacity() >= 10);
458 #[stable(feature = "rust1", since = "1.0.0")]
459 pub fn reserve(&mut self, additional
: usize) {
460 self.base
.reserve(additional
)
463 /// Tries to reserve capacity for at least `additional` more elements to be inserted
464 /// in the `HashSet`. The collection may reserve more space to speculatively
465 /// avoid frequent reallocations. After calling `try_reserve`,
466 /// capacity will be greater than or equal to `self.len() + additional` if
467 /// it returns `Ok(())`.
468 /// Does nothing if capacity is already sufficient.
472 /// If the capacity overflows, or the allocator reports a failure, then an error
478 /// use std::collections::HashSet;
479 /// let mut set: HashSet<i32> = HashSet::new();
480 /// set.try_reserve(10).expect("why is the test harness OOMing on a handful of bytes?");
483 #[stable(feature = "try_reserve", since = "1.57.0")]
484 pub fn try_reserve(&mut self, additional
: usize) -> Result
<(), TryReserveError
> {
485 self.base
.try_reserve(additional
).map_err(map_try_reserve_error
)
488 /// Shrinks the capacity of the set as much as possible. It will drop
489 /// down as much as possible while maintaining the internal rules
490 /// and possibly leaving some space in accordance with the resize policy.
495 /// use std::collections::HashSet;
497 /// let mut set = HashSet::with_capacity(100);
500 /// assert!(set.capacity() >= 100);
501 /// set.shrink_to_fit();
502 /// assert!(set.capacity() >= 2);
505 #[stable(feature = "rust1", since = "1.0.0")]
506 pub fn shrink_to_fit(&mut self) {
507 self.base
.shrink_to_fit()
510 /// Shrinks the capacity of the set with a lower limit. It will drop
511 /// down no lower than the supplied limit while maintaining the internal rules
512 /// and possibly leaving some space in accordance with the resize policy.
514 /// If the current capacity is less than the lower limit, this is a no-op.
518 /// use std::collections::HashSet;
520 /// let mut set = HashSet::with_capacity(100);
523 /// assert!(set.capacity() >= 100);
524 /// set.shrink_to(10);
525 /// assert!(set.capacity() >= 10);
526 /// set.shrink_to(0);
527 /// assert!(set.capacity() >= 2);
530 #[stable(feature = "shrink_to", since = "1.56.0")]
531 pub fn shrink_to(&mut self, min_capacity
: usize) {
532 self.base
.shrink_to(min_capacity
)
535 /// Visits the values representing the difference,
536 /// i.e., the values that are in `self` but not in `other`.
541 /// use std::collections::HashSet;
542 /// let a = HashSet::from([1, 2, 3]);
543 /// let b = HashSet::from([4, 2, 3, 4]);
545 /// // Can be seen as `a - b`.
546 /// for x in a.difference(&b) {
547 /// println!("{x}"); // Print 1
550 /// let diff: HashSet<_> = a.difference(&b).collect();
551 /// assert_eq!(diff, [1].iter().collect());
553 /// // Note that difference is not symmetric,
554 /// // and `b - a` means something else:
555 /// let diff: HashSet<_> = b.difference(&a).collect();
556 /// assert_eq!(diff, [4].iter().collect());
559 #[rustc_lint_query_instability]
560 #[stable(feature = "rust1", since = "1.0.0")]
561 pub fn difference
<'a
>(&'a
self, other
: &'a HashSet
<T
, S
>) -> Difference
<'a
, T
, S
> {
562 Difference { iter: self.iter(), other }
565 /// Visits the values representing the symmetric difference,
566 /// i.e., the values that are in `self` or in `other` but not in both.
571 /// use std::collections::HashSet;
572 /// let a = HashSet::from([1, 2, 3]);
573 /// let b = HashSet::from([4, 2, 3, 4]);
575 /// // Print 1, 4 in arbitrary order.
576 /// for x in a.symmetric_difference(&b) {
580 /// let diff1: HashSet<_> = a.symmetric_difference(&b).collect();
581 /// let diff2: HashSet<_> = b.symmetric_difference(&a).collect();
583 /// assert_eq!(diff1, diff2);
584 /// assert_eq!(diff1, [1, 4].iter().collect());
587 #[rustc_lint_query_instability]
588 #[stable(feature = "rust1", since = "1.0.0")]
589 pub fn symmetric_difference
<'a
>(
591 other
: &'a HashSet
<T
, S
>,
592 ) -> SymmetricDifference
<'a
, T
, S
> {
593 SymmetricDifference { iter: self.difference(other).chain(other.difference(self)) }
596 /// Visits the values representing the intersection,
597 /// i.e., the values that are both in `self` and `other`.
599 /// When an equal element is present in `self` and `other`
600 /// then the resulting `Intersection` may yield references to
601 /// one or the other. This can be relevant if `T` contains fields which
602 /// are not compared by its `Eq` implementation, and may hold different
603 /// value between the two equal copies of `T` in the two sets.
608 /// use std::collections::HashSet;
609 /// let a = HashSet::from([1, 2, 3]);
610 /// let b = HashSet::from([4, 2, 3, 4]);
612 /// // Print 2, 3 in arbitrary order.
613 /// for x in a.intersection(&b) {
617 /// let intersection: HashSet<_> = a.intersection(&b).collect();
618 /// assert_eq!(intersection, [2, 3].iter().collect());
621 #[rustc_lint_query_instability]
622 #[stable(feature = "rust1", since = "1.0.0")]
623 pub fn intersection
<'a
>(&'a
self, other
: &'a HashSet
<T
, S
>) -> Intersection
<'a
, T
, S
> {
624 if self.len() <= other
.len() {
625 Intersection { iter: self.iter(), other }
627 Intersection { iter: other.iter(), other: self }
631 /// Visits the values representing the union,
632 /// i.e., all the values in `self` or `other`, without duplicates.
637 /// use std::collections::HashSet;
638 /// let a = HashSet::from([1, 2, 3]);
639 /// let b = HashSet::from([4, 2, 3, 4]);
641 /// // Print 1, 2, 3, 4 in arbitrary order.
642 /// for x in a.union(&b) {
646 /// let union: HashSet<_> = a.union(&b).collect();
647 /// assert_eq!(union, [1, 2, 3, 4].iter().collect());
650 #[rustc_lint_query_instability]
651 #[stable(feature = "rust1", since = "1.0.0")]
652 pub fn union<'a
>(&'a
self, other
: &'a HashSet
<T
, S
>) -> Union
<'a
, T
, S
> {
653 if self.len() >= other
.len() {
654 Union { iter: self.iter().chain(other.difference(self)) }
656 Union { iter: other.iter().chain(self.difference(other)) }
660 /// Returns `true` if the set contains a value.
662 /// The value may be any borrowed form of the set's value type, but
663 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
669 /// use std::collections::HashSet;
671 /// let set = HashSet::from([1, 2, 3]);
672 /// assert_eq!(set.contains(&1), true);
673 /// assert_eq!(set.contains(&4), false);
676 #[stable(feature = "rust1", since = "1.0.0")]
677 pub fn contains
<Q
: ?Sized
>(&self, value
: &Q
) -> bool
682 self.base
.contains(value
)
685 /// Returns a reference to the value in the set, if any, that is equal to the given value.
687 /// The value may be any borrowed form of the set's value type, but
688 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
694 /// use std::collections::HashSet;
696 /// let set = HashSet::from([1, 2, 3]);
697 /// assert_eq!(set.get(&2), Some(&2));
698 /// assert_eq!(set.get(&4), None);
701 #[stable(feature = "set_recovery", since = "1.9.0")]
702 pub fn get
<Q
: ?Sized
>(&self, value
: &Q
) -> Option
<&T
>
710 /// Inserts the given `value` into the set if it is not present, then
711 /// returns a reference to the value in the set.
716 /// #![feature(hash_set_entry)]
718 /// use std::collections::HashSet;
720 /// let mut set = HashSet::from([1, 2, 3]);
721 /// assert_eq!(set.len(), 3);
722 /// assert_eq!(set.get_or_insert(2), &2);
723 /// assert_eq!(set.get_or_insert(100), &100);
724 /// assert_eq!(set.len(), 4); // 100 was inserted
727 #[unstable(feature = "hash_set_entry", issue = "60896")]
728 pub fn get_or_insert(&mut self, value
: T
) -> &T
{
729 // Although the raw entry gives us `&mut T`, we only return `&T` to be consistent with
730 // `get`. Key mutation is "raw" because you're not supposed to affect `Eq` or `Hash`.
731 self.base
.get_or_insert(value
)
734 /// Inserts an owned copy of the given `value` into the set if it is not
735 /// present, then returns a reference to the value in the set.
740 /// #![feature(hash_set_entry)]
742 /// use std::collections::HashSet;
744 /// let mut set: HashSet<String> = ["cat", "dog", "horse"]
745 /// .iter().map(|&pet| pet.to_owned()).collect();
747 /// assert_eq!(set.len(), 3);
748 /// for &pet in &["cat", "dog", "fish"] {
749 /// let value = set.get_or_insert_owned(pet);
750 /// assert_eq!(value, pet);
752 /// assert_eq!(set.len(), 4); // a new "fish" was inserted
755 #[unstable(feature = "hash_set_entry", issue = "60896")]
756 pub fn get_or_insert_owned
<Q
: ?Sized
>(&mut self, value
: &Q
) -> &T
759 Q
: Hash
+ Eq
+ ToOwned
<Owned
= T
>,
761 // Although the raw entry gives us `&mut T`, we only return `&T` to be consistent with
762 // `get`. Key mutation is "raw" because you're not supposed to affect `Eq` or `Hash`.
763 self.base
.get_or_insert_owned(value
)
766 /// Inserts a value computed from `f` into the set if the given `value` is
767 /// not present, then returns a reference to the value in the set.
772 /// #![feature(hash_set_entry)]
774 /// use std::collections::HashSet;
776 /// let mut set: HashSet<String> = ["cat", "dog", "horse"]
777 /// .iter().map(|&pet| pet.to_owned()).collect();
779 /// assert_eq!(set.len(), 3);
780 /// for &pet in &["cat", "dog", "fish"] {
781 /// let value = set.get_or_insert_with(pet, str::to_owned);
782 /// assert_eq!(value, pet);
784 /// assert_eq!(set.len(), 4); // a new "fish" was inserted
787 #[unstable(feature = "hash_set_entry", issue = "60896")]
788 pub fn get_or_insert_with
<Q
: ?Sized
, F
>(&mut self, value
: &Q
, f
: F
) -> &T
794 // Although the raw entry gives us `&mut T`, we only return `&T` to be consistent with
795 // `get`. Key mutation is "raw" because you're not supposed to affect `Eq` or `Hash`.
796 self.base
.get_or_insert_with(value
, f
)
799 /// Returns `true` if `self` has no elements in common with `other`.
800 /// This is equivalent to checking for an empty intersection.
805 /// use std::collections::HashSet;
807 /// let a = HashSet::from([1, 2, 3]);
808 /// let mut b = HashSet::new();
810 /// assert_eq!(a.is_disjoint(&b), true);
812 /// assert_eq!(a.is_disjoint(&b), true);
814 /// assert_eq!(a.is_disjoint(&b), false);
816 #[stable(feature = "rust1", since = "1.0.0")]
817 pub fn is_disjoint(&self, other
: &HashSet
<T
, S
>) -> bool
{
818 if self.len() <= other
.len() {
819 self.iter().all(|v
| !other
.contains(v
))
821 other
.iter().all(|v
| !self.contains(v
))
825 /// Returns `true` if the set is a subset of another,
826 /// i.e., `other` contains at least all the values in `self`.
831 /// use std::collections::HashSet;
833 /// let sup = HashSet::from([1, 2, 3]);
834 /// let mut set = HashSet::new();
836 /// assert_eq!(set.is_subset(&sup), true);
838 /// assert_eq!(set.is_subset(&sup), true);
840 /// assert_eq!(set.is_subset(&sup), false);
842 #[stable(feature = "rust1", since = "1.0.0")]
843 pub fn is_subset(&self, other
: &HashSet
<T
, S
>) -> bool
{
844 if self.len() <= other
.len() { self.iter().all(|v| other.contains(v)) }
else { false }
847 /// Returns `true` if the set is a superset of another,
848 /// i.e., `self` contains at least all the values in `other`.
853 /// use std::collections::HashSet;
855 /// let sub = HashSet::from([1, 2]);
856 /// let mut set = HashSet::new();
858 /// assert_eq!(set.is_superset(&sub), false);
862 /// assert_eq!(set.is_superset(&sub), false);
865 /// assert_eq!(set.is_superset(&sub), true);
868 #[stable(feature = "rust1", since = "1.0.0")]
869 pub fn is_superset(&self, other
: &HashSet
<T
, S
>) -> bool
{
870 other
.is_subset(self)
873 /// Adds a value to the set.
875 /// Returns whether the value was newly inserted. That is:
877 /// - If the set did not previously contain this value, `true` is returned.
878 /// - If the set already contained this value, `false` is returned.
883 /// use std::collections::HashSet;
885 /// let mut set = HashSet::new();
887 /// assert_eq!(set.insert(2), true);
888 /// assert_eq!(set.insert(2), false);
889 /// assert_eq!(set.len(), 1);
892 #[stable(feature = "rust1", since = "1.0.0")]
893 pub fn insert(&mut self, value
: T
) -> bool
{
894 self.base
.insert(value
)
897 /// Adds a value to the set, replacing the existing value, if any, that is equal to the given
898 /// one. Returns the replaced value.
903 /// use std::collections::HashSet;
905 /// let mut set = HashSet::new();
906 /// set.insert(Vec::<i32>::new());
908 /// assert_eq!(set.get(&[][..]).unwrap().capacity(), 0);
909 /// set.replace(Vec::with_capacity(10));
910 /// assert_eq!(set.get(&[][..]).unwrap().capacity(), 10);
913 #[stable(feature = "set_recovery", since = "1.9.0")]
914 pub fn replace(&mut self, value
: T
) -> Option
<T
> {
915 self.base
.replace(value
)
918 /// Removes a value from the set. Returns whether the value was
919 /// present in the set.
921 /// The value may be any borrowed form of the set's value type, but
922 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
928 /// use std::collections::HashSet;
930 /// let mut set = HashSet::new();
933 /// assert_eq!(set.remove(&2), true);
934 /// assert_eq!(set.remove(&2), false);
937 #[stable(feature = "rust1", since = "1.0.0")]
938 pub fn remove
<Q
: ?Sized
>(&mut self, value
: &Q
) -> bool
943 self.base
.remove(value
)
946 /// Removes and returns the value in the set, if any, that is equal to the given one.
948 /// The value may be any borrowed form of the set's value type, but
949 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
955 /// use std::collections::HashSet;
957 /// let mut set = HashSet::from([1, 2, 3]);
958 /// assert_eq!(set.take(&2), Some(2));
959 /// assert_eq!(set.take(&2), None);
962 #[stable(feature = "set_recovery", since = "1.9.0")]
963 pub fn take
<Q
: ?Sized
>(&mut self, value
: &Q
) -> Option
<T
>
968 self.base
.take(value
)
972 #[stable(feature = "rust1", since = "1.0.0")]
973 impl<T
, S
> Clone
for HashSet
<T
, S
>
979 fn clone(&self) -> Self {
980 Self { base: self.base.clone() }
984 fn clone_from(&mut self, other
: &Self) {
985 self.base
.clone_from(&other
.base
);
989 #[stable(feature = "rust1", since = "1.0.0")]
990 impl<T
, S
> PartialEq
for HashSet
<T
, S
>
995 fn eq(&self, other
: &HashSet
<T
, S
>) -> bool
{
996 if self.len() != other
.len() {
1000 self.iter().all(|key
| other
.contains(key
))
1004 #[stable(feature = "rust1", since = "1.0.0")]
1005 impl<T
, S
> Eq
for HashSet
<T
, S
>
1012 #[stable(feature = "rust1", since = "1.0.0")]
1013 impl<T
, S
> fmt
::Debug
for HashSet
<T
, S
>
1017 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1018 f
.debug_set().entries(self.iter()).finish()
1022 #[stable(feature = "rust1", since = "1.0.0")]
1023 impl<T
, S
> FromIterator
<T
> for HashSet
<T
, S
>
1026 S
: BuildHasher
+ Default
,
1029 fn from_iter
<I
: IntoIterator
<Item
= T
>>(iter
: I
) -> HashSet
<T
, S
> {
1030 let mut set
= HashSet
::with_hasher(Default
::default());
1036 #[stable(feature = "std_collections_from_array", since = "1.56.0")]
1037 // Note: as what is currently the most convenient built-in way to construct
1038 // a HashSet, a simple usage of this function must not *require* the user
1039 // to provide a type annotation in order to infer the third type parameter
1040 // (the hasher parameter, conventionally "S").
1041 // To that end, this impl is defined using RandomState as the concrete
1042 // type of S, rather than being generic over `S: BuildHasher + Default`.
1043 // It is expected that users who want to specify a hasher will manually use
1044 // `with_capacity_and_hasher`.
1045 // If type parameter defaults worked on impls, and if type parameter
1046 // defaults could be mixed with const generics, then perhaps
1047 // this could be generalized.
1048 // See also the equivalent impl on HashMap.
1049 impl<T
, const N
: usize> From
<[T
; N
]> for HashSet
<T
, RandomState
>
1056 /// use std::collections::HashSet;
1058 /// let set1 = HashSet::from([1, 2, 3, 4]);
1059 /// let set2: HashSet<_> = [1, 2, 3, 4].into();
1060 /// assert_eq!(set1, set2);
1062 fn from(arr
: [T
; N
]) -> Self {
1063 Self::from_iter(arr
)
1067 #[stable(feature = "rust1", since = "1.0.0")]
1068 impl<T
, S
> Extend
<T
> for HashSet
<T
, S
>
1074 fn extend
<I
: IntoIterator
<Item
= T
>>(&mut self, iter
: I
) {
1075 self.base
.extend(iter
);
1079 fn extend_one(&mut self, item
: T
) {
1080 self.base
.insert(item
);
1084 fn extend_reserve(&mut self, additional
: usize) {
1085 self.base
.extend_reserve(additional
);
1089 #[stable(feature = "hash_extend_copy", since = "1.4.0")]
1090 impl<'a
, T
, S
> Extend
<&'a T
> for HashSet
<T
, S
>
1092 T
: 'a
+ Eq
+ Hash
+ Copy
,
1096 fn extend
<I
: IntoIterator
<Item
= &'a T
>>(&mut self, iter
: I
) {
1097 self.extend(iter
.into_iter().cloned());
1101 fn extend_one(&mut self, &item
: &'a T
) {
1102 self.base
.insert(item
);
1106 fn extend_reserve(&mut self, additional
: usize) {
1107 Extend
::<T
>::extend_reserve(self, additional
)
1111 #[stable(feature = "rust1", since = "1.0.0")]
1112 impl<T
, S
> Default
for HashSet
<T
, S
>
1116 /// Creates an empty `HashSet<T, S>` with the `Default` value for the hasher.
1118 fn default() -> HashSet
<T
, S
> {
1119 HashSet { base: Default::default() }
1123 #[stable(feature = "rust1", since = "1.0.0")]
1124 impl<T
, S
> BitOr
<&HashSet
<T
, S
>> for &HashSet
<T
, S
>
1126 T
: Eq
+ Hash
+ Clone
,
1127 S
: BuildHasher
+ Default
,
1129 type Output
= HashSet
<T
, S
>;
1131 /// Returns the union of `self` and `rhs` as a new `HashSet<T, S>`.
1136 /// use std::collections::HashSet;
1138 /// let a = HashSet::from([1, 2, 3]);
1139 /// let b = HashSet::from([3, 4, 5]);
1141 /// let set = &a | &b;
1144 /// let expected = [1, 2, 3, 4, 5];
1146 /// assert!(expected.contains(x));
1149 /// assert_eq!(i, expected.len());
1151 fn bitor(self, rhs
: &HashSet
<T
, S
>) -> HashSet
<T
, S
> {
1152 self.union(rhs
).cloned().collect()
1156 #[stable(feature = "rust1", since = "1.0.0")]
1157 impl<T
, S
> BitAnd
<&HashSet
<T
, S
>> for &HashSet
<T
, S
>
1159 T
: Eq
+ Hash
+ Clone
,
1160 S
: BuildHasher
+ Default
,
1162 type Output
= HashSet
<T
, S
>;
1164 /// Returns the intersection of `self` and `rhs` as a new `HashSet<T, S>`.
1169 /// use std::collections::HashSet;
1171 /// let a = HashSet::from([1, 2, 3]);
1172 /// let b = HashSet::from([2, 3, 4]);
1174 /// let set = &a & &b;
1177 /// let expected = [2, 3];
1179 /// assert!(expected.contains(x));
1182 /// assert_eq!(i, expected.len());
1184 fn bitand(self, rhs
: &HashSet
<T
, S
>) -> HashSet
<T
, S
> {
1185 self.intersection(rhs
).cloned().collect()
1189 #[stable(feature = "rust1", since = "1.0.0")]
1190 impl<T
, S
> BitXor
<&HashSet
<T
, S
>> for &HashSet
<T
, S
>
1192 T
: Eq
+ Hash
+ Clone
,
1193 S
: BuildHasher
+ Default
,
1195 type Output
= HashSet
<T
, S
>;
1197 /// Returns the symmetric difference of `self` and `rhs` as a new `HashSet<T, S>`.
1202 /// use std::collections::HashSet;
1204 /// let a = HashSet::from([1, 2, 3]);
1205 /// let b = HashSet::from([3, 4, 5]);
1207 /// let set = &a ^ &b;
1210 /// let expected = [1, 2, 4, 5];
1212 /// assert!(expected.contains(x));
1215 /// assert_eq!(i, expected.len());
1217 fn bitxor(self, rhs
: &HashSet
<T
, S
>) -> HashSet
<T
, S
> {
1218 self.symmetric_difference(rhs
).cloned().collect()
1222 #[stable(feature = "rust1", since = "1.0.0")]
1223 impl<T
, S
> Sub
<&HashSet
<T
, S
>> for &HashSet
<T
, S
>
1225 T
: Eq
+ Hash
+ Clone
,
1226 S
: BuildHasher
+ Default
,
1228 type Output
= HashSet
<T
, S
>;
1230 /// Returns the difference of `self` and `rhs` as a new `HashSet<T, S>`.
1235 /// use std::collections::HashSet;
1237 /// let a = HashSet::from([1, 2, 3]);
1238 /// let b = HashSet::from([3, 4, 5]);
1240 /// let set = &a - &b;
1243 /// let expected = [1, 2];
1245 /// assert!(expected.contains(x));
1248 /// assert_eq!(i, expected.len());
1250 fn sub(self, rhs
: &HashSet
<T
, S
>) -> HashSet
<T
, S
> {
1251 self.difference(rhs
).cloned().collect()
1255 /// An iterator over the items of a `HashSet`.
1257 /// This `struct` is created by the [`iter`] method on [`HashSet`].
1258 /// See its documentation for more.
1260 /// [`iter`]: HashSet::iter
1265 /// use std::collections::HashSet;
1267 /// let a = HashSet::from([1, 2, 3]);
1269 /// let mut iter = a.iter();
1271 #[stable(feature = "rust1", since = "1.0.0")]
1272 pub struct Iter
<'a
, K
: 'a
> {
1273 base
: base
::Iter
<'a
, K
>,
1276 /// An owning iterator over the items of a `HashSet`.
1278 /// This `struct` is created by the [`into_iter`] method on [`HashSet`]
1279 /// (provided by the [`IntoIterator`] trait). See its documentation for more.
1281 /// [`into_iter`]: IntoIterator::into_iter
1282 /// [`IntoIterator`]: crate::iter::IntoIterator
1287 /// use std::collections::HashSet;
1289 /// let a = HashSet::from([1, 2, 3]);
1291 /// let mut iter = a.into_iter();
1293 #[stable(feature = "rust1", since = "1.0.0")]
1294 pub struct IntoIter
<K
> {
1295 base
: base
::IntoIter
<K
>,
1298 /// A draining iterator over the items of a `HashSet`.
1300 /// This `struct` is created by the [`drain`] method on [`HashSet`].
1301 /// See its documentation for more.
1303 /// [`drain`]: HashSet::drain
1308 /// use std::collections::HashSet;
1310 /// let mut a = HashSet::from([1, 2, 3]);
1312 /// let mut drain = a.drain();
1314 #[stable(feature = "rust1", since = "1.0.0")]
1315 pub struct Drain
<'a
, K
: 'a
> {
1316 base
: base
::Drain
<'a
, K
>,
1319 /// A draining, filtering iterator over the items of a `HashSet`.
1321 /// This `struct` is created by the [`drain_filter`] method on [`HashSet`].
1323 /// [`drain_filter`]: HashSet::drain_filter
1328 /// #![feature(hash_drain_filter)]
1330 /// use std::collections::HashSet;
1332 /// let mut a = HashSet::from([1, 2, 3]);
1334 /// let mut drain_filtered = a.drain_filter(|v| v % 2 == 0);
1336 #[unstable(feature = "hash_drain_filter", issue = "59618")]
1337 pub struct DrainFilter
<'a
, K
, F
>
1339 F
: FnMut(&K
) -> bool
,
1341 base
: base
::DrainFilter
<'a
, K
, F
>,
1344 /// A lazy iterator producing elements in the intersection of `HashSet`s.
1346 /// This `struct` is created by the [`intersection`] method on [`HashSet`].
1347 /// See its documentation for more.
1349 /// [`intersection`]: HashSet::intersection
1354 /// use std::collections::HashSet;
1356 /// let a = HashSet::from([1, 2, 3]);
1357 /// let b = HashSet::from([4, 2, 3, 4]);
1359 /// let mut intersection = a.intersection(&b);
1361 #[must_use = "this returns the intersection as an iterator, \
1362 without modifying either input set"]
1363 #[stable(feature = "rust1", since = "1.0.0")]
1364 pub struct Intersection
<'a
, T
: 'a
, S
: 'a
> {
1365 // iterator of the first set
1368 other
: &'a HashSet
<T
, S
>,
1371 /// A lazy iterator producing elements in the difference of `HashSet`s.
1373 /// This `struct` is created by the [`difference`] method on [`HashSet`].
1374 /// See its documentation for more.
1376 /// [`difference`]: HashSet::difference
1381 /// use std::collections::HashSet;
1383 /// let a = HashSet::from([1, 2, 3]);
1384 /// let b = HashSet::from([4, 2, 3, 4]);
1386 /// let mut difference = a.difference(&b);
1388 #[must_use = "this returns the difference as an iterator, \
1389 without modifying either input set"]
1390 #[stable(feature = "rust1", since = "1.0.0")]
1391 pub struct Difference
<'a
, T
: 'a
, S
: 'a
> {
1392 // iterator of the first set
1395 other
: &'a HashSet
<T
, S
>,
1398 /// A lazy iterator producing elements in the symmetric difference of `HashSet`s.
1400 /// This `struct` is created by the [`symmetric_difference`] method on
1401 /// [`HashSet`]. See its documentation for more.
1403 /// [`symmetric_difference`]: HashSet::symmetric_difference
1408 /// use std::collections::HashSet;
1410 /// let a = HashSet::from([1, 2, 3]);
1411 /// let b = HashSet::from([4, 2, 3, 4]);
1413 /// let mut intersection = a.symmetric_difference(&b);
1415 #[must_use = "this returns the difference as an iterator, \
1416 without modifying either input set"]
1417 #[stable(feature = "rust1", since = "1.0.0")]
1418 pub struct SymmetricDifference
<'a
, T
: 'a
, S
: 'a
> {
1419 iter
: Chain
<Difference
<'a
, T
, S
>, Difference
<'a
, T
, S
>>,
1422 /// A lazy iterator producing elements in the union of `HashSet`s.
1424 /// This `struct` is created by the [`union`] method on [`HashSet`].
1425 /// See its documentation for more.
1427 /// [`union`]: HashSet::union
1432 /// use std::collections::HashSet;
1434 /// let a = HashSet::from([1, 2, 3]);
1435 /// let b = HashSet::from([4, 2, 3, 4]);
1437 /// let mut union_iter = a.union(&b);
1439 #[must_use = "this returns the union as an iterator, \
1440 without modifying either input set"]
1441 #[stable(feature = "rust1", since = "1.0.0")]
1442 pub struct Union
<'a
, T
: 'a
, S
: 'a
> {
1443 iter
: Chain
<Iter
<'a
, T
>, Difference
<'a
, T
, S
>>,
1446 #[stable(feature = "rust1", since = "1.0.0")]
1447 impl<'a
, T
, S
> IntoIterator
for &'a HashSet
<T
, S
> {
1449 type IntoIter
= Iter
<'a
, T
>;
1452 #[rustc_lint_query_instability]
1453 fn into_iter(self) -> Iter
<'a
, T
> {
1458 #[stable(feature = "rust1", since = "1.0.0")]
1459 impl<T
, S
> IntoIterator
for HashSet
<T
, S
> {
1461 type IntoIter
= IntoIter
<T
>;
1463 /// Creates a consuming iterator, that is, one that moves each value out
1464 /// of the set in arbitrary order. The set cannot be used after calling
1470 /// use std::collections::HashSet;
1471 /// let mut set = HashSet::new();
1472 /// set.insert("a".to_string());
1473 /// set.insert("b".to_string());
1475 /// // Not possible to collect to a Vec<String> with a regular `.iter()`.
1476 /// let v: Vec<String> = set.into_iter().collect();
1478 /// // Will print in an arbitrary order.
1480 /// println!("{x}");
1484 #[rustc_lint_query_instability]
1485 fn into_iter(self) -> IntoIter
<T
> {
1486 IntoIter { base: self.base.into_iter() }
1490 #[stable(feature = "rust1", since = "1.0.0")]
1491 impl<K
> Clone
for Iter
<'_
, K
> {
1493 fn clone(&self) -> Self {
1494 Iter { base: self.base.clone() }
1497 #[stable(feature = "rust1", since = "1.0.0")]
1498 impl<'a
, K
> Iterator
for Iter
<'a
, K
> {
1502 fn next(&mut self) -> Option
<&'a K
> {
1506 fn size_hint(&self) -> (usize, Option
<usize>) {
1507 self.base
.size_hint()
1510 #[stable(feature = "rust1", since = "1.0.0")]
1511 impl<K
> ExactSizeIterator
for Iter
<'_
, K
> {
1513 fn len(&self) -> usize {
1517 #[stable(feature = "fused", since = "1.26.0")]
1518 impl<K
> FusedIterator
for Iter
<'_
, K
> {}
1520 #[stable(feature = "std_debug", since = "1.16.0")]
1521 impl<K
: fmt
::Debug
> fmt
::Debug
for Iter
<'_
, K
> {
1522 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1523 f
.debug_list().entries(self.clone()).finish()
1527 #[stable(feature = "rust1", since = "1.0.0")]
1528 impl<K
> Iterator
for IntoIter
<K
> {
1532 fn next(&mut self) -> Option
<K
> {
1536 fn size_hint(&self) -> (usize, Option
<usize>) {
1537 self.base
.size_hint()
1540 #[stable(feature = "rust1", since = "1.0.0")]
1541 impl<K
> ExactSizeIterator
for IntoIter
<K
> {
1543 fn len(&self) -> usize {
1547 #[stable(feature = "fused", since = "1.26.0")]
1548 impl<K
> FusedIterator
for IntoIter
<K
> {}
1550 #[stable(feature = "std_debug", since = "1.16.0")]
1551 impl<K
: fmt
::Debug
> fmt
::Debug
for IntoIter
<K
> {
1552 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1553 fmt
::Debug
::fmt(&self.base
, f
)
1557 #[stable(feature = "rust1", since = "1.0.0")]
1558 impl<'a
, K
> Iterator
for Drain
<'a
, K
> {
1562 fn next(&mut self) -> Option
<K
> {
1566 fn size_hint(&self) -> (usize, Option
<usize>) {
1567 self.base
.size_hint()
1570 #[stable(feature = "rust1", since = "1.0.0")]
1571 impl<K
> ExactSizeIterator
for Drain
<'_
, K
> {
1573 fn len(&self) -> usize {
1577 #[stable(feature = "fused", since = "1.26.0")]
1578 impl<K
> FusedIterator
for Drain
<'_
, K
> {}
1580 #[stable(feature = "std_debug", since = "1.16.0")]
1581 impl<K
: fmt
::Debug
> fmt
::Debug
for Drain
<'_
, K
> {
1582 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1583 fmt
::Debug
::fmt(&self.base
, f
)
1587 #[unstable(feature = "hash_drain_filter", issue = "59618")]
1588 impl<K
, F
> Iterator
for DrainFilter
<'_
, K
, F
>
1590 F
: FnMut(&K
) -> bool
,
1595 fn next(&mut self) -> Option
<K
> {
1599 fn size_hint(&self) -> (usize, Option
<usize>) {
1600 self.base
.size_hint()
1604 #[unstable(feature = "hash_drain_filter", issue = "59618")]
1605 impl<K
, F
> FusedIterator
for DrainFilter
<'_
, K
, F
> where F
: FnMut(&K
) -> bool {}
1607 #[unstable(feature = "hash_drain_filter", issue = "59618")]
1608 impl<'a
, K
, F
> fmt
::Debug
for DrainFilter
<'a
, K
, F
>
1610 F
: FnMut(&K
) -> bool
,
1612 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1613 f
.debug_struct("DrainFilter").finish_non_exhaustive()
1617 #[stable(feature = "rust1", since = "1.0.0")]
1618 impl<T
, S
> Clone
for Intersection
<'_
, T
, S
> {
1620 fn clone(&self) -> Self {
1621 Intersection { iter: self.iter.clone(), ..*self }
1625 #[stable(feature = "rust1", since = "1.0.0")]
1626 impl<'a
, T
, S
> Iterator
for Intersection
<'a
, T
, S
>
1634 fn next(&mut self) -> Option
<&'a T
> {
1636 let elt
= self.iter
.next()?
;
1637 if self.other
.contains(elt
) {
1644 fn size_hint(&self) -> (usize, Option
<usize>) {
1645 let (_
, upper
) = self.iter
.size_hint();
1650 #[stable(feature = "std_debug", since = "1.16.0")]
1651 impl<T
, S
> fmt
::Debug
for Intersection
<'_
, T
, S
>
1653 T
: fmt
::Debug
+ Eq
+ Hash
,
1656 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1657 f
.debug_list().entries(self.clone()).finish()
1661 #[stable(feature = "fused", since = "1.26.0")]
1662 impl<T
, S
> FusedIterator
for Intersection
<'_
, T
, S
>
1669 #[stable(feature = "rust1", since = "1.0.0")]
1670 impl<T
, S
> Clone
for Difference
<'_
, T
, S
> {
1672 fn clone(&self) -> Self {
1673 Difference { iter: self.iter.clone(), ..*self }
1677 #[stable(feature = "rust1", since = "1.0.0")]
1678 impl<'a
, T
, S
> Iterator
for Difference
<'a
, T
, S
>
1686 fn next(&mut self) -> Option
<&'a T
> {
1688 let elt
= self.iter
.next()?
;
1689 if !self.other
.contains(elt
) {
1696 fn size_hint(&self) -> (usize, Option
<usize>) {
1697 let (_
, upper
) = self.iter
.size_hint();
1702 #[stable(feature = "fused", since = "1.26.0")]
1703 impl<T
, S
> FusedIterator
for Difference
<'_
, T
, S
>
1710 #[stable(feature = "std_debug", since = "1.16.0")]
1711 impl<T
, S
> fmt
::Debug
for Difference
<'_
, T
, S
>
1713 T
: fmt
::Debug
+ Eq
+ Hash
,
1716 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1717 f
.debug_list().entries(self.clone()).finish()
1721 #[stable(feature = "rust1", since = "1.0.0")]
1722 impl<T
, S
> Clone
for SymmetricDifference
<'_
, T
, S
> {
1724 fn clone(&self) -> Self {
1725 SymmetricDifference { iter: self.iter.clone() }
1729 #[stable(feature = "rust1", since = "1.0.0")]
1730 impl<'a
, T
, S
> Iterator
for SymmetricDifference
<'a
, T
, S
>
1738 fn next(&mut self) -> Option
<&'a T
> {
1742 fn size_hint(&self) -> (usize, Option
<usize>) {
1743 self.iter
.size_hint()
1747 #[stable(feature = "fused", since = "1.26.0")]
1748 impl<T
, S
> FusedIterator
for SymmetricDifference
<'_
, T
, S
>
1755 #[stable(feature = "std_debug", since = "1.16.0")]
1756 impl<T
, S
> fmt
::Debug
for SymmetricDifference
<'_
, T
, S
>
1758 T
: fmt
::Debug
+ Eq
+ Hash
,
1761 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1762 f
.debug_list().entries(self.clone()).finish()
1766 #[stable(feature = "rust1", since = "1.0.0")]
1767 impl<T
, S
> Clone
for Union
<'_
, T
, S
> {
1769 fn clone(&self) -> Self {
1770 Union { iter: self.iter.clone() }
1774 #[stable(feature = "fused", since = "1.26.0")]
1775 impl<T
, S
> FusedIterator
for Union
<'_
, T
, S
>
1782 #[stable(feature = "std_debug", since = "1.16.0")]
1783 impl<T
, S
> fmt
::Debug
for Union
<'_
, T
, S
>
1785 T
: fmt
::Debug
+ Eq
+ Hash
,
1788 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1789 f
.debug_list().entries(self.clone()).finish()
1793 #[stable(feature = "rust1", since = "1.0.0")]
1794 impl<'a
, T
, S
> Iterator
for Union
<'a
, T
, S
>
1802 fn next(&mut self) -> Option
<&'a T
> {
1806 fn size_hint(&self) -> (usize, Option
<usize>) {
1807 self.iter
.size_hint()
1812 fn assert_covariance() {
1813 fn set
<'new
>(v
: HashSet
<&'
static str>) -> HashSet
<&'new
str> {
1816 fn iter
<'a
, 'new
>(v
: Iter
<'a
, &'
static str>) -> Iter
<'a
, &'new
str> {
1819 fn into_iter
<'new
>(v
: IntoIter
<&'
static str>) -> IntoIter
<&'new
str> {
1822 fn difference
<'a
, 'new
>(
1823 v
: Difference
<'a
, &'
static str, RandomState
>,
1824 ) -> Difference
<'a
, &'new
str, RandomState
> {
1827 fn symmetric_difference
<'a
, 'new
>(
1828 v
: SymmetricDifference
<'a
, &'
static str, RandomState
>,
1829 ) -> SymmetricDifference
<'a
, &'new
str, RandomState
> {
1832 fn intersection
<'a
, 'new
>(
1833 v
: Intersection
<'a
, &'
static str, RandomState
>,
1834 ) -> Intersection
<'a
, &'new
str, RandomState
> {
1838 v
: Union
<'a
, &'
static str, RandomState
>,
1839 ) -> Union
<'a
, &'new
str, RandomState
> {
1842 fn drain
<'new
>(d
: Drain
<'
static, &'
static str>) -> Drain
<'new
, &'new
str> {