indexmap/
map.rs

Help
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
4mod core;
5
6pub use crate::mutable_keys::MutableKeys;
7
8#[cfg(feature = "rayon")]
9pub use crate::rayon::map as rayon;
10
11use crate::vec::{self, Vec};
12use ::core::cmp::Ordering;
13use ::core::fmt;
14use ::core::hash::{BuildHasher, Hash, Hasher};
15use ::core::iter::FusedIterator;
16use ::core::ops::{Index, IndexMut, RangeBounds};
17use ::core::slice::{Iter as SliceIter, IterMut as SliceIterMut};
18
19#[cfg(has_std)]
20use std::collections::hash_map::RandomState;
21
22use self::core::IndexMapCore;
23use crate::equivalent::Equivalent;
24use crate::util::third;
25use crate::{Bucket, Entries, HashValue};
26
27pub 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)]
71pub struct IndexMap<K, V, S = RandomState> {
72    pub(crate) core: IndexMapCore<K, V>,
73    hash_builder: S,
74}
75#[cfg(not(has_std))]
76pub struct IndexMap<K, V, S> {
77    pub(crate) core: IndexMapCore<K, V>,
78    hash_builder: S,
79}
80
81impl<K, V, S> Clone for IndexMap<K, V, S>
82where
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
100impl<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
126impl<K, V, S> fmt::Debug for IndexMap<K, V, S>
127where
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)]
144impl<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
161impl<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
319impl<K, V, S> IndexMap<K, V, S>
320where
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
775impl<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
876pub struct Keys<'a, K, V> {
877    iter: SliceIter<'a, Bucket<K, V>>,
878}
879
880impl<'a, K, V> Iterator for Keys<'a, K, V> {
881    type Item = &'a K;
882
883    iterator_methods!(Bucket::key_ref);
884}
885
886impl<K, V> DoubleEndedIterator for Keys<'_, K, V> {
887    double_ended_iterator_methods!(Bucket::key_ref);
888}
889
890impl<K, V> ExactSizeIterator for Keys<'_, K, V> {
891    fn len(&self) -> usize {
892        self.iter.len()
893    }
894}
895
896impl<K, V> FusedIterator for Keys<'_, K, V> {}
897
898// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
899impl<K, V> Clone for Keys<'_, K, V> {
900    fn clone(&self) -> Self {
901        Keys {
902            iter: self.iter.clone(),
903        }
904    }
905}
906
907impl<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
920pub struct IntoKeys<K, V> {
921    iter: vec::IntoIter<Bucket<K, V>>,
922}
923
924impl<K, V> Iterator for IntoKeys<K, V> {
925    type Item = K;
926
927    iterator_methods!(Bucket::key);
928}
929
930impl<K, V> DoubleEndedIterator for IntoKeys<K, V> {
931    double_ended_iterator_methods!(Bucket::key);
932}
933
934impl<K, V> ExactSizeIterator for IntoKeys<K, V> {
935    fn len(&self) -> usize {
936        self.iter.len()
937    }
938}
939
940impl<K, V> FusedIterator for IntoKeys<K, V> {}
941
942impl<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
956pub struct Values<'a, K, V> {
957    iter: SliceIter<'a, Bucket<K, V>>,
958}
959
960impl<'a, K, V> Iterator for Values<'a, K, V> {
961    type Item = &'a V;
962
963    iterator_methods!(Bucket::value_ref);
964}
965
966impl<K, V> DoubleEndedIterator for Values<'_, K, V> {
967    double_ended_iterator_methods!(Bucket::value_ref);
968}
969
970impl<K, V> ExactSizeIterator for Values<'_, K, V> {
971    fn len(&self) -> usize {
972        self.iter.len()
973    }
974}
975
976impl<K, V> FusedIterator for Values<'_, K, V> {}
977
978// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
979impl<K, V> Clone for Values<'_, K, V> {
980    fn clone(&self) -> Self {
981        Values {
982            iter: self.iter.clone(),
983        }
984    }
985}
986
987impl<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
1000pub struct ValuesMut<'a, K, V> {
1001    iter: SliceIterMut<'a, Bucket<K, V>>,
1002}
1003
1004impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
1005    type Item = &'a mut V;
1006
1007    iterator_methods!(Bucket::value_mut);
1008}
1009
1010impl<K, V> DoubleEndedIterator for ValuesMut<'_, K, V> {
1011    double_ended_iterator_methods!(Bucket::value_mut);
1012}
1013
1014impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> {
1015    fn len(&self) -> usize {
1016        self.iter.len()
1017    }
1018}
1019
1020impl<K, V> FusedIterator for ValuesMut<'_, K, V> {}
1021
1022impl<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
1036pub struct IntoValues<K, V> {
1037    iter: vec::IntoIter<Bucket<K, V>>,
1038}
1039
1040impl<K, V> Iterator for IntoValues<K, V> {
1041    type Item = V;
1042
1043    iterator_methods!(Bucket::value);
1044}
1045
1046impl<K, V> DoubleEndedIterator for IntoValues<K, V> {
1047    double_ended_iterator_methods!(Bucket::value);
1048}
1049
1050impl<K, V> ExactSizeIterator for IntoValues<K, V> {
1051    fn len(&self) -> usize {
1052        self.iter.len()
1053    }
1054}
1055
1056impl<K, V> FusedIterator for IntoValues<K, V> {}
1057
1058impl<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
1072pub struct Iter<'a, K, V> {
1073    iter: SliceIter<'a, Bucket<K, V>>,
1074}
1075
1076impl<'a, K, V> Iterator for Iter<'a, K, V> {
1077    type Item = (&'a K, &'a V);
1078
1079    iterator_methods!(Bucket::refs);
1080}
1081
1082impl<K, V> DoubleEndedIterator for Iter<'_, K, V> {
1083    double_ended_iterator_methods!(Bucket::refs);
1084}
1085
1086impl<K, V> ExactSizeIterator for Iter<'_, K, V> {
1087    fn len(&self) -> usize {
1088        self.iter.len()
1089    }
1090}
1091
1092impl<K, V> FusedIterator for Iter<'_, K, V> {}
1093
1094// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
1095impl<K, V> Clone for Iter<'_, K, V> {
1096    fn clone(&self) -> Self {
1097        Iter {
1098            iter: self.iter.clone(),
1099        }
1100    }
1101}
1102
1103impl<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
1116pub struct IterMut<'a, K, V> {
1117    iter: SliceIterMut<'a, Bucket<K, V>>,
1118}
1119
1120impl<'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
1126impl<K, V> DoubleEndedIterator for IterMut<'_, K, V> {
1127    double_ended_iterator_methods!(Bucket::ref_mut);
1128}
1129
1130impl<K, V> ExactSizeIterator for IterMut<'_, K, V> {
1131    fn len(&self) -> usize {
1132        self.iter.len()
1133    }
1134}
1135
1136impl<K, V> FusedIterator for IterMut<'_, K, V> {}
1137
1138impl<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
1152pub struct IntoIter<K, V> {
1153    iter: vec::IntoIter<Bucket<K, V>>,
1154}
1155
1156impl<K, V> Iterator for IntoIter<K, V> {
1157    type Item = (K, V);
1158
1159    iterator_methods!(Bucket::key_value);
1160}
1161
1162impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
1163    double_ended_iterator_methods!(Bucket::key_value);
1164}
1165
1166impl<K, V> ExactSizeIterator for IntoIter<K, V> {
1167    fn len(&self) -> usize {
1168        self.iter.len()
1169    }
1170}
1171
1172impl<K, V> FusedIterator for IntoIter<K, V> {}
1173
1174impl<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
1188pub struct Drain<'a, K, V> {
1189    pub(crate) iter: vec::Drain<'a, Bucket<K, V>>,
1190}
1191
1192impl<K, V> Iterator for Drain<'_, K, V> {
1193    type Item = (K, V);
1194
1195    iterator_methods!(Bucket::key_value);
1196}
1197
1198impl<K, V> DoubleEndedIterator for Drain<'_, K, V> {
1199    double_ended_iterator_methods!(Bucket::key_value);
1200}
1201
1202impl<K, V> ExactSizeIterator for Drain<'_, K, V> {
1203    fn len(&self) -> usize {
1204        self.iter.len()
1205    }
1206}
1207
1208impl<K, V> FusedIterator for Drain<'_, K, V> {}
1209
1210impl<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
1217impl<'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
1225impl<'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
1233impl<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/// ```
1265impl<K, V, Q: ?Sized, S> Index<&Q> for IndexMap<K, V, S>
1266where
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/// ```
1310impl<K, V, Q: ?Sized, S> IndexMut<&Q> for IndexMap<K, V, S>
1311where
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/// ```
1352impl<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/// ```
1394impl<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
1405impl<K, V, S> FromIterator<(K, V)> for IndexMap<K, V, S>
1406where
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)]
1425impl<K, V, const N: usize> From<[(K, V); N]> for IndexMap<K, V, RandomState>
1426where
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
1443impl<K, V, S> Extend<(K, V)> for IndexMap<K, V, S>
1444where
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
1476impl<'a, K, V, S> Extend<(&'a K, &'a V)> for IndexMap<K, V, S>
1477where
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
1490impl<K, V, S> Default for IndexMap<K, V, S>
1491where
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
1500impl<K, V1, S1, V2, S2> PartialEq<IndexMap<K, V2, S2>> for IndexMap<K, V1, S1>
1501where
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
1517impl<K, V, S> Eq for IndexMap<K, V, S>
1518where
1519    K: Eq + Hash,
1520    V: Eq,
1521    S: BuildHasher,
1522{
1523}
1524
1525#[cfg(test)]
1526mod 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}
indexmap/map.rs

indexmap/
map.rs
