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