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 /// Returns a reference to the set's hasher.
197 #[unstable(feature = "hashmap_public_hasher", reason = "don't want to make insta-stable",
199 pub fn hasher(&self) -> &S {
203 /// Deprecated, renamed to `with_hasher`
205 #[unstable(feature = "hashmap_hasher", reason = "hasher stuff is unclear",
207 #[rustc_deprecated(since = "1.7.0", reason = "renamed to with_hasher")]
208 pub fn with_hash_state(hash_state: S) -> HashSet<T, S> {
209 HashSet::with_hasher(hash_state)
212 /// Deprecated, renamed to `with_capacity_and_hasher`
214 #[unstable(feature = "hashmap_hasher", reason = "hasher stuff is unclear",
216 #[rustc_deprecated(since = "1.7.0",
217 reason = "renamed to with_capacity_and_hasher")]
218 pub fn with_capacity_and_hash_state(capacity: usize, hash_state: S)
220 HashSet::with_capacity_and_hasher(capacity, hash_state)
223 /// Returns the number of elements the set can hold without reallocating.
228 /// use std::collections::HashSet;
229 /// let set: HashSet<i32> = HashSet::with_capacity(100);
230 /// assert!(set.capacity() >= 100);
233 #[stable(feature = "rust1", since = "1.0.0")]
234 pub fn capacity(&self) -> usize {
238 /// Reserves capacity for at least `additional` more elements to be inserted
239 /// in the `HashSet`. The collection may reserve more space to avoid
240 /// frequent reallocations.
244 /// Panics if the new allocation size overflows `usize`.
249 /// use std::collections::HashSet;
250 /// let mut set: HashSet<i32> = HashSet::new();
253 #[stable(feature = "rust1", since = "1.0.0")]
254 pub fn reserve(&mut self, additional: usize) {
255 self.map.reserve(additional)
258 /// Shrinks the capacity of the set as much as possible. It will drop
259 /// down as much as possible while maintaining the internal rules
260 /// and possibly leaving some space in accordance with the resize policy.
265 /// use std::collections::HashSet;
267 /// let mut set = HashSet::with_capacity(100);
270 /// assert!(set.capacity() >= 100);
271 /// set.shrink_to_fit();
272 /// assert!(set.capacity() >= 2);
274 #[stable(feature = "rust1", since = "1.0.0")]
275 pub fn shrink_to_fit(&mut self) {
276 self.map.shrink_to_fit()
279 /// An iterator visiting all elements in arbitrary order.
280 /// Iterator element type is &'a T.
285 /// use std::collections::HashSet;
286 /// let mut set = HashSet::new();
290 /// // Will print in an arbitrary order.
291 /// for x in set.iter() {
292 /// println!("{}", x);
295 #[stable(feature = "rust1", since = "1.0.0")]
296 pub fn iter(&self) -> Iter<T> {
297 Iter { iter: self.map.keys() }
300 /// Visit the values representing the difference.
305 /// use std::collections::HashSet;
306 /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
307 /// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect();
309 /// // Can be seen as `a - b`.
310 /// for x in a.difference(&b) {
311 /// println!("{}", x); // Print 1
314 /// let diff: HashSet<_> = a.difference(&b).cloned().collect();
315 /// assert_eq!(diff, [1].iter().cloned().collect());
317 /// // Note that difference is not symmetric,
318 /// // and `b - a` means something else:
319 /// let diff: HashSet<_> = b.difference(&a).cloned().collect();
320 /// assert_eq!(diff, [4].iter().cloned().collect());
322 #[stable(feature = "rust1", since = "1.0.0")]
323 pub fn difference<'a>(&'a self, other: &'a HashSet<T, S>) -> Difference<'a, T, S> {
330 /// Visit the values representing the symmetric difference.
335 /// use std::collections::HashSet;
336 /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
337 /// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect();
339 /// // Print 1, 4 in arbitrary order.
340 /// for x in a.symmetric_difference(&b) {
341 /// println!("{}", x);
344 /// let diff1: HashSet<_> = a.symmetric_difference(&b).cloned().collect();
345 /// let diff2: HashSet<_> = b.symmetric_difference(&a).cloned().collect();
347 /// assert_eq!(diff1, diff2);
348 /// assert_eq!(diff1, [1, 4].iter().cloned().collect());
350 #[stable(feature = "rust1", since = "1.0.0")]
351 pub fn symmetric_difference<'a>(&'a self, other: &'a HashSet<T, S>)
352 -> SymmetricDifference<'a, T, S> {
353 SymmetricDifference { iter: self.difference(other).chain(other.difference(self)) }
356 /// Visit the values representing the intersection.
361 /// use std::collections::HashSet;
362 /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
363 /// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect();
365 /// // Print 2, 3 in arbitrary order.
366 /// for x in a.intersection(&b) {
367 /// println!("{}", x);
370 /// let intersection: HashSet<_> = a.intersection(&b).cloned().collect();
371 /// assert_eq!(intersection, [2, 3].iter().cloned().collect());
373 #[stable(feature = "rust1", since = "1.0.0")]
374 pub fn intersection<'a>(&'a self, other: &'a HashSet<T, S>) -> Intersection<'a, T, S> {
381 /// Visit the values representing the union.
386 /// use std::collections::HashSet;
387 /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
388 /// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect();
390 /// // Print 1, 2, 3, 4 in arbitrary order.
391 /// for x in a.union(&b) {
392 /// println!("{}", x);
395 /// let union: HashSet<_> = a.union(&b).cloned().collect();
396 /// assert_eq!(union, [1, 2, 3, 4].iter().cloned().collect());
398 #[stable(feature = "rust1", since = "1.0.0")]
399 pub fn union<'a>(&'a self, other: &'a HashSet<T, S>) -> Union<'a, T, S> {
400 Union { iter: self.iter().chain(other.difference(self)) }
403 /// Returns the number of elements in the set.
408 /// use std::collections::HashSet;
410 /// let mut v = HashSet::new();
411 /// assert_eq!(v.len(), 0);
413 /// assert_eq!(v.len(), 1);
415 #[stable(feature = "rust1", since = "1.0.0")]
416 pub fn len(&self) -> usize { self.map.len() }
418 /// Returns true if the set contains no elements.
423 /// use std::collections::HashSet;
425 /// let mut v = HashSet::new();
426 /// assert!(v.is_empty());
428 /// assert!(!v.is_empty());
430 #[stable(feature = "rust1", since = "1.0.0")]
431 pub fn is_empty(&self) -> bool { self.map.is_empty() }
433 /// Clears the set, returning all elements in an iterator.
435 #[stable(feature = "drain", since = "1.6.0")]
436 pub fn drain(&mut self) -> Drain<T> {
437 fn first<A, B>((a, _): (A, B)) -> A { a }
438 let first: fn((T, ())) -> T = first; // coerce to fn pointer
440 Drain { iter: self.map.drain().map(first) }
443 /// Clears the set, removing all values.
448 /// use std::collections::HashSet;
450 /// let mut v = HashSet::new();
453 /// assert!(v.is_empty());
455 #[stable(feature = "rust1", since = "1.0.0")]
456 pub fn clear(&mut self) { self.map.clear() }
458 /// Returns `true` if the set contains a value.
460 /// The value may be any borrowed form of the set's value type, but
461 /// `Hash` and `Eq` on the borrowed form *must* match those for
467 /// use std::collections::HashSet;
469 /// let set: HashSet<_> = [1, 2, 3].iter().cloned().collect();
470 /// assert_eq!(set.contains(&1), true);
471 /// assert_eq!(set.contains(&4), false);
473 #[stable(feature = "rust1", since = "1.0.0")]
474 pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool
475 where T: Borrow<Q>, Q: Hash + Eq
477 self.map.contains_key(value)
480 /// Returns a reference to the value in the set, if any, that is equal to the given value.
482 /// The value may be any borrowed form of the set's value type, but
483 /// `Hash` and `Eq` on the borrowed form *must* match those for
485 #[unstable(feature = "set_recovery", issue = "28050")]
486 pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T>
487 where T: Borrow<Q>, Q: Hash + Eq
489 Recover::get(&self.map, value)
492 /// Returns `true` if the set has no elements in common with `other`.
493 /// This is equivalent to checking for an empty intersection.
498 /// use std::collections::HashSet;
500 /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
501 /// let mut b = HashSet::new();
503 /// assert_eq!(a.is_disjoint(&b), true);
505 /// assert_eq!(a.is_disjoint(&b), true);
507 /// assert_eq!(a.is_disjoint(&b), false);
509 #[stable(feature = "rust1", since = "1.0.0")]
510 pub fn is_disjoint(&self, other: &HashSet<T, S>) -> bool {
511 self.iter().all(|v| !other.contains(v))
514 /// Returns `true` if the set is a subset of another.
519 /// use std::collections::HashSet;
521 /// let sup: HashSet<_> = [1, 2, 3].iter().cloned().collect();
522 /// let mut set = HashSet::new();
524 /// assert_eq!(set.is_subset(&sup), true);
526 /// assert_eq!(set.is_subset(&sup), true);
528 /// assert_eq!(set.is_subset(&sup), false);
530 #[stable(feature = "rust1", since = "1.0.0")]
531 pub fn is_subset(&self, other: &HashSet<T, S>) -> bool {
532 self.iter().all(|v| other.contains(v))
535 /// Returns `true` if the set is a superset of another.
540 /// use std::collections::HashSet;
542 /// let sub: HashSet<_> = [1, 2].iter().cloned().collect();
543 /// let mut set = HashSet::new();
545 /// assert_eq!(set.is_superset(&sub), false);
549 /// assert_eq!(set.is_superset(&sub), false);
552 /// assert_eq!(set.is_superset(&sub), true);
555 #[stable(feature = "rust1", since = "1.0.0")]
556 pub fn is_superset(&self, other: &HashSet<T, S>) -> bool {
557 other.is_subset(self)
560 /// Adds a value to the set.
562 /// If the set did not have a value present, `true` is returned.
564 /// If the set did have this key present, `false` is returned.
569 /// use std::collections::HashSet;
571 /// let mut set = HashSet::new();
573 /// assert_eq!(set.insert(2), true);
574 /// assert_eq!(set.insert(2), false);
575 /// assert_eq!(set.len(), 1);
577 #[stable(feature = "rust1", since = "1.0.0")]
578 pub fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()).is_none() }
580 /// Adds a value to the set, replacing the existing value, if any, that is equal to the given
581 /// one. Returns the replaced value.
582 #[unstable(feature = "set_recovery", issue = "28050")]
583 pub fn replace(&mut self, value: T) -> Option<T> {
584 Recover::replace(&mut self.map, value)
587 /// Removes a value from the set. Returns `true` if the value was
588 /// present in the set.
590 /// The value may be any borrowed form of the set's value type, but
591 /// `Hash` and `Eq` on the borrowed form *must* match those for
597 /// use std::collections::HashSet;
599 /// let mut set = HashSet::new();
602 /// assert_eq!(set.remove(&2), true);
603 /// assert_eq!(set.remove(&2), false);
605 #[stable(feature = "rust1", since = "1.0.0")]
606 pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool
607 where T: Borrow<Q>, Q: Hash + Eq
609 self.map.remove(value).is_some()
612 /// Removes and returns the value in the set, if any, that is equal to the given one.
614 /// The value may be any borrowed form of the set's value type, but
615 /// `Hash` and `Eq` on the borrowed form *must* match those for
617 #[unstable(feature = "set_recovery", issue = "28050")]
618 pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T>
619 where T: Borrow<Q>, Q: Hash + Eq
621 Recover::take(&mut self.map, value)
625 #[stable(feature = "rust1", since = "1.0.0")]
626 impl<T, S> PartialEq for HashSet<T, S>
627 where T: Eq + Hash, S: BuildHasher
629 fn eq(&self, other: &HashSet<T, S>) -> bool {
630 if self.len() != other.len() { return false; }
632 self.iter().all(|key| other.contains(key))
636 #[stable(feature = "rust1", since = "1.0.0")]
637 impl<T, S> Eq for HashSet<T, S>
638 where T: Eq + Hash, S: BuildHasher
641 #[stable(feature = "rust1", since = "1.0.0")]
642 impl<T, S> fmt::Debug for HashSet<T, S>
643 where T: Eq + Hash + fmt::Debug,
646 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
647 f.debug_set().entries(self.iter()).finish()
651 #[stable(feature = "rust1", since = "1.0.0")]
652 impl<T, S> FromIterator<T> for HashSet<T, S>
654 S: BuildHasher + Default,
656 fn from_iter<I: IntoIterator<Item=T>>(iterable: I) -> HashSet<T, S> {
657 let iter = iterable.into_iter();
658 let lower = iter.size_hint().0;
659 let mut set = HashSet::with_capacity_and_hasher(lower, Default::default());
665 #[stable(feature = "rust1", since = "1.0.0")]
666 impl<T, S> Extend<T> for HashSet<T, S>
670 fn extend<I: IntoIterator<Item=T>>(&mut self, iter: I) {
677 #[stable(feature = "hash_extend_copy", since = "1.4.0")]
678 impl<'a, T, S> Extend<&'a T> for HashSet<T, S>
679 where T: 'a + Eq + Hash + Copy,
682 fn extend<I: IntoIterator<Item=&'a T>>(&mut self, iter: I) {
683 self.extend(iter.into_iter().cloned());
687 #[stable(feature = "rust1", since = "1.0.0")]
688 impl<T, S> Default for HashSet<T, S>
690 S: BuildHasher + Default,
692 fn default() -> HashSet<T, S> {
693 HashSet::with_hasher(Default::default())
697 #[stable(feature = "rust1", since = "1.0.0")]
698 impl<'a, 'b, T, S> BitOr<&'b HashSet<T, S>> for &'a HashSet<T, S>
699 where T: Eq + Hash + Clone,
700 S: BuildHasher + Default,
702 type Output = HashSet<T, S>;
704 /// Returns the union of `self` and `rhs` as a new `HashSet<T, S>`.
709 /// use std::collections::HashSet;
711 /// let a: HashSet<_> = vec![1, 2, 3].into_iter().collect();
712 /// let b: HashSet<_> = vec![3, 4, 5].into_iter().collect();
714 /// let set = &a | &b;
717 /// let expected = [1, 2, 3, 4, 5];
719 /// assert!(expected.contains(x));
722 /// assert_eq!(i, expected.len());
724 fn bitor(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
725 self.union(rhs).cloned().collect()
729 #[stable(feature = "rust1", since = "1.0.0")]
730 impl<'a, 'b, T, S> BitAnd<&'b HashSet<T, S>> for &'a HashSet<T, S>
731 where T: Eq + Hash + Clone,
732 S: BuildHasher + Default,
734 type Output = HashSet<T, S>;
736 /// Returns the intersection of `self` and `rhs` as a new `HashSet<T, S>`.
741 /// use std::collections::HashSet;
743 /// let a: HashSet<_> = vec![1, 2, 3].into_iter().collect();
744 /// let b: HashSet<_> = vec![2, 3, 4].into_iter().collect();
746 /// let set = &a & &b;
749 /// let expected = [2, 3];
751 /// assert!(expected.contains(x));
754 /// assert_eq!(i, expected.len());
756 fn bitand(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
757 self.intersection(rhs).cloned().collect()
761 #[stable(feature = "rust1", since = "1.0.0")]
762 impl<'a, 'b, T, S> BitXor<&'b HashSet<T, S>> for &'a HashSet<T, S>
763 where T: Eq + Hash + Clone,
764 S: BuildHasher + Default,
766 type Output = HashSet<T, S>;
768 /// Returns the symmetric difference of `self` and `rhs` as a new `HashSet<T, S>`.
773 /// use std::collections::HashSet;
775 /// let a: HashSet<_> = vec![1, 2, 3].into_iter().collect();
776 /// let b: HashSet<_> = vec![3, 4, 5].into_iter().collect();
778 /// let set = &a ^ &b;
781 /// let expected = [1, 2, 4, 5];
783 /// assert!(expected.contains(x));
786 /// assert_eq!(i, expected.len());
788 fn bitxor(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
789 self.symmetric_difference(rhs).cloned().collect()
793 #[stable(feature = "rust1", since = "1.0.0")]
794 impl<'a, 'b, T, S> Sub<&'b HashSet<T, S>> for &'a HashSet<T, S>
795 where T: Eq + Hash + Clone,
796 S: BuildHasher + Default,
798 type Output = HashSet<T, S>;
800 /// Returns the difference of `self` and `rhs` as a new `HashSet<T, S>`.
805 /// use std::collections::HashSet;
807 /// let a: HashSet<_> = vec![1, 2, 3].into_iter().collect();
808 /// let b: HashSet<_> = vec![3, 4, 5].into_iter().collect();
810 /// let set = &a - &b;
813 /// let expected = [1, 2];
815 /// assert!(expected.contains(x));
818 /// assert_eq!(i, expected.len());
820 fn sub(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
821 self.difference(rhs).cloned().collect()
826 #[stable(feature = "rust1", since = "1.0.0")]
827 pub struct Iter<'a, K: 'a> {
828 iter: Keys<'a, K, ()>
831 /// HashSet move iterator
832 #[stable(feature = "rust1", since = "1.0.0")]
833 pub struct IntoIter<K> {
834 iter: Map<map::IntoIter<K, ()>, fn((K, ())) -> K>
837 /// HashSet drain iterator
838 #[stable(feature = "rust1", since = "1.0.0")]
839 pub struct Drain<'a, K: 'a> {
840 iter: Map<map::Drain<'a, K, ()>, fn((K, ())) -> K>,
843 /// Intersection iterator
844 #[stable(feature = "rust1", since = "1.0.0")]
845 pub struct Intersection<'a, T: 'a, S: 'a> {
846 // iterator of the first set
849 other: &'a HashSet<T, S>,
852 /// Difference iterator
853 #[stable(feature = "rust1", since = "1.0.0")]
854 pub struct Difference<'a, T: 'a, S: 'a> {
855 // iterator of the first set
858 other: &'a HashSet<T, S>,
861 /// Symmetric difference iterator.
862 #[stable(feature = "rust1", since = "1.0.0")]
863 pub struct SymmetricDifference<'a, T: 'a, S: 'a> {
864 iter: Chain<Difference<'a, T, S>, Difference<'a, T, S>>
867 /// Set union iterator.
868 #[stable(feature = "rust1", since = "1.0.0")]
869 pub struct Union<'a, T: 'a, S: 'a> {
870 iter: Chain<Iter<'a, T>, Difference<'a, T, S>>
873 #[stable(feature = "rust1", since = "1.0.0")]
874 impl<'a, T, S> IntoIterator for &'a HashSet<T, S>
875 where T: Eq + Hash, S: BuildHasher
878 type IntoIter = Iter<'a, T>;
880 fn into_iter(self) -> Iter<'a, T> {
885 #[stable(feature = "rust1", since = "1.0.0")]
886 impl<T, S> IntoIterator for HashSet<T, S>
891 type IntoIter = IntoIter<T>;
893 /// Creates a consuming iterator, that is, one that moves each value out
894 /// of the set in arbitrary order. The set cannot be used after calling
900 /// use std::collections::HashSet;
901 /// let mut set = HashSet::new();
902 /// set.insert("a".to_string());
903 /// set.insert("b".to_string());
905 /// // Not possible to collect to a Vec<String> with a regular `.iter()`.
906 /// let v: Vec<String> = set.into_iter().collect();
908 /// // Will print in an arbitrary order.
910 /// println!("{}", x);
913 fn into_iter(self) -> IntoIter<T> {
914 fn first<A, B>((a, _): (A, B)) -> A { a }
915 let first: fn((T, ())) -> T = first;
917 IntoIter { iter: self.map.into_iter().map(first) }
921 #[stable(feature = "rust1", since = "1.0.0")]
922 impl<'a, K> Clone for Iter<'a, K> {
923 fn clone(&self) -> Iter<'a, K> { Iter { iter: self.iter.clone() } }
925 #[stable(feature = "rust1", since = "1.0.0")]
926 impl<'a, K> Iterator for Iter<'a, K> {
929 fn next(&mut self) -> Option<&'a K> { self.iter.next() }
930 fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
932 #[stable(feature = "rust1", since = "1.0.0")]
933 impl<'a, K> ExactSizeIterator for Iter<'a, K> {
934 fn len(&self) -> usize { self.iter.len() }
937 #[stable(feature = "rust1", since = "1.0.0")]
938 impl<K> Iterator for IntoIter<K> {
941 fn next(&mut self) -> Option<K> { self.iter.next() }
942 fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
944 #[stable(feature = "rust1", since = "1.0.0")]
945 impl<K> ExactSizeIterator for IntoIter<K> {
946 fn len(&self) -> usize { self.iter.len() }
949 #[stable(feature = "rust1", since = "1.0.0")]
950 impl<'a, K> Iterator for Drain<'a, K> {
953 fn next(&mut self) -> Option<K> { self.iter.next() }
954 fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
956 #[stable(feature = "rust1", since = "1.0.0")]
957 impl<'a, K> ExactSizeIterator for Drain<'a, K> {
958 fn len(&self) -> usize { self.iter.len() }
961 #[stable(feature = "rust1", since = "1.0.0")]
962 impl<'a, T, S> Clone for Intersection<'a, T, S> {
963 fn clone(&self) -> Intersection<'a, T, S> {
964 Intersection { iter: self.iter.clone(), ..*self }
968 #[stable(feature = "rust1", since = "1.0.0")]
969 impl<'a, T, S> Iterator for Intersection<'a, T, S>
970 where T: Eq + Hash, S: BuildHasher
974 fn next(&mut self) -> Option<&'a T> {
976 match self.iter.next() {
978 Some(elt) => if self.other.contains(elt) {
985 fn size_hint(&self) -> (usize, Option<usize>) {
986 let (_, upper) = self.iter.size_hint();
991 #[stable(feature = "rust1", since = "1.0.0")]
992 impl<'a, T, S> Clone for Difference<'a, T, S> {
993 fn clone(&self) -> Difference<'a, T, S> {
994 Difference { iter: self.iter.clone(), ..*self }
998 #[stable(feature = "rust1", since = "1.0.0")]
999 impl<'a, T, S> Iterator for Difference<'a, T, S>
1000 where T: Eq + Hash, S: BuildHasher
1004 fn next(&mut self) -> Option<&'a T> {
1006 match self.iter.next() {
1007 None => return None,
1008 Some(elt) => if !self.other.contains(elt) {
1015 fn size_hint(&self) -> (usize, Option<usize>) {
1016 let (_, upper) = self.iter.size_hint();
1021 #[stable(feature = "rust1", since = "1.0.0")]
1022 impl<'a, T, S> Clone for SymmetricDifference<'a, T, S> {
1023 fn clone(&self) -> SymmetricDifference<'a, T, S> {
1024 SymmetricDifference { iter: self.iter.clone() }
1028 #[stable(feature = "rust1", since = "1.0.0")]
1029 impl<'a, T, S> Iterator for SymmetricDifference<'a, T, S>
1030 where T: Eq + Hash, S: BuildHasher
1034 fn next(&mut self) -> Option<&'a T> { self.iter.next() }
1035 fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
1038 #[stable(feature = "rust1", since = "1.0.0")]
1039 impl<'a, T, S> Clone for Union<'a, T, S> {
1040 fn clone(&self) -> Union<'a, T, S> { Union { iter: self.iter.clone() } }
1043 #[stable(feature = "rust1", since = "1.0.0")]
1044 impl<'a, T, S> Iterator for Union<'a, T, S>
1045 where T: Eq + Hash, S: BuildHasher
1049 fn next(&mut self) -> Option<&'a T> { self.iter.next() }
1050 fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
1060 fn test_disjoint() {
1061 let mut xs = HashSet::new();
1062 let mut ys = HashSet::new();
1063 assert!(xs.is_disjoint(&ys));
1064 assert!(ys.is_disjoint(&xs));
1065 assert!(xs.insert(5));
1066 assert!(ys.insert(11));
1067 assert!(xs.is_disjoint(&ys));
1068 assert!(ys.is_disjoint(&xs));
1069 assert!(xs.insert(7));
1070 assert!(xs.insert(19));
1071 assert!(xs.insert(4));
1072 assert!(ys.insert(2));
1073 assert!(ys.insert(-11));
1074 assert!(xs.is_disjoint(&ys));
1075 assert!(ys.is_disjoint(&xs));
1076 assert!(ys.insert(7));
1077 assert!(!xs.is_disjoint(&ys));
1078 assert!(!ys.is_disjoint(&xs));
1082 fn test_subset_and_superset() {
1083 let mut a = HashSet::new();
1084 assert!(a.insert(0));
1085 assert!(a.insert(5));
1086 assert!(a.insert(11));
1087 assert!(a.insert(7));
1089 let mut b = HashSet::new();
1090 assert!(b.insert(0));
1091 assert!(b.insert(7));
1092 assert!(b.insert(19));
1093 assert!(b.insert(250));
1094 assert!(b.insert(11));
1095 assert!(b.insert(200));
1097 assert!(!a.is_subset(&b));
1098 assert!(!a.is_superset(&b));
1099 assert!(!b.is_subset(&a));
1100 assert!(!b.is_superset(&a));
1102 assert!(b.insert(5));
1104 assert!(a.is_subset(&b));
1105 assert!(!a.is_superset(&b));
1106 assert!(!b.is_subset(&a));
1107 assert!(b.is_superset(&a));
1112 let mut a = HashSet::new();
1114 assert!(a.insert(i));
1116 let mut observed: u32 = 0;
1118 observed |= 1 << *k;
1120 assert_eq!(observed, 0xFFFF_FFFF);
1124 fn test_intersection() {
1125 let mut a = HashSet::new();
1126 let mut b = HashSet::new();
1128 assert!(a.insert(11));
1129 assert!(a.insert(1));
1130 assert!(a.insert(3));
1131 assert!(a.insert(77));
1132 assert!(a.insert(103));
1133 assert!(a.insert(5));
1134 assert!(a.insert(-5));
1136 assert!(b.insert(2));
1137 assert!(b.insert(11));
1138 assert!(b.insert(77));
1139 assert!(b.insert(-9));
1140 assert!(b.insert(-42));
1141 assert!(b.insert(5));
1142 assert!(b.insert(3));
1145 let expected = [3, 5, 11, 77];
1146 for x in a.intersection(&b) {
1147 assert!(expected.contains(x));
1150 assert_eq!(i, expected.len());
1154 fn test_difference() {
1155 let mut a = HashSet::new();
1156 let mut b = HashSet::new();
1158 assert!(a.insert(1));
1159 assert!(a.insert(3));
1160 assert!(a.insert(5));
1161 assert!(a.insert(9));
1162 assert!(a.insert(11));
1164 assert!(b.insert(3));
1165 assert!(b.insert(9));
1168 let expected = [1, 5, 11];
1169 for x in a.difference(&b) {
1170 assert!(expected.contains(x));
1173 assert_eq!(i, expected.len());
1177 fn test_symmetric_difference() {
1178 let mut a = HashSet::new();
1179 let mut b = HashSet::new();
1181 assert!(a.insert(1));
1182 assert!(a.insert(3));
1183 assert!(a.insert(5));
1184 assert!(a.insert(9));
1185 assert!(a.insert(11));
1187 assert!(b.insert(-2));
1188 assert!(b.insert(3));
1189 assert!(b.insert(9));
1190 assert!(b.insert(14));
1191 assert!(b.insert(22));
1194 let expected = [-2, 1, 5, 11, 14, 22];
1195 for x in a.symmetric_difference(&b) {
1196 assert!(expected.contains(x));
1199 assert_eq!(i, expected.len());
1204 let mut a = HashSet::new();
1205 let mut b = HashSet::new();
1207 assert!(a.insert(1));
1208 assert!(a.insert(3));
1209 assert!(a.insert(5));
1210 assert!(a.insert(9));
1211 assert!(a.insert(11));
1212 assert!(a.insert(16));
1213 assert!(a.insert(19));
1214 assert!(a.insert(24));
1216 assert!(b.insert(-2));
1217 assert!(b.insert(1));
1218 assert!(b.insert(5));
1219 assert!(b.insert(9));
1220 assert!(b.insert(13));
1221 assert!(b.insert(19));
1224 let expected = [-2, 1, 3, 5, 9, 11, 13, 16, 19, 24];
1225 for x in a.union(&b) {
1226 assert!(expected.contains(x));
1229 assert_eq!(i, expected.len());
1233 fn test_from_iter() {
1234 let xs = [1, 2, 3, 4, 5, 6, 7, 8, 9];
1236 let set: HashSet<_> = xs.iter().cloned().collect();
1239 assert!(set.contains(x));
1244 fn test_move_iter() {
1246 let mut hs = HashSet::new();
1254 let v = hs.into_iter().collect::<Vec<char>>();
1255 assert!(v == ['a', 'b'] || v == ['b', 'a']);
1260 // These constants once happened to expose a bug in insert().
1261 // I'm keeping them around to prevent a regression.
1262 let mut s1 = HashSet::new();
1268 let mut s2 = HashSet::new();
1282 let mut set = HashSet::new();
1283 let empty = HashSet::<i32>::new();
1288 let set_str = format!("{:?}", set);
1290 assert!(set_str == "{1, 2}" || set_str == "{2, 1}");
1291 assert_eq!(format!("{:?}", empty), "{}");
1295 fn test_trivial_drain() {
1296 let mut s = HashSet::<i32>::new();
1297 for _ in s.drain() {}
1298 assert!(s.is_empty());
1301 let mut s = HashSet::<i32>::new();
1303 assert!(s.is_empty());
1308 let mut s: HashSet<_> = (1..100).collect();
1310 // try this a bunch of times to make sure we don't screw up internal state.
1312 assert_eq!(s.len(), 99);
1316 let mut d = s.drain();
1317 for (i, x) in d.by_ref().take(50).enumerate() {
1321 assert_eq!(last_i, 49);
1324 for _ in &s { panic!("s should be empty!"); }
1326 // reset to try again.
1336 struct Foo(&'static str, i32);
1338 impl PartialEq for Foo {
1339 fn eq(&self, other: &Self) -> bool {
1346 impl hash::Hash for Foo {
1347 fn hash<H: hash::Hasher>(&self, h: &mut H) {
1352 let mut s = HashSet::new();
1353 assert_eq!(s.replace(Foo("a", 1)), None);
1354 assert_eq!(s.len(), 1);
1355 assert_eq!(s.replace(Foo("a", 2)), Some(Foo("a", 1)));
1356 assert_eq!(s.len(), 1);
1358 let mut it = s.iter();
1359 assert_eq!(it.next(), Some(&Foo("a", 2)));
1360 assert_eq!(it.next(), None);
1364 fn test_extend_ref() {
1365 let mut a = HashSet::new();
1368 a.extend(&[2, 3, 4]);
1370 assert_eq!(a.len(), 4);
1371 assert!(a.contains(&1));
1372 assert!(a.contains(&2));
1373 assert!(a.contains(&3));
1374 assert!(a.contains(&4));
1376 let mut b = HashSet::new();
1382 assert_eq!(a.len(), 6);
1383 assert!(a.contains(&1));
1384 assert!(a.contains(&2));
1385 assert!(a.contains(&3));
1386 assert!(a.contains(&4));
1387 assert!(a.contains(&5));
1388 assert!(a.contains(&6));