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