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