Debian Codegraph @

.cargo/vendor/indexmap/src/map.rs

raw
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
6 pub use crate::mutable_keys::MutableKeys;
7
8 #[cfg(feature = "rayon")]
9 pub use crate::rayon::map as rayon;
10
11 use crate::vec::{self, Vec};
12 use ::core::cmp::Ordering;
13 use ::core::fmt;
14 use ::core::hash::{BuildHasher, Hash, Hasher};
15 use ::core::iter::FusedIterator;
16 use ::core::ops::{Index, IndexMut, RangeBounds};
17 use ::core::slice::{Iter as SliceIter, IterMut as SliceIterMut};
18
19 #[cfg(has_std)]
20 use std::collections::hash_map::RandomState;
21
22 use self::core::IndexMapCore;
23 use crate::equivalent::Equivalent;
24 use crate::util::third;
25 use crate::{Bucket, Entries, HashValue};
26
27 pub use self::core::{Entry, OccupiedEntry, VacantEntry};
28
29 /// A hash table where the iteration order of the key-value pairs is independent
30 /// of the hash values of the keys.
31 ///
32 /// The interface is closely compatible with the standard `HashMap`, but also
33 /// has additional features.
34 ///
35 /// # Order
36 ///
37 /// The key-value pairs have a consistent order that is determined by
38 /// the sequence of insertion and removal calls on the map. The order does
39 /// not depend on the keys or the hash function at all.
40 ///
41 /// All iterators traverse the map in *the order*.
42 ///
43 /// The insertion order is preserved, with **notable exceptions** like the
44 /// `.remove()` or `.swap_remove()` methods. Methods such as `.sort_by()` of
45 /// course result in a new order, depending on the sorting order.
46 ///
47 /// # Indices
48 ///
49 /// The key-value pairs are indexed in a compact range without holes in the
50 /// range `0..self.len()`. For example, the method `.get_full` looks up the
51 /// index for a key, and the method `.get_index` looks up the key-value pair by
52 /// index.
53 ///
54 /// # Examples
55 ///
56 /// ```
57 /// use indexmap::IndexMap;
58 ///
59 /// // count the frequency of each letter in a sentence.
60 /// let mut letters = IndexMap::new();
61 /// for ch in "a short treatise on fungi".chars() {
62 /// *letters.entry(ch).or_insert(0) += 1;
63 /// }
64 ///
65 /// assert_eq!(letters[&'s'], 2);
66 /// assert_eq!(letters[&'t'], 3);
67 /// assert_eq!(letters[&'u'], 1);
68 /// assert_eq!(letters.get(&'y'), None);
69 /// ```
70 #[cfg(has_std)]
71 pub struct IndexMap<K, V, S = RandomState> {
72 pub(crate) core: IndexMapCore<K, V>,
73 hash_builder: S,
74 }
75 #[cfg(not(has_std))]
76 pub struct IndexMap<K, V, S> {
77 pub(crate) core: IndexMapCore<K, V>,
78 hash_builder: S,
79 }
80
81 impl<K, V, S> Clone for IndexMap<K, V, S>
82 where
83 K: Clone,
84 V: Clone,
85 S: Clone,
86 {
87 fn clone(&self) -> Self {
88 IndexMap {
89 core: self.core.clone(),
90 hash_builder: self.hash_builder.clone(),
91 }
92 }
93
94 fn clone_from(&mut self, other: &Self) {
95 self.core.clone_from(&other.core);
96 self.hash_builder.clone_from(&other.hash_builder);
97 }
98 }
99
100 impl<K, V, S> Entries for IndexMap<K, V, S> {
101 type Entry = Bucket<K, V>;
102
103 #[inline]
104 fn into_entries(self) -> Vec<Self::Entry> {
105 self.core.into_entries()
106 }
107
108 #[inline]
109 fn as_entries(&self) -> &[Self::Entry] {
110 self.core.as_entries()
111 }
112
113 #[inline]
114 fn as_entries_mut(&mut self) -> &mut [Self::Entry] {
115 self.core.as_entries_mut()
116 }
117
118 fn with_entries<F>(&mut self, f: F)
119 where
120 F: FnOnce(&mut [Self::Entry]),
121 {
122 self.core.with_entries(f);
123 }
124 }
125
126 impl<K, V, S> fmt::Debug for IndexMap<K, V, S>
127 where
128 K: fmt::Debug,
129 V: fmt::Debug,
130 {
131 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
132 if cfg!(not(feature = "test_debug")) {
133 f.debug_map().entries(self.iter()).finish()
134 } else {
135 // Let the inner `IndexMapCore` print all of its details
136 f.debug_struct("IndexMap")
137 .field("core", &self.core)
138 .finish()
139 }
140 }
141 }
142
143 #[cfg(has_std)]
144 impl<K, V> IndexMap<K, V> {
145 /// Create a new map. (Does not allocate.)
146 #[inline]
147 pub fn new() -> Self {
148 Self::with_capacity(0)
149 }
150
151 /// Create a new map with capacity for `n` key-value pairs. (Does not
152 /// allocate if `n` is zero.)
153 ///
154 /// Computes in **O(n)** time.
155 #[inline]
156 pub fn with_capacity(n: usize) -> Self {
157 Self::with_capacity_and_hasher(n, <_>::default())
158 }
159 }
160
161 impl<K, V, S> IndexMap<K, V, S> {
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_and_hasher(n: usize, hash_builder: S) -> Self {
168 if n == 0 {
169 Self::with_hasher(hash_builder)
170 } else {
171 IndexMap {
172 core: IndexMapCore::with_capacity(n),
173 hash_builder,
174 }
175 }
176 }
177
178 /// Create a new map with `hash_builder`.
179 ///
180 /// This function is `const`, so it
181 /// can be called in `static` contexts.
182 pub const fn with_hasher(hash_builder: S) -> Self {
183 IndexMap {
184 core: IndexMapCore::new(),
185 hash_builder,
186 }
187 }
188
189 /// Computes in **O(1)** time.
190 pub fn capacity(&self) -> usize {
191 self.core.capacity()
192 }
193
194 /// Return a reference to the map's `BuildHasher`.
195 pub fn hasher(&self) -> &S {
196 &self.hash_builder
197 }
198
199 /// Return the number of key-value pairs in the map.
200 ///
201 /// Computes in **O(1)** time.
202 #[inline]
203 pub fn len(&self) -> usize {
204 self.core.len()
205 }
206
207 /// Returns true if the map contains no elements.
208 ///
209 /// Computes in **O(1)** time.
210 #[inline]
211 pub fn is_empty(&self) -> bool {
212 self.len() == 0
213 }
214
215 /// Return an iterator over the key-value pairs of the map, in their order
216 pub fn iter(&self) -> Iter<'_, K, V> {
217 Iter {
218 iter: self.as_entries().iter(),
219 }
220 }
221
222 /// Return an iterator over the key-value pairs of the map, in their order
223 pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
224 IterMut {
225 iter: self.as_entries_mut().iter_mut(),
226 }
227 }
228
229 /// Return an iterator over the keys of the map, in their order
230 pub fn keys(&self) -> Keys<'_, K, V> {
231 Keys {
232 iter: self.as_entries().iter(),
233 }
234 }
235
236 /// Return an owning iterator over the keys of the map, in their order
237 pub fn into_keys(self) -> IntoKeys<K, V> {
238 IntoKeys {
239 iter: self.into_entries().into_iter(),
240 }
241 }
242
243 /// Return an iterator over the values of the map, in their order
244 pub fn values(&self) -> Values<'_, K, V> {
245 Values {
246 iter: self.as_entries().iter(),
247 }
248 }
249
250 /// Return an iterator over mutable references to the values of the map,
251 /// in their order
252 pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
253 ValuesMut {
254 iter: self.as_entries_mut().iter_mut(),
255 }
256 }
257
258 /// Return an owning iterator over the values of the map, in their order
259 pub fn into_values(self) -> IntoValues<K, V> {
260 IntoValues {
261 iter: self.into_entries().into_iter(),
262 }
263 }
264
265 /// Remove all key-value pairs in the map, while preserving its capacity.
266 ///
267 /// Computes in **O(n)** time.
268 pub fn clear(&mut self) {
269 self.core.clear();
270 }
271
272 /// Shortens the map, keeping the first `len` elements and dropping the rest.
273 ///
274 /// If `len` is greater than the map's current length, this has no effect.
275 pub fn truncate(&mut self, len: usize) {
276 self.core.truncate(len);
277 }
278
279 /// Clears the `IndexMap` in the given index range, returning those
280 /// key-value pairs as a drain iterator.
281 ///
282 /// The range may be any type that implements `RangeBounds<usize>`,
283 /// including all of the `std::ops::Range*` types, or even a tuple pair of
284 /// `Bound` start and end values. To drain the map entirely, use `RangeFull`
285 /// like `map.drain(..)`.
286 ///
287 /// This shifts down all entries following the drained range to fill the
288 /// gap, and keeps the allocated memory for reuse.
289 ///
290 /// ***Panics*** if the starting point is greater than the end point or if
291 /// the end point is greater than the length of the map.
292 pub fn drain<R>(&mut self, range: R) -> Drain<'_, K, V>
293 where
294 R: RangeBounds<usize>,
295 {
296 Drain {
297 iter: self.core.drain(range),
298 }
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 /// Shrink the capacity of the map as much as possible.
332 ///
333 /// Computes in **O(n)** time.
334 pub fn shrink_to_fit(&mut self) {
335 self.core.shrink_to(0);
336 }
337
338 /// Shrink the capacity of the map with a lower limit.
339 ///
340 /// Computes in **O(n)** time.
341 pub fn shrink_to(&mut self, min_capacity: usize) {
342 self.core.shrink_to(min_capacity);
343 }
344
345 fn hash<Q: ?Sized + Hash>(&self, key: &Q) -> HashValue {
346 let mut h = self.hash_builder.build_hasher();
347 key.hash(&mut h);
348 HashValue(h.finish() as usize)
349 }
350
351 /// Insert a key-value pair in the map.
352 ///
353 /// If an equivalent key already exists in the map: the key remains and
354 /// retains in its place in the order, its corresponding value is updated
355 /// with `value` and the older value is returned inside `Some(_)`.
356 ///
357 /// If no equivalent key existed in the map: the new key-value pair is
358 /// inserted, last in order, and `None` is returned.
359 ///
360 /// Computes in **O(1)** time (amortized average).
361 ///
362 /// See also [`entry`](#method.entry) if you you want to insert *or* modify
363 /// or if you need to get the index of the corresponding key-value pair.
364 pub fn insert(&mut self, key: K, value: V) -> Option<V> {
365 self.insert_full(key, value).1
366 }
367
368 /// Insert a key-value pair in the map, and get their index.
369 ///
370 /// If an equivalent key already exists in the map: the key remains and
371 /// retains in its place in the order, its corresponding value is updated
372 /// with `value` and the older value is returned inside `(index, Some(_))`.
373 ///
374 /// If no equivalent key existed in the map: the new key-value pair is
375 /// inserted, last in order, and `(index, None)` is returned.
376 ///
377 /// Computes in **O(1)** time (amortized average).
378 ///
379 /// See also [`entry`](#method.entry) if you you want to insert *or* modify
380 /// or if you need to get the index of the corresponding key-value pair.
381 pub fn insert_full(&mut self, key: K, value: V) -> (usize, Option<V>) {
382 let hash = self.hash(&key);
383 self.core.insert_full(hash, key, value)
384 }
385
386 /// Get the given key’s corresponding entry in the map for insertion and/or
387 /// in-place manipulation.
388 ///
389 /// Computes in **O(1)** time (amortized average).
390 pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {
391 let hash = self.hash(&key);
392 self.core.entry(hash, key)
393 }
394
395 /// Return `true` if an equivalent to `key` exists in the map.
396 ///
397 /// Computes in **O(1)** time (average).
398 pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
399 where
400 Q: Hash + Equivalent<K>,
401 {
402 self.get_index_of(key).is_some()
403 }
404
405 /// Return a reference to the value stored for `key`, if it is present,
406 /// else `None`.
407 ///
408 /// Computes in **O(1)** time (average).
409 pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
410 where
411 Q: Hash + Equivalent<K>,
412 {
413 if let Some(i) = self.get_index_of(key) {
414 let entry = &self.as_entries()[i];
415 Some(&entry.value)
416 } else {
417 None
418 }
419 }
420
421 /// Return references to the key-value pair stored for `key`,
422 /// if it is present, else `None`.
423 ///
424 /// Computes in **O(1)** time (average).
425 pub fn get_key_value<Q: ?Sized>(&self, key: &Q) -> Option<(&K, &V)>
426 where
427 Q: Hash + Equivalent<K>,
428 {
429 if let Some(i) = self.get_index_of(key) {
430 let entry = &self.as_entries()[i];
431 Some((&entry.key, &entry.value))
432 } else {
433 None
434 }
435 }
436
437 /// Return item index, key and value
438 pub fn get_full<Q: ?Sized>(&self, key: &Q) -> Option<(usize, &K, &V)>
439 where
440 Q: Hash + Equivalent<K>,
441 {
442 if let Some(i) = self.get_index_of(key) {
443 let entry = &self.as_entries()[i];
444 Some((i, &entry.key, &entry.value))
445 } else {
446 None
447 }
448 }
449
450 /// Return item index, if it exists in the map
451 ///
452 /// Computes in **O(1)** time (average).
453 pub fn get_index_of<Q: ?Sized>(&self, key: &Q) -> Option<usize>
454 where
455 Q: Hash + Equivalent<K>,
456 {
457 if self.is_empty() {
458 None
459 } else {
460 let hash = self.hash(key);
461 self.core.get_index_of(hash, key)
462 }
463 }
464
465 pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
466 where
467 Q: Hash + Equivalent<K>,
468 {
469 if let Some(i) = self.get_index_of(key) {
470 let entry = &mut self.as_entries_mut()[i];
471 Some(&mut entry.value)
472 } else {
473 None
474 }
475 }
476
477 pub fn get_full_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, &K, &mut V)>
478 where
479 Q: Hash + Equivalent<K>,
480 {
481 if let Some(i) = self.get_index_of(key) {
482 let entry = &mut self.as_entries_mut()[i];
483 Some((i, &entry.key, &mut entry.value))
484 } else {
485 None
486 }
487 }
488
489 pub(crate) fn get_full_mut2_impl<Q: ?Sized>(
490 &mut self,
491 key: &Q,
492 ) -> Option<(usize, &mut K, &mut V)>
493 where
494 Q: Hash + Equivalent<K>,
495 {
496 if let Some(i) = self.get_index_of(key) {
497 let entry = &mut self.as_entries_mut()[i];
498 Some((i, &mut entry.key, &mut entry.value))
499 } else {
500 None
501 }
502 }
503
504 /// Remove the key-value pair equivalent to `key` and return
505 /// its value.
506 ///
507 /// **NOTE:** This is equivalent to `.swap_remove(key)`, if you need to
508 /// preserve the order of the keys in the map, use `.shift_remove(key)`
509 /// instead.
510 ///
511 /// Computes in **O(1)** time (average).
512 pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
513 where
514 Q: Hash + Equivalent<K>,
515 {
516 self.swap_remove(key)
517 }
518
519 /// Remove and return the key-value pair equivalent to `key`.
520 ///
521 /// **NOTE:** This is equivalent to `.swap_remove_entry(key)`, if you need to
522 /// preserve the order of the keys in the map, use `.shift_remove_entry(key)`
523 /// instead.
524 ///
525 /// Computes in **O(1)** time (average).
526 pub fn remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)>
527 where
528 Q: Hash + Equivalent<K>,
529 {
530 self.swap_remove_entry(key)
531 }
532
533 /// Remove the key-value pair equivalent to `key` and return
534 /// its value.
535 ///
536 /// Like `Vec::swap_remove`, the pair is removed by swapping it with the
537 /// last element of the map and popping it off. **This perturbs
538 /// the position of what used to be the last element!**
539 ///
540 /// Return `None` if `key` is not in map.
541 ///
542 /// Computes in **O(1)** time (average).
543 pub fn swap_remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
544 where
545 Q: Hash + Equivalent<K>,
546 {
547 self.swap_remove_full(key).map(third)
548 }
549
550 /// Remove and return the key-value pair equivalent to `key`.
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_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)>
560 where
561 Q: Hash + Equivalent<K>,
562 {
563 match self.swap_remove_full(key) {
564 Some((_, key, value)) => Some((key, value)),
565 None => None,
566 }
567 }
568
569 /// Remove the key-value pair equivalent to `key` and return it and
570 /// the index it had.
571 ///
572 /// Like `Vec::swap_remove`, the pair is removed by swapping it with the
573 /// last element of the map and popping it off. **This perturbs
574 /// the position of what used to be the last element!**
575 ///
576 /// Return `None` if `key` is not in map.
577 ///
578 /// Computes in **O(1)** time (average).
579 pub fn swap_remove_full<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, K, V)>
580 where
581 Q: Hash + Equivalent<K>,
582 {
583 if self.is_empty() {
584 return None;
585 }
586 let hash = self.hash(key);
587 self.core.swap_remove_full(hash, key)
588 }
589
590 /// Remove the key-value pair equivalent to `key` and return
591 /// its value.
592 ///
593 /// Like `Vec::remove`, the pair is removed by shifting all of the
594 /// elements that follow it, preserving their relative order.
595 /// **This perturbs the index of all of those elements!**
596 ///
597 /// Return `None` if `key` is not in map.
598 ///
599 /// Computes in **O(n)** time (average).
600 pub fn shift_remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
601 where
602 Q: Hash + Equivalent<K>,
603 {
604 self.shift_remove_full(key).map(third)
605 }
606
607 /// Remove and return the key-value pair equivalent to `key`.
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_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)>
617 where
618 Q: Hash + Equivalent<K>,
619 {
620 match self.shift_remove_full(key) {
621 Some((_, key, value)) => Some((key, value)),
622 None => None,
623 }
624 }
625
626 /// Remove the key-value pair equivalent to `key` and return it and
627 /// the index it had.
628 ///
629 /// Like `Vec::remove`, the pair is removed by shifting all of the
630 /// elements that follow it, preserving their relative order.
631 /// **This perturbs the index of all of those elements!**
632 ///
633 /// Return `None` if `key` is not in map.
634 ///
635 /// Computes in **O(n)** time (average).
636 pub fn shift_remove_full<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, K, V)>
637 where
638 Q: Hash + Equivalent<K>,
639 {
640 if self.is_empty() {
641 return None;
642 }
643 let hash = self.hash(key);
644 self.core.shift_remove_full(hash, key)
645 }
646
647 /// Remove the last key-value pair
648 ///
649 /// This preserves the order of the remaining elements.
650 ///
651 /// Computes in **O(1)** time (average).
652 pub fn pop(&mut self) -> Option<(K, V)> {
653 self.core.pop()
654 }
655
656 /// Scan through each key-value pair in the map and keep those where the
657 /// closure `keep` returns `true`.
658 ///
659 /// The elements are visited in order, and remaining elements keep their
660 /// order.
661 ///
662 /// Computes in **O(n)** time (average).
663 pub fn retain<F>(&mut self, mut keep: F)
664 where
665 F: FnMut(&K, &mut V) -> bool,
666 {
667 self.core.retain_in_order(move |k, v| keep(k, v));
668 }
669
670 pub(crate) fn retain_mut<F>(&mut self, keep: F)
671 where
672 F: FnMut(&mut K, &mut V) -> bool,
673 {
674 self.core.retain_in_order(keep);
675 }
676
677 /// Sort the map’s key-value pairs by the default ordering of the keys.
678 ///
679 /// See [`sort_by`](Self::sort_by) for details.
680 pub fn sort_keys(&mut self)
681 where
682 K: Ord,
683 {
684 self.with_entries(move |entries| {
685 entries.sort_by(move |a, b| K::cmp(&a.key, &b.key));
686 });
687 }
688
689 /// Sort the map’s key-value pairs in place using the comparison
690 /// function `cmp`.
691 ///
692 /// The comparison function receives two key and value pairs to compare (you
693 /// can sort by keys or values or their combination as needed).
694 ///
695 /// Computes in **O(n log n + c)** time and **O(n)** space where *n* is
696 /// the length of the map and *c* the capacity. The sort is stable.
697 pub fn sort_by<F>(&mut self, mut cmp: F)
698 where
699 F: FnMut(&K, &V, &K, &V) -> Ordering,
700 {
701 self.with_entries(move |entries| {
702 entries.sort_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value));
703 });
704 }
705
706 /// Sort the key-value pairs of the map and return a by-value iterator of
707 /// the key-value pairs with the result.
708 ///
709 /// The sort is stable.
710 pub fn sorted_by<F>(self, mut cmp: F) -> IntoIter<K, V>
711 where
712 F: FnMut(&K, &V, &K, &V) -> Ordering,
713 {
714 let mut entries = self.into_entries();
715 entries.sort_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value));
716 IntoIter {
717 iter: entries.into_iter(),
718 }
719 }
720
721 /// Sort the map's key-value pairs by the default ordering of the keys, but
722 /// may not preserve the order of equal elements.
723 ///
724 /// See [`sort_unstable_by`](Self::sort_unstable_by) for details.
725 pub fn sort_unstable_keys(&mut self)
726 where
727 K: Ord,
728 {
729 self.with_entries(move |entries| {
730 entries.sort_unstable_by(move |a, b| K::cmp(&a.key, &b.key));
731 });
732 }
733
734 /// Sort the map's key-value pairs in place using the comparison function `cmp`, but
735 /// may not preserve the order of equal elements.
736 ///
737 /// The comparison function receives two key and value pairs to compare (you
738 /// can sort by keys or values or their combination as needed).
739 ///
740 /// Computes in **O(n log n + c)** time where *n* is
741 /// the length of the map and *c* is the capacity. The sort is unstable.
742 pub fn sort_unstable_by<F>(&mut self, mut cmp: F)
743 where
744 F: FnMut(&K, &V, &K, &V) -> Ordering,
745 {
746 self.with_entries(move |entries| {
747 entries.sort_unstable_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value));
748 });
749 }
750
751 /// Sort the key-value pairs of the map and return a by-value iterator of
752 /// the key-value pairs with the result.
753 ///
754 /// The sort is unstable.
755 #[inline]
756 pub fn sorted_unstable_by<F>(self, mut cmp: F) -> IntoIter<K, V>
757 where
758 F: FnMut(&K, &V, &K, &V) -> Ordering,
759 {
760 let mut entries = self.into_entries();
761 entries.sort_unstable_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value));
762 IntoIter {
763 iter: entries.into_iter(),
764 }
765 }
766
767 /// Reverses the order of the map’s key-value pairs in place.
768 ///
769 /// Computes in **O(n)** time and **O(1)** space.
770 pub fn reverse(&mut self) {
771 self.core.reverse()
772 }
773 }
774
775 impl<K, V, S> IndexMap<K, V, S> {
776 /// Get a key-value pair by index
777 ///
778 /// Valid indices are *0 <= index < self.len()*
779 ///
780 /// Computes in **O(1)** time.
781 pub fn get_index(&self, index: usize) -> Option<(&K, &V)> {
782 self.as_entries().get(index).map(Bucket::refs)
783 }
784
785 /// Get a key-value pair by index
786 ///
787 /// Valid indices are *0 <= index < self.len()*
788 ///
789 /// Computes in **O(1)** time.
790 pub fn get_index_mut(&mut self, index: usize) -> Option<(&mut K, &mut V)> {
791 self.as_entries_mut().get_mut(index).map(Bucket::muts)
792 }
793
794 /// Get the first key-value pair
795 ///
796 /// Computes in **O(1)** time.
797 pub fn first(&self) -> Option<(&K, &V)> {
798 self.as_entries().first().map(Bucket::refs)
799 }
800
801 /// Get the first key-value pair, with mutable access to the value
802 ///
803 /// Computes in **O(1)** time.
804 pub fn first_mut(&mut self) -> Option<(&K, &mut V)> {
805 self.as_entries_mut().first_mut().map(Bucket::ref_mut)
806 }
807
808 /// Get the last key-value pair
809 ///
810 /// Computes in **O(1)** time.
811 pub fn last(&self) -> Option<(&K, &V)> {
812 self.as_entries().last().map(Bucket::refs)
813 }
814
815 /// Get the last key-value pair, with mutable access to the value
816 ///
817 /// Computes in **O(1)** time.
818 pub fn last_mut(&mut self) -> Option<(&K, &mut V)> {
819 self.as_entries_mut().last_mut().map(Bucket::ref_mut)
820 }
821
822 /// Remove the key-value pair by index
823 ///
824 /// Valid indices are *0 <= index < self.len()*
825 ///
826 /// Like `Vec::swap_remove`, the pair is removed by swapping it with the
827 /// last element of the map and popping it off. **This perturbs
828 /// the position of what used to be the last element!**
829 ///
830 /// Computes in **O(1)** time (average).
831 pub fn swap_remove_index(&mut self, index: usize) -> Option<(K, V)> {
832 self.core.swap_remove_index(index)
833 }
834
835 /// Remove the key-value pair by index
836 ///
837 /// Valid indices are *0 <= index < self.len()*
838 ///
839 /// Like `Vec::remove`, the pair is removed by shifting all of the
840 /// elements that follow it, preserving their relative order.
841 /// **This perturbs the index of all of those elements!**
842 ///
843 /// Computes in **O(n)** time (average).
844 pub fn shift_remove_index(&mut self, index: usize) -> Option<(K, V)> {
845 self.core.shift_remove_index(index)
846 }
847
848 /// Moves the position of a key-value pair from one index to another
849 /// by shifting all other pairs in-between.
850 ///
851 /// * If `from < to`, the other pairs will shift down while the targeted pair moves up.
852 /// * If `from > to`, the other pairs will shift up while the targeted pair moves down.
853 ///
854 /// ***Panics*** if `from` or `to` are out of bounds.
855 ///
856 /// Computes in **O(n)** time (average).
857 pub fn move_index(&mut self, from: usize, to: usize) {
858 self.core.move_index(from, to)
859 }
860
861 /// Swaps the position of two key-value pairs in the map.
862 ///
863 /// ***Panics*** if `a` or `b` are out of bounds.
864 pub fn swap_indices(&mut self, a: usize, b: usize) {
865 self.core.swap_indices(a, b)
866 }
867 }
868
869 /// An iterator over the keys of a `IndexMap`.
870 ///
871 /// This `struct` is created by the [`keys`] method on [`IndexMap`]. See its
872 /// documentation for more.
873 ///
874 /// [`keys`]: struct.IndexMap.html#method.keys
875 /// [`IndexMap`]: struct.IndexMap.html
876 pub struct Keys<'a, K, V> {
877 iter: SliceIter<'a, Bucket<K, V>>,
878 }
879
880 impl<'a, K, V> Iterator for Keys<'a, K, V> {
881 type Item = &'a K;
882
883 iterator_methods!(Bucket::key_ref);
884 }
885
886 impl<K, V> DoubleEndedIterator for Keys<'_, K, V> {
887 double_ended_iterator_methods!(Bucket::key_ref);
888 }
889
890 impl<K, V> ExactSizeIterator for Keys<'_, K, V> {
891 fn len(&self) -> usize {
892 self.iter.len()
893 }
894 }
895
896 impl<K, V> FusedIterator for Keys<'_, K, V> {}
897
898 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
899 impl<K, V> Clone for Keys<'_, K, V> {
900 fn clone(&self) -> Self {
901 Keys {
902 iter: self.iter.clone(),
903 }
904 }
905 }
906
907 impl<K: fmt::Debug, V> fmt::Debug for Keys<'_, K, V> {
908 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
909 f.debug_list().entries(self.clone()).finish()
910 }
911 }
912
913 /// An owning iterator over the keys of a `IndexMap`.
914 ///
915 /// This `struct` is created by the [`into_keys`] method on [`IndexMap`].
916 /// See its documentation for more.
917 ///
918 /// [`IndexMap`]: struct.IndexMap.html
919 /// [`into_keys`]: struct.IndexMap.html#method.into_keys
920 pub struct IntoKeys<K, V> {
921 iter: vec::IntoIter<Bucket<K, V>>,
922 }
923
924 impl<K, V> Iterator for IntoKeys<K, V> {
925 type Item = K;
926
927 iterator_methods!(Bucket::key);
928 }
929
930 impl<K, V> DoubleEndedIterator for IntoKeys<K, V> {
931 double_ended_iterator_methods!(Bucket::key);
932 }
933
934 impl<K, V> ExactSizeIterator for IntoKeys<K, V> {
935 fn len(&self) -> usize {
936 self.iter.len()
937 }
938 }
939
940 impl<K, V> FusedIterator for IntoKeys<K, V> {}
941
942 impl<K: fmt::Debug, V> fmt::Debug for IntoKeys<K, V> {
943 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
944 let iter = self.iter.as_slice().iter().map(Bucket::key_ref);
945 f.debug_list().entries(iter).finish()
946 }
947 }
948
949 /// An iterator over the values of a `IndexMap`.
950 ///
951 /// This `struct` is created by the [`values`] method on [`IndexMap`]. See its
952 /// documentation for more.
953 ///
954 /// [`values`]: struct.IndexMap.html#method.values
955 /// [`IndexMap`]: struct.IndexMap.html
956 pub struct Values<'a, K, V> {
957 iter: SliceIter<'a, Bucket<K, V>>,
958 }
959
960 impl<'a, K, V> Iterator for Values<'a, K, V> {
961 type Item = &'a V;
962
963 iterator_methods!(Bucket::value_ref);
964 }
965
966 impl<K, V> DoubleEndedIterator for Values<'_, K, V> {
967 double_ended_iterator_methods!(Bucket::value_ref);
968 }
969
970 impl<K, V> ExactSizeIterator for Values<'_, K, V> {
971 fn len(&self) -> usize {
972 self.iter.len()
973 }
974 }
975
976 impl<K, V> FusedIterator for Values<'_, K, V> {}
977
978 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
979 impl<K, V> Clone for Values<'_, K, V> {
980 fn clone(&self) -> Self {
981 Values {
982 iter: self.iter.clone(),
983 }
984 }
985 }
986
987 impl<K, V: fmt::Debug> fmt::Debug for Values<'_, K, V> {
988 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
989 f.debug_list().entries(self.clone()).finish()
990 }
991 }
992
993 /// A mutable iterator over the values of a `IndexMap`.
994 ///
995 /// This `struct` is created by the [`values_mut`] method on [`IndexMap`]. See its
996 /// documentation for more.
997 ///
998 /// [`values_mut`]: struct.IndexMap.html#method.values_mut
999 /// [`IndexMap`]: struct.IndexMap.html
1000 pub struct ValuesMut<'a, K, V> {
1001 iter: SliceIterMut<'a, Bucket<K, V>>,
1002 }
1003
1004 impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
1005 type Item = &'a mut V;
1006
1007 iterator_methods!(Bucket::value_mut);
1008 }
1009
1010 impl<K, V> DoubleEndedIterator for ValuesMut<'_, K, V> {
1011 double_ended_iterator_methods!(Bucket::value_mut);
1012 }
1013
1014 impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> {
1015 fn len(&self) -> usize {
1016 self.iter.len()
1017 }
1018 }
1019
1020 impl<K, V> FusedIterator for ValuesMut<'_, K, V> {}
1021
1022 impl<K, V: fmt::Debug> fmt::Debug for ValuesMut<'_, K, V> {
1023 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1024 let iter = self.iter.as_slice().iter().map(Bucket::value_ref);
1025 f.debug_list().entries(iter).finish()
1026 }
1027 }
1028
1029 /// An owning iterator over the values of a `IndexMap`.
1030 ///
1031 /// This `struct` is created by the [`into_values`] method on [`IndexMap`].
1032 /// See its documentation for more.
1033 ///
1034 /// [`IndexMap`]: struct.IndexMap.html
1035 /// [`into_values`]: struct.IndexMap.html#method.into_values
1036 pub struct IntoValues<K, V> {
1037 iter: vec::IntoIter<Bucket<K, V>>,
1038 }
1039
1040 impl<K, V> Iterator for IntoValues<K, V> {
1041 type Item = V;
1042
1043 iterator_methods!(Bucket::value);
1044 }
1045
1046 impl<K, V> DoubleEndedIterator for IntoValues<K, V> {
1047 double_ended_iterator_methods!(Bucket::value);
1048 }
1049
1050 impl<K, V> ExactSizeIterator for IntoValues<K, V> {
1051 fn len(&self) -> usize {
1052 self.iter.len()
1053 }
1054 }
1055
1056 impl<K, V> FusedIterator for IntoValues<K, V> {}
1057
1058 impl<K, V: fmt::Debug> fmt::Debug for IntoValues<K, V> {
1059 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1060 let iter = self.iter.as_slice().iter().map(Bucket::value_ref);
1061 f.debug_list().entries(iter).finish()
1062 }
1063 }
1064
1065 /// An iterator over the entries of a `IndexMap`.
1066 ///
1067 /// This `struct` is created by the [`iter`] method on [`IndexMap`]. See its
1068 /// documentation for more.
1069 ///
1070 /// [`iter`]: struct.IndexMap.html#method.iter
1071 /// [`IndexMap`]: struct.IndexMap.html
1072 pub struct Iter<'a, K, V> {
1073 iter: SliceIter<'a, Bucket<K, V>>,
1074 }
1075
1076 impl<'a, K, V> Iterator for Iter<'a, K, V> {
1077 type Item = (&'a K, &'a V);
1078
1079 iterator_methods!(Bucket::refs);
1080 }
1081
1082 impl<K, V> DoubleEndedIterator for Iter<'_, K, V> {
1083 double_ended_iterator_methods!(Bucket::refs);
1084 }
1085
1086 impl<K, V> ExactSizeIterator for Iter<'_, K, V> {
1087 fn len(&self) -> usize {
1088 self.iter.len()
1089 }
1090 }
1091
1092 impl<K, V> FusedIterator for Iter<'_, K, V> {}
1093
1094 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
1095 impl<K, V> Clone for Iter<'_, K, V> {
1096 fn clone(&self) -> Self {
1097 Iter {
1098 iter: self.iter.clone(),
1099 }
1100 }
1101 }
1102
1103 impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Iter<'_, K, V> {
1104 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1105 f.debug_list().entries(self.clone()).finish()
1106 }
1107 }
1108
1109 /// A mutable iterator over the entries of a `IndexMap`.
1110 ///
1111 /// This `struct` is created by the [`iter_mut`] method on [`IndexMap`]. See its
1112 /// documentation for more.
1113 ///
1114 /// [`iter_mut`]: struct.IndexMap.html#method.iter_mut
1115 /// [`IndexMap`]: struct.IndexMap.html
1116 pub struct IterMut<'a, K, V> {
1117 iter: SliceIterMut<'a, Bucket<K, V>>,
1118 }
1119
1120 impl<'a, K, V> Iterator for IterMut<'a, K, V> {
1121 type Item = (&'a K, &'a mut V);
1122
1123 iterator_methods!(Bucket::ref_mut);
1124 }
1125
1126 impl<K, V> DoubleEndedIterator for IterMut<'_, K, V> {
1127 double_ended_iterator_methods!(Bucket::ref_mut);
1128 }
1129
1130 impl<K, V> ExactSizeIterator for IterMut<'_, K, V> {
1131 fn len(&self) -> usize {
1132 self.iter.len()
1133 }
1134 }
1135
1136 impl<K, V> FusedIterator for IterMut<'_, K, V> {}
1137
1138 impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IterMut<'_, K, V> {
1139 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1140 let iter = self.iter.as_slice().iter().map(Bucket::refs);
1141 f.debug_list().entries(iter).finish()
1142 }
1143 }
1144
1145 /// An owning iterator over the entries of a `IndexMap`.
1146 ///
1147 /// This `struct` is created by the [`into_iter`] method on [`IndexMap`]
1148 /// (provided by the `IntoIterator` trait). See its documentation for more.
1149 ///
1150 /// [`into_iter`]: struct.IndexMap.html#method.into_iter
1151 /// [`IndexMap`]: struct.IndexMap.html
1152 pub struct IntoIter<K, V> {
1153 iter: vec::IntoIter<Bucket<K, V>>,
1154 }
1155
1156 impl<K, V> Iterator for IntoIter<K, V> {
1157 type Item = (K, V);
1158
1159 iterator_methods!(Bucket::key_value);
1160 }
1161
1162 impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
1163 double_ended_iterator_methods!(Bucket::key_value);
1164 }
1165
1166 impl<K, V> ExactSizeIterator for IntoIter<K, V> {
1167 fn len(&self) -> usize {
1168 self.iter.len()
1169 }
1170 }
1171
1172 impl<K, V> FusedIterator for IntoIter<K, V> {}
1173
1174 impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IntoIter<K, V> {
1175 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1176 let iter = self.iter.as_slice().iter().map(Bucket::refs);
1177 f.debug_list().entries(iter).finish()
1178 }
1179 }
1180
1181 /// A draining iterator over the entries of a `IndexMap`.
1182 ///
1183 /// This `struct` is created by the [`drain`] method on [`IndexMap`]. See its
1184 /// documentation for more.
1185 ///
1186 /// [`drain`]: struct.IndexMap.html#method.drain
1187 /// [`IndexMap`]: struct.IndexMap.html
1188 pub struct Drain<'a, K, V> {
1189 pub(crate) iter: vec::Drain<'a, Bucket<K, V>>,
1190 }
1191
1192 impl<K, V> Iterator for Drain<'_, K, V> {
1193 type Item = (K, V);
1194
1195 iterator_methods!(Bucket::key_value);
1196 }
1197
1198 impl<K, V> DoubleEndedIterator for Drain<'_, K, V> {
1199 double_ended_iterator_methods!(Bucket::key_value);
1200 }
1201
1202 impl<K, V> ExactSizeIterator for Drain<'_, K, V> {
1203 fn len(&self) -> usize {
1204 self.iter.len()
1205 }
1206 }
1207
1208 impl<K, V> FusedIterator for Drain<'_, K, V> {}
1209
1210 impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Drain<'_, K, V> {
1211 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1212 let iter = self.iter.as_slice().iter().map(Bucket::refs);
1213 f.debug_list().entries(iter).finish()
1214 }
1215 }
1216
1217 impl<'a, K, V, S> IntoIterator for &'a IndexMap<K, V, S> {
1218 type Item = (&'a K, &'a V);
1219 type IntoIter = Iter<'a, K, V>;
1220 fn into_iter(self) -> Self::IntoIter {
1221 self.iter()
1222 }
1223 }
1224
1225 impl<'a, K, V, S> IntoIterator for &'a mut IndexMap<K, V, S> {
1226 type Item = (&'a K, &'a mut V);
1227 type IntoIter = IterMut<'a, K, V>;
1228 fn into_iter(self) -> Self::IntoIter {
1229 self.iter_mut()
1230 }
1231 }
1232
1233 impl<K, V, S> IntoIterator for IndexMap<K, V, S> {
1234 type Item = (K, V);
1235 type IntoIter = IntoIter<K, V>;
1236 fn into_iter(self) -> Self::IntoIter {
1237 IntoIter {
1238 iter: self.into_entries().into_iter(),
1239 }
1240 }
1241 }
1242
1243 /// Access `IndexMap` values corresponding to a key.
1244 ///
1245 /// # Examples
1246 ///
1247 /// ```
1248 /// use indexmap::IndexMap;
1249 ///
1250 /// let mut map = IndexMap::new();
1251 /// for word in "Lorem ipsum dolor sit amet".split_whitespace() {
1252 /// map.insert(word.to_lowercase(), word.to_uppercase());
1253 /// }
1254 /// assert_eq!(map["lorem"], "LOREM");
1255 /// assert_eq!(map["ipsum"], "IPSUM");
1256 /// ```
1257 ///
1258 /// ```should_panic
1259 /// use indexmap::IndexMap;
1260 ///
1261 /// let mut map = IndexMap::new();
1262 /// map.insert("foo", 1);
1263 /// println!("{:?}", map["bar"]); // panics!
1264 /// ```
1265 impl<K, V, Q: ?Sized, S> Index<&Q> for IndexMap<K, V, S>
1266 where
1267 Q: Hash + Equivalent<K>,
1268 K: Hash + Eq,
1269 S: BuildHasher,
1270 {
1271 type Output = V;
1272
1273 /// Returns a reference to the value corresponding to the supplied `key`.
1274 ///
1275 /// ***Panics*** if `key` is not present in the map.
1276 fn index(&self, key: &Q) -> &V {
1277 self.get(key).expect("IndexMap: key not found")
1278 }
1279 }
1280
1281 /// Access `IndexMap` values corresponding to a key.
1282 ///
1283 /// Mutable indexing allows changing / updating values of key-value
1284 /// pairs that are already present.
1285 ///
1286 /// You can **not** insert new pairs with index syntax, use `.insert()`.
1287 ///
1288 /// # Examples
1289 ///
1290 /// ```
1291 /// use indexmap::IndexMap;
1292 ///
1293 /// let mut map = IndexMap::new();
1294 /// for word in "Lorem ipsum dolor sit amet".split_whitespace() {
1295 /// map.insert(word.to_lowercase(), word.to_string());
1296 /// }
1297 /// let lorem = &mut map["lorem"];
1298 /// assert_eq!(lorem, "Lorem");
1299 /// lorem.retain(char::is_lowercase);
1300 /// assert_eq!(map["lorem"], "orem");
1301 /// ```
1302 ///
1303 /// ```should_panic
1304 /// use indexmap::IndexMap;
1305 ///
1306 /// let mut map = IndexMap::new();
1307 /// map.insert("foo", 1);
1308 /// map["bar"] = 1; // panics!
1309 /// ```
1310 impl<K, V, Q: ?Sized, S> IndexMut<&Q> for IndexMap<K, V, S>
1311 where
1312 Q: Hash + Equivalent<K>,
1313 K: Hash + Eq,
1314 S: BuildHasher,
1315 {
1316 /// Returns a mutable reference to the value corresponding to the supplied `key`.
1317 ///
1318 /// ***Panics*** if `key` is not present in the map.
1319 fn index_mut(&mut self, key: &Q) -> &mut V {
1320 self.get_mut(key).expect("IndexMap: key not found")
1321 }
1322 }
1323
1324 /// Access `IndexMap` values at indexed positions.
1325 ///
1326 /// # Examples
1327 ///
1328 /// ```
1329 /// use indexmap::IndexMap;
1330 ///
1331 /// let mut map = IndexMap::new();
1332 /// for word in "Lorem ipsum dolor sit amet".split_whitespace() {
1333 /// map.insert(word.to_lowercase(), word.to_uppercase());
1334 /// }
1335 /// assert_eq!(map[0], "LOREM");
1336 /// assert_eq!(map[1], "IPSUM");
1337 /// map.reverse();
1338 /// assert_eq!(map[0], "AMET");
1339 /// assert_eq!(map[1], "SIT");
1340 /// map.sort_keys();
1341 /// assert_eq!(map[0], "AMET");
1342 /// assert_eq!(map[1], "DOLOR");
1343 /// ```
1344 ///
1345 /// ```should_panic
1346 /// use indexmap::IndexMap;
1347 ///
1348 /// let mut map = IndexMap::new();
1349 /// map.insert("foo", 1);
1350 /// println!("{:?}", map[10]); // panics!
1351 /// ```
1352 impl<K, V, S> Index<usize> for IndexMap<K, V, S> {
1353 type Output = V;
1354
1355 /// Returns a reference to the value at the supplied `index`.
1356 ///
1357 /// ***Panics*** if `index` is out of bounds.
1358 fn index(&self, index: usize) -> &V {
1359 self.get_index(index)
1360 .expect("IndexMap: index out of bounds")
1361 .1
1362 }
1363 }
1364
1365 /// Access `IndexMap` values at indexed positions.
1366 ///
1367 /// Mutable indexing allows changing / updating indexed values
1368 /// that are already present.
1369 ///
1370 /// You can **not** insert new values with index syntax, use `.insert()`.
1371 ///
1372 /// # Examples
1373 ///
1374 /// ```
1375 /// use indexmap::IndexMap;
1376 ///
1377 /// let mut map = IndexMap::new();
1378 /// for word in "Lorem ipsum dolor sit amet".split_whitespace() {
1379 /// map.insert(word.to_lowercase(), word.to_string());
1380 /// }
1381 /// let lorem = &mut map[0];
1382 /// assert_eq!(lorem, "Lorem");
1383 /// lorem.retain(char::is_lowercase);
1384 /// assert_eq!(map["lorem"], "orem");
1385 /// ```
1386 ///
1387 /// ```should_panic
1388 /// use indexmap::IndexMap;
1389 ///
1390 /// let mut map = IndexMap::new();
1391 /// map.insert("foo", 1);
1392 /// map[10] = 1; // panics!
1393 /// ```
1394 impl<K, V, S> IndexMut<usize> for IndexMap<K, V, S> {
1395 /// Returns a mutable reference to the value at the supplied `index`.
1396 ///
1397 /// ***Panics*** if `index` is out of bounds.
1398 fn index_mut(&mut self, index: usize) -> &mut V {
1399 self.get_index_mut(index)
1400 .expect("IndexMap: index out of bounds")
1401 .1
1402 }
1403 }
1404
1405 impl<K, V, S> FromIterator<(K, V)> for IndexMap<K, V, S>
1406 where
1407 K: Hash + Eq,
1408 S: BuildHasher + Default,
1409 {
1410 /// Create an `IndexMap` from the sequence of key-value pairs in the
1411 /// iterable.
1412 ///
1413 /// `from_iter` uses the same logic as `extend`. See
1414 /// [`extend`](#method.extend) for more details.
1415 fn from_iter<I: IntoIterator<Item = (K, V)>>(iterable: I) -> Self {
1416 let iter = iterable.into_iter();
1417 let (low, _) = iter.size_hint();
1418 let mut map = Self::with_capacity_and_hasher(low, <_>::default());
1419 map.extend(iter);
1420 map
1421 }
1422 }
1423
1424 #[cfg(has_std)]
1425 impl<K, V, const N: usize> From<[(K, V); N]> for IndexMap<K, V, RandomState>
1426 where
1427 K: Hash + Eq,
1428 {
1429 /// # Examples
1430 ///
1431 /// ```
1432 /// use indexmap::IndexMap;
1433 ///
1434 /// let map1 = IndexMap::from([(1, 2), (3, 4)]);
1435 /// let map2: IndexMap<_, _> = [(1, 2), (3, 4)].into();
1436 /// assert_eq!(map1, map2);
1437 /// ```
1438 fn from(arr: [(K, V); N]) -> Self {
1439 Self::from_iter(arr)
1440 }
1441 }
1442
1443 impl<K, V, S> Extend<(K, V)> for IndexMap<K, V, S>
1444 where
1445 K: Hash + Eq,
1446 S: BuildHasher,
1447 {
1448 /// Extend the map with all key-value pairs in the iterable.
1449 ///
1450 /// This is equivalent to calling [`insert`](#method.insert) for each of
1451 /// them in order, which means that for keys that already existed
1452 /// in the map, their value is updated but it keeps the existing order.
1453 ///
1454 /// New keys are inserted in the order they appear in the sequence. If
1455 /// equivalents of a key occur more than once, the last corresponding value
1456 /// prevails.
1457 fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iterable: I) {
1458 // (Note: this is a copy of `std`/`hashbrown`'s reservation logic.)
1459 // Keys may be already present or show multiple times in the iterator.
1460 // Reserve the entire hint lower bound if the map is empty.
1461 // Otherwise reserve half the hint (rounded up), so the map
1462 // will only resize twice in the worst case.
1463 let iter = iterable.into_iter();
1464 let reserve = if self.is_empty() {
1465 iter.size_hint().0
1466 } else {
1467 (iter.size_hint().0 + 1) / 2
1468 };
1469 self.reserve(reserve);
1470 iter.for_each(move |(k, v)| {
1471 self.insert(k, v);
1472 });
1473 }
1474 }
1475
1476 impl<'a, K, V, S> Extend<(&'a K, &'a V)> for IndexMap<K, V, S>
1477 where
1478 K: Hash + Eq + Copy,
1479 V: Copy,
1480 S: BuildHasher,
1481 {
1482 /// Extend the map with all key-value pairs in the iterable.
1483 ///
1484 /// See the first extend method for more details.
1485 fn extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iterable: I) {
1486 self.extend(iterable.into_iter().map(|(&key, &value)| (key, value)));
1487 }
1488 }
1489
1490 impl<K, V, S> Default for IndexMap<K, V, S>
1491 where
1492 S: Default,
1493 {
1494 /// Return an empty `IndexMap`
1495 fn default() -> Self {
1496 Self::with_capacity_and_hasher(0, S::default())
1497 }
1498 }
1499
1500 impl<K, V1, S1, V2, S2> PartialEq<IndexMap<K, V2, S2>> for IndexMap<K, V1, S1>
1501 where
1502 K: Hash + Eq,
1503 V1: PartialEq<V2>,
1504 S1: BuildHasher,
1505 S2: BuildHasher,
1506 {
1507 fn eq(&self, other: &IndexMap<K, V2, S2>) -> bool {
1508 if self.len() != other.len() {
1509 return false;
1510 }
1511
1512 self.iter()
1513 .all(|(key, value)| other.get(key).map_or(false, |v| *value == *v))
1514 }
1515 }
1516
1517 impl<K, V, S> Eq for IndexMap<K, V, S>
1518 where
1519 K: Eq + Hash,
1520 V: Eq,
1521 S: BuildHasher,
1522 {
1523 }
1524
1525 #[cfg(test)]
1526 mod tests {
1527 use super::*;
1528 use std::string::String;
1529
1530 #[test]
1531 fn it_works() {
1532 let mut map = IndexMap::new();
1533 assert_eq!(map.is_empty(), true);
1534 map.insert(1, ());
1535 map.insert(1, ());
1536 assert_eq!(map.len(), 1);
1537 assert!(map.get(&1).is_some());
1538 assert_eq!(map.is_empty(), false);
1539 }
1540
1541 #[test]
1542 fn new() {
1543 let map = IndexMap::<String, String>::new();
1544 println!("{:?}", map);
1545 assert_eq!(map.capacity(), 0);
1546 assert_eq!(map.len(), 0);
1547 assert_eq!(map.is_empty(), true);
1548 }
1549
1550 #[test]
1551 fn insert() {
1552 let insert = [0, 4, 2, 12, 8, 7, 11, 5];
1553 let not_present = [1, 3, 6, 9, 10];
1554 let mut map = IndexMap::with_capacity(insert.len());
1555
1556 for (i, &elt) in insert.iter().enumerate() {
1557 assert_eq!(map.len(), i);
1558 map.insert(elt, elt);
1559 assert_eq!(map.len(), i + 1);
1560 assert_eq!(map.get(&elt), Some(&elt));
1561 assert_eq!(map[&elt], elt);
1562 }
1563 println!("{:?}", map);
1564
1565 for &elt in &not_present {
1566 assert!(map.get(&elt).is_none());
1567 }
1568 }
1569
1570 #[test]
1571 fn insert_full() {
1572 let insert = vec![9, 2, 7, 1, 4, 6, 13];
1573 let present = vec![1, 6, 2];
1574 let mut map = IndexMap::with_capacity(insert.len());
1575
1576 for (i, &elt) in insert.iter().enumerate() {
1577 assert_eq!(map.len(), i);
1578 let (index, existing) = map.insert_full(elt, elt);
1579 assert_eq!(existing, None);
1580 assert_eq!(Some(index), map.get_full(&elt).map(|x| x.0));
1581 assert_eq!(map.len(), i + 1);
1582 }
1583
1584 let len = map.len();
1585 for &elt in &present {
1586 let (index, existing) = map.insert_full(elt, elt);
1587 assert_eq!(existing, Some(elt));
1588 assert_eq!(Some(index), map.get_full(&elt).map(|x| x.0));
1589 assert_eq!(map.len(), len);
1590 }
1591 }
1592
1593 #[test]
1594 fn insert_2() {
1595 let mut map = IndexMap::with_capacity(16);
1596
1597 let mut keys = vec![];
1598 keys.extend(0..16);
1599 keys.extend(if cfg!(miri) { 32..64 } else { 128..267 });
1600
1601 for &i in &keys {
1602 let old_map = map.clone();
1603 map.insert(i, ());
1604 for key in old_map.keys() {
1605 if map.get(key).is_none() {
1606 println!("old_map: {:?}", old_map);
1607 println!("map: {:?}", map);
1608 panic!("did not find {} in map", key);
1609 }
1610 }
1611 }
1612
1613 for &i in &keys {
1614 assert!(map.get(&i).is_some(), "did not find {}", i);
1615 }
1616 }
1617
1618 #[test]
1619 fn insert_order() {
1620 let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23];
1621 let mut map = IndexMap::new();
1622
1623 for &elt in &insert {
1624 map.insert(elt, ());
1625 }
1626
1627 assert_eq!(map.keys().count(), map.len());
1628 assert_eq!(map.keys().count(), insert.len());
1629 for (a, b) in insert.iter().zip(map.keys()) {
1630 assert_eq!(a, b);
1631 }
1632 for (i, k) in (0..insert.len()).zip(map.keys()) {
1633 assert_eq!(map.get_index(i).unwrap().0, k);
1634 }
1635 }
1636
1637 #[test]
1638 fn grow() {
1639 let insert = [0, 4, 2, 12, 8, 7, 11];
1640 let not_present = [1, 3, 6, 9, 10];
1641 let mut map = IndexMap::with_capacity(insert.len());
1642
1643 for (i, &elt) in insert.iter().enumerate() {
1644 assert_eq!(map.len(), i);
1645 map.insert(elt, elt);
1646 assert_eq!(map.len(), i + 1);
1647 assert_eq!(map.get(&elt), Some(&elt));
1648 assert_eq!(map[&elt], elt);
1649 }
1650
1651 println!("{:?}", map);
1652 for &elt in &insert {
1653 map.insert(elt * 10, elt);
1654 }
1655 for &elt in &insert {
1656 map.insert(elt * 100, elt);
1657 }
1658 for (i, &elt) in insert.iter().cycle().enumerate().take(100) {
1659 map.insert(elt * 100 + i as i32, elt);
1660 }
1661 println!("{:?}", map);
1662 for &elt in &not_present {
1663 assert!(map.get(&elt).is_none());
1664 }
1665 }
1666
1667 #[test]
1668 fn reserve() {
1669 let mut map = IndexMap::<usize, usize>::new();
1670 assert_eq!(map.capacity(), 0);
1671 map.reserve(100);
1672 let capacity = map.capacity();
1673 assert!(capacity >= 100);
1674 for i in 0..capacity {
1675 assert_eq!(map.len(), i);
1676 map.insert(i, i * i);
1677 assert_eq!(map.len(), i + 1);
1678 assert_eq!(map.capacity(), capacity);
1679 assert_eq!(map.get(&i), Some(&(i * i)));
1680 }
1681 map.insert(capacity, std::usize::MAX);
1682 assert_eq!(map.len(), capacity + 1);
1683 assert!(map.capacity() > capacity);
1684 assert_eq!(map.get(&capacity), Some(&std::usize::MAX));
1685 }
1686
1687 #[test]
1688 fn shrink_to_fit() {
1689 let mut map = IndexMap::<usize, usize>::new();
1690 assert_eq!(map.capacity(), 0);
1691 for i in 0..100 {
1692 assert_eq!(map.len(), i);
1693 map.insert(i, i * i);
1694 assert_eq!(map.len(), i + 1);
1695 assert!(map.capacity() >= i + 1);
1696 assert_eq!(map.get(&i), Some(&(i * i)));
1697 map.shrink_to_fit();
1698 assert_eq!(map.len(), i + 1);
1699 assert_eq!(map.capacity(), i + 1);
1700 assert_eq!(map.get(&i), Some(&(i * i)));
1701 }
1702 }
1703
1704 #[test]
1705 fn remove() {
1706 let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23];
1707 let mut map = IndexMap::new();
1708
1709 for &elt in &insert {
1710 map.insert(elt, elt);
1711 }
1712
1713 assert_eq!(map.keys().count(), map.len());
1714 assert_eq!(map.keys().count(), insert.len());
1715 for (a, b) in insert.iter().zip(map.keys()) {
1716 assert_eq!(a, b);
1717 }
1718
1719 let remove_fail = [99, 77];
1720 let remove = [4, 12, 8, 7];
1721
1722 for &key in &remove_fail {
1723 assert!(map.swap_remove_full(&key).is_none());
1724 }
1725 println!("{:?}", map);
1726 for &key in &remove {
1727 //println!("{:?}", map);
1728 let index = map.get_full(&key).unwrap().0;
1729 assert_eq!(map.swap_remove_full(&key), Some((index, key, key)));
1730 }
1731 println!("{:?}", map);
1732
1733 for key in &insert {
1734 assert_eq!(map.get(key).is_some(), !remove.contains(key));
1735 }
1736 assert_eq!(map.len(), insert.len() - remove.len());
1737 assert_eq!(map.keys().count(), insert.len() - remove.len());
1738 }
1739
1740 #[test]
1741 fn remove_to_empty() {
1742 let mut map = indexmap! { 0 => 0, 4 => 4, 5 => 5 };
1743 map.swap_remove(&5).unwrap();
1744 map.swap_remove(&4).unwrap();
1745 map.swap_remove(&0).unwrap();
1746 assert!(map.is_empty());
1747 }
1748
1749 #[test]
1750 fn swap_remove_index() {
1751 let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23];
1752 let mut map = IndexMap::new();
1753
1754 for &elt in &insert {
1755 map.insert(elt, elt * 2);
1756 }
1757
1758 let mut vector = insert.to_vec();
1759 let remove_sequence = &[3, 3, 10, 4, 5, 4, 3, 0, 1];
1760
1761 // check that the same swap remove sequence on vec and map
1762 // have the same result.
1763 for &rm in remove_sequence {
1764 let out_vec = vector.swap_remove(rm);
1765 let (out_map, _) = map.swap_remove_index(rm).unwrap();
1766 assert_eq!(out_vec, out_map);
1767 }
1768 assert_eq!(vector.len(), map.len());
1769 for (a, b) in vector.iter().zip(map.keys()) {
1770 assert_eq!(a, b);
1771 }
1772 }
1773
1774 #[test]
1775 fn partial_eq_and_eq() {
1776 let mut map_a = IndexMap::new();
1777 map_a.insert(1, "1");
1778 map_a.insert(2, "2");
1779 let mut map_b = map_a.clone();
1780 assert_eq!(map_a, map_b);
1781 map_b.swap_remove(&1);
1782 assert_ne!(map_a, map_b);
1783
1784 let map_c: IndexMap<_, String> = map_b.into_iter().map(|(k, v)| (k, v.into())).collect();
1785 assert_ne!(map_a, map_c);
1786 assert_ne!(map_c, map_a);
1787 }
1788
1789 #[test]
1790 fn extend() {
1791 let mut map = IndexMap::new();
1792 map.extend(vec![(&1, &2), (&3, &4)]);
1793 map.extend(vec![(5, 6)]);
1794 assert_eq!(
1795 map.into_iter().collect::<Vec<_>>(),
1796 vec![(1, 2), (3, 4), (5, 6)]
1797 );
1798 }
1799
1800 #[test]
1801 fn entry() {
1802 let mut map = IndexMap::new();
1803
1804 map.insert(1, "1");
1805 map.insert(2, "2");
1806 {
1807 let e = map.entry(3);
1808 assert_eq!(e.index(), 2);
1809 let e = e.or_insert("3");
1810 assert_eq!(e, &"3");
1811 }
1812
1813 let e = map.entry(2);
1814 assert_eq!(e.index(), 1);
1815 assert_eq!(e.key(), &2);
1816 match e {
1817 Entry::Occupied(ref e) => assert_eq!(e.get(), &"2"),
1818 Entry::Vacant(_) => panic!(),
1819 }
1820 assert_eq!(e.or_insert("4"), &"2");
1821 }
1822
1823 #[test]
1824 fn entry_and_modify() {
1825 let mut map = IndexMap::new();
1826
1827 map.insert(1, "1");
1828 map.entry(1).and_modify(|x| *x = "2");
1829 assert_eq!(Some(&"2"), map.get(&1));
1830
1831 map.entry(2).and_modify(|x| *x = "doesn't exist");
1832 assert_eq!(None, map.get(&2));
1833 }
1834
1835 #[test]
1836 fn entry_or_default() {
1837 let mut map = IndexMap::new();
1838
1839 #[derive(Debug, PartialEq)]
1840 enum TestEnum {
1841 DefaultValue,
1842 NonDefaultValue,
1843 }
1844
1845 impl Default for TestEnum {
1846 fn default() -> Self {
1847 TestEnum::DefaultValue
1848 }
1849 }
1850
1851 map.insert(1, TestEnum::NonDefaultValue);
1852 assert_eq!(&mut TestEnum::NonDefaultValue, map.entry(1).or_default());
1853
1854 assert_eq!(&mut TestEnum::DefaultValue, map.entry(2).or_default());
1855 }
1856
1857 #[test]
1858 fn occupied_entry_key() {
1859 // These keys match hash and equality, but their addresses are distinct.
1860 let (k1, k2) = (&mut 1, &mut 1);
1861 let k1_ptr = k1 as *const i32;
1862 let k2_ptr = k2 as *const i32;
1863 assert_ne!(k1_ptr, k2_ptr);
1864
1865 let mut map = IndexMap::new();
1866 map.insert(k1, "value");
1867 match map.entry(k2) {
1868 Entry::Occupied(ref e) => {
1869 // `OccupiedEntry::key` should reference the key in the map,
1870 // not the key that was used to find the entry.
1871 let ptr = *e.key() as *const i32;
1872 assert_eq!(ptr, k1_ptr);
1873 assert_ne!(ptr, k2_ptr);
1874 }
1875 Entry::Vacant(_) => panic!(),
1876 }
1877 }
1878
1879 #[test]
1880 fn keys() {
1881 let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
1882 let map: IndexMap<_, _> = vec.into_iter().collect();
1883 let keys: Vec<_> = map.keys().copied().collect();
1884 assert_eq!(keys.len(), 3);
1885 assert!(keys.contains(&1));
1886 assert!(keys.contains(&2));
1887 assert!(keys.contains(&3));
1888 }
1889
1890 #[test]
1891 fn into_keys() {
1892 let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
1893 let map: IndexMap<_, _> = vec.into_iter().collect();
1894 let keys: Vec<i32> = map.into_keys().collect();
1895 assert_eq!(keys.len(), 3);
1896 assert!(keys.contains(&1));
1897 assert!(keys.contains(&2));
1898 assert!(keys.contains(&3));
1899 }
1900
1901 #[test]
1902 fn values() {
1903 let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
1904 let map: IndexMap<_, _> = vec.into_iter().collect();
1905 let values: Vec<_> = map.values().copied().collect();
1906 assert_eq!(values.len(), 3);
1907 assert!(values.contains(&'a'));
1908 assert!(values.contains(&'b'));
1909 assert!(values.contains(&'c'));
1910 }
1911
1912 #[test]
1913 fn values_mut() {
1914 let vec = vec![(1, 1), (2, 2), (3, 3)];
1915 let mut map: IndexMap<_, _> = vec.into_iter().collect();
1916 for value in map.values_mut() {
1917 *value *= 2
1918 }
1919 let values: Vec<_> = map.values().copied().collect();
1920 assert_eq!(values.len(), 3);
1921 assert!(values.contains(&2));
1922 assert!(values.contains(&4));
1923 assert!(values.contains(&6));
1924 }
1925
1926 #[test]
1927 fn into_values() {
1928 let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
1929 let map: IndexMap<_, _> = vec.into_iter().collect();
1930 let values: Vec<char> = map.into_values().collect();
1931 assert_eq!(values.len(), 3);
1932 assert!(values.contains(&'a'));
1933 assert!(values.contains(&'b'));
1934 assert!(values.contains(&'c'));
1935 }
1936
1937 #[test]
1938 #[cfg(has_std)]
1939 fn from_array() {
1940 let map = IndexMap::from([(1, 2), (3, 4)]);
1941 let mut expected = IndexMap::new();
1942 expected.insert(1, 2);
1943 expected.insert(3, 4);
1944
1945 assert_eq!(map, expected)
1946 }
1947 }