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 hash::{Hash, BuildHasher};
14 use iter::{Map, Chain, FromIterator};
15 use ops::{BitOr, BitAnd, BitXor, Sub};
18 use super::map::{self, HashMap, Keys, RandomState};
20 const INITIAL_CAPACITY: usize = 32;
22 // Future Optimization (FIXME!)
23 // =============================
25 // Iteration over zero sized values is a noop. There is no need
26 // for `bucket.val` in the case of HashSet. I suppose we would need HKT
27 // to get rid of it properly.
29 /// An implementation of a hash set using the underlying representation of a
30 /// HashMap where the value is ().
32 /// As with the `HashMap` type, a `HashSet` requires that the elements
33 /// implement the `Eq` and `Hash` traits. This can frequently be achieved by
34 /// using `#[derive(PartialEq, Eq, Hash)]`. If you implement these yourself,
35 /// it is important that the following property holds:
38 /// k1 == k2 -> hash(k1) == hash(k2)
41 /// In other words, if two keys are equal, their hashes must be equal.
44 /// It is a logic error for an item to be modified in such a way that the
45 /// item's hash, as determined by the `Hash` trait, or its equality, as
46 /// determined by the `Eq` trait, changes while it is in the set. This is
47 /// normally only possible through `Cell`, `RefCell`, global state, I/O, or
53 /// use std::collections::HashSet;
54 /// // Type inference lets us omit an explicit type signature (which
55 /// // would be `HashSet<&str>` in this example).
56 /// let mut books = HashSet::new();
58 /// // Add some books.
59 /// books.insert("A Dance With Dragons");
60 /// books.insert("To Kill a Mockingbird");
61 /// books.insert("The Odyssey");
62 /// books.insert("The Great Gatsby");
64 /// // Check for a specific one.
65 /// if !books.contains("The Winds of Winter") {
66 /// println!("We have {} books, but The Winds of Winter ain't one.",
71 /// books.remove("The Odyssey");
73 /// // Iterate over everything.
74 /// for book in &books {
75 /// println!("{}", book);
79 /// The easiest way to use `HashSet` with a custom type is to derive
80 /// `Eq` and `Hash`. We must also derive `PartialEq`, this will in the
81 /// future be implied by `Eq`.
84 /// use std::collections::HashSet;
85 /// #[derive(Hash, Eq, PartialEq, Debug)]
86 /// struct Viking<'a> {
91 /// let mut vikings = HashSet::new();
93 /// vikings.insert(Viking { name: "Einar", power: 9 });
94 /// vikings.insert(Viking { name: "Einar", power: 9 });
95 /// vikings.insert(Viking { name: "Olaf", power: 4 });
96 /// vikings.insert(Viking { name: "Harald", power: 8 });
98 /// // Use derived implementation to print the vikings.
99 /// for x in &vikings {
100 /// println!("{:?}", x);
104 #[stable(feature = "rust1", since = "1.0.0")]
105 pub struct HashSet<T, S = RandomState> {
106 map: HashMap<T, (), S>
109 impl<T: Hash + Eq> HashSet<T, RandomState> {
110 /// Creates an empty HashSet.
115 /// use std::collections::HashSet;
116 /// let mut set: HashSet<i32> = HashSet::new();
119 #[stable(feature = "rust1", since = "1.0.0")]
120 pub fn new() -> HashSet<T, RandomState> {
121 HashSet::with_capacity(INITIAL_CAPACITY)
124 /// Creates an empty HashSet with space for at least `n` elements in
130 /// use std::collections::HashSet;
131 /// let mut set: HashSet<i32> = HashSet::with_capacity(10);
134 #[stable(feature = "rust1", since = "1.0.0")]
135 pub fn with_capacity(capacity: usize) -> HashSet<T, RandomState> {
136 HashSet { map: HashMap::with_capacity(capacity) }
140 impl<T, S> HashSet<T, S>
141 where T: Eq + Hash, S: BuildHasher
143 /// Creates a new empty hash set which will use the given hasher to hash
146 /// The hash set is also created with the default initial capacity.
148 /// Warning: `hasher` is normally randomly generated, and
149 /// is designed to allow `HashSet`s to be resistant to attacks that
150 /// cause many collisions and very poor performance. Setting it
151 /// manually using this function can expose a DoS attack vector.
156 /// use std::collections::HashSet;
157 /// use std::collections::hash_map::RandomState;
159 /// let s = RandomState::new();
160 /// let mut set = HashSet::with_hasher(s);
164 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
165 pub fn with_hasher(hasher: S) -> HashSet<T, S> {
166 HashSet::with_capacity_and_hasher(INITIAL_CAPACITY, hasher)
169 /// Creates an empty HashSet with space for at least `capacity`
170 /// elements in the hash table, using `hasher` to hash the keys.
172 /// Warning: `hasher` is normally randomly generated, and
173 /// is designed to allow `HashSet`s to be resistant to attacks that
174 /// cause many collisions and very poor performance. Setting it
175 /// manually using this function can expose a DoS attack vector.
180 /// use std::collections::HashSet;
181 /// use std::collections::hash_map::RandomState;
183 /// let s = RandomState::new();
184 /// let mut set = HashSet::with_capacity_and_hasher(10, s);
188 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
189 pub fn with_capacity_and_hasher(capacity: usize, hasher: S)
192 map: HashMap::with_capacity_and_hasher(capacity, hasher),
196 /// Deprecated, renamed to `with_hasher`
198 #[unstable(feature = "hashmap_hasher", reason = "hasher stuff is unclear",
200 #[rustc_deprecated(since = "1.7.0", reason = "renamed to with_hasher")]
201 pub fn with_hash_state(hash_state: S) -> HashSet<T, S> {
202 HashSet::with_hasher(hash_state)
205 /// Deprecated, renamed to `with_capacity_and_hasher`
207 #[unstable(feature = "hashmap_hasher", reason = "hasher stuff is unclear",
209 #[rustc_deprecated(since = "1.7.0",
210 reason = "renamed to with_capacity_and_hasher")]
211 pub fn with_capacity_and_hash_state(capacity: usize, hash_state: S)
213 HashSet::with_capacity_and_hasher(capacity, hash_state)
216 /// Returns the number of elements the set can hold without reallocating.
221 /// use std::collections::HashSet;
222 /// let set: HashSet<i32> = HashSet::with_capacity(100);
223 /// assert!(set.capacity() >= 100);
226 #[stable(feature = "rust1", since = "1.0.0")]
227 pub fn capacity(&self) -> usize {
231 /// Reserves capacity for at least `additional` more elements to be inserted
232 /// in the `HashSet`. The collection may reserve more space to avoid
233 /// frequent reallocations.
237 /// Panics if the new allocation size overflows `usize`.
242 /// use std::collections::HashSet;
243 /// let mut set: HashSet<i32> = HashSet::new();
246 #[stable(feature = "rust1", since = "1.0.0")]
247 pub fn reserve(&mut self, additional: usize) {
248 self.map.reserve(additional)
251 /// Shrinks the capacity of the set as much as possible. It will drop
252 /// down as much as possible while maintaining the internal rules
253 /// and possibly leaving some space in accordance with the resize policy.
258 /// use std::collections::HashSet;
260 /// let mut set = HashSet::with_capacity(100);
263 /// assert!(set.capacity() >= 100);
264 /// set.shrink_to_fit();
265 /// assert!(set.capacity() >= 2);
267 #[stable(feature = "rust1", since = "1.0.0")]
268 pub fn shrink_to_fit(&mut self) {
269 self.map.shrink_to_fit()
272 /// An iterator visiting all elements in arbitrary order.
273 /// Iterator element type is &'a T.
278 /// use std::collections::HashSet;
279 /// let mut set = HashSet::new();
283 /// // Will print in an arbitrary order.
284 /// for x in set.iter() {
285 /// println!("{}", x);
288 #[stable(feature = "rust1", since = "1.0.0")]
289 pub fn iter(&self) -> Iter<T> {
290 Iter { iter: self.map.keys() }
293 /// Visit the values representing the difference.
298 /// use std::collections::HashSet;
299 /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
300 /// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect();
302 /// // Can be seen as `a - b`.
303 /// for x in a.difference(&b) {
304 /// println!("{}", x); // Print 1
307 /// let diff: HashSet<_> = a.difference(&b).cloned().collect();
308 /// assert_eq!(diff, [1].iter().cloned().collect());
310 /// // Note that difference is not symmetric,
311 /// // and `b - a` means something else:
312 /// let diff: HashSet<_> = b.difference(&a).cloned().collect();
313 /// assert_eq!(diff, [4].iter().cloned().collect());
315 #[stable(feature = "rust1", since = "1.0.0")]
316 pub fn difference<'a>(&'a self, other: &'a HashSet<T, S>) -> Difference<'a, T, S> {
323 /// Visit the values representing the symmetric difference.
328 /// use std::collections::HashSet;
329 /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
330 /// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect();
332 /// // Print 1, 4 in arbitrary order.
333 /// for x in a.symmetric_difference(&b) {
334 /// println!("{}", x);
337 /// let diff1: HashSet<_> = a.symmetric_difference(&b).cloned().collect();
338 /// let diff2: HashSet<_> = b.symmetric_difference(&a).cloned().collect();
340 /// assert_eq!(diff1, diff2);
341 /// assert_eq!(diff1, [1, 4].iter().cloned().collect());
343 #[stable(feature = "rust1", since = "1.0.0")]
344 pub fn symmetric_difference<'a>(&'a self, other: &'a HashSet<T, S>)
345 -> SymmetricDifference<'a, T, S> {
346 SymmetricDifference { iter: self.difference(other).chain(other.difference(self)) }
349 /// Visit the values representing the intersection.
354 /// use std::collections::HashSet;
355 /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
356 /// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect();
358 /// // Print 2, 3 in arbitrary order.
359 /// for x in a.intersection(&b) {
360 /// println!("{}", x);
363 /// let intersection: HashSet<_> = a.intersection(&b).cloned().collect();
364 /// assert_eq!(intersection, [2, 3].iter().cloned().collect());
366 #[stable(feature = "rust1", since = "1.0.0")]
367 pub fn intersection<'a>(&'a self, other: &'a HashSet<T, S>) -> Intersection<'a, T, S> {
374 /// Visit the values representing the union.
379 /// use std::collections::HashSet;
380 /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
381 /// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect();
383 /// // Print 1, 2, 3, 4 in arbitrary order.
384 /// for x in a.union(&b) {
385 /// println!("{}", x);
388 /// let union: HashSet<_> = a.union(&b).cloned().collect();
389 /// assert_eq!(union, [1, 2, 3, 4].iter().cloned().collect());
391 #[stable(feature = "rust1", since = "1.0.0")]
392 pub fn union<'a>(&'a self, other: &'a HashSet<T, S>) -> Union<'a, T, S> {
393 Union { iter: self.iter().chain(other.difference(self)) }
396 /// Returns the number of elements in the set.
401 /// use std::collections::HashSet;
403 /// let mut v = HashSet::new();
404 /// assert_eq!(v.len(), 0);
406 /// assert_eq!(v.len(), 1);
408 #[stable(feature = "rust1", since = "1.0.0")]
409 pub fn len(&self) -> usize { self.map.len() }
411 /// Returns true if the set contains no elements.
416 /// use std::collections::HashSet;
418 /// let mut v = HashSet::new();
419 /// assert!(v.is_empty());
421 /// assert!(!v.is_empty());
423 #[stable(feature = "rust1", since = "1.0.0")]
424 pub fn is_empty(&self) -> bool { self.map.is_empty() }
426 /// Clears the set, returning all elements in an iterator.
428 #[stable(feature = "drain", since = "1.6.0")]
429 pub fn drain(&mut self) -> Drain<T> {
430 fn first<A, B>((a, _): (A, B)) -> A { a }
431 let first: fn((T, ())) -> T = first; // coerce to fn pointer
433 Drain { iter: self.map.drain().map(first) }
436 /// Clears the set, removing all values.
441 /// use std::collections::HashSet;
443 /// let mut v = HashSet::new();
446 /// assert!(v.is_empty());
448 #[stable(feature = "rust1", since = "1.0.0")]
449 pub fn clear(&mut self) { self.map.clear() }
451 /// Returns `true` if the set contains a value.
453 /// The value may be any borrowed form of the set's value type, but
454 /// `Hash` and `Eq` on the borrowed form *must* match those for
460 /// use std::collections::HashSet;
462 /// let set: HashSet<_> = [1, 2, 3].iter().cloned().collect();
463 /// assert_eq!(set.contains(&1), true);
464 /// assert_eq!(set.contains(&4), false);
466 #[stable(feature = "rust1", since = "1.0.0")]
467 pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool
468 where T: Borrow<Q>, Q: Hash + Eq
470 self.map.contains_key(value)
473 /// Returns a reference to the value in the set, if any, that is equal to the given value.
475 /// The value may be any borrowed form of the set's value type, but
476 /// `Hash` and `Eq` on the borrowed form *must* match those for
478 #[unstable(feature = "set_recovery", issue = "28050")]
479 pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T>
480 where T: Borrow<Q>, Q: Hash + Eq
482 Recover::get(&self.map, value)
485 /// Returns `true` if the set has no elements in common with `other`.
486 /// This is equivalent to checking for an empty intersection.
491 /// use std::collections::HashSet;
493 /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
494 /// let mut b = HashSet::new();
496 /// assert_eq!(a.is_disjoint(&b), true);
498 /// assert_eq!(a.is_disjoint(&b), true);
500 /// assert_eq!(a.is_disjoint(&b), false);
502 #[stable(feature = "rust1", since = "1.0.0")]
503 pub fn is_disjoint(&self, other: &HashSet<T, S>) -> bool {
504 self.iter().all(|v| !other.contains(v))
507 /// Returns `true` if the set is a subset of another.
512 /// use std::collections::HashSet;
514 /// let sup: HashSet<_> = [1, 2, 3].iter().cloned().collect();
515 /// let mut set = HashSet::new();
517 /// assert_eq!(set.is_subset(&sup), true);
519 /// assert_eq!(set.is_subset(&sup), true);
521 /// assert_eq!(set.is_subset(&sup), false);
523 #[stable(feature = "rust1", since = "1.0.0")]
524 pub fn is_subset(&self, other: &HashSet<T, S>) -> bool {
525 self.iter().all(|v| other.contains(v))
528 /// Returns `true` if the set is a superset of another.
533 /// use std::collections::HashSet;
535 /// let sub: HashSet<_> = [1, 2].iter().cloned().collect();
536 /// let mut set = HashSet::new();
538 /// assert_eq!(set.is_superset(&sub), false);
542 /// assert_eq!(set.is_superset(&sub), false);
545 /// assert_eq!(set.is_superset(&sub), true);
548 #[stable(feature = "rust1", since = "1.0.0")]
549 pub fn is_superset(&self, other: &HashSet<T, S>) -> bool {
550 other.is_subset(self)
553 /// Adds a value to the set.
555 /// If the set did not have a value present, `true` is returned.
557 /// If the set did have this key present, `false` is returned.
562 /// use std::collections::HashSet;
564 /// let mut set = HashSet::new();
566 /// assert_eq!(set.insert(2), true);
567 /// assert_eq!(set.insert(2), false);
568 /// assert_eq!(set.len(), 1);
570 #[stable(feature = "rust1", since = "1.0.0")]
571 pub fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()).is_none() }
573 /// Adds a value to the set, replacing the existing value, if any, that is equal to the given
574 /// one. Returns the replaced value.
575 #[unstable(feature = "set_recovery", issue = "28050")]
576 pub fn replace(&mut self, value: T) -> Option<T> {
577 Recover::replace(&mut self.map, value)
580 /// Removes a value from the set. Returns `true` if the value was
581 /// present in the set.
583 /// The value may be any borrowed form of the set's value type, but
584 /// `Hash` and `Eq` on the borrowed form *must* match those for
590 /// use std::collections::HashSet;
592 /// let mut set = HashSet::new();
595 /// assert_eq!(set.remove(&2), true);
596 /// assert_eq!(set.remove(&2), false);
598 #[stable(feature = "rust1", since = "1.0.0")]
599 pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool
600 where T: Borrow<Q>, Q: Hash + Eq
602 self.map.remove(value).is_some()
605 /// Removes and returns the value in the set, if any, that is equal to the given one.
607 /// The value may be any borrowed form of the set's value type, but
608 /// `Hash` and `Eq` on the borrowed form *must* match those for
610 #[unstable(feature = "set_recovery", issue = "28050")]
611 pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T>
612 where T: Borrow<Q>, Q: Hash + Eq
614 Recover::take(&mut self.map, value)
618 #[stable(feature = "rust1", since = "1.0.0")]
619 impl<T, S> PartialEq for HashSet<T, S>
620 where T: Eq + Hash, S: BuildHasher
622 fn eq(&self, other: &HashSet<T, S>) -> bool {
623 if self.len() != other.len() { return false; }
625 self.iter().all(|key| other.contains(key))
629 #[stable(feature = "rust1", since = "1.0.0")]
630 impl<T, S> Eq for HashSet<T, S>
631 where T: Eq + Hash, S: BuildHasher
634 #[stable(feature = "rust1", since = "1.0.0")]
635 impl<T, S> fmt::Debug for HashSet<T, S>
636 where T: Eq + Hash + fmt::Debug,
639 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
640 f.debug_set().entries(self.iter()).finish()
644 #[stable(feature = "rust1", since = "1.0.0")]
645 impl<T, S> FromIterator<T> for HashSet<T, S>
647 S: BuildHasher + Default,
649 fn from_iter<I: IntoIterator<Item=T>>(iterable: I) -> HashSet<T, S> {
650 let iter = iterable.into_iter();
651 let lower = iter.size_hint().0;
652 let mut set = HashSet::with_capacity_and_hasher(lower, Default::default());
658 #[stable(feature = "rust1", since = "1.0.0")]
659 impl<T, S> Extend<T> for HashSet<T, S>
663 fn extend<I: IntoIterator<Item=T>>(&mut self, iter: I) {
670 #[stable(feature = "hash_extend_copy", since = "1.4.0")]
671 impl<'a, T, S> Extend<&'a T> for HashSet<T, S>
672 where T: 'a + Eq + Hash + Copy,
675 fn extend<I: IntoIterator<Item=&'a T>>(&mut self, iter: I) {
676 self.extend(iter.into_iter().cloned());
680 #[stable(feature = "rust1", since = "1.0.0")]
681 impl<T, S> Default for HashSet<T, S>
683 S: BuildHasher + Default,
685 fn default() -> HashSet<T, S> {
686 HashSet::with_hasher(Default::default())
690 #[stable(feature = "rust1", since = "1.0.0")]
691 impl<'a, 'b, T, S> BitOr<&'b HashSet<T, S>> for &'a HashSet<T, S>
692 where T: Eq + Hash + Clone,
693 S: BuildHasher + Default,
695 type Output = HashSet<T, S>;
697 /// Returns the union of `self` and `rhs` as a new `HashSet<T, S>`.
702 /// use std::collections::HashSet;
704 /// let a: HashSet<_> = vec![1, 2, 3].into_iter().collect();
705 /// let b: HashSet<_> = vec![3, 4, 5].into_iter().collect();
707 /// let set = &a | &b;
710 /// let expected = [1, 2, 3, 4, 5];
712 /// assert!(expected.contains(x));
715 /// assert_eq!(i, expected.len());
717 fn bitor(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
718 self.union(rhs).cloned().collect()
722 #[stable(feature = "rust1", since = "1.0.0")]
723 impl<'a, 'b, T, S> BitAnd<&'b HashSet<T, S>> for &'a HashSet<T, S>
724 where T: Eq + Hash + Clone,
725 S: BuildHasher + Default,
727 type Output = HashSet<T, S>;
729 /// Returns the intersection of `self` and `rhs` as a new `HashSet<T, S>`.
734 /// use std::collections::HashSet;
736 /// let a: HashSet<_> = vec![1, 2, 3].into_iter().collect();
737 /// let b: HashSet<_> = vec![2, 3, 4].into_iter().collect();
739 /// let set = &a & &b;
742 /// let expected = [2, 3];
744 /// assert!(expected.contains(x));
747 /// assert_eq!(i, expected.len());
749 fn bitand(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
750 self.intersection(rhs).cloned().collect()
754 #[stable(feature = "rust1", since = "1.0.0")]
755 impl<'a, 'b, T, S> BitXor<&'b HashSet<T, S>> for &'a HashSet<T, S>
756 where T: Eq + Hash + Clone,
757 S: BuildHasher + Default,
759 type Output = HashSet<T, S>;
761 /// Returns the symmetric difference of `self` and `rhs` as a new `HashSet<T, S>`.
766 /// use std::collections::HashSet;
768 /// let a: HashSet<_> = vec![1, 2, 3].into_iter().collect();
769 /// let b: HashSet<_> = vec![3, 4, 5].into_iter().collect();
771 /// let set = &a ^ &b;
774 /// let expected = [1, 2, 4, 5];
776 /// assert!(expected.contains(x));
779 /// assert_eq!(i, expected.len());
781 fn bitxor(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
782 self.symmetric_difference(rhs).cloned().collect()
786 #[stable(feature = "rust1", since = "1.0.0")]
787 impl<'a, 'b, T, S> Sub<&'b HashSet<T, S>> for &'a HashSet<T, S>
788 where T: Eq + Hash + Clone,
789 S: BuildHasher + Default,
791 type Output = HashSet<T, S>;
793 /// Returns the difference of `self` and `rhs` as a new `HashSet<T, S>`.
798 /// use std::collections::HashSet;
800 /// let a: HashSet<_> = vec![1, 2, 3].into_iter().collect();
801 /// let b: HashSet<_> = vec![3, 4, 5].into_iter().collect();
803 /// let set = &a - &b;
806 /// let expected = [1, 2];
808 /// assert!(expected.contains(x));
811 /// assert_eq!(i, expected.len());
813 fn sub(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
814 self.difference(rhs).cloned().collect()
819 #[stable(feature = "rust1", since = "1.0.0")]
820 pub struct Iter<'a, K: 'a> {
821 iter: Keys<'a, K, ()>
824 /// HashSet move iterator
825 #[stable(feature = "rust1", since = "1.0.0")]
826 pub struct IntoIter<K> {
827 iter: Map<map::IntoIter<K, ()>, fn((K, ())) -> K>
830 /// HashSet drain iterator
831 #[stable(feature = "rust1", since = "1.0.0")]
832 pub struct Drain<'a, K: 'a> {
833 iter: Map<map::Drain<'a, K, ()>, fn((K, ())) -> K>,
836 /// Intersection iterator
837 #[stable(feature = "rust1", since = "1.0.0")]
838 pub struct Intersection<'a, T: 'a, S: 'a> {
839 // iterator of the first set
842 other: &'a HashSet<T, S>,
845 /// Difference iterator
846 #[stable(feature = "rust1", since = "1.0.0")]
847 pub struct Difference<'a, T: 'a, S: 'a> {
848 // iterator of the first set
851 other: &'a HashSet<T, S>,
854 /// Symmetric difference iterator.
855 #[stable(feature = "rust1", since = "1.0.0")]
856 pub struct SymmetricDifference<'a, T: 'a, S: 'a> {
857 iter: Chain<Difference<'a, T, S>, Difference<'a, T, S>>
860 /// Set union iterator.
861 #[stable(feature = "rust1", since = "1.0.0")]
862 pub struct Union<'a, T: 'a, S: 'a> {
863 iter: Chain<Iter<'a, T>, Difference<'a, T, S>>
866 #[stable(feature = "rust1", since = "1.0.0")]
867 impl<'a, T, S> IntoIterator for &'a HashSet<T, S>
868 where T: Eq + Hash, S: BuildHasher
871 type IntoIter = Iter<'a, T>;
873 fn into_iter(self) -> Iter<'a, T> {
878 #[stable(feature = "rust1", since = "1.0.0")]
879 impl<T, S> IntoIterator for HashSet<T, S>
884 type IntoIter = IntoIter<T>;
886 /// Creates a consuming iterator, that is, one that moves each value out
887 /// of the set in arbitrary order. The set cannot be used after calling
893 /// use std::collections::HashSet;
894 /// let mut set = HashSet::new();
895 /// set.insert("a".to_string());
896 /// set.insert("b".to_string());
898 /// // Not possible to collect to a Vec<String> with a regular `.iter()`.
899 /// let v: Vec<String> = set.into_iter().collect();
901 /// // Will print in an arbitrary order.
903 /// println!("{}", x);
906 fn into_iter(self) -> IntoIter<T> {
907 fn first<A, B>((a, _): (A, B)) -> A { a }
908 let first: fn((T, ())) -> T = first;
910 IntoIter { iter: self.map.into_iter().map(first) }
914 #[stable(feature = "rust1", since = "1.0.0")]
915 impl<'a, K> Clone for Iter<'a, K> {
916 fn clone(&self) -> Iter<'a, K> { Iter { iter: self.iter.clone() } }
918 #[stable(feature = "rust1", since = "1.0.0")]
919 impl<'a, K> Iterator for Iter<'a, K> {
922 fn next(&mut self) -> Option<&'a K> { self.iter.next() }
923 fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
925 #[stable(feature = "rust1", since = "1.0.0")]
926 impl<'a, K> ExactSizeIterator for Iter<'a, K> {
927 fn len(&self) -> usize { self.iter.len() }
930 #[stable(feature = "rust1", since = "1.0.0")]
931 impl<K> Iterator for IntoIter<K> {
934 fn next(&mut self) -> Option<K> { self.iter.next() }
935 fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
937 #[stable(feature = "rust1", since = "1.0.0")]
938 impl<K> ExactSizeIterator for IntoIter<K> {
939 fn len(&self) -> usize { self.iter.len() }
942 #[stable(feature = "rust1", since = "1.0.0")]
943 impl<'a, K> Iterator for Drain<'a, K> {
946 fn next(&mut self) -> Option<K> { self.iter.next() }
947 fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
949 #[stable(feature = "rust1", since = "1.0.0")]
950 impl<'a, K> ExactSizeIterator for Drain<'a, K> {
951 fn len(&self) -> usize { self.iter.len() }
954 #[stable(feature = "rust1", since = "1.0.0")]
955 impl<'a, T, S> Clone for Intersection<'a, T, S> {
956 fn clone(&self) -> Intersection<'a, T, S> {
957 Intersection { iter: self.iter.clone(), ..*self }
961 #[stable(feature = "rust1", since = "1.0.0")]
962 impl<'a, T, S> Iterator for Intersection<'a, T, S>
963 where T: Eq + Hash, S: BuildHasher
967 fn next(&mut self) -> Option<&'a T> {
969 match self.iter.next() {
971 Some(elt) => if self.other.contains(elt) {
978 fn size_hint(&self) -> (usize, Option<usize>) {
979 let (_, upper) = self.iter.size_hint();
984 #[stable(feature = "rust1", since = "1.0.0")]
985 impl<'a, T, S> Clone for Difference<'a, T, S> {
986 fn clone(&self) -> Difference<'a, T, S> {
987 Difference { iter: self.iter.clone(), ..*self }
991 #[stable(feature = "rust1", since = "1.0.0")]
992 impl<'a, T, S> Iterator for Difference<'a, T, S>
993 where T: Eq + Hash, S: BuildHasher
997 fn next(&mut self) -> Option<&'a T> {
999 match self.iter.next() {
1000 None => return None,
1001 Some(elt) => if !self.other.contains(elt) {
1008 fn size_hint(&self) -> (usize, Option<usize>) {
1009 let (_, upper) = self.iter.size_hint();
1014 #[stable(feature = "rust1", since = "1.0.0")]
1015 impl<'a, T, S> Clone for SymmetricDifference<'a, T, S> {
1016 fn clone(&self) -> SymmetricDifference<'a, T, S> {
1017 SymmetricDifference { iter: self.iter.clone() }
1021 #[stable(feature = "rust1", since = "1.0.0")]
1022 impl<'a, T, S> Iterator for SymmetricDifference<'a, T, S>
1023 where T: Eq + Hash, S: BuildHasher
1027 fn next(&mut self) -> Option<&'a T> { self.iter.next() }
1028 fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
1031 #[stable(feature = "rust1", since = "1.0.0")]
1032 impl<'a, T, S> Clone for Union<'a, T, S> {
1033 fn clone(&self) -> Union<'a, T, S> { Union { iter: self.iter.clone() } }
1036 #[stable(feature = "rust1", since = "1.0.0")]
1037 impl<'a, T, S> Iterator for Union<'a, T, S>
1038 where T: Eq + Hash, S: BuildHasher
1042 fn next(&mut self) -> Option<&'a T> { self.iter.next() }
1043 fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
1053 fn test_disjoint() {
1054 let mut xs = HashSet::new();
1055 let mut ys = HashSet::new();
1056 assert!(xs.is_disjoint(&ys));
1057 assert!(ys.is_disjoint(&xs));
1058 assert!(xs.insert(5));
1059 assert!(ys.insert(11));
1060 assert!(xs.is_disjoint(&ys));
1061 assert!(ys.is_disjoint(&xs));
1062 assert!(xs.insert(7));
1063 assert!(xs.insert(19));
1064 assert!(xs.insert(4));
1065 assert!(ys.insert(2));
1066 assert!(ys.insert(-11));
1067 assert!(xs.is_disjoint(&ys));
1068 assert!(ys.is_disjoint(&xs));
1069 assert!(ys.insert(7));
1070 assert!(!xs.is_disjoint(&ys));
1071 assert!(!ys.is_disjoint(&xs));
1075 fn test_subset_and_superset() {
1076 let mut a = HashSet::new();
1077 assert!(a.insert(0));
1078 assert!(a.insert(5));
1079 assert!(a.insert(11));
1080 assert!(a.insert(7));
1082 let mut b = HashSet::new();
1083 assert!(b.insert(0));
1084 assert!(b.insert(7));
1085 assert!(b.insert(19));
1086 assert!(b.insert(250));
1087 assert!(b.insert(11));
1088 assert!(b.insert(200));
1090 assert!(!a.is_subset(&b));
1091 assert!(!a.is_superset(&b));
1092 assert!(!b.is_subset(&a));
1093 assert!(!b.is_superset(&a));
1095 assert!(b.insert(5));
1097 assert!(a.is_subset(&b));
1098 assert!(!a.is_superset(&b));
1099 assert!(!b.is_subset(&a));
1100 assert!(b.is_superset(&a));
1105 let mut a = HashSet::new();
1107 assert!(a.insert(i));
1109 let mut observed: u32 = 0;
1111 observed |= 1 << *k;
1113 assert_eq!(observed, 0xFFFF_FFFF);
1117 fn test_intersection() {
1118 let mut a = HashSet::new();
1119 let mut b = HashSet::new();
1121 assert!(a.insert(11));
1122 assert!(a.insert(1));
1123 assert!(a.insert(3));
1124 assert!(a.insert(77));
1125 assert!(a.insert(103));
1126 assert!(a.insert(5));
1127 assert!(a.insert(-5));
1129 assert!(b.insert(2));
1130 assert!(b.insert(11));
1131 assert!(b.insert(77));
1132 assert!(b.insert(-9));
1133 assert!(b.insert(-42));
1134 assert!(b.insert(5));
1135 assert!(b.insert(3));
1138 let expected = [3, 5, 11, 77];
1139 for x in a.intersection(&b) {
1140 assert!(expected.contains(x));
1143 assert_eq!(i, expected.len());
1147 fn test_difference() {
1148 let mut a = HashSet::new();
1149 let mut b = HashSet::new();
1151 assert!(a.insert(1));
1152 assert!(a.insert(3));
1153 assert!(a.insert(5));
1154 assert!(a.insert(9));
1155 assert!(a.insert(11));
1157 assert!(b.insert(3));
1158 assert!(b.insert(9));
1161 let expected = [1, 5, 11];
1162 for x in a.difference(&b) {
1163 assert!(expected.contains(x));
1166 assert_eq!(i, expected.len());
1170 fn test_symmetric_difference() {
1171 let mut a = HashSet::new();
1172 let mut b = HashSet::new();
1174 assert!(a.insert(1));
1175 assert!(a.insert(3));
1176 assert!(a.insert(5));
1177 assert!(a.insert(9));
1178 assert!(a.insert(11));
1180 assert!(b.insert(-2));
1181 assert!(b.insert(3));
1182 assert!(b.insert(9));
1183 assert!(b.insert(14));
1184 assert!(b.insert(22));
1187 let expected = [-2, 1, 5, 11, 14, 22];
1188 for x in a.symmetric_difference(&b) {
1189 assert!(expected.contains(x));
1192 assert_eq!(i, expected.len());
1197 let mut a = HashSet::new();
1198 let mut b = HashSet::new();
1200 assert!(a.insert(1));
1201 assert!(a.insert(3));
1202 assert!(a.insert(5));
1203 assert!(a.insert(9));
1204 assert!(a.insert(11));
1205 assert!(a.insert(16));
1206 assert!(a.insert(19));
1207 assert!(a.insert(24));
1209 assert!(b.insert(-2));
1210 assert!(b.insert(1));
1211 assert!(b.insert(5));
1212 assert!(b.insert(9));
1213 assert!(b.insert(13));
1214 assert!(b.insert(19));
1217 let expected = [-2, 1, 3, 5, 9, 11, 13, 16, 19, 24];
1218 for x in a.union(&b) {
1219 assert!(expected.contains(x));
1222 assert_eq!(i, expected.len());
1226 fn test_from_iter() {
1227 let xs = [1, 2, 3, 4, 5, 6, 7, 8, 9];
1229 let set: HashSet<_> = xs.iter().cloned().collect();
1232 assert!(set.contains(x));
1237 fn test_move_iter() {
1239 let mut hs = HashSet::new();
1247 let v = hs.into_iter().collect::<Vec<char>>();
1248 assert!(v == ['a', 'b'] || v == ['b', 'a']);
1253 // These constants once happened to expose a bug in insert().
1254 // I'm keeping them around to prevent a regression.
1255 let mut s1 = HashSet::new();
1261 let mut s2 = HashSet::new();
1275 let mut set = HashSet::new();
1276 let empty = HashSet::<i32>::new();
1281 let set_str = format!("{:?}", set);
1283 assert!(set_str == "{1, 2}" || set_str == "{2, 1}");
1284 assert_eq!(format!("{:?}", empty), "{}");
1288 fn test_trivial_drain() {
1289 let mut s = HashSet::<i32>::new();
1290 for _ in s.drain() {}
1291 assert!(s.is_empty());
1294 let mut s = HashSet::<i32>::new();
1296 assert!(s.is_empty());
1301 let mut s: HashSet<_> = (1..100).collect();
1303 // try this a bunch of times to make sure we don't screw up internal state.
1305 assert_eq!(s.len(), 99);
1309 let mut d = s.drain();
1310 for (i, x) in d.by_ref().take(50).enumerate() {
1314 assert_eq!(last_i, 49);
1317 for _ in &s { panic!("s should be empty!"); }
1319 // reset to try again.
1329 struct Foo(&'static str, i32);
1331 impl PartialEq for Foo {
1332 fn eq(&self, other: &Self) -> bool {
1339 impl hash::Hash for Foo {
1340 fn hash<H: hash::Hasher>(&self, h: &mut H) {
1345 let mut s = HashSet::new();
1346 assert_eq!(s.replace(Foo("a", 1)), None);
1347 assert_eq!(s.len(), 1);
1348 assert_eq!(s.replace(Foo("a", 2)), Some(Foo("a", 1)));
1349 assert_eq!(s.len(), 1);
1351 let mut it = s.iter();
1352 assert_eq!(it.next(), Some(&Foo("a", 2)));
1353 assert_eq!(it.next(), None);
1357 fn test_extend_ref() {
1358 let mut a = HashSet::new();
1361 a.extend(&[2, 3, 4]);
1363 assert_eq!(a.len(), 4);
1364 assert!(a.contains(&1));
1365 assert!(a.contains(&2));
1366 assert!(a.contains(&3));
1367 assert!(a.contains(&4));
1369 let mut b = HashSet::new();
1375 assert_eq!(a.len(), 6);
1376 assert!(a.contains(&1));
1377 assert!(a.contains(&2));
1378 assert!(a.contains(&3));
1379 assert!(a.contains(&4));
1380 assert!(a.contains(&5));
1381 assert!(a.contains(&6));