std/collections/hash/
map.rs

1#[cfg(test)]
2mod tests;
3
4use hashbrown::hash_map as base;
5
6use self::Entry::*;
7use crate::borrow::Borrow;
8use crate::collections::{TryReserveError, TryReserveErrorKind};
9use crate::error::Error;
10use crate::fmt::{self, Debug};
11use crate::hash::{BuildHasher, Hash, RandomState};
12use crate::iter::FusedIterator;
13use crate::ops::Index;
14
15/// A [hash map] implemented with quadratic probing and SIMD lookup.
16///
17/// By default, `HashMap` uses a hashing algorithm selected to provide
18/// resistance against HashDoS attacks. The algorithm is randomly seeded, and a
19/// reasonable best-effort is made to generate this seed from a high quality,
20/// secure source of randomness provided by the host without blocking the
21/// program. Because of this, the randomness of the seed depends on the output
22/// quality of the system's random number coroutine when the seed is created.
23/// In particular, seeds generated when the system's entropy pool is abnormally
24/// low such as during system boot may be of a lower quality.
25///
26/// The default hashing algorithm is currently SipHash 1-3, though this is
27/// subject to change at any point in the future. While its performance is very
28/// competitive for medium sized keys, other hashing algorithms will outperform
29/// it for small keys such as integers as well as large keys such as long
30/// strings, though those algorithms will typically *not* protect against
31/// attacks such as HashDoS.
32///
33/// The hashing algorithm can be replaced on a per-`HashMap` basis using the
34/// [`default`], [`with_hasher`], and [`with_capacity_and_hasher`] methods.
35/// There are many alternative [hashing algorithms available on crates.io].
36///
37/// It is required that the keys implement the [`Eq`] and [`Hash`] traits, although
38/// this can frequently be achieved by using `#[derive(PartialEq, Eq, Hash)]`.
39/// If you implement these yourself, it is important that the following
40/// property holds:
41///
42/// ```text
43/// k1 == k2 -> hash(k1) == hash(k2)
44/// ```
45///
46/// In other words, if two keys are equal, their hashes must be equal.
47/// Violating this property is a logic error.
48///
49/// It is also a logic error for a key to be modified in such a way that the key's
50/// hash, as determined by the [`Hash`] trait, or its equality, as determined by
51/// the [`Eq`] trait, changes while it is in the map. This is normally only
52/// possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code.
53///
54/// The behavior resulting from either logic error is not specified, but will
55/// be encapsulated to the `HashMap` that observed the logic error and not
56/// result in undefined behavior. This could include panics, incorrect results,
57/// aborts, memory leaks, and non-termination.
58///
59/// The hash table implementation is a Rust port of Google's [SwissTable].
60/// The original C++ version of SwissTable can be found [here], and this
61/// [CppCon talk] gives an overview of how the algorithm works.
62///
63/// [hash map]: crate::collections#use-a-hashmap-when
64/// [hashing algorithms available on crates.io]: https://crates.io/keywords/hasher
65/// [SwissTable]: https://abseil.io/blog/20180927-swisstables
66/// [here]: https://github.com/abseil/abseil-cpp/blob/master/absl/container/internal/raw_hash_set.h
67/// [CppCon talk]: https://www.youtube.com/watch?v=ncHmEUmJZf4
68///
69/// # Examples
70///
71/// ```
72/// use std::collections::HashMap;
73///
74/// // Type inference lets us omit an explicit type signature (which
75/// // would be `HashMap<String, String>` in this example).
76/// let mut book_reviews = HashMap::new();
77///
78/// // Review some books.
79/// book_reviews.insert(
80///     "Adventures of Huckleberry Finn".to_string(),
81///     "My favorite book.".to_string(),
82/// );
83/// book_reviews.insert(
84///     "Grimms' Fairy Tales".to_string(),
85///     "Masterpiece.".to_string(),
86/// );
87/// book_reviews.insert(
88///     "Pride and Prejudice".to_string(),
89///     "Very enjoyable.".to_string(),
90/// );
91/// book_reviews.insert(
92///     "The Adventures of Sherlock Holmes".to_string(),
93///     "Eye lyked it alot.".to_string(),
94/// );
95///
96/// // Check for a specific one.
97/// // When collections store owned values (String), they can still be
98/// // queried using references (&str).
99/// if !book_reviews.contains_key("Les Misérables") {
100///     println!("We've got {} reviews, but Les Misérables ain't one.",
101///              book_reviews.len());
102/// }
103///
104/// // oops, this review has a lot of spelling mistakes, let's delete it.
105/// book_reviews.remove("The Adventures of Sherlock Holmes");
106///
107/// // Look up the values associated with some keys.
108/// let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"];
109/// for &book in &to_find {
110///     match book_reviews.get(book) {
111///         Some(review) => println!("{book}: {review}"),
112///         None => println!("{book} is unreviewed.")
113///     }
114/// }
115///
116/// // Look up the value for a key (will panic if the key is not found).
117/// println!("Review for Jane: {}", book_reviews["Pride and Prejudice"]);
118///
119/// // Iterate over everything.
120/// for (book, review) in &book_reviews {
121///     println!("{book}: \"{review}\"");
122/// }
123/// ```
124///
125/// A `HashMap` with a known list of items can be initialized from an array:
126///
127/// ```
128/// use std::collections::HashMap;
129///
130/// let solar_distance = HashMap::from([
131///     ("Mercury", 0.4),
132///     ("Venus", 0.7),
133///     ("Earth", 1.0),
134///     ("Mars", 1.5),
135/// ]);
136/// ```
137///
138/// `HashMap` implements an [`Entry` API](#method.entry), which allows
139/// for complex methods of getting, setting, updating and removing keys and
140/// their values:
141///
142/// ```
143/// use std::collections::HashMap;
144///
145/// // type inference lets us omit an explicit type signature (which
146/// // would be `HashMap<&str, u8>` in this example).
147/// let mut player_stats = HashMap::new();
148///
149/// fn random_stat_buff() -> u8 {
150///     // could actually return some random value here - let's just return
151///     // some fixed value for now
152///     42
153/// }
154///
155/// // insert a key only if it doesn't already exist
156/// player_stats.entry("health").or_insert(100);
157///
158/// // insert a key using a function that provides a new value only if it
159/// // doesn't already exist
160/// player_stats.entry("defence").or_insert_with(random_stat_buff);
161///
162/// // update a key, guarding against the key possibly not being set
163/// let stat = player_stats.entry("attack").or_insert(100);
164/// *stat += random_stat_buff();
165///
166/// // modify an entry before an insert with in-place mutation
167/// player_stats.entry("mana").and_modify(|mana| *mana += 200).or_insert(100);
168/// ```
169///
170/// The easiest way to use `HashMap` with a custom key type is to derive [`Eq`] and [`Hash`].
171/// We must also derive [`PartialEq`].
172///
173/// [`RefCell`]: crate::cell::RefCell
174/// [`Cell`]: crate::cell::Cell
175/// [`default`]: Default::default
176/// [`with_hasher`]: Self::with_hasher
177/// [`with_capacity_and_hasher`]: Self::with_capacity_and_hasher
178///
179/// ```
180/// use std::collections::HashMap;
181///
182/// #[derive(Hash, Eq, PartialEq, Debug)]
183/// struct Viking {
184///     name: String,
185///     country: String,
186/// }
187///
188/// impl Viking {
189///     /// Creates a new Viking.
190///     fn new(name: &str, country: &str) -> Viking {
191///         Viking { name: name.to_string(), country: country.to_string() }
192///     }
193/// }
194///
195/// // Use a HashMap to store the vikings' health points.
196/// let vikings = HashMap::from([
197///     (Viking::new("Einar", "Norway"), 25),
198///     (Viking::new("Olaf", "Denmark"), 24),
199///     (Viking::new("Harald", "Iceland"), 12),
200/// ]);
201///
202/// // Use derived implementation to print the status of the vikings.
203/// for (viking, health) in &vikings {
204///     println!("{viking:?} has {health} hp");
205/// }
206/// ```
207///
208/// # Usage in `const` and `static`
209///
210/// As explained above, `HashMap` is randomly seeded: each `HashMap` instance uses a different seed,
211/// which means that `HashMap::new` cannot be used in const context. To construct a `HashMap` in the
212/// initializer of a `const` or `static` item, you will have to use a different hasher that does not
213/// involve a random seed, as demonstrated in the following example. **A `HashMap` constructed this
214/// way is not resistant against HashDoS!**
215///
216/// ```rust
217/// use std::collections::HashMap;
218/// use std::hash::{BuildHasherDefault, DefaultHasher};
219/// use std::sync::Mutex;
220///
221/// const EMPTY_MAP: HashMap<String, Vec<i32>, BuildHasherDefault<DefaultHasher>> =
222///     HashMap::with_hasher(BuildHasherDefault::new());
223/// static MAP: Mutex<HashMap<String, Vec<i32>, BuildHasherDefault<DefaultHasher>>> =
224///     Mutex::new(HashMap::with_hasher(BuildHasherDefault::new()));
225/// ```
226
227#[cfg_attr(not(test), rustc_diagnostic_item = "HashMap")]
228#[stable(feature = "rust1", since = "1.0.0")]
229#[rustc_insignificant_dtor]
230pub struct HashMap<K, V, S = RandomState> {
231    base: base::HashMap<K, V, S>,
232}
233
234impl<K, V> HashMap<K, V, RandomState> {
235    /// Creates an empty `HashMap`.
236    ///
237    /// The hash map is initially created with a capacity of 0, so it will not allocate until it
238    /// is first inserted into.
239    ///
240    /// # Examples
241    ///
242    /// ```
243    /// use std::collections::HashMap;
244    /// let mut map: HashMap<&str, i32> = HashMap::new();
245    /// ```
246    #[inline]
247    #[must_use]
248    #[stable(feature = "rust1", since = "1.0.0")]
249    pub fn new() -> HashMap<K, V, RandomState> {
250        Default::default()
251    }
252
253    /// Creates an empty `HashMap` with at least the specified capacity.
254    ///
255    /// The hash map will be able to hold at least `capacity` elements without
256    /// reallocating. This method is allowed to allocate for more elements than
257    /// `capacity`. If `capacity` is zero, the hash map will not allocate.
258    ///
259    /// # Examples
260    ///
261    /// ```
262    /// use std::collections::HashMap;
263    /// let mut map: HashMap<&str, i32> = HashMap::with_capacity(10);
264    /// ```
265    #[inline]
266    #[must_use]
267    #[stable(feature = "rust1", since = "1.0.0")]
268    pub fn with_capacity(capacity: usize) -> HashMap<K, V, RandomState> {
269        HashMap::with_capacity_and_hasher(capacity, Default::default())
270    }
271}
272
273impl<K, V, S> HashMap<K, V, S> {
274    /// Creates an empty `HashMap` which will use the given hash builder to hash
275    /// keys.
276    ///
277    /// The created map has the default initial capacity.
278    ///
279    /// Warning: `hash_builder` is normally randomly generated, and
280    /// is designed to allow HashMaps to be resistant to attacks that
281    /// cause many collisions and very poor performance. Setting it
282    /// manually using this function can expose a DoS attack vector.
283    ///
284    /// The `hash_builder` passed should implement the [`BuildHasher`] trait for
285    /// the `HashMap` to be useful, see its documentation for details.
286    ///
287    /// # Examples
288    ///
289    /// ```
290    /// use std::collections::HashMap;
291    /// use std::hash::RandomState;
292    ///
293    /// let s = RandomState::new();
294    /// let mut map = HashMap::with_hasher(s);
295    /// map.insert(1, 2);
296    /// ```
297    #[inline]
298    #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
299    #[rustc_const_stable(feature = "const_collections_with_hasher", since = "1.85.0")]
300    pub const fn with_hasher(hash_builder: S) -> HashMap<K, V, S> {
301        HashMap { base: base::HashMap::with_hasher(hash_builder) }
302    }
303
304    /// Creates an empty `HashMap` with at least the specified capacity, using
305    /// `hasher` to hash the keys.
306    ///
307    /// The hash map will be able to hold at least `capacity` elements without
308    /// reallocating. This method is allowed to allocate for more elements than
309    /// `capacity`. If `capacity` is zero, the hash map will not allocate.
310    ///
311    /// Warning: `hasher` is normally randomly generated, and
312    /// is designed to allow HashMaps to be resistant to attacks that
313    /// cause many collisions and very poor performance. Setting it
314    /// manually using this function can expose a DoS attack vector.
315    ///
316    /// The `hasher` passed should implement the [`BuildHasher`] trait for
317    /// the `HashMap` to be useful, see its documentation for details.
318    ///
319    /// # Examples
320    ///
321    /// ```
322    /// use std::collections::HashMap;
323    /// use std::hash::RandomState;
324    ///
325    /// let s = RandomState::new();
326    /// let mut map = HashMap::with_capacity_and_hasher(10, s);
327    /// map.insert(1, 2);
328    /// ```
329    #[inline]
330    #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
331    pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> HashMap<K, V, S> {
332        HashMap { base: base::HashMap::with_capacity_and_hasher(capacity, hasher) }
333    }
334
335    /// Returns the number of elements the map can hold without reallocating.
336    ///
337    /// This number is a lower bound; the `HashMap<K, V>` might be able to hold
338    /// more, but is guaranteed to be able to hold at least this many.
339    ///
340    /// # Examples
341    ///
342    /// ```
343    /// use std::collections::HashMap;
344    /// let map: HashMap<i32, i32> = HashMap::with_capacity(100);
345    /// assert!(map.capacity() >= 100);
346    /// ```
347    #[inline]
348    #[stable(feature = "rust1", since = "1.0.0")]
349    pub fn capacity(&self) -> usize {
350        self.base.capacity()
351    }
352
353    /// An iterator visiting all keys in arbitrary order.
354    /// The iterator element type is `&'a K`.
355    ///
356    /// # Examples
357    ///
358    /// ```
359    /// use std::collections::HashMap;
360    ///
361    /// let map = HashMap::from([
362    ///     ("a", 1),
363    ///     ("b", 2),
364    ///     ("c", 3),
365    /// ]);
366    ///
367    /// for key in map.keys() {
368    ///     println!("{key}");
369    /// }
370    /// ```
371    ///
372    /// # Performance
373    ///
374    /// In the current implementation, iterating over keys takes O(capacity) time
375    /// instead of O(len) because it internally visits empty buckets too.
376    #[rustc_lint_query_instability]
377    #[stable(feature = "rust1", since = "1.0.0")]
378    pub fn keys(&self) -> Keys<'_, K, V> {
379        Keys { inner: self.iter() }
380    }
381
382    /// Creates a consuming iterator visiting all the keys in arbitrary order.
383    /// The map cannot be used after calling this.
384    /// The iterator element type is `K`.
385    ///
386    /// # Examples
387    ///
388    /// ```
389    /// use std::collections::HashMap;
390    ///
391    /// let map = HashMap::from([
392    ///     ("a", 1),
393    ///     ("b", 2),
394    ///     ("c", 3),
395    /// ]);
396    ///
397    /// let mut vec: Vec<&str> = map.into_keys().collect();
398    /// // The `IntoKeys` iterator produces keys in arbitrary order, so the
399    /// // keys must be sorted to test them against a sorted array.
400    /// vec.sort_unstable();
401    /// assert_eq!(vec, ["a", "b", "c"]);
402    /// ```
403    ///
404    /// # Performance
405    ///
406    /// In the current implementation, iterating over keys takes O(capacity) time
407    /// instead of O(len) because it internally visits empty buckets too.
408    #[inline]
409    #[rustc_lint_query_instability]
410    #[stable(feature = "map_into_keys_values", since = "1.54.0")]
411    pub fn into_keys(self) -> IntoKeys<K, V> {
412        IntoKeys { inner: self.into_iter() }
413    }
414
415    /// An iterator visiting all values in arbitrary order.
416    /// The iterator element type is `&'a V`.
417    ///
418    /// # Examples
419    ///
420    /// ```
421    /// use std::collections::HashMap;
422    ///
423    /// let map = HashMap::from([
424    ///     ("a", 1),
425    ///     ("b", 2),
426    ///     ("c", 3),
427    /// ]);
428    ///
429    /// for val in map.values() {
430    ///     println!("{val}");
431    /// }
432    /// ```
433    ///
434    /// # Performance
435    ///
436    /// In the current implementation, iterating over values takes O(capacity) time
437    /// instead of O(len) because it internally visits empty buckets too.
438    #[rustc_lint_query_instability]
439    #[stable(feature = "rust1", since = "1.0.0")]
440    pub fn values(&self) -> Values<'_, K, V> {
441        Values { inner: self.iter() }
442    }
443
444    /// An iterator visiting all values mutably in arbitrary order.
445    /// The iterator element type is `&'a mut V`.
446    ///
447    /// # Examples
448    ///
449    /// ```
450    /// use std::collections::HashMap;
451    ///
452    /// let mut map = HashMap::from([
453    ///     ("a", 1),
454    ///     ("b", 2),
455    ///     ("c", 3),
456    /// ]);
457    ///
458    /// for val in map.values_mut() {
459    ///     *val = *val + 10;
460    /// }
461    ///
462    /// for val in map.values() {
463    ///     println!("{val}");
464    /// }
465    /// ```
466    ///
467    /// # Performance
468    ///
469    /// In the current implementation, iterating over values takes O(capacity) time
470    /// instead of O(len) because it internally visits empty buckets too.
471    #[rustc_lint_query_instability]
472    #[stable(feature = "map_values_mut", since = "1.10.0")]
473    pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
474        ValuesMut { inner: self.iter_mut() }
475    }
476
477    /// Creates a consuming iterator visiting all the values in arbitrary order.
478    /// The map cannot be used after calling this.
479    /// The iterator element type is `V`.
480    ///
481    /// # Examples
482    ///
483    /// ```
484    /// use std::collections::HashMap;
485    ///
486    /// let map = HashMap::from([
487    ///     ("a", 1),
488    ///     ("b", 2),
489    ///     ("c", 3),
490    /// ]);
491    ///
492    /// let mut vec: Vec<i32> = map.into_values().collect();
493    /// // The `IntoValues` iterator produces values in arbitrary order, so
494    /// // the values must be sorted to test them against a sorted array.
495    /// vec.sort_unstable();
496    /// assert_eq!(vec, [1, 2, 3]);
497    /// ```
498    ///
499    /// # Performance
500    ///
501    /// In the current implementation, iterating over values takes O(capacity) time
502    /// instead of O(len) because it internally visits empty buckets too.
503    #[inline]
504    #[rustc_lint_query_instability]
505    #[stable(feature = "map_into_keys_values", since = "1.54.0")]
506    pub fn into_values(self) -> IntoValues<K, V> {
507        IntoValues { inner: self.into_iter() }
508    }
509
510    /// An iterator visiting all key-value pairs in arbitrary order.
511    /// The iterator element type is `(&'a K, &'a V)`.
512    ///
513    /// # Examples
514    ///
515    /// ```
516    /// use std::collections::HashMap;
517    ///
518    /// let map = HashMap::from([
519    ///     ("a", 1),
520    ///     ("b", 2),
521    ///     ("c", 3),
522    /// ]);
523    ///
524    /// for (key, val) in map.iter() {
525    ///     println!("key: {key} val: {val}");
526    /// }
527    /// ```
528    ///
529    /// # Performance
530    ///
531    /// In the current implementation, iterating over map takes O(capacity) time
532    /// instead of O(len) because it internally visits empty buckets too.
533    #[rustc_lint_query_instability]
534    #[stable(feature = "rust1", since = "1.0.0")]
535    pub fn iter(&self) -> Iter<'_, K, V> {
536        Iter { base: self.base.iter() }
537    }
538
539    /// An iterator visiting all key-value pairs in arbitrary order,
540    /// with mutable references to the values.
541    /// The iterator element type is `(&'a K, &'a mut V)`.
542    ///
543    /// # Examples
544    ///
545    /// ```
546    /// use std::collections::HashMap;
547    ///
548    /// let mut map = HashMap::from([
549    ///     ("a", 1),
550    ///     ("b", 2),
551    ///     ("c", 3),
552    /// ]);
553    ///
554    /// // Update all values
555    /// for (_, val) in map.iter_mut() {
556    ///     *val *= 2;
557    /// }
558    ///
559    /// for (key, val) in &map {
560    ///     println!("key: {key} val: {val}");
561    /// }
562    /// ```
563    ///
564    /// # Performance
565    ///
566    /// In the current implementation, iterating over map takes O(capacity) time
567    /// instead of O(len) because it internally visits empty buckets too.
568    #[rustc_lint_query_instability]
569    #[stable(feature = "rust1", since = "1.0.0")]
570    pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
571        IterMut { base: self.base.iter_mut() }
572    }
573
574    /// Returns the number of elements in the map.
575    ///
576    /// # Examples
577    ///
578    /// ```
579    /// use std::collections::HashMap;
580    ///
581    /// let mut a = HashMap::new();
582    /// assert_eq!(a.len(), 0);
583    /// a.insert(1, "a");
584    /// assert_eq!(a.len(), 1);
585    /// ```
586    #[stable(feature = "rust1", since = "1.0.0")]
587    pub fn len(&self) -> usize {
588        self.base.len()
589    }
590
591    /// Returns `true` if the map contains no elements.
592    ///
593    /// # Examples
594    ///
595    /// ```
596    /// use std::collections::HashMap;
597    ///
598    /// let mut a = HashMap::new();
599    /// assert!(a.is_empty());
600    /// a.insert(1, "a");
601    /// assert!(!a.is_empty());
602    /// ```
603    #[inline]
604    #[stable(feature = "rust1", since = "1.0.0")]
605    pub fn is_empty(&self) -> bool {
606        self.base.is_empty()
607    }
608
609    /// Clears the map, returning all key-value pairs as an iterator. Keeps the
610    /// allocated memory for reuse.
611    ///
612    /// If the returned iterator is dropped before being fully consumed, it
613    /// drops the remaining key-value pairs. The returned iterator keeps a
614    /// mutable borrow on the map to optimize its implementation.
615    ///
616    /// # Examples
617    ///
618    /// ```
619    /// use std::collections::HashMap;
620    ///
621    /// let mut a = HashMap::new();
622    /// a.insert(1, "a");
623    /// a.insert(2, "b");
624    ///
625    /// for (k, v) in a.drain().take(1) {
626    ///     assert!(k == 1 || k == 2);
627    ///     assert!(v == "a" || v == "b");
628    /// }
629    ///
630    /// assert!(a.is_empty());
631    /// ```
632    #[inline]
633    #[rustc_lint_query_instability]
634    #[stable(feature = "drain", since = "1.6.0")]
635    pub fn drain(&mut self) -> Drain<'_, K, V> {
636        Drain { base: self.base.drain() }
637    }
638
639    /// Creates an iterator which uses a closure to determine if an element should be removed.
640    ///
641    /// If the closure returns true, the element is removed from the map and yielded.
642    /// If the closure returns false, or panics, the element remains in the map and will not be
643    /// yielded.
644    ///
645    /// Note that `extract_if` lets you mutate every value in the filter closure, regardless of
646    /// whether you choose to keep or remove it.
647    ///
648    /// If the returned `ExtractIf` is not exhausted, e.g. because it is dropped without iterating
649    /// or the iteration short-circuits, then the remaining elements will be retained.
650    /// Use [`retain`] with a negated predicate if you do not need the returned iterator.
651    ///
652    /// [`retain`]: HashMap::retain
653    ///
654    /// # Examples
655    ///
656    /// Splitting a map into even and odd keys, reusing the original map:
657    ///
658    /// ```
659    /// #![feature(hash_extract_if)]
660    /// use std::collections::HashMap;
661    ///
662    /// let mut map: HashMap<i32, i32> = (0..8).map(|x| (x, x)).collect();
663    /// let extracted: HashMap<i32, i32> = map.extract_if(|k, _v| k % 2 == 0).collect();
664    ///
665    /// let mut evens = extracted.keys().copied().collect::<Vec<_>>();
666    /// let mut odds = map.keys().copied().collect::<Vec<_>>();
667    /// evens.sort();
668    /// odds.sort();
669    ///
670    /// assert_eq!(evens, vec![0, 2, 4, 6]);
671    /// assert_eq!(odds, vec![1, 3, 5, 7]);
672    /// ```
673    #[inline]
674    #[rustc_lint_query_instability]
675    #[unstable(feature = "hash_extract_if", issue = "59618")]
676    pub fn extract_if<F>(&mut self, pred: F) -> ExtractIf<'_, K, V, F>
677    where
678        F: FnMut(&K, &mut V) -> bool,
679    {
680        ExtractIf { base: self.base.extract_if(pred) }
681    }
682
683    /// Retains only the elements specified by the predicate.
684    ///
685    /// In other words, remove all pairs `(k, v)` for which `f(&k, &mut v)` returns `false`.
686    /// The elements are visited in unsorted (and unspecified) order.
687    ///
688    /// # Examples
689    ///
690    /// ```
691    /// use std::collections::HashMap;
692    ///
693    /// let mut map: HashMap<i32, i32> = (0..8).map(|x| (x, x*10)).collect();
694    /// map.retain(|&k, _| k % 2 == 0);
695    /// assert_eq!(map.len(), 4);
696    /// ```
697    ///
698    /// # Performance
699    ///
700    /// In the current implementation, this operation takes O(capacity) time
701    /// instead of O(len) because it internally visits empty buckets too.
702    #[inline]
703    #[rustc_lint_query_instability]
704    #[stable(feature = "retain_hash_collection", since = "1.18.0")]
705    pub fn retain<F>(&mut self, f: F)
706    where
707        F: FnMut(&K, &mut V) -> bool,
708    {
709        self.base.retain(f)
710    }
711
712    /// Clears the map, removing all key-value pairs. Keeps the allocated memory
713    /// for reuse.
714    ///
715    /// # Examples
716    ///
717    /// ```
718    /// use std::collections::HashMap;
719    ///
720    /// let mut a = HashMap::new();
721    /// a.insert(1, "a");
722    /// a.clear();
723    /// assert!(a.is_empty());
724    /// ```
725    #[inline]
726    #[stable(feature = "rust1", since = "1.0.0")]
727    pub fn clear(&mut self) {
728        self.base.clear();
729    }
730
731    /// Returns a reference to the map's [`BuildHasher`].
732    ///
733    /// # Examples
734    ///
735    /// ```
736    /// use std::collections::HashMap;
737    /// use std::hash::RandomState;
738    ///
739    /// let hasher = RandomState::new();
740    /// let map: HashMap<i32, i32> = HashMap::with_hasher(hasher);
741    /// let hasher: &RandomState = map.hasher();
742    /// ```
743    #[inline]
744    #[stable(feature = "hashmap_public_hasher", since = "1.9.0")]
745    pub fn hasher(&self) -> &S {
746        self.base.hasher()
747    }
748}
749
750impl<K, V, S> HashMap<K, V, S>
751where
752    K: Eq + Hash,
753    S: BuildHasher,
754{
755    /// Reserves capacity for at least `additional` more elements to be inserted
756    /// in the `HashMap`. The collection may reserve more space to speculatively
757    /// avoid frequent reallocations. After calling `reserve`,
758    /// capacity will be greater than or equal to `self.len() + additional`.
759    /// Does nothing if capacity is already sufficient.
760    ///
761    /// # Panics
762    ///
763    /// Panics if the new allocation size overflows [`usize`].
764    ///
765    /// # Examples
766    ///
767    /// ```
768    /// use std::collections::HashMap;
769    /// let mut map: HashMap<&str, i32> = HashMap::new();
770    /// map.reserve(10);
771    /// ```
772    #[inline]
773    #[stable(feature = "rust1", since = "1.0.0")]
774    pub fn reserve(&mut self, additional: usize) {
775        self.base.reserve(additional)
776    }
777
778    /// Tries to reserve capacity for at least `additional` more elements to be inserted
779    /// in the `HashMap`. The collection may reserve more space to speculatively
780    /// avoid frequent reallocations. After calling `try_reserve`,
781    /// capacity will be greater than or equal to `self.len() + additional` if
782    /// it returns `Ok(())`.
783    /// Does nothing if capacity is already sufficient.
784    ///
785    /// # Errors
786    ///
787    /// If the capacity overflows, or the allocator reports a failure, then an error
788    /// is returned.
789    ///
790    /// # Examples
791    ///
792    /// ```
793    /// use std::collections::HashMap;
794    ///
795    /// let mut map: HashMap<&str, isize> = HashMap::new();
796    /// map.try_reserve(10).expect("why is the test harness OOMing on a handful of bytes?");
797    /// ```
798    #[inline]
799    #[stable(feature = "try_reserve", since = "1.57.0")]
800    pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
801        self.base.try_reserve(additional).map_err(map_try_reserve_error)
802    }
803
804    /// Shrinks the capacity of the map as much as possible. It will drop
805    /// down as much as possible while maintaining the internal rules
806    /// and possibly leaving some space in accordance with the resize policy.
807    ///
808    /// # Examples
809    ///
810    /// ```
811    /// use std::collections::HashMap;
812    ///
813    /// let mut map: HashMap<i32, i32> = HashMap::with_capacity(100);
814    /// map.insert(1, 2);
815    /// map.insert(3, 4);
816    /// assert!(map.capacity() >= 100);
817    /// map.shrink_to_fit();
818    /// assert!(map.capacity() >= 2);
819    /// ```
820    #[inline]
821    #[stable(feature = "rust1", since = "1.0.0")]
822    pub fn shrink_to_fit(&mut self) {
823        self.base.shrink_to_fit();
824    }
825
826    /// Shrinks the capacity of the map with a lower limit. It will drop
827    /// down no lower than the supplied limit while maintaining the internal rules
828    /// and possibly leaving some space in accordance with the resize policy.
829    ///
830    /// If the current capacity is less than the lower limit, this is a no-op.
831    ///
832    /// # Examples
833    ///
834    /// ```
835    /// use std::collections::HashMap;
836    ///
837    /// let mut map: HashMap<i32, i32> = HashMap::with_capacity(100);
838    /// map.insert(1, 2);
839    /// map.insert(3, 4);
840    /// assert!(map.capacity() >= 100);
841    /// map.shrink_to(10);
842    /// assert!(map.capacity() >= 10);
843    /// map.shrink_to(0);
844    /// assert!(map.capacity() >= 2);
845    /// ```
846    #[inline]
847    #[stable(feature = "shrink_to", since = "1.56.0")]
848    pub fn shrink_to(&mut self, min_capacity: usize) {
849        self.base.shrink_to(min_capacity);
850    }
851
852    /// Gets the given key's corresponding entry in the map for in-place manipulation.
853    ///
854    /// # Examples
855    ///
856    /// ```
857    /// use std::collections::HashMap;
858    ///
859    /// let mut letters = HashMap::new();
860    ///
861    /// for ch in "a short treatise on fungi".chars() {
862    ///     letters.entry(ch).and_modify(|counter| *counter += 1).or_insert(1);
863    /// }
864    ///
865    /// assert_eq!(letters[&'s'], 2);
866    /// assert_eq!(letters[&'t'], 3);
867    /// assert_eq!(letters[&'u'], 1);
868    /// assert_eq!(letters.get(&'y'), None);
869    /// ```
870    #[inline]
871    #[stable(feature = "rust1", since = "1.0.0")]
872    pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {
873        map_entry(self.base.rustc_entry(key))
874    }
875
876    /// Returns a reference to the value corresponding to the key.
877    ///
878    /// The key may be any borrowed form of the map's key type, but
879    /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
880    /// the key type.
881    ///
882    /// # Examples
883    ///
884    /// ```
885    /// use std::collections::HashMap;
886    ///
887    /// let mut map = HashMap::new();
888    /// map.insert(1, "a");
889    /// assert_eq!(map.get(&1), Some(&"a"));
890    /// assert_eq!(map.get(&2), None);
891    /// ```
892    #[stable(feature = "rust1", since = "1.0.0")]
893    #[inline]
894    pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
895    where
896        K: Borrow<Q>,
897        Q: Hash + Eq,
898    {
899        self.base.get(k)
900    }
901
902    /// Returns the key-value pair corresponding to the supplied key. This is
903    /// potentially useful:
904    /// - for key types where non-identical keys can be considered equal;
905    /// - for getting the `&K` stored key value from a borrowed `&Q` lookup key; or
906    /// - for getting a reference to a key with the same lifetime as the collection.
907    ///
908    /// The supplied key may be any borrowed form of the map's key type, but
909    /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
910    /// the key type.
911    ///
912    /// # Examples
913    ///
914    /// ```
915    /// use std::collections::HashMap;
916    /// use std::hash::{Hash, Hasher};
917    ///
918    /// #[derive(Clone, Copy, Debug)]
919    /// struct S {
920    ///     id: u32,
921    /// #   #[allow(unused)] // prevents a "field `name` is never read" error
922    ///     name: &'static str, // ignored by equality and hashing operations
923    /// }
924    ///
925    /// impl PartialEq for S {
926    ///     fn eq(&self, other: &S) -> bool {
927    ///         self.id == other.id
928    ///     }
929    /// }
930    ///
931    /// impl Eq for S {}
932    ///
933    /// impl Hash for S {
934    ///     fn hash<H: Hasher>(&self, state: &mut H) {
935    ///         self.id.hash(state);
936    ///     }
937    /// }
938    ///
939    /// let j_a = S { id: 1, name: "Jessica" };
940    /// let j_b = S { id: 1, name: "Jess" };
941    /// let p = S { id: 2, name: "Paul" };
942    /// assert_eq!(j_a, j_b);
943    ///
944    /// let mut map = HashMap::new();
945    /// map.insert(j_a, "Paris");
946    /// assert_eq!(map.get_key_value(&j_a), Some((&j_a, &"Paris")));
947    /// assert_eq!(map.get_key_value(&j_b), Some((&j_a, &"Paris"))); // the notable case
948    /// assert_eq!(map.get_key_value(&p), None);
949    /// ```
950    #[inline]
951    #[stable(feature = "map_get_key_value", since = "1.40.0")]
952    pub fn get_key_value<Q: ?Sized>(&self, k: &Q) -> Option<(&K, &V)>
953    where
954        K: Borrow<Q>,
955        Q: Hash + Eq,
956    {
957        self.base.get_key_value(k)
958    }
959
960    /// Attempts to get mutable references to `N` values in the map at once.
961    ///
962    /// Returns an array of length `N` with the results of each query. For soundness, at most one
963    /// mutable reference will be returned to any value. `None` will be used if the key is missing.
964    ///
965    /// # Panics
966    ///
967    /// Panics if any keys are overlapping.
968    ///
969    /// # Examples
970    ///
971    /// ```
972    /// use std::collections::HashMap;
973    ///
974    /// let mut libraries = HashMap::new();
975    /// libraries.insert("Bodleian Library".to_string(), 1602);
976    /// libraries.insert("Athenæum".to_string(), 1807);
977    /// libraries.insert("Herzogin-Anna-Amalia-Bibliothek".to_string(), 1691);
978    /// libraries.insert("Library of Congress".to_string(), 1800);
979    ///
980    /// // Get Athenæum and Bodleian Library
981    /// let [Some(a), Some(b)] = libraries.get_disjoint_mut([
982    ///     "Athenæum",
983    ///     "Bodleian Library",
984    /// ]) else { panic!() };
985    ///
986    /// // Assert values of Athenæum and Library of Congress
987    /// let got = libraries.get_disjoint_mut([
988    ///     "Athenæum",
989    ///     "Library of Congress",
990    /// ]);
991    /// assert_eq!(
992    ///     got,
993    ///     [
994    ///         Some(&mut 1807),
995    ///         Some(&mut 1800),
996    ///     ],
997    /// );
998    ///
999    /// // Missing keys result in None
1000    /// let got = libraries.get_disjoint_mut([
1001    ///     "Athenæum",
1002    ///     "New York Public Library",
1003    /// ]);
1004    /// assert_eq!(
1005    ///     got,
1006    ///     [
1007    ///         Some(&mut 1807),
1008    ///         None
1009    ///     ]
1010    /// );
1011    /// ```
1012    ///
1013    /// ```should_panic
1014    /// use std::collections::HashMap;
1015    ///
1016    /// let mut libraries = HashMap::new();
1017    /// libraries.insert("Athenæum".to_string(), 1807);
1018    ///
1019    /// // Duplicate keys panic!
1020    /// let got = libraries.get_disjoint_mut([
1021    ///     "Athenæum",
1022    ///     "Athenæum",
1023    /// ]);
1024    /// ```
1025    #[inline]
1026    #[doc(alias = "get_many_mut")]
1027    #[stable(feature = "map_many_mut", since = "CURRENT_RUSTC_VERSION")]
1028    pub fn get_disjoint_mut<Q: ?Sized, const N: usize>(
1029        &mut self,
1030        ks: [&Q; N],
1031    ) -> [Option<&'_ mut V>; N]
1032    where
1033        K: Borrow<Q>,
1034        Q: Hash + Eq,
1035    {
1036        self.base.get_many_mut(ks)
1037    }
1038
1039    /// Attempts to get mutable references to `N` values in the map at once, without validating that
1040    /// the values are unique.
1041    ///
1042    /// Returns an array of length `N` with the results of each query. `None` will be used if
1043    /// the key is missing.
1044    ///
1045    /// For a safe alternative see [`get_disjoint_mut`](`HashMap::get_disjoint_mut`).
1046    ///
1047    /// # Safety
1048    ///
1049    /// Calling this method with overlapping keys is *[undefined behavior]* even if the resulting
1050    /// references are not used.
1051    ///
1052    /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
1053    ///
1054    /// # Examples
1055    ///
1056    /// ```
1057    /// use std::collections::HashMap;
1058    ///
1059    /// let mut libraries = HashMap::new();
1060    /// libraries.insert("Bodleian Library".to_string(), 1602);
1061    /// libraries.insert("Athenæum".to_string(), 1807);
1062    /// libraries.insert("Herzogin-Anna-Amalia-Bibliothek".to_string(), 1691);
1063    /// libraries.insert("Library of Congress".to_string(), 1800);
1064    ///
1065    /// // SAFETY: The keys do not overlap.
1066    /// let [Some(a), Some(b)] = (unsafe { libraries.get_disjoint_unchecked_mut([
1067    ///     "Athenæum",
1068    ///     "Bodleian Library",
1069    /// ]) }) else { panic!() };
1070    ///
1071    /// // SAFETY: The keys do not overlap.
1072    /// let got = unsafe { libraries.get_disjoint_unchecked_mut([
1073    ///     "Athenæum",
1074    ///     "Library of Congress",
1075    /// ]) };
1076    /// assert_eq!(
1077    ///     got,
1078    ///     [
1079    ///         Some(&mut 1807),
1080    ///         Some(&mut 1800),
1081    ///     ],
1082    /// );
1083    ///
1084    /// // SAFETY: The keys do not overlap.
1085    /// let got = unsafe { libraries.get_disjoint_unchecked_mut([
1086    ///     "Athenæum",
1087    ///     "New York Public Library",
1088    /// ]) };
1089    /// // Missing keys result in None
1090    /// assert_eq!(got, [Some(&mut 1807), None]);
1091    /// ```
1092    #[inline]
1093    #[doc(alias = "get_many_unchecked_mut")]
1094    #[stable(feature = "map_many_mut", since = "CURRENT_RUSTC_VERSION")]
1095    pub unsafe fn get_disjoint_unchecked_mut<Q: ?Sized, const N: usize>(
1096        &mut self,
1097        ks: [&Q; N],
1098    ) -> [Option<&'_ mut V>; N]
1099    where
1100        K: Borrow<Q>,
1101        Q: Hash + Eq,
1102    {
1103        unsafe { self.base.get_many_unchecked_mut(ks) }
1104    }
1105
1106    /// Returns `true` if the map contains a value for the specified key.
1107    ///
1108    /// The key may be any borrowed form of the map's key type, but
1109    /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
1110    /// the key type.
1111    ///
1112    /// # Examples
1113    ///
1114    /// ```
1115    /// use std::collections::HashMap;
1116    ///
1117    /// let mut map = HashMap::new();
1118    /// map.insert(1, "a");
1119    /// assert_eq!(map.contains_key(&1), true);
1120    /// assert_eq!(map.contains_key(&2), false);
1121    /// ```
1122    #[inline]
1123    #[stable(feature = "rust1", since = "1.0.0")]
1124    #[cfg_attr(not(test), rustc_diagnostic_item = "hashmap_contains_key")]
1125    pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool
1126    where
1127        K: Borrow<Q>,
1128        Q: Hash + Eq,
1129    {
1130        self.base.contains_key(k)
1131    }
1132
1133    /// Returns a mutable reference to the value corresponding to the key.
1134    ///
1135    /// The key may be any borrowed form of the map's key type, but
1136    /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
1137    /// the key type.
1138    ///
1139    /// # Examples
1140    ///
1141    /// ```
1142    /// use std::collections::HashMap;
1143    ///
1144    /// let mut map = HashMap::new();
1145    /// map.insert(1, "a");
1146    /// if let Some(x) = map.get_mut(&1) {
1147    ///     *x = "b";
1148    /// }
1149    /// assert_eq!(map[&1], "b");
1150    /// ```
1151    #[inline]
1152    #[stable(feature = "rust1", since = "1.0.0")]
1153    pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
1154    where
1155        K: Borrow<Q>,
1156        Q: Hash + Eq,
1157    {
1158        self.base.get_mut(k)
1159    }
1160
1161    /// Inserts a key-value pair into the map.
1162    ///
1163    /// If the map did not have this key present, [`None`] is returned.
1164    ///
1165    /// If the map did have this key present, the value is updated, and the old
1166    /// value is returned. The key is not updated, though; this matters for
1167    /// types that can be `==` without being identical. See the [module-level
1168    /// documentation] for more.
1169    ///
1170    /// [module-level documentation]: crate::collections#insert-and-complex-keys
1171    ///
1172    /// # Examples
1173    ///
1174    /// ```
1175    /// use std::collections::HashMap;
1176    ///
1177    /// let mut map = HashMap::new();
1178    /// assert_eq!(map.insert(37, "a"), None);
1179    /// assert_eq!(map.is_empty(), false);
1180    ///
1181    /// map.insert(37, "b");
1182    /// assert_eq!(map.insert(37, "c"), Some("b"));
1183    /// assert_eq!(map[&37], "c");
1184    /// ```
1185    #[inline]
1186    #[stable(feature = "rust1", since = "1.0.0")]
1187    #[rustc_confusables("push", "append", "put")]
1188    #[cfg_attr(not(test), rustc_diagnostic_item = "hashmap_insert")]
1189    pub fn insert(&mut self, k: K, v: V) -> Option<V> {
1190        self.base.insert(k, v)
1191    }
1192
1193    /// Tries to insert a key-value pair into the map, and returns
1194    /// a mutable reference to the value in the entry.
1195    ///
1196    /// If the map already had this key present, nothing is updated, and
1197    /// an error containing the occupied entry and the value is returned.
1198    ///
1199    /// # Examples
1200    ///
1201    /// Basic usage:
1202    ///
1203    /// ```
1204    /// #![feature(map_try_insert)]
1205    ///
1206    /// use std::collections::HashMap;
1207    ///
1208    /// let mut map = HashMap::new();
1209    /// assert_eq!(map.try_insert(37, "a").unwrap(), &"a");
1210    ///
1211    /// let err = map.try_insert(37, "b").unwrap_err();
1212    /// assert_eq!(err.entry.key(), &37);
1213    /// assert_eq!(err.entry.get(), &"a");
1214    /// assert_eq!(err.value, "b");
1215    /// ```
1216    #[unstable(feature = "map_try_insert", issue = "82766")]
1217    pub fn try_insert(&mut self, key: K, value: V) -> Result<&mut V, OccupiedError<'_, K, V>> {
1218        match self.entry(key) {
1219            Occupied(entry) => Err(OccupiedError { entry, value }),
1220            Vacant(entry) => Ok(entry.insert(value)),
1221        }
1222    }
1223
1224    /// Removes a key from the map, returning the value at the key if the key
1225    /// was previously in the map.
1226    ///
1227    /// The key may be any borrowed form of the map's key type, but
1228    /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
1229    /// the key type.
1230    ///
1231    /// # Examples
1232    ///
1233    /// ```
1234    /// use std::collections::HashMap;
1235    ///
1236    /// let mut map = HashMap::new();
1237    /// map.insert(1, "a");
1238    /// assert_eq!(map.remove(&1), Some("a"));
1239    /// assert_eq!(map.remove(&1), None);
1240    /// ```
1241    #[inline]
1242    #[stable(feature = "rust1", since = "1.0.0")]
1243    #[rustc_confusables("delete", "take")]
1244    pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V>
1245    where
1246        K: Borrow<Q>,
1247        Q: Hash + Eq,
1248    {
1249        self.base.remove(k)
1250    }
1251
1252    /// Removes a key from the map, returning the stored key and value if the
1253    /// key was previously in the map.
1254    ///
1255    /// The key may be any borrowed form of the map's key type, but
1256    /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
1257    /// the key type.
1258    ///
1259    /// # Examples
1260    ///
1261    /// ```
1262    /// use std::collections::HashMap;
1263    ///
1264    /// # fn main() {
1265    /// let mut map = HashMap::new();
1266    /// map.insert(1, "a");
1267    /// assert_eq!(map.remove_entry(&1), Some((1, "a")));
1268    /// assert_eq!(map.remove(&1), None);
1269    /// # }
1270    /// ```
1271    #[inline]
1272    #[stable(feature = "hash_map_remove_entry", since = "1.27.0")]
1273    pub fn remove_entry<Q: ?Sized>(&mut self, k: &Q) -> Option<(K, V)>
1274    where
1275        K: Borrow<Q>,
1276        Q: Hash + Eq,
1277    {
1278        self.base.remove_entry(k)
1279    }
1280}
1281
1282impl<K, V, S> HashMap<K, V, S>
1283where
1284    S: BuildHasher,
1285{
1286    /// Creates a raw entry builder for the `HashMap`.
1287    ///
1288    /// Raw entries provide the lowest level of control for searching and
1289    /// manipulating a map. They must be manually initialized with a hash and
1290    /// then manually searched. After this, insertions into a vacant entry
1291    /// still require an owned key to be provided.
1292    ///
1293    /// Raw entries are useful for such exotic situations as:
1294    ///
1295    /// * Hash memoization
1296    /// * Deferring the creation of an owned key until it is known to be required
1297    /// * Using a search key that doesn't work with the Borrow trait
1298    /// * Using custom comparison logic without newtype wrappers
1299    ///
1300    /// Because raw entries provide much more low-level control, it's much easier
1301    /// to put the `HashMap` into an inconsistent state which, while memory-safe,
1302    /// will cause the map to produce seemingly random results. Higher-level and
1303    /// more foolproof APIs like `entry` should be preferred when possible.
1304    ///
1305    /// In particular, the hash used to initialize the raw entry must still be
1306    /// consistent with the hash of the key that is ultimately stored in the entry.
1307    /// This is because implementations of `HashMap` may need to recompute hashes
1308    /// when resizing, at which point only the keys are available.
1309    ///
1310    /// Raw entries give mutable access to the keys. This must not be used
1311    /// to modify how the key would compare or hash, as the map will not re-evaluate
1312    /// where the key should go, meaning the keys may become "lost" if their
1313    /// location does not reflect their state. For instance, if you change a key
1314    /// so that the map now contains keys which compare equal, search may start
1315    /// acting erratically, with two keys randomly masking each other. Implementations
1316    /// are free to assume this doesn't happen (within the limits of memory-safety).
1317    #[inline]
1318    #[unstable(feature = "hash_raw_entry", issue = "56167")]
1319    pub fn raw_entry_mut(&mut self) -> RawEntryBuilderMut<'_, K, V, S> {
1320        RawEntryBuilderMut { map: self }
1321    }
1322
1323    /// Creates a raw immutable entry builder for the `HashMap`.
1324    ///
1325    /// Raw entries provide the lowest level of control for searching and
1326    /// manipulating a map. They must be manually initialized with a hash and
1327    /// then manually searched.
1328    ///
1329    /// This is useful for
1330    /// * Hash memoization
1331    /// * Using a search key that doesn't work with the Borrow trait
1332    /// * Using custom comparison logic without newtype wrappers
1333    ///
1334    /// Unless you are in such a situation, higher-level and more foolproof APIs like
1335    /// `get` should be preferred.
1336    ///
1337    /// Immutable raw entries have very limited use; you might instead want `raw_entry_mut`.
1338    #[inline]
1339    #[unstable(feature = "hash_raw_entry", issue = "56167")]
1340    pub fn raw_entry(&self) -> RawEntryBuilder<'_, K, V, S> {
1341        RawEntryBuilder { map: self }
1342    }
1343}
1344
1345#[stable(feature = "rust1", since = "1.0.0")]
1346impl<K, V, S> Clone for HashMap<K, V, S>
1347where
1348    K: Clone,
1349    V: Clone,
1350    S: Clone,
1351{
1352    #[inline]
1353    fn clone(&self) -> Self {
1354        Self { base: self.base.clone() }
1355    }
1356
1357    #[inline]
1358    fn clone_from(&mut self, source: &Self) {
1359        self.base.clone_from(&source.base);
1360    }
1361}
1362
1363#[stable(feature = "rust1", since = "1.0.0")]
1364impl<K, V, S> PartialEq for HashMap<K, V, S>
1365where
1366    K: Eq + Hash,
1367    V: PartialEq,
1368    S: BuildHasher,
1369{
1370    fn eq(&self, other: &HashMap<K, V, S>) -> bool {
1371        if self.len() != other.len() {
1372            return false;
1373        }
1374
1375        self.iter().all(|(key, value)| other.get(key).map_or(false, |v| *value == *v))
1376    }
1377}
1378
1379#[stable(feature = "rust1", since = "1.0.0")]
1380impl<K, V, S> Eq for HashMap<K, V, S>
1381where
1382    K: Eq + Hash,
1383    V: Eq,
1384    S: BuildHasher,
1385{
1386}
1387
1388#[stable(feature = "rust1", since = "1.0.0")]
1389impl<K, V, S> Debug for HashMap<K, V, S>
1390where
1391    K: Debug,
1392    V: Debug,
1393{
1394    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1395        f.debug_map().entries(self.iter()).finish()
1396    }
1397}
1398
1399#[stable(feature = "rust1", since = "1.0.0")]
1400impl<K, V, S> Default for HashMap<K, V, S>
1401where
1402    S: Default,
1403{
1404    /// Creates an empty `HashMap<K, V, S>`, with the `Default` value for the hasher.
1405    #[inline]
1406    fn default() -> HashMap<K, V, S> {
1407        HashMap::with_hasher(Default::default())
1408    }
1409}
1410
1411#[stable(feature = "rust1", since = "1.0.0")]
1412impl<K, Q: ?Sized, V, S> Index<&Q> for HashMap<K, V, S>
1413where
1414    K: Eq + Hash + Borrow<Q>,
1415    Q: Eq + Hash,
1416    S: BuildHasher,
1417{
1418    type Output = V;
1419
1420    /// Returns a reference to the value corresponding to the supplied key.
1421    ///
1422    /// # Panics
1423    ///
1424    /// Panics if the key is not present in the `HashMap`.
1425    #[inline]
1426    fn index(&self, key: &Q) -> &V {
1427        self.get(key).expect("no entry found for key")
1428    }
1429}
1430
1431#[stable(feature = "std_collections_from_array", since = "1.56.0")]
1432// Note: as what is currently the most convenient built-in way to construct
1433// a HashMap, a simple usage of this function must not *require* the user
1434// to provide a type annotation in order to infer the third type parameter
1435// (the hasher parameter, conventionally "S").
1436// To that end, this impl is defined using RandomState as the concrete
1437// type of S, rather than being generic over `S: BuildHasher + Default`.
1438// It is expected that users who want to specify a hasher will manually use
1439// `with_capacity_and_hasher`.
1440// If type parameter defaults worked on impls, and if type parameter
1441// defaults could be mixed with const generics, then perhaps
1442// this could be generalized.
1443// See also the equivalent impl on HashSet.
1444impl<K, V, const N: usize> From<[(K, V); N]> for HashMap<K, V, RandomState>
1445where
1446    K: Eq + Hash,
1447{
1448    /// Converts a `[(K, V); N]` into a `HashMap<K, V>`.
1449    ///
1450    /// If any entries in the array have equal keys,
1451    /// all but one of the corresponding values will be dropped.
1452    ///
1453    /// # Examples
1454    ///
1455    /// ```
1456    /// use std::collections::HashMap;
1457    ///
1458    /// let map1 = HashMap::from([(1, 2), (3, 4)]);
1459    /// let map2: HashMap<_, _> = [(1, 2), (3, 4)].into();
1460    /// assert_eq!(map1, map2);
1461    /// ```
1462    fn from(arr: [(K, V); N]) -> Self {
1463        Self::from_iter(arr)
1464    }
1465}
1466
1467/// An iterator over the entries of a `HashMap`.
1468///
1469/// This `struct` is created by the [`iter`] method on [`HashMap`]. See its
1470/// documentation for more.
1471///
1472/// [`iter`]: HashMap::iter
1473///
1474/// # Example
1475///
1476/// ```
1477/// use std::collections::HashMap;
1478///
1479/// let map = HashMap::from([
1480///     ("a", 1),
1481/// ]);
1482/// let iter = map.iter();
1483/// ```
1484#[stable(feature = "rust1", since = "1.0.0")]
1485#[cfg_attr(not(test), rustc_diagnostic_item = "hashmap_iter_ty")]
1486pub struct Iter<'a, K: 'a, V: 'a> {
1487    base: base::Iter<'a, K, V>,
1488}
1489
1490// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
1491#[stable(feature = "rust1", since = "1.0.0")]
1492impl<K, V> Clone for Iter<'_, K, V> {
1493    #[inline]
1494    fn clone(&self) -> Self {
1495        Iter { base: self.base.clone() }
1496    }
1497}
1498
1499#[stable(feature = "default_iters_hash", since = "1.83.0")]
1500impl<K, V> Default for Iter<'_, K, V> {
1501    #[inline]
1502    fn default() -> Self {
1503        Iter { base: Default::default() }
1504    }
1505}
1506
1507#[stable(feature = "std_debug", since = "1.16.0")]
1508impl<K: Debug, V: Debug> fmt::Debug for Iter<'_, K, V> {
1509    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1510        f.debug_list().entries(self.clone()).finish()
1511    }
1512}
1513
1514/// A mutable iterator over the entries of a `HashMap`.
1515///
1516/// This `struct` is created by the [`iter_mut`] method on [`HashMap`]. See its
1517/// documentation for more.
1518///
1519/// [`iter_mut`]: HashMap::iter_mut
1520///
1521/// # Example
1522///
1523/// ```
1524/// use std::collections::HashMap;
1525///
1526/// let mut map = HashMap::from([
1527///     ("a", 1),
1528/// ]);
1529/// let iter = map.iter_mut();
1530/// ```
1531#[stable(feature = "rust1", since = "1.0.0")]
1532#[cfg_attr(not(test), rustc_diagnostic_item = "hashmap_iter_mut_ty")]
1533pub struct IterMut<'a, K: 'a, V: 'a> {
1534    base: base::IterMut<'a, K, V>,
1535}
1536
1537impl<'a, K, V> IterMut<'a, K, V> {
1538    /// Returns an iterator of references over the remaining items.
1539    #[inline]
1540    pub(super) fn iter(&self) -> Iter<'_, K, V> {
1541        Iter { base: self.base.rustc_iter() }
1542    }
1543}
1544
1545#[stable(feature = "default_iters_hash", since = "1.83.0")]
1546impl<K, V> Default for IterMut<'_, K, V> {
1547    #[inline]
1548    fn default() -> Self {
1549        IterMut { base: Default::default() }
1550    }
1551}
1552
1553/// An owning iterator over the entries of a `HashMap`.
1554///
1555/// This `struct` is created by the [`into_iter`] method on [`HashMap`]
1556/// (provided by the [`IntoIterator`] trait). See its documentation for more.
1557///
1558/// [`into_iter`]: IntoIterator::into_iter
1559///
1560/// # Example
1561///
1562/// ```
1563/// use std::collections::HashMap;
1564///
1565/// let map = HashMap::from([
1566///     ("a", 1),
1567/// ]);
1568/// let iter = map.into_iter();
1569/// ```
1570#[stable(feature = "rust1", since = "1.0.0")]
1571pub struct IntoIter<K, V> {
1572    base: base::IntoIter<K, V>,
1573}
1574
1575impl<K, V> IntoIter<K, V> {
1576    /// Returns an iterator of references over the remaining items.
1577    #[inline]
1578    pub(super) fn iter(&self) -> Iter<'_, K, V> {
1579        Iter { base: self.base.rustc_iter() }
1580    }
1581}
1582
1583#[stable(feature = "default_iters_hash", since = "1.83.0")]
1584impl<K, V> Default for IntoIter<K, V> {
1585    #[inline]
1586    fn default() -> Self {
1587        IntoIter { base: Default::default() }
1588    }
1589}
1590
1591/// An iterator over the keys of a `HashMap`.
1592///
1593/// This `struct` is created by the [`keys`] method on [`HashMap`]. See its
1594/// documentation for more.
1595///
1596/// [`keys`]: HashMap::keys
1597///
1598/// # Example
1599///
1600/// ```
1601/// use std::collections::HashMap;
1602///
1603/// let map = HashMap::from([
1604///     ("a", 1),
1605/// ]);
1606/// let iter_keys = map.keys();
1607/// ```
1608#[stable(feature = "rust1", since = "1.0.0")]
1609#[cfg_attr(not(test), rustc_diagnostic_item = "hashmap_keys_ty")]
1610pub struct Keys<'a, K: 'a, V: 'a> {
1611    inner: Iter<'a, K, V>,
1612}
1613
1614// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
1615#[stable(feature = "rust1", since = "1.0.0")]
1616impl<K, V> Clone for Keys<'_, K, V> {
1617    #[inline]
1618    fn clone(&self) -> Self {
1619        Keys { inner: self.inner.clone() }
1620    }
1621}
1622
1623#[stable(feature = "default_iters_hash", since = "1.83.0")]
1624impl<K, V> Default for Keys<'_, K, V> {
1625    #[inline]
1626    fn default() -> Self {
1627        Keys { inner: Default::default() }
1628    }
1629}
1630
1631#[stable(feature = "std_debug", since = "1.16.0")]
1632impl<K: Debug, V> fmt::Debug for Keys<'_, K, V> {
1633    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1634        f.debug_list().entries(self.clone()).finish()
1635    }
1636}
1637
1638/// An iterator over the values of a `HashMap`.
1639///
1640/// This `struct` is created by the [`values`] method on [`HashMap`]. See its
1641/// documentation for more.
1642///
1643/// [`values`]: HashMap::values
1644///
1645/// # Example
1646///
1647/// ```
1648/// use std::collections::HashMap;
1649///
1650/// let map = HashMap::from([
1651///     ("a", 1),
1652/// ]);
1653/// let iter_values = map.values();
1654/// ```
1655#[stable(feature = "rust1", since = "1.0.0")]
1656#[cfg_attr(not(test), rustc_diagnostic_item = "hashmap_values_ty")]
1657pub struct Values<'a, K: 'a, V: 'a> {
1658    inner: Iter<'a, K, V>,
1659}
1660
1661// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
1662#[stable(feature = "rust1", since = "1.0.0")]
1663impl<K, V> Clone for Values<'_, K, V> {
1664    #[inline]
1665    fn clone(&self) -> Self {
1666        Values { inner: self.inner.clone() }
1667    }
1668}
1669
1670#[stable(feature = "default_iters_hash", since = "1.83.0")]
1671impl<K, V> Default for Values<'_, K, V> {
1672    #[inline]
1673    fn default() -> Self {
1674        Values { inner: Default::default() }
1675    }
1676}
1677
1678#[stable(feature = "std_debug", since = "1.16.0")]
1679impl<K, V: Debug> fmt::Debug for Values<'_, K, V> {
1680    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1681        f.debug_list().entries(self.clone()).finish()
1682    }
1683}
1684
1685/// A draining iterator over the entries of a `HashMap`.
1686///
1687/// This `struct` is created by the [`drain`] method on [`HashMap`]. See its
1688/// documentation for more.
1689///
1690/// [`drain`]: HashMap::drain
1691///
1692/// # Example
1693///
1694/// ```
1695/// use std::collections::HashMap;
1696///
1697/// let mut map = HashMap::from([
1698///     ("a", 1),
1699/// ]);
1700/// let iter = map.drain();
1701/// ```
1702#[stable(feature = "drain", since = "1.6.0")]
1703#[cfg_attr(not(test), rustc_diagnostic_item = "hashmap_drain_ty")]
1704pub struct Drain<'a, K: 'a, V: 'a> {
1705    base: base::Drain<'a, K, V>,
1706}
1707
1708impl<'a, K, V> Drain<'a, K, V> {
1709    /// Returns an iterator of references over the remaining items.
1710    #[inline]
1711    pub(super) fn iter(&self) -> Iter<'_, K, V> {
1712        Iter { base: self.base.rustc_iter() }
1713    }
1714}
1715
1716/// A draining, filtering iterator over the entries of a `HashMap`.
1717///
1718/// This `struct` is created by the [`extract_if`] method on [`HashMap`].
1719///
1720/// [`extract_if`]: HashMap::extract_if
1721///
1722/// # Example
1723///
1724/// ```
1725/// #![feature(hash_extract_if)]
1726///
1727/// use std::collections::HashMap;
1728///
1729/// let mut map = HashMap::from([
1730///     ("a", 1),
1731/// ]);
1732/// let iter = map.extract_if(|_k, v| *v % 2 == 0);
1733/// ```
1734#[unstable(feature = "hash_extract_if", issue = "59618")]
1735#[must_use = "iterators are lazy and do nothing unless consumed"]
1736pub struct ExtractIf<'a, K, V, F>
1737where
1738    F: FnMut(&K, &mut V) -> bool,
1739{
1740    base: base::ExtractIf<'a, K, V, F>,
1741}
1742
1743/// A mutable iterator over the values of a `HashMap`.
1744///
1745/// This `struct` is created by the [`values_mut`] method on [`HashMap`]. See its
1746/// documentation for more.
1747///
1748/// [`values_mut`]: HashMap::values_mut
1749///
1750/// # Example
1751///
1752/// ```
1753/// use std::collections::HashMap;
1754///
1755/// let mut map = HashMap::from([
1756///     ("a", 1),
1757/// ]);
1758/// let iter_values = map.values_mut();
1759/// ```
1760#[stable(feature = "map_values_mut", since = "1.10.0")]
1761#[cfg_attr(not(test), rustc_diagnostic_item = "hashmap_values_mut_ty")]
1762pub struct ValuesMut<'a, K: 'a, V: 'a> {
1763    inner: IterMut<'a, K, V>,
1764}
1765
1766#[stable(feature = "default_iters_hash", since = "1.83.0")]
1767impl<K, V> Default for ValuesMut<'_, K, V> {
1768    #[inline]
1769    fn default() -> Self {
1770        ValuesMut { inner: Default::default() }
1771    }
1772}
1773
1774/// An owning iterator over the keys of a `HashMap`.
1775///
1776/// This `struct` is created by the [`into_keys`] method on [`HashMap`].
1777/// See its documentation for more.
1778///
1779/// [`into_keys`]: HashMap::into_keys
1780///
1781/// # Example
1782///
1783/// ```
1784/// use std::collections::HashMap;
1785///
1786/// let map = HashMap::from([
1787///     ("a", 1),
1788/// ]);
1789/// let iter_keys = map.into_keys();
1790/// ```
1791#[stable(feature = "map_into_keys_values", since = "1.54.0")]
1792pub struct IntoKeys<K, V> {
1793    inner: IntoIter<K, V>,
1794}
1795
1796#[stable(feature = "default_iters_hash", since = "1.83.0")]
1797impl<K, V> Default for IntoKeys<K, V> {
1798    #[inline]
1799    fn default() -> Self {
1800        IntoKeys { inner: Default::default() }
1801    }
1802}
1803
1804/// An owning iterator over the values of a `HashMap`.
1805///
1806/// This `struct` is created by the [`into_values`] method on [`HashMap`].
1807/// See its documentation for more.
1808///
1809/// [`into_values`]: HashMap::into_values
1810///
1811/// # Example
1812///
1813/// ```
1814/// use std::collections::HashMap;
1815///
1816/// let map = HashMap::from([
1817///     ("a", 1),
1818/// ]);
1819/// let iter_keys = map.into_values();
1820/// ```
1821#[stable(feature = "map_into_keys_values", since = "1.54.0")]
1822pub struct IntoValues<K, V> {
1823    inner: IntoIter<K, V>,
1824}
1825
1826#[stable(feature = "default_iters_hash", since = "1.83.0")]
1827impl<K, V> Default for IntoValues<K, V> {
1828    #[inline]
1829    fn default() -> Self {
1830        IntoValues { inner: Default::default() }
1831    }
1832}
1833
1834/// A builder for computing where in a HashMap a key-value pair would be stored.
1835///
1836/// See the [`HashMap::raw_entry_mut`] docs for usage examples.
1837#[unstable(feature = "hash_raw_entry", issue = "56167")]
1838pub struct RawEntryBuilderMut<'a, K: 'a, V: 'a, S: 'a> {
1839    map: &'a mut HashMap<K, V, S>,
1840}
1841
1842/// A view into a single entry in a map, which may either be vacant or occupied.
1843///
1844/// This is a lower-level version of [`Entry`].
1845///
1846/// This `enum` is constructed through the [`raw_entry_mut`] method on [`HashMap`],
1847/// then calling one of the methods of that [`RawEntryBuilderMut`].
1848///
1849/// [`raw_entry_mut`]: HashMap::raw_entry_mut
1850#[unstable(feature = "hash_raw_entry", issue = "56167")]
1851pub enum RawEntryMut<'a, K: 'a, V: 'a, S: 'a> {
1852    /// An occupied entry.
1853    Occupied(RawOccupiedEntryMut<'a, K, V, S>),
1854    /// A vacant entry.
1855    Vacant(RawVacantEntryMut<'a, K, V, S>),
1856}
1857
1858/// A view into an occupied entry in a `HashMap`.
1859/// It is part of the [`RawEntryMut`] enum.
1860#[unstable(feature = "hash_raw_entry", issue = "56167")]
1861pub struct RawOccupiedEntryMut<'a, K: 'a, V: 'a, S: 'a> {
1862    base: base::RawOccupiedEntryMut<'a, K, V, S>,
1863}
1864
1865/// A view into a vacant entry in a `HashMap`.
1866/// It is part of the [`RawEntryMut`] enum.
1867#[unstable(feature = "hash_raw_entry", issue = "56167")]
1868pub struct RawVacantEntryMut<'a, K: 'a, V: 'a, S: 'a> {
1869    base: base::RawVacantEntryMut<'a, K, V, S>,
1870}
1871
1872/// A builder for computing where in a HashMap a key-value pair would be stored.
1873///
1874/// See the [`HashMap::raw_entry`] docs for usage examples.
1875#[unstable(feature = "hash_raw_entry", issue = "56167")]
1876pub struct RawEntryBuilder<'a, K: 'a, V: 'a, S: 'a> {
1877    map: &'a HashMap<K, V, S>,
1878}
1879
1880impl<'a, K, V, S> RawEntryBuilderMut<'a, K, V, S>
1881where
1882    S: BuildHasher,
1883{
1884    /// Creates a `RawEntryMut` from the given key.
1885    #[inline]
1886    #[unstable(feature = "hash_raw_entry", issue = "56167")]
1887    pub fn from_key<Q: ?Sized>(self, k: &Q) -> RawEntryMut<'a, K, V, S>
1888    where
1889        K: Borrow<Q>,
1890        Q: Hash + Eq,
1891    {
1892        map_raw_entry(self.map.base.raw_entry_mut().from_key(k))
1893    }
1894
1895    /// Creates a `RawEntryMut` from the given key and its hash.
1896    #[inline]
1897    #[unstable(feature = "hash_raw_entry", issue = "56167")]
1898    pub fn from_key_hashed_nocheck<Q: ?Sized>(self, hash: u64, k: &Q) -> RawEntryMut<'a, K, V, S>
1899    where
1900        K: Borrow<Q>,
1901        Q: Eq,
1902    {
1903        map_raw_entry(self.map.base.raw_entry_mut().from_key_hashed_nocheck(hash, k))
1904    }
1905
1906    /// Creates a `RawEntryMut` from the given hash.
1907    #[inline]
1908    #[unstable(feature = "hash_raw_entry", issue = "56167")]
1909    pub fn from_hash<F>(self, hash: u64, is_match: F) -> RawEntryMut<'a, K, V, S>
1910    where
1911        for<'b> F: FnMut(&'b K) -> bool,
1912    {
1913        map_raw_entry(self.map.base.raw_entry_mut().from_hash(hash, is_match))
1914    }
1915}
1916
1917impl<'a, K, V, S> RawEntryBuilder<'a, K, V, S>
1918where
1919    S: BuildHasher,
1920{
1921    /// Access an entry by key.
1922    #[inline]
1923    #[unstable(feature = "hash_raw_entry", issue = "56167")]
1924    pub fn from_key<Q: ?Sized>(self, k: &Q) -> Option<(&'a K, &'a V)>
1925    where
1926        K: Borrow<Q>,
1927        Q: Hash + Eq,
1928    {
1929        self.map.base.raw_entry().from_key(k)
1930    }
1931
1932    /// Access an entry by a key and its hash.
1933    #[inline]
1934    #[unstable(feature = "hash_raw_entry", issue = "56167")]
1935    pub fn from_key_hashed_nocheck<Q: ?Sized>(self, hash: u64, k: &Q) -> Option<(&'a K, &'a V)>
1936    where
1937        K: Borrow<Q>,
1938        Q: Hash + Eq,
1939    {
1940        self.map.base.raw_entry().from_key_hashed_nocheck(hash, k)
1941    }
1942
1943    /// Access an entry by hash.
1944    #[inline]
1945    #[unstable(feature = "hash_raw_entry", issue = "56167")]
1946    pub fn from_hash<F>(self, hash: u64, is_match: F) -> Option<(&'a K, &'a V)>
1947    where
1948        F: FnMut(&K) -> bool,
1949    {
1950        self.map.base.raw_entry().from_hash(hash, is_match)
1951    }
1952}
1953
1954impl<'a, K, V, S> RawEntryMut<'a, K, V, S> {
1955    /// Ensures a value is in the entry by inserting the default if empty, and returns
1956    /// mutable references to the key and value in the entry.
1957    ///
1958    /// # Examples
1959    ///
1960    /// ```
1961    /// #![feature(hash_raw_entry)]
1962    /// use std::collections::HashMap;
1963    ///
1964    /// let mut map: HashMap<&str, u32> = HashMap::new();
1965    ///
1966    /// map.raw_entry_mut().from_key("poneyland").or_insert("poneyland", 3);
1967    /// assert_eq!(map["poneyland"], 3);
1968    ///
1969    /// *map.raw_entry_mut().from_key("poneyland").or_insert("poneyland", 10).1 *= 2;
1970    /// assert_eq!(map["poneyland"], 6);
1971    /// ```
1972    #[inline]
1973    #[unstable(feature = "hash_raw_entry", issue = "56167")]
1974    pub fn or_insert(self, default_key: K, default_val: V) -> (&'a mut K, &'a mut V)
1975    where
1976        K: Hash,
1977        S: BuildHasher,
1978    {
1979        match self {
1980            RawEntryMut::Occupied(entry) => entry.into_key_value(),
1981            RawEntryMut::Vacant(entry) => entry.insert(default_key, default_val),
1982        }
1983    }
1984
1985    /// Ensures a value is in the entry by inserting the result of the default function if empty,
1986    /// and returns mutable references to the key and value in the entry.
1987    ///
1988    /// # Examples
1989    ///
1990    /// ```
1991    /// #![feature(hash_raw_entry)]
1992    /// use std::collections::HashMap;
1993    ///
1994    /// let mut map: HashMap<&str, String> = HashMap::new();
1995    ///
1996    /// map.raw_entry_mut().from_key("poneyland").or_insert_with(|| {
1997    ///     ("poneyland", "hoho".to_string())
1998    /// });
1999    ///
2000    /// assert_eq!(map["poneyland"], "hoho".to_string());
2001    /// ```
2002    #[inline]
2003    #[unstable(feature = "hash_raw_entry", issue = "56167")]
2004    pub fn or_insert_with<F>(self, default: F) -> (&'a mut K, &'a mut V)
2005    where
2006        F: FnOnce() -> (K, V),
2007        K: Hash,
2008        S: BuildHasher,
2009    {
2010        match self {
2011            RawEntryMut::Occupied(entry) => entry.into_key_value(),
2012            RawEntryMut::Vacant(entry) => {
2013                let (k, v) = default();
2014                entry.insert(k, v)
2015            }
2016        }
2017    }
2018
2019    /// Provides in-place mutable access to an occupied entry before any
2020    /// potential inserts into the map.
2021    ///
2022    /// # Examples
2023    ///
2024    /// ```
2025    /// #![feature(hash_raw_entry)]
2026    /// use std::collections::HashMap;
2027    ///
2028    /// let mut map: HashMap<&str, u32> = HashMap::new();
2029    ///
2030    /// map.raw_entry_mut()
2031    ///    .from_key("poneyland")
2032    ///    .and_modify(|_k, v| { *v += 1 })
2033    ///    .or_insert("poneyland", 42);
2034    /// assert_eq!(map["poneyland"], 42);
2035    ///
2036    /// map.raw_entry_mut()
2037    ///    .from_key("poneyland")
2038    ///    .and_modify(|_k, v| { *v += 1 })
2039    ///    .or_insert("poneyland", 0);
2040    /// assert_eq!(map["poneyland"], 43);
2041    /// ```
2042    #[inline]
2043    #[unstable(feature = "hash_raw_entry", issue = "56167")]
2044    pub fn and_modify<F>(self, f: F) -> Self
2045    where
2046        F: FnOnce(&mut K, &mut V),
2047    {
2048        match self {
2049            RawEntryMut::Occupied(mut entry) => {
2050                {
2051                    let (k, v) = entry.get_key_value_mut();
2052                    f(k, v);
2053                }
2054                RawEntryMut::Occupied(entry)
2055            }
2056            RawEntryMut::Vacant(entry) => RawEntryMut::Vacant(entry),
2057        }
2058    }
2059}
2060
2061impl<'a, K, V, S> RawOccupiedEntryMut<'a, K, V, S> {
2062    /// Gets a reference to the key in the entry.
2063    #[inline]
2064    #[must_use]
2065    #[unstable(feature = "hash_raw_entry", issue = "56167")]
2066    pub fn key(&self) -> &K {
2067        self.base.key()
2068    }
2069
2070    /// Gets a mutable reference to the key in the entry.
2071    #[inline]
2072    #[must_use]
2073    #[unstable(feature = "hash_raw_entry", issue = "56167")]
2074    pub fn key_mut(&mut self) -> &mut K {
2075        self.base.key_mut()
2076    }
2077
2078    /// Converts the entry into a mutable reference to the key in the entry
2079    /// with a lifetime bound to the map itself.
2080    #[inline]
2081    #[must_use = "`self` will be dropped if the result is not used"]
2082    #[unstable(feature = "hash_raw_entry", issue = "56167")]
2083    pub fn into_key(self) -> &'a mut K {
2084        self.base.into_key()
2085    }
2086
2087    /// Gets a reference to the value in the entry.
2088    #[inline]
2089    #[must_use]
2090    #[unstable(feature = "hash_raw_entry", issue = "56167")]
2091    pub fn get(&self) -> &V {
2092        self.base.get()
2093    }
2094
2095    /// Converts the `OccupiedEntry` into a mutable reference to the value in the entry
2096    /// with a lifetime bound to the map itself.
2097    #[inline]
2098    #[must_use = "`self` will be dropped if the result is not used"]
2099    #[unstable(feature = "hash_raw_entry", issue = "56167")]
2100    pub fn into_mut(self) -> &'a mut V {
2101        self.base.into_mut()
2102    }
2103
2104    /// Gets a mutable reference to the value in the entry.
2105    #[inline]
2106    #[must_use]
2107    #[unstable(feature = "hash_raw_entry", issue = "56167")]
2108    pub fn get_mut(&mut self) -> &mut V {
2109        self.base.get_mut()
2110    }
2111
2112    /// Gets a reference to the key and value in the entry.
2113    #[inline]
2114    #[must_use]
2115    #[unstable(feature = "hash_raw_entry", issue = "56167")]
2116    pub fn get_key_value(&mut self) -> (&K, &V) {
2117        self.base.get_key_value()
2118    }
2119
2120    /// Gets a mutable reference to the key and value in the entry.
2121    #[inline]
2122    #[unstable(feature = "hash_raw_entry", issue = "56167")]
2123    pub fn get_key_value_mut(&mut self) -> (&mut K, &mut V) {
2124        self.base.get_key_value_mut()
2125    }
2126
2127    /// Converts the `OccupiedEntry` into a mutable reference to the key and value in the entry
2128    /// with a lifetime bound to the map itself.
2129    #[inline]
2130    #[must_use = "`self` will be dropped if the result is not used"]
2131    #[unstable(feature = "hash_raw_entry", issue = "56167")]
2132    pub fn into_key_value(self) -> (&'a mut K, &'a mut V) {
2133        self.base.into_key_value()
2134    }
2135
2136    /// Sets the value of the entry, and returns the entry's old value.
2137    #[inline]
2138    #[unstable(feature = "hash_raw_entry", issue = "56167")]
2139    pub fn insert(&mut self, value: V) -> V {
2140        self.base.insert(value)
2141    }
2142
2143    /// Sets the value of the entry, and returns the entry's old value.
2144    #[inline]
2145    #[unstable(feature = "hash_raw_entry", issue = "56167")]
2146    pub fn insert_key(&mut self, key: K) -> K {
2147        self.base.insert_key(key)
2148    }
2149
2150    /// Takes the value out of the entry, and returns it.
2151    #[inline]
2152    #[unstable(feature = "hash_raw_entry", issue = "56167")]
2153    pub fn remove(self) -> V {
2154        self.base.remove()
2155    }
2156
2157    /// Take the ownership of the key and value from the map.
2158    #[inline]
2159    #[unstable(feature = "hash_raw_entry", issue = "56167")]
2160    pub fn remove_entry(self) -> (K, V) {
2161        self.base.remove_entry()
2162    }
2163}
2164
2165impl<'a, K, V, S> RawVacantEntryMut<'a, K, V, S> {
2166    /// Sets the value of the entry with the `VacantEntry`'s key,
2167    /// and returns a mutable reference to it.
2168    #[inline]
2169    #[unstable(feature = "hash_raw_entry", issue = "56167")]
2170    pub fn insert(self, key: K, value: V) -> (&'a mut K, &'a mut V)
2171    where
2172        K: Hash,
2173        S: BuildHasher,
2174    {
2175        self.base.insert(key, value)
2176    }
2177
2178    /// Sets the value of the entry with the VacantEntry's key,
2179    /// and returns a mutable reference to it.
2180    #[inline]
2181    #[unstable(feature = "hash_raw_entry", issue = "56167")]
2182    pub fn insert_hashed_nocheck(self, hash: u64, key: K, value: V) -> (&'a mut K, &'a mut V)
2183    where
2184        K: Hash,
2185        S: BuildHasher,
2186    {
2187        self.base.insert_hashed_nocheck(hash, key, value)
2188    }
2189}
2190
2191#[unstable(feature = "hash_raw_entry", issue = "56167")]
2192impl<K, V, S> Debug for RawEntryBuilderMut<'_, K, V, S> {
2193    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2194        f.debug_struct("RawEntryBuilder").finish_non_exhaustive()
2195    }
2196}
2197
2198#[unstable(feature = "hash_raw_entry", issue = "56167")]
2199impl<K: Debug, V: Debug, S> Debug for RawEntryMut<'_, K, V, S> {
2200    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2201        match *self {
2202            RawEntryMut::Vacant(ref v) => f.debug_tuple("RawEntry").field(v).finish(),
2203            RawEntryMut::Occupied(ref o) => f.debug_tuple("RawEntry").field(o).finish(),
2204        }
2205    }
2206}
2207
2208#[unstable(feature = "hash_raw_entry", issue = "56167")]
2209impl<K: Debug, V: Debug, S> Debug for RawOccupiedEntryMut<'_, K, V, S> {
2210    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2211        f.debug_struct("RawOccupiedEntryMut")
2212            .field("key", self.key())
2213            .field("value", self.get())
2214            .finish_non_exhaustive()
2215    }
2216}
2217
2218#[unstable(feature = "hash_raw_entry", issue = "56167")]
2219impl<K, V, S> Debug for RawVacantEntryMut<'_, K, V, S> {
2220    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2221        f.debug_struct("RawVacantEntryMut").finish_non_exhaustive()
2222    }
2223}
2224
2225#[unstable(feature = "hash_raw_entry", issue = "56167")]
2226impl<K, V, S> Debug for RawEntryBuilder<'_, K, V, S> {
2227    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2228        f.debug_struct("RawEntryBuilder").finish_non_exhaustive()
2229    }
2230}
2231
2232/// A view into a single entry in a map, which may either be vacant or occupied.
2233///
2234/// This `enum` is constructed from the [`entry`] method on [`HashMap`].
2235///
2236/// [`entry`]: HashMap::entry
2237#[stable(feature = "rust1", since = "1.0.0")]
2238#[cfg_attr(not(test), rustc_diagnostic_item = "HashMapEntry")]
2239pub enum Entry<'a, K: 'a, V: 'a> {
2240    /// An occupied entry.
2241    #[stable(feature = "rust1", since = "1.0.0")]
2242    Occupied(#[stable(feature = "rust1", since = "1.0.0")] OccupiedEntry<'a, K, V>),
2243
2244    /// A vacant entry.
2245    #[stable(feature = "rust1", since = "1.0.0")]
2246    Vacant(#[stable(feature = "rust1", since = "1.0.0")] VacantEntry<'a, K, V>),
2247}
2248
2249#[stable(feature = "debug_hash_map", since = "1.12.0")]
2250impl<K: Debug, V: Debug> Debug for Entry<'_, K, V> {
2251    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2252        match *self {
2253            Vacant(ref v) => f.debug_tuple("Entry").field(v).finish(),
2254            Occupied(ref o) => f.debug_tuple("Entry").field(o).finish(),
2255        }
2256    }
2257}
2258
2259/// A view into an occupied entry in a `HashMap`.
2260/// It is part of the [`Entry`] enum.
2261#[stable(feature = "rust1", since = "1.0.0")]
2262pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
2263    base: base::RustcOccupiedEntry<'a, K, V>,
2264}
2265
2266#[stable(feature = "debug_hash_map", since = "1.12.0")]
2267impl<K: Debug, V: Debug> Debug for OccupiedEntry<'_, K, V> {
2268    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2269        f.debug_struct("OccupiedEntry")
2270            .field("key", self.key())
2271            .field("value", self.get())
2272            .finish_non_exhaustive()
2273    }
2274}
2275
2276/// A view into a vacant entry in a `HashMap`.
2277/// It is part of the [`Entry`] enum.
2278#[stable(feature = "rust1", since = "1.0.0")]
2279pub struct VacantEntry<'a, K: 'a, V: 'a> {
2280    base: base::RustcVacantEntry<'a, K, V>,
2281}
2282
2283#[stable(feature = "debug_hash_map", since = "1.12.0")]
2284impl<K: Debug, V> Debug for VacantEntry<'_, K, V> {
2285    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2286        f.debug_tuple("VacantEntry").field(self.key()).finish()
2287    }
2288}
2289
2290/// The error returned by [`try_insert`](HashMap::try_insert) when the key already exists.
2291///
2292/// Contains the occupied entry, and the value that was not inserted.
2293#[unstable(feature = "map_try_insert", issue = "82766")]
2294pub struct OccupiedError<'a, K: 'a, V: 'a> {
2295    /// The entry in the map that was already occupied.
2296    pub entry: OccupiedEntry<'a, K, V>,
2297    /// The value which was not inserted, because the entry was already occupied.
2298    pub value: V,
2299}
2300
2301#[unstable(feature = "map_try_insert", issue = "82766")]
2302impl<K: Debug, V: Debug> Debug for OccupiedError<'_, K, V> {
2303    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2304        f.debug_struct("OccupiedError")
2305            .field("key", self.entry.key())
2306            .field("old_value", self.entry.get())
2307            .field("new_value", &self.value)
2308            .finish_non_exhaustive()
2309    }
2310}
2311
2312#[unstable(feature = "map_try_insert", issue = "82766")]
2313impl<'a, K: Debug, V: Debug> fmt::Display for OccupiedError<'a, K, V> {
2314    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2315        write!(
2316            f,
2317            "failed to insert {:?}, key {:?} already exists with value {:?}",
2318            self.value,
2319            self.entry.key(),
2320            self.entry.get(),
2321        )
2322    }
2323}
2324
2325#[unstable(feature = "map_try_insert", issue = "82766")]
2326impl<'a, K: fmt::Debug, V: fmt::Debug> Error for OccupiedError<'a, K, V> {
2327    #[allow(deprecated)]
2328    fn description(&self) -> &str {
2329        "key already exists"
2330    }
2331}
2332
2333#[stable(feature = "rust1", since = "1.0.0")]
2334impl<'a, K, V, S> IntoIterator for &'a HashMap<K, V, S> {
2335    type Item = (&'a K, &'a V);
2336    type IntoIter = Iter<'a, K, V>;
2337
2338    #[inline]
2339    #[rustc_lint_query_instability]
2340    fn into_iter(self) -> Iter<'a, K, V> {
2341        self.iter()
2342    }
2343}
2344
2345#[stable(feature = "rust1", since = "1.0.0")]
2346impl<'a, K, V, S> IntoIterator for &'a mut HashMap<K, V, S> {
2347    type Item = (&'a K, &'a mut V);
2348    type IntoIter = IterMut<'a, K, V>;
2349
2350    #[inline]
2351    #[rustc_lint_query_instability]
2352    fn into_iter(self) -> IterMut<'a, K, V> {
2353        self.iter_mut()
2354    }
2355}
2356
2357#[stable(feature = "rust1", since = "1.0.0")]
2358impl<K, V, S> IntoIterator for HashMap<K, V, S> {
2359    type Item = (K, V);
2360    type IntoIter = IntoIter<K, V>;
2361
2362    /// Creates a consuming iterator, that is, one that moves each key-value
2363    /// pair out of the map in arbitrary order. The map cannot be used after
2364    /// calling this.
2365    ///
2366    /// # Examples
2367    ///
2368    /// ```
2369    /// use std::collections::HashMap;
2370    ///
2371    /// let map = HashMap::from([
2372    ///     ("a", 1),
2373    ///     ("b", 2),
2374    ///     ("c", 3),
2375    /// ]);
2376    ///
2377    /// // Not possible with .iter()
2378    /// let vec: Vec<(&str, i32)> = map.into_iter().collect();
2379    /// ```
2380    #[inline]
2381    #[rustc_lint_query_instability]
2382    fn into_iter(self) -> IntoIter<K, V> {
2383        IntoIter { base: self.base.into_iter() }
2384    }
2385}
2386
2387#[stable(feature = "rust1", since = "1.0.0")]
2388impl<'a, K, V> Iterator for Iter<'a, K, V> {
2389    type Item = (&'a K, &'a V);
2390
2391    #[inline]
2392    fn next(&mut self) -> Option<(&'a K, &'a V)> {
2393        self.base.next()
2394    }
2395    #[inline]
2396    fn size_hint(&self) -> (usize, Option<usize>) {
2397        self.base.size_hint()
2398    }
2399    #[inline]
2400    fn count(self) -> usize {
2401        self.base.len()
2402    }
2403    #[inline]
2404    fn fold<B, F>(self, init: B, f: F) -> B
2405    where
2406        Self: Sized,
2407        F: FnMut(B, Self::Item) -> B,
2408    {
2409        self.base.fold(init, f)
2410    }
2411}
2412#[stable(feature = "rust1", since = "1.0.0")]
2413impl<K, V> ExactSizeIterator for Iter<'_, K, V> {
2414    #[inline]
2415    fn len(&self) -> usize {
2416        self.base.len()
2417    }
2418}
2419
2420#[stable(feature = "fused", since = "1.26.0")]
2421impl<K, V> FusedIterator for Iter<'_, K, V> {}
2422
2423#[stable(feature = "rust1", since = "1.0.0")]
2424impl<'a, K, V> Iterator for IterMut<'a, K, V> {
2425    type Item = (&'a K, &'a mut V);
2426
2427    #[inline]
2428    fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
2429        self.base.next()
2430    }
2431    #[inline]
2432    fn size_hint(&self) -> (usize, Option<usize>) {
2433        self.base.size_hint()
2434    }
2435    #[inline]
2436    fn count(self) -> usize {
2437        self.base.len()
2438    }
2439    #[inline]
2440    fn fold<B, F>(self, init: B, f: F) -> B
2441    where
2442        Self: Sized,
2443        F: FnMut(B, Self::Item) -> B,
2444    {
2445        self.base.fold(init, f)
2446    }
2447}
2448#[stable(feature = "rust1", since = "1.0.0")]
2449impl<K, V> ExactSizeIterator for IterMut<'_, K, V> {
2450    #[inline]
2451    fn len(&self) -> usize {
2452        self.base.len()
2453    }
2454}
2455#[stable(feature = "fused", since = "1.26.0")]
2456impl<K, V> FusedIterator for IterMut<'_, K, V> {}
2457
2458#[stable(feature = "std_debug", since = "1.16.0")]
2459impl<K, V> fmt::Debug for IterMut<'_, K, V>
2460where
2461    K: fmt::Debug,
2462    V: fmt::Debug,
2463{
2464    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2465        f.debug_list().entries(self.iter()).finish()
2466    }
2467}
2468
2469#[stable(feature = "rust1", since = "1.0.0")]
2470impl<K, V> Iterator for IntoIter<K, V> {
2471    type Item = (K, V);
2472
2473    #[inline]
2474    fn next(&mut self) -> Option<(K, V)> {
2475        self.base.next()
2476    }
2477    #[inline]
2478    fn size_hint(&self) -> (usize, Option<usize>) {
2479        self.base.size_hint()
2480    }
2481    #[inline]
2482    fn count(self) -> usize {
2483        self.base.len()
2484    }
2485    #[inline]
2486    fn fold<B, F>(self, init: B, f: F) -> B
2487    where
2488        Self: Sized,
2489        F: FnMut(B, Self::Item) -> B,
2490    {
2491        self.base.fold(init, f)
2492    }
2493}
2494#[stable(feature = "rust1", since = "1.0.0")]
2495impl<K, V> ExactSizeIterator for IntoIter<K, V> {
2496    #[inline]
2497    fn len(&self) -> usize {
2498        self.base.len()
2499    }
2500}
2501#[stable(feature = "fused", since = "1.26.0")]
2502impl<K, V> FusedIterator for IntoIter<K, V> {}
2503
2504#[stable(feature = "std_debug", since = "1.16.0")]
2505impl<K: Debug, V: Debug> fmt::Debug for IntoIter<K, V> {
2506    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2507        f.debug_list().entries(self.iter()).finish()
2508    }
2509}
2510
2511#[stable(feature = "rust1", since = "1.0.0")]
2512impl<'a, K, V> Iterator for Keys<'a, K, V> {
2513    type Item = &'a K;
2514
2515    #[inline]
2516    fn next(&mut self) -> Option<&'a K> {
2517        self.inner.next().map(|(k, _)| k)
2518    }
2519    #[inline]
2520    fn size_hint(&self) -> (usize, Option<usize>) {
2521        self.inner.size_hint()
2522    }
2523    #[inline]
2524    fn count(self) -> usize {
2525        self.inner.len()
2526    }
2527    #[inline]
2528    fn fold<B, F>(self, init: B, mut f: F) -> B
2529    where
2530        Self: Sized,
2531        F: FnMut(B, Self::Item) -> B,
2532    {
2533        self.inner.fold(init, |acc, (k, _)| f(acc, k))
2534    }
2535}
2536#[stable(feature = "rust1", since = "1.0.0")]
2537impl<K, V> ExactSizeIterator for Keys<'_, K, V> {
2538    #[inline]
2539    fn len(&self) -> usize {
2540        self.inner.len()
2541    }
2542}
2543#[stable(feature = "fused", since = "1.26.0")]
2544impl<K, V> FusedIterator for Keys<'_, K, V> {}
2545
2546#[stable(feature = "rust1", since = "1.0.0")]
2547impl<'a, K, V> Iterator for Values<'a, K, V> {
2548    type Item = &'a V;
2549
2550    #[inline]
2551    fn next(&mut self) -> Option<&'a V> {
2552        self.inner.next().map(|(_, v)| v)
2553    }
2554    #[inline]
2555    fn size_hint(&self) -> (usize, Option<usize>) {
2556        self.inner.size_hint()
2557    }
2558    #[inline]
2559    fn count(self) -> usize {
2560        self.inner.len()
2561    }
2562    #[inline]
2563    fn fold<B, F>(self, init: B, mut f: F) -> B
2564    where
2565        Self: Sized,
2566        F: FnMut(B, Self::Item) -> B,
2567    {
2568        self.inner.fold(init, |acc, (_, v)| f(acc, v))
2569    }
2570}
2571#[stable(feature = "rust1", since = "1.0.0")]
2572impl<K, V> ExactSizeIterator for Values<'_, K, V> {
2573    #[inline]
2574    fn len(&self) -> usize {
2575        self.inner.len()
2576    }
2577}
2578#[stable(feature = "fused", since = "1.26.0")]
2579impl<K, V> FusedIterator for Values<'_, K, V> {}
2580
2581#[stable(feature = "map_values_mut", since = "1.10.0")]
2582impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
2583    type Item = &'a mut V;
2584
2585    #[inline]
2586    fn next(&mut self) -> Option<&'a mut V> {
2587        self.inner.next().map(|(_, v)| v)
2588    }
2589    #[inline]
2590    fn size_hint(&self) -> (usize, Option<usize>) {
2591        self.inner.size_hint()
2592    }
2593    #[inline]
2594    fn count(self) -> usize {
2595        self.inner.len()
2596    }
2597    #[inline]
2598    fn fold<B, F>(self, init: B, mut f: F) -> B
2599    where
2600        Self: Sized,
2601        F: FnMut(B, Self::Item) -> B,
2602    {
2603        self.inner.fold(init, |acc, (_, v)| f(acc, v))
2604    }
2605}
2606#[stable(feature = "map_values_mut", since = "1.10.0")]
2607impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> {
2608    #[inline]
2609    fn len(&self) -> usize {
2610        self.inner.len()
2611    }
2612}
2613#[stable(feature = "fused", since = "1.26.0")]
2614impl<K, V> FusedIterator for ValuesMut<'_, K, V> {}
2615
2616#[stable(feature = "std_debug", since = "1.16.0")]
2617impl<K, V: fmt::Debug> fmt::Debug for ValuesMut<'_, K, V> {
2618    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2619        f.debug_list().entries(self.inner.iter().map(|(_, val)| val)).finish()
2620    }
2621}
2622
2623#[stable(feature = "map_into_keys_values", since = "1.54.0")]
2624impl<K, V> Iterator for IntoKeys<K, V> {
2625    type Item = K;
2626
2627    #[inline]
2628    fn next(&mut self) -> Option<K> {
2629        self.inner.next().map(|(k, _)| k)
2630    }
2631    #[inline]
2632    fn size_hint(&self) -> (usize, Option<usize>) {
2633        self.inner.size_hint()
2634    }
2635    #[inline]
2636    fn count(self) -> usize {
2637        self.inner.len()
2638    }
2639    #[inline]
2640    fn fold<B, F>(self, init: B, mut f: F) -> B
2641    where
2642        Self: Sized,
2643        F: FnMut(B, Self::Item) -> B,
2644    {
2645        self.inner.fold(init, |acc, (k, _)| f(acc, k))
2646    }
2647}
2648#[stable(feature = "map_into_keys_values", since = "1.54.0")]
2649impl<K, V> ExactSizeIterator for IntoKeys<K, V> {
2650    #[inline]
2651    fn len(&self) -> usize {
2652        self.inner.len()
2653    }
2654}
2655#[stable(feature = "map_into_keys_values", since = "1.54.0")]
2656impl<K, V> FusedIterator for IntoKeys<K, V> {}
2657
2658#[stable(feature = "map_into_keys_values", since = "1.54.0")]
2659impl<K: Debug, V> fmt::Debug for IntoKeys<K, V> {
2660    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2661        f.debug_list().entries(self.inner.iter().map(|(k, _)| k)).finish()
2662    }
2663}
2664
2665#[stable(feature = "map_into_keys_values", since = "1.54.0")]
2666impl<K, V> Iterator for IntoValues<K, V> {
2667    type Item = V;
2668
2669    #[inline]
2670    fn next(&mut self) -> Option<V> {
2671        self.inner.next().map(|(_, v)| v)
2672    }
2673    #[inline]
2674    fn size_hint(&self) -> (usize, Option<usize>) {
2675        self.inner.size_hint()
2676    }
2677    #[inline]
2678    fn count(self) -> usize {
2679        self.inner.len()
2680    }
2681    #[inline]
2682    fn fold<B, F>(self, init: B, mut f: F) -> B
2683    where
2684        Self: Sized,
2685        F: FnMut(B, Self::Item) -> B,
2686    {
2687        self.inner.fold(init, |acc, (_, v)| f(acc, v))
2688    }
2689}
2690#[stable(feature = "map_into_keys_values", since = "1.54.0")]
2691impl<K, V> ExactSizeIterator for IntoValues<K, V> {
2692    #[inline]
2693    fn len(&self) -> usize {
2694        self.inner.len()
2695    }
2696}
2697#[stable(feature = "map_into_keys_values", since = "1.54.0")]
2698impl<K, V> FusedIterator for IntoValues<K, V> {}
2699
2700#[stable(feature = "map_into_keys_values", since = "1.54.0")]
2701impl<K, V: Debug> fmt::Debug for IntoValues<K, V> {
2702    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2703        f.debug_list().entries(self.inner.iter().map(|(_, v)| v)).finish()
2704    }
2705}
2706
2707#[stable(feature = "drain", since = "1.6.0")]
2708impl<'a, K, V> Iterator for Drain<'a, K, V> {
2709    type Item = (K, V);
2710
2711    #[inline]
2712    fn next(&mut self) -> Option<(K, V)> {
2713        self.base.next()
2714    }
2715    #[inline]
2716    fn size_hint(&self) -> (usize, Option<usize>) {
2717        self.base.size_hint()
2718    }
2719    #[inline]
2720    fn fold<B, F>(self, init: B, f: F) -> B
2721    where
2722        Self: Sized,
2723        F: FnMut(B, Self::Item) -> B,
2724    {
2725        self.base.fold(init, f)
2726    }
2727}
2728#[stable(feature = "drain", since = "1.6.0")]
2729impl<K, V> ExactSizeIterator for Drain<'_, K, V> {
2730    #[inline]
2731    fn len(&self) -> usize {
2732        self.base.len()
2733    }
2734}
2735#[stable(feature = "fused", since = "1.26.0")]
2736impl<K, V> FusedIterator for Drain<'_, K, V> {}
2737
2738#[stable(feature = "std_debug", since = "1.16.0")]
2739impl<K, V> fmt::Debug for Drain<'_, K, V>
2740where
2741    K: fmt::Debug,
2742    V: fmt::Debug,
2743{
2744    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2745        f.debug_list().entries(self.iter()).finish()
2746    }
2747}
2748
2749#[unstable(feature = "hash_extract_if", issue = "59618")]
2750impl<K, V, F> Iterator for ExtractIf<'_, K, V, F>
2751where
2752    F: FnMut(&K, &mut V) -> bool,
2753{
2754    type Item = (K, V);
2755
2756    #[inline]
2757    fn next(&mut self) -> Option<(K, V)> {
2758        self.base.next()
2759    }
2760    #[inline]
2761    fn size_hint(&self) -> (usize, Option<usize>) {
2762        self.base.size_hint()
2763    }
2764}
2765
2766#[unstable(feature = "hash_extract_if", issue = "59618")]
2767impl<K, V, F> FusedIterator for ExtractIf<'_, K, V, F> where F: FnMut(&K, &mut V) -> bool {}
2768
2769#[unstable(feature = "hash_extract_if", issue = "59618")]
2770impl<'a, K, V, F> fmt::Debug for ExtractIf<'a, K, V, F>
2771where
2772    F: FnMut(&K, &mut V) -> bool,
2773{
2774    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2775        f.debug_struct("ExtractIf").finish_non_exhaustive()
2776    }
2777}
2778
2779impl<'a, K, V> Entry<'a, K, V> {
2780    /// Ensures a value is in the entry by inserting the default if empty, and returns
2781    /// a mutable reference to the value in the entry.
2782    ///
2783    /// # Examples
2784    ///
2785    /// ```
2786    /// use std::collections::HashMap;
2787    ///
2788    /// let mut map: HashMap<&str, u32> = HashMap::new();
2789    ///
2790    /// map.entry("poneyland").or_insert(3);
2791    /// assert_eq!(map["poneyland"], 3);
2792    ///
2793    /// *map.entry("poneyland").or_insert(10) *= 2;
2794    /// assert_eq!(map["poneyland"], 6);
2795    /// ```
2796    #[inline]
2797    #[stable(feature = "rust1", since = "1.0.0")]
2798    pub fn or_insert(self, default: V) -> &'a mut V {
2799        match self {
2800            Occupied(entry) => entry.into_mut(),
2801            Vacant(entry) => entry.insert(default),
2802        }
2803    }
2804
2805    /// Ensures a value is in the entry by inserting the result of the default function if empty,
2806    /// and returns a mutable reference to the value in the entry.
2807    ///
2808    /// # Examples
2809    ///
2810    /// ```
2811    /// use std::collections::HashMap;
2812    ///
2813    /// let mut map = HashMap::new();
2814    /// let value = "hoho";
2815    ///
2816    /// map.entry("poneyland").or_insert_with(|| value);
2817    ///
2818    /// assert_eq!(map["poneyland"], "hoho");
2819    /// ```
2820    #[inline]
2821    #[stable(feature = "rust1", since = "1.0.0")]
2822    pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
2823        match self {
2824            Occupied(entry) => entry.into_mut(),
2825            Vacant(entry) => entry.insert(default()),
2826        }
2827    }
2828
2829    /// Ensures a value is in the entry by inserting, if empty, the result of the default function.
2830    /// This method allows for generating key-derived values for insertion by providing the default
2831    /// function a reference to the key that was moved during the `.entry(key)` method call.
2832    ///
2833    /// The reference to the moved key is provided so that cloning or copying the key is
2834    /// unnecessary, unlike with `.or_insert_with(|| ... )`.
2835    ///
2836    /// # Examples
2837    ///
2838    /// ```
2839    /// use std::collections::HashMap;
2840    ///
2841    /// let mut map: HashMap<&str, usize> = HashMap::new();
2842    ///
2843    /// map.entry("poneyland").or_insert_with_key(|key| key.chars().count());
2844    ///
2845    /// assert_eq!(map["poneyland"], 9);
2846    /// ```
2847    #[inline]
2848    #[stable(feature = "or_insert_with_key", since = "1.50.0")]
2849    pub fn or_insert_with_key<F: FnOnce(&K) -> V>(self, default: F) -> &'a mut V {
2850        match self {
2851            Occupied(entry) => entry.into_mut(),
2852            Vacant(entry) => {
2853                let value = default(entry.key());
2854                entry.insert(value)
2855            }
2856        }
2857    }
2858
2859    /// Returns a reference to this entry's key.
2860    ///
2861    /// # Examples
2862    ///
2863    /// ```
2864    /// use std::collections::HashMap;
2865    ///
2866    /// let mut map: HashMap<&str, u32> = HashMap::new();
2867    /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
2868    /// ```
2869    #[inline]
2870    #[stable(feature = "map_entry_keys", since = "1.10.0")]
2871    pub fn key(&self) -> &K {
2872        match *self {
2873            Occupied(ref entry) => entry.key(),
2874            Vacant(ref entry) => entry.key(),
2875        }
2876    }
2877
2878    /// Provides in-place mutable access to an occupied entry before any
2879    /// potential inserts into the map.
2880    ///
2881    /// # Examples
2882    ///
2883    /// ```
2884    /// use std::collections::HashMap;
2885    ///
2886    /// let mut map: HashMap<&str, u32> = HashMap::new();
2887    ///
2888    /// map.entry("poneyland")
2889    ///    .and_modify(|e| { *e += 1 })
2890    ///    .or_insert(42);
2891    /// assert_eq!(map["poneyland"], 42);
2892    ///
2893    /// map.entry("poneyland")
2894    ///    .and_modify(|e| { *e += 1 })
2895    ///    .or_insert(42);
2896    /// assert_eq!(map["poneyland"], 43);
2897    /// ```
2898    #[inline]
2899    #[stable(feature = "entry_and_modify", since = "1.26.0")]
2900    pub fn and_modify<F>(self, f: F) -> Self
2901    where
2902        F: FnOnce(&mut V),
2903    {
2904        match self {
2905            Occupied(mut entry) => {
2906                f(entry.get_mut());
2907                Occupied(entry)
2908            }
2909            Vacant(entry) => Vacant(entry),
2910        }
2911    }
2912
2913    /// Sets the value of the entry, and returns an `OccupiedEntry`.
2914    ///
2915    /// # Examples
2916    ///
2917    /// ```
2918    /// use std::collections::HashMap;
2919    ///
2920    /// let mut map: HashMap<&str, String> = HashMap::new();
2921    /// let entry = map.entry("poneyland").insert_entry("hoho".to_string());
2922    ///
2923    /// assert_eq!(entry.key(), &"poneyland");
2924    /// ```
2925    #[inline]
2926    #[stable(feature = "entry_insert", since = "1.83.0")]
2927    pub fn insert_entry(self, value: V) -> OccupiedEntry<'a, K, V> {
2928        match self {
2929            Occupied(mut entry) => {
2930                entry.insert(value);
2931                entry
2932            }
2933            Vacant(entry) => entry.insert_entry(value),
2934        }
2935    }
2936}
2937
2938impl<'a, K, V: Default> Entry<'a, K, V> {
2939    /// Ensures a value is in the entry by inserting the default value if empty,
2940    /// and returns a mutable reference to the value in the entry.
2941    ///
2942    /// # Examples
2943    ///
2944    /// ```
2945    /// # fn main() {
2946    /// use std::collections::HashMap;
2947    ///
2948    /// let mut map: HashMap<&str, Option<u32>> = HashMap::new();
2949    /// map.entry("poneyland").or_default();
2950    ///
2951    /// assert_eq!(map["poneyland"], None);
2952    /// # }
2953    /// ```
2954    #[inline]
2955    #[stable(feature = "entry_or_default", since = "1.28.0")]
2956    pub fn or_default(self) -> &'a mut V {
2957        match self {
2958            Occupied(entry) => entry.into_mut(),
2959            Vacant(entry) => entry.insert(Default::default()),
2960        }
2961    }
2962}
2963
2964impl<'a, K, V> OccupiedEntry<'a, K, V> {
2965    /// Gets a reference to the key in the entry.
2966    ///
2967    /// # Examples
2968    ///
2969    /// ```
2970    /// use std::collections::HashMap;
2971    ///
2972    /// let mut map: HashMap<&str, u32> = HashMap::new();
2973    /// map.entry("poneyland").or_insert(12);
2974    /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
2975    /// ```
2976    #[inline]
2977    #[stable(feature = "map_entry_keys", since = "1.10.0")]
2978    pub fn key(&self) -> &K {
2979        self.base.key()
2980    }
2981
2982    /// Take the ownership of the key and value from the map.
2983    ///
2984    /// # Examples
2985    ///
2986    /// ```
2987    /// use std::collections::HashMap;
2988    /// use std::collections::hash_map::Entry;
2989    ///
2990    /// let mut map: HashMap<&str, u32> = HashMap::new();
2991    /// map.entry("poneyland").or_insert(12);
2992    ///
2993    /// if let Entry::Occupied(o) = map.entry("poneyland") {
2994    ///     // We delete the entry from the map.
2995    ///     o.remove_entry();
2996    /// }
2997    ///
2998    /// assert_eq!(map.contains_key("poneyland"), false);
2999    /// ```
3000    #[inline]
3001    #[stable(feature = "map_entry_recover_keys2", since = "1.12.0")]
3002    pub fn remove_entry(self) -> (K, V) {
3003        self.base.remove_entry()
3004    }
3005
3006    /// Gets a reference to the value in the entry.
3007    ///
3008    /// # Examples
3009    ///
3010    /// ```
3011    /// use std::collections::HashMap;
3012    /// use std::collections::hash_map::Entry;
3013    ///
3014    /// let mut map: HashMap<&str, u32> = HashMap::new();
3015    /// map.entry("poneyland").or_insert(12);
3016    ///
3017    /// if let Entry::Occupied(o) = map.entry("poneyland") {
3018    ///     assert_eq!(o.get(), &12);
3019    /// }
3020    /// ```
3021    #[inline]
3022    #[stable(feature = "rust1", since = "1.0.0")]
3023    pub fn get(&self) -> &V {
3024        self.base.get()
3025    }
3026
3027    /// Gets a mutable reference to the value in the entry.
3028    ///
3029    /// If you need a reference to the `OccupiedEntry` which may outlive the
3030    /// destruction of the `Entry` value, see [`into_mut`].
3031    ///
3032    /// [`into_mut`]: Self::into_mut
3033    ///
3034    /// # Examples
3035    ///
3036    /// ```
3037    /// use std::collections::HashMap;
3038    /// use std::collections::hash_map::Entry;
3039    ///
3040    /// let mut map: HashMap<&str, u32> = HashMap::new();
3041    /// map.entry("poneyland").or_insert(12);
3042    ///
3043    /// assert_eq!(map["poneyland"], 12);
3044    /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
3045    ///     *o.get_mut() += 10;
3046    ///     assert_eq!(*o.get(), 22);
3047    ///
3048    ///     // We can use the same Entry multiple times.
3049    ///     *o.get_mut() += 2;
3050    /// }
3051    ///
3052    /// assert_eq!(map["poneyland"], 24);
3053    /// ```
3054    #[inline]
3055    #[stable(feature = "rust1", since = "1.0.0")]
3056    pub fn get_mut(&mut self) -> &mut V {
3057        self.base.get_mut()
3058    }
3059
3060    /// Converts the `OccupiedEntry` into a mutable reference to the value in the entry
3061    /// with a lifetime bound to the map itself.
3062    ///
3063    /// If you need multiple references to the `OccupiedEntry`, see [`get_mut`].
3064    ///
3065    /// [`get_mut`]: Self::get_mut
3066    ///
3067    /// # Examples
3068    ///
3069    /// ```
3070    /// use std::collections::HashMap;
3071    /// use std::collections::hash_map::Entry;
3072    ///
3073    /// let mut map: HashMap<&str, u32> = HashMap::new();
3074    /// map.entry("poneyland").or_insert(12);
3075    ///
3076    /// assert_eq!(map["poneyland"], 12);
3077    /// if let Entry::Occupied(o) = map.entry("poneyland") {
3078    ///     *o.into_mut() += 10;
3079    /// }
3080    ///
3081    /// assert_eq!(map["poneyland"], 22);
3082    /// ```
3083    #[inline]
3084    #[stable(feature = "rust1", since = "1.0.0")]
3085    pub fn into_mut(self) -> &'a mut V {
3086        self.base.into_mut()
3087    }
3088
3089    /// Sets the value of the entry, and returns the entry's old value.
3090    ///
3091    /// # Examples
3092    ///
3093    /// ```
3094    /// use std::collections::HashMap;
3095    /// use std::collections::hash_map::Entry;
3096    ///
3097    /// let mut map: HashMap<&str, u32> = HashMap::new();
3098    /// map.entry("poneyland").or_insert(12);
3099    ///
3100    /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
3101    ///     assert_eq!(o.insert(15), 12);
3102    /// }
3103    ///
3104    /// assert_eq!(map["poneyland"], 15);
3105    /// ```
3106    #[inline]
3107    #[stable(feature = "rust1", since = "1.0.0")]
3108    pub fn insert(&mut self, value: V) -> V {
3109        self.base.insert(value)
3110    }
3111
3112    /// Takes the value out of the entry, and returns it.
3113    ///
3114    /// # Examples
3115    ///
3116    /// ```
3117    /// use std::collections::HashMap;
3118    /// use std::collections::hash_map::Entry;
3119    ///
3120    /// let mut map: HashMap<&str, u32> = HashMap::new();
3121    /// map.entry("poneyland").or_insert(12);
3122    ///
3123    /// if let Entry::Occupied(o) = map.entry("poneyland") {
3124    ///     assert_eq!(o.remove(), 12);
3125    /// }
3126    ///
3127    /// assert_eq!(map.contains_key("poneyland"), false);
3128    /// ```
3129    #[inline]
3130    #[stable(feature = "rust1", since = "1.0.0")]
3131    pub fn remove(self) -> V {
3132        self.base.remove()
3133    }
3134}
3135
3136impl<'a, K: 'a, V: 'a> VacantEntry<'a, K, V> {
3137    /// Gets a reference to the key that would be used when inserting a value
3138    /// through the `VacantEntry`.
3139    ///
3140    /// # Examples
3141    ///
3142    /// ```
3143    /// use std::collections::HashMap;
3144    ///
3145    /// let mut map: HashMap<&str, u32> = HashMap::new();
3146    /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
3147    /// ```
3148    #[inline]
3149    #[stable(feature = "map_entry_keys", since = "1.10.0")]
3150    pub fn key(&self) -> &K {
3151        self.base.key()
3152    }
3153
3154    /// Take ownership of the key.
3155    ///
3156    /// # Examples
3157    ///
3158    /// ```
3159    /// use std::collections::HashMap;
3160    /// use std::collections::hash_map::Entry;
3161    ///
3162    /// let mut map: HashMap<&str, u32> = HashMap::new();
3163    ///
3164    /// if let Entry::Vacant(v) = map.entry("poneyland") {
3165    ///     v.into_key();
3166    /// }
3167    /// ```
3168    #[inline]
3169    #[stable(feature = "map_entry_recover_keys2", since = "1.12.0")]
3170    pub fn into_key(self) -> K {
3171        self.base.into_key()
3172    }
3173
3174    /// Sets the value of the entry with the `VacantEntry`'s key,
3175    /// and returns a mutable reference to it.
3176    ///
3177    /// # Examples
3178    ///
3179    /// ```
3180    /// use std::collections::HashMap;
3181    /// use std::collections::hash_map::Entry;
3182    ///
3183    /// let mut map: HashMap<&str, u32> = HashMap::new();
3184    ///
3185    /// if let Entry::Vacant(o) = map.entry("poneyland") {
3186    ///     o.insert(37);
3187    /// }
3188    /// assert_eq!(map["poneyland"], 37);
3189    /// ```
3190    #[inline]
3191    #[stable(feature = "rust1", since = "1.0.0")]
3192    pub fn insert(self, value: V) -> &'a mut V {
3193        self.base.insert(value)
3194    }
3195
3196    /// Sets the value of the entry with the `VacantEntry`'s key,
3197    /// and returns an `OccupiedEntry`.
3198    ///
3199    /// # Examples
3200    ///
3201    /// ```
3202    /// use std::collections::HashMap;
3203    /// use std::collections::hash_map::Entry;
3204    ///
3205    /// let mut map: HashMap<&str, u32> = HashMap::new();
3206    ///
3207    /// if let Entry::Vacant(o) = map.entry("poneyland") {
3208    ///     o.insert_entry(37);
3209    /// }
3210    /// assert_eq!(map["poneyland"], 37);
3211    /// ```
3212    #[inline]
3213    #[stable(feature = "entry_insert", since = "1.83.0")]
3214    pub fn insert_entry(self, value: V) -> OccupiedEntry<'a, K, V> {
3215        let base = self.base.insert_entry(value);
3216        OccupiedEntry { base }
3217    }
3218}
3219
3220#[stable(feature = "rust1", since = "1.0.0")]
3221impl<K, V, S> FromIterator<(K, V)> for HashMap<K, V, S>
3222where
3223    K: Eq + Hash,
3224    S: BuildHasher + Default,
3225{
3226    /// Constructs a `HashMap<K, V>` from an iterator of key-value pairs.
3227    ///
3228    /// If the iterator produces any pairs with equal keys,
3229    /// all but one of the corresponding values will be dropped.
3230    fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> HashMap<K, V, S> {
3231        let mut map = HashMap::with_hasher(Default::default());
3232        map.extend(iter);
3233        map
3234    }
3235}
3236
3237/// Inserts all new key-values from the iterator and replaces values with existing
3238/// keys with new values returned from the iterator.
3239#[stable(feature = "rust1", since = "1.0.0")]
3240impl<K, V, S> Extend<(K, V)> for HashMap<K, V, S>
3241where
3242    K: Eq + Hash,
3243    S: BuildHasher,
3244{
3245    #[inline]
3246    fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
3247        self.base.extend(iter)
3248    }
3249
3250    #[inline]
3251    fn extend_one(&mut self, (k, v): (K, V)) {
3252        self.base.insert(k, v);
3253    }
3254
3255    #[inline]
3256    fn extend_reserve(&mut self, additional: usize) {
3257        self.base.extend_reserve(additional);
3258    }
3259}
3260
3261#[stable(feature = "hash_extend_copy", since = "1.4.0")]
3262impl<'a, K, V, S> Extend<(&'a K, &'a V)> for HashMap<K, V, S>
3263where
3264    K: Eq + Hash + Copy,
3265    V: Copy,
3266    S: BuildHasher,
3267{
3268    #[inline]
3269    fn extend<T: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: T) {
3270        self.base.extend(iter)
3271    }
3272
3273    #[inline]
3274    fn extend_one(&mut self, (&k, &v): (&'a K, &'a V)) {
3275        self.base.insert(k, v);
3276    }
3277
3278    #[inline]
3279    fn extend_reserve(&mut self, additional: usize) {
3280        Extend::<(K, V)>::extend_reserve(self, additional)
3281    }
3282}
3283
3284#[inline]
3285fn map_entry<'a, K: 'a, V: 'a>(raw: base::RustcEntry<'a, K, V>) -> Entry<'a, K, V> {
3286    match raw {
3287        base::RustcEntry::Occupied(base) => Entry::Occupied(OccupiedEntry { base }),
3288        base::RustcEntry::Vacant(base) => Entry::Vacant(VacantEntry { base }),
3289    }
3290}
3291
3292#[inline]
3293pub(super) fn map_try_reserve_error(err: hashbrown::TryReserveError) -> TryReserveError {
3294    match err {
3295        hashbrown::TryReserveError::CapacityOverflow => {
3296            TryReserveErrorKind::CapacityOverflow.into()
3297        }
3298        hashbrown::TryReserveError::AllocError { layout } => {
3299            TryReserveErrorKind::AllocError { layout, non_exhaustive: () }.into()
3300        }
3301    }
3302}
3303
3304#[inline]
3305fn map_raw_entry<'a, K: 'a, V: 'a, S: 'a>(
3306    raw: base::RawEntryMut<'a, K, V, S>,
3307) -> RawEntryMut<'a, K, V, S> {
3308    match raw {
3309        base::RawEntryMut::Occupied(base) => RawEntryMut::Occupied(RawOccupiedEntryMut { base }),
3310        base::RawEntryMut::Vacant(base) => RawEntryMut::Vacant(RawVacantEntryMut { base }),
3311    }
3312}
3313
3314#[allow(dead_code)]
3315fn assert_covariance() {
3316    fn map_key<'new>(v: HashMap<&'static str, u8>) -> HashMap<&'new str, u8> {
3317        v
3318    }
3319    fn map_val<'new>(v: HashMap<u8, &'static str>) -> HashMap<u8, &'new str> {
3320        v
3321    }
3322    fn iter_key<'a, 'new>(v: Iter<'a, &'static str, u8>) -> Iter<'a, &'new str, u8> {
3323        v
3324    }
3325    fn iter_val<'a, 'new>(v: Iter<'a, u8, &'static str>) -> Iter<'a, u8, &'new str> {
3326        v
3327    }
3328    fn into_iter_key<'new>(v: IntoIter<&'static str, u8>) -> IntoIter<&'new str, u8> {
3329        v
3330    }
3331    fn into_iter_val<'new>(v: IntoIter<u8, &'static str>) -> IntoIter<u8, &'new str> {
3332        v
3333    }
3334    fn keys_key<'a, 'new>(v: Keys<'a, &'static str, u8>) -> Keys<'a, &'new str, u8> {
3335        v
3336    }
3337    fn keys_val<'a, 'new>(v: Keys<'a, u8, &'static str>) -> Keys<'a, u8, &'new str> {
3338        v
3339    }
3340    fn values_key<'a, 'new>(v: Values<'a, &'static str, u8>) -> Values<'a, &'new str, u8> {
3341        v
3342    }
3343    fn values_val<'a, 'new>(v: Values<'a, u8, &'static str>) -> Values<'a, u8, &'new str> {
3344        v
3345    }
3346    fn drain<'new>(
3347        d: Drain<'static, &'static str, &'static str>,
3348    ) -> Drain<'new, &'new str, &'new str> {
3349        d
3350    }
3351}