aboutsummaryrefslogtreecommitdiff
path: root/src/set.rs
diff options
context:
space:
mode:
Diffstat (limited to 'src/set.rs')
-rw-r--r--src/set.rs428
1 files changed, 304 insertions, 124 deletions
diff --git a/src/set.rs b/src/set.rs
index b8460fd..d59183b 100644
--- a/src/set.rs
+++ b/src/set.rs
@@ -8,6 +8,7 @@ use core::mem;
use core::ops::{BitAnd, BitOr, BitXor, Sub};
use super::map::{self, ConsumeAllOnDrop, DefaultHashBuilder, DrainFilterInner, HashMap, Keys};
+use crate::raw::{Allocator, Global};
// Future Optimization (FIXME!)
// =============================
@@ -71,7 +72,7 @@ use super::map::{self, ConsumeAllOnDrop, DefaultHashBuilder, DrainFilterInner, H
/// ```
///
/// The easiest way to use `HashSet` with a custom type is to derive
-/// [`Eq`] and [`Hash`]. We must also derive [`PartialEq`], this will in the
+/// [`Eq`] and [`Hash`]. We must also derive [`PartialEq`]. This will in the
/// future be implied by [`Eq`].
///
/// ```
@@ -111,11 +112,11 @@ use super::map::{self, ConsumeAllOnDrop, DefaultHashBuilder, DrainFilterInner, H
/// [`HashMap`]: struct.HashMap.html
/// [`PartialEq`]: https://doc.rust-lang.org/std/cmp/trait.PartialEq.html
/// [`RefCell`]: https://doc.rust-lang.org/std/cell/struct.RefCell.html
-pub struct HashSet<T, S = DefaultHashBuilder> {
- pub(crate) map: HashMap<T, (), S>,
+pub struct HashSet<T, S = DefaultHashBuilder, A: Allocator + Clone = Global> {
+ pub(crate) map: HashMap<T, (), S, A>,
}
-impl<T: Clone, S: Clone> Clone for HashSet<T, S> {
+impl<T: Clone, S: Clone, A: Allocator + Clone> Clone for HashSet<T, S, A> {
fn clone(&self) -> Self {
HashSet {
map: self.map.clone(),
@@ -167,73 +168,47 @@ impl<T> HashSet<T, DefaultHashBuilder> {
}
}
-impl<T, S> HashSet<T, S> {
- /// Creates a new empty hash set which will use the given hasher to hash
- /// keys.
- ///
- /// The hash set is also created with the default initial capacity.
- ///
- /// Warning: `hasher` is normally randomly generated, and
- /// is designed to allow `HashSet`s to be resistant to attacks that
- /// cause many collisions and very poor performance. Setting it
- /// manually using this function can expose a DoS attack vector.
- ///
- /// The `hash_builder` passed should implement the [`BuildHasher`] trait for
- /// the HashMap to be useful, see its documentation for details.
+#[cfg(feature = "ahash")]
+impl<T: Hash + Eq, A: Allocator + Clone> HashSet<T, DefaultHashBuilder, A> {
+ /// Creates an empty `HashSet`.
///
+ /// The hash set is initially created with a capacity of 0, so it will not allocate until it
+ /// is first inserted into.
///
/// # Examples
///
/// ```
/// use hashbrown::HashSet;
- /// use hashbrown::hash_map::DefaultHashBuilder;
- ///
- /// let s = DefaultHashBuilder::default();
- /// let mut set = HashSet::with_hasher(s);
- /// set.insert(2);
+ /// let set: HashSet<i32> = HashSet::new();
/// ```
- ///
- /// [`BuildHasher`]: ../../std/hash/trait.BuildHasher.html
#[cfg_attr(feature = "inline-more", inline)]
- pub const fn with_hasher(hasher: S) -> Self {
+ pub fn new_in(alloc: A) -> Self {
Self {
- map: HashMap::with_hasher(hasher),
+ map: HashMap::new_in(alloc),
}
}
- /// Creates an empty `HashSet` with the specified capacity, using
- /// `hasher` to hash the keys.
+ /// Creates an empty `HashSet` with the specified capacity.
///
/// The hash set will be able to hold at least `capacity` elements without
/// reallocating. If `capacity` is 0, the hash set will not allocate.
///
- /// Warning: `hasher` is normally randomly generated, and
- /// is designed to allow `HashSet`s to be resistant to attacks that
- /// cause many collisions and very poor performance. Setting it
- /// manually using this function can expose a DoS attack vector.
- ///
- /// The `hash_builder` passed should implement the [`BuildHasher`] trait for
- /// the HashMap to be useful, see its documentation for details.
- ///
/// # Examples
///
/// ```
/// use hashbrown::HashSet;
- /// use hashbrown::hash_map::DefaultHashBuilder;
- ///
- /// let s = DefaultHashBuilder::default();
- /// let mut set = HashSet::with_capacity_and_hasher(10, s);
- /// set.insert(1);
+ /// let set: HashSet<i32> = HashSet::with_capacity(10);
+ /// assert!(set.capacity() >= 10);
/// ```
- ///
- /// [`BuildHasher`]: ../../std/hash/trait.BuildHasher.html
#[cfg_attr(feature = "inline-more", inline)]
- pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> Self {
+ pub fn with_capacity_in(capacity: usize, alloc: A) -> Self {
Self {
- map: HashMap::with_capacity_and_hasher(capacity, hasher),
+ map: HashMap::with_capacity_in(capacity, alloc),
}
}
+}
+impl<T, S, A: Allocator + Clone> HashSet<T, S, A> {
/// Returns the number of elements the set can hold without reallocating.
///
/// # Examples
@@ -323,7 +298,7 @@ impl<T, S> HashSet<T, S> {
/// assert!(set.is_empty());
/// ```
#[cfg_attr(feature = "inline-more", inline)]
- pub fn drain(&mut self) -> Drain<'_, T> {
+ pub fn drain(&mut self) -> Drain<'_, T, A> {
Drain {
iter: self.map.drain(),
}
@@ -376,7 +351,7 @@ impl<T, S> HashSet<T, S> {
/// assert_eq!(odds, vec![1, 3, 5, 7]);
/// ```
#[cfg_attr(feature = "inline-more", inline)]
- pub fn drain_filter<F>(&mut self, f: F) -> DrainFilter<'_, T, F>
+ pub fn drain_filter<F>(&mut self, f: F) -> DrainFilter<'_, T, F, A>
where
F: FnMut(&T) -> bool,
{
@@ -405,6 +380,134 @@ impl<T, S> HashSet<T, S> {
pub fn clear(&mut self) {
self.map.clear()
}
+}
+
+impl<T, S> HashSet<T, S, Global> {
+ /// Creates a new empty hash set which will use the given hasher to hash
+ /// keys.
+ ///
+ /// The hash set is also created with the default initial capacity.
+ ///
+ /// Warning: `hasher` is normally randomly generated, and
+ /// is designed to allow `HashSet`s to be resistant to attacks that
+ /// cause many collisions and very poor performance. Setting it
+ /// manually using this function can expose a DoS attack vector.
+ ///
+ /// The `hash_builder` passed should implement the [`BuildHasher`] trait for
+ /// the HashMap to be useful, see its documentation for details.
+ ///
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::HashSet;
+ /// use hashbrown::hash_map::DefaultHashBuilder;
+ ///
+ /// let s = DefaultHashBuilder::default();
+ /// let mut set = HashSet::with_hasher(s);
+ /// set.insert(2);
+ /// ```
+ ///
+ /// [`BuildHasher`]: ../../std/hash/trait.BuildHasher.html
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub const fn with_hasher(hasher: S) -> Self {
+ Self {
+ map: HashMap::with_hasher(hasher),
+ }
+ }
+
+ /// Creates an empty `HashSet` with the specified capacity, using
+ /// `hasher` to hash the keys.
+ ///
+ /// The hash set will be able to hold at least `capacity` elements without
+ /// reallocating. If `capacity` is 0, the hash set will not allocate.
+ ///
+ /// Warning: `hasher` is normally randomly generated, and
+ /// is designed to allow `HashSet`s to be resistant to attacks that
+ /// cause many collisions and very poor performance. Setting it
+ /// manually using this function can expose a DoS attack vector.
+ ///
+ /// The `hash_builder` passed should implement the [`BuildHasher`] trait for
+ /// the HashMap to be useful, see its documentation for details.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::HashSet;
+ /// use hashbrown::hash_map::DefaultHashBuilder;
+ ///
+ /// let s = DefaultHashBuilder::default();
+ /// let mut set = HashSet::with_capacity_and_hasher(10, s);
+ /// set.insert(1);
+ /// ```
+ ///
+ /// [`BuildHasher`]: ../../std/hash/trait.BuildHasher.html
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> Self {
+ Self {
+ map: HashMap::with_capacity_and_hasher(capacity, hasher),
+ }
+ }
+}
+
+impl<T, S, A> HashSet<T, S, A>
+where
+ A: Allocator + Clone,
+{
+ /// Creates a new empty hash set which will use the given hasher to hash
+ /// keys.
+ ///
+ /// The hash set is also created with the default initial capacity.
+ ///
+ /// Warning: `hasher` is normally randomly generated, and
+ /// is designed to allow `HashSet`s to be resistant to attacks that
+ /// cause many collisions and very poor performance. Setting it
+ /// manually using this function can expose a DoS attack vector.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::HashSet;
+ /// use hashbrown::hash_map::DefaultHashBuilder;
+ ///
+ /// let s = DefaultHashBuilder::default();
+ /// let mut set = HashSet::with_hasher(s);
+ /// set.insert(2);
+ /// ```
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn with_hasher_in(hasher: S, alloc: A) -> Self {
+ Self {
+ map: HashMap::with_hasher_in(hasher, alloc),
+ }
+ }
+
+ /// Creates an empty `HashSet` with the specified capacity, using
+ /// `hasher` to hash the keys.
+ ///
+ /// The hash set will be able to hold at least `capacity` elements without
+ /// reallocating. If `capacity` is 0, the hash set will not allocate.
+ ///
+ /// Warning: `hasher` is normally randomly generated, and
+ /// is designed to allow `HashSet`s to be resistant to attacks that
+ /// cause many collisions and very poor performance. Setting it
+ /// manually using this function can expose a DoS attack vector.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::HashSet;
+ /// use hashbrown::hash_map::DefaultHashBuilder;
+ ///
+ /// let s = DefaultHashBuilder::default();
+ /// let mut set = HashSet::with_capacity_and_hasher(10, s);
+ /// set.insert(1);
+ /// ```
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn with_capacity_and_hasher_in(capacity: usize, hasher: S, alloc: A) -> Self {
+ Self {
+ map: HashMap::with_capacity_and_hasher_in(capacity, hasher, alloc),
+ }
+ }
/// Returns a reference to the set's [`BuildHasher`].
///
@@ -426,10 +529,11 @@ impl<T, S> HashSet<T, S> {
}
}
-impl<T, S> HashSet<T, S>
+impl<T, S, A> HashSet<T, S, A>
where
T: Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
/// Reserves capacity for at least `additional` more elements to be inserted
/// in the `HashSet`. The collection may reserve more space to avoid
@@ -544,7 +648,7 @@ where
/// assert_eq!(diff, [4].iter().collect());
/// ```
#[cfg_attr(feature = "inline-more", inline)]
- pub fn difference<'a>(&'a self, other: &'a Self) -> Difference<'a, T, S> {
+ pub fn difference<'a>(&'a self, other: &'a Self) -> Difference<'a, T, S, A> {
Difference {
iter: self.iter(),
other,
@@ -573,7 +677,7 @@ where
/// assert_eq!(diff1, [1, 4].iter().collect());
/// ```
#[cfg_attr(feature = "inline-more", inline)]
- pub fn symmetric_difference<'a>(&'a self, other: &'a Self) -> SymmetricDifference<'a, T, S> {
+ pub fn symmetric_difference<'a>(&'a self, other: &'a Self) -> SymmetricDifference<'a, T, S, A> {
SymmetricDifference {
iter: self.difference(other).chain(other.difference(self)),
}
@@ -598,7 +702,7 @@ where
/// assert_eq!(intersection, [2, 3].iter().collect());
/// ```
#[cfg_attr(feature = "inline-more", inline)]
- pub fn intersection<'a>(&'a self, other: &'a Self) -> Intersection<'a, T, S> {
+ pub fn intersection<'a>(&'a self, other: &'a Self) -> Intersection<'a, T, S, A> {
let (smaller, larger) = if self.len() <= other.len() {
(self, other)
} else {
@@ -629,8 +733,10 @@ where
/// assert_eq!(union, [1, 2, 3, 4].iter().collect());
/// ```
#[cfg_attr(feature = "inline-more", inline)]
- pub fn union<'a>(&'a self, other: &'a Self) -> Union<'a, T, S> {
- let (smaller, larger) = if self.len() >= other.len() {
+ pub fn union<'a>(&'a self, other: &'a Self) -> Union<'a, T, S, A> {
+ // We'll iterate one set in full, and only the remaining difference from the other.
+ // Use the smaller set for the difference in order to reduce hash lookups.
+ let (smaller, larger) = if self.len() <= other.len() {
(self, other)
} else {
(other, self)
@@ -967,10 +1073,11 @@ where
}
}
-impl<T, S> PartialEq for HashSet<T, S>
+impl<T, S, A> PartialEq for HashSet<T, S, A>
where
T: Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
fn eq(&self, other: &Self) -> bool {
if self.len() != other.len() {
@@ -981,40 +1088,53 @@ where
}
}
-impl<T, S> Eq for HashSet<T, S>
+impl<T, S, A> Eq for HashSet<T, S, A>
where
T: Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
}
-impl<T, S> fmt::Debug for HashSet<T, S>
+impl<T, S, A> fmt::Debug for HashSet<T, S, A>
where
T: Eq + Hash + fmt::Debug,
S: BuildHasher,
+ A: Allocator + Clone,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_set().entries(self.iter()).finish()
}
}
-impl<T, S> FromIterator<T> for HashSet<T, S>
+impl<T, S, A> From<HashMap<T, (), S, A>> for HashSet<T, S, A>
+where
+ A: Allocator + Clone,
+{
+ fn from(map: HashMap<T, (), S, A>) -> Self {
+ Self { map }
+ }
+}
+
+impl<T, S, A> FromIterator<T> for HashSet<T, S, A>
where
T: Eq + Hash,
S: BuildHasher + Default,
+ A: Default + Allocator + Clone,
{
#[cfg_attr(feature = "inline-more", inline)]
fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
- let mut set = Self::with_hasher(Default::default());
+ let mut set = Self::with_hasher_in(Default::default(), Default::default());
set.extend(iter);
set
}
}
-impl<T, S> Extend<T> for HashSet<T, S>
+impl<T, S, A> Extend<T> for HashSet<T, S, A>
where
T: Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
#[cfg_attr(feature = "inline-more", inline)]
fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
@@ -1034,10 +1154,11 @@ where
}
}
-impl<'a, T, S> Extend<&'a T> for HashSet<T, S>
+impl<'a, T, S, A> Extend<&'a T> for HashSet<T, S, A>
where
T: 'a + Eq + Hash + Copy,
S: BuildHasher,
+ A: Allocator + Clone,
{
#[cfg_attr(feature = "inline-more", inline)]
fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
@@ -1057,9 +1178,10 @@ where
}
}
-impl<T, S> Default for HashSet<T, S>
+impl<T, S, A> Default for HashSet<T, S, A>
where
S: Default,
+ A: Default + Allocator + Clone,
{
/// Creates an empty `HashSet<T, S>` with the `Default` value for the hasher.
#[cfg_attr(feature = "inline-more", inline)]
@@ -1070,10 +1192,11 @@ where
}
}
-impl<T, S> BitOr<&HashSet<T, S>> for &HashSet<T, S>
+impl<T, S, A> BitOr<&HashSet<T, S, A>> for &HashSet<T, S, A>
where
T: Eq + Hash + Clone,
S: BuildHasher + Default,
+ A: Allocator + Clone,
{
type Output = HashSet<T, S>;
@@ -1097,15 +1220,16 @@ where
/// }
/// assert_eq!(i, expected.len());
/// ```
- fn bitor(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
+ fn bitor(self, rhs: &HashSet<T, S, A>) -> HashSet<T, S> {
self.union(rhs).cloned().collect()
}
}
-impl<T, S> BitAnd<&HashSet<T, S>> for &HashSet<T, S>
+impl<T, S, A> BitAnd<&HashSet<T, S, A>> for &HashSet<T, S, A>
where
T: Eq + Hash + Clone,
S: BuildHasher + Default,
+ A: Allocator + Clone,
{
type Output = HashSet<T, S>;
@@ -1129,7 +1253,7 @@ where
/// }
/// assert_eq!(i, expected.len());
/// ```
- fn bitand(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
+ fn bitand(self, rhs: &HashSet<T, S, A>) -> HashSet<T, S> {
self.intersection(rhs).cloned().collect()
}
}
@@ -1216,8 +1340,8 @@ pub struct Iter<'a, K> {
///
/// [`HashSet`]: struct.HashSet.html
/// [`into_iter`]: struct.HashSet.html#method.into_iter
-pub struct IntoIter<K> {
- iter: map::IntoIter<K, ()>,
+pub struct IntoIter<K, A: Allocator + Clone = Global> {
+ iter: map::IntoIter<K, (), A>,
}
/// A draining iterator over the items of a `HashSet`.
@@ -1227,8 +1351,8 @@ pub struct IntoIter<K> {
///
/// [`HashSet`]: struct.HashSet.html
/// [`drain`]: struct.HashSet.html#method.drain
-pub struct Drain<'a, K> {
- iter: map::Drain<'a, K, ()>,
+pub struct Drain<'a, K, A: Allocator + Clone = Global> {
+ iter: map::Drain<'a, K, (), A>,
}
/// A draining iterator over entries of a `HashSet` which don't satisfy the predicate `f`.
@@ -1238,12 +1362,12 @@ pub struct Drain<'a, K> {
///
/// [`drain_filter`]: struct.HashSet.html#method.drain_filter
/// [`HashSet`]: struct.HashSet.html
-pub struct DrainFilter<'a, K, F>
+pub struct DrainFilter<'a, K, F, A: Allocator + Clone = Global>
where
F: FnMut(&K) -> bool,
{
f: F,
- inner: DrainFilterInner<'a, K, ()>,
+ inner: DrainFilterInner<'a, K, (), A>,
}
/// A lazy iterator producing elements in the intersection of `HashSet`s.
@@ -1253,11 +1377,11 @@ where
///
/// [`HashSet`]: struct.HashSet.html
/// [`intersection`]: struct.HashSet.html#method.intersection
-pub struct Intersection<'a, T, S> {
+pub struct Intersection<'a, T, S, A: Allocator + Clone = Global> {
// iterator of the first set
iter: Iter<'a, T>,
// the second set
- other: &'a HashSet<T, S>,
+ other: &'a HashSet<T, S, A>,
}
/// A lazy iterator producing elements in the difference of `HashSet`s.
@@ -1267,11 +1391,11 @@ pub struct Intersection<'a, T, S> {
///
/// [`HashSet`]: struct.HashSet.html
/// [`difference`]: struct.HashSet.html#method.difference
-pub struct Difference<'a, T, S> {
+pub struct Difference<'a, T, S, A: Allocator + Clone = Global> {
// iterator of the first set
iter: Iter<'a, T>,
// the second set
- other: &'a HashSet<T, S>,
+ other: &'a HashSet<T, S, A>,
}
/// A lazy iterator producing elements in the symmetric difference of `HashSet`s.
@@ -1281,8 +1405,8 @@ pub struct Difference<'a, T, S> {
///
/// [`HashSet`]: struct.HashSet.html
/// [`symmetric_difference`]: struct.HashSet.html#method.symmetric_difference
-pub struct SymmetricDifference<'a, T, S> {
- iter: Chain<Difference<'a, T, S>, Difference<'a, T, S>>,
+pub struct SymmetricDifference<'a, T, S, A: Allocator + Clone = Global> {
+ iter: Chain<Difference<'a, T, S, A>, Difference<'a, T, S, A>>,
}
/// A lazy iterator producing elements in the union of `HashSet`s.
@@ -1292,11 +1416,11 @@ pub struct SymmetricDifference<'a, T, S> {
///
/// [`HashSet`]: struct.HashSet.html
/// [`union`]: struct.HashSet.html#method.union
-pub struct Union<'a, T, S> {
- iter: Chain<Iter<'a, T>, Difference<'a, T, S>>,
+pub struct Union<'a, T, S, A: Allocator + Clone = Global> {
+ iter: Chain<Iter<'a, T>, Difference<'a, T, S, A>>,
}
-impl<'a, T, S> IntoIterator for &'a HashSet<T, S> {
+impl<'a, T, S, A: Allocator + Clone> IntoIterator for &'a HashSet<T, S, A> {
type Item = &'a T;
type IntoIter = Iter<'a, T>;
@@ -1306,9 +1430,9 @@ impl<'a, T, S> IntoIterator for &'a HashSet<T, S> {
}
}
-impl<T, S> IntoIterator for HashSet<T, S> {
+impl<T, S, A: Allocator + Clone> IntoIterator for HashSet<T, S, A> {
type Item = T;
- type IntoIter = IntoIter<T>;
+ type IntoIter = IntoIter<T, A>;
/// Creates a consuming iterator, that is, one that moves each value out
/// of the set in arbitrary order. The set cannot be used after calling
@@ -1331,7 +1455,7 @@ impl<T, S> IntoIterator for HashSet<T, S> {
/// }
/// ```
#[cfg_attr(feature = "inline-more", inline)]
- fn into_iter(self) -> IntoIter<T> {
+ fn into_iter(self) -> IntoIter<T, A> {
IntoIter {
iter: self.map.into_iter(),
}
@@ -1372,7 +1496,7 @@ impl<K: fmt::Debug> fmt::Debug for Iter<'_, K> {
}
}
-impl<K> Iterator for IntoIter<K> {
+impl<K, A: Allocator + Clone> Iterator for IntoIter<K, A> {
type Item = K;
#[cfg_attr(feature = "inline-more", inline)]
@@ -1388,22 +1512,22 @@ impl<K> Iterator for IntoIter<K> {
self.iter.size_hint()
}
}
-impl<K> ExactSizeIterator for IntoIter<K> {
+impl<K, A: Allocator + Clone> ExactSizeIterator for IntoIter<K, A> {
#[cfg_attr(feature = "inline-more", inline)]
fn len(&self) -> usize {
self.iter.len()
}
}
-impl<K> FusedIterator for IntoIter<K> {}
+impl<K, A: Allocator + Clone> FusedIterator for IntoIter<K, A> {}
-impl<K: fmt::Debug> fmt::Debug for IntoIter<K> {
+impl<K: fmt::Debug, A: Allocator + Clone> fmt::Debug for IntoIter<K, A> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
let entries_iter = self.iter.iter().map(|(k, _)| k);
f.debug_list().entries(entries_iter).finish()
}
}
-impl<K> Iterator for Drain<'_, K> {
+impl<K, A: Allocator + Clone> Iterator for Drain<'_, K, A> {
type Item = K;
#[cfg_attr(feature = "inline-more", inline)]
@@ -1419,22 +1543,22 @@ impl<K> Iterator for Drain<'_, K> {
self.iter.size_hint()
}
}
-impl<K> ExactSizeIterator for Drain<'_, K> {
+impl<K, A: Allocator + Clone> ExactSizeIterator for Drain<'_, K, A> {
#[cfg_attr(feature = "inline-more", inline)]
fn len(&self) -> usize {
self.iter.len()
}
}
-impl<K> FusedIterator for Drain<'_, K> {}
+impl<K, A: Allocator + Clone> FusedIterator for Drain<'_, K, A> {}
-impl<K: fmt::Debug> fmt::Debug for Drain<'_, K> {
+impl<K: fmt::Debug, A: Allocator + Clone> fmt::Debug for Drain<'_, K, A> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
let entries_iter = self.iter.iter().map(|(k, _)| k);
f.debug_list().entries(entries_iter).finish()
}
}
-impl<'a, K, F> Drop for DrainFilter<'a, K, F>
+impl<'a, K, F, A: Allocator + Clone> Drop for DrainFilter<'a, K, F, A>
where
F: FnMut(&K) -> bool,
{
@@ -1448,7 +1572,7 @@ where
}
}
-impl<K, F> Iterator for DrainFilter<'_, K, F>
+impl<K, F, A: Allocator + Clone> Iterator for DrainFilter<'_, K, F, A>
where
F: FnMut(&K) -> bool,
{
@@ -1467,9 +1591,12 @@ where
}
}
-impl<K, F> FusedIterator for DrainFilter<'_, K, F> where F: FnMut(&K) -> bool {}
+impl<K, F, A: Allocator + Clone> FusedIterator for DrainFilter<'_, K, F, A> where
+ F: FnMut(&K) -> bool
+{
+}
-impl<T, S> Clone for Intersection<'_, T, S> {
+impl<T, S, A: Allocator + Clone> Clone for Intersection<'_, T, S, A> {
#[cfg_attr(feature = "inline-more", inline)]
fn clone(&self) -> Self {
Intersection {
@@ -1479,10 +1606,11 @@ impl<T, S> Clone for Intersection<'_, T, S> {
}
}
-impl<'a, T, S> Iterator for Intersection<'a, T, S>
+impl<'a, T, S, A> Iterator for Intersection<'a, T, S, A>
where
T: Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
type Item = &'a T;
@@ -1503,24 +1631,26 @@ where
}
}
-impl<T, S> fmt::Debug for Intersection<'_, T, S>
+impl<T, S, A> fmt::Debug for Intersection<'_, T, S, A>
where
T: fmt::Debug + Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_list().entries(self.clone()).finish()
}
}
-impl<T, S> FusedIterator for Intersection<'_, T, S>
+impl<T, S, A> FusedIterator for Intersection<'_, T, S, A>
where
T: Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
}
-impl<T, S> Clone for Difference<'_, T, S> {
+impl<T, S, A: Allocator + Clone> Clone for Difference<'_, T, S, A> {
#[cfg_attr(feature = "inline-more", inline)]
fn clone(&self) -> Self {
Difference {
@@ -1530,10 +1660,11 @@ impl<T, S> Clone for Difference<'_, T, S> {
}
}
-impl<'a, T, S> Iterator for Difference<'a, T, S>
+impl<'a, T, S, A> Iterator for Difference<'a, T, S, A>
where
T: Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
type Item = &'a T;
@@ -1554,24 +1685,26 @@ where
}
}
-impl<T, S> FusedIterator for Difference<'_, T, S>
+impl<T, S, A> FusedIterator for Difference<'_, T, S, A>
where
T: Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
}
-impl<T, S> fmt::Debug for Difference<'_, T, S>
+impl<T, S, A> fmt::Debug for Difference<'_, T, S, A>
where
T: fmt::Debug + Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_list().entries(self.clone()).finish()
}
}
-impl<T, S> Clone for SymmetricDifference<'_, T, S> {
+impl<T, S, A: Allocator + Clone> Clone for SymmetricDifference<'_, T, S, A> {
#[cfg_attr(feature = "inline-more", inline)]
fn clone(&self) -> Self {
SymmetricDifference {
@@ -1580,10 +1713,11 @@ impl<T, S> Clone for SymmetricDifference<'_, T, S> {
}
}
-impl<'a, T, S> Iterator for SymmetricDifference<'a, T, S>
+impl<'a, T, S, A> Iterator for SymmetricDifference<'a, T, S, A>
where
T: Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
type Item = &'a T;
@@ -1597,24 +1731,26 @@ where
}
}
-impl<T, S> FusedIterator for SymmetricDifference<'_, T, S>
+impl<T, S, A> FusedIterator for SymmetricDifference<'_, T, S, A>
where
T: Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
}
-impl<T, S> fmt::Debug for SymmetricDifference<'_, T, S>
+impl<T, S, A> fmt::Debug for SymmetricDifference<'_, T, S, A>
where
T: fmt::Debug + Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_list().entries(self.clone()).finish()
}
}
-impl<T, S> Clone for Union<'_, T, S> {
+impl<T, S, A: Allocator + Clone> Clone for Union<'_, T, S, A> {
#[cfg_attr(feature = "inline-more", inline)]
fn clone(&self) -> Self {
Union {
@@ -1623,27 +1759,30 @@ impl<T, S> Clone for Union<'_, T, S> {
}
}
-impl<T, S> FusedIterator for Union<'_, T, S>
+impl<T, S, A> FusedIterator for Union<'_, T, S, A>
where
T: Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
}
-impl<T, S> fmt::Debug for Union<'_, T, S>
+impl<T, S, A> fmt::Debug for Union<'_, T, S, A>
where
T: fmt::Debug + Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_list().entries(self.clone()).finish()
}
}
-impl<'a, T, S> Iterator for Union<'a, T, S>
+impl<'a, T, S, A> Iterator for Union<'a, T, S, A>
where
T: Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
type Item = &'a T;
@@ -1665,30 +1804,34 @@ fn assert_covariance() {
fn iter<'a, 'new>(v: Iter<'a, &'static str>) -> Iter<'a, &'new str> {
v
}
- fn into_iter<'new>(v: IntoIter<&'static str>) -> IntoIter<&'new str> {
+ fn into_iter<'new, A: Allocator + Clone>(
+ v: IntoIter<&'static str, A>,
+ ) -> IntoIter<&'new str, A> {
v
}
- fn difference<'a, 'new>(
- v: Difference<'a, &'static str, DefaultHashBuilder>,
- ) -> Difference<'a, &'new str, DefaultHashBuilder> {
+ fn difference<'a, 'new, A: Allocator + Clone>(
+ v: Difference<'a, &'static str, DefaultHashBuilder, A>,
+ ) -> Difference<'a, &'new str, DefaultHashBuilder, A> {
v
}
- fn symmetric_difference<'a, 'new>(
- v: SymmetricDifference<'a, &'static str, DefaultHashBuilder>,
- ) -> SymmetricDifference<'a, &'new str, DefaultHashBuilder> {
+ fn symmetric_difference<'a, 'new, A: Allocator + Clone>(
+ v: SymmetricDifference<'a, &'static str, DefaultHashBuilder, A>,
+ ) -> SymmetricDifference<'a, &'new str, DefaultHashBuilder, A> {
v
}
- fn intersection<'a, 'new>(
- v: Intersection<'a, &'static str, DefaultHashBuilder>,
- ) -> Intersection<'a, &'new str, DefaultHashBuilder> {
+ fn intersection<'a, 'new, A: Allocator + Clone>(
+ v: Intersection<'a, &'static str, DefaultHashBuilder, A>,
+ ) -> Intersection<'a, &'new str, DefaultHashBuilder, A> {
v
}
- fn union<'a, 'new>(
- v: Union<'a, &'static str, DefaultHashBuilder>,
- ) -> Union<'a, &'new str, DefaultHashBuilder> {
+ fn union<'a, 'new, A: Allocator + Clone>(
+ v: Union<'a, &'static str, DefaultHashBuilder, A>,
+ ) -> Union<'a, &'new str, DefaultHashBuilder, A> {
v
}
- fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
+ fn drain<'new, A: Allocator + Clone>(
+ d: Drain<'static, &'static str, A>,
+ ) -> Drain<'new, &'new str, A> {
d
}
}
@@ -1905,6 +2048,23 @@ mod test_set {
}
#[test]
+ fn test_from_map() {
+ let mut a = crate::HashMap::new();
+ a.insert(1, ());
+ a.insert(2, ());
+ a.insert(3, ());
+ a.insert(4, ());
+
+ let a: HashSet<_> = a.into();
+
+ assert_eq!(a.len(), 4);
+ assert!(a.contains(&1));
+ assert!(a.contains(&2));
+ assert!(a.contains(&3));
+ assert!(a.contains(&4));
+ }
+
+ #[test]
fn test_from_iter() {
let xs = [1, 2, 2, 3, 4, 5, 6, 7, 8, 9];
@@ -2116,4 +2276,24 @@ mod test_set {
set.insert(19);
assert!(set.contains(&19));
}
+
+ #[test]
+ fn rehash_in_place() {
+ let mut set = HashSet::new();
+
+ for i in 0..224 {
+ set.insert(i);
+ }
+
+ assert_eq!(
+ set.capacity(),
+ 224,
+ "The set must be at or close to capacity to trigger a re hashing"
+ );
+
+ for i in 100..1400 {
+ set.remove(&(i - 100));
+ set.insert(i);
+ }
+ }
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-20 23:11:26 +0000