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