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` normally cannot be used in a `const` or `static` initializer.
212///
213/// However, if you need to use a `HashMap` in a `const` or `static` initializer while retaining
214/// random seed generation, you can wrap the `HashMap` in [`LazyLock`].
215///
216/// Alternatively, you can construct a `HashMap` in a `const` or `static` initializer using a different
217/// hasher that does not rely on a random seed. **Be aware that a `HashMap` created this way is not
218/// resistant to HashDoS attacks!**
219///
220/// [`LazyLock`]: crate::sync::LazyLock
221/// ```rust
222/// use std::collections::HashMap;
223/// use std::hash::{BuildHasherDefault, DefaultHasher};
224/// use std::sync::{LazyLock, Mutex};
225///
226/// // HashMaps with a fixed, non-random hasher
227/// const NONRANDOM_EMPTY_MAP: HashMap<String, Vec<i32>, BuildHasherDefault<DefaultHasher>> =
228/// HashMap::with_hasher(BuildHasherDefault::new());
229/// static NONRANDOM_MAP: Mutex<HashMap<String, Vec<i32>, BuildHasherDefault<DefaultHasher>>> =
230/// Mutex::new(HashMap::with_hasher(BuildHasherDefault::new()));
231///
232/// // HashMaps using LazyLock to retain random seeding
233/// const RANDOM_EMPTY_MAP: LazyLock<HashMap<String, Vec<i32>>> =
234/// LazyLock::new(HashMap::new);
235/// static RANDOM_MAP: LazyLock<Mutex<HashMap<String, Vec<i32>>>> =
236/// LazyLock::new(|| Mutex::new(HashMap::new()));
237/// ```
238
239#[cfg_attr(not(test), rustc_diagnostic_item = "HashMap")]
240#[stable(feature = "rust1", since = "1.0.0")]
241#[rustc_insignificant_dtor]
242pub struct HashMap<K, V, S = RandomState> {
243 base: base::HashMap<K, V, S>,
244}
245
246impl<K, V> HashMap<K, V, RandomState> {
247 /// Creates an empty `HashMap`.
248 ///
249 /// The hash map is initially created with a capacity of 0, so it will not allocate until it
250 /// is first inserted into.
251 ///
252 /// # Examples
253 ///
254 /// ```
255 /// use std::collections::HashMap;
256 /// let mut map: HashMap<&str, i32> = HashMap::new();
257 /// ```
258 #[inline]
259 #[must_use]
260 #[stable(feature = "rust1", since = "1.0.0")]
261 pub fn new() -> HashMap<K, V, RandomState> {
262 Default::default()
263 }
264
265 /// Creates an empty `HashMap` with at least the specified capacity.
266 ///
267 /// The hash map will be able to hold at least `capacity` elements without
268 /// reallocating. This method is allowed to allocate for more elements than
269 /// `capacity`. If `capacity` is zero, the hash map will not allocate.
270 ///
271 /// # Examples
272 ///
273 /// ```
274 /// use std::collections::HashMap;
275 /// let mut map: HashMap<&str, i32> = HashMap::with_capacity(10);
276 /// ```
277 #[inline]
278 #[must_use]
279 #[stable(feature = "rust1", since = "1.0.0")]
280 pub fn with_capacity(capacity: usize) -> HashMap<K, V, RandomState> {
281 HashMap::with_capacity_and_hasher(capacity, Default::default())
282 }
283}
284
285impl<K, V, S> HashMap<K, V, S> {
286 /// Creates an empty `HashMap` which will use the given hash builder to hash
287 /// keys.
288 ///
289 /// The created map has the default initial capacity.
290 ///
291 /// Warning: `hash_builder` is normally randomly generated, and
292 /// is designed to allow HashMaps to be resistant to attacks that
293 /// cause many collisions and very poor performance. Setting it
294 /// manually using this function can expose a DoS attack vector.
295 ///
296 /// The `hash_builder` passed should implement the [`BuildHasher`] trait for
297 /// the `HashMap` to be useful, see its documentation for details.
298 ///
299 /// # Examples
300 ///
301 /// ```
302 /// use std::collections::HashMap;
303 /// use std::hash::RandomState;
304 ///
305 /// let s = RandomState::new();
306 /// let mut map = HashMap::with_hasher(s);
307 /// map.insert(1, 2);
308 /// ```
309 #[inline]
310 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
311 #[rustc_const_stable(feature = "const_collections_with_hasher", since = "1.85.0")]
312 pub const fn with_hasher(hash_builder: S) -> HashMap<K, V, S> {
313 HashMap { base: base::HashMap::with_hasher(hash_builder) }
314 }
315
316 /// Creates an empty `HashMap` with at least the specified capacity, using
317 /// `hasher` to hash the keys.
318 ///
319 /// The hash map will be able to hold at least `capacity` elements without
320 /// reallocating. This method is allowed to allocate for more elements than
321 /// `capacity`. If `capacity` is zero, the hash map will not allocate.
322 ///
323 /// Warning: `hasher` is normally randomly generated, and
324 /// is designed to allow HashMaps to be resistant to attacks that
325 /// cause many collisions and very poor performance. Setting it
326 /// manually using this function can expose a DoS attack vector.
327 ///
328 /// The `hasher` passed should implement the [`BuildHasher`] trait for
329 /// the `HashMap` to be useful, see its documentation for details.
330 ///
331 /// # Examples
332 ///
333 /// ```
334 /// use std::collections::HashMap;
335 /// use std::hash::RandomState;
336 ///
337 /// let s = RandomState::new();
338 /// let mut map = HashMap::with_capacity_and_hasher(10, s);
339 /// map.insert(1, 2);
340 /// ```
341 #[inline]
342 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
343 pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> HashMap<K, V, S> {
344 HashMap { base: base::HashMap::with_capacity_and_hasher(capacity, hasher) }
345 }
346
347 /// Returns the number of elements the map can hold without reallocating.
348 ///
349 /// This number is a lower bound; the `HashMap<K, V>` might be able to hold
350 /// more, but is guaranteed to be able to hold at least this many.
351 ///
352 /// # Examples
353 ///
354 /// ```
355 /// use std::collections::HashMap;
356 /// let map: HashMap<i32, i32> = HashMap::with_capacity(100);
357 /// assert!(map.capacity() >= 100);
358 /// ```
359 #[inline]
360 #[stable(feature = "rust1", since = "1.0.0")]
361 pub fn capacity(&self) -> usize {
362 self.base.capacity()
363 }
364
365 /// An iterator visiting all keys in arbitrary order.
366 /// The iterator element type is `&'a K`.
367 ///
368 /// # Examples
369 ///
370 /// ```
371 /// use std::collections::HashMap;
372 ///
373 /// let map = HashMap::from([
374 /// ("a", 1),
375 /// ("b", 2),
376 /// ("c", 3),
377 /// ]);
378 ///
379 /// for key in map.keys() {
380 /// println!("{key}");
381 /// }
382 /// ```
383 ///
384 /// # Performance
385 ///
386 /// In the current implementation, iterating over keys takes O(capacity) time
387 /// instead of O(len) because it internally visits empty buckets too.
388 #[rustc_lint_query_instability]
389 #[stable(feature = "rust1", since = "1.0.0")]
390 pub fn keys(&self) -> Keys<'_, K, V> {
391 Keys { inner: self.iter() }
392 }
393
394 /// Creates a consuming iterator visiting all the keys in arbitrary order.
395 /// The map cannot be used after calling this.
396 /// The iterator element type is `K`.
397 ///
398 /// # Examples
399 ///
400 /// ```
401 /// use std::collections::HashMap;
402 ///
403 /// let map = HashMap::from([
404 /// ("a", 1),
405 /// ("b", 2),
406 /// ("c", 3),
407 /// ]);
408 ///
409 /// let mut vec: Vec<&str> = map.into_keys().collect();
410 /// // The `IntoKeys` iterator produces keys in arbitrary order, so the
411 /// // keys must be sorted to test them against a sorted array.
412 /// vec.sort_unstable();
413 /// assert_eq!(vec, ["a", "b", "c"]);
414 /// ```
415 ///
416 /// # Performance
417 ///
418 /// In the current implementation, iterating over keys takes O(capacity) time
419 /// instead of O(len) because it internally visits empty buckets too.
420 #[inline]
421 #[rustc_lint_query_instability]
422 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
423 pub fn into_keys(self) -> IntoKeys<K, V> {
424 IntoKeys { inner: self.into_iter() }
425 }
426
427 /// An iterator visiting all values in arbitrary order.
428 /// The iterator element type is `&'a V`.
429 ///
430 /// # Examples
431 ///
432 /// ```
433 /// use std::collections::HashMap;
434 ///
435 /// let map = HashMap::from([
436 /// ("a", 1),
437 /// ("b", 2),
438 /// ("c", 3),
439 /// ]);
440 ///
441 /// for val in map.values() {
442 /// println!("{val}");
443 /// }
444 /// ```
445 ///
446 /// # Performance
447 ///
448 /// In the current implementation, iterating over values takes O(capacity) time
449 /// instead of O(len) because it internally visits empty buckets too.
450 #[rustc_lint_query_instability]
451 #[stable(feature = "rust1", since = "1.0.0")]
452 pub fn values(&self) -> Values<'_, K, V> {
453 Values { inner: self.iter() }
454 }
455
456 /// An iterator visiting all values mutably in arbitrary order.
457 /// The iterator element type is `&'a mut V`.
458 ///
459 /// # Examples
460 ///
461 /// ```
462 /// use std::collections::HashMap;
463 ///
464 /// let mut map = HashMap::from([
465 /// ("a", 1),
466 /// ("b", 2),
467 /// ("c", 3),
468 /// ]);
469 ///
470 /// for val in map.values_mut() {
471 /// *val = *val + 10;
472 /// }
473 ///
474 /// for val in map.values() {
475 /// println!("{val}");
476 /// }
477 /// ```
478 ///
479 /// # Performance
480 ///
481 /// In the current implementation, iterating over values takes O(capacity) time
482 /// instead of O(len) because it internally visits empty buckets too.
483 #[rustc_lint_query_instability]
484 #[stable(feature = "map_values_mut", since = "1.10.0")]
485 pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
486 ValuesMut { inner: self.iter_mut() }
487 }
488
489 /// Creates a consuming iterator visiting all the values in arbitrary order.
490 /// The map cannot be used after calling this.
491 /// The iterator element type is `V`.
492 ///
493 /// # Examples
494 ///
495 /// ```
496 /// use std::collections::HashMap;
497 ///
498 /// let map = HashMap::from([
499 /// ("a", 1),
500 /// ("b", 2),
501 /// ("c", 3),
502 /// ]);
503 ///
504 /// let mut vec: Vec<i32> = map.into_values().collect();
505 /// // The `IntoValues` iterator produces values in arbitrary order, so
506 /// // the values must be sorted to test them against a sorted array.
507 /// vec.sort_unstable();
508 /// assert_eq!(vec, [1, 2, 3]);
509 /// ```
510 ///
511 /// # Performance
512 ///
513 /// In the current implementation, iterating over values takes O(capacity) time
514 /// instead of O(len) because it internally visits empty buckets too.
515 #[inline]
516 #[rustc_lint_query_instability]
517 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
518 pub fn into_values(self) -> IntoValues<K, V> {
519 IntoValues { inner: self.into_iter() }
520 }
521
522 /// An iterator visiting all key-value pairs in arbitrary order.
523 /// The iterator element type is `(&'a K, &'a V)`.
524 ///
525 /// # Examples
526 ///
527 /// ```
528 /// use std::collections::HashMap;
529 ///
530 /// let map = HashMap::from([
531 /// ("a", 1),
532 /// ("b", 2),
533 /// ("c", 3),
534 /// ]);
535 ///
536 /// for (key, val) in map.iter() {
537 /// println!("key: {key} val: {val}");
538 /// }
539 /// ```
540 ///
541 /// # Performance
542 ///
543 /// In the current implementation, iterating over map takes O(capacity) time
544 /// instead of O(len) because it internally visits empty buckets too.
545 #[rustc_lint_query_instability]
546 #[stable(feature = "rust1", since = "1.0.0")]
547 pub fn iter(&self) -> Iter<'_, K, V> {
548 Iter { base: self.base.iter() }
549 }
550
551 /// An iterator visiting all key-value pairs in arbitrary order,
552 /// with mutable references to the values.
553 /// The iterator element type is `(&'a K, &'a mut V)`.
554 ///
555 /// # Examples
556 ///
557 /// ```
558 /// use std::collections::HashMap;
559 ///
560 /// let mut map = HashMap::from([
561 /// ("a", 1),
562 /// ("b", 2),
563 /// ("c", 3),
564 /// ]);
565 ///
566 /// // Update all values
567 /// for (_, val) in map.iter_mut() {
568 /// *val *= 2;
569 /// }
570 ///
571 /// for (key, val) in &map {
572 /// println!("key: {key} val: {val}");
573 /// }
574 /// ```
575 ///
576 /// # Performance
577 ///
578 /// In the current implementation, iterating over map takes O(capacity) time
579 /// instead of O(len) because it internally visits empty buckets too.
580 #[rustc_lint_query_instability]
581 #[stable(feature = "rust1", since = "1.0.0")]
582 pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
583 IterMut { base: self.base.iter_mut() }
584 }
585
586 /// Returns the number of elements in the map.
587 ///
588 /// # Examples
589 ///
590 /// ```
591 /// use std::collections::HashMap;
592 ///
593 /// let mut a = HashMap::new();
594 /// assert_eq!(a.len(), 0);
595 /// a.insert(1, "a");
596 /// assert_eq!(a.len(), 1);
597 /// ```
598 #[stable(feature = "rust1", since = "1.0.0")]
599 pub fn len(&self) -> usize {
600 self.base.len()
601 }
602
603 /// Returns `true` if the map contains no elements.
604 ///
605 /// # Examples
606 ///
607 /// ```
608 /// use std::collections::HashMap;
609 ///
610 /// let mut a = HashMap::new();
611 /// assert!(a.is_empty());
612 /// a.insert(1, "a");
613 /// assert!(!a.is_empty());
614 /// ```
615 #[inline]
616 #[stable(feature = "rust1", since = "1.0.0")]
617 pub fn is_empty(&self) -> bool {
618 self.base.is_empty()
619 }
620
621 /// Clears the map, returning all key-value pairs as an iterator. Keeps the
622 /// allocated memory for reuse.
623 ///
624 /// If the returned iterator is dropped before being fully consumed, it
625 /// drops the remaining key-value pairs. The returned iterator keeps a
626 /// mutable borrow on the map to optimize its implementation.
627 ///
628 /// # Examples
629 ///
630 /// ```
631 /// use std::collections::HashMap;
632 ///
633 /// let mut a = HashMap::new();
634 /// a.insert(1, "a");
635 /// a.insert(2, "b");
636 ///
637 /// for (k, v) in a.drain().take(1) {
638 /// assert!(k == 1 || k == 2);
639 /// assert!(v == "a" || v == "b");
640 /// }
641 ///
642 /// assert!(a.is_empty());
643 /// ```
644 #[inline]
645 #[rustc_lint_query_instability]
646 #[stable(feature = "drain", since = "1.6.0")]
647 pub fn drain(&mut self) -> Drain<'_, K, V> {
648 Drain { base: self.base.drain() }
649 }
650
651 /// Creates an iterator which uses a closure to determine if an element should be removed.
652 ///
653 /// If the closure returns true, the element is removed from the map and yielded.
654 /// If the closure returns false, or panics, the element remains in the map and will not be
655 /// yielded.
656 ///
657 /// Note that `extract_if` lets you mutate every value in the filter closure, regardless of
658 /// whether you choose to keep or remove it.
659 ///
660 /// If the returned `ExtractIf` is not exhausted, e.g. because it is dropped without iterating
661 /// or the iteration short-circuits, then the remaining elements will be retained.
662 /// Use [`retain`] with a negated predicate if you do not need the returned iterator.
663 ///
664 /// [`retain`]: HashMap::retain
665 ///
666 /// # Examples
667 ///
668 /// Splitting a map into even and odd keys, reusing the original map:
669 ///
670 /// ```
671 /// #![feature(hash_extract_if)]
672 /// use std::collections::HashMap;
673 ///
674 /// let mut map: HashMap<i32, i32> = (0..8).map(|x| (x, x)).collect();
675 /// let extracted: HashMap<i32, i32> = map.extract_if(|k, _v| k % 2 == 0).collect();
676 ///
677 /// let mut evens = extracted.keys().copied().collect::<Vec<_>>();
678 /// let mut odds = map.keys().copied().collect::<Vec<_>>();
679 /// evens.sort();
680 /// odds.sort();
681 ///
682 /// assert_eq!(evens, vec![0, 2, 4, 6]);
683 /// assert_eq!(odds, vec![1, 3, 5, 7]);
684 /// ```
685 #[inline]
686 #[rustc_lint_query_instability]
687 #[unstable(feature = "hash_extract_if", issue = "59618")]
688 pub fn extract_if<F>(&mut self, pred: F) -> ExtractIf<'_, K, V, F>
689 where
690 F: FnMut(&K, &mut V) -> bool,
691 {
692 ExtractIf { base: self.base.extract_if(pred) }
693 }
694
695 /// Retains only the elements specified by the predicate.
696 ///
697 /// In other words, remove all pairs `(k, v)` for which `f(&k, &mut v)` returns `false`.
698 /// The elements are visited in unsorted (and unspecified) order.
699 ///
700 /// # Examples
701 ///
702 /// ```
703 /// use std::collections::HashMap;
704 ///
705 /// let mut map: HashMap<i32, i32> = (0..8).map(|x| (x, x*10)).collect();
706 /// map.retain(|&k, _| k % 2 == 0);
707 /// assert_eq!(map.len(), 4);
708 /// ```
709 ///
710 /// # Performance
711 ///
712 /// In the current implementation, this operation takes O(capacity) time
713 /// instead of O(len) because it internally visits empty buckets too.
714 #[inline]
715 #[rustc_lint_query_instability]
716 #[stable(feature = "retain_hash_collection", since = "1.18.0")]
717 pub fn retain<F>(&mut self, f: F)
718 where
719 F: FnMut(&K, &mut V) -> bool,
720 {
721 self.base.retain(f)
722 }
723
724 /// Clears the map, removing all key-value pairs. Keeps the allocated memory
725 /// for reuse.
726 ///
727 /// # Examples
728 ///
729 /// ```
730 /// use std::collections::HashMap;
731 ///
732 /// let mut a = HashMap::new();
733 /// a.insert(1, "a");
734 /// a.clear();
735 /// assert!(a.is_empty());
736 /// ```
737 #[inline]
738 #[stable(feature = "rust1", since = "1.0.0")]
739 pub fn clear(&mut self) {
740 self.base.clear();
741 }
742
743 /// Returns a reference to the map's [`BuildHasher`].
744 ///
745 /// # Examples
746 ///
747 /// ```
748 /// use std::collections::HashMap;
749 /// use std::hash::RandomState;
750 ///
751 /// let hasher = RandomState::new();
752 /// let map: HashMap<i32, i32> = HashMap::with_hasher(hasher);
753 /// let hasher: &RandomState = map.hasher();
754 /// ```
755 #[inline]
756 #[stable(feature = "hashmap_public_hasher", since = "1.9.0")]
757 pub fn hasher(&self) -> &S {
758 self.base.hasher()
759 }
760}
761
762impl<K, V, S> HashMap<K, V, S>
763where
764 K: Eq + Hash,
765 S: BuildHasher,
766{
767 /// Reserves capacity for at least `additional` more elements to be inserted
768 /// in the `HashMap`. The collection may reserve more space to speculatively
769 /// avoid frequent reallocations. After calling `reserve`,
770 /// capacity will be greater than or equal to `self.len() + additional`.
771 /// Does nothing if capacity is already sufficient.
772 ///
773 /// # Panics
774 ///
775 /// Panics if the new allocation size overflows [`usize`].
776 ///
777 /// # Examples
778 ///
779 /// ```
780 /// use std::collections::HashMap;
781 /// let mut map: HashMap<&str, i32> = HashMap::new();
782 /// map.reserve(10);
783 /// ```
784 #[inline]
785 #[stable(feature = "rust1", since = "1.0.0")]
786 pub fn reserve(&mut self, additional: usize) {
787 self.base.reserve(additional)
788 }
789
790 /// Tries to reserve capacity for at least `additional` more elements to be inserted
791 /// in the `HashMap`. The collection may reserve more space to speculatively
792 /// avoid frequent reallocations. After calling `try_reserve`,
793 /// capacity will be greater than or equal to `self.len() + additional` if
794 /// it returns `Ok(())`.
795 /// Does nothing if capacity is already sufficient.
796 ///
797 /// # Errors
798 ///
799 /// If the capacity overflows, or the allocator reports a failure, then an error
800 /// is returned.
801 ///
802 /// # Examples
803 ///
804 /// ```
805 /// use std::collections::HashMap;
806 ///
807 /// let mut map: HashMap<&str, isize> = HashMap::new();
808 /// map.try_reserve(10).expect("why is the test harness OOMing on a handful of bytes?");
809 /// ```
810 #[inline]
811 #[stable(feature = "try_reserve", since = "1.57.0")]
812 pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
813 self.base.try_reserve(additional).map_err(map_try_reserve_error)
814 }
815
816 /// Shrinks the capacity of the map as much as possible. It will drop
817 /// down as much as possible while maintaining the internal rules
818 /// and possibly leaving some space in accordance with the resize policy.
819 ///
820 /// # Examples
821 ///
822 /// ```
823 /// use std::collections::HashMap;
824 ///
825 /// let mut map: HashMap<i32, i32> = HashMap::with_capacity(100);
826 /// map.insert(1, 2);
827 /// map.insert(3, 4);
828 /// assert!(map.capacity() >= 100);
829 /// map.shrink_to_fit();
830 /// assert!(map.capacity() >= 2);
831 /// ```
832 #[inline]
833 #[stable(feature = "rust1", since = "1.0.0")]
834 pub fn shrink_to_fit(&mut self) {
835 self.base.shrink_to_fit();
836 }
837
838 /// Shrinks the capacity of the map with a lower limit. It will drop
839 /// down no lower than the supplied limit while maintaining the internal rules
840 /// and possibly leaving some space in accordance with the resize policy.
841 ///
842 /// If the current capacity is less than the lower limit, this is a no-op.
843 ///
844 /// # Examples
845 ///
846 /// ```
847 /// use std::collections::HashMap;
848 ///
849 /// let mut map: HashMap<i32, i32> = HashMap::with_capacity(100);
850 /// map.insert(1, 2);
851 /// map.insert(3, 4);
852 /// assert!(map.capacity() >= 100);
853 /// map.shrink_to(10);
854 /// assert!(map.capacity() >= 10);
855 /// map.shrink_to(0);
856 /// assert!(map.capacity() >= 2);
857 /// ```
858 #[inline]
859 #[stable(feature = "shrink_to", since = "1.56.0")]
860 pub fn shrink_to(&mut self, min_capacity: usize) {
861 self.base.shrink_to(min_capacity);
862 }
863
864 /// Gets the given key's corresponding entry in the map for in-place manipulation.
865 ///
866 /// # Examples
867 ///
868 /// ```
869 /// use std::collections::HashMap;
870 ///
871 /// let mut letters = HashMap::new();
872 ///
873 /// for ch in "a short treatise on fungi".chars() {
874 /// letters.entry(ch).and_modify(|counter| *counter += 1).or_insert(1);
875 /// }
876 ///
877 /// assert_eq!(letters[&'s'], 2);
878 /// assert_eq!(letters[&'t'], 3);
879 /// assert_eq!(letters[&'u'], 1);
880 /// assert_eq!(letters.get(&'y'), None);
881 /// ```
882 #[inline]
883 #[stable(feature = "rust1", since = "1.0.0")]
884 pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {
885 map_entry(self.base.rustc_entry(key))
886 }
887
888 /// Returns a reference to the value corresponding to the key.
889 ///
890 /// The key may be any borrowed form of the map's key type, but
891 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
892 /// the key type.
893 ///
894 /// # Examples
895 ///
896 /// ```
897 /// use std::collections::HashMap;
898 ///
899 /// let mut map = HashMap::new();
900 /// map.insert(1, "a");
901 /// assert_eq!(map.get(&1), Some(&"a"));
902 /// assert_eq!(map.get(&2), None);
903 /// ```
904 #[stable(feature = "rust1", since = "1.0.0")]
905 #[inline]
906 pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
907 where
908 K: Borrow<Q>,
909 Q: Hash + Eq,
910 {
911 self.base.get(k)
912 }
913
914 /// Returns the key-value pair corresponding to the supplied key. This is
915 /// potentially useful:
916 /// - for key types where non-identical keys can be considered equal;
917 /// - for getting the `&K` stored key value from a borrowed `&Q` lookup key; or
918 /// - for getting a reference to a key with the same lifetime as the collection.
919 ///
920 /// The supplied key may be any borrowed form of the map's key type, but
921 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
922 /// the key type.
923 ///
924 /// # Examples
925 ///
926 /// ```
927 /// use std::collections::HashMap;
928 /// use std::hash::{Hash, Hasher};
929 ///
930 /// #[derive(Clone, Copy, Debug)]
931 /// struct S {
932 /// id: u32,
933 /// # #[allow(unused)] // prevents a "field `name` is never read" error
934 /// name: &'static str, // ignored by equality and hashing operations
935 /// }
936 ///
937 /// impl PartialEq for S {
938 /// fn eq(&self, other: &S) -> bool {
939 /// self.id == other.id
940 /// }
941 /// }
942 ///
943 /// impl Eq for S {}
944 ///
945 /// impl Hash for S {
946 /// fn hash<H: Hasher>(&self, state: &mut H) {
947 /// self.id.hash(state);
948 /// }
949 /// }
950 ///
951 /// let j_a = S { id: 1, name: "Jessica" };
952 /// let j_b = S { id: 1, name: "Jess" };
953 /// let p = S { id: 2, name: "Paul" };
954 /// assert_eq!(j_a, j_b);
955 ///
956 /// let mut map = HashMap::new();
957 /// map.insert(j_a, "Paris");
958 /// assert_eq!(map.get_key_value(&j_a), Some((&j_a, &"Paris")));
959 /// assert_eq!(map.get_key_value(&j_b), Some((&j_a, &"Paris"))); // the notable case
960 /// assert_eq!(map.get_key_value(&p), None);
961 /// ```
962 #[inline]
963 #[stable(feature = "map_get_key_value", since = "1.40.0")]
964 pub fn get_key_value<Q: ?Sized>(&self, k: &Q) -> Option<(&K, &V)>
965 where
966 K: Borrow<Q>,
967 Q: Hash + Eq,
968 {
969 self.base.get_key_value(k)
970 }
971
972 /// Attempts to get mutable references to `N` values in the map at once.
973 ///
974 /// Returns an array of length `N` with the results of each query. For soundness, at most one
975 /// mutable reference will be returned to any value. `None` will be used if the key is missing.
976 ///
977 /// # Panics
978 ///
979 /// Panics if any keys are overlapping.
980 ///
981 /// # Examples
982 ///
983 /// ```
984 /// use std::collections::HashMap;
985 ///
986 /// let mut libraries = HashMap::new();
987 /// libraries.insert("Bodleian Library".to_string(), 1602);
988 /// libraries.insert("Athenæum".to_string(), 1807);
989 /// libraries.insert("Herzogin-Anna-Amalia-Bibliothek".to_string(), 1691);
990 /// libraries.insert("Library of Congress".to_string(), 1800);
991 ///
992 /// // Get Athenæum and Bodleian Library
993 /// let [Some(a), Some(b)] = libraries.get_disjoint_mut([
994 /// "Athenæum",
995 /// "Bodleian Library",
996 /// ]) else { panic!() };
997 ///
998 /// // Assert values of Athenæum and Library of Congress
999 /// let got = libraries.get_disjoint_mut([
1000 /// "Athenæum",
1001 /// "Library of Congress",
1002 /// ]);
1003 /// assert_eq!(
1004 /// got,
1005 /// [
1006 /// Some(&mut 1807),
1007 /// Some(&mut 1800),
1008 /// ],
1009 /// );
1010 ///
1011 /// // Missing keys result in None
1012 /// let got = libraries.get_disjoint_mut([
1013 /// "Athenæum",
1014 /// "New York Public Library",
1015 /// ]);
1016 /// assert_eq!(
1017 /// got,
1018 /// [
1019 /// Some(&mut 1807),
1020 /// None
1021 /// ]
1022 /// );
1023 /// ```
1024 ///
1025 /// ```should_panic
1026 /// use std::collections::HashMap;
1027 ///
1028 /// let mut libraries = HashMap::new();
1029 /// libraries.insert("Athenæum".to_string(), 1807);
1030 ///
1031 /// // Duplicate keys panic!
1032 /// let got = libraries.get_disjoint_mut([
1033 /// "Athenæum",
1034 /// "Athenæum",
1035 /// ]);
1036 /// ```
1037 #[inline]
1038 #[doc(alias = "get_many_mut")]
1039 #[stable(feature = "map_many_mut", since = "1.86.0")]
1040 pub fn get_disjoint_mut<Q: ?Sized, const N: usize>(
1041 &mut self,
1042 ks: [&Q; N],
1043 ) -> [Option<&'_ mut V>; N]
1044 where
1045 K: Borrow<Q>,
1046 Q: Hash + Eq,
1047 {
1048 self.base.get_many_mut(ks)
1049 }
1050
1051 /// Attempts to get mutable references to `N` values in the map at once, without validating that
1052 /// the values are unique.
1053 ///
1054 /// Returns an array of length `N` with the results of each query. `None` will be used if
1055 /// the key is missing.
1056 ///
1057 /// For a safe alternative see [`get_disjoint_mut`](`HashMap::get_disjoint_mut`).
1058 ///
1059 /// # Safety
1060 ///
1061 /// Calling this method with overlapping keys is *[undefined behavior]* even if the resulting
1062 /// references are not used.
1063 ///
1064 /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
1065 ///
1066 /// # Examples
1067 ///
1068 /// ```
1069 /// use std::collections::HashMap;
1070 ///
1071 /// let mut libraries = HashMap::new();
1072 /// libraries.insert("Bodleian Library".to_string(), 1602);
1073 /// libraries.insert("Athenæum".to_string(), 1807);
1074 /// libraries.insert("Herzogin-Anna-Amalia-Bibliothek".to_string(), 1691);
1075 /// libraries.insert("Library of Congress".to_string(), 1800);
1076 ///
1077 /// // SAFETY: The keys do not overlap.
1078 /// let [Some(a), Some(b)] = (unsafe { libraries.get_disjoint_unchecked_mut([
1079 /// "Athenæum",
1080 /// "Bodleian Library",
1081 /// ]) }) else { panic!() };
1082 ///
1083 /// // SAFETY: The keys do not overlap.
1084 /// let got = unsafe { libraries.get_disjoint_unchecked_mut([
1085 /// "Athenæum",
1086 /// "Library of Congress",
1087 /// ]) };
1088 /// assert_eq!(
1089 /// got,
1090 /// [
1091 /// Some(&mut 1807),
1092 /// Some(&mut 1800),
1093 /// ],
1094 /// );
1095 ///
1096 /// // SAFETY: The keys do not overlap.
1097 /// let got = unsafe { libraries.get_disjoint_unchecked_mut([
1098 /// "Athenæum",
1099 /// "New York Public Library",
1100 /// ]) };
1101 /// // Missing keys result in None
1102 /// assert_eq!(got, [Some(&mut 1807), None]);
1103 /// ```
1104 #[inline]
1105 #[doc(alias = "get_many_unchecked_mut")]
1106 #[stable(feature = "map_many_mut", since = "1.86.0")]
1107 pub unsafe fn get_disjoint_unchecked_mut<Q: ?Sized, const N: usize>(
1108 &mut self,
1109 ks: [&Q; N],
1110 ) -> [Option<&'_ mut V>; N]
1111 where
1112 K: Borrow<Q>,
1113 Q: Hash + Eq,
1114 {
1115 unsafe { self.base.get_many_unchecked_mut(ks) }
1116 }
1117
1118 /// Returns `true` if the map contains a value for the specified key.
1119 ///
1120 /// The key may be any borrowed form of the map's key type, but
1121 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
1122 /// the key type.
1123 ///
1124 /// # Examples
1125 ///
1126 /// ```
1127 /// use std::collections::HashMap;
1128 ///
1129 /// let mut map = HashMap::new();
1130 /// map.insert(1, "a");
1131 /// assert_eq!(map.contains_key(&1), true);
1132 /// assert_eq!(map.contains_key(&2), false);
1133 /// ```
1134 #[inline]
1135 #[stable(feature = "rust1", since = "1.0.0")]
1136 #[cfg_attr(not(test), rustc_diagnostic_item = "hashmap_contains_key")]
1137 pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool
1138 where
1139 K: Borrow<Q>,
1140 Q: Hash + Eq,
1141 {
1142 self.base.contains_key(k)
1143 }
1144
1145 /// Returns a mutable reference to the value corresponding to the key.
1146 ///
1147 /// The key may be any borrowed form of the map's key type, but
1148 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
1149 /// the key type.
1150 ///
1151 /// # Examples
1152 ///
1153 /// ```
1154 /// use std::collections::HashMap;
1155 ///
1156 /// let mut map = HashMap::new();
1157 /// map.insert(1, "a");
1158 /// if let Some(x) = map.get_mut(&1) {
1159 /// *x = "b";
1160 /// }
1161 /// assert_eq!(map[&1], "b");
1162 /// ```
1163 #[inline]
1164 #[stable(feature = "rust1", since = "1.0.0")]
1165 pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
1166 where
1167 K: Borrow<Q>,
1168 Q: Hash + Eq,
1169 {
1170 self.base.get_mut(k)
1171 }
1172
1173 /// Inserts a key-value pair into the map.
1174 ///
1175 /// If the map did not have this key present, [`None`] is returned.
1176 ///
1177 /// If the map did have this key present, the value is updated, and the old
1178 /// value is returned. The key is not updated, though; this matters for
1179 /// types that can be `==` without being identical. See the [module-level
1180 /// documentation] for more.
1181 ///
1182 /// [module-level documentation]: crate::collections#insert-and-complex-keys
1183 ///
1184 /// # Examples
1185 ///
1186 /// ```
1187 /// use std::collections::HashMap;
1188 ///
1189 /// let mut map = HashMap::new();
1190 /// assert_eq!(map.insert(37, "a"), None);
1191 /// assert_eq!(map.is_empty(), false);
1192 ///
1193 /// map.insert(37, "b");
1194 /// assert_eq!(map.insert(37, "c"), Some("b"));
1195 /// assert_eq!(map[&37], "c");
1196 /// ```
1197 #[inline]
1198 #[stable(feature = "rust1", since = "1.0.0")]
1199 #[rustc_confusables("push", "append", "put")]
1200 #[cfg_attr(not(test), rustc_diagnostic_item = "hashmap_insert")]
1201 pub fn insert(&mut self, k: K, v: V) -> Option<V> {
1202 self.base.insert(k, v)
1203 }
1204
1205 /// Tries to insert a key-value pair into the map, and returns
1206 /// a mutable reference to the value in the entry.
1207 ///
1208 /// If the map already had this key present, nothing is updated, and
1209 /// an error containing the occupied entry and the value is returned.
1210 ///
1211 /// # Examples
1212 ///
1213 /// Basic usage:
1214 ///
1215 /// ```
1216 /// #![feature(map_try_insert)]
1217 ///
1218 /// use std::collections::HashMap;
1219 ///
1220 /// let mut map = HashMap::new();
1221 /// assert_eq!(map.try_insert(37, "a").unwrap(), &"a");
1222 ///
1223 /// let err = map.try_insert(37, "b").unwrap_err();
1224 /// assert_eq!(err.entry.key(), &37);
1225 /// assert_eq!(err.entry.get(), &"a");
1226 /// assert_eq!(err.value, "b");
1227 /// ```
1228 #[unstable(feature = "map_try_insert", issue = "82766")]
1229 pub fn try_insert(&mut self, key: K, value: V) -> Result<&mut V, OccupiedError<'_, K, V>> {
1230 match self.entry(key) {
1231 Occupied(entry) => Err(OccupiedError { entry, value }),
1232 Vacant(entry) => Ok(entry.insert(value)),
1233 }
1234 }
1235
1236 /// Removes a key from the map, returning the value at the key if the key
1237 /// was previously in the map.
1238 ///
1239 /// The key may be any borrowed form of the map's key type, but
1240 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
1241 /// the key type.
1242 ///
1243 /// # Examples
1244 ///
1245 /// ```
1246 /// use std::collections::HashMap;
1247 ///
1248 /// let mut map = HashMap::new();
1249 /// map.insert(1, "a");
1250 /// assert_eq!(map.remove(&1), Some("a"));
1251 /// assert_eq!(map.remove(&1), None);
1252 /// ```
1253 #[inline]
1254 #[stable(feature = "rust1", since = "1.0.0")]
1255 #[rustc_confusables("delete", "take")]
1256 pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V>
1257 where
1258 K: Borrow<Q>,
1259 Q: Hash + Eq,
1260 {
1261 self.base.remove(k)
1262 }
1263
1264 /// Removes a key from the map, returning the stored key and value if the
1265 /// key was previously in the map.
1266 ///
1267 /// The key may be any borrowed form of the map's key type, but
1268 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
1269 /// the key type.
1270 ///
1271 /// # Examples
1272 ///
1273 /// ```
1274 /// use std::collections::HashMap;
1275 ///
1276 /// # fn main() {
1277 /// let mut map = HashMap::new();
1278 /// map.insert(1, "a");
1279 /// assert_eq!(map.remove_entry(&1), Some((1, "a")));
1280 /// assert_eq!(map.remove(&1), None);
1281 /// # }
1282 /// ```
1283 #[inline]
1284 #[stable(feature = "hash_map_remove_entry", since = "1.27.0")]
1285 pub fn remove_entry<Q: ?Sized>(&mut self, k: &Q) -> Option<(K, V)>
1286 where
1287 K: Borrow<Q>,
1288 Q: Hash + Eq,
1289 {
1290 self.base.remove_entry(k)
1291 }
1292}
1293
1294#[stable(feature = "rust1", since = "1.0.0")]
1295impl<K, V, S> Clone for HashMap<K, V, S>
1296where
1297 K: Clone,
1298 V: Clone,
1299 S: Clone,
1300{
1301 #[inline]
1302 fn clone(&self) -> Self {
1303 Self { base: self.base.clone() }
1304 }
1305
1306 #[inline]
1307 fn clone_from(&mut self, source: &Self) {
1308 self.base.clone_from(&source.base);
1309 }
1310}
1311
1312#[stable(feature = "rust1", since = "1.0.0")]
1313impl<K, V, S> PartialEq for HashMap<K, V, S>
1314where
1315 K: Eq + Hash,
1316 V: PartialEq,
1317 S: BuildHasher,
1318{
1319 fn eq(&self, other: &HashMap<K, V, S>) -> bool {
1320 if self.len() != other.len() {
1321 return false;
1322 }
1323
1324 self.iter().all(|(key: &K, value: &V)| other.get(key).map_or(default:false, |v: &V| *value == *v))
1325 }
1326}
1327
1328#[stable(feature = "rust1", since = "1.0.0")]
1329impl<K, V, S> Eq for HashMap<K, V, S>
1330where
1331 K: Eq + Hash,
1332 V: Eq,
1333 S: BuildHasher,
1334{
1335}
1336
1337#[stable(feature = "rust1", since = "1.0.0")]
1338impl<K, V, S> Debug for HashMap<K, V, S>
1339where
1340 K: Debug,
1341 V: Debug,
1342{
1343 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1344 f.debug_map().entries(self.iter()).finish()
1345 }
1346}
1347
1348#[stable(feature = "rust1", since = "1.0.0")]
1349impl<K, V, S> Default for HashMap<K, V, S>
1350where
1351 S: Default,
1352{
1353 /// Creates an empty `HashMap<K, V, S>`, with the `Default` value for the hasher.
1354 #[inline]
1355 fn default() -> HashMap<K, V, S> {
1356 HashMap::with_hasher(hash_builder:Default::default())
1357 }
1358}
1359
1360#[stable(feature = "rust1", since = "1.0.0")]
1361impl<K, Q: ?Sized, V, S> Index<&Q> for HashMap<K, V, S>
1362where
1363 K: Eq + Hash + Borrow<Q>,
1364 Q: Eq + Hash,
1365 S: BuildHasher,
1366{
1367 type Output = V;
1368
1369 /// Returns a reference to the value corresponding to the supplied key.
1370 ///
1371 /// # Panics
1372 ///
1373 /// Panics if the key is not present in the `HashMap`.
1374 #[inline]
1375 fn index(&self, key: &Q) -> &V {
1376 self.get(key).expect(msg:"no entry found for key")
1377 }
1378}
1379
1380#[stable(feature = "std_collections_from_array", since = "1.56.0")]
1381// Note: as what is currently the most convenient built-in way to construct
1382// a HashMap, a simple usage of this function must not *require* the user
1383// to provide a type annotation in order to infer the third type parameter
1384// (the hasher parameter, conventionally "S").
1385// To that end, this impl is defined using RandomState as the concrete
1386// type of S, rather than being generic over `S: BuildHasher + Default`.
1387// It is expected that users who want to specify a hasher will manually use
1388// `with_capacity_and_hasher`.
1389// If type parameter defaults worked on impls, and if type parameter
1390// defaults could be mixed with const generics, then perhaps
1391// this could be generalized.
1392// See also the equivalent impl on HashSet.
1393impl<K, V, const N: usize> From<[(K, V); N]> for HashMap<K, V, RandomState>
1394where
1395 K: Eq + Hash,
1396{
1397 /// Converts a `[(K, V); N]` into a `HashMap<K, V>`.
1398 ///
1399 /// If any entries in the array have equal keys,
1400 /// all but one of the corresponding values will be dropped.
1401 ///
1402 /// # Examples
1403 ///
1404 /// ```
1405 /// use std::collections::HashMap;
1406 ///
1407 /// let map1 = HashMap::from([(1, 2), (3, 4)]);
1408 /// let map2: HashMap<_, _> = [(1, 2), (3, 4)].into();
1409 /// assert_eq!(map1, map2);
1410 /// ```
1411 fn from(arr: [(K, V); N]) -> Self {
1412 Self::from_iter(arr)
1413 }
1414}
1415
1416/// An iterator over the entries of a `HashMap`.
1417///
1418/// This `struct` is created by the [`iter`] method on [`HashMap`]. See its
1419/// documentation for more.
1420///
1421/// [`iter`]: HashMap::iter
1422///
1423/// # Example
1424///
1425/// ```
1426/// use std::collections::HashMap;
1427///
1428/// let map = HashMap::from([
1429/// ("a", 1),
1430/// ]);
1431/// let iter = map.iter();
1432/// ```
1433#[stable(feature = "rust1", since = "1.0.0")]
1434#[cfg_attr(not(test), rustc_diagnostic_item = "hashmap_iter_ty")]
1435pub struct Iter<'a, K: 'a, V: 'a> {
1436 base: base::Iter<'a, K, V>,
1437}
1438
1439// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
1440#[stable(feature = "rust1", since = "1.0.0")]
1441impl<K, V> Clone for Iter<'_, K, V> {
1442 #[inline]
1443 fn clone(&self) -> Self {
1444 Iter { base: self.base.clone() }
1445 }
1446}
1447
1448#[stable(feature = "default_iters_hash", since = "1.83.0")]
1449impl<K, V> Default for Iter<'_, K, V> {
1450 #[inline]
1451 fn default() -> Self {
1452 Iter { base: Default::default() }
1453 }
1454}
1455
1456#[stable(feature = "std_debug", since = "1.16.0")]
1457impl<K: Debug, V: Debug> fmt::Debug for Iter<'_, K, V> {
1458 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1459 f.debug_list().entries(self.clone()).finish()
1460 }
1461}
1462
1463/// A mutable iterator over the entries of a `HashMap`.
1464///
1465/// This `struct` is created by the [`iter_mut`] method on [`HashMap`]. See its
1466/// documentation for more.
1467///
1468/// [`iter_mut`]: HashMap::iter_mut
1469///
1470/// # Example
1471///
1472/// ```
1473/// use std::collections::HashMap;
1474///
1475/// let mut map = HashMap::from([
1476/// ("a", 1),
1477/// ]);
1478/// let iter = map.iter_mut();
1479/// ```
1480#[stable(feature = "rust1", since = "1.0.0")]
1481#[cfg_attr(not(test), rustc_diagnostic_item = "hashmap_iter_mut_ty")]
1482pub struct IterMut<'a, K: 'a, V: 'a> {
1483 base: base::IterMut<'a, K, V>,
1484}
1485
1486impl<'a, K, V> IterMut<'a, K, V> {
1487 /// Returns an iterator of references over the remaining items.
1488 #[inline]
1489 pub(super) fn iter(&self) -> Iter<'_, K, V> {
1490 Iter { base: self.base.rustc_iter() }
1491 }
1492}
1493
1494#[stable(feature = "default_iters_hash", since = "1.83.0")]
1495impl<K, V> Default for IterMut<'_, K, V> {
1496 #[inline]
1497 fn default() -> Self {
1498 IterMut { base: Default::default() }
1499 }
1500}
1501
1502/// An owning iterator over the entries of a `HashMap`.
1503///
1504/// This `struct` is created by the [`into_iter`] method on [`HashMap`]
1505/// (provided by the [`IntoIterator`] trait). See its documentation for more.
1506///
1507/// [`into_iter`]: IntoIterator::into_iter
1508///
1509/// # Example
1510///
1511/// ```
1512/// use std::collections::HashMap;
1513///
1514/// let map = HashMap::from([
1515/// ("a", 1),
1516/// ]);
1517/// let iter = map.into_iter();
1518/// ```
1519#[stable(feature = "rust1", since = "1.0.0")]
1520pub struct IntoIter<K, V> {
1521 base: base::IntoIter<K, V>,
1522}
1523
1524impl<K, V> IntoIter<K, V> {
1525 /// Returns an iterator of references over the remaining items.
1526 #[inline]
1527 pub(super) fn iter(&self) -> Iter<'_, K, V> {
1528 Iter { base: self.base.rustc_iter() }
1529 }
1530}
1531
1532#[stable(feature = "default_iters_hash", since = "1.83.0")]
1533impl<K, V> Default for IntoIter<K, V> {
1534 #[inline]
1535 fn default() -> Self {
1536 IntoIter { base: Default::default() }
1537 }
1538}
1539
1540/// An iterator over the keys of a `HashMap`.
1541///
1542/// This `struct` is created by the [`keys`] method on [`HashMap`]. See its
1543/// documentation for more.
1544///
1545/// [`keys`]: HashMap::keys
1546///
1547/// # Example
1548///
1549/// ```
1550/// use std::collections::HashMap;
1551///
1552/// let map = HashMap::from([
1553/// ("a", 1),
1554/// ]);
1555/// let iter_keys = map.keys();
1556/// ```
1557#[stable(feature = "rust1", since = "1.0.0")]
1558#[cfg_attr(not(test), rustc_diagnostic_item = "hashmap_keys_ty")]
1559pub struct Keys<'a, K: 'a, V: 'a> {
1560 inner: Iter<'a, K, V>,
1561}
1562
1563// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
1564#[stable(feature = "rust1", since = "1.0.0")]
1565impl<K, V> Clone for Keys<'_, K, V> {
1566 #[inline]
1567 fn clone(&self) -> Self {
1568 Keys { inner: self.inner.clone() }
1569 }
1570}
1571
1572#[stable(feature = "default_iters_hash", since = "1.83.0")]
1573impl<K, V> Default for Keys<'_, K, V> {
1574 #[inline]
1575 fn default() -> Self {
1576 Keys { inner: Default::default() }
1577 }
1578}
1579
1580#[stable(feature = "std_debug", since = "1.16.0")]
1581impl<K: Debug, V> fmt::Debug for Keys<'_, K, V> {
1582 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1583 f.debug_list().entries(self.clone()).finish()
1584 }
1585}
1586
1587/// An iterator over the values of a `HashMap`.
1588///
1589/// This `struct` is created by the [`values`] method on [`HashMap`]. See its
1590/// documentation for more.
1591///
1592/// [`values`]: HashMap::values
1593///
1594/// # Example
1595///
1596/// ```
1597/// use std::collections::HashMap;
1598///
1599/// let map = HashMap::from([
1600/// ("a", 1),
1601/// ]);
1602/// let iter_values = map.values();
1603/// ```
1604#[stable(feature = "rust1", since = "1.0.0")]
1605#[cfg_attr(not(test), rustc_diagnostic_item = "hashmap_values_ty")]
1606pub struct Values<'a, K: 'a, V: 'a> {
1607 inner: Iter<'a, K, V>,
1608}
1609
1610// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
1611#[stable(feature = "rust1", since = "1.0.0")]
1612impl<K, V> Clone for Values<'_, K, V> {
1613 #[inline]
1614 fn clone(&self) -> Self {
1615 Values { inner: self.inner.clone() }
1616 }
1617}
1618
1619#[stable(feature = "default_iters_hash", since = "1.83.0")]
1620impl<K, V> Default for Values<'_, K, V> {
1621 #[inline]
1622 fn default() -> Self {
1623 Values { inner: Default::default() }
1624 }
1625}
1626
1627#[stable(feature = "std_debug", since = "1.16.0")]
1628impl<K, V: Debug> fmt::Debug for Values<'_, K, V> {
1629 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1630 f.debug_list().entries(self.clone()).finish()
1631 }
1632}
1633
1634/// A draining iterator over the entries of a `HashMap`.
1635///
1636/// This `struct` is created by the [`drain`] method on [`HashMap`]. See its
1637/// documentation for more.
1638///
1639/// [`drain`]: HashMap::drain
1640///
1641/// # Example
1642///
1643/// ```
1644/// use std::collections::HashMap;
1645///
1646/// let mut map = HashMap::from([
1647/// ("a", 1),
1648/// ]);
1649/// let iter = map.drain();
1650/// ```
1651#[stable(feature = "drain", since = "1.6.0")]
1652#[cfg_attr(not(test), rustc_diagnostic_item = "hashmap_drain_ty")]
1653pub struct Drain<'a, K: 'a, V: 'a> {
1654 base: base::Drain<'a, K, V>,
1655}
1656
1657impl<'a, K, V> Drain<'a, K, V> {
1658 /// Returns an iterator of references over the remaining items.
1659 #[inline]
1660 pub(super) fn iter(&self) -> Iter<'_, K, V> {
1661 Iter { base: self.base.rustc_iter() }
1662 }
1663}
1664
1665/// A draining, filtering iterator over the entries of a `HashMap`.
1666///
1667/// This `struct` is created by the [`extract_if`] method on [`HashMap`].
1668///
1669/// [`extract_if`]: HashMap::extract_if
1670///
1671/// # Example
1672///
1673/// ```
1674/// #![feature(hash_extract_if)]
1675///
1676/// use std::collections::HashMap;
1677///
1678/// let mut map = HashMap::from([
1679/// ("a", 1),
1680/// ]);
1681/// let iter = map.extract_if(|_k, v| *v % 2 == 0);
1682/// ```
1683#[unstable(feature = "hash_extract_if", issue = "59618")]
1684#[must_use = "iterators are lazy and do nothing unless consumed"]
1685pub struct ExtractIf<'a, K, V, F>
1686where
1687 F: FnMut(&K, &mut V) -> bool,
1688{
1689 base: base::ExtractIf<'a, K, V, F>,
1690}
1691
1692/// A mutable iterator over the values of a `HashMap`.
1693///
1694/// This `struct` is created by the [`values_mut`] method on [`HashMap`]. See its
1695/// documentation for more.
1696///
1697/// [`values_mut`]: HashMap::values_mut
1698///
1699/// # Example
1700///
1701/// ```
1702/// use std::collections::HashMap;
1703///
1704/// let mut map = HashMap::from([
1705/// ("a", 1),
1706/// ]);
1707/// let iter_values = map.values_mut();
1708/// ```
1709#[stable(feature = "map_values_mut", since = "1.10.0")]
1710#[cfg_attr(not(test), rustc_diagnostic_item = "hashmap_values_mut_ty")]
1711pub struct ValuesMut<'a, K: 'a, V: 'a> {
1712 inner: IterMut<'a, K, V>,
1713}
1714
1715#[stable(feature = "default_iters_hash", since = "1.83.0")]
1716impl<K, V> Default for ValuesMut<'_, K, V> {
1717 #[inline]
1718 fn default() -> Self {
1719 ValuesMut { inner: Default::default() }
1720 }
1721}
1722
1723/// An owning iterator over the keys of a `HashMap`.
1724///
1725/// This `struct` is created by the [`into_keys`] method on [`HashMap`].
1726/// See its documentation for more.
1727///
1728/// [`into_keys`]: HashMap::into_keys
1729///
1730/// # Example
1731///
1732/// ```
1733/// use std::collections::HashMap;
1734///
1735/// let map = HashMap::from([
1736/// ("a", 1),
1737/// ]);
1738/// let iter_keys = map.into_keys();
1739/// ```
1740#[stable(feature = "map_into_keys_values", since = "1.54.0")]
1741pub struct IntoKeys<K, V> {
1742 inner: IntoIter<K, V>,
1743}
1744
1745#[stable(feature = "default_iters_hash", since = "1.83.0")]
1746impl<K, V> Default for IntoKeys<K, V> {
1747 #[inline]
1748 fn default() -> Self {
1749 IntoKeys { inner: Default::default() }
1750 }
1751}
1752
1753/// An owning iterator over the values of a `HashMap`.
1754///
1755/// This `struct` is created by the [`into_values`] method on [`HashMap`].
1756/// See its documentation for more.
1757///
1758/// [`into_values`]: HashMap::into_values
1759///
1760/// # Example
1761///
1762/// ```
1763/// use std::collections::HashMap;
1764///
1765/// let map = HashMap::from([
1766/// ("a", 1),
1767/// ]);
1768/// let iter_keys = map.into_values();
1769/// ```
1770#[stable(feature = "map_into_keys_values", since = "1.54.0")]
1771pub struct IntoValues<K, V> {
1772 inner: IntoIter<K, V>,
1773}
1774
1775#[stable(feature = "default_iters_hash", since = "1.83.0")]
1776impl<K, V> Default for IntoValues<K, V> {
1777 #[inline]
1778 fn default() -> Self {
1779 IntoValues { inner: Default::default() }
1780 }
1781}
1782
1783/// A view into a single entry in a map, which may either be vacant or occupied.
1784///
1785/// This `enum` is constructed from the [`entry`] method on [`HashMap`].
1786///
1787/// [`entry`]: HashMap::entry
1788#[stable(feature = "rust1", since = "1.0.0")]
1789#[cfg_attr(not(test), rustc_diagnostic_item = "HashMapEntry")]
1790pub enum Entry<'a, K: 'a, V: 'a> {
1791 /// An occupied entry.
1792 #[stable(feature = "rust1", since = "1.0.0")]
1793 Occupied(#[stable(feature = "rust1", since = "1.0.0")] OccupiedEntry<'a, K, V>),
1794
1795 /// A vacant entry.
1796 #[stable(feature = "rust1", since = "1.0.0")]
1797 Vacant(#[stable(feature = "rust1", since = "1.0.0")] VacantEntry<'a, K, V>),
1798}
1799
1800#[stable(feature = "debug_hash_map", since = "1.12.0")]
1801impl<K: Debug, V: Debug> Debug for Entry<'_, K, V> {
1802 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1803 match *self {
1804 Vacant(ref v: &VacantEntry<'_, K, V>) => f.debug_tuple(name:"Entry").field(v).finish(),
1805 Occupied(ref o: &OccupiedEntry<'_, K, V>) => f.debug_tuple(name:"Entry").field(o).finish(),
1806 }
1807 }
1808}
1809
1810/// A view into an occupied entry in a `HashMap`.
1811/// It is part of the [`Entry`] enum.
1812#[stable(feature = "rust1", since = "1.0.0")]
1813pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
1814 base: base::RustcOccupiedEntry<'a, K, V>,
1815}
1816
1817#[stable(feature = "debug_hash_map", since = "1.12.0")]
1818impl<K: Debug, V: Debug> Debug for OccupiedEntry<'_, K, V> {
1819 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1820 f&mut DebugStruct<'_, '_>.debug_struct("OccupiedEntry")
1821 .field("key", self.key())
1822 .field(name:"value", self.get())
1823 .finish_non_exhaustive()
1824 }
1825}
1826
1827/// A view into a vacant entry in a `HashMap`.
1828/// It is part of the [`Entry`] enum.
1829#[stable(feature = "rust1", since = "1.0.0")]
1830pub struct VacantEntry<'a, K: 'a, V: 'a> {
1831 base: base::RustcVacantEntry<'a, K, V>,
1832}
1833
1834#[stable(feature = "debug_hash_map", since = "1.12.0")]
1835impl<K: Debug, V> Debug for VacantEntry<'_, K, V> {
1836 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1837 f.debug_tuple(name:"VacantEntry").field(self.key()).finish()
1838 }
1839}
1840
1841/// The error returned by [`try_insert`](HashMap::try_insert) when the key already exists.
1842///
1843/// Contains the occupied entry, and the value that was not inserted.
1844#[unstable(feature = "map_try_insert", issue = "82766")]
1845pub struct OccupiedError<'a, K: 'a, V: 'a> {
1846 /// The entry in the map that was already occupied.
1847 pub entry: OccupiedEntry<'a, K, V>,
1848 /// The value which was not inserted, because the entry was already occupied.
1849 pub value: V,
1850}
1851
1852#[unstable(feature = "map_try_insert", issue = "82766")]
1853impl<K: Debug, V: Debug> Debug for OccupiedError<'_, K, V> {
1854 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1855 f&mut DebugStruct<'_, '_>.debug_struct("OccupiedError")
1856 .field("key", self.entry.key())
1857 .field("old_value", self.entry.get())
1858 .field(name:"new_value", &self.value)
1859 .finish_non_exhaustive()
1860 }
1861}
1862
1863#[unstable(feature = "map_try_insert", issue = "82766")]
1864impl<'a, K: Debug, V: Debug> fmt::Display for OccupiedError<'a, K, V> {
1865 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1866 write!(
1867 f,
1868 "failed to insert {:?}, key {:?} already exists with value {:?}",
1869 self.value,
1870 self.entry.key(),
1871 self.entry.get(),
1872 )
1873 }
1874}
1875
1876#[unstable(feature = "map_try_insert", issue = "82766")]
1877impl<'a, K: fmt::Debug, V: fmt::Debug> Error for OccupiedError<'a, K, V> {
1878 #[allow(deprecated)]
1879 fn description(&self) -> &str {
1880 "key already exists"
1881 }
1882}
1883
1884#[stable(feature = "rust1", since = "1.0.0")]
1885impl<'a, K, V, S> IntoIterator for &'a HashMap<K, V, S> {
1886 type Item = (&'a K, &'a V);
1887 type IntoIter = Iter<'a, K, V>;
1888
1889 #[inline]
1890 #[rustc_lint_query_instability]
1891 fn into_iter(self) -> Iter<'a, K, V> {
1892 self.iter()
1893 }
1894}
1895
1896#[stable(feature = "rust1", since = "1.0.0")]
1897impl<'a, K, V, S> IntoIterator for &'a mut HashMap<K, V, S> {
1898 type Item = (&'a K, &'a mut V);
1899 type IntoIter = IterMut<'a, K, V>;
1900
1901 #[inline]
1902 #[rustc_lint_query_instability]
1903 fn into_iter(self) -> IterMut<'a, K, V> {
1904 self.iter_mut()
1905 }
1906}
1907
1908#[stable(feature = "rust1", since = "1.0.0")]
1909impl<K, V, S> IntoIterator for HashMap<K, V, S> {
1910 type Item = (K, V);
1911 type IntoIter = IntoIter<K, V>;
1912
1913 /// Creates a consuming iterator, that is, one that moves each key-value
1914 /// pair out of the map in arbitrary order. The map cannot be used after
1915 /// calling this.
1916 ///
1917 /// # Examples
1918 ///
1919 /// ```
1920 /// use std::collections::HashMap;
1921 ///
1922 /// let map = HashMap::from([
1923 /// ("a", 1),
1924 /// ("b", 2),
1925 /// ("c", 3),
1926 /// ]);
1927 ///
1928 /// // Not possible with .iter()
1929 /// let vec: Vec<(&str, i32)> = map.into_iter().collect();
1930 /// ```
1931 #[inline]
1932 #[rustc_lint_query_instability]
1933 fn into_iter(self) -> IntoIter<K, V> {
1934 IntoIter { base: self.base.into_iter() }
1935 }
1936}
1937
1938#[stable(feature = "rust1", since = "1.0.0")]
1939impl<'a, K, V> Iterator for Iter<'a, K, V> {
1940 type Item = (&'a K, &'a V);
1941
1942 #[inline]
1943 fn next(&mut self) -> Option<(&'a K, &'a V)> {
1944 self.base.next()
1945 }
1946 #[inline]
1947 fn size_hint(&self) -> (usize, Option<usize>) {
1948 self.base.size_hint()
1949 }
1950 #[inline]
1951 fn count(self) -> usize {
1952 self.base.len()
1953 }
1954 #[inline]
1955 fn fold<B, F>(self, init: B, f: F) -> B
1956 where
1957 Self: Sized,
1958 F: FnMut(B, Self::Item) -> B,
1959 {
1960 self.base.fold(init, f)
1961 }
1962}
1963#[stable(feature = "rust1", since = "1.0.0")]
1964impl<K, V> ExactSizeIterator for Iter<'_, K, V> {
1965 #[inline]
1966 fn len(&self) -> usize {
1967 self.base.len()
1968 }
1969}
1970
1971#[stable(feature = "fused", since = "1.26.0")]
1972impl<K, V> FusedIterator for Iter<'_, K, V> {}
1973
1974#[stable(feature = "rust1", since = "1.0.0")]
1975impl<'a, K, V> Iterator for IterMut<'a, K, V> {
1976 type Item = (&'a K, &'a mut V);
1977
1978 #[inline]
1979 fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
1980 self.base.next()
1981 }
1982 #[inline]
1983 fn size_hint(&self) -> (usize, Option<usize>) {
1984 self.base.size_hint()
1985 }
1986 #[inline]
1987 fn count(self) -> usize {
1988 self.base.len()
1989 }
1990 #[inline]
1991 fn fold<B, F>(self, init: B, f: F) -> B
1992 where
1993 Self: Sized,
1994 F: FnMut(B, Self::Item) -> B,
1995 {
1996 self.base.fold(init, f)
1997 }
1998}
1999#[stable(feature = "rust1", since = "1.0.0")]
2000impl<K, V> ExactSizeIterator for IterMut<'_, K, V> {
2001 #[inline]
2002 fn len(&self) -> usize {
2003 self.base.len()
2004 }
2005}
2006#[stable(feature = "fused", since = "1.26.0")]
2007impl<K, V> FusedIterator for IterMut<'_, K, V> {}
2008
2009#[stable(feature = "std_debug", since = "1.16.0")]
2010impl<K, V> fmt::Debug for IterMut<'_, K, V>
2011where
2012 K: fmt::Debug,
2013 V: fmt::Debug,
2014{
2015 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2016 f.debug_list().entries(self.iter()).finish()
2017 }
2018}
2019
2020#[stable(feature = "rust1", since = "1.0.0")]
2021impl<K, V> Iterator for IntoIter<K, V> {
2022 type Item = (K, V);
2023
2024 #[inline]
2025 fn next(&mut self) -> Option<(K, V)> {
2026 self.base.next()
2027 }
2028 #[inline]
2029 fn size_hint(&self) -> (usize, Option<usize>) {
2030 self.base.size_hint()
2031 }
2032 #[inline]
2033 fn count(self) -> usize {
2034 self.base.len()
2035 }
2036 #[inline]
2037 fn fold<B, F>(self, init: B, f: F) -> B
2038 where
2039 Self: Sized,
2040 F: FnMut(B, Self::Item) -> B,
2041 {
2042 self.base.fold(init, f)
2043 }
2044}
2045#[stable(feature = "rust1", since = "1.0.0")]
2046impl<K, V> ExactSizeIterator for IntoIter<K, V> {
2047 #[inline]
2048 fn len(&self) -> usize {
2049 self.base.len()
2050 }
2051}
2052#[stable(feature = "fused", since = "1.26.0")]
2053impl<K, V> FusedIterator for IntoIter<K, V> {}
2054
2055#[stable(feature = "std_debug", since = "1.16.0")]
2056impl<K: Debug, V: Debug> fmt::Debug for IntoIter<K, V> {
2057 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2058 f.debug_list().entries(self.iter()).finish()
2059 }
2060}
2061
2062#[stable(feature = "rust1", since = "1.0.0")]
2063impl<'a, K, V> Iterator for Keys<'a, K, V> {
2064 type Item = &'a K;
2065
2066 #[inline]
2067 fn next(&mut self) -> Option<&'a K> {
2068 self.inner.next().map(|(k: &'a K, _)| k)
2069 }
2070 #[inline]
2071 fn size_hint(&self) -> (usize, Option<usize>) {
2072 self.inner.size_hint()
2073 }
2074 #[inline]
2075 fn count(self) -> usize {
2076 self.inner.len()
2077 }
2078 #[inline]
2079 fn fold<B, F>(self, init: B, mut f: F) -> B
2080 where
2081 Self: Sized,
2082 F: FnMut(B, Self::Item) -> B,
2083 {
2084 self.inner.fold(init, |acc: B, (k: &'a K, _)| f(acc, k))
2085 }
2086}
2087#[stable(feature = "rust1", since = "1.0.0")]
2088impl<K, V> ExactSizeIterator for Keys<'_, K, V> {
2089 #[inline]
2090 fn len(&self) -> usize {
2091 self.inner.len()
2092 }
2093}
2094#[stable(feature = "fused", since = "1.26.0")]
2095impl<K, V> FusedIterator for Keys<'_, K, V> {}
2096
2097#[stable(feature = "rust1", since = "1.0.0")]
2098impl<'a, K, V> Iterator for Values<'a, K, V> {
2099 type Item = &'a V;
2100
2101 #[inline]
2102 fn next(&mut self) -> Option<&'a V> {
2103 self.inner.next().map(|(_, v: &'a V)| v)
2104 }
2105 #[inline]
2106 fn size_hint(&self) -> (usize, Option<usize>) {
2107 self.inner.size_hint()
2108 }
2109 #[inline]
2110 fn count(self) -> usize {
2111 self.inner.len()
2112 }
2113 #[inline]
2114 fn fold<B, F>(self, init: B, mut f: F) -> B
2115 where
2116 Self: Sized,
2117 F: FnMut(B, Self::Item) -> B,
2118 {
2119 self.inner.fold(init, |acc: B, (_, v: &'a V)| f(acc, v))
2120 }
2121}
2122#[stable(feature = "rust1", since = "1.0.0")]
2123impl<K, V> ExactSizeIterator for Values<'_, K, V> {
2124 #[inline]
2125 fn len(&self) -> usize {
2126 self.inner.len()
2127 }
2128}
2129#[stable(feature = "fused", since = "1.26.0")]
2130impl<K, V> FusedIterator for Values<'_, K, V> {}
2131
2132#[stable(feature = "map_values_mut", since = "1.10.0")]
2133impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
2134 type Item = &'a mut V;
2135
2136 #[inline]
2137 fn next(&mut self) -> Option<&'a mut V> {
2138 self.inner.next().map(|(_, v: &'a mut V)| v)
2139 }
2140 #[inline]
2141 fn size_hint(&self) -> (usize, Option<usize>) {
2142 self.inner.size_hint()
2143 }
2144 #[inline]
2145 fn count(self) -> usize {
2146 self.inner.len()
2147 }
2148 #[inline]
2149 fn fold<B, F>(self, init: B, mut f: F) -> B
2150 where
2151 Self: Sized,
2152 F: FnMut(B, Self::Item) -> B,
2153 {
2154 self.inner.fold(init, |acc: B, (_, v: &'a mut V)| f(acc, v))
2155 }
2156}
2157#[stable(feature = "map_values_mut", since = "1.10.0")]
2158impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> {
2159 #[inline]
2160 fn len(&self) -> usize {
2161 self.inner.len()
2162 }
2163}
2164#[stable(feature = "fused", since = "1.26.0")]
2165impl<K, V> FusedIterator for ValuesMut<'_, K, V> {}
2166
2167#[stable(feature = "std_debug", since = "1.16.0")]
2168impl<K, V: fmt::Debug> fmt::Debug for ValuesMut<'_, K, V> {
2169 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2170 f.debug_list().entries(self.inner.iter().map(|(_, val: &V)| val)).finish()
2171 }
2172}
2173
2174#[stable(feature = "map_into_keys_values", since = "1.54.0")]
2175impl<K, V> Iterator for IntoKeys<K, V> {
2176 type Item = K;
2177
2178 #[inline]
2179 fn next(&mut self) -> Option<K> {
2180 self.inner.next().map(|(k: K, _)| k)
2181 }
2182 #[inline]
2183 fn size_hint(&self) -> (usize, Option<usize>) {
2184 self.inner.size_hint()
2185 }
2186 #[inline]
2187 fn count(self) -> usize {
2188 self.inner.len()
2189 }
2190 #[inline]
2191 fn fold<B, F>(self, init: B, mut f: F) -> B
2192 where
2193 Self: Sized,
2194 F: FnMut(B, Self::Item) -> B,
2195 {
2196 self.inner.fold(init, |acc: B, (k: K, _)| f(acc, k))
2197 }
2198}
2199#[stable(feature = "map_into_keys_values", since = "1.54.0")]
2200impl<K, V> ExactSizeIterator for IntoKeys<K, V> {
2201 #[inline]
2202 fn len(&self) -> usize {
2203 self.inner.len()
2204 }
2205}
2206#[stable(feature = "map_into_keys_values", since = "1.54.0")]
2207impl<K, V> FusedIterator for IntoKeys<K, V> {}
2208
2209#[stable(feature = "map_into_keys_values", since = "1.54.0")]
2210impl<K: Debug, V> fmt::Debug for IntoKeys<K, V> {
2211 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2212 f.debug_list().entries(self.inner.iter().map(|(k: &K, _)| k)).finish()
2213 }
2214}
2215
2216#[stable(feature = "map_into_keys_values", since = "1.54.0")]
2217impl<K, V> Iterator for IntoValues<K, V> {
2218 type Item = V;
2219
2220 #[inline]
2221 fn next(&mut self) -> Option<V> {
2222 self.inner.next().map(|(_, v: V)| v)
2223 }
2224 #[inline]
2225 fn size_hint(&self) -> (usize, Option<usize>) {
2226 self.inner.size_hint()
2227 }
2228 #[inline]
2229 fn count(self) -> usize {
2230 self.inner.len()
2231 }
2232 #[inline]
2233 fn fold<B, F>(self, init: B, mut f: F) -> B
2234 where
2235 Self: Sized,
2236 F: FnMut(B, Self::Item) -> B,
2237 {
2238 self.inner.fold(init, |acc: B, (_, v: V)| f(acc, v))
2239 }
2240}
2241#[stable(feature = "map_into_keys_values", since = "1.54.0")]
2242impl<K, V> ExactSizeIterator for IntoValues<K, V> {
2243 #[inline]
2244 fn len(&self) -> usize {
2245 self.inner.len()
2246 }
2247}
2248#[stable(feature = "map_into_keys_values", since = "1.54.0")]
2249impl<K, V> FusedIterator for IntoValues<K, V> {}
2250
2251#[stable(feature = "map_into_keys_values", since = "1.54.0")]
2252impl<K, V: Debug> fmt::Debug for IntoValues<K, V> {
2253 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2254 f.debug_list().entries(self.inner.iter().map(|(_, v: &V)| v)).finish()
2255 }
2256}
2257
2258#[stable(feature = "drain", since = "1.6.0")]
2259impl<'a, K, V> Iterator for Drain<'a, K, V> {
2260 type Item = (K, V);
2261
2262 #[inline]
2263 fn next(&mut self) -> Option<(K, V)> {
2264 self.base.next()
2265 }
2266 #[inline]
2267 fn size_hint(&self) -> (usize, Option<usize>) {
2268 self.base.size_hint()
2269 }
2270 #[inline]
2271 fn fold<B, F>(self, init: B, f: F) -> B
2272 where
2273 Self: Sized,
2274 F: FnMut(B, Self::Item) -> B,
2275 {
2276 self.base.fold(init, f)
2277 }
2278}
2279#[stable(feature = "drain", since = "1.6.0")]
2280impl<K, V> ExactSizeIterator for Drain<'_, K, V> {
2281 #[inline]
2282 fn len(&self) -> usize {
2283 self.base.len()
2284 }
2285}
2286#[stable(feature = "fused", since = "1.26.0")]
2287impl<K, V> FusedIterator for Drain<'_, K, V> {}
2288
2289#[stable(feature = "std_debug", since = "1.16.0")]
2290impl<K, V> fmt::Debug for Drain<'_, K, V>
2291where
2292 K: fmt::Debug,
2293 V: fmt::Debug,
2294{
2295 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2296 f.debug_list().entries(self.iter()).finish()
2297 }
2298}
2299
2300#[unstable(feature = "hash_extract_if", issue = "59618")]
2301impl<K, V, F> Iterator for ExtractIf<'_, K, V, F>
2302where
2303 F: FnMut(&K, &mut V) -> bool,
2304{
2305 type Item = (K, V);
2306
2307 #[inline]
2308 fn next(&mut self) -> Option<(K, V)> {
2309 self.base.next()
2310 }
2311 #[inline]
2312 fn size_hint(&self) -> (usize, Option<usize>) {
2313 self.base.size_hint()
2314 }
2315}
2316
2317#[unstable(feature = "hash_extract_if", issue = "59618")]
2318impl<K, V, F> FusedIterator for ExtractIf<'_, K, V, F> where F: FnMut(&K, &mut V) -> bool {}
2319
2320#[unstable(feature = "hash_extract_if", issue = "59618")]
2321impl<'a, K, V, F> fmt::Debug for ExtractIf<'a, K, V, F>
2322where
2323 F: FnMut(&K, &mut V) -> bool,
2324{
2325 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2326 f.debug_struct(name:"ExtractIf").finish_non_exhaustive()
2327 }
2328}
2329
2330impl<'a, K, V> Entry<'a, K, V> {
2331 /// Ensures a value is in the entry by inserting the default if empty, and returns
2332 /// a mutable reference to the value in the entry.
2333 ///
2334 /// # Examples
2335 ///
2336 /// ```
2337 /// use std::collections::HashMap;
2338 ///
2339 /// let mut map: HashMap<&str, u32> = HashMap::new();
2340 ///
2341 /// map.entry("poneyland").or_insert(3);
2342 /// assert_eq!(map["poneyland"], 3);
2343 ///
2344 /// *map.entry("poneyland").or_insert(10) *= 2;
2345 /// assert_eq!(map["poneyland"], 6);
2346 /// ```
2347 #[inline]
2348 #[stable(feature = "rust1", since = "1.0.0")]
2349 pub fn or_insert(self, default: V) -> &'a mut V {
2350 match self {
2351 Occupied(entry) => entry.into_mut(),
2352 Vacant(entry) => entry.insert(default),
2353 }
2354 }
2355
2356 /// Ensures a value is in the entry by inserting the result of the default function if empty,
2357 /// and returns a mutable reference to the value in the entry.
2358 ///
2359 /// # Examples
2360 ///
2361 /// ```
2362 /// use std::collections::HashMap;
2363 ///
2364 /// let mut map = HashMap::new();
2365 /// let value = "hoho";
2366 ///
2367 /// map.entry("poneyland").or_insert_with(|| value);
2368 ///
2369 /// assert_eq!(map["poneyland"], "hoho");
2370 /// ```
2371 #[inline]
2372 #[stable(feature = "rust1", since = "1.0.0")]
2373 pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
2374 match self {
2375 Occupied(entry) => entry.into_mut(),
2376 Vacant(entry) => entry.insert(default()),
2377 }
2378 }
2379
2380 /// Ensures a value is in the entry by inserting, if empty, the result of the default function.
2381 /// This method allows for generating key-derived values for insertion by providing the default
2382 /// function a reference to the key that was moved during the `.entry(key)` method call.
2383 ///
2384 /// The reference to the moved key is provided so that cloning or copying the key is
2385 /// unnecessary, unlike with `.or_insert_with(|| ... )`.
2386 ///
2387 /// # Examples
2388 ///
2389 /// ```
2390 /// use std::collections::HashMap;
2391 ///
2392 /// let mut map: HashMap<&str, usize> = HashMap::new();
2393 ///
2394 /// map.entry("poneyland").or_insert_with_key(|key| key.chars().count());
2395 ///
2396 /// assert_eq!(map["poneyland"], 9);
2397 /// ```
2398 #[inline]
2399 #[stable(feature = "or_insert_with_key", since = "1.50.0")]
2400 pub fn or_insert_with_key<F: FnOnce(&K) -> V>(self, default: F) -> &'a mut V {
2401 match self {
2402 Occupied(entry) => entry.into_mut(),
2403 Vacant(entry) => {
2404 let value = default(entry.key());
2405 entry.insert(value)
2406 }
2407 }
2408 }
2409
2410 /// Returns a reference to this entry's key.
2411 ///
2412 /// # Examples
2413 ///
2414 /// ```
2415 /// use std::collections::HashMap;
2416 ///
2417 /// let mut map: HashMap<&str, u32> = HashMap::new();
2418 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
2419 /// ```
2420 #[inline]
2421 #[stable(feature = "map_entry_keys", since = "1.10.0")]
2422 pub fn key(&self) -> &K {
2423 match *self {
2424 Occupied(ref entry) => entry.key(),
2425 Vacant(ref entry) => entry.key(),
2426 }
2427 }
2428
2429 /// Provides in-place mutable access to an occupied entry before any
2430 /// potential inserts into the map.
2431 ///
2432 /// # Examples
2433 ///
2434 /// ```
2435 /// use std::collections::HashMap;
2436 ///
2437 /// let mut map: HashMap<&str, u32> = HashMap::new();
2438 ///
2439 /// map.entry("poneyland")
2440 /// .and_modify(|e| { *e += 1 })
2441 /// .or_insert(42);
2442 /// assert_eq!(map["poneyland"], 42);
2443 ///
2444 /// map.entry("poneyland")
2445 /// .and_modify(|e| { *e += 1 })
2446 /// .or_insert(42);
2447 /// assert_eq!(map["poneyland"], 43);
2448 /// ```
2449 #[inline]
2450 #[stable(feature = "entry_and_modify", since = "1.26.0")]
2451 pub fn and_modify<F>(self, f: F) -> Self
2452 where
2453 F: FnOnce(&mut V),
2454 {
2455 match self {
2456 Occupied(mut entry) => {
2457 f(entry.get_mut());
2458 Occupied(entry)
2459 }
2460 Vacant(entry) => Vacant(entry),
2461 }
2462 }
2463
2464 /// Sets the value of the entry, and returns an `OccupiedEntry`.
2465 ///
2466 /// # Examples
2467 ///
2468 /// ```
2469 /// use std::collections::HashMap;
2470 ///
2471 /// let mut map: HashMap<&str, String> = HashMap::new();
2472 /// let entry = map.entry("poneyland").insert_entry("hoho".to_string());
2473 ///
2474 /// assert_eq!(entry.key(), &"poneyland");
2475 /// ```
2476 #[inline]
2477 #[stable(feature = "entry_insert", since = "1.83.0")]
2478 pub fn insert_entry(self, value: V) -> OccupiedEntry<'a, K, V> {
2479 match self {
2480 Occupied(mut entry) => {
2481 entry.insert(value);
2482 entry
2483 }
2484 Vacant(entry) => entry.insert_entry(value),
2485 }
2486 }
2487}
2488
2489impl<'a, K, V: Default> Entry<'a, K, V> {
2490 /// Ensures a value is in the entry by inserting the default value if empty,
2491 /// and returns a mutable reference to the value in the entry.
2492 ///
2493 /// # Examples
2494 ///
2495 /// ```
2496 /// # fn main() {
2497 /// use std::collections::HashMap;
2498 ///
2499 /// let mut map: HashMap<&str, Option<u32>> = HashMap::new();
2500 /// map.entry("poneyland").or_default();
2501 ///
2502 /// assert_eq!(map["poneyland"], None);
2503 /// # }
2504 /// ```
2505 #[inline]
2506 #[stable(feature = "entry_or_default", since = "1.28.0")]
2507 pub fn or_default(self) -> &'a mut V {
2508 match self {
2509 Occupied(entry) => entry.into_mut(),
2510 Vacant(entry) => entry.insert(Default::default()),
2511 }
2512 }
2513}
2514
2515impl<'a, K, V> OccupiedEntry<'a, K, V> {
2516 /// Gets a reference to the key in the entry.
2517 ///
2518 /// # Examples
2519 ///
2520 /// ```
2521 /// use std::collections::HashMap;
2522 ///
2523 /// let mut map: HashMap<&str, u32> = HashMap::new();
2524 /// map.entry("poneyland").or_insert(12);
2525 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
2526 /// ```
2527 #[inline]
2528 #[stable(feature = "map_entry_keys", since = "1.10.0")]
2529 pub fn key(&self) -> &K {
2530 self.base.key()
2531 }
2532
2533 /// Take the ownership of the key and value from the map.
2534 ///
2535 /// # Examples
2536 ///
2537 /// ```
2538 /// use std::collections::HashMap;
2539 /// use std::collections::hash_map::Entry;
2540 ///
2541 /// let mut map: HashMap<&str, u32> = HashMap::new();
2542 /// map.entry("poneyland").or_insert(12);
2543 ///
2544 /// if let Entry::Occupied(o) = map.entry("poneyland") {
2545 /// // We delete the entry from the map.
2546 /// o.remove_entry();
2547 /// }
2548 ///
2549 /// assert_eq!(map.contains_key("poneyland"), false);
2550 /// ```
2551 #[inline]
2552 #[stable(feature = "map_entry_recover_keys2", since = "1.12.0")]
2553 pub fn remove_entry(self) -> (K, V) {
2554 self.base.remove_entry()
2555 }
2556
2557 /// Gets a reference to the value in the entry.
2558 ///
2559 /// # Examples
2560 ///
2561 /// ```
2562 /// use std::collections::HashMap;
2563 /// use std::collections::hash_map::Entry;
2564 ///
2565 /// let mut map: HashMap<&str, u32> = HashMap::new();
2566 /// map.entry("poneyland").or_insert(12);
2567 ///
2568 /// if let Entry::Occupied(o) = map.entry("poneyland") {
2569 /// assert_eq!(o.get(), &12);
2570 /// }
2571 /// ```
2572 #[inline]
2573 #[stable(feature = "rust1", since = "1.0.0")]
2574 pub fn get(&self) -> &V {
2575 self.base.get()
2576 }
2577
2578 /// Gets a mutable reference to the value in the entry.
2579 ///
2580 /// If you need a reference to the `OccupiedEntry` which may outlive the
2581 /// destruction of the `Entry` value, see [`into_mut`].
2582 ///
2583 /// [`into_mut`]: Self::into_mut
2584 ///
2585 /// # Examples
2586 ///
2587 /// ```
2588 /// use std::collections::HashMap;
2589 /// use std::collections::hash_map::Entry;
2590 ///
2591 /// let mut map: HashMap<&str, u32> = HashMap::new();
2592 /// map.entry("poneyland").or_insert(12);
2593 ///
2594 /// assert_eq!(map["poneyland"], 12);
2595 /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
2596 /// *o.get_mut() += 10;
2597 /// assert_eq!(*o.get(), 22);
2598 ///
2599 /// // We can use the same Entry multiple times.
2600 /// *o.get_mut() += 2;
2601 /// }
2602 ///
2603 /// assert_eq!(map["poneyland"], 24);
2604 /// ```
2605 #[inline]
2606 #[stable(feature = "rust1", since = "1.0.0")]
2607 pub fn get_mut(&mut self) -> &mut V {
2608 self.base.get_mut()
2609 }
2610
2611 /// Converts the `OccupiedEntry` into a mutable reference to the value in the entry
2612 /// with a lifetime bound to the map itself.
2613 ///
2614 /// If you need multiple references to the `OccupiedEntry`, see [`get_mut`].
2615 ///
2616 /// [`get_mut`]: Self::get_mut
2617 ///
2618 /// # Examples
2619 ///
2620 /// ```
2621 /// use std::collections::HashMap;
2622 /// use std::collections::hash_map::Entry;
2623 ///
2624 /// let mut map: HashMap<&str, u32> = HashMap::new();
2625 /// map.entry("poneyland").or_insert(12);
2626 ///
2627 /// assert_eq!(map["poneyland"], 12);
2628 /// if let Entry::Occupied(o) = map.entry("poneyland") {
2629 /// *o.into_mut() += 10;
2630 /// }
2631 ///
2632 /// assert_eq!(map["poneyland"], 22);
2633 /// ```
2634 #[inline]
2635 #[stable(feature = "rust1", since = "1.0.0")]
2636 pub fn into_mut(self) -> &'a mut V {
2637 self.base.into_mut()
2638 }
2639
2640 /// Sets the value of the entry, and returns the entry's old value.
2641 ///
2642 /// # Examples
2643 ///
2644 /// ```
2645 /// use std::collections::HashMap;
2646 /// use std::collections::hash_map::Entry;
2647 ///
2648 /// let mut map: HashMap<&str, u32> = HashMap::new();
2649 /// map.entry("poneyland").or_insert(12);
2650 ///
2651 /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
2652 /// assert_eq!(o.insert(15), 12);
2653 /// }
2654 ///
2655 /// assert_eq!(map["poneyland"], 15);
2656 /// ```
2657 #[inline]
2658 #[stable(feature = "rust1", since = "1.0.0")]
2659 pub fn insert(&mut self, value: V) -> V {
2660 self.base.insert(value)
2661 }
2662
2663 /// Takes the value out of the entry, and returns it.
2664 ///
2665 /// # Examples
2666 ///
2667 /// ```
2668 /// use std::collections::HashMap;
2669 /// use std::collections::hash_map::Entry;
2670 ///
2671 /// let mut map: HashMap<&str, u32> = HashMap::new();
2672 /// map.entry("poneyland").or_insert(12);
2673 ///
2674 /// if let Entry::Occupied(o) = map.entry("poneyland") {
2675 /// assert_eq!(o.remove(), 12);
2676 /// }
2677 ///
2678 /// assert_eq!(map.contains_key("poneyland"), false);
2679 /// ```
2680 #[inline]
2681 #[stable(feature = "rust1", since = "1.0.0")]
2682 pub fn remove(self) -> V {
2683 self.base.remove()
2684 }
2685}
2686
2687impl<'a, K: 'a, V: 'a> VacantEntry<'a, K, V> {
2688 /// Gets a reference to the key that would be used when inserting a value
2689 /// through the `VacantEntry`.
2690 ///
2691 /// # Examples
2692 ///
2693 /// ```
2694 /// use std::collections::HashMap;
2695 ///
2696 /// let mut map: HashMap<&str, u32> = HashMap::new();
2697 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
2698 /// ```
2699 #[inline]
2700 #[stable(feature = "map_entry_keys", since = "1.10.0")]
2701 pub fn key(&self) -> &K {
2702 self.base.key()
2703 }
2704
2705 /// Take ownership of the key.
2706 ///
2707 /// # Examples
2708 ///
2709 /// ```
2710 /// use std::collections::HashMap;
2711 /// use std::collections::hash_map::Entry;
2712 ///
2713 /// let mut map: HashMap<&str, u32> = HashMap::new();
2714 ///
2715 /// if let Entry::Vacant(v) = map.entry("poneyland") {
2716 /// v.into_key();
2717 /// }
2718 /// ```
2719 #[inline]
2720 #[stable(feature = "map_entry_recover_keys2", since = "1.12.0")]
2721 pub fn into_key(self) -> K {
2722 self.base.into_key()
2723 }
2724
2725 /// Sets the value of the entry with the `VacantEntry`'s key,
2726 /// and returns a mutable reference to it.
2727 ///
2728 /// # Examples
2729 ///
2730 /// ```
2731 /// use std::collections::HashMap;
2732 /// use std::collections::hash_map::Entry;
2733 ///
2734 /// let mut map: HashMap<&str, u32> = HashMap::new();
2735 ///
2736 /// if let Entry::Vacant(o) = map.entry("poneyland") {
2737 /// o.insert(37);
2738 /// }
2739 /// assert_eq!(map["poneyland"], 37);
2740 /// ```
2741 #[inline]
2742 #[stable(feature = "rust1", since = "1.0.0")]
2743 pub fn insert(self, value: V) -> &'a mut V {
2744 self.base.insert(value)
2745 }
2746
2747 /// Sets the value of the entry with the `VacantEntry`'s key,
2748 /// and returns an `OccupiedEntry`.
2749 ///
2750 /// # Examples
2751 ///
2752 /// ```
2753 /// use std::collections::HashMap;
2754 /// use std::collections::hash_map::Entry;
2755 ///
2756 /// let mut map: HashMap<&str, u32> = HashMap::new();
2757 ///
2758 /// if let Entry::Vacant(o) = map.entry("poneyland") {
2759 /// o.insert_entry(37);
2760 /// }
2761 /// assert_eq!(map["poneyland"], 37);
2762 /// ```
2763 #[inline]
2764 #[stable(feature = "entry_insert", since = "1.83.0")]
2765 pub fn insert_entry(self, value: V) -> OccupiedEntry<'a, K, V> {
2766 let base = self.base.insert_entry(value);
2767 OccupiedEntry { base }
2768 }
2769}
2770
2771#[stable(feature = "rust1", since = "1.0.0")]
2772impl<K, V, S> FromIterator<(K, V)> for HashMap<K, V, S>
2773where
2774 K: Eq + Hash,
2775 S: BuildHasher + Default,
2776{
2777 /// Constructs a `HashMap<K, V>` from an iterator of key-value pairs.
2778 ///
2779 /// If the iterator produces any pairs with equal keys,
2780 /// all but one of the corresponding values will be dropped.
2781 fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> HashMap<K, V, S> {
2782 let mut map: HashMap = HashMap::with_hasher(hash_builder:Default::default());
2783 map.extend(iter);
2784 map
2785 }
2786}
2787
2788/// Inserts all new key-values from the iterator and replaces values with existing
2789/// keys with new values returned from the iterator.
2790#[stable(feature = "rust1", since = "1.0.0")]
2791impl<K, V, S> Extend<(K, V)> for HashMap<K, V, S>
2792where
2793 K: Eq + Hash,
2794 S: BuildHasher,
2795{
2796 #[inline]
2797 fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
2798 self.base.extend(iter)
2799 }
2800
2801 #[inline]
2802 fn extend_one(&mut self, (k: K, v: V): (K, V)) {
2803 self.base.insert(k, v);
2804 }
2805
2806 #[inline]
2807 fn extend_reserve(&mut self, additional: usize) {
2808 self.base.extend_reserve(additional);
2809 }
2810}
2811
2812#[stable(feature = "hash_extend_copy", since = "1.4.0")]
2813impl<'a, K, V, S> Extend<(&'a K, &'a V)> for HashMap<K, V, S>
2814where
2815 K: Eq + Hash + Copy,
2816 V: Copy,
2817 S: BuildHasher,
2818{
2819 #[inline]
2820 fn extend<T: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: T) {
2821 self.base.extend(iter)
2822 }
2823
2824 #[inline]
2825 fn extend_one(&mut self, (&k: K, &v: V): (&'a K, &'a V)) {
2826 self.base.insert(k, v);
2827 }
2828
2829 #[inline]
2830 fn extend_reserve(&mut self, additional: usize) {
2831 Extend::<(K, V)>::extend_reserve(self, additional)
2832 }
2833}
2834
2835#[inline]
2836fn map_entry<'a, K: 'a, V: 'a>(raw: base::RustcEntry<'a, K, V>) -> Entry<'a, K, V> {
2837 match raw {
2838 base::RustcEntry::Occupied(base: RustcOccupiedEntry<'_, K, …>) => Entry::Occupied(OccupiedEntry { base }),
2839 base::RustcEntry::Vacant(base: RustcVacantEntry<'_, K, V>) => Entry::Vacant(VacantEntry { base }),
2840 }
2841}
2842
2843#[inline]
2844pub(super) fn map_try_reserve_error(err: hashbrown::TryReserveError) -> TryReserveError {
2845 match err {
2846 hashbrown::TryReserveError::CapacityOverflow => {
2847 TryReserveErrorKind::CapacityOverflow.into()
2848 }
2849 hashbrown::TryReserveError::AllocError { layout: Layout } => {
2850 TryReserveErrorKind::AllocError { layout, non_exhaustive: () }.into()
2851 }
2852 }
2853}
2854
2855#[allow(dead_code)]
2856fn assert_covariance() {
2857 fn map_key<'new>(v: HashMap<&'static str, u8>) -> HashMap<&'new str, u8> {
2858 v
2859 }
2860 fn map_val<'new>(v: HashMap<u8, &'static str>) -> HashMap<u8, &'new str> {
2861 v
2862 }
2863 fn iter_key<'a, 'new>(v: Iter<'a, &'static str, u8>) -> Iter<'a, &'new str, u8> {
2864 v
2865 }
2866 fn iter_val<'a, 'new>(v: Iter<'a, u8, &'static str>) -> Iter<'a, u8, &'new str> {
2867 v
2868 }
2869 fn into_iter_key<'new>(v: IntoIter<&'static str, u8>) -> IntoIter<&'new str, u8> {
2870 v
2871 }
2872 fn into_iter_val<'new>(v: IntoIter<u8, &'static str>) -> IntoIter<u8, &'new str> {
2873 v
2874 }
2875 fn keys_key<'a, 'new>(v: Keys<'a, &'static str, u8>) -> Keys<'a, &'new str, u8> {
2876 v
2877 }
2878 fn keys_val<'a, 'new>(v: Keys<'a, u8, &'static str>) -> Keys<'a, u8, &'new str> {
2879 v
2880 }
2881 fn values_key<'a, 'new>(v: Values<'a, &'static str, u8>) -> Values<'a, &'new str, u8> {
2882 v
2883 }
2884 fn values_val<'a, 'new>(v: Values<'a, u8, &'static str>) -> Values<'a, u8, &'new str> {
2885 v
2886 }
2887 fn drain<'new>(
2888 d: Drain<'static, &'static str, &'static str>,
2889 ) -> Drain<'new, &'new str, &'new str> {
2890 d
2891 }
2892}
2893