1 | //! `IndexMap` is a hash table where the iteration order of the key-value |
2 | //! pairs is independent of the hash values of the keys. |
3 | |
4 | mod core; |
5 | mod iter; |
6 | mod slice; |
7 | |
8 | #[cfg (feature = "serde" )] |
9 | #[cfg_attr (docsrs, doc(cfg(feature = "serde" )))] |
10 | pub mod serde_seq; |
11 | |
12 | #[cfg (test)] |
13 | mod tests; |
14 | |
15 | pub use self::core::{Entry, OccupiedEntry, VacantEntry}; |
16 | pub use self::iter::{ |
17 | Drain, IntoIter, IntoKeys, IntoValues, Iter, IterMut, Keys, Values, ValuesMut, |
18 | }; |
19 | pub use self::slice::Slice; |
20 | pub use crate::mutable_keys::MutableKeys; |
21 | |
22 | #[cfg (feature = "rayon" )] |
23 | pub use crate::rayon::map as rayon; |
24 | |
25 | use ::core::cmp::Ordering; |
26 | use ::core::fmt; |
27 | use ::core::hash::{BuildHasher, Hash, Hasher}; |
28 | use ::core::ops::{Index, IndexMut, RangeBounds}; |
29 | use alloc::boxed::Box; |
30 | use alloc::vec::Vec; |
31 | |
32 | #[cfg (feature = "std" )] |
33 | use std::collections::hash_map::RandomState; |
34 | |
35 | use self::core::IndexMapCore; |
36 | use crate::util::{third, try_simplify_range}; |
37 | use crate::{Bucket, Entries, Equivalent, HashValue, TryReserveError}; |
38 | |
39 | /// A hash table where the iteration order of the key-value pairs is independent |
40 | /// of the hash values of the keys. |
41 | /// |
42 | /// The interface is closely compatible with the standard `HashMap`, but also |
43 | /// has additional features. |
44 | /// |
45 | /// # Order |
46 | /// |
47 | /// The key-value pairs have a consistent order that is determined by |
48 | /// the sequence of insertion and removal calls on the map. The order does |
49 | /// not depend on the keys or the hash function at all. |
50 | /// |
51 | /// All iterators traverse the map in *the order*. |
52 | /// |
53 | /// The insertion order is preserved, with **notable exceptions** like the |
54 | /// `.remove()` or `.swap_remove()` methods. Methods such as `.sort_by()` of |
55 | /// course result in a new order, depending on the sorting order. |
56 | /// |
57 | /// # Indices |
58 | /// |
59 | /// The key-value pairs are indexed in a compact range without holes in the |
60 | /// range `0..self.len()`. For example, the method `.get_full` looks up the |
61 | /// index for a key, and the method `.get_index` looks up the key-value pair by |
62 | /// index. |
63 | /// |
64 | /// # Examples |
65 | /// |
66 | /// ``` |
67 | /// use indexmap::IndexMap; |
68 | /// |
69 | /// // count the frequency of each letter in a sentence. |
70 | /// let mut letters = IndexMap::new(); |
71 | /// for ch in "a short treatise on fungi" .chars() { |
72 | /// *letters.entry(ch).or_insert(0) += 1; |
73 | /// } |
74 | /// |
75 | /// assert_eq!(letters[&'s' ], 2); |
76 | /// assert_eq!(letters[&'t' ], 3); |
77 | /// assert_eq!(letters[&'u' ], 1); |
78 | /// assert_eq!(letters.get(&'y' ), None); |
79 | /// ``` |
80 | #[cfg (feature = "std" )] |
81 | pub struct IndexMap<K, V, S = RandomState> { |
82 | pub(crate) core: IndexMapCore<K, V>, |
83 | hash_builder: S, |
84 | } |
85 | #[cfg (not(feature = "std" ))] |
86 | pub struct IndexMap<K, V, S> { |
87 | pub(crate) core: IndexMapCore<K, V>, |
88 | hash_builder: S, |
89 | } |
90 | |
91 | impl<K, V, S> Clone for IndexMap<K, V, S> |
92 | where |
93 | K: Clone, |
94 | V: Clone, |
95 | S: Clone, |
96 | { |
97 | fn clone(&self) -> Self { |
98 | IndexMap { |
99 | core: self.core.clone(), |
100 | hash_builder: self.hash_builder.clone(), |
101 | } |
102 | } |
103 | |
104 | fn clone_from(&mut self, other: &Self) { |
105 | self.core.clone_from(&other.core); |
106 | self.hash_builder.clone_from(&other.hash_builder); |
107 | } |
108 | } |
109 | |
110 | impl<K, V, S> Entries for IndexMap<K, V, S> { |
111 | type Entry = Bucket<K, V>; |
112 | |
113 | #[inline ] |
114 | fn into_entries(self) -> Vec<Self::Entry> { |
115 | self.core.into_entries() |
116 | } |
117 | |
118 | #[inline ] |
119 | fn as_entries(&self) -> &[Self::Entry] { |
120 | self.core.as_entries() |
121 | } |
122 | |
123 | #[inline ] |
124 | fn as_entries_mut(&mut self) -> &mut [Self::Entry] { |
125 | self.core.as_entries_mut() |
126 | } |
127 | |
128 | fn with_entries<F>(&mut self, f: F) |
129 | where |
130 | F: FnOnce(&mut [Self::Entry]), |
131 | { |
132 | self.core.with_entries(f); |
133 | } |
134 | } |
135 | |
136 | impl<K, V, S> fmt::Debug for IndexMap<K, V, S> |
137 | where |
138 | K: fmt::Debug, |
139 | V: fmt::Debug, |
140 | { |
141 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
142 | if cfg!(not(feature = "test_debug" )) { |
143 | f.debug_map().entries(self.iter()).finish() |
144 | } else { |
145 | // Let the inner `IndexMapCore` print all of its details |
146 | f&mut DebugStruct<'_, '_>.debug_struct("IndexMap" ) |
147 | .field(name:"core" , &self.core) |
148 | .finish() |
149 | } |
150 | } |
151 | } |
152 | |
153 | #[cfg (feature = "std" )] |
154 | #[cfg_attr (docsrs, doc(cfg(feature = "std" )))] |
155 | impl<K, V> IndexMap<K, V> { |
156 | /// Create a new map. (Does not allocate.) |
157 | #[inline ] |
158 | pub fn new() -> Self { |
159 | Self::with_capacity(0) |
160 | } |
161 | |
162 | /// Create a new map with capacity for `n` key-value pairs. (Does not |
163 | /// allocate if `n` is zero.) |
164 | /// |
165 | /// Computes in **O(n)** time. |
166 | #[inline ] |
167 | pub fn with_capacity(n: usize) -> Self { |
168 | Self::with_capacity_and_hasher(n, <_>::default()) |
169 | } |
170 | } |
171 | |
172 | impl<K, V, S> IndexMap<K, V, S> { |
173 | /// Create a new map with capacity for `n` key-value pairs. (Does not |
174 | /// allocate if `n` is zero.) |
175 | /// |
176 | /// Computes in **O(n)** time. |
177 | #[inline ] |
178 | pub fn with_capacity_and_hasher(n: usize, hash_builder: S) -> Self { |
179 | if n == 0 { |
180 | Self::with_hasher(hash_builder) |
181 | } else { |
182 | IndexMap { |
183 | core: IndexMapCore::with_capacity(n), |
184 | hash_builder, |
185 | } |
186 | } |
187 | } |
188 | |
189 | /// Create a new map with `hash_builder`. |
190 | /// |
191 | /// This function is `const`, so it |
192 | /// can be called in `static` contexts. |
193 | pub const fn with_hasher(hash_builder: S) -> Self { |
194 | IndexMap { |
195 | core: IndexMapCore::new(), |
196 | hash_builder, |
197 | } |
198 | } |
199 | |
200 | /// Return the number of elements the map can hold without reallocating. |
201 | /// |
202 | /// This number is a lower bound; the map might be able to hold more, |
203 | /// but is guaranteed to be able to hold at least this many. |
204 | /// |
205 | /// Computes in **O(1)** time. |
206 | pub fn capacity(&self) -> usize { |
207 | self.core.capacity() |
208 | } |
209 | |
210 | /// Return a reference to the map's `BuildHasher`. |
211 | pub fn hasher(&self) -> &S { |
212 | &self.hash_builder |
213 | } |
214 | |
215 | /// Return the number of key-value pairs in the map. |
216 | /// |
217 | /// Computes in **O(1)** time. |
218 | #[inline ] |
219 | pub fn len(&self) -> usize { |
220 | self.core.len() |
221 | } |
222 | |
223 | /// Returns true if the map contains no elements. |
224 | /// |
225 | /// Computes in **O(1)** time. |
226 | #[inline ] |
227 | pub fn is_empty(&self) -> bool { |
228 | self.len() == 0 |
229 | } |
230 | |
231 | /// Return an iterator over the key-value pairs of the map, in their order |
232 | pub fn iter(&self) -> Iter<'_, K, V> { |
233 | Iter::new(self.as_entries()) |
234 | } |
235 | |
236 | /// Return an iterator over the key-value pairs of the map, in their order |
237 | pub fn iter_mut(&mut self) -> IterMut<'_, K, V> { |
238 | IterMut::new(self.as_entries_mut()) |
239 | } |
240 | |
241 | /// Return an iterator over the keys of the map, in their order |
242 | pub fn keys(&self) -> Keys<'_, K, V> { |
243 | Keys::new(self.as_entries()) |
244 | } |
245 | |
246 | /// Return an owning iterator over the keys of the map, in their order |
247 | pub fn into_keys(self) -> IntoKeys<K, V> { |
248 | IntoKeys::new(self.into_entries()) |
249 | } |
250 | |
251 | /// Return an iterator over the values of the map, in their order |
252 | pub fn values(&self) -> Values<'_, K, V> { |
253 | Values::new(self.as_entries()) |
254 | } |
255 | |
256 | /// Return an iterator over mutable references to the values of the map, |
257 | /// in their order |
258 | pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> { |
259 | ValuesMut::new(self.as_entries_mut()) |
260 | } |
261 | |
262 | /// Return an owning iterator over the values of the map, in their order |
263 | pub fn into_values(self) -> IntoValues<K, V> { |
264 | IntoValues::new(self.into_entries()) |
265 | } |
266 | |
267 | /// Remove all key-value pairs in the map, while preserving its capacity. |
268 | /// |
269 | /// Computes in **O(n)** time. |
270 | pub fn clear(&mut self) { |
271 | self.core.clear(); |
272 | } |
273 | |
274 | /// Shortens the map, keeping the first `len` elements and dropping the rest. |
275 | /// |
276 | /// If `len` is greater than the map's current length, this has no effect. |
277 | pub fn truncate(&mut self, len: usize) { |
278 | self.core.truncate(len); |
279 | } |
280 | |
281 | /// Clears the `IndexMap` in the given index range, returning those |
282 | /// key-value pairs as a drain iterator. |
283 | /// |
284 | /// The range may be any type that implements `RangeBounds<usize>`, |
285 | /// including all of the `std::ops::Range*` types, or even a tuple pair of |
286 | /// `Bound` start and end values. To drain the map entirely, use `RangeFull` |
287 | /// like `map.drain(..)`. |
288 | /// |
289 | /// This shifts down all entries following the drained range to fill the |
290 | /// gap, and keeps the allocated memory for reuse. |
291 | /// |
292 | /// ***Panics*** if the starting point is greater than the end point or if |
293 | /// the end point is greater than the length of the map. |
294 | pub fn drain<R>(&mut self, range: R) -> Drain<'_, K, V> |
295 | where |
296 | R: RangeBounds<usize>, |
297 | { |
298 | Drain::new(self.core.drain(range)) |
299 | } |
300 | |
301 | /// Splits the collection into two at the given index. |
302 | /// |
303 | /// Returns a newly allocated map containing the elements in the range |
304 | /// `[at, len)`. After the call, the original map will be left containing |
305 | /// the elements `[0, at)` with its previous capacity unchanged. |
306 | /// |
307 | /// ***Panics*** if `at > len`. |
308 | pub fn split_off(&mut self, at: usize) -> Self |
309 | where |
310 | S: Clone, |
311 | { |
312 | Self { |
313 | core: self.core.split_off(at), |
314 | hash_builder: self.hash_builder.clone(), |
315 | } |
316 | } |
317 | } |
318 | |
319 | impl<K, V, S> IndexMap<K, V, S> |
320 | where |
321 | K: Hash + Eq, |
322 | S: BuildHasher, |
323 | { |
324 | /// Reserve capacity for `additional` more key-value pairs. |
325 | /// |
326 | /// Computes in **O(n)** time. |
327 | pub fn reserve(&mut self, additional: usize) { |
328 | self.core.reserve(additional); |
329 | } |
330 | |
331 | /// Reserve capacity for `additional` more key-value pairs, without over-allocating. |
332 | /// |
333 | /// Unlike `reserve`, this does not deliberately over-allocate the entry capacity to avoid |
334 | /// frequent re-allocations. However, the underlying data structures may still have internal |
335 | /// capacity requirements, and the allocator itself may give more space than requested, so this |
336 | /// cannot be relied upon to be precisely minimal. |
337 | /// |
338 | /// Computes in **O(n)** time. |
339 | pub fn reserve_exact(&mut self, additional: usize) { |
340 | self.core.reserve_exact(additional); |
341 | } |
342 | |
343 | /// Try to reserve capacity for `additional` more key-value pairs. |
344 | /// |
345 | /// Computes in **O(n)** time. |
346 | pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> { |
347 | self.core.try_reserve(additional) |
348 | } |
349 | |
350 | /// Try to reserve capacity for `additional` more key-value pairs, without over-allocating. |
351 | /// |
352 | /// Unlike `try_reserve`, this does not deliberately over-allocate the entry capacity to avoid |
353 | /// frequent re-allocations. However, the underlying data structures may still have internal |
354 | /// capacity requirements, and the allocator itself may give more space than requested, so this |
355 | /// cannot be relied upon to be precisely minimal. |
356 | /// |
357 | /// Computes in **O(n)** time. |
358 | pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> { |
359 | self.core.try_reserve_exact(additional) |
360 | } |
361 | |
362 | /// Shrink the capacity of the map as much as possible. |
363 | /// |
364 | /// Computes in **O(n)** time. |
365 | pub fn shrink_to_fit(&mut self) { |
366 | self.core.shrink_to(0); |
367 | } |
368 | |
369 | /// Shrink the capacity of the map with a lower limit. |
370 | /// |
371 | /// Computes in **O(n)** time. |
372 | pub fn shrink_to(&mut self, min_capacity: usize) { |
373 | self.core.shrink_to(min_capacity); |
374 | } |
375 | |
376 | fn hash<Q: ?Sized + Hash>(&self, key: &Q) -> HashValue { |
377 | let mut h = self.hash_builder.build_hasher(); |
378 | key.hash(&mut h); |
379 | HashValue(h.finish() as usize) |
380 | } |
381 | |
382 | /// Insert a key-value pair in the map. |
383 | /// |
384 | /// If an equivalent key already exists in the map: the key remains and |
385 | /// retains in its place in the order, its corresponding value is updated |
386 | /// with `value` and the older value is returned inside `Some(_)`. |
387 | /// |
388 | /// If no equivalent key existed in the map: the new key-value pair is |
389 | /// inserted, last in order, and `None` is returned. |
390 | /// |
391 | /// Computes in **O(1)** time (amortized average). |
392 | /// |
393 | /// See also [`entry`](#method.entry) if you you want to insert *or* modify |
394 | /// or if you need to get the index of the corresponding key-value pair. |
395 | pub fn insert(&mut self, key: K, value: V) -> Option<V> { |
396 | self.insert_full(key, value).1 |
397 | } |
398 | |
399 | /// Insert a key-value pair in the map, and get their index. |
400 | /// |
401 | /// If an equivalent key already exists in the map: the key remains and |
402 | /// retains in its place in the order, its corresponding value is updated |
403 | /// with `value` and the older value is returned inside `(index, Some(_))`. |
404 | /// |
405 | /// If no equivalent key existed in the map: the new key-value pair is |
406 | /// inserted, last in order, and `(index, None)` is returned. |
407 | /// |
408 | /// Computes in **O(1)** time (amortized average). |
409 | /// |
410 | /// See also [`entry`](#method.entry) if you you want to insert *or* modify |
411 | /// or if you need to get the index of the corresponding key-value pair. |
412 | pub fn insert_full(&mut self, key: K, value: V) -> (usize, Option<V>) { |
413 | let hash = self.hash(&key); |
414 | self.core.insert_full(hash, key, value) |
415 | } |
416 | |
417 | /// Get the given key’s corresponding entry in the map for insertion and/or |
418 | /// in-place manipulation. |
419 | /// |
420 | /// Computes in **O(1)** time (amortized average). |
421 | pub fn entry(&mut self, key: K) -> Entry<'_, K, V> { |
422 | let hash = self.hash(&key); |
423 | self.core.entry(hash, key) |
424 | } |
425 | |
426 | /// Return `true` if an equivalent to `key` exists in the map. |
427 | /// |
428 | /// Computes in **O(1)** time (average). |
429 | pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool |
430 | where |
431 | Q: Hash + Equivalent<K>, |
432 | { |
433 | self.get_index_of(key).is_some() |
434 | } |
435 | |
436 | /// Return a reference to the value stored for `key`, if it is present, |
437 | /// else `None`. |
438 | /// |
439 | /// Computes in **O(1)** time (average). |
440 | pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> |
441 | where |
442 | Q: Hash + Equivalent<K>, |
443 | { |
444 | if let Some(i) = self.get_index_of(key) { |
445 | let entry = &self.as_entries()[i]; |
446 | Some(&entry.value) |
447 | } else { |
448 | None |
449 | } |
450 | } |
451 | |
452 | /// Return references to the key-value pair stored for `key`, |
453 | /// if it is present, else `None`. |
454 | /// |
455 | /// Computes in **O(1)** time (average). |
456 | pub fn get_key_value<Q: ?Sized>(&self, key: &Q) -> Option<(&K, &V)> |
457 | where |
458 | Q: Hash + Equivalent<K>, |
459 | { |
460 | if let Some(i) = self.get_index_of(key) { |
461 | let entry = &self.as_entries()[i]; |
462 | Some((&entry.key, &entry.value)) |
463 | } else { |
464 | None |
465 | } |
466 | } |
467 | |
468 | /// Return item index, key and value |
469 | pub fn get_full<Q: ?Sized>(&self, key: &Q) -> Option<(usize, &K, &V)> |
470 | where |
471 | Q: Hash + Equivalent<K>, |
472 | { |
473 | if let Some(i) = self.get_index_of(key) { |
474 | let entry = &self.as_entries()[i]; |
475 | Some((i, &entry.key, &entry.value)) |
476 | } else { |
477 | None |
478 | } |
479 | } |
480 | |
481 | /// Return item index, if it exists in the map |
482 | /// |
483 | /// Computes in **O(1)** time (average). |
484 | pub fn get_index_of<Q: ?Sized>(&self, key: &Q) -> Option<usize> |
485 | where |
486 | Q: Hash + Equivalent<K>, |
487 | { |
488 | if self.is_empty() { |
489 | None |
490 | } else { |
491 | let hash = self.hash(key); |
492 | self.core.get_index_of(hash, key) |
493 | } |
494 | } |
495 | |
496 | pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> |
497 | where |
498 | Q: Hash + Equivalent<K>, |
499 | { |
500 | if let Some(i) = self.get_index_of(key) { |
501 | let entry = &mut self.as_entries_mut()[i]; |
502 | Some(&mut entry.value) |
503 | } else { |
504 | None |
505 | } |
506 | } |
507 | |
508 | pub fn get_full_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, &K, &mut V)> |
509 | where |
510 | Q: Hash + Equivalent<K>, |
511 | { |
512 | if let Some(i) = self.get_index_of(key) { |
513 | let entry = &mut self.as_entries_mut()[i]; |
514 | Some((i, &entry.key, &mut entry.value)) |
515 | } else { |
516 | None |
517 | } |
518 | } |
519 | |
520 | /// Remove the key-value pair equivalent to `key` and return |
521 | /// its value. |
522 | /// |
523 | /// **NOTE:** This is equivalent to `.swap_remove(key)`, if you need to |
524 | /// preserve the order of the keys in the map, use `.shift_remove(key)` |
525 | /// instead. |
526 | /// |
527 | /// Computes in **O(1)** time (average). |
528 | pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> |
529 | where |
530 | Q: Hash + Equivalent<K>, |
531 | { |
532 | self.swap_remove(key) |
533 | } |
534 | |
535 | /// Remove and return the key-value pair equivalent to `key`. |
536 | /// |
537 | /// **NOTE:** This is equivalent to `.swap_remove_entry(key)`, if you need to |
538 | /// preserve the order of the keys in the map, use `.shift_remove_entry(key)` |
539 | /// instead. |
540 | /// |
541 | /// Computes in **O(1)** time (average). |
542 | pub fn remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)> |
543 | where |
544 | Q: Hash + Equivalent<K>, |
545 | { |
546 | self.swap_remove_entry(key) |
547 | } |
548 | |
549 | /// Remove the key-value pair equivalent to `key` and return |
550 | /// its value. |
551 | /// |
552 | /// Like `Vec::swap_remove`, the pair is removed by swapping it with the |
553 | /// last element of the map and popping it off. **This perturbs |
554 | /// the position of what used to be the last element!** |
555 | /// |
556 | /// Return `None` if `key` is not in map. |
557 | /// |
558 | /// Computes in **O(1)** time (average). |
559 | pub fn swap_remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> |
560 | where |
561 | Q: Hash + Equivalent<K>, |
562 | { |
563 | self.swap_remove_full(key).map(third) |
564 | } |
565 | |
566 | /// Remove and return the key-value pair equivalent to `key`. |
567 | /// |
568 | /// Like `Vec::swap_remove`, the pair is removed by swapping it with the |
569 | /// last element of the map and popping it off. **This perturbs |
570 | /// the position of what used to be the last element!** |
571 | /// |
572 | /// Return `None` if `key` is not in map. |
573 | /// |
574 | /// Computes in **O(1)** time (average). |
575 | pub fn swap_remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)> |
576 | where |
577 | Q: Hash + Equivalent<K>, |
578 | { |
579 | match self.swap_remove_full(key) { |
580 | Some((_, key, value)) => Some((key, value)), |
581 | None => None, |
582 | } |
583 | } |
584 | |
585 | /// Remove the key-value pair equivalent to `key` and return it and |
586 | /// the index it had. |
587 | /// |
588 | /// Like `Vec::swap_remove`, the pair is removed by swapping it with the |
589 | /// last element of the map and popping it off. **This perturbs |
590 | /// the position of what used to be the last element!** |
591 | /// |
592 | /// Return `None` if `key` is not in map. |
593 | /// |
594 | /// Computes in **O(1)** time (average). |
595 | pub fn swap_remove_full<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, K, V)> |
596 | where |
597 | Q: Hash + Equivalent<K>, |
598 | { |
599 | if self.is_empty() { |
600 | return None; |
601 | } |
602 | let hash = self.hash(key); |
603 | self.core.swap_remove_full(hash, key) |
604 | } |
605 | |
606 | /// Remove the key-value pair equivalent to `key` and return |
607 | /// its value. |
608 | /// |
609 | /// Like `Vec::remove`, the pair is removed by shifting all of the |
610 | /// elements that follow it, preserving their relative order. |
611 | /// **This perturbs the index of all of those elements!** |
612 | /// |
613 | /// Return `None` if `key` is not in map. |
614 | /// |
615 | /// Computes in **O(n)** time (average). |
616 | pub fn shift_remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> |
617 | where |
618 | Q: Hash + Equivalent<K>, |
619 | { |
620 | self.shift_remove_full(key).map(third) |
621 | } |
622 | |
623 | /// Remove and return the key-value pair equivalent to `key`. |
624 | /// |
625 | /// Like `Vec::remove`, the pair is removed by shifting all of the |
626 | /// elements that follow it, preserving their relative order. |
627 | /// **This perturbs the index of all of those elements!** |
628 | /// |
629 | /// Return `None` if `key` is not in map. |
630 | /// |
631 | /// Computes in **O(n)** time (average). |
632 | pub fn shift_remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)> |
633 | where |
634 | Q: Hash + Equivalent<K>, |
635 | { |
636 | match self.shift_remove_full(key) { |
637 | Some((_, key, value)) => Some((key, value)), |
638 | None => None, |
639 | } |
640 | } |
641 | |
642 | /// Remove the key-value pair equivalent to `key` and return it and |
643 | /// the index it had. |
644 | /// |
645 | /// Like `Vec::remove`, the pair is removed by shifting all of the |
646 | /// elements that follow it, preserving their relative order. |
647 | /// **This perturbs the index of all of those elements!** |
648 | /// |
649 | /// Return `None` if `key` is not in map. |
650 | /// |
651 | /// Computes in **O(n)** time (average). |
652 | pub fn shift_remove_full<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, K, V)> |
653 | where |
654 | Q: Hash + Equivalent<K>, |
655 | { |
656 | if self.is_empty() { |
657 | return None; |
658 | } |
659 | let hash = self.hash(key); |
660 | self.core.shift_remove_full(hash, key) |
661 | } |
662 | |
663 | /// Remove the last key-value pair |
664 | /// |
665 | /// This preserves the order of the remaining elements. |
666 | /// |
667 | /// Computes in **O(1)** time (average). |
668 | pub fn pop(&mut self) -> Option<(K, V)> { |
669 | self.core.pop() |
670 | } |
671 | |
672 | /// Scan through each key-value pair in the map and keep those where the |
673 | /// closure `keep` returns `true`. |
674 | /// |
675 | /// The elements are visited in order, and remaining elements keep their |
676 | /// order. |
677 | /// |
678 | /// Computes in **O(n)** time (average). |
679 | pub fn retain<F>(&mut self, mut keep: F) |
680 | where |
681 | F: FnMut(&K, &mut V) -> bool, |
682 | { |
683 | self.core.retain_in_order(move |k, v| keep(k, v)); |
684 | } |
685 | |
686 | pub(crate) fn retain_mut<F>(&mut self, keep: F) |
687 | where |
688 | F: FnMut(&mut K, &mut V) -> bool, |
689 | { |
690 | self.core.retain_in_order(keep); |
691 | } |
692 | |
693 | /// Sort the map’s key-value pairs by the default ordering of the keys. |
694 | /// |
695 | /// See [`sort_by`](Self::sort_by) for details. |
696 | pub fn sort_keys(&mut self) |
697 | where |
698 | K: Ord, |
699 | { |
700 | self.with_entries(move |entries| { |
701 | entries.sort_by(move |a, b| K::cmp(&a.key, &b.key)); |
702 | }); |
703 | } |
704 | |
705 | /// Sort the map’s key-value pairs in place using the comparison |
706 | /// function `cmp`. |
707 | /// |
708 | /// The comparison function receives two key and value pairs to compare (you |
709 | /// can sort by keys or values or their combination as needed). |
710 | /// |
711 | /// Computes in **O(n log n + c)** time and **O(n)** space where *n* is |
712 | /// the length of the map and *c* the capacity. The sort is stable. |
713 | pub fn sort_by<F>(&mut self, mut cmp: F) |
714 | where |
715 | F: FnMut(&K, &V, &K, &V) -> Ordering, |
716 | { |
717 | self.with_entries(move |entries| { |
718 | entries.sort_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value)); |
719 | }); |
720 | } |
721 | |
722 | /// Sort the key-value pairs of the map and return a by-value iterator of |
723 | /// the key-value pairs with the result. |
724 | /// |
725 | /// The sort is stable. |
726 | pub fn sorted_by<F>(self, mut cmp: F) -> IntoIter<K, V> |
727 | where |
728 | F: FnMut(&K, &V, &K, &V) -> Ordering, |
729 | { |
730 | let mut entries = self.into_entries(); |
731 | entries.sort_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value)); |
732 | IntoIter::new(entries) |
733 | } |
734 | |
735 | /// Sort the map's key-value pairs by the default ordering of the keys, but |
736 | /// may not preserve the order of equal elements. |
737 | /// |
738 | /// See [`sort_unstable_by`](Self::sort_unstable_by) for details. |
739 | pub fn sort_unstable_keys(&mut self) |
740 | where |
741 | K: Ord, |
742 | { |
743 | self.with_entries(move |entries| { |
744 | entries.sort_unstable_by(move |a, b| K::cmp(&a.key, &b.key)); |
745 | }); |
746 | } |
747 | |
748 | /// Sort the map's key-value pairs in place using the comparison function `cmp`, but |
749 | /// may not preserve the order of equal elements. |
750 | /// |
751 | /// The comparison function receives two key and value pairs to compare (you |
752 | /// can sort by keys or values or their combination as needed). |
753 | /// |
754 | /// Computes in **O(n log n + c)** time where *n* is |
755 | /// the length of the map and *c* is the capacity. The sort is unstable. |
756 | pub fn sort_unstable_by<F>(&mut self, mut cmp: F) |
757 | where |
758 | F: FnMut(&K, &V, &K, &V) -> Ordering, |
759 | { |
760 | self.with_entries(move |entries| { |
761 | entries.sort_unstable_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value)); |
762 | }); |
763 | } |
764 | |
765 | /// Sort the key-value pairs of the map and return a by-value iterator of |
766 | /// the key-value pairs with the result. |
767 | /// |
768 | /// The sort is unstable. |
769 | #[inline ] |
770 | pub fn sorted_unstable_by<F>(self, mut cmp: F) -> IntoIter<K, V> |
771 | where |
772 | F: FnMut(&K, &V, &K, &V) -> Ordering, |
773 | { |
774 | let mut entries = self.into_entries(); |
775 | entries.sort_unstable_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value)); |
776 | IntoIter::new(entries) |
777 | } |
778 | |
779 | /// Sort the map’s key-value pairs in place using a sort-key extraction function. |
780 | /// |
781 | /// During sorting, the function is called at most once per entry, by using temporary storage |
782 | /// to remember the results of its evaluation. The order of calls to the function is |
783 | /// unspecified and may change between versions of `indexmap` or the standard library. |
784 | /// |
785 | /// Computes in **O(m n + n log n + c)** time () and **O(n)** space, where the function is |
786 | /// **O(m)**, *n* is the length of the map, and *c* the capacity. The sort is stable. |
787 | pub fn sort_by_cached_key<T, F>(&mut self, mut sort_key: F) |
788 | where |
789 | T: Ord, |
790 | F: FnMut(&K, &V) -> T, |
791 | { |
792 | self.with_entries(move |entries| { |
793 | entries.sort_by_cached_key(move |a| sort_key(&a.key, &a.value)); |
794 | }); |
795 | } |
796 | |
797 | /// Reverses the order of the map’s key-value pairs in place. |
798 | /// |
799 | /// Computes in **O(n)** time and **O(1)** space. |
800 | pub fn reverse(&mut self) { |
801 | self.core.reverse() |
802 | } |
803 | } |
804 | |
805 | impl<K, V, S> IndexMap<K, V, S> { |
806 | /// Returns a slice of all the key-value pairs in the map. |
807 | /// |
808 | /// Computes in **O(1)** time. |
809 | pub fn as_slice(&self) -> &Slice<K, V> { |
810 | Slice::from_slice(self.as_entries()) |
811 | } |
812 | |
813 | /// Returns a mutable slice of all the key-value pairs in the map. |
814 | /// |
815 | /// Computes in **O(1)** time. |
816 | pub fn as_mut_slice(&mut self) -> &mut Slice<K, V> { |
817 | Slice::from_mut_slice(self.as_entries_mut()) |
818 | } |
819 | |
820 | /// Converts into a boxed slice of all the key-value pairs in the map. |
821 | /// |
822 | /// Note that this will drop the inner hash table and any excess capacity. |
823 | pub fn into_boxed_slice(self) -> Box<Slice<K, V>> { |
824 | Slice::from_boxed(self.into_entries().into_boxed_slice()) |
825 | } |
826 | |
827 | /// Get a key-value pair by index |
828 | /// |
829 | /// Valid indices are *0 <= index < self.len()* |
830 | /// |
831 | /// Computes in **O(1)** time. |
832 | pub fn get_index(&self, index: usize) -> Option<(&K, &V)> { |
833 | self.as_entries().get(index).map(Bucket::refs) |
834 | } |
835 | |
836 | /// Get a key-value pair by index |
837 | /// |
838 | /// Valid indices are *0 <= index < self.len()* |
839 | /// |
840 | /// Computes in **O(1)** time. |
841 | pub fn get_index_mut(&mut self, index: usize) -> Option<(&K, &mut V)> { |
842 | self.as_entries_mut().get_mut(index).map(Bucket::ref_mut) |
843 | } |
844 | |
845 | /// Returns a slice of key-value pairs in the given range of indices. |
846 | /// |
847 | /// Valid indices are *0 <= index < self.len()* |
848 | /// |
849 | /// Computes in **O(1)** time. |
850 | pub fn get_range<R: RangeBounds<usize>>(&self, range: R) -> Option<&Slice<K, V>> { |
851 | let entries = self.as_entries(); |
852 | let range = try_simplify_range(range, entries.len())?; |
853 | entries.get(range).map(Slice::from_slice) |
854 | } |
855 | |
856 | /// Returns a mutable slice of key-value pairs in the given range of indices. |
857 | /// |
858 | /// Valid indices are *0 <= index < self.len()* |
859 | /// |
860 | /// Computes in **O(1)** time. |
861 | pub fn get_range_mut<R: RangeBounds<usize>>(&mut self, range: R) -> Option<&mut Slice<K, V>> { |
862 | let entries = self.as_entries_mut(); |
863 | let range = try_simplify_range(range, entries.len())?; |
864 | entries.get_mut(range).map(Slice::from_mut_slice) |
865 | } |
866 | |
867 | /// Get the first key-value pair |
868 | /// |
869 | /// Computes in **O(1)** time. |
870 | pub fn first(&self) -> Option<(&K, &V)> { |
871 | self.as_entries().first().map(Bucket::refs) |
872 | } |
873 | |
874 | /// Get the first key-value pair, with mutable access to the value |
875 | /// |
876 | /// Computes in **O(1)** time. |
877 | pub fn first_mut(&mut self) -> Option<(&K, &mut V)> { |
878 | self.as_entries_mut().first_mut().map(Bucket::ref_mut) |
879 | } |
880 | |
881 | /// Get the last key-value pair |
882 | /// |
883 | /// Computes in **O(1)** time. |
884 | pub fn last(&self) -> Option<(&K, &V)> { |
885 | self.as_entries().last().map(Bucket::refs) |
886 | } |
887 | |
888 | /// Get the last key-value pair, with mutable access to the value |
889 | /// |
890 | /// Computes in **O(1)** time. |
891 | pub fn last_mut(&mut self) -> Option<(&K, &mut V)> { |
892 | self.as_entries_mut().last_mut().map(Bucket::ref_mut) |
893 | } |
894 | |
895 | /// Remove the key-value pair by index |
896 | /// |
897 | /// Valid indices are *0 <= index < self.len()* |
898 | /// |
899 | /// Like `Vec::swap_remove`, the pair is removed by swapping it with the |
900 | /// last element of the map and popping it off. **This perturbs |
901 | /// the position of what used to be the last element!** |
902 | /// |
903 | /// Computes in **O(1)** time (average). |
904 | pub fn swap_remove_index(&mut self, index: usize) -> Option<(K, V)> { |
905 | self.core.swap_remove_index(index) |
906 | } |
907 | |
908 | /// Remove the key-value pair by index |
909 | /// |
910 | /// Valid indices are *0 <= index < self.len()* |
911 | /// |
912 | /// Like `Vec::remove`, the pair is removed by shifting all of the |
913 | /// elements that follow it, preserving their relative order. |
914 | /// **This perturbs the index of all of those elements!** |
915 | /// |
916 | /// Computes in **O(n)** time (average). |
917 | pub fn shift_remove_index(&mut self, index: usize) -> Option<(K, V)> { |
918 | self.core.shift_remove_index(index) |
919 | } |
920 | |
921 | /// Moves the position of a key-value pair from one index to another |
922 | /// by shifting all other pairs in-between. |
923 | /// |
924 | /// * If `from < to`, the other pairs will shift down while the targeted pair moves up. |
925 | /// * If `from > to`, the other pairs will shift up while the targeted pair moves down. |
926 | /// |
927 | /// ***Panics*** if `from` or `to` are out of bounds. |
928 | /// |
929 | /// Computes in **O(n)** time (average). |
930 | pub fn move_index(&mut self, from: usize, to: usize) { |
931 | self.core.move_index(from, to) |
932 | } |
933 | |
934 | /// Swaps the position of two key-value pairs in the map. |
935 | /// |
936 | /// ***Panics*** if `a` or `b` are out of bounds. |
937 | pub fn swap_indices(&mut self, a: usize, b: usize) { |
938 | self.core.swap_indices(a, b) |
939 | } |
940 | } |
941 | |
942 | /// Access `IndexMap` values corresponding to a key. |
943 | /// |
944 | /// # Examples |
945 | /// |
946 | /// ``` |
947 | /// use indexmap::IndexMap; |
948 | /// |
949 | /// let mut map = IndexMap::new(); |
950 | /// for word in "Lorem ipsum dolor sit amet" .split_whitespace() { |
951 | /// map.insert(word.to_lowercase(), word.to_uppercase()); |
952 | /// } |
953 | /// assert_eq!(map["lorem" ], "LOREM" ); |
954 | /// assert_eq!(map["ipsum" ], "IPSUM" ); |
955 | /// ``` |
956 | /// |
957 | /// ```should_panic |
958 | /// use indexmap::IndexMap; |
959 | /// |
960 | /// let mut map = IndexMap::new(); |
961 | /// map.insert("foo" , 1); |
962 | /// println!("{:?}" , map["bar" ]); // panics! |
963 | /// ``` |
964 | impl<K, V, Q: ?Sized, S> Index<&Q> for IndexMap<K, V, S> |
965 | where |
966 | Q: Hash + Equivalent<K>, |
967 | K: Hash + Eq, |
968 | S: BuildHasher, |
969 | { |
970 | type Output = V; |
971 | |
972 | /// Returns a reference to the value corresponding to the supplied `key`. |
973 | /// |
974 | /// ***Panics*** if `key` is not present in the map. |
975 | fn index(&self, key: &Q) -> &V { |
976 | self.get(key).expect(msg:"IndexMap: key not found" ) |
977 | } |
978 | } |
979 | |
980 | /// Access `IndexMap` values corresponding to a key. |
981 | /// |
982 | /// Mutable indexing allows changing / updating values of key-value |
983 | /// pairs that are already present. |
984 | /// |
985 | /// You can **not** insert new pairs with index syntax, use `.insert()`. |
986 | /// |
987 | /// # Examples |
988 | /// |
989 | /// ``` |
990 | /// use indexmap::IndexMap; |
991 | /// |
992 | /// let mut map = IndexMap::new(); |
993 | /// for word in "Lorem ipsum dolor sit amet" .split_whitespace() { |
994 | /// map.insert(word.to_lowercase(), word.to_string()); |
995 | /// } |
996 | /// let lorem = &mut map["lorem" ]; |
997 | /// assert_eq!(lorem, "Lorem" ); |
998 | /// lorem.retain(char::is_lowercase); |
999 | /// assert_eq!(map["lorem" ], "orem" ); |
1000 | /// ``` |
1001 | /// |
1002 | /// ```should_panic |
1003 | /// use indexmap::IndexMap; |
1004 | /// |
1005 | /// let mut map = IndexMap::new(); |
1006 | /// map.insert("foo" , 1); |
1007 | /// map["bar" ] = 1; // panics! |
1008 | /// ``` |
1009 | impl<K, V, Q: ?Sized, S> IndexMut<&Q> for IndexMap<K, V, S> |
1010 | where |
1011 | Q: Hash + Equivalent<K>, |
1012 | K: Hash + Eq, |
1013 | S: BuildHasher, |
1014 | { |
1015 | /// Returns a mutable reference to the value corresponding to the supplied `key`. |
1016 | /// |
1017 | /// ***Panics*** if `key` is not present in the map. |
1018 | fn index_mut(&mut self, key: &Q) -> &mut V { |
1019 | self.get_mut(key).expect(msg:"IndexMap: key not found" ) |
1020 | } |
1021 | } |
1022 | |
1023 | /// Access `IndexMap` values at indexed positions. |
1024 | /// |
1025 | /// # Examples |
1026 | /// |
1027 | /// ``` |
1028 | /// use indexmap::IndexMap; |
1029 | /// |
1030 | /// let mut map = IndexMap::new(); |
1031 | /// for word in "Lorem ipsum dolor sit amet" .split_whitespace() { |
1032 | /// map.insert(word.to_lowercase(), word.to_uppercase()); |
1033 | /// } |
1034 | /// assert_eq!(map[0], "LOREM" ); |
1035 | /// assert_eq!(map[1], "IPSUM" ); |
1036 | /// map.reverse(); |
1037 | /// assert_eq!(map[0], "AMET" ); |
1038 | /// assert_eq!(map[1], "SIT" ); |
1039 | /// map.sort_keys(); |
1040 | /// assert_eq!(map[0], "AMET" ); |
1041 | /// assert_eq!(map[1], "DOLOR" ); |
1042 | /// ``` |
1043 | /// |
1044 | /// ```should_panic |
1045 | /// use indexmap::IndexMap; |
1046 | /// |
1047 | /// let mut map = IndexMap::new(); |
1048 | /// map.insert("foo" , 1); |
1049 | /// println!("{:?}" , map[10]); // panics! |
1050 | /// ``` |
1051 | impl<K, V, S> Index<usize> for IndexMap<K, V, S> { |
1052 | type Output = V; |
1053 | |
1054 | /// Returns a reference to the value at the supplied `index`. |
1055 | /// |
1056 | /// ***Panics*** if `index` is out of bounds. |
1057 | fn index(&self, index: usize) -> &V { |
1058 | self.get_index(index) |
1059 | .expect(msg:"IndexMap: index out of bounds" ) |
1060 | .1 |
1061 | } |
1062 | } |
1063 | |
1064 | /// Access `IndexMap` values at indexed positions. |
1065 | /// |
1066 | /// Mutable indexing allows changing / updating indexed values |
1067 | /// that are already present. |
1068 | /// |
1069 | /// You can **not** insert new values with index syntax, use `.insert()`. |
1070 | /// |
1071 | /// # Examples |
1072 | /// |
1073 | /// ``` |
1074 | /// use indexmap::IndexMap; |
1075 | /// |
1076 | /// let mut map = IndexMap::new(); |
1077 | /// for word in "Lorem ipsum dolor sit amet" .split_whitespace() { |
1078 | /// map.insert(word.to_lowercase(), word.to_string()); |
1079 | /// } |
1080 | /// let lorem = &mut map[0]; |
1081 | /// assert_eq!(lorem, "Lorem" ); |
1082 | /// lorem.retain(char::is_lowercase); |
1083 | /// assert_eq!(map["lorem" ], "orem" ); |
1084 | /// ``` |
1085 | /// |
1086 | /// ```should_panic |
1087 | /// use indexmap::IndexMap; |
1088 | /// |
1089 | /// let mut map = IndexMap::new(); |
1090 | /// map.insert("foo" , 1); |
1091 | /// map[10] = 1; // panics! |
1092 | /// ``` |
1093 | impl<K, V, S> IndexMut<usize> for IndexMap<K, V, S> { |
1094 | /// Returns a mutable reference to the value at the supplied `index`. |
1095 | /// |
1096 | /// ***Panics*** if `index` is out of bounds. |
1097 | fn index_mut(&mut self, index: usize) -> &mut V { |
1098 | self.get_index_mut(index) |
1099 | .expect(msg:"IndexMap: index out of bounds" ) |
1100 | .1 |
1101 | } |
1102 | } |
1103 | |
1104 | impl<K, V, S> FromIterator<(K, V)> for IndexMap<K, V, S> |
1105 | where |
1106 | K: Hash + Eq, |
1107 | S: BuildHasher + Default, |
1108 | { |
1109 | /// Create an `IndexMap` from the sequence of key-value pairs in the |
1110 | /// iterable. |
1111 | /// |
1112 | /// `from_iter` uses the same logic as `extend`. See |
1113 | /// [`extend`](#method.extend) for more details. |
1114 | fn from_iter<I: IntoIterator<Item = (K, V)>>(iterable: I) -> Self { |
1115 | let iter: ::IntoIter = iterable.into_iter(); |
1116 | let (low: usize, _) = iter.size_hint(); |
1117 | let mut map: IndexMap = Self::with_capacity_and_hasher(n:low, <_>::default()); |
1118 | map.extend(iter); |
1119 | map |
1120 | } |
1121 | } |
1122 | |
1123 | #[cfg (feature = "std" )] |
1124 | #[cfg_attr (docsrs, doc(cfg(feature = "std" )))] |
1125 | impl<K, V, const N: usize> From<[(K, V); N]> for IndexMap<K, V, RandomState> |
1126 | where |
1127 | K: Hash + Eq, |
1128 | { |
1129 | /// # Examples |
1130 | /// |
1131 | /// ``` |
1132 | /// use indexmap::IndexMap; |
1133 | /// |
1134 | /// let map1 = IndexMap::from([(1, 2), (3, 4)]); |
1135 | /// let map2: IndexMap<_, _> = [(1, 2), (3, 4)].into(); |
1136 | /// assert_eq!(map1, map2); |
1137 | /// ``` |
1138 | fn from(arr: [(K, V); N]) -> Self { |
1139 | Self::from_iter(arr) |
1140 | } |
1141 | } |
1142 | |
1143 | impl<K, V, S> Extend<(K, V)> for IndexMap<K, V, S> |
1144 | where |
1145 | K: Hash + Eq, |
1146 | S: BuildHasher, |
1147 | { |
1148 | /// Extend the map with all key-value pairs in the iterable. |
1149 | /// |
1150 | /// This is equivalent to calling [`insert`](#method.insert) for each of |
1151 | /// them in order, which means that for keys that already existed |
1152 | /// in the map, their value is updated but it keeps the existing order. |
1153 | /// |
1154 | /// New keys are inserted in the order they appear in the sequence. If |
1155 | /// equivalents of a key occur more than once, the last corresponding value |
1156 | /// prevails. |
1157 | fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iterable: I) { |
1158 | // (Note: this is a copy of `std`/`hashbrown`'s reservation logic.) |
1159 | // Keys may be already present or show multiple times in the iterator. |
1160 | // Reserve the entire hint lower bound if the map is empty. |
1161 | // Otherwise reserve half the hint (rounded up), so the map |
1162 | // will only resize twice in the worst case. |
1163 | let iter = iterable.into_iter(); |
1164 | let reserve = if self.is_empty() { |
1165 | iter.size_hint().0 |
1166 | } else { |
1167 | (iter.size_hint().0 + 1) / 2 |
1168 | }; |
1169 | self.reserve(reserve); |
1170 | iter.for_each(move |(k, v)| { |
1171 | self.insert(k, v); |
1172 | }); |
1173 | } |
1174 | } |
1175 | |
1176 | impl<'a, K, V, S> Extend<(&'a K, &'a V)> for IndexMap<K, V, S> |
1177 | where |
1178 | K: Hash + Eq + Copy, |
1179 | V: Copy, |
1180 | S: BuildHasher, |
1181 | { |
1182 | /// Extend the map with all key-value pairs in the iterable. |
1183 | /// |
1184 | /// See the first extend method for more details. |
1185 | fn extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iterable: I) { |
1186 | self.extend(iter:iterable.into_iter().map(|(&key: K, &value: V)| (key, value))); |
1187 | } |
1188 | } |
1189 | |
1190 | impl<K, V, S> Default for IndexMap<K, V, S> |
1191 | where |
1192 | S: Default, |
1193 | { |
1194 | /// Return an empty `IndexMap` |
1195 | fn default() -> Self { |
1196 | Self::with_capacity_and_hasher(n:0, S::default()) |
1197 | } |
1198 | } |
1199 | |
1200 | impl<K, V1, S1, V2, S2> PartialEq<IndexMap<K, V2, S2>> for IndexMap<K, V1, S1> |
1201 | where |
1202 | K: Hash + Eq, |
1203 | V1: PartialEq<V2>, |
1204 | S1: BuildHasher, |
1205 | S2: BuildHasher, |
1206 | { |
1207 | fn eq(&self, other: &IndexMap<K, V2, S2>) -> bool { |
1208 | if self.len() != other.len() { |
1209 | return false; |
1210 | } |
1211 | |
1212 | self.iter() |
1213 | .all(|(key: &K, value: &V1)| other.get(key).map_or(default:false, |v: &V2| *value == *v)) |
1214 | } |
1215 | } |
1216 | |
1217 | impl<K, V, S> Eq for IndexMap<K, V, S> |
1218 | where |
1219 | K: Eq + Hash, |
1220 | V: Eq, |
1221 | S: BuildHasher, |
1222 | { |
1223 | } |
1224 | |