summaryrefslogtreecommitdiffstats
path: root/library/std/src/collections
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--library/std/src/collections/hash/map.rs3276
-rw-r--r--library/std/src/collections/hash/map/tests.rs1113
-rw-r--r--library/std/src/collections/hash/mod.rs4
-rw-r--r--library/std/src/collections/hash/set.rs1844
-rw-r--r--library/std/src/collections/hash/set/tests.rs498
-rw-r--r--library/std/src/collections/mod.rs446
6 files changed, 7181 insertions, 0 deletions
diff --git a/library/std/src/collections/hash/map.rs b/library/std/src/collections/hash/map.rs
new file mode 100644
index 000000000..db811343f
--- /dev/null
+++ b/library/std/src/collections/hash/map.rs
@@ -0,0 +1,3276 @@
+#[cfg(test)]
+mod tests;
+
+use self::Entry::*;
+
+use hashbrown::hash_map as base;
+
+use crate::borrow::Borrow;
+use crate::cell::Cell;
+use crate::collections::TryReserveError;
+use crate::collections::TryReserveErrorKind;
+use crate::fmt::{self, Debug};
+#[allow(deprecated)]
+use crate::hash::{BuildHasher, Hash, Hasher, SipHasher13};
+use crate::iter::FusedIterator;
+use crate::ops::Index;
+use crate::sys;
+
+/// A [hash map] implemented with quadratic probing and SIMD lookup.
+///
+/// By default, `HashMap` uses a hashing algorithm selected to provide
+/// resistance against HashDoS attacks. The algorithm is randomly seeded, and a
+/// reasonable best-effort is made to generate this seed from a high quality,
+/// secure source of randomness provided by the host without blocking the
+/// program. Because of this, the randomness of the seed depends on the output
+/// quality of the system's random number generator when the seed is created.
+/// In particular, seeds generated when the system's entropy pool is abnormally
+/// low such as during system boot may be of a lower quality.
+///
+/// The default hashing algorithm is currently SipHash 1-3, though this is
+/// subject to change at any point in the future. While its performance is very
+/// competitive for medium sized keys, other hashing algorithms will outperform
+/// it for small keys such as integers as well as large keys such as long
+/// strings, though those algorithms will typically *not* protect against
+/// attacks such as HashDoS.
+///
+/// The hashing algorithm can be replaced on a per-`HashMap` basis using the
+/// [`default`], [`with_hasher`], and [`with_capacity_and_hasher`] methods.
+/// There are many alternative [hashing algorithms available on crates.io].
+///
+/// It is required that the keys implement the [`Eq`] and [`Hash`] traits, although
+/// this can frequently be achieved by using `#[derive(PartialEq, Eq, Hash)]`.
+/// If you implement these yourself, it is important that the following
+/// property holds:
+///
+/// ```text
+/// k1 == k2 -> hash(k1) == hash(k2)
+/// ```
+///
+/// In other words, if two keys are equal, their hashes must be equal.
+///
+/// It is a logic error for a key to be modified in such a way that the key's
+/// hash, as determined by the [`Hash`] trait, or its equality, as determined by
+/// the [`Eq`] trait, changes while it is in the map. This is normally only
+/// possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code.
+/// The behavior resulting from such a logic error is not specified, but will
+/// be encapsulated to the `HashMap` that observed the logic error and not
+/// result in undefined behavior. This could include panics, incorrect results,
+/// aborts, memory leaks, and non-termination.
+///
+/// The hash table implementation is a Rust port of Google's [SwissTable].
+/// The original C++ version of SwissTable can be found [here], and this
+/// [CppCon talk] gives an overview of how the algorithm works.
+///
+/// [hash map]: crate::collections#use-a-hashmap-when
+/// [hashing algorithms available on crates.io]: https://crates.io/keywords/hasher
+/// [SwissTable]: https://abseil.io/blog/20180927-swisstables
+/// [here]: https://github.com/abseil/abseil-cpp/blob/master/absl/container/internal/raw_hash_set.h
+/// [CppCon talk]: https://www.youtube.com/watch?v=ncHmEUmJZf4
+///
+/// # Examples
+///
+/// ```
+/// use std::collections::HashMap;
+///
+/// // Type inference lets us omit an explicit type signature (which
+/// // would be `HashMap<String, String>` in this example).
+/// let mut book_reviews = HashMap::new();
+///
+/// // Review some books.
+/// book_reviews.insert(
+/// "Adventures of Huckleberry Finn".to_string(),
+/// "My favorite book.".to_string(),
+/// );
+/// book_reviews.insert(
+/// "Grimms' Fairy Tales".to_string(),
+/// "Masterpiece.".to_string(),
+/// );
+/// book_reviews.insert(
+/// "Pride and Prejudice".to_string(),
+/// "Very enjoyable.".to_string(),
+/// );
+/// book_reviews.insert(
+/// "The Adventures of Sherlock Holmes".to_string(),
+/// "Eye lyked it alot.".to_string(),
+/// );
+///
+/// // Check for a specific one.
+/// // When collections store owned values (String), they can still be
+/// // queried using references (&str).
+/// if !book_reviews.contains_key("Les Misérables") {
+/// println!("We've got {} reviews, but Les Misérables ain't one.",
+/// book_reviews.len());
+/// }
+///
+/// // oops, this review has a lot of spelling mistakes, let's delete it.
+/// book_reviews.remove("The Adventures of Sherlock Holmes");
+///
+/// // Look up the values associated with some keys.
+/// let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"];
+/// for &book in &to_find {
+/// match book_reviews.get(book) {
+/// Some(review) => println!("{book}: {review}"),
+/// None => println!("{book} is unreviewed.")
+/// }
+/// }
+///
+/// // Look up the value for a key (will panic if the key is not found).
+/// println!("Review for Jane: {}", book_reviews["Pride and Prejudice"]);
+///
+/// // Iterate over everything.
+/// for (book, review) in &book_reviews {
+/// println!("{book}: \"{review}\"");
+/// }
+/// ```
+///
+/// A `HashMap` with a known list of items can be initialized from an array:
+///
+/// ```
+/// use std::collections::HashMap;
+///
+/// let solar_distance = HashMap::from([
+/// ("Mercury", 0.4),
+/// ("Venus", 0.7),
+/// ("Earth", 1.0),
+/// ("Mars", 1.5),
+/// ]);
+/// ```
+///
+/// `HashMap` implements an [`Entry` API](#method.entry), which allows
+/// for complex methods of getting, setting, updating and removing keys and
+/// their values:
+///
+/// ```
+/// use std::collections::HashMap;
+///
+/// // type inference lets us omit an explicit type signature (which
+/// // would be `HashMap<&str, u8>` in this example).
+/// let mut player_stats = HashMap::new();
+///
+/// fn random_stat_buff() -> u8 {
+/// // could actually return some random value here - let's just return
+/// // some fixed value for now
+/// 42
+/// }
+///
+/// // insert a key only if it doesn't already exist
+/// player_stats.entry("health").or_insert(100);
+///
+/// // insert a key using a function that provides a new value only if it
+/// // doesn't already exist
+/// player_stats.entry("defence").or_insert_with(random_stat_buff);
+///
+/// // update a key, guarding against the key possibly not being set
+/// let stat = player_stats.entry("attack").or_insert(100);
+/// *stat += random_stat_buff();
+///
+/// // modify an entry before an insert with in-place mutation
+/// player_stats.entry("mana").and_modify(|mana| *mana += 200).or_insert(100);
+/// ```
+///
+/// The easiest way to use `HashMap` with a custom key type is to derive [`Eq`] and [`Hash`].
+/// We must also derive [`PartialEq`].
+///
+/// [`RefCell`]: crate::cell::RefCell
+/// [`Cell`]: crate::cell::Cell
+/// [`default`]: Default::default
+/// [`with_hasher`]: Self::with_hasher
+/// [`with_capacity_and_hasher`]: Self::with_capacity_and_hasher
+///
+/// ```
+/// use std::collections::HashMap;
+///
+/// #[derive(Hash, Eq, PartialEq, Debug)]
+/// struct Viking {
+/// name: String,
+/// country: String,
+/// }
+///
+/// impl Viking {
+/// /// Creates a new Viking.
+/// fn new(name: &str, country: &str) -> Viking {
+/// Viking { name: name.to_string(), country: country.to_string() }
+/// }
+/// }
+///
+/// // Use a HashMap to store the vikings' health points.
+/// let vikings = HashMap::from([
+/// (Viking::new("Einar", "Norway"), 25),
+/// (Viking::new("Olaf", "Denmark"), 24),
+/// (Viking::new("Harald", "Iceland"), 12),
+/// ]);
+///
+/// // Use derived implementation to print the status of the vikings.
+/// for (viking, health) in &vikings {
+/// println!("{viking:?} has {health} hp");
+/// }
+/// ```
+
+#[cfg_attr(not(test), rustc_diagnostic_item = "HashMap")]
+#[stable(feature = "rust1", since = "1.0.0")]
+#[rustc_insignificant_dtor]
+pub struct HashMap<K, V, S = RandomState> {
+ base: base::HashMap<K, V, S>,
+}
+
+impl<K, V> HashMap<K, V, RandomState> {
+ /// Creates an empty `HashMap`.
+ ///
+ /// The hash map is initially created with a capacity of 0, so it will not allocate until it
+ /// is first inserted into.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ /// let mut map: HashMap<&str, i32> = HashMap::new();
+ /// ```
+ #[inline]
+ #[must_use]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn new() -> HashMap<K, V, RandomState> {
+ Default::default()
+ }
+
+ /// Creates an empty `HashMap` with at least the specified capacity.
+ ///
+ /// The hash map will be able to hold at least `capacity` elements without
+ /// reallocating. This method is allowed to allocate for more elements than
+ /// `capacity`. If `capacity` is 0, the hash set will not allocate.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ /// let mut map: HashMap<&str, i32> = HashMap::with_capacity(10);
+ /// ```
+ #[inline]
+ #[must_use]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn with_capacity(capacity: usize) -> HashMap<K, V, RandomState> {
+ HashMap::with_capacity_and_hasher(capacity, Default::default())
+ }
+}
+
+impl<K, V, S> HashMap<K, V, S> {
+ /// Creates an empty `HashMap` which will use the given hash builder to hash
+ /// keys.
+ ///
+ /// The created map has the default initial capacity.
+ ///
+ /// Warning: `hash_builder` is normally randomly generated, and
+ /// is designed to allow HashMaps 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 std::collections::HashMap;
+ /// use std::collections::hash_map::RandomState;
+ ///
+ /// let s = RandomState::new();
+ /// let mut map = HashMap::with_hasher(s);
+ /// map.insert(1, 2);
+ /// ```
+ #[inline]
+ #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
+ pub fn with_hasher(hash_builder: S) -> HashMap<K, V, S> {
+ HashMap { base: base::HashMap::with_hasher(hash_builder) }
+ }
+
+ /// Creates an empty `HashMap` with at least the specified capacity, using
+ /// `hasher` to hash the keys.
+ ///
+ /// The hash map will be able to hold at least `capacity` elements without
+ /// reallocating. This method is allowed to allocate for more elements than
+ /// `capacity`. If `capacity` is 0, the hash map will not allocate.
+ ///
+ /// Warning: `hasher` is normally randomly generated, and
+ /// is designed to allow HashMaps 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 `hasher` passed should implement the [`BuildHasher`] trait for
+ /// the HashMap to be useful, see its documentation for details.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ /// use std::collections::hash_map::RandomState;
+ ///
+ /// let s = RandomState::new();
+ /// let mut map = HashMap::with_capacity_and_hasher(10, s);
+ /// map.insert(1, 2);
+ /// ```
+ #[inline]
+ #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
+ pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> HashMap<K, V, S> {
+ HashMap { base: base::HashMap::with_capacity_and_hasher(capacity, hasher) }
+ }
+
+ /// Returns the number of elements the map can hold without reallocating.
+ ///
+ /// This number is a lower bound; the `HashMap<K, V>` might be able to hold
+ /// more, but is guaranteed to be able to hold at least this many.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ /// let map: HashMap<i32, i32> = HashMap::with_capacity(100);
+ /// assert!(map.capacity() >= 100);
+ /// ```
+ #[inline]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn capacity(&self) -> usize {
+ self.base.capacity()
+ }
+
+ /// An iterator visiting all keys in arbitrary order.
+ /// The iterator element type is `&'a K`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let map = HashMap::from([
+ /// ("a", 1),
+ /// ("b", 2),
+ /// ("c", 3),
+ /// ]);
+ ///
+ /// for key in map.keys() {
+ /// println!("{key}");
+ /// }
+ /// ```
+ ///
+ /// # Performance
+ ///
+ /// In the current implementation, iterating over keys takes O(capacity) time
+ /// instead of O(len) because it internally visits empty buckets too.
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn keys(&self) -> Keys<'_, K, V> {
+ Keys { inner: self.iter() }
+ }
+
+ /// Creates a consuming iterator visiting all the keys in arbitrary order.
+ /// The map cannot be used after calling this.
+ /// The iterator element type is `K`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let map = HashMap::from([
+ /// ("a", 1),
+ /// ("b", 2),
+ /// ("c", 3),
+ /// ]);
+ ///
+ /// let mut vec: Vec<&str> = map.into_keys().collect();
+ /// // The `IntoKeys` iterator produces keys in arbitrary order, so the
+ /// // keys must be sorted to test them against a sorted array.
+ /// vec.sort_unstable();
+ /// assert_eq!(vec, ["a", "b", "c"]);
+ /// ```
+ ///
+ /// # Performance
+ ///
+ /// In the current implementation, iterating over keys takes O(capacity) time
+ /// instead of O(len) because it internally visits empty buckets too.
+ #[inline]
+ #[rustc_lint_query_instability]
+ #[stable(feature = "map_into_keys_values", since = "1.54.0")]
+ pub fn into_keys(self) -> IntoKeys<K, V> {
+ IntoKeys { inner: self.into_iter() }
+ }
+
+ /// An iterator visiting all values in arbitrary order.
+ /// The iterator element type is `&'a V`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let map = HashMap::from([
+ /// ("a", 1),
+ /// ("b", 2),
+ /// ("c", 3),
+ /// ]);
+ ///
+ /// for val in map.values() {
+ /// println!("{val}");
+ /// }
+ /// ```
+ ///
+ /// # Performance
+ ///
+ /// In the current implementation, iterating over values takes O(capacity) time
+ /// instead of O(len) because it internally visits empty buckets too.
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn values(&self) -> Values<'_, K, V> {
+ Values { inner: self.iter() }
+ }
+
+ /// An iterator visiting all values mutably in arbitrary order.
+ /// The iterator element type is `&'a mut V`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let mut map = HashMap::from([
+ /// ("a", 1),
+ /// ("b", 2),
+ /// ("c", 3),
+ /// ]);
+ ///
+ /// for val in map.values_mut() {
+ /// *val = *val + 10;
+ /// }
+ ///
+ /// for val in map.values() {
+ /// println!("{val}");
+ /// }
+ /// ```
+ ///
+ /// # Performance
+ ///
+ /// In the current implementation, iterating over values takes O(capacity) time
+ /// instead of O(len) because it internally visits empty buckets too.
+ #[stable(feature = "map_values_mut", since = "1.10.0")]
+ pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
+ ValuesMut { inner: self.iter_mut() }
+ }
+
+ /// Creates a consuming iterator visiting all the values in arbitrary order.
+ /// The map cannot be used after calling this.
+ /// The iterator element type is `V`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let map = HashMap::from([
+ /// ("a", 1),
+ /// ("b", 2),
+ /// ("c", 3),
+ /// ]);
+ ///
+ /// let mut vec: Vec<i32> = map.into_values().collect();
+ /// // The `IntoValues` iterator produces values in arbitrary order, so
+ /// // the values must be sorted to test them against a sorted array.
+ /// vec.sort_unstable();
+ /// assert_eq!(vec, [1, 2, 3]);
+ /// ```
+ ///
+ /// # Performance
+ ///
+ /// In the current implementation, iterating over values takes O(capacity) time
+ /// instead of O(len) because it internally visits empty buckets too.
+ #[inline]
+ #[rustc_lint_query_instability]
+ #[stable(feature = "map_into_keys_values", since = "1.54.0")]
+ pub fn into_values(self) -> IntoValues<K, V> {
+ IntoValues { inner: self.into_iter() }
+ }
+
+ /// An iterator visiting all key-value pairs in arbitrary order.
+ /// The iterator element type is `(&'a K, &'a V)`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let map = HashMap::from([
+ /// ("a", 1),
+ /// ("b", 2),
+ /// ("c", 3),
+ /// ]);
+ ///
+ /// for (key, val) in map.iter() {
+ /// println!("key: {key} val: {val}");
+ /// }
+ /// ```
+ ///
+ /// # Performance
+ ///
+ /// In the current implementation, iterating over map takes O(capacity) time
+ /// instead of O(len) because it internally visits empty buckets too.
+ #[rustc_lint_query_instability]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn iter(&self) -> Iter<'_, K, V> {
+ Iter { base: self.base.iter() }
+ }
+
+ /// An iterator visiting all key-value pairs in arbitrary order,
+ /// with mutable references to the values.
+ /// The iterator element type is `(&'a K, &'a mut V)`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let mut map = HashMap::from([
+ /// ("a", 1),
+ /// ("b", 2),
+ /// ("c", 3),
+ /// ]);
+ ///
+ /// // Update all values
+ /// for (_, val) in map.iter_mut() {
+ /// *val *= 2;
+ /// }
+ ///
+ /// for (key, val) in &map {
+ /// println!("key: {key} val: {val}");
+ /// }
+ /// ```
+ ///
+ /// # Performance
+ ///
+ /// In the current implementation, iterating over map takes O(capacity) time
+ /// instead of O(len) because it internally visits empty buckets too.
+ #[rustc_lint_query_instability]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
+ IterMut { base: self.base.iter_mut() }
+ }
+
+ /// Returns the number of elements in the map.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let mut a = HashMap::new();
+ /// assert_eq!(a.len(), 0);
+ /// a.insert(1, "a");
+ /// assert_eq!(a.len(), 1);
+ /// ```
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn len(&self) -> usize {
+ self.base.len()
+ }
+
+ /// Returns `true` if the map contains no elements.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let mut a = HashMap::new();
+ /// assert!(a.is_empty());
+ /// a.insert(1, "a");
+ /// assert!(!a.is_empty());
+ /// ```
+ #[inline]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn is_empty(&self) -> bool {
+ self.base.is_empty()
+ }
+
+ /// Clears the map, returning all key-value pairs as an iterator. Keeps the
+ /// allocated memory for reuse.
+ ///
+ /// If the returned iterator is dropped before being fully consumed, it
+ /// drops the remaining key-value pairs. The returned iterator keeps a
+ /// mutable borrow on the map to optimize its implementation.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let mut a = HashMap::new();
+ /// a.insert(1, "a");
+ /// a.insert(2, "b");
+ ///
+ /// for (k, v) in a.drain().take(1) {
+ /// assert!(k == 1 || k == 2);
+ /// assert!(v == "a" || v == "b");
+ /// }
+ ///
+ /// assert!(a.is_empty());
+ /// ```
+ #[inline]
+ #[rustc_lint_query_instability]
+ #[stable(feature = "drain", since = "1.6.0")]
+ pub fn drain(&mut self) -> Drain<'_, K, V> {
+ Drain { base: self.base.drain() }
+ }
+
+ /// Creates an iterator which uses a closure to determine if an element should be removed.
+ ///
+ /// If the closure returns true, the element is removed from the map and yielded.
+ /// If the closure returns false, or panics, the element remains in the map and will not be
+ /// yielded.
+ ///
+ /// Note that `drain_filter` lets you mutate every value in the filter closure, regardless of
+ /// whether you choose to keep or remove it.
+ ///
+ /// If the iterator is only partially consumed or not consumed at all, each of the remaining
+ /// elements will still be subjected to the closure and removed and dropped if it returns true.
+ ///
+ /// It is unspecified how many more elements will be subjected to the closure
+ /// if a panic occurs in the closure, or a panic occurs while dropping an element,
+ /// or if the `DrainFilter` value is leaked.
+ ///
+ /// # Examples
+ ///
+ /// Splitting a map into even and odd keys, reusing the original map:
+ ///
+ /// ```
+ /// #![feature(hash_drain_filter)]
+ /// use std::collections::HashMap;
+ ///
+ /// let mut map: HashMap<i32, i32> = (0..8).map(|x| (x, x)).collect();
+ /// let drained: HashMap<i32, i32> = map.drain_filter(|k, _v| k % 2 == 0).collect();
+ ///
+ /// let mut evens = drained.keys().copied().collect::<Vec<_>>();
+ /// let mut odds = map.keys().copied().collect::<Vec<_>>();
+ /// evens.sort();
+ /// odds.sort();
+ ///
+ /// assert_eq!(evens, vec![0, 2, 4, 6]);
+ /// assert_eq!(odds, vec![1, 3, 5, 7]);
+ /// ```
+ #[inline]
+ #[rustc_lint_query_instability]
+ #[unstable(feature = "hash_drain_filter", issue = "59618")]
+ pub fn drain_filter<F>(&mut self, pred: F) -> DrainFilter<'_, K, V, F>
+ where
+ F: FnMut(&K, &mut V) -> bool,
+ {
+ DrainFilter { base: self.base.drain_filter(pred) }
+ }
+
+ /// Retains only the elements specified by the predicate.
+ ///
+ /// In other words, remove all pairs `(k, v)` for which `f(&k, &mut v)` returns `false`.
+ /// The elements are visited in unsorted (and unspecified) order.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let mut map: HashMap<i32, i32> = (0..8).map(|x| (x, x*10)).collect();
+ /// map.retain(|&k, _| k % 2 == 0);
+ /// assert_eq!(map.len(), 4);
+ /// ```
+ ///
+ /// # Performance
+ ///
+ /// In the current implementation, this operation takes O(capacity) time
+ /// instead of O(len) because it internally visits empty buckets too.
+ #[inline]
+ #[rustc_lint_query_instability]
+ #[stable(feature = "retain_hash_collection", since = "1.18.0")]
+ pub fn retain<F>(&mut self, f: F)
+ where
+ F: FnMut(&K, &mut V) -> bool,
+ {
+ self.base.retain(f)
+ }
+
+ /// Clears the map, removing all key-value pairs. Keeps the allocated memory
+ /// for reuse.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let mut a = HashMap::new();
+ /// a.insert(1, "a");
+ /// a.clear();
+ /// assert!(a.is_empty());
+ /// ```
+ #[inline]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn clear(&mut self) {
+ self.base.clear();
+ }
+
+ /// Returns a reference to the map's [`BuildHasher`].
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ /// use std::collections::hash_map::RandomState;
+ ///
+ /// let hasher = RandomState::new();
+ /// let map: HashMap<i32, i32> = HashMap::with_hasher(hasher);
+ /// let hasher: &RandomState = map.hasher();
+ /// ```
+ #[inline]
+ #[stable(feature = "hashmap_public_hasher", since = "1.9.0")]
+ pub fn hasher(&self) -> &S {
+ self.base.hasher()
+ }
+}
+
+impl<K, V, S> HashMap<K, V, S>
+where
+ K: Eq + Hash,
+ S: BuildHasher,
+{
+ /// Reserves capacity for at least `additional` more elements to be inserted
+ /// in the `HashMap`. The collection may reserve more space to speculatively
+ /// avoid frequent reallocations. After calling `reserve`,
+ /// capacity will be greater than or equal to `self.len() + additional`.
+ /// Does nothing if capacity is already sufficient.
+ ///
+ /// # Panics
+ ///
+ /// Panics if the new allocation size overflows [`usize`].
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ /// let mut map: HashMap<&str, i32> = HashMap::new();
+ /// map.reserve(10);
+ /// ```
+ #[inline]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn reserve(&mut self, additional: usize) {
+ self.base.reserve(additional)
+ }
+
+ /// Tries to reserve capacity for at least `additional` more elements to be inserted
+ /// in the `HashMap`. The collection may reserve more space to speculatively
+ /// avoid frequent reallocations. After calling `reserve`,
+ /// capacity will be greater than or equal to `self.len() + additional` if
+ /// it returns `Ok(())`.
+ /// Does nothing if capacity is already sufficient.
+ ///
+ /// # Errors
+ ///
+ /// If the capacity overflows, or the allocator reports a failure, then an error
+ /// is returned.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let mut map: HashMap<&str, isize> = HashMap::new();
+ /// map.try_reserve(10).expect("why is the test harness OOMing on a handful of bytes?");
+ /// ```
+ #[inline]
+ #[stable(feature = "try_reserve", since = "1.57.0")]
+ pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
+ self.base.try_reserve(additional).map_err(map_try_reserve_error)
+ }
+
+ /// Shrinks the capacity of the map as much as possible. It will drop
+ /// down as much as possible while maintaining the internal rules
+ /// and possibly leaving some space in accordance with the resize policy.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let mut map: HashMap<i32, i32> = HashMap::with_capacity(100);
+ /// map.insert(1, 2);
+ /// map.insert(3, 4);
+ /// assert!(map.capacity() >= 100);
+ /// map.shrink_to_fit();
+ /// assert!(map.capacity() >= 2);
+ /// ```
+ #[inline]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn shrink_to_fit(&mut self) {
+ self.base.shrink_to_fit();
+ }
+
+ /// Shrinks the capacity of the map with a lower limit. It will drop
+ /// down no lower than the supplied limit while maintaining the internal rules
+ /// and possibly leaving some space in accordance with the resize policy.
+ ///
+ /// If the current capacity is less than the lower limit, this is a no-op.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let mut map: HashMap<i32, i32> = HashMap::with_capacity(100);
+ /// map.insert(1, 2);
+ /// map.insert(3, 4);
+ /// assert!(map.capacity() >= 100);
+ /// map.shrink_to(10);
+ /// assert!(map.capacity() >= 10);
+ /// map.shrink_to(0);
+ /// assert!(map.capacity() >= 2);
+ /// ```
+ #[inline]
+ #[stable(feature = "shrink_to", since = "1.56.0")]
+ pub fn shrink_to(&mut self, min_capacity: usize) {
+ self.base.shrink_to(min_capacity);
+ }
+
+ /// Gets the given key's corresponding entry in the map for in-place manipulation.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let mut letters = HashMap::new();
+ ///
+ /// for ch in "a short treatise on fungi".chars() {
+ /// letters.entry(ch).and_modify(|counter| *counter += 1).or_insert(1);
+ /// }
+ ///
+ /// assert_eq!(letters[&'s'], 2);
+ /// assert_eq!(letters[&'t'], 3);
+ /// assert_eq!(letters[&'u'], 1);
+ /// assert_eq!(letters.get(&'y'), None);
+ /// ```
+ #[inline]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {
+ map_entry(self.base.rustc_entry(key))
+ }
+
+ /// Returns a reference to the value corresponding to the key.
+ ///
+ /// The key may be any borrowed form of the map's key type, but
+ /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
+ /// the key type.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let mut map = HashMap::new();
+ /// map.insert(1, "a");
+ /// assert_eq!(map.get(&1), Some(&"a"));
+ /// assert_eq!(map.get(&2), None);
+ /// ```
+ #[stable(feature = "rust1", since = "1.0.0")]
+ #[inline]
+ pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
+ where
+ K: Borrow<Q>,
+ Q: Hash + Eq,
+ {
+ self.base.get(k)
+ }
+
+ /// Returns the key-value pair corresponding to the supplied key.
+ ///
+ /// The supplied key may be any borrowed form of the map's key type, but
+ /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
+ /// the key type.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let mut map = HashMap::new();
+ /// map.insert(1, "a");
+ /// assert_eq!(map.get_key_value(&1), Some((&1, &"a")));
+ /// assert_eq!(map.get_key_value(&2), None);
+ /// ```
+ #[inline]
+ #[stable(feature = "map_get_key_value", since = "1.40.0")]
+ pub fn get_key_value<Q: ?Sized>(&self, k: &Q) -> Option<(&K, &V)>
+ where
+ K: Borrow<Q>,
+ Q: Hash + Eq,
+ {
+ self.base.get_key_value(k)
+ }
+
+ /// Attempts to get mutable references to `N` values in the map at once.
+ ///
+ /// Returns an array of length `N` with the results of each query. For soundness, at most one
+ /// mutable reference will be returned to any value. `None` will be returned if any of the
+ /// keys are duplicates or missing.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// #![feature(map_many_mut)]
+ /// use std::collections::HashMap;
+ ///
+ /// let mut libraries = HashMap::new();
+ /// libraries.insert("Bodleian Library".to_string(), 1602);
+ /// libraries.insert("Athenæum".to_string(), 1807);
+ /// libraries.insert("Herzogin-Anna-Amalia-Bibliothek".to_string(), 1691);
+ /// libraries.insert("Library of Congress".to_string(), 1800);
+ ///
+ /// let got = libraries.get_many_mut([
+ /// "Athenæum",
+ /// "Library of Congress",
+ /// ]);
+ /// assert_eq!(
+ /// got,
+ /// Some([
+ /// &mut 1807,
+ /// &mut 1800,
+ /// ]),
+ /// );
+ ///
+ /// // Missing keys result in None
+ /// let got = libraries.get_many_mut([
+ /// "Athenæum",
+ /// "New York Public Library",
+ /// ]);
+ /// assert_eq!(got, None);
+ ///
+ /// // Duplicate keys result in None
+ /// let got = libraries.get_many_mut([
+ /// "Athenæum",
+ /// "Athenæum",
+ /// ]);
+ /// assert_eq!(got, None);
+ /// ```
+ #[inline]
+ #[unstable(feature = "map_many_mut", issue = "97601")]
+ pub fn get_many_mut<Q: ?Sized, const N: usize>(&mut self, ks: [&Q; N]) -> Option<[&'_ mut V; N]>
+ where
+ K: Borrow<Q>,
+ Q: Hash + Eq,
+ {
+ self.base.get_many_mut(ks)
+ }
+
+ /// Attempts to get mutable references to `N` values in the map at once, without validating that
+ /// the values are unique.
+ ///
+ /// Returns an array of length `N` with the results of each query. `None` will be returned if
+ /// any of the keys are missing.
+ ///
+ /// For a safe alternative see [`get_many_mut`](Self::get_many_mut).
+ ///
+ /// # Safety
+ ///
+ /// Calling this method with overlapping keys is *[undefined behavior]* even if the resulting
+ /// references are not used.
+ ///
+ /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// #![feature(map_many_mut)]
+ /// use std::collections::HashMap;
+ ///
+ /// let mut libraries = HashMap::new();
+ /// libraries.insert("Bodleian Library".to_string(), 1602);
+ /// libraries.insert("Athenæum".to_string(), 1807);
+ /// libraries.insert("Herzogin-Anna-Amalia-Bibliothek".to_string(), 1691);
+ /// libraries.insert("Library of Congress".to_string(), 1800);
+ ///
+ /// let got = libraries.get_many_mut([
+ /// "Athenæum",
+ /// "Library of Congress",
+ /// ]);
+ /// assert_eq!(
+ /// got,
+ /// Some([
+ /// &mut 1807,
+ /// &mut 1800,
+ /// ]),
+ /// );
+ ///
+ /// // Missing keys result in None
+ /// let got = libraries.get_many_mut([
+ /// "Athenæum",
+ /// "New York Public Library",
+ /// ]);
+ /// assert_eq!(got, None);
+ /// ```
+ #[inline]
+ #[unstable(feature = "map_many_mut", issue = "97601")]
+ pub unsafe fn get_many_unchecked_mut<Q: ?Sized, const N: usize>(
+ &mut self,
+ ks: [&Q; N],
+ ) -> Option<[&'_ mut V; N]>
+ where
+ K: Borrow<Q>,
+ Q: Hash + Eq,
+ {
+ self.base.get_many_unchecked_mut(ks)
+ }
+
+ /// Returns `true` if the map contains a value for the specified key.
+ ///
+ /// The key may be any borrowed form of the map's key type, but
+ /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
+ /// the key type.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let mut map = HashMap::new();
+ /// map.insert(1, "a");
+ /// assert_eq!(map.contains_key(&1), true);
+ /// assert_eq!(map.contains_key(&2), false);
+ /// ```
+ #[inline]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool
+ where
+ K: Borrow<Q>,
+ Q: Hash + Eq,
+ {
+ self.base.contains_key(k)
+ }
+
+ /// Returns a mutable reference to the value corresponding to the key.
+ ///
+ /// The key may be any borrowed form of the map's key type, but
+ /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
+ /// the key type.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let mut map = HashMap::new();
+ /// map.insert(1, "a");
+ /// if let Some(x) = map.get_mut(&1) {
+ /// *x = "b";
+ /// }
+ /// assert_eq!(map[&1], "b");
+ /// ```
+ #[inline]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
+ where
+ K: Borrow<Q>,
+ Q: Hash + Eq,
+ {
+ self.base.get_mut(k)
+ }
+
+ /// Inserts a key-value pair into the map.
+ ///
+ /// If the map did not have this key present, [`None`] is returned.
+ ///
+ /// If the map did have this key present, the value is updated, and the old
+ /// value is returned. The key is not updated, though; this matters for
+ /// types that can be `==` without being identical. See the [module-level
+ /// documentation] for more.
+ ///
+ /// [module-level documentation]: crate::collections#insert-and-complex-keys
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let mut map = HashMap::new();
+ /// assert_eq!(map.insert(37, "a"), None);
+ /// assert_eq!(map.is_empty(), false);
+ ///
+ /// map.insert(37, "b");
+ /// assert_eq!(map.insert(37, "c"), Some("b"));
+ /// assert_eq!(map[&37], "c");
+ /// ```
+ #[inline]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn insert(&mut self, k: K, v: V) -> Option<V> {
+ self.base.insert(k, v)
+ }
+
+ /// Tries to insert a key-value pair into the map, and returns
+ /// a mutable reference to the value in the entry.
+ ///
+ /// If the map already had this key present, nothing is updated, and
+ /// an error containing the occupied entry and the value is returned.
+ ///
+ /// # Examples
+ ///
+ /// Basic usage:
+ ///
+ /// ```
+ /// #![feature(map_try_insert)]
+ ///
+ /// use std::collections::HashMap;
+ ///
+ /// let mut map = HashMap::new();
+ /// assert_eq!(map.try_insert(37, "a").unwrap(), &"a");
+ ///
+ /// let err = map.try_insert(37, "b").unwrap_err();
+ /// assert_eq!(err.entry.key(), &37);
+ /// assert_eq!(err.entry.get(), &"a");
+ /// assert_eq!(err.value, "b");
+ /// ```
+ #[unstable(feature = "map_try_insert", issue = "82766")]
+ pub fn try_insert(&mut self, key: K, value: V) -> Result<&mut V, OccupiedError<'_, K, V>> {
+ match self.entry(key) {
+ Occupied(entry) => Err(OccupiedError { entry, value }),
+ Vacant(entry) => Ok(entry.insert(value)),
+ }
+ }
+
+ /// Removes a key from the map, returning the value at the key if the key
+ /// was previously in the map.
+ ///
+ /// The key may be any borrowed form of the map's key type, but
+ /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
+ /// the key type.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let mut map = HashMap::new();
+ /// map.insert(1, "a");
+ /// assert_eq!(map.remove(&1), Some("a"));
+ /// assert_eq!(map.remove(&1), None);
+ /// ```
+ #[inline]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V>
+ where
+ K: Borrow<Q>,
+ Q: Hash + Eq,
+ {
+ self.base.remove(k)
+ }
+
+ /// Removes a key from the map, returning the stored key and value if the
+ /// key was previously in the map.
+ ///
+ /// The key may be any borrowed form of the map's key type, but
+ /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
+ /// the key type.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// # fn main() {
+ /// let mut map = HashMap::new();
+ /// map.insert(1, "a");
+ /// assert_eq!(map.remove_entry(&1), Some((1, "a")));
+ /// assert_eq!(map.remove(&1), None);
+ /// # }
+ /// ```
+ #[inline]
+ #[stable(feature = "hash_map_remove_entry", since = "1.27.0")]
+ pub fn remove_entry<Q: ?Sized>(&mut self, k: &Q) -> Option<(K, V)>
+ where
+ K: Borrow<Q>,
+ Q: Hash + Eq,
+ {
+ self.base.remove_entry(k)
+ }
+}
+
+impl<K, V, S> HashMap<K, V, S>
+where
+ S: BuildHasher,
+{
+ /// Creates a raw entry builder for the HashMap.
+ ///
+ /// Raw entries provide the lowest level of control for searching and
+ /// manipulating a map. They must be manually initialized with a hash and
+ /// then manually searched. After this, insertions into a vacant entry
+ /// still require an owned key to be provided.
+ ///
+ /// Raw entries are useful for such exotic situations as:
+ ///
+ /// * Hash memoization
+ /// * Deferring the creation of an owned key until it is known to be required
+ /// * Using a search key that doesn't work with the Borrow trait
+ /// * Using custom comparison logic without newtype wrappers
+ ///
+ /// Because raw entries provide much more low-level control, it's much easier
+ /// to put the HashMap into an inconsistent state which, while memory-safe,
+ /// will cause the map to produce seemingly random results. Higher-level and
+ /// more foolproof APIs like `entry` should be preferred when possible.
+ ///
+ /// In particular, the hash used to initialized the raw entry must still be
+ /// consistent with the hash of the key that is ultimately stored in the entry.
+ /// This is because implementations of HashMap may need to recompute hashes
+ /// when resizing, at which point only the keys are available.
+ ///
+ /// Raw entries give mutable access to the keys. This must not be used
+ /// to modify how the key would compare or hash, as the map will not re-evaluate
+ /// where the key should go, meaning the keys may become "lost" if their
+ /// location does not reflect their state. For instance, if you change a key
+ /// so that the map now contains keys which compare equal, search may start
+ /// acting erratically, with two keys randomly masking each other. Implementations
+ /// are free to assume this doesn't happen (within the limits of memory-safety).
+ #[inline]
+ #[unstable(feature = "hash_raw_entry", issue = "56167")]
+ pub fn raw_entry_mut(&mut self) -> RawEntryBuilderMut<'_, K, V, S> {
+ RawEntryBuilderMut { map: self }
+ }
+
+ /// Creates a raw immutable entry builder for the HashMap.
+ ///
+ /// Raw entries provide the lowest level of control for searching and
+ /// manipulating a map. They must be manually initialized with a hash and
+ /// then manually searched.
+ ///
+ /// This is useful for
+ /// * Hash memoization
+ /// * Using a search key that doesn't work with the Borrow trait
+ /// * Using custom comparison logic without newtype wrappers
+ ///
+ /// Unless you are in such a situation, higher-level and more foolproof APIs like
+ /// `get` should be preferred.
+ ///
+ /// Immutable raw entries have very limited use; you might instead want `raw_entry_mut`.
+ #[inline]
+ #[unstable(feature = "hash_raw_entry", issue = "56167")]
+ pub fn raw_entry(&self) -> RawEntryBuilder<'_, K, V, S> {
+ RawEntryBuilder { map: self }
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<K, V, S> Clone for HashMap<K, V, S>
+where
+ K: Clone,
+ V: Clone,
+ S: Clone,
+{
+ #[inline]
+ fn clone(&self) -> Self {
+ Self { base: self.base.clone() }
+ }
+
+ #[inline]
+ fn clone_from(&mut self, other: &Self) {
+ self.base.clone_from(&other.base);
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<K, V, S> PartialEq for HashMap<K, V, S>
+where
+ K: Eq + Hash,
+ V: PartialEq,
+ S: BuildHasher,
+{
+ fn eq(&self, other: &HashMap<K, V, S>) -> bool {
+ if self.len() != other.len() {
+ return false;
+ }
+
+ self.iter().all(|(key, value)| other.get(key).map_or(false, |v| *value == *v))
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<K, V, S> Eq for HashMap<K, V, S>
+where
+ K: Eq + Hash,
+ V: Eq,
+ S: BuildHasher,
+{
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<K, V, S> Debug for HashMap<K, V, S>
+where
+ K: Debug,
+ V: Debug,
+{
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_map().entries(self.iter()).finish()
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<K, V, S> Default for HashMap<K, V, S>
+where
+ S: Default,
+{
+ /// Creates an empty `HashMap<K, V, S>`, with the `Default` value for the hasher.
+ #[inline]
+ fn default() -> HashMap<K, V, S> {
+ HashMap::with_hasher(Default::default())
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<K, Q: ?Sized, V, S> Index<&Q> for HashMap<K, V, S>
+where
+ K: Eq + Hash + Borrow<Q>,
+ Q: Eq + Hash,
+ S: BuildHasher,
+{
+ type Output = V;
+
+ /// Returns a reference to the value corresponding to the supplied key.
+ ///
+ /// # Panics
+ ///
+ /// Panics if the key is not present in the `HashMap`.
+ #[inline]
+ fn index(&self, key: &Q) -> &V {
+ self.get(key).expect("no entry found for key")
+ }
+}
+
+#[stable(feature = "std_collections_from_array", since = "1.56.0")]
+// Note: as what is currently the most convenient built-in way to construct
+// a HashMap, a simple usage of this function must not *require* the user
+// to provide a type annotation in order to infer the third type parameter
+// (the hasher parameter, conventionally "S").
+// To that end, this impl is defined using RandomState as the concrete
+// type of S, rather than being generic over `S: BuildHasher + Default`.
+// It is expected that users who want to specify a hasher will manually use
+// `with_capacity_and_hasher`.
+// If type parameter defaults worked on impls, and if type parameter
+// defaults could be mixed with const generics, then perhaps
+// this could be generalized.
+// See also the equivalent impl on HashSet.
+impl<K, V, const N: usize> From<[(K, V); N]> for HashMap<K, V, RandomState>
+where
+ K: Eq + Hash,
+{
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let map1 = HashMap::from([(1, 2), (3, 4)]);
+ /// let map2: HashMap<_, _> = [(1, 2), (3, 4)].into();
+ /// assert_eq!(map1, map2);
+ /// ```
+ fn from(arr: [(K, V); N]) -> Self {
+ Self::from_iter(arr)
+ }
+}
+
+/// An iterator over the entries of a `HashMap`.
+///
+/// This `struct` is created by the [`iter`] method on [`HashMap`]. See its
+/// documentation for more.
+///
+/// [`iter`]: HashMap::iter
+///
+/// # Example
+///
+/// ```
+/// use std::collections::HashMap;
+///
+/// let map = HashMap::from([
+/// ("a", 1),
+/// ]);
+/// let iter = map.iter();
+/// ```
+#[stable(feature = "rust1", since = "1.0.0")]
+pub struct Iter<'a, K: 'a, V: 'a> {
+ base: base::Iter<'a, K, V>,
+}
+
+// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<K, V> Clone for Iter<'_, K, V> {
+ #[inline]
+ fn clone(&self) -> Self {
+ Iter { base: self.base.clone() }
+ }
+}
+
+#[stable(feature = "std_debug", since = "1.16.0")]
+impl<K: Debug, V: Debug> fmt::Debug for Iter<'_, K, V> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_list().entries(self.clone()).finish()
+ }
+}
+
+/// A mutable iterator over the entries of a `HashMap`.
+///
+/// This `struct` is created by the [`iter_mut`] method on [`HashMap`]. See its
+/// documentation for more.
+///
+/// [`iter_mut`]: HashMap::iter_mut
+///
+/// # Example
+///
+/// ```
+/// use std::collections::HashMap;
+///
+/// let mut map = HashMap::from([
+/// ("a", 1),
+/// ]);
+/// let iter = map.iter_mut();
+/// ```
+#[stable(feature = "rust1", since = "1.0.0")]
+pub struct IterMut<'a, K: 'a, V: 'a> {
+ base: base::IterMut<'a, K, V>,
+}
+
+impl<'a, K, V> IterMut<'a, K, V> {
+ /// Returns an iterator of references over the remaining items.
+ #[inline]
+ pub(super) fn iter(&self) -> Iter<'_, K, V> {
+ Iter { base: self.base.rustc_iter() }
+ }
+}
+
+/// An owning iterator over the entries of a `HashMap`.
+///
+/// This `struct` is created by the [`into_iter`] method on [`HashMap`]
+/// (provided by the [`IntoIterator`] trait). See its documentation for more.
+///
+/// [`into_iter`]: IntoIterator::into_iter
+/// [`IntoIterator`]: crate::iter::IntoIterator
+///
+/// # Example
+///
+/// ```
+/// use std::collections::HashMap;
+///
+/// let map = HashMap::from([
+/// ("a", 1),
+/// ]);
+/// let iter = map.into_iter();
+/// ```
+#[stable(feature = "rust1", since = "1.0.0")]
+pub struct IntoIter<K, V> {
+ base: base::IntoIter<K, V>,
+}
+
+impl<K, V> IntoIter<K, V> {
+ /// Returns an iterator of references over the remaining items.
+ #[inline]
+ pub(super) fn iter(&self) -> Iter<'_, K, V> {
+ Iter { base: self.base.rustc_iter() }
+ }
+}
+
+/// An iterator over the keys of a `HashMap`.
+///
+/// This `struct` is created by the [`keys`] method on [`HashMap`]. See its
+/// documentation for more.
+///
+/// [`keys`]: HashMap::keys
+///
+/// # Example
+///
+/// ```
+/// use std::collections::HashMap;
+///
+/// let map = HashMap::from([
+/// ("a", 1),
+/// ]);
+/// let iter_keys = map.keys();
+/// ```
+#[stable(feature = "rust1", since = "1.0.0")]
+pub struct Keys<'a, K: 'a, V: 'a> {
+ inner: Iter<'a, K, V>,
+}
+
+// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<K, V> Clone for Keys<'_, K, V> {
+ #[inline]
+ fn clone(&self) -> Self {
+ Keys { inner: self.inner.clone() }
+ }
+}
+
+#[stable(feature = "std_debug", since = "1.16.0")]
+impl<K: Debug, V> fmt::Debug for Keys<'_, K, V> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_list().entries(self.clone()).finish()
+ }
+}
+
+/// An iterator over the values of a `HashMap`.
+///
+/// This `struct` is created by the [`values`] method on [`HashMap`]. See its
+/// documentation for more.
+///
+/// [`values`]: HashMap::values
+///
+/// # Example
+///
+/// ```
+/// use std::collections::HashMap;
+///
+/// let map = HashMap::from([
+/// ("a", 1),
+/// ]);
+/// let iter_values = map.values();
+/// ```
+#[stable(feature = "rust1", since = "1.0.0")]
+pub struct Values<'a, K: 'a, V: 'a> {
+ inner: Iter<'a, K, V>,
+}
+
+// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<K, V> Clone for Values<'_, K, V> {
+ #[inline]
+ fn clone(&self) -> Self {
+ Values { inner: self.inner.clone() }
+ }
+}
+
+#[stable(feature = "std_debug", since = "1.16.0")]
+impl<K, V: Debug> fmt::Debug for Values<'_, K, V> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_list().entries(self.clone()).finish()
+ }
+}
+
+/// A draining iterator over the entries of a `HashMap`.
+///
+/// This `struct` is created by the [`drain`] method on [`HashMap`]. See its
+/// documentation for more.
+///
+/// [`drain`]: HashMap::drain
+///
+/// # Example
+///
+/// ```
+/// use std::collections::HashMap;
+///
+/// let mut map = HashMap::from([
+/// ("a", 1),
+/// ]);
+/// let iter = map.drain();
+/// ```
+#[stable(feature = "drain", since = "1.6.0")]
+pub struct Drain<'a, K: 'a, V: 'a> {
+ base: base::Drain<'a, K, V>,
+}
+
+impl<'a, K, V> Drain<'a, K, V> {
+ /// Returns an iterator of references over the remaining items.
+ #[inline]
+ pub(super) fn iter(&self) -> Iter<'_, K, V> {
+ Iter { base: self.base.rustc_iter() }
+ }
+}
+
+/// A draining, filtering iterator over the entries of a `HashMap`.
+///
+/// This `struct` is created by the [`drain_filter`] method on [`HashMap`].
+///
+/// [`drain_filter`]: HashMap::drain_filter
+///
+/// # Example
+///
+/// ```
+/// #![feature(hash_drain_filter)]
+///
+/// use std::collections::HashMap;
+///
+/// let mut map = HashMap::from([
+/// ("a", 1),
+/// ]);
+/// let iter = map.drain_filter(|_k, v| *v % 2 == 0);
+/// ```
+#[unstable(feature = "hash_drain_filter", issue = "59618")]
+pub struct DrainFilter<'a, K, V, F>
+where
+ F: FnMut(&K, &mut V) -> bool,
+{
+ base: base::DrainFilter<'a, K, V, F>,
+}
+
+/// A mutable iterator over the values of a `HashMap`.
+///
+/// This `struct` is created by the [`values_mut`] method on [`HashMap`]. See its
+/// documentation for more.
+///
+/// [`values_mut`]: HashMap::values_mut
+///
+/// # Example
+///
+/// ```
+/// use std::collections::HashMap;
+///
+/// let mut map = HashMap::from([
+/// ("a", 1),
+/// ]);
+/// let iter_values = map.values_mut();
+/// ```
+#[stable(feature = "map_values_mut", since = "1.10.0")]
+pub struct ValuesMut<'a, K: 'a, V: 'a> {
+ inner: IterMut<'a, K, V>,
+}
+
+/// An owning iterator over the keys of a `HashMap`.
+///
+/// This `struct` is created by the [`into_keys`] method on [`HashMap`].
+/// See its documentation for more.
+///
+/// [`into_keys`]: HashMap::into_keys
+///
+/// # Example
+///
+/// ```
+/// use std::collections::HashMap;
+///
+/// let map = HashMap::from([
+/// ("a", 1),
+/// ]);
+/// let iter_keys = map.into_keys();
+/// ```
+#[stable(feature = "map_into_keys_values", since = "1.54.0")]
+pub struct IntoKeys<K, V> {
+ inner: IntoIter<K, V>,
+}
+
+/// An owning iterator over the values of a `HashMap`.
+///
+/// This `struct` is created by the [`into_values`] method on [`HashMap`].
+/// See its documentation for more.
+///
+/// [`into_values`]: HashMap::into_values
+///
+/// # Example
+///
+/// ```
+/// use std::collections::HashMap;
+///
+/// let map = HashMap::from([
+/// ("a", 1),
+/// ]);
+/// let iter_keys = map.into_values();
+/// ```
+#[stable(feature = "map_into_keys_values", since = "1.54.0")]
+pub struct IntoValues<K, V> {
+ inner: IntoIter<K, V>,
+}
+
+/// A builder for computing where in a HashMap a key-value pair would be stored.
+///
+/// See the [`HashMap::raw_entry_mut`] docs for usage examples.
+#[unstable(feature = "hash_raw_entry", issue = "56167")]
+pub struct RawEntryBuilderMut<'a, K: 'a, V: 'a, S: 'a> {
+ map: &'a mut HashMap<K, V, S>,
+}
+
+/// A view into a single entry in a map, which may either be vacant or occupied.
+///
+/// This is a lower-level version of [`Entry`].
+///
+/// This `enum` is constructed through the [`raw_entry_mut`] method on [`HashMap`],
+/// then calling one of the methods of that [`RawEntryBuilderMut`].
+///
+/// [`raw_entry_mut`]: HashMap::raw_entry_mut
+#[unstable(feature = "hash_raw_entry", issue = "56167")]
+pub enum RawEntryMut<'a, K: 'a, V: 'a, S: 'a> {
+ /// An occupied entry.
+ Occupied(RawOccupiedEntryMut<'a, K, V, S>),
+ /// A vacant entry.
+ Vacant(RawVacantEntryMut<'a, K, V, S>),
+}
+
+/// A view into an occupied entry in a `HashMap`.
+/// It is part of the [`RawEntryMut`] enum.
+#[unstable(feature = "hash_raw_entry", issue = "56167")]
+pub struct RawOccupiedEntryMut<'a, K: 'a, V: 'a, S: 'a> {
+ base: base::RawOccupiedEntryMut<'a, K, V, S>,
+}
+
+/// A view into a vacant entry in a `HashMap`.
+/// It is part of the [`RawEntryMut`] enum.
+#[unstable(feature = "hash_raw_entry", issue = "56167")]
+pub struct RawVacantEntryMut<'a, K: 'a, V: 'a, S: 'a> {
+ base: base::RawVacantEntryMut<'a, K, V, S>,
+}
+
+/// A builder for computing where in a HashMap a key-value pair would be stored.
+///
+/// See the [`HashMap::raw_entry`] docs for usage examples.
+#[unstable(feature = "hash_raw_entry", issue = "56167")]
+pub struct RawEntryBuilder<'a, K: 'a, V: 'a, S: 'a> {
+ map: &'a HashMap<K, V, S>,
+}
+
+impl<'a, K, V, S> RawEntryBuilderMut<'a, K, V, S>
+where
+ S: BuildHasher,
+{
+ /// Creates a `RawEntryMut` from the given key.
+ #[inline]
+ #[unstable(feature = "hash_raw_entry", issue = "56167")]
+ pub fn from_key<Q: ?Sized>(self, k: &Q) -> RawEntryMut<'a, K, V, S>
+ where
+ K: Borrow<Q>,
+ Q: Hash + Eq,
+ {
+ map_raw_entry(self.map.base.raw_entry_mut().from_key(k))
+ }
+
+ /// Creates a `RawEntryMut` from the given key and its hash.
+ #[inline]
+ #[unstable(feature = "hash_raw_entry", issue = "56167")]
+ pub fn from_key_hashed_nocheck<Q: ?Sized>(self, hash: u64, k: &Q) -> RawEntryMut<'a, K, V, S>
+ where
+ K: Borrow<Q>,
+ Q: Eq,
+ {
+ map_raw_entry(self.map.base.raw_entry_mut().from_key_hashed_nocheck(hash, k))
+ }
+
+ /// Creates a `RawEntryMut` from the given hash.
+ #[inline]
+ #[unstable(feature = "hash_raw_entry", issue = "56167")]
+ pub fn from_hash<F>(self, hash: u64, is_match: F) -> RawEntryMut<'a, K, V, S>
+ where
+ for<'b> F: FnMut(&'b K) -> bool,
+ {
+ map_raw_entry(self.map.base.raw_entry_mut().from_hash(hash, is_match))
+ }
+}
+
+impl<'a, K, V, S> RawEntryBuilder<'a, K, V, S>
+where
+ S: BuildHasher,
+{
+ /// Access an entry by key.
+ #[inline]
+ #[unstable(feature = "hash_raw_entry", issue = "56167")]
+ pub fn from_key<Q: ?Sized>(self, k: &Q) -> Option<(&'a K, &'a V)>
+ where
+ K: Borrow<Q>,
+ Q: Hash + Eq,
+ {
+ self.map.base.raw_entry().from_key(k)
+ }
+
+ /// Access an entry by a key and its hash.
+ #[inline]
+ #[unstable(feature = "hash_raw_entry", issue = "56167")]
+ pub fn from_key_hashed_nocheck<Q: ?Sized>(self, hash: u64, k: &Q) -> Option<(&'a K, &'a V)>
+ where
+ K: Borrow<Q>,
+ Q: Hash + Eq,
+ {
+ self.map.base.raw_entry().from_key_hashed_nocheck(hash, k)
+ }
+
+ /// Access an entry by hash.
+ #[inline]
+ #[unstable(feature = "hash_raw_entry", issue = "56167")]
+ pub fn from_hash<F>(self, hash: u64, is_match: F) -> Option<(&'a K, &'a V)>
+ where
+ F: FnMut(&K) -> bool,
+ {
+ self.map.base.raw_entry().from_hash(hash, is_match)
+ }
+}
+
+impl<'a, K, V, S> RawEntryMut<'a, K, V, S> {
+ /// Ensures a value is in the entry by inserting the default if empty, and returns
+ /// mutable references to the key and value in the entry.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// #![feature(hash_raw_entry)]
+ /// use std::collections::HashMap;
+ ///
+ /// let mut map: HashMap<&str, u32> = HashMap::new();
+ ///
+ /// map.raw_entry_mut().from_key("poneyland").or_insert("poneyland", 3);
+ /// assert_eq!(map["poneyland"], 3);
+ ///
+ /// *map.raw_entry_mut().from_key("poneyland").or_insert("poneyland", 10).1 *= 2;
+ /// assert_eq!(map["poneyland"], 6);
+ /// ```
+ #[inline]
+ #[unstable(feature = "hash_raw_entry", issue = "56167")]
+ pub fn or_insert(self, default_key: K, default_val: V) -> (&'a mut K, &'a mut V)
+ where
+ K: Hash,
+ S: BuildHasher,
+ {
+ match self {
+ RawEntryMut::Occupied(entry) => entry.into_key_value(),
+ RawEntryMut::Vacant(entry) => entry.insert(default_key, default_val),
+ }
+ }
+
+ /// Ensures a value is in the entry by inserting the result of the default function if empty,
+ /// and returns mutable references to the key and value in the entry.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// #![feature(hash_raw_entry)]
+ /// use std::collections::HashMap;
+ ///
+ /// let mut map: HashMap<&str, String> = HashMap::new();
+ ///
+ /// map.raw_entry_mut().from_key("poneyland").or_insert_with(|| {
+ /// ("poneyland", "hoho".to_string())
+ /// });
+ ///
+ /// assert_eq!(map["poneyland"], "hoho".to_string());
+ /// ```
+ #[inline]
+ #[unstable(feature = "hash_raw_entry", issue = "56167")]
+ pub fn or_insert_with<F>(self, default: F) -> (&'a mut K, &'a mut V)
+ where
+ F: FnOnce() -> (K, V),
+ K: Hash,
+ S: BuildHasher,
+ {
+ match self {
+ RawEntryMut::Occupied(entry) => entry.into_key_value(),
+ RawEntryMut::Vacant(entry) => {
+ let (k, v) = default();
+ entry.insert(k, v)
+ }
+ }
+ }
+
+ /// Provides in-place mutable access to an occupied entry before any
+ /// potential inserts into the map.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// #![feature(hash_raw_entry)]
+ /// use std::collections::HashMap;
+ ///
+ /// let mut map: HashMap<&str, u32> = HashMap::new();
+ ///
+ /// map.raw_entry_mut()
+ /// .from_key("poneyland")
+ /// .and_modify(|_k, v| { *v += 1 })
+ /// .or_insert("poneyland", 42);
+ /// assert_eq!(map["poneyland"], 42);
+ ///
+ /// map.raw_entry_mut()
+ /// .from_key("poneyland")
+ /// .and_modify(|_k, v| { *v += 1 })
+ /// .or_insert("poneyland", 0);
+ /// assert_eq!(map["poneyland"], 43);
+ /// ```
+ #[inline]
+ #[unstable(feature = "hash_raw_entry", issue = "56167")]
+ pub fn and_modify<F>(self, f: F) -> Self
+ where
+ F: FnOnce(&mut K, &mut V),
+ {
+ match self {
+ RawEntryMut::Occupied(mut entry) => {
+ {
+ let (k, v) = entry.get_key_value_mut();
+ f(k, v);
+ }
+ RawEntryMut::Occupied(entry)
+ }
+ RawEntryMut::Vacant(entry) => RawEntryMut::Vacant(entry),
+ }
+ }
+}
+
+impl<'a, K, V, S> RawOccupiedEntryMut<'a, K, V, S> {
+ /// Gets a reference to the key in the entry.
+ #[inline]
+ #[must_use]
+ #[unstable(feature = "hash_raw_entry", issue = "56167")]
+ pub fn key(&self) -> &K {
+ self.base.key()
+ }
+
+ /// Gets a mutable reference to the key in the entry.
+ #[inline]
+ #[must_use]
+ #[unstable(feature = "hash_raw_entry", issue = "56167")]
+ pub fn key_mut(&mut self) -> &mut K {
+ self.base.key_mut()
+ }
+
+ /// Converts the entry into a mutable reference to the key in the entry
+ /// with a lifetime bound to the map itself.
+ #[inline]
+ #[must_use = "`self` will be dropped if the result is not used"]
+ #[unstable(feature = "hash_raw_entry", issue = "56167")]
+ pub fn into_key(self) -> &'a mut K {
+ self.base.into_key()
+ }
+
+ /// Gets a reference to the value in the entry.
+ #[inline]
+ #[must_use]
+ #[unstable(feature = "hash_raw_entry", issue = "56167")]
+ pub fn get(&self) -> &V {
+ self.base.get()
+ }
+
+ /// Converts the `OccupiedEntry` into a mutable reference to the value in the entry
+ /// with a lifetime bound to the map itself.
+ #[inline]
+ #[must_use = "`self` will be dropped if the result is not used"]
+ #[unstable(feature = "hash_raw_entry", issue = "56167")]
+ pub fn into_mut(self) -> &'a mut V {
+ self.base.into_mut()
+ }
+
+ /// Gets a mutable reference to the value in the entry.
+ #[inline]
+ #[must_use]
+ #[unstable(feature = "hash_raw_entry", issue = "56167")]
+ pub fn get_mut(&mut self) -> &mut V {
+ self.base.get_mut()
+ }
+
+ /// Gets a reference to the key and value in the entry.
+ #[inline]
+ #[must_use]
+ #[unstable(feature = "hash_raw_entry", issue = "56167")]
+ pub fn get_key_value(&mut self) -> (&K, &V) {
+ self.base.get_key_value()
+ }
+
+ /// Gets a mutable reference to the key and value in the entry.
+ #[inline]
+ #[unstable(feature = "hash_raw_entry", issue = "56167")]
+ pub fn get_key_value_mut(&mut self) -> (&mut K, &mut V) {
+ self.base.get_key_value_mut()
+ }
+
+ /// Converts the `OccupiedEntry` into a mutable reference to the key and value in the entry
+ /// with a lifetime bound to the map itself.
+ #[inline]
+ #[must_use = "`self` will be dropped if the result is not used"]
+ #[unstable(feature = "hash_raw_entry", issue = "56167")]
+ pub fn into_key_value(self) -> (&'a mut K, &'a mut V) {
+ self.base.into_key_value()
+ }
+
+ /// Sets the value of the entry, and returns the entry's old value.
+ #[inline]
+ #[unstable(feature = "hash_raw_entry", issue = "56167")]
+ pub fn insert(&mut self, value: V) -> V {
+ self.base.insert(value)
+ }
+
+ /// Sets the value of the entry, and returns the entry's old value.
+ #[inline]
+ #[unstable(feature = "hash_raw_entry", issue = "56167")]
+ pub fn insert_key(&mut self, key: K) -> K {
+ self.base.insert_key(key)
+ }
+
+ /// Takes the value out of the entry, and returns it.
+ #[inline]
+ #[unstable(feature = "hash_raw_entry", issue = "56167")]
+ pub fn remove(self) -> V {
+ self.base.remove()
+ }
+
+ /// Take the ownership of the key and value from the map.
+ #[inline]
+ #[unstable(feature = "hash_raw_entry", issue = "56167")]
+ pub fn remove_entry(self) -> (K, V) {
+ self.base.remove_entry()
+ }
+}
+
+impl<'a, K, V, S> RawVacantEntryMut<'a, K, V, S> {
+ /// Sets the value of the entry with the `VacantEntry`'s key,
+ /// and returns a mutable reference to it.
+ #[inline]
+ #[unstable(feature = "hash_raw_entry", issue = "56167")]
+ pub fn insert(self, key: K, value: V) -> (&'a mut K, &'a mut V)
+ where
+ K: Hash,
+ S: BuildHasher,
+ {
+ self.base.insert(key, value)
+ }
+
+ /// Sets the value of the entry with the VacantEntry's key,
+ /// and returns a mutable reference to it.
+ #[inline]
+ #[unstable(feature = "hash_raw_entry", issue = "56167")]
+ pub fn insert_hashed_nocheck(self, hash: u64, key: K, value: V) -> (&'a mut K, &'a mut V)
+ where
+ K: Hash,
+ S: BuildHasher,
+ {
+ self.base.insert_hashed_nocheck(hash, key, value)
+ }
+}
+
+#[unstable(feature = "hash_raw_entry", issue = "56167")]
+impl<K, V, S> Debug for RawEntryBuilderMut<'_, K, V, S> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_struct("RawEntryBuilder").finish_non_exhaustive()
+ }
+}
+
+#[unstable(feature = "hash_raw_entry", issue = "56167")]
+impl<K: Debug, V: Debug, S> Debug for RawEntryMut<'_, K, V, S> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ match *self {
+ RawEntryMut::Vacant(ref v) => f.debug_tuple("RawEntry").field(v).finish(),
+ RawEntryMut::Occupied(ref o) => f.debug_tuple("RawEntry").field(o).finish(),
+ }
+ }
+}
+
+#[unstable(feature = "hash_raw_entry", issue = "56167")]
+impl<K: Debug, V: Debug, S> Debug for RawOccupiedEntryMut<'_, K, V, S> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_struct("RawOccupiedEntryMut")
+ .field("key", self.key())
+ .field("value", self.get())
+ .finish_non_exhaustive()
+ }
+}
+
+#[unstable(feature = "hash_raw_entry", issue = "56167")]
+impl<K, V, S> Debug for RawVacantEntryMut<'_, K, V, S> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_struct("RawVacantEntryMut").finish_non_exhaustive()
+ }
+}
+
+#[unstable(feature = "hash_raw_entry", issue = "56167")]
+impl<K, V, S> Debug for RawEntryBuilder<'_, K, V, S> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_struct("RawEntryBuilder").finish_non_exhaustive()
+ }
+}
+
+/// A view into a single entry in a map, which may either be vacant or occupied.
+///
+/// This `enum` is constructed from the [`entry`] method on [`HashMap`].
+///
+/// [`entry`]: HashMap::entry
+#[stable(feature = "rust1", since = "1.0.0")]
+#[cfg_attr(not(test), rustc_diagnostic_item = "HashMapEntry")]
+pub enum Entry<'a, K: 'a, V: 'a> {
+ /// An occupied entry.
+ #[stable(feature = "rust1", since = "1.0.0")]
+ Occupied(#[stable(feature = "rust1", since = "1.0.0")] OccupiedEntry<'a, K, V>),
+
+ /// A vacant entry.
+ #[stable(feature = "rust1", since = "1.0.0")]
+ Vacant(#[stable(feature = "rust1", since = "1.0.0")] VacantEntry<'a, K, V>),
+}
+
+#[stable(feature = "debug_hash_map", since = "1.12.0")]
+impl<K: Debug, V: Debug> Debug for Entry<'_, K, V> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ match *self {
+ Vacant(ref v) => f.debug_tuple("Entry").field(v).finish(),
+ Occupied(ref o) => f.debug_tuple("Entry").field(o).finish(),
+ }
+ }
+}
+
+/// A view into an occupied entry in a `HashMap`.
+/// It is part of the [`Entry`] enum.
+#[stable(feature = "rust1", since = "1.0.0")]
+pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
+ base: base::RustcOccupiedEntry<'a, K, V>,
+}
+
+#[stable(feature = "debug_hash_map", since = "1.12.0")]
+impl<K: Debug, V: Debug> Debug for OccupiedEntry<'_, K, V> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_struct("OccupiedEntry")
+ .field("key", self.key())
+ .field("value", self.get())
+ .finish_non_exhaustive()
+ }
+}
+
+/// A view into a vacant entry in a `HashMap`.
+/// It is part of the [`Entry`] enum.
+#[stable(feature = "rust1", since = "1.0.0")]
+pub struct VacantEntry<'a, K: 'a, V: 'a> {
+ base: base::RustcVacantEntry<'a, K, V>,
+}
+
+#[stable(feature = "debug_hash_map", since = "1.12.0")]
+impl<K: Debug, V> Debug for VacantEntry<'_, K, V> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_tuple("VacantEntry").field(self.key()).finish()
+ }
+}
+
+/// The error returned by [`try_insert`](HashMap::try_insert) when the key already exists.
+///
+/// Contains the occupied entry, and the value that was not inserted.
+#[unstable(feature = "map_try_insert", issue = "82766")]
+pub struct OccupiedError<'a, K: 'a, V: 'a> {
+ /// The entry in the map that was already occupied.
+ pub entry: OccupiedEntry<'a, K, V>,
+ /// The value which was not inserted, because the entry was already occupied.
+ pub value: V,
+}
+
+#[unstable(feature = "map_try_insert", issue = "82766")]
+impl<K: Debug, V: Debug> Debug for OccupiedError<'_, K, V> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_struct("OccupiedError")
+ .field("key", self.entry.key())
+ .field("old_value", self.entry.get())
+ .field("new_value", &self.value)
+ .finish_non_exhaustive()
+ }
+}
+
+#[unstable(feature = "map_try_insert", issue = "82766")]
+impl<'a, K: Debug, V: Debug> fmt::Display for OccupiedError<'a, K, V> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ write!(
+ f,
+ "failed to insert {:?}, key {:?} already exists with value {:?}",
+ self.value,
+ self.entry.key(),
+ self.entry.get(),
+ )
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<'a, K, V, S> IntoIterator for &'a HashMap<K, V, S> {
+ type Item = (&'a K, &'a V);
+ type IntoIter = Iter<'a, K, V>;
+
+ #[inline]
+ #[rustc_lint_query_instability]
+ fn into_iter(self) -> Iter<'a, K, V> {
+ self.iter()
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<'a, K, V, S> IntoIterator for &'a mut HashMap<K, V, S> {
+ type Item = (&'a K, &'a mut V);
+ type IntoIter = IterMut<'a, K, V>;
+
+ #[inline]
+ #[rustc_lint_query_instability]
+ fn into_iter(self) -> IterMut<'a, K, V> {
+ self.iter_mut()
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<K, V, S> IntoIterator for HashMap<K, V, S> {
+ type Item = (K, V);
+ type IntoIter = IntoIter<K, V>;
+
+ /// Creates a consuming iterator, that is, one that moves each key-value
+ /// pair out of the map in arbitrary order. The map cannot be used after
+ /// calling this.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let map = HashMap::from([
+ /// ("a", 1),
+ /// ("b", 2),
+ /// ("c", 3),
+ /// ]);
+ ///
+ /// // Not possible with .iter()
+ /// let vec: Vec<(&str, i32)> = map.into_iter().collect();
+ /// ```
+ #[inline]
+ #[rustc_lint_query_instability]
+ fn into_iter(self) -> IntoIter<K, V> {
+ IntoIter { base: self.base.into_iter() }
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<'a, K, V> Iterator for Iter<'a, K, V> {
+ type Item = (&'a K, &'a V);
+
+ #[inline]
+ fn next(&mut self) -> Option<(&'a K, &'a V)> {
+ self.base.next()
+ }
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ self.base.size_hint()
+ }
+}
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<K, V> ExactSizeIterator for Iter<'_, K, V> {
+ #[inline]
+ fn len(&self) -> usize {
+ self.base.len()
+ }
+}
+
+#[stable(feature = "fused", since = "1.26.0")]
+impl<K, V> FusedIterator for Iter<'_, K, V> {}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<'a, K, V> Iterator for IterMut<'a, K, V> {
+ type Item = (&'a K, &'a mut V);
+
+ #[inline]
+ fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
+ self.base.next()
+ }
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ self.base.size_hint()
+ }
+}
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<K, V> ExactSizeIterator for IterMut<'_, K, V> {
+ #[inline]
+ fn len(&self) -> usize {
+ self.base.len()
+ }
+}
+#[stable(feature = "fused", since = "1.26.0")]
+impl<K, V> FusedIterator for IterMut<'_, K, V> {}
+
+#[stable(feature = "std_debug", since = "1.16.0")]
+impl<K, V> fmt::Debug for IterMut<'_, K, V>
+where
+ K: fmt::Debug,
+ V: fmt::Debug,
+{
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_list().entries(self.iter()).finish()
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<K, V> Iterator for IntoIter<K, V> {
+ type Item = (K, V);
+
+ #[inline]
+ fn next(&mut self) -> Option<(K, V)> {
+ self.base.next()
+ }
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ self.base.size_hint()
+ }
+}
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<K, V> ExactSizeIterator for IntoIter<K, V> {
+ #[inline]
+ fn len(&self) -> usize {
+ self.base.len()
+ }
+}
+#[stable(feature = "fused", since = "1.26.0")]
+impl<K, V> FusedIterator for IntoIter<K, V> {}
+
+#[stable(feature = "std_debug", since = "1.16.0")]
+impl<K: Debug, V: Debug> fmt::Debug for IntoIter<K, V> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_list().entries(self.iter()).finish()
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<'a, K, V> Iterator for Keys<'a, K, V> {
+ type Item = &'a K;
+
+ #[inline]
+ fn next(&mut self) -> Option<&'a K> {
+ self.inner.next().map(|(k, _)| k)
+ }
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ self.inner.size_hint()
+ }
+}
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<K, V> ExactSizeIterator for Keys<'_, K, V> {
+ #[inline]
+ fn len(&self) -> usize {
+ self.inner.len()
+ }
+}
+#[stable(feature = "fused", since = "1.26.0")]
+impl<K, V> FusedIterator for Keys<'_, K, V> {}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<'a, K, V> Iterator for Values<'a, K, V> {
+ type Item = &'a V;
+
+ #[inline]
+ fn next(&mut self) -> Option<&'a V> {
+ self.inner.next().map(|(_, v)| v)
+ }
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ self.inner.size_hint()
+ }
+}
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<K, V> ExactSizeIterator for Values<'_, K, V> {
+ #[inline]
+ fn len(&self) -> usize {
+ self.inner.len()
+ }
+}
+#[stable(feature = "fused", since = "1.26.0")]
+impl<K, V> FusedIterator for Values<'_, K, V> {}
+
+#[stable(feature = "map_values_mut", since = "1.10.0")]
+impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
+ type Item = &'a mut V;
+
+ #[inline]
+ fn next(&mut self) -> Option<&'a mut V> {
+ self.inner.next().map(|(_, v)| v)
+ }
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ self.inner.size_hint()
+ }
+}
+#[stable(feature = "map_values_mut", since = "1.10.0")]
+impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> {
+ #[inline]
+ fn len(&self) -> usize {
+ self.inner.len()
+ }
+}
+#[stable(feature = "fused", since = "1.26.0")]
+impl<K, V> FusedIterator for ValuesMut<'_, K, V> {}
+
+#[stable(feature = "std_debug", since = "1.16.0")]
+impl<K, V: fmt::Debug> fmt::Debug for ValuesMut<'_, K, V> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_list().entries(self.inner.iter().map(|(_, val)| val)).finish()
+ }
+}
+
+#[stable(feature = "map_into_keys_values", since = "1.54.0")]
+impl<K, V> Iterator for IntoKeys<K, V> {
+ type Item = K;
+
+ #[inline]
+ fn next(&mut self) -> Option<K> {
+ self.inner.next().map(|(k, _)| k)
+ }
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ self.inner.size_hint()
+ }
+}
+#[stable(feature = "map_into_keys_values", since = "1.54.0")]
+impl<K, V> ExactSizeIterator for IntoKeys<K, V> {
+ #[inline]
+ fn len(&self) -> usize {
+ self.inner.len()
+ }
+}
+#[stable(feature = "map_into_keys_values", since = "1.54.0")]
+impl<K, V> FusedIterator for IntoKeys<K, V> {}
+
+#[stable(feature = "map_into_keys_values", since = "1.54.0")]
+impl<K: Debug, V> fmt::Debug for IntoKeys<K, V> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_list().entries(self.inner.iter().map(|(k, _)| k)).finish()
+ }
+}
+
+#[stable(feature = "map_into_keys_values", since = "1.54.0")]
+impl<K, V> Iterator for IntoValues<K, V> {
+ type Item = V;
+
+ #[inline]
+ fn next(&mut self) -> Option<V> {
+ self.inner.next().map(|(_, v)| v)
+ }
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ self.inner.size_hint()
+ }
+}
+#[stable(feature = "map_into_keys_values", since = "1.54.0")]
+impl<K, V> ExactSizeIterator for IntoValues<K, V> {
+ #[inline]
+ fn len(&self) -> usize {
+ self.inner.len()
+ }
+}
+#[stable(feature = "map_into_keys_values", since = "1.54.0")]
+impl<K, V> FusedIterator for IntoValues<K, V> {}
+
+#[stable(feature = "map_into_keys_values", since = "1.54.0")]
+impl<K, V: Debug> fmt::Debug for IntoValues<K, V> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_list().entries(self.inner.iter().map(|(_, v)| v)).finish()
+ }
+}
+
+#[stable(feature = "drain", since = "1.6.0")]
+impl<'a, K, V> Iterator for Drain<'a, K, V> {
+ type Item = (K, V);
+
+ #[inline]
+ fn next(&mut self) -> Option<(K, V)> {
+ self.base.next()
+ }
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ self.base.size_hint()
+ }
+}
+#[stable(feature = "drain", since = "1.6.0")]
+impl<K, V> ExactSizeIterator for Drain<'_, K, V> {
+ #[inline]
+ fn len(&self) -> usize {
+ self.base.len()
+ }
+}
+#[stable(feature = "fused", since = "1.26.0")]
+impl<K, V> FusedIterator for Drain<'_, K, V> {}
+
+#[stable(feature = "std_debug", since = "1.16.0")]
+impl<K, V> fmt::Debug for Drain<'_, K, V>
+where
+ K: fmt::Debug,
+ V: fmt::Debug,
+{
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_list().entries(self.iter()).finish()
+ }
+}
+
+#[unstable(feature = "hash_drain_filter", issue = "59618")]
+impl<K, V, F> Iterator for DrainFilter<'_, K, V, F>
+where
+ F: FnMut(&K, &mut V) -> bool,
+{
+ type Item = (K, V);
+
+ #[inline]
+ fn next(&mut self) -> Option<(K, V)> {
+ self.base.next()
+ }
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ self.base.size_hint()
+ }
+}
+
+#[unstable(feature = "hash_drain_filter", issue = "59618")]
+impl<K, V, F> FusedIterator for DrainFilter<'_, K, V, F> where F: FnMut(&K, &mut V) -> bool {}
+
+#[unstable(feature = "hash_drain_filter", issue = "59618")]
+impl<'a, K, V, F> fmt::Debug for DrainFilter<'a, K, V, F>
+where
+ F: FnMut(&K, &mut V) -> bool,
+{
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_struct("DrainFilter").finish_non_exhaustive()
+ }
+}
+
+impl<'a, K, V> Entry<'a, K, V> {
+ /// Ensures a value is in the entry by inserting the default if empty, and returns
+ /// a mutable reference to the value in the entry.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let mut map: HashMap<&str, u32> = HashMap::new();
+ ///
+ /// map.entry("poneyland").or_insert(3);
+ /// assert_eq!(map["poneyland"], 3);
+ ///
+ /// *map.entry("poneyland").or_insert(10) *= 2;
+ /// assert_eq!(map["poneyland"], 6);
+ /// ```
+ #[inline]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn or_insert(self, default: V) -> &'a mut V {
+ match self {
+ Occupied(entry) => entry.into_mut(),
+ Vacant(entry) => entry.insert(default),
+ }
+ }
+
+ /// Ensures a value is in the entry by inserting the result of the default function if empty,
+ /// and returns a mutable reference to the value in the entry.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let mut map: HashMap<&str, String> = HashMap::new();
+ /// let s = "hoho".to_string();
+ ///
+ /// map.entry("poneyland").or_insert_with(|| s);
+ ///
+ /// assert_eq!(map["poneyland"], "hoho".to_string());
+ /// ```
+ #[inline]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
+ match self {
+ Occupied(entry) => entry.into_mut(),
+ Vacant(entry) => entry.insert(default()),
+ }
+ }
+
+ /// Ensures a value is in the entry by inserting, if empty, the result of the default function.
+ /// This method allows for generating key-derived values for insertion by providing the default
+ /// function a reference to the key that was moved during the `.entry(key)` method call.
+ ///
+ /// The reference to the moved key is provided so that cloning or copying the key is
+ /// unnecessary, unlike with `.or_insert_with(|| ... )`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let mut map: HashMap<&str, usize> = HashMap::new();
+ ///
+ /// map.entry("poneyland").or_insert_with_key(|key| key.chars().count());
+ ///
+ /// assert_eq!(map["poneyland"], 9);
+ /// ```
+ #[inline]
+ #[stable(feature = "or_insert_with_key", since = "1.50.0")]
+ pub fn or_insert_with_key<F: FnOnce(&K) -> V>(self, default: F) -> &'a mut V {
+ match self {
+ Occupied(entry) => entry.into_mut(),
+ Vacant(entry) => {
+ let value = default(entry.key());
+ entry.insert(value)
+ }
+ }
+ }
+
+ /// Returns a reference to this entry's key.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let mut map: HashMap<&str, u32> = HashMap::new();
+ /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
+ /// ```
+ #[inline]
+ #[stable(feature = "map_entry_keys", since = "1.10.0")]
+ pub fn key(&self) -> &K {
+ match *self {
+ Occupied(ref entry) => entry.key(),
+ Vacant(ref entry) => entry.key(),
+ }
+ }
+
+ /// Provides in-place mutable access to an occupied entry before any
+ /// potential inserts into the map.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let mut map: HashMap<&str, u32> = HashMap::new();
+ ///
+ /// map.entry("poneyland")
+ /// .and_modify(|e| { *e += 1 })
+ /// .or_insert(42);
+ /// assert_eq!(map["poneyland"], 42);
+ ///
+ /// map.entry("poneyland")
+ /// .and_modify(|e| { *e += 1 })
+ /// .or_insert(42);
+ /// assert_eq!(map["poneyland"], 43);
+ /// ```
+ #[inline]
+ #[stable(feature = "entry_and_modify", since = "1.26.0")]
+ pub fn and_modify<F>(self, f: F) -> Self
+ where
+ F: FnOnce(&mut V),
+ {
+ match self {
+ Occupied(mut entry) => {
+ f(entry.get_mut());
+ Occupied(entry)
+ }
+ Vacant(entry) => Vacant(entry),
+ }
+ }
+
+ /// Sets the value of the entry, and returns an `OccupiedEntry`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// #![feature(entry_insert)]
+ /// use std::collections::HashMap;
+ ///
+ /// let mut map: HashMap<&str, String> = HashMap::new();
+ /// let entry = map.entry("poneyland").insert_entry("hoho".to_string());
+ ///
+ /// assert_eq!(entry.key(), &"poneyland");
+ /// ```
+ #[inline]
+ #[unstable(feature = "entry_insert", issue = "65225")]
+ pub fn insert_entry(self, value: V) -> OccupiedEntry<'a, K, V> {
+ match self {
+ Occupied(mut entry) => {
+ entry.insert(value);
+ entry
+ }
+ Vacant(entry) => entry.insert_entry(value),
+ }
+ }
+}
+
+impl<'a, K, V: Default> Entry<'a, K, V> {
+ /// Ensures a value is in the entry by inserting the default value if empty,
+ /// and returns a mutable reference to the value in the entry.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// # fn main() {
+ /// use std::collections::HashMap;
+ ///
+ /// let mut map: HashMap<&str, Option<u32>> = HashMap::new();
+ /// map.entry("poneyland").or_default();
+ ///
+ /// assert_eq!(map["poneyland"], None);
+ /// # }
+ /// ```
+ #[inline]
+ #[stable(feature = "entry_or_default", since = "1.28.0")]
+ pub fn or_default(self) -> &'a mut V {
+ match self {
+ Occupied(entry) => entry.into_mut(),
+ Vacant(entry) => entry.insert(Default::default()),
+ }
+ }
+}
+
+impl<'a, K, V> OccupiedEntry<'a, K, V> {
+ /// Gets a reference to the key in the entry.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let mut map: HashMap<&str, u32> = HashMap::new();
+ /// map.entry("poneyland").or_insert(12);
+ /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
+ /// ```
+ #[inline]
+ #[stable(feature = "map_entry_keys", since = "1.10.0")]
+ pub fn key(&self) -> &K {
+ self.base.key()
+ }
+
+ /// Take the ownership of the key and value from the map.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ /// use std::collections::hash_map::Entry;
+ ///
+ /// let mut map: HashMap<&str, u32> = HashMap::new();
+ /// map.entry("poneyland").or_insert(12);
+ ///
+ /// if let Entry::Occupied(o) = map.entry("poneyland") {
+ /// // We delete the entry from the map.
+ /// o.remove_entry();
+ /// }
+ ///
+ /// assert_eq!(map.contains_key("poneyland"), false);
+ /// ```
+ #[inline]
+ #[stable(feature = "map_entry_recover_keys2", since = "1.12.0")]
+ pub fn remove_entry(self) -> (K, V) {
+ self.base.remove_entry()
+ }
+
+ /// Gets a reference to the value in the entry.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ /// use std::collections::hash_map::Entry;
+ ///
+ /// let mut map: HashMap<&str, u32> = HashMap::new();
+ /// map.entry("poneyland").or_insert(12);
+ ///
+ /// if let Entry::Occupied(o) = map.entry("poneyland") {
+ /// assert_eq!(o.get(), &12);
+ /// }
+ /// ```
+ #[inline]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn get(&self) -> &V {
+ self.base.get()
+ }
+
+ /// Gets a mutable reference to the value in the entry.
+ ///
+ /// If you need a reference to the `OccupiedEntry` which may outlive the
+ /// destruction of the `Entry` value, see [`into_mut`].
+ ///
+ /// [`into_mut`]: Self::into_mut
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ /// use std::collections::hash_map::Entry;
+ ///
+ /// let mut map: HashMap<&str, u32> = HashMap::new();
+ /// map.entry("poneyland").or_insert(12);
+ ///
+ /// assert_eq!(map["poneyland"], 12);
+ /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
+ /// *o.get_mut() += 10;
+ /// assert_eq!(*o.get(), 22);
+ ///
+ /// // We can use the same Entry multiple times.
+ /// *o.get_mut() += 2;
+ /// }
+ ///
+ /// assert_eq!(map["poneyland"], 24);
+ /// ```
+ #[inline]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn get_mut(&mut self) -> &mut V {
+ self.base.get_mut()
+ }
+
+ /// Converts the `OccupiedEntry` into a mutable reference to the value in the entry
+ /// with a lifetime bound to the map itself.
+ ///
+ /// If you need multiple references to the `OccupiedEntry`, see [`get_mut`].
+ ///
+ /// [`get_mut`]: Self::get_mut
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ /// use std::collections::hash_map::Entry;
+ ///
+ /// let mut map: HashMap<&str, u32> = HashMap::new();
+ /// map.entry("poneyland").or_insert(12);
+ ///
+ /// assert_eq!(map["poneyland"], 12);
+ /// if let Entry::Occupied(o) = map.entry("poneyland") {
+ /// *o.into_mut() += 10;
+ /// }
+ ///
+ /// assert_eq!(map["poneyland"], 22);
+ /// ```
+ #[inline]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn into_mut(self) -> &'a mut V {
+ self.base.into_mut()
+ }
+
+ /// Sets the value of the entry, and returns the entry's old value.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ /// use std::collections::hash_map::Entry;
+ ///
+ /// let mut map: HashMap<&str, u32> = HashMap::new();
+ /// map.entry("poneyland").or_insert(12);
+ ///
+ /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
+ /// assert_eq!(o.insert(15), 12);
+ /// }
+ ///
+ /// assert_eq!(map["poneyland"], 15);
+ /// ```
+ #[inline]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn insert(&mut self, value: V) -> V {
+ self.base.insert(value)
+ }
+
+ /// Takes the value out of the entry, and returns it.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ /// use std::collections::hash_map::Entry;
+ ///
+ /// let mut map: HashMap<&str, u32> = HashMap::new();
+ /// map.entry("poneyland").or_insert(12);
+ ///
+ /// if let Entry::Occupied(o) = map.entry("poneyland") {
+ /// assert_eq!(o.remove(), 12);
+ /// }
+ ///
+ /// assert_eq!(map.contains_key("poneyland"), false);
+ /// ```
+ #[inline]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn remove(self) -> V {
+ self.base.remove()
+ }
+
+ /// Replaces the entry, returning the old key and value. The new key in the hash map will be
+ /// the key used to create this entry.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// #![feature(map_entry_replace)]
+ /// use std::collections::hash_map::{Entry, HashMap};
+ /// use std::rc::Rc;
+ ///
+ /// let mut map: HashMap<Rc<String>, u32> = HashMap::new();
+ /// map.insert(Rc::new("Stringthing".to_string()), 15);
+ ///
+ /// let my_key = Rc::new("Stringthing".to_string());
+ ///
+ /// if let Entry::Occupied(entry) = map.entry(my_key) {
+ /// // Also replace the key with a handle to our other key.
+ /// let (old_key, old_value): (Rc<String>, u32) = entry.replace_entry(16);
+ /// }
+ ///
+ /// ```
+ #[inline]
+ #[unstable(feature = "map_entry_replace", issue = "44286")]
+ pub fn replace_entry(self, value: V) -> (K, V) {
+ self.base.replace_entry(value)
+ }
+
+ /// Replaces the key in the hash map with the key used to create this entry.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// #![feature(map_entry_replace)]
+ /// use std::collections::hash_map::{Entry, HashMap};
+ /// use std::rc::Rc;
+ ///
+ /// let mut map: HashMap<Rc<String>, u32> = HashMap::new();
+ /// let known_strings: Vec<Rc<String>> = Vec::new();
+ ///
+ /// // Initialise known strings, run program, etc.
+ ///
+ /// reclaim_memory(&mut map, &known_strings);
+ ///
+ /// fn reclaim_memory(map: &mut HashMap<Rc<String>, u32>, known_strings: &[Rc<String>] ) {
+ /// for s in known_strings {
+ /// if let Entry::Occupied(entry) = map.entry(Rc::clone(s)) {
+ /// // Replaces the entry's key with our version of it in `known_strings`.
+ /// entry.replace_key();
+ /// }
+ /// }
+ /// }
+ /// ```
+ #[inline]
+ #[unstable(feature = "map_entry_replace", issue = "44286")]
+ pub fn replace_key(self) -> K {
+ self.base.replace_key()
+ }
+}
+
+impl<'a, K: 'a, V: 'a> VacantEntry<'a, K, V> {
+ /// Gets a reference to the key that would be used when inserting a value
+ /// through the `VacantEntry`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let mut map: HashMap<&str, u32> = HashMap::new();
+ /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
+ /// ```
+ #[inline]
+ #[stable(feature = "map_entry_keys", since = "1.10.0")]
+ pub fn key(&self) -> &K {
+ self.base.key()
+ }
+
+ /// Take ownership of the key.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ /// use std::collections::hash_map::Entry;
+ ///
+ /// let mut map: HashMap<&str, u32> = HashMap::new();
+ ///
+ /// if let Entry::Vacant(v) = map.entry("poneyland") {
+ /// v.into_key();
+ /// }
+ /// ```
+ #[inline]
+ #[stable(feature = "map_entry_recover_keys2", since = "1.12.0")]
+ pub fn into_key(self) -> K {
+ self.base.into_key()
+ }
+
+ /// Sets the value of the entry with the `VacantEntry`'s key,
+ /// and returns a mutable reference to it.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ /// use std::collections::hash_map::Entry;
+ ///
+ /// let mut map: HashMap<&str, u32> = HashMap::new();
+ ///
+ /// if let Entry::Vacant(o) = map.entry("poneyland") {
+ /// o.insert(37);
+ /// }
+ /// assert_eq!(map["poneyland"], 37);
+ /// ```
+ #[inline]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn insert(self, value: V) -> &'a mut V {
+ self.base.insert(value)
+ }
+
+ /// Sets the value of the entry with the `VacantEntry`'s key,
+ /// and returns an `OccupiedEntry`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// #![feature(entry_insert)]
+ /// use std::collections::HashMap;
+ /// use std::collections::hash_map::Entry;
+ ///
+ /// let mut map: HashMap<&str, u32> = HashMap::new();
+ ///
+ /// if let Entry::Vacant(o) = map.entry("poneyland") {
+ /// o.insert_entry(37);
+ /// }
+ /// assert_eq!(map["poneyland"], 37);
+ /// ```
+ #[inline]
+ #[unstable(feature = "entry_insert", issue = "65225")]
+ pub fn insert_entry(self, value: V) -> OccupiedEntry<'a, K, V> {
+ let base = self.base.insert_entry(value);
+ OccupiedEntry { base }
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<K, V, S> FromIterator<(K, V)> for HashMap<K, V, S>
+where
+ K: Eq + Hash,
+ S: BuildHasher + Default,
+{
+ fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> HashMap<K, V, S> {
+ let mut map = HashMap::with_hasher(Default::default());
+ map.extend(iter);
+ map
+ }
+}
+
+/// Inserts all new key-values from the iterator and replaces values with existing
+/// keys with new values returned from the iterator.
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<K, V, S> Extend<(K, V)> for HashMap<K, V, S>
+where
+ K: Eq + Hash,
+ S: BuildHasher,
+{
+ #[inline]
+ fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
+ self.base.extend(iter)
+ }
+
+ #[inline]
+ fn extend_one(&mut self, (k, v): (K, V)) {
+ self.base.insert(k, v);
+ }
+
+ #[inline]
+ fn extend_reserve(&mut self, additional: usize) {
+ self.base.extend_reserve(additional);
+ }
+}
+
+#[stable(feature = "hash_extend_copy", since = "1.4.0")]
+impl<'a, K, V, S> Extend<(&'a K, &'a V)> for HashMap<K, V, S>
+where
+ K: Eq + Hash + Copy,
+ V: Copy,
+ S: BuildHasher,
+{
+ #[inline]
+ fn extend<T: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: T) {
+ self.base.extend(iter)
+ }
+
+ #[inline]
+ fn extend_one(&mut self, (&k, &v): (&'a K, &'a V)) {
+ self.base.insert(k, v);
+ }
+
+ #[inline]
+ fn extend_reserve(&mut self, additional: usize) {
+ Extend::<(K, V)>::extend_reserve(self, additional)
+ }
+}
+
+/// `RandomState` is the default state for [`HashMap`] types.
+///
+/// A particular instance `RandomState` will create the same instances of
+/// [`Hasher`], but the hashers created by two different `RandomState`
+/// instances are unlikely to produce the same result for the same values.
+///
+/// # Examples
+///
+/// ```
+/// use std::collections::HashMap;
+/// use std::collections::hash_map::RandomState;
+///
+/// let s = RandomState::new();
+/// let mut map = HashMap::with_hasher(s);
+/// map.insert(1, 2);
+/// ```
+#[derive(Clone)]
+#[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
+pub struct RandomState {
+ k0: u64,
+ k1: u64,
+}
+
+impl RandomState {
+ /// Constructs a new `RandomState` that is initialized with random keys.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::hash_map::RandomState;
+ ///
+ /// let s = RandomState::new();
+ /// ```
+ #[inline]
+ #[allow(deprecated)]
+ // rand
+ #[must_use]
+ #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
+ pub fn new() -> RandomState {
+ // Historically this function did not cache keys from the OS and instead
+ // simply always called `rand::thread_rng().gen()` twice. In #31356 it
+ // was discovered, however, that because we re-seed the thread-local RNG
+ // from the OS periodically that this can cause excessive slowdown when
+ // many hash maps are created on a thread. To solve this performance
+ // trap we cache the first set of randomly generated keys per-thread.
+ //
+ // Later in #36481 it was discovered that exposing a deterministic
+ // iteration order allows a form of DOS attack. To counter that we
+ // increment one of the seeds on every RandomState creation, giving
+ // every corresponding HashMap a different iteration order.
+ thread_local!(static KEYS: Cell<(u64, u64)> = {
+ Cell::new(sys::hashmap_random_keys())
+ });
+
+ KEYS.with(|keys| {
+ let (k0, k1) = keys.get();
+ keys.set((k0.wrapping_add(1), k1));
+ RandomState { k0, k1 }
+ })
+ }
+}
+
+#[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
+impl BuildHasher for RandomState {
+ type Hasher = DefaultHasher;
+ #[inline]
+ #[allow(deprecated)]
+ fn build_hasher(&self) -> DefaultHasher {
+ DefaultHasher(SipHasher13::new_with_keys(self.k0, self.k1))
+ }
+}
+
+/// The default [`Hasher`] used by [`RandomState`].
+///
+/// The internal algorithm is not specified, and so it and its hashes should
+/// not be relied upon over releases.
+#[stable(feature = "hashmap_default_hasher", since = "1.13.0")]
+#[allow(deprecated)]
+#[derive(Clone, Debug)]
+pub struct DefaultHasher(SipHasher13);
+
+impl DefaultHasher {
+ /// Creates a new `DefaultHasher`.
+ ///
+ /// This hasher is not guaranteed to be the same as all other
+ /// `DefaultHasher` instances, but is the same as all other `DefaultHasher`
+ /// instances created through `new` or `default`.
+ #[stable(feature = "hashmap_default_hasher", since = "1.13.0")]
+ #[inline]
+ #[allow(deprecated)]
+ #[must_use]
+ pub fn new() -> DefaultHasher {
+ DefaultHasher(SipHasher13::new_with_keys(0, 0))
+ }
+}
+
+#[stable(feature = "hashmap_default_hasher", since = "1.13.0")]
+impl Default for DefaultHasher {
+ /// Creates a new `DefaultHasher` using [`new`].
+ /// See its documentation for more.
+ ///
+ /// [`new`]: DefaultHasher::new
+ #[inline]
+ fn default() -> DefaultHasher {
+ DefaultHasher::new()
+ }
+}
+
+#[stable(feature = "hashmap_default_hasher", since = "1.13.0")]
+impl Hasher for DefaultHasher {
+ // The underlying `SipHasher13` doesn't override the other
+ // `write_*` methods, so it's ok not to forward them here.
+
+ #[inline]
+ fn write(&mut self, msg: &[u8]) {
+ self.0.write(msg)
+ }
+
+ #[inline]
+ fn write_str(&mut self, s: &str) {
+ self.0.write_str(s);
+ }
+
+ #[inline]
+ fn finish(&self) -> u64 {
+ self.0.finish()
+ }
+}
+
+#[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
+impl Default for RandomState {
+ /// Constructs a new `RandomState`.
+ #[inline]
+ fn default() -> RandomState {
+ RandomState::new()
+ }
+}
+
+#[stable(feature = "std_debug", since = "1.16.0")]
+impl fmt::Debug for RandomState {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_struct("RandomState").finish_non_exhaustive()
+ }
+}
+
+#[inline]
+fn map_entry<'a, K: 'a, V: 'a>(raw: base::RustcEntry<'a, K, V>) -> Entry<'a, K, V> {
+ match raw {
+ base::RustcEntry::Occupied(base) => Entry::Occupied(OccupiedEntry { base }),
+ base::RustcEntry::Vacant(base) => Entry::Vacant(VacantEntry { base }),
+ }
+}
+
+#[inline]
+pub(super) fn map_try_reserve_error(err: hashbrown::TryReserveError) -> TryReserveError {
+ match err {
+ hashbrown::TryReserveError::CapacityOverflow => {
+ TryReserveErrorKind::CapacityOverflow.into()
+ }
+ hashbrown::TryReserveError::AllocError { layout } => {
+ TryReserveErrorKind::AllocError { layout, non_exhaustive: () }.into()
+ }
+ }
+}
+
+#[inline]
+fn map_raw_entry<'a, K: 'a, V: 'a, S: 'a>(
+ raw: base::RawEntryMut<'a, K, V, S>,
+) -> RawEntryMut<'a, K, V, S> {
+ match raw {
+ base::RawEntryMut::Occupied(base) => RawEntryMut::Occupied(RawOccupiedEntryMut { base }),
+ base::RawEntryMut::Vacant(base) => RawEntryMut::Vacant(RawVacantEntryMut { base }),
+ }
+}
+
+#[allow(dead_code)]
+fn assert_covariance() {
+ fn map_key<'new>(v: HashMap<&'static str, u8>) -> HashMap<&'new str, u8> {
+ v
+ }
+ fn map_val<'new>(v: HashMap<u8, &'static str>) -> HashMap<u8, &'new str> {
+ v
+ }
+ fn iter_key<'a, 'new>(v: Iter<'a, &'static str, u8>) -> Iter<'a, &'new str, u8> {
+ v
+ }
+ fn iter_val<'a, 'new>(v: Iter<'a, u8, &'static str>) -> Iter<'a, u8, &'new str> {
+ v
+ }
+ fn into_iter_key<'new>(v: IntoIter<&'static str, u8>) -> IntoIter<&'new str, u8> {
+ v
+ }
+ fn into_iter_val<'new>(v: IntoIter<u8, &'static str>) -> IntoIter<u8, &'new str> {
+ v
+ }
+ fn keys_key<'a, 'new>(v: Keys<'a, &'static str, u8>) -> Keys<'a, &'new str, u8> {
+ v
+ }
+ fn keys_val<'a, 'new>(v: Keys<'a, u8, &'static str>) -> Keys<'a, u8, &'new str> {
+ v
+ }
+ fn values_key<'a, 'new>(v: Values<'a, &'static str, u8>) -> Values<'a, &'new str, u8> {
+ v
+ }
+ fn values_val<'a, 'new>(v: Values<'a, u8, &'static str>) -> Values<'a, u8, &'new str> {
+ v
+ }
+ fn drain<'new>(
+ d: Drain<'static, &'static str, &'static str>,
+ ) -> Drain<'new, &'new str, &'new str> {
+ d
+ }
+}
diff --git a/library/std/src/collections/hash/map/tests.rs b/library/std/src/collections/hash/map/tests.rs
new file mode 100644
index 000000000..7ebc41588
--- /dev/null
+++ b/library/std/src/collections/hash/map/tests.rs
@@ -0,0 +1,1113 @@
+use super::Entry::{Occupied, Vacant};
+use super::HashMap;
+use super::RandomState;
+use crate::assert_matches::assert_matches;
+use crate::cell::RefCell;
+use rand::{thread_rng, Rng};
+use realstd::collections::TryReserveErrorKind::*;
+
+// https://github.com/rust-lang/rust/issues/62301
+fn _assert_hashmap_is_unwind_safe() {
+ fn assert_unwind_safe<T: crate::panic::UnwindSafe>() {}
+ assert_unwind_safe::<HashMap<(), crate::cell::UnsafeCell<()>>>();
+}
+
+#[test]
+fn test_zero_capacities() {
+ type HM = HashMap<i32, i32>;
+
+ let m = HM::new();
+ assert_eq!(m.capacity(), 0);
+
+ let m = HM::default();
+ assert_eq!(m.capacity(), 0);
+
+ let m = HM::with_hasher(RandomState::new());
+ assert_eq!(m.capacity(), 0);
+
+ let m = HM::with_capacity(0);
+ assert_eq!(m.capacity(), 0);
+
+ let m = HM::with_capacity_and_hasher(0, RandomState::new());
+ assert_eq!(m.capacity(), 0);
+
+ let mut m = HM::new();
+ m.insert(1, 1);
+ m.insert(2, 2);
+ m.remove(&1);
+ m.remove(&2);
+ m.shrink_to_fit();
+ assert_eq!(m.capacity(), 0);
+
+ let mut m = HM::new();
+ m.reserve(0);
+ assert_eq!(m.capacity(), 0);
+}
+
+#[test]
+fn test_create_capacity_zero() {
+ let mut m = HashMap::with_capacity(0);
+
+ assert!(m.insert(1, 1).is_none());
+
+ assert!(m.contains_key(&1));
+ assert!(!m.contains_key(&0));
+}
+
+#[test]
+fn test_insert() {
+ let mut m = HashMap::new();
+ assert_eq!(m.len(), 0);
+ assert!(m.insert(1, 2).is_none());
+ assert_eq!(m.len(), 1);
+ assert!(m.insert(2, 4).is_none());
+ assert_eq!(m.len(), 2);
+ assert_eq!(*m.get(&1).unwrap(), 2);
+ assert_eq!(*m.get(&2).unwrap(), 4);
+}
+
+#[test]
+fn test_clone() {
+ let mut m = HashMap::new();
+ assert_eq!(m.len(), 0);
+ assert!(m.insert(1, 2).is_none());
+ assert_eq!(m.len(), 1);
+ assert!(m.insert(2, 4).is_none());
+ assert_eq!(m.len(), 2);
+ let m2 = m.clone();
+ assert_eq!(*m2.get(&1).unwrap(), 2);
+ assert_eq!(*m2.get(&2).unwrap(), 4);
+ assert_eq!(m2.len(), 2);
+}
+
+thread_local! { static DROP_VECTOR: RefCell<Vec<i32>> = RefCell::new(Vec::new()) }
+
+#[derive(Hash, PartialEq, Eq)]
+struct Droppable {
+ k: usize,
+}
+
+impl Droppable {
+ fn new(k: usize) -> Droppable {
+ DROP_VECTOR.with(|slot| {
+ slot.borrow_mut()[k] += 1;
+ });
+
+ Droppable { k }
+ }
+}
+
+impl Drop for Droppable {
+ fn drop(&mut self) {
+ DROP_VECTOR.with(|slot| {
+ slot.borrow_mut()[self.k] -= 1;
+ });
+ }
+}
+
+impl Clone for Droppable {
+ fn clone(&self) -> Droppable {
+ Droppable::new(self.k)
+ }
+}
+
+#[test]
+fn test_drops() {
+ DROP_VECTOR.with(|slot| {
+ *slot.borrow_mut() = vec![0; 200];
+ });
+
+ {
+ let mut m = HashMap::new();
+
+ DROP_VECTOR.with(|v| {
+ for i in 0..200 {
+ assert_eq!(v.borrow()[i], 0);
+ }
+ });
+
+ for i in 0..100 {
+ let d1 = Droppable::new(i);
+ let d2 = Droppable::new(i + 100);
+ m.insert(d1, d2);
+ }
+
+ DROP_VECTOR.with(|v| {
+ for i in 0..200 {
+ assert_eq!(v.borrow()[i], 1);
+ }
+ });
+
+ for i in 0..50 {
+ let k = Droppable::new(i);
+ let v = m.remove(&k);
+
+ assert!(v.is_some());
+
+ DROP_VECTOR.with(|v| {
+ assert_eq!(v.borrow()[i], 1);
+ assert_eq!(v.borrow()[i + 100], 1);
+ });
+ }
+
+ DROP_VECTOR.with(|v| {
+ for i in 0..50 {
+ assert_eq!(v.borrow()[i], 0);
+ assert_eq!(v.borrow()[i + 100], 0);
+ }
+
+ for i in 50..100 {
+ assert_eq!(v.borrow()[i], 1);
+ assert_eq!(v.borrow()[i + 100], 1);
+ }
+ });
+ }
+
+ DROP_VECTOR.with(|v| {
+ for i in 0..200 {
+ assert_eq!(v.borrow()[i], 0);
+ }
+ });
+}
+
+#[test]
+fn test_into_iter_drops() {
+ DROP_VECTOR.with(|v| {
+ *v.borrow_mut() = vec![0; 200];
+ });
+
+ let hm = {
+ let mut hm = HashMap::new();
+
+ DROP_VECTOR.with(|v| {
+ for i in 0..200 {
+ assert_eq!(v.borrow()[i], 0);
+ }
+ });
+
+ for i in 0..100 {
+ let d1 = Droppable::new(i);
+ let d2 = Droppable::new(i + 100);
+ hm.insert(d1, d2);
+ }
+
+ DROP_VECTOR.with(|v| {
+ for i in 0..200 {
+ assert_eq!(v.borrow()[i], 1);
+ }
+ });
+
+ hm
+ };
+
+ // By the way, ensure that cloning doesn't screw up the dropping.
+ drop(hm.clone());
+
+ {
+ let mut half = hm.into_iter().take(50);
+
+ DROP_VECTOR.with(|v| {
+ for i in 0..200 {
+ assert_eq!(v.borrow()[i], 1);
+ }
+ });
+
+ for _ in half.by_ref() {}
+
+ DROP_VECTOR.with(|v| {
+ let nk = (0..100).filter(|&i| v.borrow()[i] == 1).count();
+
+ let nv = (0..100).filter(|&i| v.borrow()[i + 100] == 1).count();
+
+ assert_eq!(nk, 50);
+ assert_eq!(nv, 50);
+ });
+ };
+
+ DROP_VECTOR.with(|v| {
+ for i in 0..200 {
+ assert_eq!(v.borrow()[i], 0);
+ }
+ });
+}
+
+#[test]
+fn test_empty_remove() {
+ let mut m: HashMap<i32, bool> = HashMap::new();
+ assert_eq!(m.remove(&0), None);
+}
+
+#[test]
+fn test_empty_entry() {
+ let mut m: HashMap<i32, bool> = HashMap::new();
+ match m.entry(0) {
+ Occupied(_) => panic!(),
+ Vacant(_) => {}
+ }
+ assert!(*m.entry(0).or_insert(true));
+ assert_eq!(m.len(), 1);
+}
+
+#[test]
+fn test_empty_iter() {
+ let mut m: HashMap<i32, bool> = HashMap::new();
+ assert_eq!(m.drain().next(), None);
+ assert_eq!(m.keys().next(), None);
+ assert_eq!(m.values().next(), None);
+ assert_eq!(m.values_mut().next(), None);
+ assert_eq!(m.iter().next(), None);
+ assert_eq!(m.iter_mut().next(), None);
+ assert_eq!(m.len(), 0);
+ assert!(m.is_empty());
+ assert_eq!(m.into_iter().next(), None);
+}
+
+#[test]
+fn test_lots_of_insertions() {
+ let mut m = HashMap::new();
+
+ // Try this a few times to make sure we never screw up the hashmap's
+ // internal state.
+ for _ in 0..10 {
+ assert!(m.is_empty());
+
+ for i in 1..1001 {
+ assert!(m.insert(i, i).is_none());
+
+ for j in 1..=i {
+ let r = m.get(&j);
+ assert_eq!(r, Some(&j));
+ }
+
+ for j in i + 1..1001 {
+ let r = m.get(&j);
+ assert_eq!(r, None);
+ }
+ }
+
+ for i in 1001..2001 {
+ assert!(!m.contains_key(&i));
+ }
+
+ // remove forwards
+ for i in 1..1001 {
+ assert!(m.remove(&i).is_some());
+
+ for j in 1..=i {
+ assert!(!m.contains_key(&j));
+ }
+
+ for j in i + 1..1001 {
+ assert!(m.contains_key(&j));
+ }
+ }
+
+ for i in 1..1001 {
+ assert!(!m.contains_key(&i));
+ }
+
+ for i in 1..1001 {
+ assert!(m.insert(i, i).is_none());
+ }
+
+ // remove backwards
+ for i in (1..1001).rev() {
+ assert!(m.remove(&i).is_some());
+
+ for j in i..1001 {
+ assert!(!m.contains_key(&j));
+ }
+
+ for j in 1..i {
+ assert!(m.contains_key(&j));
+ }
+ }
+ }
+}
+
+#[test]
+fn test_find_mut() {
+ let mut m = HashMap::new();
+ assert!(m.insert(1, 12).is_none());
+ assert!(m.insert(2, 8).is_none());
+ assert!(m.insert(5, 14).is_none());
+ let new = 100;
+ match m.get_mut(&5) {
+ None => panic!(),
+ Some(x) => *x = new,
+ }
+ assert_eq!(m.get(&5), Some(&new));
+}
+
+#[test]
+fn test_insert_overwrite() {
+ let mut m = HashMap::new();
+ assert!(m.insert(1, 2).is_none());
+ assert_eq!(*m.get(&1).unwrap(), 2);
+ assert!(!m.insert(1, 3).is_none());
+ assert_eq!(*m.get(&1).unwrap(), 3);
+}
+
+#[test]
+fn test_insert_conflicts() {
+ let mut m = HashMap::with_capacity(4);
+ assert!(m.insert(1, 2).is_none());
+ assert!(m.insert(5, 3).is_none());
+ assert!(m.insert(9, 4).is_none());
+ assert_eq!(*m.get(&9).unwrap(), 4);
+ assert_eq!(*m.get(&5).unwrap(), 3);
+ assert_eq!(*m.get(&1).unwrap(), 2);
+}
+
+#[test]
+fn test_conflict_remove() {
+ let mut m = HashMap::with_capacity(4);
+ assert!(m.insert(1, 2).is_none());
+ assert_eq!(*m.get(&1).unwrap(), 2);
+ assert!(m.insert(5, 3).is_none());
+ assert_eq!(*m.get(&1).unwrap(), 2);
+ assert_eq!(*m.get(&5).unwrap(), 3);
+ assert!(m.insert(9, 4).is_none());
+ assert_eq!(*m.get(&1).unwrap(), 2);
+ assert_eq!(*m.get(&5).unwrap(), 3);
+ assert_eq!(*m.get(&9).unwrap(), 4);
+ assert!(m.remove(&1).is_some());
+ assert_eq!(*m.get(&9).unwrap(), 4);
+ assert_eq!(*m.get(&5).unwrap(), 3);
+}
+
+#[test]
+fn test_is_empty() {
+ let mut m = HashMap::with_capacity(4);
+ assert!(m.insert(1, 2).is_none());
+ assert!(!m.is_empty());
+ assert!(m.remove(&1).is_some());
+ assert!(m.is_empty());
+}
+
+#[test]
+fn test_remove() {
+ let mut m = HashMap::new();
+ m.insert(1, 2);
+ assert_eq!(m.remove(&1), Some(2));
+ assert_eq!(m.remove(&1), None);
+}
+
+#[test]
+fn test_remove_entry() {
+ let mut m = HashMap::new();
+ m.insert(1, 2);
+ assert_eq!(m.remove_entry(&1), Some((1, 2)));
+ assert_eq!(m.remove(&1), None);
+}
+
+#[test]
+fn test_iterate() {
+ let mut m = HashMap::with_capacity(4);
+ for i in 0..32 {
+ assert!(m.insert(i, i * 2).is_none());
+ }
+ assert_eq!(m.len(), 32);
+
+ let mut observed: u32 = 0;
+
+ for (k, v) in &m {
+ assert_eq!(*v, *k * 2);
+ observed |= 1 << *k;
+ }
+ assert_eq!(observed, 0xFFFF_FFFF);
+}
+
+#[test]
+fn test_keys() {
+ let pairs = [(1, 'a'), (2, 'b'), (3, 'c')];
+ let map: HashMap<_, _> = pairs.into_iter().collect();
+ let keys: Vec<_> = map.keys().cloned().collect();
+ assert_eq!(keys.len(), 3);
+ assert!(keys.contains(&1));
+ assert!(keys.contains(&2));
+ assert!(keys.contains(&3));
+}
+
+#[test]
+fn test_values() {
+ let pairs = [(1, 'a'), (2, 'b'), (3, 'c')];
+ let map: HashMap<_, _> = pairs.into_iter().collect();
+ let values: Vec<_> = map.values().cloned().collect();
+ assert_eq!(values.len(), 3);
+ assert!(values.contains(&'a'));
+ assert!(values.contains(&'b'));
+ assert!(values.contains(&'c'));
+}
+
+#[test]
+fn test_values_mut() {
+ let pairs = [(1, 1), (2, 2), (3, 3)];
+ let mut map: HashMap<_, _> = pairs.into_iter().collect();
+ for value in map.values_mut() {
+ *value = (*value) * 2
+ }
+ let values: Vec<_> = map.values().cloned().collect();
+ assert_eq!(values.len(), 3);
+ assert!(values.contains(&2));
+ assert!(values.contains(&4));
+ assert!(values.contains(&6));
+}
+
+#[test]
+fn test_into_keys() {
+ let pairs = [(1, 'a'), (2, 'b'), (3, 'c')];
+ let map: HashMap<_, _> = pairs.into_iter().collect();
+ let keys: Vec<_> = map.into_keys().collect();
+
+ assert_eq!(keys.len(), 3);
+ assert!(keys.contains(&1));
+ assert!(keys.contains(&2));
+ assert!(keys.contains(&3));
+}
+
+#[test]
+fn test_into_values() {
+ let pairs = [(1, 'a'), (2, 'b'), (3, 'c')];
+ let map: HashMap<_, _> = pairs.into_iter().collect();
+ let values: Vec<_> = map.into_values().collect();
+
+ assert_eq!(values.len(), 3);
+ assert!(values.contains(&'a'));
+ assert!(values.contains(&'b'));
+ assert!(values.contains(&'c'));
+}
+
+#[test]
+fn test_find() {
+ let mut m = HashMap::new();
+ assert!(m.get(&1).is_none());
+ m.insert(1, 2);
+ match m.get(&1) {
+ None => panic!(),
+ Some(v) => assert_eq!(*v, 2),
+ }
+}
+
+#[test]
+fn test_eq() {
+ let mut m1 = HashMap::new();
+ m1.insert(1, 2);
+ m1.insert(2, 3);
+ m1.insert(3, 4);
+
+ let mut m2 = HashMap::new();
+ m2.insert(1, 2);
+ m2.insert(2, 3);
+
+ assert!(m1 != m2);
+
+ m2.insert(3, 4);
+
+ assert_eq!(m1, m2);
+}
+
+#[test]
+fn test_show() {
+ let mut map = HashMap::new();
+ let empty: HashMap<i32, i32> = HashMap::new();
+
+ map.insert(1, 2);
+ map.insert(3, 4);
+
+ let map_str = format!("{map:?}");
+
+ assert!(map_str == "{1: 2, 3: 4}" || map_str == "{3: 4, 1: 2}");
+ assert_eq!(format!("{empty:?}"), "{}");
+}
+
+#[test]
+fn test_reserve_shrink_to_fit() {
+ let mut m = HashMap::new();
+ m.insert(0, 0);
+ m.remove(&0);
+ assert!(m.capacity() >= m.len());
+ for i in 0..128 {
+ m.insert(i, i);
+ }
+ m.reserve(256);
+
+ let usable_cap = m.capacity();
+ for i in 128..(128 + 256) {
+ m.insert(i, i);
+ assert_eq!(m.capacity(), usable_cap);
+ }
+
+ for i in 100..(128 + 256) {
+ assert_eq!(m.remove(&i), Some(i));
+ }
+ m.shrink_to_fit();
+
+ assert_eq!(m.len(), 100);
+ assert!(!m.is_empty());
+ assert!(m.capacity() >= m.len());
+
+ for i in 0..100 {
+ assert_eq!(m.remove(&i), Some(i));
+ }
+ m.shrink_to_fit();
+ m.insert(0, 0);
+
+ assert_eq!(m.len(), 1);
+ assert!(m.capacity() >= m.len());
+ assert_eq!(m.remove(&0), Some(0));
+}
+
+#[test]
+fn test_from_iter() {
+ let xs = [(1, 1), (2, 2), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
+
+ let map: HashMap<_, _> = xs.iter().cloned().collect();
+
+ for &(k, v) in &xs {
+ assert_eq!(map.get(&k), Some(&v));
+ }
+
+ assert_eq!(map.iter().len(), xs.len() - 1);
+}
+
+#[test]
+fn test_size_hint() {
+ let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
+
+ let map: HashMap<_, _> = xs.iter().cloned().collect();
+
+ let mut iter = map.iter();
+
+ for _ in iter.by_ref().take(3) {}
+
+ assert_eq!(iter.size_hint(), (3, Some(3)));
+}
+
+#[test]
+fn test_iter_len() {
+ let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
+
+ let map: HashMap<_, _> = xs.iter().cloned().collect();
+
+ let mut iter = map.iter();
+
+ for _ in iter.by_ref().take(3) {}
+
+ assert_eq!(iter.len(), 3);
+}
+
+#[test]
+fn test_mut_size_hint() {
+ let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
+
+ let mut map: HashMap<_, _> = xs.iter().cloned().collect();
+
+ let mut iter = map.iter_mut();
+
+ for _ in iter.by_ref().take(3) {}
+
+ assert_eq!(iter.size_hint(), (3, Some(3)));
+}
+
+#[test]
+fn test_iter_mut_len() {
+ let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
+
+ let mut map: HashMap<_, _> = xs.iter().cloned().collect();
+
+ let mut iter = map.iter_mut();
+
+ for _ in iter.by_ref().take(3) {}
+
+ assert_eq!(iter.len(), 3);
+}
+
+#[test]
+fn test_index() {
+ let mut map = HashMap::new();
+
+ map.insert(1, 2);
+ map.insert(2, 1);
+ map.insert(3, 4);
+
+ assert_eq!(map[&2], 1);
+}
+
+#[test]
+#[should_panic]
+fn test_index_nonexistent() {
+ let mut map = HashMap::new();
+
+ map.insert(1, 2);
+ map.insert(2, 1);
+ map.insert(3, 4);
+
+ map[&4];
+}
+
+#[test]
+fn test_entry() {
+ let xs = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
+
+ let mut map: HashMap<_, _> = xs.iter().cloned().collect();
+
+ // Existing key (insert)
+ match map.entry(1) {
+ Vacant(_) => unreachable!(),
+ Occupied(mut view) => {
+ assert_eq!(view.get(), &10);
+ assert_eq!(view.insert(100), 10);
+ }
+ }
+ assert_eq!(map.get(&1).unwrap(), &100);
+ assert_eq!(map.len(), 6);
+
+ // Existing key (update)
+ match map.entry(2) {
+ Vacant(_) => unreachable!(),
+ Occupied(mut view) => {
+ let v = view.get_mut();
+ let new_v = (*v) * 10;
+ *v = new_v;
+ }
+ }
+ assert_eq!(map.get(&2).unwrap(), &200);
+ assert_eq!(map.len(), 6);
+
+ // Existing key (take)
+ match map.entry(3) {
+ Vacant(_) => unreachable!(),
+ Occupied(view) => {
+ assert_eq!(view.remove(), 30);
+ }
+ }
+ assert_eq!(map.get(&3), None);
+ assert_eq!(map.len(), 5);
+
+ // Inexistent key (insert)
+ match map.entry(10) {
+ Occupied(_) => unreachable!(),
+ Vacant(view) => {
+ assert_eq!(*view.insert(1000), 1000);
+ }
+ }
+ assert_eq!(map.get(&10).unwrap(), &1000);
+ assert_eq!(map.len(), 6);
+}
+
+#[test]
+fn test_entry_take_doesnt_corrupt() {
+ #![allow(deprecated)] //rand
+ // Test for #19292
+ fn check(m: &HashMap<i32, ()>) {
+ for k in m.keys() {
+ assert!(m.contains_key(k), "{k} is in keys() but not in the map?");
+ }
+ }
+
+ let mut m = HashMap::new();
+ let mut rng = thread_rng();
+
+ // Populate the map with some items.
+ for _ in 0..50 {
+ let x = rng.gen_range(-10, 10);
+ m.insert(x, ());
+ }
+
+ for _ in 0..1000 {
+ let x = rng.gen_range(-10, 10);
+ match m.entry(x) {
+ Vacant(_) => {}
+ Occupied(e) => {
+ e.remove();
+ }
+ }
+
+ check(&m);
+ }
+}
+
+#[test]
+fn test_extend_ref() {
+ let mut a = HashMap::new();
+ a.insert(1, "one");
+ let mut b = HashMap::new();
+ b.insert(2, "two");
+ b.insert(3, "three");
+
+ a.extend(&b);
+
+ assert_eq!(a.len(), 3);
+ assert_eq!(a[&1], "one");
+ assert_eq!(a[&2], "two");
+ assert_eq!(a[&3], "three");
+}
+
+#[test]
+fn test_capacity_not_less_than_len() {
+ let mut a = HashMap::new();
+ let mut item = 0;
+
+ for _ in 0..116 {
+ a.insert(item, 0);
+ item += 1;
+ }
+
+ assert!(a.capacity() > a.len());
+
+ let free = a.capacity() - a.len();
+ for _ in 0..free {
+ a.insert(item, 0);
+ item += 1;
+ }
+
+ assert_eq!(a.len(), a.capacity());
+
+ // Insert at capacity should cause allocation.
+ a.insert(item, 0);
+ assert!(a.capacity() > a.len());
+}
+
+#[test]
+fn test_occupied_entry_key() {
+ let mut a = HashMap::new();
+ let key = "hello there";
+ let value = "value goes here";
+ assert!(a.is_empty());
+ a.insert(key, value);
+ assert_eq!(a.len(), 1);
+ assert_eq!(a[key], value);
+
+ match a.entry(key) {
+ Vacant(_) => panic!(),
+ Occupied(e) => assert_eq!(key, *e.key()),
+ }
+ assert_eq!(a.len(), 1);
+ assert_eq!(a[key], value);
+}
+
+#[test]
+fn test_vacant_entry_key() {
+ let mut a = HashMap::new();
+ let key = "hello there";
+ let value = "value goes here";
+
+ assert!(a.is_empty());
+ match a.entry(key) {
+ Occupied(_) => panic!(),
+ Vacant(e) => {
+ assert_eq!(key, *e.key());
+ e.insert(value);
+ }
+ }
+ assert_eq!(a.len(), 1);
+ assert_eq!(a[key], value);
+}
+
+#[test]
+fn test_retain() {
+ let mut map: HashMap<i32, i32> = (0..100).map(|x| (x, x * 10)).collect();
+
+ map.retain(|&k, _| k % 2 == 0);
+ assert_eq!(map.len(), 50);
+ assert_eq!(map[&2], 20);
+ assert_eq!(map[&4], 40);
+ assert_eq!(map[&6], 60);
+}
+
+#[test]
+#[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc
+fn test_try_reserve() {
+ let mut empty_bytes: HashMap<u8, u8> = HashMap::new();
+
+ const MAX_USIZE: usize = usize::MAX;
+
+ assert_matches!(
+ empty_bytes.try_reserve(MAX_USIZE).map_err(|e| e.kind()),
+ Err(CapacityOverflow),
+ "usize::MAX should trigger an overflow!"
+ );
+
+ if let Err(AllocError { .. }) = empty_bytes.try_reserve(MAX_USIZE / 16).map_err(|e| e.kind()) {
+ } else {
+ // This may succeed if there is enough free memory. Attempt to
+ // allocate a few more hashmaps to ensure the allocation will fail.
+ let mut empty_bytes2: HashMap<u8, u8> = HashMap::new();
+ let _ = empty_bytes2.try_reserve(MAX_USIZE / 16);
+ let mut empty_bytes3: HashMap<u8, u8> = HashMap::new();
+ let _ = empty_bytes3.try_reserve(MAX_USIZE / 16);
+ let mut empty_bytes4: HashMap<u8, u8> = HashMap::new();
+ assert_matches!(
+ empty_bytes4.try_reserve(MAX_USIZE / 16).map_err(|e| e.kind()),
+ Err(AllocError { .. }),
+ "usize::MAX / 16 should trigger an OOM!"
+ );
+ }
+}
+
+#[test]
+fn test_raw_entry() {
+ use super::RawEntryMut::{Occupied, Vacant};
+
+ let xs = [(1i32, 10i32), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
+
+ let mut map: HashMap<_, _> = xs.iter().cloned().collect();
+
+ let compute_hash = |map: &HashMap<i32, i32>, k: i32| -> u64 {
+ use core::hash::{BuildHasher, Hash, Hasher};
+
+ let mut hasher = map.hasher().build_hasher();
+ k.hash(&mut hasher);
+ hasher.finish()
+ };
+
+ // Existing key (insert)
+ match map.raw_entry_mut().from_key(&1) {
+ Vacant(_) => unreachable!(),
+ Occupied(mut view) => {
+ assert_eq!(view.get(), &10);
+ assert_eq!(view.insert(100), 10);
+ }
+ }
+ let hash1 = compute_hash(&map, 1);
+ assert_eq!(map.raw_entry().from_key(&1).unwrap(), (&1, &100));
+ assert_eq!(map.raw_entry().from_hash(hash1, |k| *k == 1).unwrap(), (&1, &100));
+ assert_eq!(map.raw_entry().from_key_hashed_nocheck(hash1, &1).unwrap(), (&1, &100));
+ assert_eq!(map.len(), 6);
+
+ // Existing key (update)
+ match map.raw_entry_mut().from_key(&2) {
+ Vacant(_) => unreachable!(),
+ Occupied(mut view) => {
+ let v = view.get_mut();
+ let new_v = (*v) * 10;
+ *v = new_v;
+ }
+ }
+ let hash2 = compute_hash(&map, 2);
+ assert_eq!(map.raw_entry().from_key(&2).unwrap(), (&2, &200));
+ assert_eq!(map.raw_entry().from_hash(hash2, |k| *k == 2).unwrap(), (&2, &200));
+ assert_eq!(map.raw_entry().from_key_hashed_nocheck(hash2, &2).unwrap(), (&2, &200));
+ assert_eq!(map.len(), 6);
+
+ // Existing key (take)
+ let hash3 = compute_hash(&map, 3);
+ match map.raw_entry_mut().from_key_hashed_nocheck(hash3, &3) {
+ Vacant(_) => unreachable!(),
+ Occupied(view) => {
+ assert_eq!(view.remove_entry(), (3, 30));
+ }
+ }
+ assert_eq!(map.raw_entry().from_key(&3), None);
+ assert_eq!(map.raw_entry().from_hash(hash3, |k| *k == 3), None);
+ assert_eq!(map.raw_entry().from_key_hashed_nocheck(hash3, &3), None);
+ assert_eq!(map.len(), 5);
+
+ // Nonexistent key (insert)
+ match map.raw_entry_mut().from_key(&10) {
+ Occupied(_) => unreachable!(),
+ Vacant(view) => {
+ assert_eq!(view.insert(10, 1000), (&mut 10, &mut 1000));
+ }
+ }
+ assert_eq!(map.raw_entry().from_key(&10).unwrap(), (&10, &1000));
+ assert_eq!(map.len(), 6);
+
+ // Ensure all lookup methods produce equivalent results.
+ for k in 0..12 {
+ let hash = compute_hash(&map, k);
+ let v = map.get(&k).cloned();
+ let kv = v.as_ref().map(|v| (&k, v));
+
+ assert_eq!(map.raw_entry().from_key(&k), kv);
+ assert_eq!(map.raw_entry().from_hash(hash, |q| *q == k), kv);
+ assert_eq!(map.raw_entry().from_key_hashed_nocheck(hash, &k), kv);
+
+ match map.raw_entry_mut().from_key(&k) {
+ Occupied(mut o) => assert_eq!(Some(o.get_key_value()), kv),
+ Vacant(_) => assert_eq!(v, None),
+ }
+ match map.raw_entry_mut().from_key_hashed_nocheck(hash, &k) {
+ Occupied(mut o) => assert_eq!(Some(o.get_key_value()), kv),
+ Vacant(_) => assert_eq!(v, None),
+ }
+ match map.raw_entry_mut().from_hash(hash, |q| *q == k) {
+ Occupied(mut o) => assert_eq!(Some(o.get_key_value()), kv),
+ Vacant(_) => assert_eq!(v, None),
+ }
+ }
+}
+
+mod test_drain_filter {
+ use super::*;
+
+ use crate::panic::{catch_unwind, AssertUnwindSafe};
+ use crate::sync::atomic::{AtomicUsize, Ordering};
+
+ trait EqSorted: Iterator {
+ fn eq_sorted<I: IntoIterator<Item = Self::Item>>(self, other: I) -> bool;
+ }
+
+ impl<T: Iterator> EqSorted for T
+ where
+ T::Item: Eq + Ord,
+ {
+ fn eq_sorted<I: IntoIterator<Item = Self::Item>>(self, other: I) -> bool {
+ let mut v: Vec<_> = self.collect();
+ v.sort_unstable();
+ v.into_iter().eq(other)
+ }
+ }
+
+ #[test]
+ fn empty() {
+ let mut map: HashMap<i32, i32> = HashMap::new();
+ map.drain_filter(|_, _| unreachable!("there's nothing to decide on"));
+ assert!(map.is_empty());
+ }
+
+ #[test]
+ fn consuming_nothing() {
+ let pairs = (0..3).map(|i| (i, i));
+ let mut map: HashMap<_, _> = pairs.collect();
+ assert!(map.drain_filter(|_, _| false).eq_sorted(crate::iter::empty()));
+ assert_eq!(map.len(), 3);
+ }
+
+ #[test]
+ fn consuming_all() {
+ let pairs = (0..3).map(|i| (i, i));
+ let mut map: HashMap<_, _> = pairs.clone().collect();
+ assert!(map.drain_filter(|_, _| true).eq_sorted(pairs));
+ assert!(map.is_empty());
+ }
+
+ #[test]
+ fn mutating_and_keeping() {
+ let pairs = (0..3).map(|i| (i, i));
+ let mut map: HashMap<_, _> = pairs.collect();
+ assert!(
+ map.drain_filter(|_, v| {
+ *v += 6;
+ false
+ })
+ .eq_sorted(crate::iter::empty())
+ );
+ assert!(map.keys().copied().eq_sorted(0..3));
+ assert!(map.values().copied().eq_sorted(6..9));
+ }
+
+ #[test]
+ fn mutating_and_removing() {
+ let pairs = (0..3).map(|i| (i, i));
+ let mut map: HashMap<_, _> = pairs.collect();
+ assert!(
+ map.drain_filter(|_, v| {
+ *v += 6;
+ true
+ })
+ .eq_sorted((0..3).map(|i| (i, i + 6)))
+ );
+ assert!(map.is_empty());
+ }
+
+ #[test]
+ fn drop_panic_leak() {
+ static PREDS: AtomicUsize = AtomicUsize::new(0);
+ static DROPS: AtomicUsize = AtomicUsize::new(0);
+
+ struct D;
+ impl Drop for D {
+ fn drop(&mut self) {
+ if DROPS.fetch_add(1, Ordering::SeqCst) == 1 {
+ panic!("panic in `drop`");
+ }
+ }
+ }
+
+ let mut map = (0..3).map(|i| (i, D)).collect::<HashMap<_, _>>();
+
+ catch_unwind(move || {
+ drop(map.drain_filter(|_, _| {
+ PREDS.fetch_add(1, Ordering::SeqCst);
+ true
+ }))
+ })
+ .unwrap_err();
+
+ assert_eq!(PREDS.load(Ordering::SeqCst), 3);
+ assert_eq!(DROPS.load(Ordering::SeqCst), 3);
+ }
+
+ #[test]
+ fn pred_panic_leak() {
+ static PREDS: AtomicUsize = AtomicUsize::new(0);
+ static DROPS: AtomicUsize = AtomicUsize::new(0);
+
+ struct D;
+ impl Drop for D {
+ fn drop(&mut self) {
+ DROPS.fetch_add(1, Ordering::SeqCst);
+ }
+ }
+
+ let mut map = (0..3).map(|i| (i, D)).collect::<HashMap<_, _>>();
+
+ catch_unwind(AssertUnwindSafe(|| {
+ drop(map.drain_filter(|_, _| match PREDS.fetch_add(1, Ordering::SeqCst) {
+ 0 => true,
+ _ => panic!(),
+ }))
+ }))
+ .unwrap_err();
+
+ assert_eq!(PREDS.load(Ordering::SeqCst), 2);
+ assert_eq!(DROPS.load(Ordering::SeqCst), 1);
+ assert_eq!(map.len(), 2);
+ }
+
+ // Same as above, but attempt to use the iterator again after the panic in the predicate
+ #[test]
+ fn pred_panic_reuse() {
+ static PREDS: AtomicUsize = AtomicUsize::new(0);
+ static DROPS: AtomicUsize = AtomicUsize::new(0);
+
+ struct D;
+ impl Drop for D {
+ fn drop(&mut self) {
+ DROPS.fetch_add(1, Ordering::SeqCst);
+ }
+ }
+
+ let mut map = (0..3).map(|i| (i, D)).collect::<HashMap<_, _>>();
+
+ {
+ let mut it = map.drain_filter(|_, _| match PREDS.fetch_add(1, Ordering::SeqCst) {
+ 0 => true,
+ _ => panic!(),
+ });
+ catch_unwind(AssertUnwindSafe(|| while it.next().is_some() {})).unwrap_err();
+ // Iterator behaviour after a panic is explicitly unspecified,
+ // so this is just the current implementation:
+ let result = catch_unwind(AssertUnwindSafe(|| it.next()));
+ assert!(result.is_err());
+ }
+
+ assert_eq!(PREDS.load(Ordering::SeqCst), 3);
+ assert_eq!(DROPS.load(Ordering::SeqCst), 1);
+ assert_eq!(map.len(), 2);
+ }
+}
+
+#[test]
+fn from_array() {
+ let map = HashMap::from([(1, 2), (3, 4)]);
+ let unordered_duplicates = HashMap::from([(3, 4), (1, 2), (1, 2)]);
+ assert_eq!(map, unordered_duplicates);
+
+ // This next line must infer the hasher type parameter.
+ // If you make a change that causes this line to no longer infer,
+ // that's a problem!
+ let _must_not_require_type_annotation = HashMap::from([(1, 2)]);
+}
diff --git a/library/std/src/collections/hash/mod.rs b/library/std/src/collections/hash/mod.rs
new file mode 100644
index 000000000..348820af5
--- /dev/null
+++ b/library/std/src/collections/hash/mod.rs
@@ -0,0 +1,4 @@
+//! Unordered containers, implemented as hash-tables
+
+pub mod map;
+pub mod set;
diff --git a/library/std/src/collections/hash/set.rs b/library/std/src/collections/hash/set.rs
new file mode 100644
index 000000000..abff82788
--- /dev/null
+++ b/library/std/src/collections/hash/set.rs
@@ -0,0 +1,1844 @@
+#[cfg(test)]
+mod tests;
+
+use hashbrown::hash_set as base;
+
+use crate::borrow::Borrow;
+use crate::collections::TryReserveError;
+use crate::fmt;
+use crate::hash::{BuildHasher, Hash};
+use crate::iter::{Chain, FusedIterator};
+use crate::ops::{BitAnd, BitOr, BitXor, Sub};
+
+use super::map::{map_try_reserve_error, RandomState};
+
+// Future Optimization (FIXME!)
+// ============================
+//
+// Iteration over zero sized values is a noop. There is no need
+// for `bucket.val` in the case of HashSet. I suppose we would need HKT
+// to get rid of it properly.
+
+/// A [hash set] implemented as a `HashMap` where the value is `()`.
+///
+/// As with the [`HashMap`] type, a `HashSet` requires that the elements
+/// implement the [`Eq`] and [`Hash`] traits. This can frequently be achieved by
+/// using `#[derive(PartialEq, Eq, Hash)]`. If you implement these yourself,
+/// it is important that the following property holds:
+///
+/// ```text
+/// k1 == k2 -> hash(k1) == hash(k2)
+/// ```
+///
+/// In other words, if two keys are equal, their hashes must be equal.
+///
+///
+/// It is a logic error for a key to be modified in such a way that the key's
+/// hash, as determined by the [`Hash`] trait, or its equality, as determined by
+/// the [`Eq`] trait, changes while it is in the map. This is normally only
+/// possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code.
+/// The behavior resulting from such a logic error is not specified, but will
+/// be encapsulated to the `HashSet` that observed the logic error and not
+/// result in undefined behavior. This could include panics, incorrect results,
+/// aborts, memory leaks, and non-termination.
+///
+/// # Examples
+///
+/// ```
+/// use std::collections::HashSet;
+/// // Type inference lets us omit an explicit type signature (which
+/// // would be `HashSet<String>` in this example).
+/// let mut books = HashSet::new();
+///
+/// // Add some books.
+/// books.insert("A Dance With Dragons".to_string());
+/// books.insert("To Kill a Mockingbird".to_string());
+/// books.insert("The Odyssey".to_string());
+/// books.insert("The Great Gatsby".to_string());
+///
+/// // Check for a specific one.
+/// if !books.contains("The Winds of Winter") {
+/// println!("We have {} books, but The Winds of Winter ain't one.",
+/// books.len());
+/// }
+///
+/// // Remove a book.
+/// books.remove("The Odyssey");
+///
+/// // Iterate over everything.
+/// for book in &books {
+/// println!("{book}");
+/// }
+/// ```
+///
+/// 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
+/// future be implied by [`Eq`].
+///
+/// ```
+/// use std::collections::HashSet;
+/// #[derive(Hash, Eq, PartialEq, Debug)]
+/// struct Viking {
+/// name: String,
+/// power: usize,
+/// }
+///
+/// let mut vikings = HashSet::new();
+///
+/// vikings.insert(Viking { name: "Einar".to_string(), power: 9 });
+/// vikings.insert(Viking { name: "Einar".to_string(), power: 9 });
+/// vikings.insert(Viking { name: "Olaf".to_string(), power: 4 });
+/// vikings.insert(Viking { name: "Harald".to_string(), power: 8 });
+///
+/// // Use derived implementation to print the vikings.
+/// for x in &vikings {
+/// println!("{x:?}");
+/// }
+/// ```
+///
+/// A `HashSet` with a known list of items can be initialized from an array:
+///
+/// ```
+/// use std::collections::HashSet;
+///
+/// let viking_names = HashSet::from(["Einar", "Olaf", "Harald"]);
+/// ```
+///
+/// [hash set]: crate::collections#use-the-set-variant-of-any-of-these-maps-when
+/// [`HashMap`]: crate::collections::HashMap
+/// [`RefCell`]: crate::cell::RefCell
+/// [`Cell`]: crate::cell::Cell
+#[cfg_attr(not(test), rustc_diagnostic_item = "HashSet")]
+#[stable(feature = "rust1", since = "1.0.0")]
+pub struct HashSet<T, S = RandomState> {
+ base: base::HashSet<T, S>,
+}
+
+impl<T> HashSet<T, RandomState> {
+ /// 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 std::collections::HashSet;
+ /// let set: HashSet<i32> = HashSet::new();
+ /// ```
+ #[inline]
+ #[must_use]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn new() -> HashSet<T, RandomState> {
+ Default::default()
+ }
+
+ /// Creates an empty `HashSet` with at least the specified capacity.
+ ///
+ /// The hash set will be able to hold at least `capacity` elements without
+ /// reallocating. This method is allowed to allocate for more elements than
+ /// `capacity`. If `capacity` is 0, the hash set will not allocate.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashSet;
+ /// let set: HashSet<i32> = HashSet::with_capacity(10);
+ /// assert!(set.capacity() >= 10);
+ /// ```
+ #[inline]
+ #[must_use]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn with_capacity(capacity: usize) -> HashSet<T, RandomState> {
+ HashSet { base: base::HashSet::with_capacity_and_hasher(capacity, Default::default()) }
+ }
+}
+
+impl<T, S> HashSet<T, S> {
+ /// Returns the number of elements the set can hold without reallocating.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashSet;
+ /// let set: HashSet<i32> = HashSet::with_capacity(100);
+ /// assert!(set.capacity() >= 100);
+ /// ```
+ #[inline]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn capacity(&self) -> usize {
+ self.base.capacity()
+ }
+
+ /// An iterator visiting all elements in arbitrary order.
+ /// The iterator element type is `&'a T`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashSet;
+ /// let mut set = HashSet::new();
+ /// set.insert("a");
+ /// set.insert("b");
+ ///
+ /// // Will print in an arbitrary order.
+ /// for x in set.iter() {
+ /// println!("{x}");
+ /// }
+ /// ```
+ ///
+ /// # Performance
+ ///
+ /// In the current implementation, iterating over set takes O(capacity) time
+ /// instead of O(len) because it internally visits empty buckets too.
+ #[inline]
+ #[rustc_lint_query_instability]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn iter(&self) -> Iter<'_, T> {
+ Iter { base: self.base.iter() }
+ }
+
+ /// Returns the number of elements in the set.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashSet;
+ ///
+ /// let mut v = HashSet::new();
+ /// assert_eq!(v.len(), 0);
+ /// v.insert(1);
+ /// assert_eq!(v.len(), 1);
+ /// ```
+ #[inline]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn len(&self) -> usize {
+ self.base.len()
+ }
+
+ /// Returns `true` if the set contains no elements.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashSet;
+ ///
+ /// let mut v = HashSet::new();
+ /// assert!(v.is_empty());
+ /// v.insert(1);
+ /// assert!(!v.is_empty());
+ /// ```
+ #[inline]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn is_empty(&self) -> bool {
+ self.base.is_empty()
+ }
+
+ /// Clears the set, returning all elements as an iterator. Keeps the
+ /// allocated memory for reuse.
+ ///
+ /// If the returned iterator is dropped before being fully consumed, it
+ /// drops the remaining elements. The returned iterator keeps a mutable
+ /// borrow on the vector to optimize its implementation.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashSet;
+ ///
+ /// let mut set = HashSet::from([1, 2, 3]);
+ /// assert!(!set.is_empty());
+ ///
+ /// // print 1, 2, 3 in an arbitrary order
+ /// for i in set.drain() {
+ /// println!("{i}");
+ /// }
+ ///
+ /// assert!(set.is_empty());
+ /// ```
+ #[inline]
+ #[rustc_lint_query_instability]
+ #[stable(feature = "drain", since = "1.6.0")]
+ pub fn drain(&mut self) -> Drain<'_, T> {
+ Drain { base: self.base.drain() }
+ }
+
+ /// Creates an iterator which uses a closure to determine if a value should be removed.
+ ///
+ /// If the closure returns true, then the value is removed and yielded.
+ /// If the closure returns false, the value will remain in the list and will not be yielded
+ /// by the iterator.
+ ///
+ /// If the iterator is only partially consumed or not consumed at all, each of the remaining
+ /// values will still be subjected to the closure and removed and dropped if it returns true.
+ ///
+ /// It is unspecified how many more values will be subjected to the closure
+ /// if a panic occurs in the closure, or if a panic occurs while dropping a value, or if the
+ /// `DrainFilter` itself is leaked.
+ ///
+ /// # Examples
+ ///
+ /// Splitting a set into even and odd values, reusing the original set:
+ ///
+ /// ```
+ /// #![feature(hash_drain_filter)]
+ /// use std::collections::HashSet;
+ ///
+ /// let mut set: HashSet<i32> = (0..8).collect();
+ /// let drained: HashSet<i32> = set.drain_filter(|v| v % 2 == 0).collect();
+ ///
+ /// let mut evens = drained.into_iter().collect::<Vec<_>>();
+ /// let mut odds = set.into_iter().collect::<Vec<_>>();
+ /// evens.sort();
+ /// odds.sort();
+ ///
+ /// assert_eq!(evens, vec![0, 2, 4, 6]);
+ /// assert_eq!(odds, vec![1, 3, 5, 7]);
+ /// ```
+ #[inline]
+ #[rustc_lint_query_instability]
+ #[unstable(feature = "hash_drain_filter", issue = "59618")]
+ pub fn drain_filter<F>(&mut self, pred: F) -> DrainFilter<'_, T, F>
+ where
+ F: FnMut(&T) -> bool,
+ {
+ DrainFilter { base: self.base.drain_filter(pred) }
+ }
+
+ /// Retains only the elements specified by the predicate.
+ ///
+ /// In other words, remove all elements `e` for which `f(&e)` returns `false`.
+ /// The elements are visited in unsorted (and unspecified) order.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashSet;
+ ///
+ /// let mut set = HashSet::from([1, 2, 3, 4, 5, 6]);
+ /// set.retain(|&k| k % 2 == 0);
+ /// assert_eq!(set.len(), 3);
+ /// ```
+ ///
+ /// # Performance
+ ///
+ /// In the current implementation, this operation takes O(capacity) time
+ /// instead of O(len) because it internally visits empty buckets too.
+ #[rustc_lint_query_instability]
+ #[stable(feature = "retain_hash_collection", since = "1.18.0")]
+ pub fn retain<F>(&mut self, f: F)
+ where
+ F: FnMut(&T) -> bool,
+ {
+ self.base.retain(f)
+ }
+
+ /// Clears the set, removing all values.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashSet;
+ ///
+ /// let mut v = HashSet::new();
+ /// v.insert(1);
+ /// v.clear();
+ /// assert!(v.is_empty());
+ /// ```
+ #[inline]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn clear(&mut self) {
+ self.base.clear()
+ }
+
+ /// 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 std::collections::HashSet;
+ /// use std::collections::hash_map::RandomState;
+ ///
+ /// let s = RandomState::new();
+ /// let mut set = HashSet::with_hasher(s);
+ /// set.insert(2);
+ /// ```
+ #[inline]
+ #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
+ pub fn with_hasher(hasher: S) -> HashSet<T, S> {
+ HashSet { base: base::HashSet::with_hasher(hasher) }
+ }
+
+ /// Creates an empty `HashSet` with at least the specified capacity, using
+ /// `hasher` to hash the keys.
+ ///
+ /// The hash set will be able to hold at least `capacity` elements without
+ /// reallocating. This method is allowed to allocate for more elements than
+ /// `capacity`. 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 std::collections::HashSet;
+ /// use std::collections::hash_map::RandomState;
+ ///
+ /// let s = RandomState::new();
+ /// let mut set = HashSet::with_capacity_and_hasher(10, s);
+ /// set.insert(1);
+ /// ```
+ #[inline]
+ #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
+ pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> HashSet<T, S> {
+ HashSet { base: base::HashSet::with_capacity_and_hasher(capacity, hasher) }
+ }
+
+ /// Returns a reference to the set's [`BuildHasher`].
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashSet;
+ /// use std::collections::hash_map::RandomState;
+ ///
+ /// let hasher = RandomState::new();
+ /// let set: HashSet<i32> = HashSet::with_hasher(hasher);
+ /// let hasher: &RandomState = set.hasher();
+ /// ```
+ #[inline]
+ #[stable(feature = "hashmap_public_hasher", since = "1.9.0")]
+ pub fn hasher(&self) -> &S {
+ self.base.hasher()
+ }
+}
+
+impl<T, S> HashSet<T, S>
+where
+ T: Eq + Hash,
+ S: BuildHasher,
+{
+ /// Reserves capacity for at least `additional` more elements to be inserted
+ /// in the `HashSet`. The collection may reserve more space to speculatively
+ /// avoid frequent reallocations. After calling `reserve`,
+ /// capacity will be greater than or equal to `self.len() + additional`.
+ /// Does nothing if capacity is already sufficient.
+ ///
+ /// # Panics
+ ///
+ /// Panics if the new allocation size overflows `usize`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashSet;
+ /// let mut set: HashSet<i32> = HashSet::new();
+ /// set.reserve(10);
+ /// assert!(set.capacity() >= 10);
+ /// ```
+ #[inline]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn reserve(&mut self, additional: usize) {
+ self.base.reserve(additional)
+ }
+
+ /// Tries to reserve capacity for at least `additional` more elements to be inserted
+ /// in the `HashSet`. The collection may reserve more space to speculatively
+ /// avoid frequent reallocations. After calling `reserve`,
+ /// capacity will be greater than or equal to `self.len() + additional` if
+ /// it returns `Ok(())`.
+ /// Does nothing if capacity is already sufficient.
+ ///
+ /// # Errors
+ ///
+ /// If the capacity overflows, or the allocator reports a failure, then an error
+ /// is returned.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashSet;
+ /// let mut set: HashSet<i32> = HashSet::new();
+ /// set.try_reserve(10).expect("why is the test harness OOMing on a handful of bytes?");
+ /// ```
+ #[inline]
+ #[stable(feature = "try_reserve", since = "1.57.0")]
+ pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
+ self.base.try_reserve(additional).map_err(map_try_reserve_error)
+ }
+
+ /// Shrinks the capacity of the set as much as possible. It will drop
+ /// down as much as possible while maintaining the internal rules
+ /// and possibly leaving some space in accordance with the resize policy.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashSet;
+ ///
+ /// let mut set = HashSet::with_capacity(100);
+ /// set.insert(1);
+ /// set.insert(2);
+ /// assert!(set.capacity() >= 100);
+ /// set.shrink_to_fit();
+ /// assert!(set.capacity() >= 2);
+ /// ```
+ #[inline]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn shrink_to_fit(&mut self) {
+ self.base.shrink_to_fit()
+ }
+
+ /// Shrinks the capacity of the set with a lower limit. It will drop
+ /// down no lower than the supplied limit while maintaining the internal rules
+ /// and possibly leaving some space in accordance with the resize policy.
+ ///
+ /// If the current capacity is less than the lower limit, this is a no-op.
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashSet;
+ ///
+ /// let mut set = HashSet::with_capacity(100);
+ /// set.insert(1);
+ /// set.insert(2);
+ /// assert!(set.capacity() >= 100);
+ /// set.shrink_to(10);
+ /// assert!(set.capacity() >= 10);
+ /// set.shrink_to(0);
+ /// assert!(set.capacity() >= 2);
+ /// ```
+ #[inline]
+ #[stable(feature = "shrink_to", since = "1.56.0")]
+ pub fn shrink_to(&mut self, min_capacity: usize) {
+ self.base.shrink_to(min_capacity)
+ }
+
+ /// Visits the values representing the difference,
+ /// i.e., the values that are in `self` but not in `other`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashSet;
+ /// let a = HashSet::from([1, 2, 3]);
+ /// let b = HashSet::from([4, 2, 3, 4]);
+ ///
+ /// // Can be seen as `a - b`.
+ /// for x in a.difference(&b) {
+ /// println!("{x}"); // Print 1
+ /// }
+ ///
+ /// let diff: HashSet<_> = a.difference(&b).collect();
+ /// assert_eq!(diff, [1].iter().collect());
+ ///
+ /// // Note that difference is not symmetric,
+ /// // and `b - a` means something else:
+ /// let diff: HashSet<_> = b.difference(&a).collect();
+ /// assert_eq!(diff, [4].iter().collect());
+ /// ```
+ #[inline]
+ #[rustc_lint_query_instability]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn difference<'a>(&'a self, other: &'a HashSet<T, S>) -> Difference<'a, T, S> {
+ Difference { iter: self.iter(), other }
+ }
+
+ /// Visits the values representing the symmetric difference,
+ /// i.e., the values that are in `self` or in `other` but not in both.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashSet;
+ /// let a = HashSet::from([1, 2, 3]);
+ /// let b = HashSet::from([4, 2, 3, 4]);
+ ///
+ /// // Print 1, 4 in arbitrary order.
+ /// for x in a.symmetric_difference(&b) {
+ /// println!("{x}");
+ /// }
+ ///
+ /// let diff1: HashSet<_> = a.symmetric_difference(&b).collect();
+ /// let diff2: HashSet<_> = b.symmetric_difference(&a).collect();
+ ///
+ /// assert_eq!(diff1, diff2);
+ /// assert_eq!(diff1, [1, 4].iter().collect());
+ /// ```
+ #[inline]
+ #[rustc_lint_query_instability]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn symmetric_difference<'a>(
+ &'a self,
+ other: &'a HashSet<T, S>,
+ ) -> SymmetricDifference<'a, T, S> {
+ SymmetricDifference { iter: self.difference(other).chain(other.difference(self)) }
+ }
+
+ /// Visits the values representing the intersection,
+ /// i.e., the values that are both in `self` and `other`.
+ ///
+ /// When an equal element is present in `self` and `other`
+ /// then the resulting `Intersection` may yield references to
+ /// one or the other. This can be relevant if `T` contains fields which
+ /// are not compared by its `Eq` implementation, and may hold different
+ /// value between the two equal copies of `T` in the two sets.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashSet;
+ /// let a = HashSet::from([1, 2, 3]);
+ /// let b = HashSet::from([4, 2, 3, 4]);
+ ///
+ /// // Print 2, 3 in arbitrary order.
+ /// for x in a.intersection(&b) {
+ /// println!("{x}");
+ /// }
+ ///
+ /// let intersection: HashSet<_> = a.intersection(&b).collect();
+ /// assert_eq!(intersection, [2, 3].iter().collect());
+ /// ```
+ #[inline]
+ #[rustc_lint_query_instability]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn intersection<'a>(&'a self, other: &'a HashSet<T, S>) -> Intersection<'a, T, S> {
+ if self.len() <= other.len() {
+ Intersection { iter: self.iter(), other }
+ } else {
+ Intersection { iter: other.iter(), other: self }
+ }
+ }
+
+ /// Visits the values representing the union,
+ /// i.e., all the values in `self` or `other`, without duplicates.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashSet;
+ /// let a = HashSet::from([1, 2, 3]);
+ /// let b = HashSet::from([4, 2, 3, 4]);
+ ///
+ /// // Print 1, 2, 3, 4 in arbitrary order.
+ /// for x in a.union(&b) {
+ /// println!("{x}");
+ /// }
+ ///
+ /// let union: HashSet<_> = a.union(&b).collect();
+ /// assert_eq!(union, [1, 2, 3, 4].iter().collect());
+ /// ```
+ #[inline]
+ #[rustc_lint_query_instability]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn union<'a>(&'a self, other: &'a HashSet<T, S>) -> Union<'a, T, S> {
+ if self.len() >= other.len() {
+ Union { iter: self.iter().chain(other.difference(self)) }
+ } else {
+ Union { iter: other.iter().chain(self.difference(other)) }
+ }
+ }
+
+ /// Returns `true` if the set contains a value.
+ ///
+ /// The value may be any borrowed form of the set's value type, but
+ /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
+ /// the value type.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashSet;
+ ///
+ /// let set = HashSet::from([1, 2, 3]);
+ /// assert_eq!(set.contains(&1), true);
+ /// assert_eq!(set.contains(&4), false);
+ /// ```
+ #[inline]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool
+ where
+ T: Borrow<Q>,
+ Q: Hash + Eq,
+ {
+ self.base.contains(value)
+ }
+
+ /// Returns a reference to the value in the set, if any, that is equal to the given value.
+ ///
+ /// The value may be any borrowed form of the set's value type, but
+ /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
+ /// the value type.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashSet;
+ ///
+ /// let set = HashSet::from([1, 2, 3]);
+ /// assert_eq!(set.get(&2), Some(&2));
+ /// assert_eq!(set.get(&4), None);
+ /// ```
+ #[inline]
+ #[stable(feature = "set_recovery", since = "1.9.0")]
+ pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T>
+ where
+ T: Borrow<Q>,
+ Q: Hash + Eq,
+ {
+ self.base.get(value)
+ }
+
+ /// Inserts the given `value` into the set if it is not present, then
+ /// returns a reference to the value in the set.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// #![feature(hash_set_entry)]
+ ///
+ /// use std::collections::HashSet;
+ ///
+ /// let mut set = HashSet::from([1, 2, 3]);
+ /// assert_eq!(set.len(), 3);
+ /// assert_eq!(set.get_or_insert(2), &2);
+ /// assert_eq!(set.get_or_insert(100), &100);
+ /// assert_eq!(set.len(), 4); // 100 was inserted
+ /// ```
+ #[inline]
+ #[unstable(feature = "hash_set_entry", issue = "60896")]
+ pub fn get_or_insert(&mut self, value: T) -> &T {
+ // Although the raw entry gives us `&mut T`, we only return `&T` to be consistent with
+ // `get`. Key mutation is "raw" because you're not supposed to affect `Eq` or `Hash`.
+ self.base.get_or_insert(value)
+ }
+
+ /// Inserts an owned copy of the given `value` into the set if it is not
+ /// present, then returns a reference to the value in the set.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// #![feature(hash_set_entry)]
+ ///
+ /// use std::collections::HashSet;
+ ///
+ /// let mut set: HashSet<String> = ["cat", "dog", "horse"]
+ /// .iter().map(|&pet| pet.to_owned()).collect();
+ ///
+ /// assert_eq!(set.len(), 3);
+ /// for &pet in &["cat", "dog", "fish"] {
+ /// let value = set.get_or_insert_owned(pet);
+ /// assert_eq!(value, pet);
+ /// }
+ /// assert_eq!(set.len(), 4); // a new "fish" was inserted
+ /// ```
+ #[inline]
+ #[unstable(feature = "hash_set_entry", issue = "60896")]
+ pub fn get_or_insert_owned<Q: ?Sized>(&mut self, value: &Q) -> &T
+ where
+ T: Borrow<Q>,
+ Q: Hash + Eq + ToOwned<Owned = T>,
+ {
+ // Although the raw entry gives us `&mut T`, we only return `&T` to be consistent with
+ // `get`. Key mutation is "raw" because you're not supposed to affect `Eq` or `Hash`.
+ self.base.get_or_insert_owned(value)
+ }
+
+ /// Inserts a value computed from `f` into the set if the given `value` is
+ /// not present, then returns a reference to the value in the set.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// #![feature(hash_set_entry)]
+ ///
+ /// use std::collections::HashSet;
+ ///
+ /// let mut set: HashSet<String> = ["cat", "dog", "horse"]
+ /// .iter().map(|&pet| pet.to_owned()).collect();
+ ///
+ /// assert_eq!(set.len(), 3);
+ /// for &pet in &["cat", "dog", "fish"] {
+ /// let value = set.get_or_insert_with(pet, str::to_owned);
+ /// assert_eq!(value, pet);
+ /// }
+ /// assert_eq!(set.len(), 4); // a new "fish" was inserted
+ /// ```
+ #[inline]
+ #[unstable(feature = "hash_set_entry", issue = "60896")]
+ pub fn get_or_insert_with<Q: ?Sized, F>(&mut self, value: &Q, f: F) -> &T
+ where
+ T: Borrow<Q>,
+ Q: Hash + Eq,
+ F: FnOnce(&Q) -> T,
+ {
+ // Although the raw entry gives us `&mut T`, we only return `&T` to be consistent with
+ // `get`. Key mutation is "raw" because you're not supposed to affect `Eq` or `Hash`.
+ self.base.get_or_insert_with(value, f)
+ }
+
+ /// Returns `true` if `self` has no elements in common with `other`.
+ /// This is equivalent to checking for an empty intersection.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashSet;
+ ///
+ /// let a = HashSet::from([1, 2, 3]);
+ /// let mut b = HashSet::new();
+ ///
+ /// assert_eq!(a.is_disjoint(&b), true);
+ /// b.insert(4);
+ /// assert_eq!(a.is_disjoint(&b), true);
+ /// b.insert(1);
+ /// assert_eq!(a.is_disjoint(&b), false);
+ /// ```
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn is_disjoint(&self, other: &HashSet<T, S>) -> bool {
+ if self.len() <= other.len() {
+ self.iter().all(|v| !other.contains(v))
+ } else {
+ other.iter().all(|v| !self.contains(v))
+ }
+ }
+
+ /// Returns `true` if the set is a subset of another,
+ /// i.e., `other` contains at least all the values in `self`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashSet;
+ ///
+ /// let sup = HashSet::from([1, 2, 3]);
+ /// let mut set = HashSet::new();
+ ///
+ /// assert_eq!(set.is_subset(&sup), true);
+ /// set.insert(2);
+ /// assert_eq!(set.is_subset(&sup), true);
+ /// set.insert(4);
+ /// assert_eq!(set.is_subset(&sup), false);
+ /// ```
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn is_subset(&self, other: &HashSet<T, S>) -> bool {
+ if self.len() <= other.len() { self.iter().all(|v| other.contains(v)) } else { false }
+ }
+
+ /// Returns `true` if the set is a superset of another,
+ /// i.e., `self` contains at least all the values in `other`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashSet;
+ ///
+ /// let sub = HashSet::from([1, 2]);
+ /// let mut set = HashSet::new();
+ ///
+ /// assert_eq!(set.is_superset(&sub), false);
+ ///
+ /// set.insert(0);
+ /// set.insert(1);
+ /// assert_eq!(set.is_superset(&sub), false);
+ ///
+ /// set.insert(2);
+ /// assert_eq!(set.is_superset(&sub), true);
+ /// ```
+ #[inline]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn is_superset(&self, other: &HashSet<T, S>) -> bool {
+ other.is_subset(self)
+ }
+
+ /// Adds a value to the set.
+ ///
+ /// Returns whether the value was newly inserted. That is:
+ ///
+ /// - If the set did not previously contain this value, `true` is returned.
+ /// - If the set already contained this value, `false` is returned.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashSet;
+ ///
+ /// let mut set = HashSet::new();
+ ///
+ /// assert_eq!(set.insert(2), true);
+ /// assert_eq!(set.insert(2), false);
+ /// assert_eq!(set.len(), 1);
+ /// ```
+ #[inline]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn insert(&mut self, value: T) -> bool {
+ self.base.insert(value)
+ }
+
+ /// Adds a value to the set, replacing the existing value, if any, that is equal to the given
+ /// one. Returns the replaced value.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashSet;
+ ///
+ /// let mut set = HashSet::new();
+ /// set.insert(Vec::<i32>::new());
+ ///
+ /// assert_eq!(set.get(&[][..]).unwrap().capacity(), 0);
+ /// set.replace(Vec::with_capacity(10));
+ /// assert_eq!(set.get(&[][..]).unwrap().capacity(), 10);
+ /// ```
+ #[inline]
+ #[stable(feature = "set_recovery", since = "1.9.0")]
+ pub fn replace(&mut self, value: T) -> Option<T> {
+ self.base.replace(value)
+ }
+
+ /// Removes a value from the set. Returns whether the value was
+ /// present in the set.
+ ///
+ /// The value may be any borrowed form of the set's value type, but
+ /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
+ /// the value type.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashSet;
+ ///
+ /// let mut set = HashSet::new();
+ ///
+ /// set.insert(2);
+ /// assert_eq!(set.remove(&2), true);
+ /// assert_eq!(set.remove(&2), false);
+ /// ```
+ #[inline]
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool
+ where
+ T: Borrow<Q>,
+ Q: Hash + Eq,
+ {
+ self.base.remove(value)
+ }
+
+ /// Removes and returns the value in the set, if any, that is equal to the given one.
+ ///
+ /// The value may be any borrowed form of the set's value type, but
+ /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
+ /// the value type.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashSet;
+ ///
+ /// let mut set = HashSet::from([1, 2, 3]);
+ /// assert_eq!(set.take(&2), Some(2));
+ /// assert_eq!(set.take(&2), None);
+ /// ```
+ #[inline]
+ #[stable(feature = "set_recovery", since = "1.9.0")]
+ pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T>
+ where
+ T: Borrow<Q>,
+ Q: Hash + Eq,
+ {
+ self.base.take(value)
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T, S> Clone for HashSet<T, S>
+where
+ T: Clone,
+ S: Clone,
+{
+ #[inline]
+ fn clone(&self) -> Self {
+ Self { base: self.base.clone() }
+ }
+
+ #[inline]
+ fn clone_from(&mut self, other: &Self) {
+ self.base.clone_from(&other.base);
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T, S> PartialEq for HashSet<T, S>
+where
+ T: Eq + Hash,
+ S: BuildHasher,
+{
+ fn eq(&self, other: &HashSet<T, S>) -> bool {
+ if self.len() != other.len() {
+ return false;
+ }
+
+ self.iter().all(|key| other.contains(key))
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T, S> Eq for HashSet<T, S>
+where
+ T: Eq + Hash,
+ S: BuildHasher,
+{
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T, S> fmt::Debug for HashSet<T, S>
+where
+ T: fmt::Debug,
+{
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_set().entries(self.iter()).finish()
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T, S> FromIterator<T> for HashSet<T, S>
+where
+ T: Eq + Hash,
+ S: BuildHasher + Default,
+{
+ #[inline]
+ fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> HashSet<T, S> {
+ let mut set = HashSet::with_hasher(Default::default());
+ set.extend(iter);
+ set
+ }
+}
+
+#[stable(feature = "std_collections_from_array", since = "1.56.0")]
+// Note: as what is currently the most convenient built-in way to construct
+// a HashSet, a simple usage of this function must not *require* the user
+// to provide a type annotation in order to infer the third type parameter
+// (the hasher parameter, conventionally "S").
+// To that end, this impl is defined using RandomState as the concrete
+// type of S, rather than being generic over `S: BuildHasher + Default`.
+// It is expected that users who want to specify a hasher will manually use
+// `with_capacity_and_hasher`.
+// If type parameter defaults worked on impls, and if type parameter
+// defaults could be mixed with const generics, then perhaps
+// this could be generalized.
+// See also the equivalent impl on HashMap.
+impl<T, const N: usize> From<[T; N]> for HashSet<T, RandomState>
+where
+ T: Eq + Hash,
+{
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashSet;
+ ///
+ /// let set1 = HashSet::from([1, 2, 3, 4]);
+ /// let set2: HashSet<_> = [1, 2, 3, 4].into();
+ /// assert_eq!(set1, set2);
+ /// ```
+ fn from(arr: [T; N]) -> Self {
+ Self::from_iter(arr)
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T, S> Extend<T> for HashSet<T, S>
+where
+ T: Eq + Hash,
+ S: BuildHasher,
+{
+ #[inline]
+ fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
+ self.base.extend(iter);
+ }
+
+ #[inline]
+ fn extend_one(&mut self, item: T) {
+ self.base.insert(item);
+ }
+
+ #[inline]
+ fn extend_reserve(&mut self, additional: usize) {
+ self.base.extend_reserve(additional);
+ }
+}
+
+#[stable(feature = "hash_extend_copy", since = "1.4.0")]
+impl<'a, T, S> Extend<&'a T> for HashSet<T, S>
+where
+ T: 'a + Eq + Hash + Copy,
+ S: BuildHasher,
+{
+ #[inline]
+ fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
+ self.extend(iter.into_iter().cloned());
+ }
+
+ #[inline]
+ fn extend_one(&mut self, &item: &'a T) {
+ self.base.insert(item);
+ }
+
+ #[inline]
+ fn extend_reserve(&mut self, additional: usize) {
+ Extend::<T>::extend_reserve(self, additional)
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T, S> Default for HashSet<T, S>
+where
+ S: Default,
+{
+ /// Creates an empty `HashSet<T, S>` with the `Default` value for the hasher.
+ #[inline]
+ fn default() -> HashSet<T, S> {
+ HashSet { base: Default::default() }
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T, S> BitOr<&HashSet<T, S>> for &HashSet<T, S>
+where
+ T: Eq + Hash + Clone,
+ S: BuildHasher + Default,
+{
+ type Output = HashSet<T, S>;
+
+ /// Returns the union of `self` and `rhs` as a new `HashSet<T, S>`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashSet;
+ ///
+ /// let a = HashSet::from([1, 2, 3]);
+ /// let b = HashSet::from([3, 4, 5]);
+ ///
+ /// let set = &a | &b;
+ ///
+ /// let mut i = 0;
+ /// let expected = [1, 2, 3, 4, 5];
+ /// for x in &set {
+ /// assert!(expected.contains(x));
+ /// i += 1;
+ /// }
+ /// assert_eq!(i, expected.len());
+ /// ```
+ fn bitor(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
+ self.union(rhs).cloned().collect()
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T, S> BitAnd<&HashSet<T, S>> for &HashSet<T, S>
+where
+ T: Eq + Hash + Clone,
+ S: BuildHasher + Default,
+{
+ type Output = HashSet<T, S>;
+
+ /// Returns the intersection of `self` and `rhs` as a new `HashSet<T, S>`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashSet;
+ ///
+ /// let a = HashSet::from([1, 2, 3]);
+ /// let b = HashSet::from([2, 3, 4]);
+ ///
+ /// let set = &a & &b;
+ ///
+ /// let mut i = 0;
+ /// let expected = [2, 3];
+ /// for x in &set {
+ /// assert!(expected.contains(x));
+ /// i += 1;
+ /// }
+ /// assert_eq!(i, expected.len());
+ /// ```
+ fn bitand(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
+ self.intersection(rhs).cloned().collect()
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T, S> BitXor<&HashSet<T, S>> for &HashSet<T, S>
+where
+ T: Eq + Hash + Clone,
+ S: BuildHasher + Default,
+{
+ type Output = HashSet<T, S>;
+
+ /// Returns the symmetric difference of `self` and `rhs` as a new `HashSet<T, S>`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashSet;
+ ///
+ /// let a = HashSet::from([1, 2, 3]);
+ /// let b = HashSet::from([3, 4, 5]);
+ ///
+ /// let set = &a ^ &b;
+ ///
+ /// let mut i = 0;
+ /// let expected = [1, 2, 4, 5];
+ /// for x in &set {
+ /// assert!(expected.contains(x));
+ /// i += 1;
+ /// }
+ /// assert_eq!(i, expected.len());
+ /// ```
+ fn bitxor(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
+ self.symmetric_difference(rhs).cloned().collect()
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T, S> Sub<&HashSet<T, S>> for &HashSet<T, S>
+where
+ T: Eq + Hash + Clone,
+ S: BuildHasher + Default,
+{
+ type Output = HashSet<T, S>;
+
+ /// Returns the difference of `self` and `rhs` as a new `HashSet<T, S>`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashSet;
+ ///
+ /// let a = HashSet::from([1, 2, 3]);
+ /// let b = HashSet::from([3, 4, 5]);
+ ///
+ /// let set = &a - &b;
+ ///
+ /// let mut i = 0;
+ /// let expected = [1, 2];
+ /// for x in &set {
+ /// assert!(expected.contains(x));
+ /// i += 1;
+ /// }
+ /// assert_eq!(i, expected.len());
+ /// ```
+ fn sub(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
+ self.difference(rhs).cloned().collect()
+ }
+}
+
+/// An iterator over the items of a `HashSet`.
+///
+/// This `struct` is created by the [`iter`] method on [`HashSet`].
+/// See its documentation for more.
+///
+/// [`iter`]: HashSet::iter
+///
+/// # Examples
+///
+/// ```
+/// use std::collections::HashSet;
+///
+/// let a = HashSet::from([1, 2, 3]);
+///
+/// let mut iter = a.iter();
+/// ```
+#[stable(feature = "rust1", since = "1.0.0")]
+pub struct Iter<'a, K: 'a> {
+ base: base::Iter<'a, K>,
+}
+
+/// An owning iterator over the items of a `HashSet`.
+///
+/// This `struct` is created by the [`into_iter`] method on [`HashSet`]
+/// (provided by the [`IntoIterator`] trait). See its documentation for more.
+///
+/// [`into_iter`]: IntoIterator::into_iter
+/// [`IntoIterator`]: crate::iter::IntoIterator
+///
+/// # Examples
+///
+/// ```
+/// use std::collections::HashSet;
+///
+/// let a = HashSet::from([1, 2, 3]);
+///
+/// let mut iter = a.into_iter();
+/// ```
+#[stable(feature = "rust1", since = "1.0.0")]
+pub struct IntoIter<K> {
+ base: base::IntoIter<K>,
+}
+
+/// A draining iterator over the items of a `HashSet`.
+///
+/// This `struct` is created by the [`drain`] method on [`HashSet`].
+/// See its documentation for more.
+///
+/// [`drain`]: HashSet::drain
+///
+/// # Examples
+///
+/// ```
+/// use std::collections::HashSet;
+///
+/// let mut a = HashSet::from([1, 2, 3]);
+///
+/// let mut drain = a.drain();
+/// ```
+#[stable(feature = "rust1", since = "1.0.0")]
+pub struct Drain<'a, K: 'a> {
+ base: base::Drain<'a, K>,
+}
+
+/// A draining, filtering iterator over the items of a `HashSet`.
+///
+/// This `struct` is created by the [`drain_filter`] method on [`HashSet`].
+///
+/// [`drain_filter`]: HashSet::drain_filter
+///
+/// # Examples
+///
+/// ```
+/// #![feature(hash_drain_filter)]
+///
+/// use std::collections::HashSet;
+///
+/// let mut a = HashSet::from([1, 2, 3]);
+///
+/// let mut drain_filtered = a.drain_filter(|v| v % 2 == 0);
+/// ```
+#[unstable(feature = "hash_drain_filter", issue = "59618")]
+pub struct DrainFilter<'a, K, F>
+where
+ F: FnMut(&K) -> bool,
+{
+ base: base::DrainFilter<'a, K, F>,
+}
+
+/// A lazy iterator producing elements in the intersection of `HashSet`s.
+///
+/// This `struct` is created by the [`intersection`] method on [`HashSet`].
+/// See its documentation for more.
+///
+/// [`intersection`]: HashSet::intersection
+///
+/// # Examples
+///
+/// ```
+/// use std::collections::HashSet;
+///
+/// let a = HashSet::from([1, 2, 3]);
+/// let b = HashSet::from([4, 2, 3, 4]);
+///
+/// let mut intersection = a.intersection(&b);
+/// ```
+#[must_use = "this returns the intersection as an iterator, \
+ without modifying either input set"]
+#[stable(feature = "rust1", since = "1.0.0")]
+pub struct Intersection<'a, T: 'a, S: 'a> {
+ // iterator of the first set
+ iter: Iter<'a, T>,
+ // the second set
+ other: &'a HashSet<T, S>,
+}
+
+/// A lazy iterator producing elements in the difference of `HashSet`s.
+///
+/// This `struct` is created by the [`difference`] method on [`HashSet`].
+/// See its documentation for more.
+///
+/// [`difference`]: HashSet::difference
+///
+/// # Examples
+///
+/// ```
+/// use std::collections::HashSet;
+///
+/// let a = HashSet::from([1, 2, 3]);
+/// let b = HashSet::from([4, 2, 3, 4]);
+///
+/// let mut difference = a.difference(&b);
+/// ```
+#[must_use = "this returns the difference as an iterator, \
+ without modifying either input set"]
+#[stable(feature = "rust1", since = "1.0.0")]
+pub struct Difference<'a, T: 'a, S: 'a> {
+ // iterator of the first set
+ iter: Iter<'a, T>,
+ // the second set
+ other: &'a HashSet<T, S>,
+}
+
+/// A lazy iterator producing elements in the symmetric difference of `HashSet`s.
+///
+/// This `struct` is created by the [`symmetric_difference`] method on
+/// [`HashSet`]. See its documentation for more.
+///
+/// [`symmetric_difference`]: HashSet::symmetric_difference
+///
+/// # Examples
+///
+/// ```
+/// use std::collections::HashSet;
+///
+/// let a = HashSet::from([1, 2, 3]);
+/// let b = HashSet::from([4, 2, 3, 4]);
+///
+/// let mut intersection = a.symmetric_difference(&b);
+/// ```
+#[must_use = "this returns the difference as an iterator, \
+ without modifying either input set"]
+#[stable(feature = "rust1", since = "1.0.0")]
+pub struct SymmetricDifference<'a, T: 'a, S: 'a> {
+ iter: Chain<Difference<'a, T, S>, Difference<'a, T, S>>,
+}
+
+/// A lazy iterator producing elements in the union of `HashSet`s.
+///
+/// This `struct` is created by the [`union`] method on [`HashSet`].
+/// See its documentation for more.
+///
+/// [`union`]: HashSet::union
+///
+/// # Examples
+///
+/// ```
+/// use std::collections::HashSet;
+///
+/// let a = HashSet::from([1, 2, 3]);
+/// let b = HashSet::from([4, 2, 3, 4]);
+///
+/// let mut union_iter = a.union(&b);
+/// ```
+#[must_use = "this returns the union as an iterator, \
+ without modifying either input set"]
+#[stable(feature = "rust1", since = "1.0.0")]
+pub struct Union<'a, T: 'a, S: 'a> {
+ iter: Chain<Iter<'a, T>, Difference<'a, T, S>>,
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<'a, T, S> IntoIterator for &'a HashSet<T, S> {
+ type Item = &'a T;
+ type IntoIter = Iter<'a, T>;
+
+ #[inline]
+ #[rustc_lint_query_instability]
+ fn into_iter(self) -> Iter<'a, T> {
+ self.iter()
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T, S> IntoIterator for HashSet<T, S> {
+ type Item = T;
+ type IntoIter = IntoIter<T>;
+
+ /// 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
+ /// this.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashSet;
+ /// let mut set = HashSet::new();
+ /// set.insert("a".to_string());
+ /// set.insert("b".to_string());
+ ///
+ /// // Not possible to collect to a Vec<String> with a regular `.iter()`.
+ /// let v: Vec<String> = set.into_iter().collect();
+ ///
+ /// // Will print in an arbitrary order.
+ /// for x in &v {
+ /// println!("{x}");
+ /// }
+ /// ```
+ #[inline]
+ #[rustc_lint_query_instability]
+ fn into_iter(self) -> IntoIter<T> {
+ IntoIter { base: self.base.into_iter() }
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<K> Clone for Iter<'_, K> {
+ #[inline]
+ fn clone(&self) -> Self {
+ Iter { base: self.base.clone() }
+ }
+}
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<'a, K> Iterator for Iter<'a, K> {
+ type Item = &'a K;
+
+ #[inline]
+ fn next(&mut self) -> Option<&'a K> {
+ self.base.next()
+ }
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ self.base.size_hint()
+ }
+}
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<K> ExactSizeIterator for Iter<'_, K> {
+ #[inline]
+ fn len(&self) -> usize {
+ self.base.len()
+ }
+}
+#[stable(feature = "fused", since = "1.26.0")]
+impl<K> FusedIterator for Iter<'_, K> {}
+
+#[stable(feature = "std_debug", since = "1.16.0")]
+impl<K: fmt::Debug> fmt::Debug for Iter<'_, K> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_list().entries(self.clone()).finish()
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<K> Iterator for IntoIter<K> {
+ type Item = K;
+
+ #[inline]
+ fn next(&mut self) -> Option<K> {
+ self.base.next()
+ }
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ self.base.size_hint()
+ }
+}
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<K> ExactSizeIterator for IntoIter<K> {
+ #[inline]
+ fn len(&self) -> usize {
+ self.base.len()
+ }
+}
+#[stable(feature = "fused", since = "1.26.0")]
+impl<K> FusedIterator for IntoIter<K> {}
+
+#[stable(feature = "std_debug", since = "1.16.0")]
+impl<K: fmt::Debug> fmt::Debug for IntoIter<K> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ fmt::Debug::fmt(&self.base, f)
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<'a, K> Iterator for Drain<'a, K> {
+ type Item = K;
+
+ #[inline]
+ fn next(&mut self) -> Option<K> {
+ self.base.next()
+ }
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ self.base.size_hint()
+ }
+}
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<K> ExactSizeIterator for Drain<'_, K> {
+ #[inline]
+ fn len(&self) -> usize {
+ self.base.len()
+ }
+}
+#[stable(feature = "fused", since = "1.26.0")]
+impl<K> FusedIterator for Drain<'_, K> {}
+
+#[stable(feature = "std_debug", since = "1.16.0")]
+impl<K: fmt::Debug> fmt::Debug for Drain<'_, K> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ fmt::Debug::fmt(&self.base, f)
+ }
+}
+
+#[unstable(feature = "hash_drain_filter", issue = "59618")]
+impl<K, F> Iterator for DrainFilter<'_, K, F>
+where
+ F: FnMut(&K) -> bool,
+{
+ type Item = K;
+
+ #[inline]
+ fn next(&mut self) -> Option<K> {
+ self.base.next()
+ }
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ self.base.size_hint()
+ }
+}
+
+#[unstable(feature = "hash_drain_filter", issue = "59618")]
+impl<K, F> FusedIterator for DrainFilter<'_, K, F> where F: FnMut(&K) -> bool {}
+
+#[unstable(feature = "hash_drain_filter", issue = "59618")]
+impl<'a, K, F> fmt::Debug for DrainFilter<'a, K, F>
+where
+ F: FnMut(&K) -> bool,
+{
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_struct("DrainFilter").finish_non_exhaustive()
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T, S> Clone for Intersection<'_, T, S> {
+ #[inline]
+ fn clone(&self) -> Self {
+ Intersection { iter: self.iter.clone(), ..*self }
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<'a, T, S> Iterator for Intersection<'a, T, S>
+where
+ T: Eq + Hash,
+ S: BuildHasher,
+{
+ type Item = &'a T;
+
+ #[inline]
+ fn next(&mut self) -> Option<&'a T> {
+ loop {
+ let elt = self.iter.next()?;
+ if self.other.contains(elt) {
+ return Some(elt);
+ }
+ }
+ }
+
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ let (_, upper) = self.iter.size_hint();
+ (0, upper)
+ }
+}
+
+#[stable(feature = "std_debug", since = "1.16.0")]
+impl<T, S> fmt::Debug for Intersection<'_, T, S>
+where
+ T: fmt::Debug + Eq + Hash,
+ S: BuildHasher,
+{
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_list().entries(self.clone()).finish()
+ }
+}
+
+#[stable(feature = "fused", since = "1.26.0")]
+impl<T, S> FusedIterator for Intersection<'_, T, S>
+where
+ T: Eq + Hash,
+ S: BuildHasher,
+{
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T, S> Clone for Difference<'_, T, S> {
+ #[inline]
+ fn clone(&self) -> Self {
+ Difference { iter: self.iter.clone(), ..*self }
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<'a, T, S> Iterator for Difference<'a, T, S>
+where
+ T: Eq + Hash,
+ S: BuildHasher,
+{
+ type Item = &'a T;
+
+ #[inline]
+ fn next(&mut self) -> Option<&'a T> {
+ loop {
+ let elt = self.iter.next()?;
+ if !self.other.contains(elt) {
+ return Some(elt);
+ }
+ }
+ }
+
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ let (_, upper) = self.iter.size_hint();
+ (0, upper)
+ }
+}
+
+#[stable(feature = "fused", since = "1.26.0")]
+impl<T, S> FusedIterator for Difference<'_, T, S>
+where
+ T: Eq + Hash,
+ S: BuildHasher,
+{
+}
+
+#[stable(feature = "std_debug", since = "1.16.0")]
+impl<T, S> fmt::Debug for Difference<'_, T, S>
+where
+ T: fmt::Debug + Eq + Hash,
+ S: BuildHasher,
+{
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_list().entries(self.clone()).finish()
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T, S> Clone for SymmetricDifference<'_, T, S> {
+ #[inline]
+ fn clone(&self) -> Self {
+ SymmetricDifference { iter: self.iter.clone() }
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<'a, T, S> Iterator for SymmetricDifference<'a, T, S>
+where
+ T: Eq + Hash,
+ S: BuildHasher,
+{
+ type Item = &'a T;
+
+ #[inline]
+ fn next(&mut self) -> Option<&'a T> {
+ self.iter.next()
+ }
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ self.iter.size_hint()
+ }
+}
+
+#[stable(feature = "fused", since = "1.26.0")]
+impl<T, S> FusedIterator for SymmetricDifference<'_, T, S>
+where
+ T: Eq + Hash,
+ S: BuildHasher,
+{
+}
+
+#[stable(feature = "std_debug", since = "1.16.0")]
+impl<T, S> fmt::Debug for SymmetricDifference<'_, T, S>
+where
+ T: fmt::Debug + Eq + Hash,
+ S: BuildHasher,
+{
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_list().entries(self.clone()).finish()
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T, S> Clone for Union<'_, T, S> {
+ #[inline]
+ fn clone(&self) -> Self {
+ Union { iter: self.iter.clone() }
+ }
+}
+
+#[stable(feature = "fused", since = "1.26.0")]
+impl<T, S> FusedIterator for Union<'_, T, S>
+where
+ T: Eq + Hash,
+ S: BuildHasher,
+{
+}
+
+#[stable(feature = "std_debug", since = "1.16.0")]
+impl<T, S> fmt::Debug for Union<'_, T, S>
+where
+ T: fmt::Debug + Eq + Hash,
+ S: BuildHasher,
+{
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_list().entries(self.clone()).finish()
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<'a, T, S> Iterator for Union<'a, T, S>
+where
+ T: Eq + Hash,
+ S: BuildHasher,
+{
+ type Item = &'a T;
+
+ #[inline]
+ fn next(&mut self) -> Option<&'a T> {
+ self.iter.next()
+ }
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ self.iter.size_hint()
+ }
+}
+
+#[allow(dead_code)]
+fn assert_covariance() {
+ fn set<'new>(v: HashSet<&'static str>) -> HashSet<&'new str> {
+ v
+ }
+ 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> {
+ v
+ }
+ fn difference<'a, 'new>(
+ v: Difference<'a, &'static str, RandomState>,
+ ) -> Difference<'a, &'new str, RandomState> {
+ v
+ }
+ fn symmetric_difference<'a, 'new>(
+ v: SymmetricDifference<'a, &'static str, RandomState>,
+ ) -> SymmetricDifference<'a, &'new str, RandomState> {
+ v
+ }
+ fn intersection<'a, 'new>(
+ v: Intersection<'a, &'static str, RandomState>,
+ ) -> Intersection<'a, &'new str, RandomState> {
+ v
+ }
+ fn union<'a, 'new>(
+ v: Union<'a, &'static str, RandomState>,
+ ) -> Union<'a, &'new str, RandomState> {
+ v
+ }
+ fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
+ d
+ }
+}
diff --git a/library/std/src/collections/hash/set/tests.rs b/library/std/src/collections/hash/set/tests.rs
new file mode 100644
index 000000000..233db276b
--- /dev/null
+++ b/library/std/src/collections/hash/set/tests.rs
@@ -0,0 +1,498 @@
+use super::super::map::RandomState;
+use super::HashSet;
+
+use crate::panic::{catch_unwind, AssertUnwindSafe};
+use crate::sync::atomic::{AtomicU32, Ordering};
+
+#[test]
+fn test_zero_capacities() {
+ type HS = HashSet<i32>;
+
+ let s = HS::new();
+ assert_eq!(s.capacity(), 0);
+
+ let s = HS::default();
+ assert_eq!(s.capacity(), 0);
+
+ let s = HS::with_hasher(RandomState::new());
+ assert_eq!(s.capacity(), 0);
+
+ let s = HS::with_capacity(0);
+ assert_eq!(s.capacity(), 0);
+
+ let s = HS::with_capacity_and_hasher(0, RandomState::new());
+ assert_eq!(s.capacity(), 0);
+
+ let mut s = HS::new();
+ s.insert(1);
+ s.insert(2);
+ s.remove(&1);
+ s.remove(&2);
+ s.shrink_to_fit();
+ assert_eq!(s.capacity(), 0);
+
+ let mut s = HS::new();
+ s.reserve(0);
+ assert_eq!(s.capacity(), 0);
+}
+
+#[test]
+fn test_disjoint() {
+ let mut xs = HashSet::new();
+ let mut ys = HashSet::new();
+ assert!(xs.is_disjoint(&ys));
+ assert!(ys.is_disjoint(&xs));
+ assert!(xs.insert(5));
+ assert!(ys.insert(11));
+ assert!(xs.is_disjoint(&ys));
+ assert!(ys.is_disjoint(&xs));
+ assert!(xs.insert(7));
+ assert!(xs.insert(19));
+ assert!(xs.insert(4));
+ assert!(ys.insert(2));
+ assert!(ys.insert(-11));
+ assert!(xs.is_disjoint(&ys));
+ assert!(ys.is_disjoint(&xs));
+ assert!(ys.insert(7));
+ assert!(!xs.is_disjoint(&ys));
+ assert!(!ys.is_disjoint(&xs));
+}
+
+#[test]
+fn test_subset_and_superset() {
+ let mut a = HashSet::new();
+ assert!(a.insert(0));
+ assert!(a.insert(5));
+ assert!(a.insert(11));
+ assert!(a.insert(7));
+
+ let mut b = HashSet::new();
+ assert!(b.insert(0));
+ assert!(b.insert(7));
+ assert!(b.insert(19));
+ assert!(b.insert(250));
+ assert!(b.insert(11));
+ assert!(b.insert(200));
+
+ assert!(!a.is_subset(&b));
+ assert!(!a.is_superset(&b));
+ assert!(!b.is_subset(&a));
+ assert!(!b.is_superset(&a));
+
+ assert!(b.insert(5));
+
+ assert!(a.is_subset(&b));
+ assert!(!a.is_superset(&b));
+ assert!(!b.is_subset(&a));
+ assert!(b.is_superset(&a));
+}
+
+#[test]
+fn test_iterate() {
+ let mut a = HashSet::new();
+ for i in 0..32 {
+ assert!(a.insert(i));
+ }
+ let mut observed: u32 = 0;
+ for k in &a {
+ observed |= 1 << *k;
+ }
+ assert_eq!(observed, 0xFFFF_FFFF);
+}
+
+#[test]
+fn test_intersection() {
+ let mut a = HashSet::new();
+ let mut b = HashSet::new();
+ assert!(a.intersection(&b).next().is_none());
+
+ assert!(a.insert(11));
+ assert!(a.insert(1));
+ assert!(a.insert(3));
+ assert!(a.insert(77));
+ assert!(a.insert(103));
+ assert!(a.insert(5));
+ assert!(a.insert(-5));
+
+ assert!(b.insert(2));
+ assert!(b.insert(11));
+ assert!(b.insert(77));
+ assert!(b.insert(-9));
+ assert!(b.insert(-42));
+ assert!(b.insert(5));
+ assert!(b.insert(3));
+
+ let mut i = 0;
+ let expected = [3, 5, 11, 77];
+ for x in a.intersection(&b) {
+ assert!(expected.contains(x));
+ i += 1
+ }
+ assert_eq!(i, expected.len());
+
+ assert!(a.insert(9)); // make a bigger than b
+
+ i = 0;
+ for x in a.intersection(&b) {
+ assert!(expected.contains(x));
+ i += 1
+ }
+ assert_eq!(i, expected.len());
+
+ i = 0;
+ for x in b.intersection(&a) {
+ assert!(expected.contains(x));
+ i += 1
+ }
+ assert_eq!(i, expected.len());
+}
+
+#[test]
+fn test_difference() {
+ let mut a = HashSet::new();
+ let mut b = HashSet::new();
+
+ assert!(a.insert(1));
+ assert!(a.insert(3));
+ assert!(a.insert(5));
+ assert!(a.insert(9));
+ assert!(a.insert(11));
+
+ assert!(b.insert(3));
+ assert!(b.insert(9));
+
+ let mut i = 0;
+ let expected = [1, 5, 11];
+ for x in a.difference(&b) {
+ assert!(expected.contains(x));
+ i += 1
+ }
+ assert_eq!(i, expected.len());
+}
+
+#[test]
+fn test_symmetric_difference() {
+ let mut a = HashSet::new();
+ let mut b = HashSet::new();
+
+ assert!(a.insert(1));
+ assert!(a.insert(3));
+ assert!(a.insert(5));
+ assert!(a.insert(9));
+ assert!(a.insert(11));
+
+ assert!(b.insert(-2));
+ assert!(b.insert(3));
+ assert!(b.insert(9));
+ assert!(b.insert(14));
+ assert!(b.insert(22));
+
+ let mut i = 0;
+ let expected = [-2, 1, 5, 11, 14, 22];
+ for x in a.symmetric_difference(&b) {
+ assert!(expected.contains(x));
+ i += 1
+ }
+ assert_eq!(i, expected.len());
+}
+
+#[test]
+fn test_union() {
+ let mut a = HashSet::new();
+ let mut b = HashSet::new();
+ assert!(a.union(&b).next().is_none());
+ assert!(b.union(&a).next().is_none());
+
+ assert!(a.insert(1));
+ assert!(a.insert(3));
+ assert!(a.insert(11));
+ assert!(a.insert(16));
+ assert!(a.insert(19));
+ assert!(a.insert(24));
+
+ assert!(b.insert(-2));
+ assert!(b.insert(1));
+ assert!(b.insert(5));
+ assert!(b.insert(9));
+ assert!(b.insert(13));
+ assert!(b.insert(19));
+
+ let mut i = 0;
+ let expected = [-2, 1, 3, 5, 9, 11, 13, 16, 19, 24];
+ for x in a.union(&b) {
+ assert!(expected.contains(x));
+ i += 1
+ }
+ assert_eq!(i, expected.len());
+
+ assert!(a.insert(9)); // make a bigger than b
+ assert!(a.insert(5));
+
+ i = 0;
+ for x in a.union(&b) {
+ assert!(expected.contains(x));
+ i += 1
+ }
+ assert_eq!(i, expected.len());
+
+ i = 0;
+ for x in b.union(&a) {
+ assert!(expected.contains(x));
+ i += 1
+ }
+ assert_eq!(i, expected.len());
+}
+
+#[test]
+fn test_from_iter() {
+ let xs = [1, 2, 2, 3, 4, 5, 6, 7, 8, 9];
+
+ let set: HashSet<_> = xs.iter().cloned().collect();
+
+ for x in &xs {
+ assert!(set.contains(x));
+ }
+
+ assert_eq!(set.iter().len(), xs.len() - 1);
+}
+
+#[test]
+fn test_move_iter() {
+ let hs = {
+ let mut hs = HashSet::new();
+
+ hs.insert('a');
+ hs.insert('b');
+
+ hs
+ };
+
+ let v = hs.into_iter().collect::<Vec<char>>();
+ assert!(v == ['a', 'b'] || v == ['b', 'a']);
+}
+
+#[test]
+fn test_eq() {
+ // These constants once happened to expose a bug in insert().
+ // I'm keeping them around to prevent a regression.
+ let mut s1 = HashSet::new();
+
+ s1.insert(1);
+ s1.insert(2);
+ s1.insert(3);
+
+ let mut s2 = HashSet::new();
+
+ s2.insert(1);
+ s2.insert(2);
+
+ assert!(s1 != s2);
+
+ s2.insert(3);
+
+ assert_eq!(s1, s2);
+}
+
+#[test]
+fn test_show() {
+ let mut set = HashSet::new();
+ let empty = HashSet::<i32>::new();
+
+ set.insert(1);
+ set.insert(2);
+
+ let set_str = format!("{set:?}");
+
+ assert!(set_str == "{1, 2}" || set_str == "{2, 1}");
+ assert_eq!(format!("{empty:?}"), "{}");
+}
+
+#[test]
+fn test_trivial_drain() {
+ let mut s = HashSet::<i32>::new();
+ for _ in s.drain() {}
+ assert!(s.is_empty());
+ drop(s);
+
+ let mut s = HashSet::<i32>::new();
+ drop(s.drain());
+ assert!(s.is_empty());
+}
+
+#[test]
+fn test_drain() {
+ let mut s: HashSet<_> = (1..100).collect();
+
+ // try this a bunch of times to make sure we don't screw up internal state.
+ for _ in 0..20 {
+ assert_eq!(s.len(), 99);
+
+ {
+ let mut last_i = 0;
+ let mut d = s.drain();
+ for (i, x) in d.by_ref().take(50).enumerate() {
+ last_i = i;
+ assert!(x != 0);
+ }
+ assert_eq!(last_i, 49);
+ }
+
+ for _ in &s {
+ panic!("s should be empty!");
+ }
+
+ // reset to try again.
+ s.extend(1..100);
+ }
+}
+
+#[test]
+fn test_replace() {
+ use crate::hash;
+
+ #[derive(Debug)]
+ struct Foo(&'static str, i32);
+
+ impl PartialEq for Foo {
+ fn eq(&self, other: &Self) -> bool {
+ self.0 == other.0
+ }
+ }
+
+ impl Eq for Foo {}
+
+ impl hash::Hash for Foo {
+ fn hash<H: hash::Hasher>(&self, h: &mut H) {
+ self.0.hash(h);
+ }
+ }
+
+ let mut s = HashSet::new();
+ assert_eq!(s.replace(Foo("a", 1)), None);
+ assert_eq!(s.len(), 1);
+ assert_eq!(s.replace(Foo("a", 2)), Some(Foo("a", 1)));
+ assert_eq!(s.len(), 1);
+
+ let mut it = s.iter();
+ assert_eq!(it.next(), Some(&Foo("a", 2)));
+ assert_eq!(it.next(), None);
+}
+
+#[test]
+fn test_extend_ref() {
+ let mut a = HashSet::new();
+ a.insert(1);
+
+ a.extend(&[2, 3, 4]);
+
+ assert_eq!(a.len(), 4);
+ assert!(a.contains(&1));
+ assert!(a.contains(&2));
+ assert!(a.contains(&3));
+ assert!(a.contains(&4));
+
+ let mut b = HashSet::new();
+ b.insert(5);
+ b.insert(6);
+
+ a.extend(&b);
+
+ assert_eq!(a.len(), 6);
+ assert!(a.contains(&1));
+ assert!(a.contains(&2));
+ assert!(a.contains(&3));
+ assert!(a.contains(&4));
+ assert!(a.contains(&5));
+ assert!(a.contains(&6));
+}
+
+#[test]
+fn test_retain() {
+ let xs = [1, 2, 3, 4, 5, 6];
+ let mut set: HashSet<i32> = xs.iter().cloned().collect();
+ set.retain(|&k| k % 2 == 0);
+ assert_eq!(set.len(), 3);
+ assert!(set.contains(&2));
+ assert!(set.contains(&4));
+ assert!(set.contains(&6));
+}
+
+#[test]
+fn test_drain_filter() {
+ let mut x: HashSet<_> = [1].iter().copied().collect();
+ let mut y: HashSet<_> = [1].iter().copied().collect();
+
+ x.drain_filter(|_| true);
+ y.drain_filter(|_| false);
+ assert_eq!(x.len(), 0);
+ assert_eq!(y.len(), 1);
+}
+
+#[test]
+fn test_drain_filter_drop_panic_leak() {
+ static PREDS: AtomicU32 = AtomicU32::new(0);
+ static DROPS: AtomicU32 = AtomicU32::new(0);
+
+ #[derive(PartialEq, Eq, PartialOrd, Hash)]
+ struct D(i32);
+ impl Drop for D {
+ fn drop(&mut self) {
+ if DROPS.fetch_add(1, Ordering::SeqCst) == 1 {
+ panic!("panic in `drop`");
+ }
+ }
+ }
+
+ let mut set = (0..3).map(|i| D(i)).collect::<HashSet<_>>();
+
+ catch_unwind(move || {
+ drop(set.drain_filter(|_| {
+ PREDS.fetch_add(1, Ordering::SeqCst);
+ true
+ }))
+ })
+ .ok();
+
+ assert_eq!(PREDS.load(Ordering::SeqCst), 3);
+ assert_eq!(DROPS.load(Ordering::SeqCst), 3);
+}
+
+#[test]
+fn test_drain_filter_pred_panic_leak() {
+ static PREDS: AtomicU32 = AtomicU32::new(0);
+ static DROPS: AtomicU32 = AtomicU32::new(0);
+
+ #[derive(PartialEq, Eq, PartialOrd, Hash)]
+ struct D;
+ impl Drop for D {
+ fn drop(&mut self) {
+ DROPS.fetch_add(1, Ordering::SeqCst);
+ }
+ }
+
+ let mut set: HashSet<_> = (0..3).map(|_| D).collect();
+
+ catch_unwind(AssertUnwindSafe(|| {
+ drop(set.drain_filter(|_| match PREDS.fetch_add(1, Ordering::SeqCst) {
+ 0 => true,
+ _ => panic!(),
+ }))
+ }))
+ .ok();
+
+ assert_eq!(PREDS.load(Ordering::SeqCst), 1);
+ assert_eq!(DROPS.load(Ordering::SeqCst), 3);
+ assert_eq!(set.len(), 0);
+}
+
+#[test]
+fn from_array() {
+ let set = HashSet::from([1, 2, 3, 4]);
+ let unordered_duplicates = HashSet::from([4, 1, 4, 3, 2]);
+ assert_eq!(set, unordered_duplicates);
+
+ // This next line must infer the hasher type parameter.
+ // If you make a change that causes this line to no longer infer,
+ // that's a problem!
+ let _must_not_require_type_annotation = HashSet::from([1, 2]);
+}
diff --git a/library/std/src/collections/mod.rs b/library/std/src/collections/mod.rs
new file mode 100644
index 000000000..ae2baba09
--- /dev/null
+++ b/library/std/src/collections/mod.rs
@@ -0,0 +1,446 @@
+//! Collection types.
+//!
+//! Rust's standard collection library provides efficient implementations of the
+//! most common general purpose programming data structures. By using the
+//! standard implementations, it should be possible for two libraries to
+//! communicate without significant data conversion.
+//!
+//! To get this out of the way: you should probably just use [`Vec`] or [`HashMap`].
+//! These two collections cover most use cases for generic data storage and
+//! processing. They are exceptionally good at doing what they do. All the other
+//! collections in the standard library have specific use cases where they are
+//! the optimal choice, but these cases are borderline *niche* in comparison.
+//! Even when `Vec` and `HashMap` are technically suboptimal, they're probably a
+//! good enough choice to get started.
+//!
+//! Rust's collections can be grouped into four major categories:
+//!
+//! * Sequences: [`Vec`], [`VecDeque`], [`LinkedList`]
+//! * Maps: [`HashMap`], [`BTreeMap`]
+//! * Sets: [`HashSet`], [`BTreeSet`]
+//! * Misc: [`BinaryHeap`]
+//!
+//! # When Should You Use Which Collection?
+//!
+//! These are fairly high-level and quick break-downs of when each collection
+//! should be considered. Detailed discussions of strengths and weaknesses of
+//! individual collections can be found on their own documentation pages.
+//!
+//! ### Use a `Vec` when:
+//! * You want to collect items up to be processed or sent elsewhere later, and
+//! don't care about any properties of the actual values being stored.
+//! * You want a sequence of elements in a particular order, and will only be
+//! appending to (or near) the end.
+//! * You want a stack.
+//! * You want a resizable array.
+//! * You want a heap-allocated array.
+//!
+//! ### Use a `VecDeque` when:
+//! * You want a [`Vec`] that supports efficient insertion at both ends of the
+//! sequence.
+//! * You want a queue.
+//! * You want a double-ended queue (deque).
+//!
+//! ### Use a `LinkedList` when:
+//! * You want a [`Vec`] or [`VecDeque`] of unknown size, and can't tolerate
+//! amortization.
+//! * You want to efficiently split and append lists.
+//! * You are *absolutely* certain you *really*, *truly*, want a doubly linked
+//! list.
+//!
+//! ### Use a `HashMap` when:
+//! * You want to associate arbitrary keys with an arbitrary value.
+//! * You want a cache.
+//! * You want a map, with no extra functionality.
+//!
+//! ### Use a `BTreeMap` when:
+//! * You want a map sorted by its keys.
+//! * You want to be able to get a range of entries on-demand.
+//! * You're interested in what the smallest or largest key-value pair is.
+//! * You want to find the largest or smallest key that is smaller or larger
+//! than something.
+//!
+//! ### Use the `Set` variant of any of these `Map`s when:
+//! * You just want to remember which keys you've seen.
+//! * There is no meaningful value to associate with your keys.
+//! * You just want a set.
+//!
+//! ### Use a `BinaryHeap` when:
+//!
+//! * You want to store a bunch of elements, but only ever want to process the
+//! "biggest" or "most important" one at any given time.
+//! * You want a priority queue.
+//!
+//! # Performance
+//!
+//! Choosing the right collection for the job requires an understanding of what
+//! each collection is good at. Here we briefly summarize the performance of
+//! different collections for certain important operations. For further details,
+//! see each type's documentation, and note that the names of actual methods may
+//! differ from the tables below on certain collections.
+//!
+//! Throughout the documentation, we will follow a few conventions. For all
+//! operations, the collection's size is denoted by n. If another collection is
+//! involved in the operation, it contains m elements. Operations which have an
+//! *amortized* cost are suffixed with a `*`. Operations with an *expected*
+//! cost are suffixed with a `~`.
+//!
+//! All amortized costs are for the potential need to resize when capacity is
+//! exhausted. If a resize occurs it will take *O*(*n*) time. Our collections never
+//! automatically shrink, so removal operations aren't amortized. Over a
+//! sufficiently large series of operations, the average cost per operation will
+//! deterministically equal the given cost.
+//!
+//! Only [`HashMap`] has expected costs, due to the probabilistic nature of hashing.
+//! It is theoretically possible, though very unlikely, for [`HashMap`] to
+//! experience worse performance.
+//!
+//! ## Sequences
+//!
+//! | | get(i) | insert(i) | remove(i) | append | split_off(i) |
+//! |----------------|------------------------|-------------------------|------------------------|-----------|------------------------|
+//! | [`Vec`] | *O*(1) | *O*(*n*-*i*)* | *O*(*n*-*i*) | *O*(*m*)* | *O*(*n*-*i*) |
+//! | [`VecDeque`] | *O*(1) | *O*(min(*i*, *n*-*i*))* | *O*(min(*i*, *n*-*i*)) | *O*(*m*)* | *O*(min(*i*, *n*-*i*)) |
+//! | [`LinkedList`] | *O*(min(*i*, *n*-*i*)) | *O*(min(*i*, *n*-*i*)) | *O*(min(*i*, *n*-*i*)) | *O*(1) | *O*(min(*i*, *n*-*i*)) |
+//!
+//! Note that where ties occur, [`Vec`] is generally going to be faster than [`VecDeque`], and
+//! [`VecDeque`] is generally going to be faster than [`LinkedList`].
+//!
+//! ## Maps
+//!
+//! For Sets, all operations have the cost of the equivalent Map operation.
+//!
+//! | | get | insert | remove | range | append |
+//! |--------------|---------------|---------------|---------------|---------------|--------------|
+//! | [`HashMap`] | *O*(1)~ | *O*(1)~* | *O*(1)~ | N/A | N/A |
+//! | [`BTreeMap`] | *O*(log(*n*)) | *O*(log(*n*)) | *O*(log(*n*)) | *O*(log(*n*)) | *O*(*n*+*m*) |
+//!
+//! # Correct and Efficient Usage of Collections
+//!
+//! Of course, knowing which collection is the right one for the job doesn't
+//! instantly permit you to use it correctly. Here are some quick tips for
+//! efficient and correct usage of the standard collections in general. If
+//! you're interested in how to use a specific collection in particular, consult
+//! its documentation for detailed discussion and code examples.
+//!
+//! ## Capacity Management
+//!
+//! Many collections provide several constructors and methods that refer to
+//! "capacity". These collections are generally built on top of an array.
+//! Optimally, this array would be exactly the right size to fit only the
+//! elements stored in the collection, but for the collection to do this would
+//! be very inefficient. If the backing array was exactly the right size at all
+//! times, then every time an element is inserted, the collection would have to
+//! grow the array to fit it. Due to the way memory is allocated and managed on
+//! most computers, this would almost surely require allocating an entirely new
+//! array and copying every single element from the old one into the new one.
+//! Hopefully you can see that this wouldn't be very efficient to do on every
+//! operation.
+//!
+//! Most collections therefore use an *amortized* allocation strategy. They
+//! generally let themselves have a fair amount of unoccupied space so that they
+//! only have to grow on occasion. When they do grow, they allocate a
+//! substantially larger array to move the elements into so that it will take a
+//! while for another grow to be required. While this strategy is great in
+//! general, it would be even better if the collection *never* had to resize its
+//! backing array. Unfortunately, the collection itself doesn't have enough
+//! information to do this itself. Therefore, it is up to us programmers to give
+//! it hints.
+//!
+//! Any `with_capacity` constructor will instruct the collection to allocate
+//! enough space for the specified number of elements. Ideally this will be for
+//! exactly that many elements, but some implementation details may prevent
+//! this. See collection-specific documentation for details. In general, use
+//! `with_capacity` when you know exactly how many elements will be inserted, or
+//! at least have a reasonable upper-bound on that number.
+//!
+//! When anticipating a large influx of elements, the `reserve` family of
+//! methods can be used to hint to the collection how much room it should make
+//! for the coming items. As with `with_capacity`, the precise behavior of
+//! these methods will be specific to the collection of interest.
+//!
+//! For optimal performance, collections will generally avoid shrinking
+//! themselves. If you believe that a collection will not soon contain any more
+//! elements, or just really need the memory, the `shrink_to_fit` method prompts
+//! the collection to shrink the backing array to the minimum size capable of
+//! holding its elements.
+//!
+//! Finally, if ever you're interested in what the actual capacity of the
+//! collection is, most collections provide a `capacity` method to query this
+//! information on demand. This can be useful for debugging purposes, or for
+//! use with the `reserve` methods.
+//!
+//! ## Iterators
+//!
+//! Iterators are a powerful and robust mechanism used throughout Rust's
+//! standard libraries. Iterators provide a sequence of values in a generic,
+//! safe, efficient and convenient way. The contents of an iterator are usually
+//! *lazily* evaluated, so that only the values that are actually needed are
+//! ever actually produced, and no allocation need be done to temporarily store
+//! them. Iterators are primarily consumed using a `for` loop, although many
+//! functions also take iterators where a collection or sequence of values is
+//! desired.
+//!
+//! All of the standard collections provide several iterators for performing
+//! bulk manipulation of their contents. The three primary iterators almost
+//! every collection should provide are `iter`, `iter_mut`, and `into_iter`.
+//! Some of these are not provided on collections where it would be unsound or
+//! unreasonable to provide them.
+//!
+//! `iter` provides an iterator of immutable references to all the contents of a
+//! collection in the most "natural" order. For sequence collections like [`Vec`],
+//! this means the items will be yielded in increasing order of index starting
+//! at 0. For ordered collections like [`BTreeMap`], this means that the items
+//! will be yielded in sorted order. For unordered collections like [`HashMap`],
+//! the items will be yielded in whatever order the internal representation made
+//! most convenient. This is great for reading through all the contents of the
+//! collection.
+//!
+//! ```
+//! let vec = vec![1, 2, 3, 4];
+//! for x in vec.iter() {
+//! println!("vec contained {x:?}");
+//! }
+//! ```
+//!
+//! `iter_mut` provides an iterator of *mutable* references in the same order as
+//! `iter`. This is great for mutating all the contents of the collection.
+//!
+//! ```
+//! let mut vec = vec![1, 2, 3, 4];
+//! for x in vec.iter_mut() {
+//! *x += 1;
+//! }
+//! ```
+//!
+//! `into_iter` transforms the actual collection into an iterator over its
+//! contents by-value. This is great when the collection itself is no longer
+//! needed, and the values are needed elsewhere. Using `extend` with `into_iter`
+//! is the main way that contents of one collection are moved into another.
+//! `extend` automatically calls `into_iter`, and takes any <code>T: [IntoIterator]</code>.
+//! Calling `collect` on an iterator itself is also a great way to convert one
+//! collection into another. Both of these methods should internally use the
+//! capacity management tools discussed in the previous section to do this as
+//! efficiently as possible.
+//!
+//! ```
+//! let mut vec1 = vec![1, 2, 3, 4];
+//! let vec2 = vec![10, 20, 30, 40];
+//! vec1.extend(vec2);
+//! ```
+//!
+//! ```
+//! use std::collections::VecDeque;
+//!
+//! let vec = [1, 2, 3, 4];
+//! let buf: VecDeque<_> = vec.into_iter().collect();
+//! ```
+//!
+//! Iterators also provide a series of *adapter* methods for performing common
+//! threads to sequences. Among the adapters are functional favorites like `map`,
+//! `fold`, `skip` and `take`. Of particular interest to collections is the
+//! `rev` adapter, which reverses any iterator that supports this operation. Most
+//! collections provide reversible iterators as the way to iterate over them in
+//! reverse order.
+//!
+//! ```
+//! let vec = vec![1, 2, 3, 4];
+//! for x in vec.iter().rev() {
+//! println!("vec contained {x:?}");
+//! }
+//! ```
+//!
+//! Several other collection methods also return iterators to yield a sequence
+//! of results but avoid allocating an entire collection to store the result in.
+//! This provides maximum flexibility as `collect` or `extend` can be called to
+//! "pipe" the sequence into any collection if desired. Otherwise, the sequence
+//! can be looped over with a `for` loop. The iterator can also be discarded
+//! after partial use, preventing the computation of the unused items.
+//!
+//! ## Entries
+//!
+//! The `entry` API is intended to provide an efficient mechanism for
+//! manipulating the contents of a map conditionally on the presence of a key or
+//! not. The primary motivating use case for this is to provide efficient
+//! accumulator maps. For instance, if one wishes to maintain a count of the
+//! number of times each key has been seen, they will have to perform some
+//! conditional logic on whether this is the first time the key has been seen or
+//! not. Normally, this would require a `find` followed by an `insert`,
+//! effectively duplicating the search effort on each insertion.
+//!
+//! When a user calls `map.entry(key)`, the map will search for the key and
+//! then yield a variant of the `Entry` enum.
+//!
+//! If a `Vacant(entry)` is yielded, then the key *was not* found. In this case
+//! the only valid operation is to `insert` a value into the entry. When this is
+//! done, the vacant entry is consumed and converted into a mutable reference to
+//! the value that was inserted. This allows for further manipulation of the
+//! value beyond the lifetime of the search itself. This is useful if complex
+//! logic needs to be performed on the value regardless of whether the value was
+//! just inserted.
+//!
+//! If an `Occupied(entry)` is yielded, then the key *was* found. In this case,
+//! the user has several options: they can `get`, `insert` or `remove` the
+//! value of the occupied entry. Additionally, they can convert the occupied
+//! entry into a mutable reference to its value, providing symmetry to the
+//! vacant `insert` case.
+//!
+//! ### Examples
+//!
+//! Here are the two primary ways in which `entry` is used. First, a simple
+//! example where the logic performed on the values is trivial.
+//!
+//! #### Counting the number of times each character in a string occurs
+//!
+//! ```
+//! use std::collections::btree_map::BTreeMap;
+//!
+//! let mut count = BTreeMap::new();
+//! let message = "she sells sea shells by the sea shore";
+//!
+//! for c in message.chars() {
+//! *count.entry(c).or_insert(0) += 1;
+//! }
+//!
+//! assert_eq!(count.get(&'s'), Some(&8));
+//!
+//! println!("Number of occurrences of each character");
+//! for (char, count) in &count {
+//! println!("{char}: {count}");
+//! }
+//! ```
+//!
+//! When the logic to be performed on the value is more complex, we may simply
+//! use the `entry` API to ensure that the value is initialized and perform the
+//! logic afterwards.
+//!
+//! #### Tracking the inebriation of customers at a bar
+//!
+//! ```
+//! use std::collections::btree_map::BTreeMap;
+//!
+//! // A client of the bar. They have a blood alcohol level.
+//! struct Person { blood_alcohol: f32 }
+//!
+//! // All the orders made to the bar, by client ID.
+//! let orders = vec![1, 2, 1, 2, 3, 4, 1, 2, 2, 3, 4, 1, 1, 1];
+//!
+//! // Our clients.
+//! let mut blood_alcohol = BTreeMap::new();
+//!
+//! for id in orders {
+//! // If this is the first time we've seen this customer, initialize them
+//! // with no blood alcohol. Otherwise, just retrieve them.
+//! let person = blood_alcohol.entry(id).or_insert(Person { blood_alcohol: 0.0 });
+//!
+//! // Reduce their blood alcohol level. It takes time to order and drink a beer!
+//! person.blood_alcohol *= 0.9;
+//!
+//! // Check if they're sober enough to have another beer.
+//! if person.blood_alcohol > 0.3 {
+//! // Too drunk... for now.
+//! println!("Sorry {id}, I have to cut you off");
+//! } else {
+//! // Have another!
+//! person.blood_alcohol += 0.1;
+//! }
+//! }
+//! ```
+//!
+//! # Insert and complex keys
+//!
+//! If we have a more complex key, calls to `insert` will
+//! not update the value of the key. For example:
+//!
+//! ```
+//! use std::cmp::Ordering;
+//! use std::collections::BTreeMap;
+//! use std::hash::{Hash, Hasher};
+//!
+//! #[derive(Debug)]
+//! struct Foo {
+//! a: u32,
+//! b: &'static str,
+//! }
+//!
+//! // we will compare `Foo`s by their `a` value only.
+//! impl PartialEq for Foo {
+//! fn eq(&self, other: &Self) -> bool { self.a == other.a }
+//! }
+//!
+//! impl Eq for Foo {}
+//!
+//! // we will hash `Foo`s by their `a` value only.
+//! impl Hash for Foo {
+//! fn hash<H: Hasher>(&self, h: &mut H) { self.a.hash(h); }
+//! }
+//!
+//! impl PartialOrd for Foo {
+//! fn partial_cmp(&self, other: &Self) -> Option<Ordering> { self.a.partial_cmp(&other.a) }
+//! }
+//!
+//! impl Ord for Foo {
+//! fn cmp(&self, other: &Self) -> Ordering { self.a.cmp(&other.a) }
+//! }
+//!
+//! let mut map = BTreeMap::new();
+//! map.insert(Foo { a: 1, b: "baz" }, 99);
+//!
+//! // We already have a Foo with an a of 1, so this will be updating the value.
+//! map.insert(Foo { a: 1, b: "xyz" }, 100);
+//!
+//! // The value has been updated...
+//! assert_eq!(map.values().next().unwrap(), &100);
+//!
+//! // ...but the key hasn't changed. b is still "baz", not "xyz".
+//! assert_eq!(map.keys().next().unwrap().b, "baz");
+//! ```
+//!
+//! [IntoIterator]: crate::iter::IntoIterator "iter::IntoIterator"
+
+#![stable(feature = "rust1", since = "1.0.0")]
+
+#[stable(feature = "rust1", since = "1.0.0")]
+// FIXME(#82080) The deprecation here is only theoretical, and does not actually produce a warning.
+#[deprecated(note = "moved to `std::ops::Bound`", since = "1.26.0")]
+#[doc(hidden)]
+pub use crate::ops::Bound;
+
+#[stable(feature = "rust1", since = "1.0.0")]
+pub use alloc_crate::collections::{binary_heap, btree_map, btree_set};
+#[stable(feature = "rust1", since = "1.0.0")]
+pub use alloc_crate::collections::{linked_list, vec_deque};
+#[stable(feature = "rust1", since = "1.0.0")]
+pub use alloc_crate::collections::{BTreeMap, BTreeSet, BinaryHeap};
+#[stable(feature = "rust1", since = "1.0.0")]
+pub use alloc_crate::collections::{LinkedList, VecDeque};
+
+#[stable(feature = "rust1", since = "1.0.0")]
+pub use self::hash_map::HashMap;
+#[stable(feature = "rust1", since = "1.0.0")]
+pub use self::hash_set::HashSet;
+
+#[stable(feature = "try_reserve", since = "1.57.0")]
+pub use alloc_crate::collections::TryReserveError;
+#[unstable(
+ feature = "try_reserve_kind",
+ reason = "Uncertain how much info should be exposed",
+ issue = "48043"
+)]
+pub use alloc_crate::collections::TryReserveErrorKind;
+
+mod hash;
+
+#[stable(feature = "rust1", since = "1.0.0")]
+pub mod hash_map {
+ //! A hash map implemented with quadratic probing and SIMD lookup.
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub use super::hash::map::*;
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+pub mod hash_set {
+ //! A hash set implemented as a `HashMap` where the value is `()`.
+ #[stable(feature = "rust1", since = "1.0.0")]
+ pub use super::hash::set::*;
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-08 00:45:58 +0000