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}