1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
13 use cmp
::{Eq, PartialEq}
;
14 use core
::marker
::Sized
;
19 use iter
::{Iterator, IntoIterator, ExactSizeIterator, FromIterator, Map, Chain, Extend}
;
20 use ops
::{BitOr, BitAnd, BitXor, Sub}
;
21 use option
::Option
::{Some, None, self}
;
23 use super::map
::{self, HashMap, Keys, RandomState}
;
24 use super::state
::HashState
;
26 const INITIAL_CAPACITY
: usize = 32;
28 // Future Optimization (FIXME!)
29 // =============================
31 // Iteration over zero sized values is a noop. There is no need
32 // for `bucket.val` in the case of HashSet. I suppose we would need HKT
33 // to get rid of it properly.
35 /// An implementation of a hash set using the underlying representation of a
36 /// HashMap where the value is ().
38 /// As with the `HashMap` type, a `HashSet` requires that the elements
39 /// implement the `Eq` and `Hash` traits. This can frequently be achieved by
40 /// using `#[derive(PartialEq, Eq, Hash)]`. If you implement these yourself,
41 /// it is important that the following property holds:
44 /// k1 == k2 -> hash(k1) == hash(k2)
47 /// In other words, if two keys are equal, their hashes must be equal.
50 /// It is a logic error for an item to be modified in such a way that the
51 /// item's hash, as determined by the `Hash` trait, or its equality, as
52 /// determined by the `Eq` trait, changes while it is in the set. This is
53 /// normally only possible through `Cell`, `RefCell`, global state, I/O, or
59 /// use std::collections::HashSet;
60 /// // Type inference lets us omit an explicit type signature (which
61 /// // would be `HashSet<&str>` in this example).
62 /// let mut books = HashSet::new();
64 /// // Add some books.
65 /// books.insert("A Dance With Dragons");
66 /// books.insert("To Kill a Mockingbird");
67 /// books.insert("The Odyssey");
68 /// books.insert("The Great Gatsby");
70 /// // Check for a specific one.
71 /// if !books.contains("The Winds of Winter") {
72 /// println!("We have {} books, but The Winds of Winter ain't one.",
77 /// books.remove("The Odyssey");
79 /// // Iterate over everything.
80 /// for book in &books {
81 /// println!("{}", book);
85 /// The easiest way to use `HashSet` with a custom type is to derive
86 /// `Eq` and `Hash`. We must also derive `PartialEq`, this will in the
87 /// future be implied by `Eq`.
90 /// use std::collections::HashSet;
91 /// #[derive(Hash, Eq, PartialEq, Debug)]
92 /// struct Viking<'a> {
97 /// let mut vikings = HashSet::new();
99 /// vikings.insert(Viking { name: "Einar", power: 9 });
100 /// vikings.insert(Viking { name: "Einar", power: 9 });
101 /// vikings.insert(Viking { name: "Olaf", power: 4 });
102 /// vikings.insert(Viking { name: "Harald", power: 8 });
104 /// // Use derived implementation to print the vikings.
105 /// for x in &vikings {
106 /// println!("{:?}", x);
110 #[stable(feature = "rust1", since = "1.0.0")]
111 pub struct HashSet
<T
, S
= RandomState
> {
112 map
: HashMap
<T
, (), S
>
115 impl<T
: Hash
+ Eq
> HashSet
<T
, RandomState
> {
116 /// Creates an empty HashSet.
121 /// use std::collections::HashSet;
122 /// let mut set: HashSet<i32> = HashSet::new();
125 #[stable(feature = "rust1", since = "1.0.0")]
126 pub fn new() -> HashSet
<T
, RandomState
> {
127 HashSet
::with_capacity(INITIAL_CAPACITY
)
130 /// Creates an empty HashSet with space for at least `n` elements in
136 /// use std::collections::HashSet;
137 /// let mut set: HashSet<i32> = HashSet::with_capacity(10);
140 #[stable(feature = "rust1", since = "1.0.0")]
141 pub fn with_capacity(capacity
: usize) -> HashSet
<T
, RandomState
> {
142 HashSet { map: HashMap::with_capacity(capacity) }
146 impl<T
, S
> HashSet
<T
, S
>
147 where T
: Eq
+ Hash
, S
: HashState
149 /// Creates a new empty hash set which will use the given hasher to hash
152 /// The hash set is also created with the default initial capacity.
157 /// # #![feature(hashmap_hasher)]
158 /// use std::collections::HashSet;
159 /// use std::collections::hash_map::RandomState;
161 /// let s = RandomState::new();
162 /// let mut set = HashSet::with_hash_state(s);
166 #[unstable(feature = "hashmap_hasher", reason = "hasher stuff is unclear")]
167 pub fn with_hash_state(hash_state
: S
) -> HashSet
<T
, S
> {
168 HashSet
::with_capacity_and_hash_state(INITIAL_CAPACITY
, hash_state
)
171 /// Creates an empty HashSet with space for at least `capacity`
172 /// elements in the hash table, using `hasher` to hash the keys.
174 /// Warning: `hasher` is normally randomly generated, and
175 /// is designed to allow `HashSet`s to be resistant to attacks that
176 /// cause many collisions and very poor performance. Setting it
177 /// manually using this function can expose a DoS attack vector.
182 /// # #![feature(hashmap_hasher)]
183 /// use std::collections::HashSet;
184 /// use std::collections::hash_map::RandomState;
186 /// let s = RandomState::new();
187 /// let mut set = HashSet::with_capacity_and_hash_state(10, s);
191 #[unstable(feature = "hashmap_hasher", reason = "hasher stuff is unclear")]
192 pub fn with_capacity_and_hash_state(capacity
: usize, hash_state
: S
)
195 map
: HashMap
::with_capacity_and_hash_state(capacity
, hash_state
),
199 /// Returns the number of elements the set can hold without reallocating.
204 /// use std::collections::HashSet;
205 /// let set: HashSet<i32> = HashSet::with_capacity(100);
206 /// assert!(set.capacity() >= 100);
209 #[stable(feature = "rust1", since = "1.0.0")]
210 pub fn capacity(&self) -> usize {
214 /// Reserves capacity for at least `additional` more elements to be inserted
215 /// in the `HashSet`. The collection may reserve more space to avoid
216 /// frequent reallocations.
220 /// Panics if the new allocation size overflows `usize`.
225 /// use std::collections::HashSet;
226 /// let mut set: HashSet<i32> = HashSet::new();
229 #[stable(feature = "rust1", since = "1.0.0")]
230 pub fn reserve(&mut self, additional
: usize) {
231 self.map
.reserve(additional
)
234 /// Shrinks the capacity of the set as much as possible. It will drop
235 /// down as much as possible while maintaining the internal rules
236 /// and possibly leaving some space in accordance with the resize policy.
241 /// use std::collections::HashSet;
243 /// let mut set = HashSet::with_capacity(100);
246 /// assert!(set.capacity() >= 100);
247 /// set.shrink_to_fit();
248 /// assert!(set.capacity() >= 2);
250 #[stable(feature = "rust1", since = "1.0.0")]
251 pub fn shrink_to_fit(&mut self) {
252 self.map
.shrink_to_fit()
255 /// An iterator visiting all elements in arbitrary order.
256 /// Iterator element type is &'a T.
261 /// use std::collections::HashSet;
262 /// let mut set = HashSet::new();
266 /// // Will print in an arbitrary order.
267 /// for x in set.iter() {
268 /// println!("{}", x);
271 #[stable(feature = "rust1", since = "1.0.0")]
272 pub fn iter(&self) -> Iter
<T
> {
273 Iter { iter: self.map.keys() }
276 /// Visit the values representing the difference.
281 /// use std::collections::HashSet;
282 /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
283 /// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect();
285 /// // Can be seen as `a - b`.
286 /// for x in a.difference(&b) {
287 /// println!("{}", x); // Print 1
290 /// let diff: HashSet<_> = a.difference(&b).cloned().collect();
291 /// assert_eq!(diff, [1].iter().cloned().collect());
293 /// // Note that difference is not symmetric,
294 /// // and `b - a` means something else:
295 /// let diff: HashSet<_> = b.difference(&a).cloned().collect();
296 /// assert_eq!(diff, [4].iter().cloned().collect());
298 #[stable(feature = "rust1", since = "1.0.0")]
299 pub fn difference
<'a
>(&'a
self, other
: &'a HashSet
<T
, S
>) -> Difference
<'a
, T
, S
> {
306 /// Visit the values representing the symmetric difference.
311 /// use std::collections::HashSet;
312 /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
313 /// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect();
315 /// // Print 1, 4 in arbitrary order.
316 /// for x in a.symmetric_difference(&b) {
317 /// println!("{}", x);
320 /// let diff1: HashSet<_> = a.symmetric_difference(&b).cloned().collect();
321 /// let diff2: HashSet<_> = b.symmetric_difference(&a).cloned().collect();
323 /// assert_eq!(diff1, diff2);
324 /// assert_eq!(diff1, [1, 4].iter().cloned().collect());
326 #[stable(feature = "rust1", since = "1.0.0")]
327 pub fn symmetric_difference
<'a
>(&'a
self, other
: &'a HashSet
<T
, S
>)
328 -> SymmetricDifference
<'a
, T
, S
> {
329 SymmetricDifference { iter: self.difference(other).chain(other.difference(self)) }
332 /// Visit the values representing the intersection.
337 /// use std::collections::HashSet;
338 /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
339 /// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect();
341 /// // Print 2, 3 in arbitrary order.
342 /// for x in a.intersection(&b) {
343 /// println!("{}", x);
346 /// let diff: HashSet<_> = a.intersection(&b).cloned().collect();
347 /// assert_eq!(diff, [2, 3].iter().cloned().collect());
349 #[stable(feature = "rust1", since = "1.0.0")]
350 pub fn intersection
<'a
>(&'a
self, other
: &'a HashSet
<T
, S
>) -> Intersection
<'a
, T
, S
> {
357 /// Visit the values representing the union.
362 /// use std::collections::HashSet;
363 /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
364 /// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect();
366 /// // Print 1, 2, 3, 4 in arbitrary order.
367 /// for x in a.union(&b) {
368 /// println!("{}", x);
371 /// let diff: HashSet<_> = a.union(&b).cloned().collect();
372 /// assert_eq!(diff, [1, 2, 3, 4].iter().cloned().collect());
374 #[stable(feature = "rust1", since = "1.0.0")]
375 pub fn union<'a
>(&'a
self, other
: &'a HashSet
<T
, S
>) -> Union
<'a
, T
, S
> {
376 Union { iter: self.iter().chain(other.difference(self)) }
379 /// Returns the number of elements in the set.
384 /// use std::collections::HashSet;
386 /// let mut v = HashSet::new();
387 /// assert_eq!(v.len(), 0);
389 /// assert_eq!(v.len(), 1);
391 #[stable(feature = "rust1", since = "1.0.0")]
392 pub fn len(&self) -> usize { self.map.len() }
394 /// Returns true if the set contains no elements.
399 /// use std::collections::HashSet;
401 /// let mut v = HashSet::new();
402 /// assert!(v.is_empty());
404 /// assert!(!v.is_empty());
406 #[stable(feature = "rust1", since = "1.0.0")]
407 pub fn is_empty(&self) -> bool { self.map.is_empty() }
409 /// Clears the set, returning all elements in an iterator.
411 #[unstable(feature = "drain",
412 reason
= "matches collection reform specification, waiting for dust to settle")]
413 pub fn drain(&mut self) -> Drain
<T
> {
414 fn first
<A
, B
>((a
, _
): (A
, B
)) -> A { a }
415 let first
: fn((T
, ())) -> T
= first
; // coerce to fn pointer
417 Drain { iter: self.map.drain().map(first) }
420 /// Clears the set, removing all values.
425 /// use std::collections::HashSet;
427 /// let mut v = HashSet::new();
430 /// assert!(v.is_empty());
432 #[stable(feature = "rust1", since = "1.0.0")]
433 pub fn clear(&mut self) { self.map.clear() }
435 /// Returns `true` if the set contains a value.
437 /// The value may be any borrowed form of the set's value type, but
438 /// `Hash` and `Eq` on the borrowed form *must* match those for
444 /// use std::collections::HashSet;
446 /// let set: HashSet<_> = [1, 2, 3].iter().cloned().collect();
447 /// assert_eq!(set.contains(&1), true);
448 /// assert_eq!(set.contains(&4), false);
450 #[stable(feature = "rust1", since = "1.0.0")]
451 pub fn contains
<Q
: ?Sized
>(&self, value
: &Q
) -> bool
452 where T
: Borrow
<Q
>, Q
: Hash
+ Eq
454 self.map
.contains_key(value
)
457 /// Returns `true` if the set has no elements in common with `other`.
458 /// This is equivalent to checking for an empty intersection.
463 /// use std::collections::HashSet;
465 /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
466 /// let mut b = HashSet::new();
468 /// assert_eq!(a.is_disjoint(&b), true);
470 /// assert_eq!(a.is_disjoint(&b), true);
472 /// assert_eq!(a.is_disjoint(&b), false);
474 #[stable(feature = "rust1", since = "1.0.0")]
475 pub fn is_disjoint(&self, other
: &HashSet
<T
, S
>) -> bool
{
476 self.iter().all(|v
| !other
.contains(v
))
479 /// Returns `true` if the set is a subset of another.
484 /// use std::collections::HashSet;
486 /// let sup: HashSet<_> = [1, 2, 3].iter().cloned().collect();
487 /// let mut set = HashSet::new();
489 /// assert_eq!(set.is_subset(&sup), true);
491 /// assert_eq!(set.is_subset(&sup), true);
493 /// assert_eq!(set.is_subset(&sup), false);
495 #[stable(feature = "rust1", since = "1.0.0")]
496 pub fn is_subset(&self, other
: &HashSet
<T
, S
>) -> bool
{
497 self.iter().all(|v
| other
.contains(v
))
500 /// Returns `true` if the set is a superset of another.
505 /// use std::collections::HashSet;
507 /// let sub: HashSet<_> = [1, 2].iter().cloned().collect();
508 /// let mut set = HashSet::new();
510 /// assert_eq!(set.is_superset(&sub), false);
514 /// assert_eq!(set.is_superset(&sub), false);
517 /// assert_eq!(set.is_superset(&sub), true);
520 #[stable(feature = "rust1", since = "1.0.0")]
521 pub fn is_superset(&self, other
: &HashSet
<T
, S
>) -> bool
{
522 other
.is_subset(self)
525 /// Adds a value to the set. Returns `true` if the value was not already
526 /// present in the set.
531 /// use std::collections::HashSet;
533 /// let mut set = HashSet::new();
535 /// assert_eq!(set.insert(2), true);
536 /// assert_eq!(set.insert(2), false);
537 /// assert_eq!(set.len(), 1);
539 #[stable(feature = "rust1", since = "1.0.0")]
540 pub fn insert(&mut self, value
: T
) -> bool { self.map.insert(value, ()).is_none() }
542 /// Removes a value from the set. Returns `true` if the value was
543 /// present in the set.
545 /// The value may be any borrowed form of the set's value type, but
546 /// `Hash` and `Eq` on the borrowed form *must* match those for
552 /// use std::collections::HashSet;
554 /// let mut set = HashSet::new();
557 /// assert_eq!(set.remove(&2), true);
558 /// assert_eq!(set.remove(&2), false);
560 #[stable(feature = "rust1", since = "1.0.0")]
561 pub fn remove
<Q
: ?Sized
>(&mut self, value
: &Q
) -> bool
562 where T
: Borrow
<Q
>, Q
: Hash
+ Eq
564 self.map
.remove(value
).is_some()
568 #[stable(feature = "rust1", since = "1.0.0")]
569 impl<T
, S
> PartialEq
for HashSet
<T
, S
>
570 where T
: Eq
+ Hash
, S
: HashState
572 fn eq(&self, other
: &HashSet
<T
, S
>) -> bool
{
573 if self.len() != other
.len() { return false; }
575 self.iter().all(|key
| other
.contains(key
))
579 #[stable(feature = "rust1", since = "1.0.0")]
580 impl<T
, S
> Eq
for HashSet
<T
, S
>
581 where T
: Eq
+ Hash
, S
: HashState
584 #[stable(feature = "rust1", since = "1.0.0")]
585 impl<T
, S
> fmt
::Debug
for HashSet
<T
, S
>
586 where T
: Eq
+ Hash
+ fmt
::Debug
,
589 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
590 f
.debug_set().entries(self.iter()).finish()
594 #[stable(feature = "rust1", since = "1.0.0")]
595 impl<T
, S
> FromIterator
<T
> for HashSet
<T
, S
>
597 S
: HashState
+ Default
,
599 fn from_iter
<I
: IntoIterator
<Item
=T
>>(iterable
: I
) -> HashSet
<T
, S
> {
600 let iter
= iterable
.into_iter();
601 let lower
= iter
.size_hint().0;
602 let mut set
= HashSet
::with_capacity_and_hash_state(lower
, Default
::default());
608 #[stable(feature = "rust1", since = "1.0.0")]
609 impl<T
, S
> Extend
<T
> for HashSet
<T
, S
>
613 fn extend
<I
: IntoIterator
<Item
=T
>>(&mut self, iter
: I
) {
620 #[stable(feature = "rust1", since = "1.0.0")]
621 impl<T
, S
> Default
for HashSet
<T
, S
>
623 S
: HashState
+ Default
,
625 #[stable(feature = "rust1", since = "1.0.0")]
626 fn default() -> HashSet
<T
, S
> {
627 HashSet
::with_hash_state(Default
::default())
631 #[stable(feature = "rust1", since = "1.0.0")]
632 impl<'a
, 'b
, T
, S
> BitOr
<&'b HashSet
<T
, S
>> for &'a HashSet
<T
, S
>
633 where T
: Eq
+ Hash
+ Clone
,
634 S
: HashState
+ Default
,
636 type Output
= HashSet
<T
, S
>;
638 /// Returns the union of `self` and `rhs` as a new `HashSet<T, S>`.
643 /// use std::collections::HashSet;
645 /// let a: HashSet<_> = vec![1, 2, 3].into_iter().collect();
646 /// let b: HashSet<_> = vec![3, 4, 5].into_iter().collect();
648 /// let set = &a | &b;
651 /// let expected = [1, 2, 3, 4, 5];
653 /// assert!(expected.contains(x));
656 /// assert_eq!(i, expected.len());
658 fn bitor(self, rhs
: &HashSet
<T
, S
>) -> HashSet
<T
, S
> {
659 self.union(rhs
).cloned().collect()
663 #[stable(feature = "rust1", since = "1.0.0")]
664 impl<'a
, 'b
, T
, S
> BitAnd
<&'b HashSet
<T
, S
>> for &'a HashSet
<T
, S
>
665 where T
: Eq
+ Hash
+ Clone
,
666 S
: HashState
+ Default
,
668 type Output
= HashSet
<T
, S
>;
670 /// Returns the intersection of `self` and `rhs` as a new `HashSet<T, S>`.
675 /// use std::collections::HashSet;
677 /// let a: HashSet<_> = vec![1, 2, 3].into_iter().collect();
678 /// let b: HashSet<_> = vec![2, 3, 4].into_iter().collect();
680 /// let set = &a & &b;
683 /// let expected = [2, 3];
685 /// assert!(expected.contains(x));
688 /// assert_eq!(i, expected.len());
690 fn bitand(self, rhs
: &HashSet
<T
, S
>) -> HashSet
<T
, S
> {
691 self.intersection(rhs
).cloned().collect()
695 #[stable(feature = "rust1", since = "1.0.0")]
696 impl<'a
, 'b
, T
, S
> BitXor
<&'b HashSet
<T
, S
>> for &'a HashSet
<T
, S
>
697 where T
: Eq
+ Hash
+ Clone
,
698 S
: HashState
+ Default
,
700 type Output
= HashSet
<T
, S
>;
702 /// Returns the symmetric difference of `self` and `rhs` as a new `HashSet<T, S>`.
707 /// use std::collections::HashSet;
709 /// let a: HashSet<_> = vec![1, 2, 3].into_iter().collect();
710 /// let b: HashSet<_> = vec![3, 4, 5].into_iter().collect();
712 /// let set = &a ^ &b;
715 /// let expected = [1, 2, 4, 5];
717 /// assert!(expected.contains(x));
720 /// assert_eq!(i, expected.len());
722 fn bitxor(self, rhs
: &HashSet
<T
, S
>) -> HashSet
<T
, S
> {
723 self.symmetric_difference(rhs
).cloned().collect()
727 #[stable(feature = "rust1", since = "1.0.0")]
728 impl<'a
, 'b
, T
, S
> Sub
<&'b HashSet
<T
, S
>> for &'a HashSet
<T
, S
>
729 where T
: Eq
+ Hash
+ Clone
,
730 S
: HashState
+ Default
,
732 type Output
= HashSet
<T
, S
>;
734 /// Returns the difference of `self` and `rhs` as a new `HashSet<T, S>`.
739 /// use std::collections::HashSet;
741 /// let a: HashSet<_> = vec![1, 2, 3].into_iter().collect();
742 /// let b: HashSet<_> = vec![3, 4, 5].into_iter().collect();
744 /// let set = &a - &b;
747 /// let expected = [1, 2];
749 /// assert!(expected.contains(x));
752 /// assert_eq!(i, expected.len());
754 fn sub(self, rhs
: &HashSet
<T
, S
>) -> HashSet
<T
, S
> {
755 self.difference(rhs
).cloned().collect()
760 #[stable(feature = "rust1", since = "1.0.0")]
761 pub struct Iter
<'a
, K
: 'a
> {
762 iter
: Keys
<'a
, K
, ()>
765 /// HashSet move iterator
766 #[stable(feature = "rust1", since = "1.0.0")]
767 pub struct IntoIter
<K
> {
768 iter
: Map
<map
::IntoIter
<K
, ()>, fn((K
, ())) -> K
>
771 /// HashSet drain iterator
772 #[stable(feature = "rust1", since = "1.0.0")]
773 pub struct Drain
<'a
, K
: 'a
> {
774 iter
: Map
<map
::Drain
<'a
, K
, ()>, fn((K
, ())) -> K
>,
777 /// Intersection iterator
778 #[stable(feature = "rust1", since = "1.0.0")]
779 pub struct Intersection
<'a
, T
: 'a
, S
: 'a
> {
780 // iterator of the first set
783 other
: &'a HashSet
<T
, S
>,
786 /// Difference iterator
787 #[stable(feature = "rust1", since = "1.0.0")]
788 pub struct Difference
<'a
, T
: 'a
, S
: 'a
> {
789 // iterator of the first set
792 other
: &'a HashSet
<T
, S
>,
795 /// Symmetric difference iterator.
796 #[stable(feature = "rust1", since = "1.0.0")]
797 pub struct SymmetricDifference
<'a
, T
: 'a
, S
: 'a
> {
798 iter
: Chain
<Difference
<'a
, T
, S
>, Difference
<'a
, T
, S
>>
801 /// Set union iterator.
802 #[stable(feature = "rust1", since = "1.0.0")]
803 pub struct Union
<'a
, T
: 'a
, S
: 'a
> {
804 iter
: Chain
<Iter
<'a
, T
>, Difference
<'a
, T
, S
>>
807 #[stable(feature = "rust1", since = "1.0.0")]
808 impl<'a
, T
, S
> IntoIterator
for &'a HashSet
<T
, S
>
809 where T
: Eq
+ Hash
, S
: HashState
812 type IntoIter
= Iter
<'a
, T
>;
814 fn into_iter(self) -> Iter
<'a
, T
> {
819 #[stable(feature = "rust1", since = "1.0.0")]
820 impl<T
, S
> IntoIterator
for HashSet
<T
, S
>
825 type IntoIter
= IntoIter
<T
>;
827 /// Creates a consuming iterator, that is, one that moves each value out
828 /// of the set in arbitrary order. The set cannot be used after calling
834 /// use std::collections::HashSet;
835 /// let mut set = HashSet::new();
836 /// set.insert("a".to_string());
837 /// set.insert("b".to_string());
839 /// // Not possible to collect to a Vec<String> with a regular `.iter()`.
840 /// let v: Vec<String> = set.into_iter().collect();
842 /// // Will print in an arbitrary order.
844 /// println!("{}", x);
847 fn into_iter(self) -> IntoIter
<T
> {
848 fn first
<A
, B
>((a
, _
): (A
, B
)) -> A { a }
849 let first
: fn((T
, ())) -> T
= first
;
851 IntoIter { iter: self.map.into_iter().map(first) }
855 impl<'a
, K
> Clone
for Iter
<'a
, K
> {
856 fn clone(&self) -> Iter
<'a
, K
> { Iter { iter: self.iter.clone() }
}
858 #[stable(feature = "rust1", since = "1.0.0")]
859 impl<'a
, K
> Iterator
for Iter
<'a
, K
> {
862 fn next(&mut self) -> Option
<&'a K
> { self.iter.next() }
863 fn size_hint(&self) -> (usize, Option
<usize>) { self.iter.size_hint() }
865 #[stable(feature = "rust1", since = "1.0.0")]
866 impl<'a
, K
> ExactSizeIterator
for Iter
<'a
, K
> {
867 fn len(&self) -> usize { self.iter.len() }
870 #[stable(feature = "rust1", since = "1.0.0")]
871 impl<K
> Iterator
for IntoIter
<K
> {
874 fn next(&mut self) -> Option
<K
> { self.iter.next() }
875 fn size_hint(&self) -> (usize, Option
<usize>) { self.iter.size_hint() }
877 #[stable(feature = "rust1", since = "1.0.0")]
878 impl<K
> ExactSizeIterator
for IntoIter
<K
> {
879 fn len(&self) -> usize { self.iter.len() }
882 #[stable(feature = "rust1", since = "1.0.0")]
883 impl<'a
, K
> Iterator
for Drain
<'a
, K
> {
886 fn next(&mut self) -> Option
<K
> { self.iter.next() }
887 fn size_hint(&self) -> (usize, Option
<usize>) { self.iter.size_hint() }
889 #[stable(feature = "rust1", since = "1.0.0")]
890 impl<'a
, K
> ExactSizeIterator
for Drain
<'a
, K
> {
891 fn len(&self) -> usize { self.iter.len() }
894 impl<'a
, T
, S
> Clone
for Intersection
<'a
, T
, S
> {
895 fn clone(&self) -> Intersection
<'a
, T
, S
> {
896 Intersection { iter: self.iter.clone(), ..*self }
900 #[stable(feature = "rust1", since = "1.0.0")]
901 impl<'a
, T
, S
> Iterator
for Intersection
<'a
, T
, S
>
902 where T
: Eq
+ Hash
, S
: HashState
906 fn next(&mut self) -> Option
<&'a T
> {
908 match self.iter
.next() {
910 Some(elt
) => if self.other
.contains(elt
) {
917 fn size_hint(&self) -> (usize, Option
<usize>) {
918 let (_
, upper
) = self.iter
.size_hint();
923 impl<'a
, T
, S
> Clone
for Difference
<'a
, T
, S
> {
924 fn clone(&self) -> Difference
<'a
, T
, S
> {
925 Difference { iter: self.iter.clone(), ..*self }
929 #[stable(feature = "rust1", since = "1.0.0")]
930 impl<'a
, T
, S
> Iterator
for Difference
<'a
, T
, S
>
931 where T
: Eq
+ Hash
, S
: HashState
935 fn next(&mut self) -> Option
<&'a T
> {
937 match self.iter
.next() {
939 Some(elt
) => if !self.other
.contains(elt
) {
946 fn size_hint(&self) -> (usize, Option
<usize>) {
947 let (_
, upper
) = self.iter
.size_hint();
952 impl<'a
, T
, S
> Clone
for SymmetricDifference
<'a
, T
, S
> {
953 fn clone(&self) -> SymmetricDifference
<'a
, T
, S
> {
954 SymmetricDifference { iter: self.iter.clone() }
958 #[stable(feature = "rust1", since = "1.0.0")]
959 impl<'a
, T
, S
> Iterator
for SymmetricDifference
<'a
, T
, S
>
960 where T
: Eq
+ Hash
, S
: HashState
964 fn next(&mut self) -> Option
<&'a T
> { self.iter.next() }
965 fn size_hint(&self) -> (usize, Option
<usize>) { self.iter.size_hint() }
968 impl<'a
, T
, S
> Clone
for Union
<'a
, T
, S
> {
969 fn clone(&self) -> Union
<'a
, T
, S
> { Union { iter: self.iter.clone() }
}
972 #[stable(feature = "rust1", since = "1.0.0")]
973 impl<'a
, T
, S
> Iterator
for Union
<'a
, T
, S
>
974 where T
: Eq
+ Hash
, S
: HashState
978 fn next(&mut self) -> Option
<&'a T
> { self.iter.next() }
979 fn size_hint(&self) -> (usize, Option
<usize>) { self.iter.size_hint() }
990 let mut xs
= HashSet
::new();
991 let mut ys
= HashSet
::new();
992 assert
!(xs
.is_disjoint(&ys
));
993 assert
!(ys
.is_disjoint(&xs
));
994 assert
!(xs
.insert(5));
995 assert
!(ys
.insert(11));
996 assert
!(xs
.is_disjoint(&ys
));
997 assert
!(ys
.is_disjoint(&xs
));
998 assert
!(xs
.insert(7));
999 assert
!(xs
.insert(19));
1000 assert
!(xs
.insert(4));
1001 assert
!(ys
.insert(2));
1002 assert
!(ys
.insert(-11));
1003 assert
!(xs
.is_disjoint(&ys
));
1004 assert
!(ys
.is_disjoint(&xs
));
1005 assert
!(ys
.insert(7));
1006 assert
!(!xs
.is_disjoint(&ys
));
1007 assert
!(!ys
.is_disjoint(&xs
));
1011 fn test_subset_and_superset() {
1012 let mut a
= HashSet
::new();
1013 assert
!(a
.insert(0));
1014 assert
!(a
.insert(5));
1015 assert
!(a
.insert(11));
1016 assert
!(a
.insert(7));
1018 let mut b
= HashSet
::new();
1019 assert
!(b
.insert(0));
1020 assert
!(b
.insert(7));
1021 assert
!(b
.insert(19));
1022 assert
!(b
.insert(250));
1023 assert
!(b
.insert(11));
1024 assert
!(b
.insert(200));
1026 assert
!(!a
.is_subset(&b
));
1027 assert
!(!a
.is_superset(&b
));
1028 assert
!(!b
.is_subset(&a
));
1029 assert
!(!b
.is_superset(&a
));
1031 assert
!(b
.insert(5));
1033 assert
!(a
.is_subset(&b
));
1034 assert
!(!a
.is_superset(&b
));
1035 assert
!(!b
.is_subset(&a
));
1036 assert
!(b
.is_superset(&a
));
1041 let mut a
= HashSet
::new();
1043 assert
!(a
.insert(i
));
1045 let mut observed
: u32 = 0;
1047 observed
|= 1 << *k
;
1049 assert_eq
!(observed
, 0xFFFF_FFFF);
1053 fn test_intersection() {
1054 let mut a
= HashSet
::new();
1055 let mut b
= HashSet
::new();
1057 assert
!(a
.insert(11));
1058 assert
!(a
.insert(1));
1059 assert
!(a
.insert(3));
1060 assert
!(a
.insert(77));
1061 assert
!(a
.insert(103));
1062 assert
!(a
.insert(5));
1063 assert
!(a
.insert(-5));
1065 assert
!(b
.insert(2));
1066 assert
!(b
.insert(11));
1067 assert
!(b
.insert(77));
1068 assert
!(b
.insert(-9));
1069 assert
!(b
.insert(-42));
1070 assert
!(b
.insert(5));
1071 assert
!(b
.insert(3));
1074 let expected
= [3, 5, 11, 77];
1075 for x
in a
.intersection(&b
) {
1076 assert
!(expected
.contains(x
));
1079 assert_eq
!(i
, expected
.len());
1083 fn test_difference() {
1084 let mut a
= HashSet
::new();
1085 let mut b
= HashSet
::new();
1087 assert
!(a
.insert(1));
1088 assert
!(a
.insert(3));
1089 assert
!(a
.insert(5));
1090 assert
!(a
.insert(9));
1091 assert
!(a
.insert(11));
1093 assert
!(b
.insert(3));
1094 assert
!(b
.insert(9));
1097 let expected
= [1, 5, 11];
1098 for x
in a
.difference(&b
) {
1099 assert
!(expected
.contains(x
));
1102 assert_eq
!(i
, expected
.len());
1106 fn test_symmetric_difference() {
1107 let mut a
= HashSet
::new();
1108 let mut b
= HashSet
::new();
1110 assert
!(a
.insert(1));
1111 assert
!(a
.insert(3));
1112 assert
!(a
.insert(5));
1113 assert
!(a
.insert(9));
1114 assert
!(a
.insert(11));
1116 assert
!(b
.insert(-2));
1117 assert
!(b
.insert(3));
1118 assert
!(b
.insert(9));
1119 assert
!(b
.insert(14));
1120 assert
!(b
.insert(22));
1123 let expected
= [-2, 1, 5, 11, 14, 22];
1124 for x
in a
.symmetric_difference(&b
) {
1125 assert
!(expected
.contains(x
));
1128 assert_eq
!(i
, expected
.len());
1133 let mut a
= HashSet
::new();
1134 let mut b
= HashSet
::new();
1136 assert
!(a
.insert(1));
1137 assert
!(a
.insert(3));
1138 assert
!(a
.insert(5));
1139 assert
!(a
.insert(9));
1140 assert
!(a
.insert(11));
1141 assert
!(a
.insert(16));
1142 assert
!(a
.insert(19));
1143 assert
!(a
.insert(24));
1145 assert
!(b
.insert(-2));
1146 assert
!(b
.insert(1));
1147 assert
!(b
.insert(5));
1148 assert
!(b
.insert(9));
1149 assert
!(b
.insert(13));
1150 assert
!(b
.insert(19));
1153 let expected
= [-2, 1, 3, 5, 9, 11, 13, 16, 19, 24];
1154 for x
in a
.union(&b
) {
1155 assert
!(expected
.contains(x
));
1158 assert_eq
!(i
, expected
.len());
1162 fn test_from_iter() {
1163 let xs
= [1, 2, 3, 4, 5, 6, 7, 8, 9];
1165 let set
: HashSet
<_
> = xs
.iter().cloned().collect();
1168 assert
!(set
.contains(x
));
1173 fn test_move_iter() {
1175 let mut hs
= HashSet
::new();
1183 let v
= hs
.into_iter().collect
::<Vec
<char>>();
1184 assert
!(v
== ['a'
, 'b'
] || v
== ['b'
, 'a'
]);
1189 // These constants once happened to expose a bug in insert().
1190 // I'm keeping them around to prevent a regression.
1191 let mut s1
= HashSet
::new();
1197 let mut s2
= HashSet
::new();
1211 let mut set
= HashSet
::new();
1212 let empty
= HashSet
::<i32>::new();
1217 let set_str
= format
!("{:?}", set
);
1219 assert
!(set_str
== "{1, 2}" || set_str
== "{2, 1}");
1220 assert_eq
!(format
!("{:?}", empty
), "{}");
1224 fn test_trivial_drain() {
1225 let mut s
= HashSet
::<i32>::new();
1226 for _
in s
.drain() {}
1227 assert
!(s
.is_empty());
1230 let mut s
= HashSet
::<i32>::new();
1232 assert
!(s
.is_empty());
1237 let mut s
: HashSet
<_
> = (1..100).collect();
1239 // try this a bunch of times to make sure we don't screw up internal state.
1241 assert_eq
!(s
.len(), 99);
1245 let mut d
= s
.drain();
1246 for (i
, x
) in d
.by_ref().take(50).enumerate() {
1250 assert_eq
!(last_i
, 49);
1253 for _
in &s { panic!("s should be empty!"); }
1255 // reset to try again.