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&mut DebugStruct<'_, '_>.debug_struct("IndexMap")
137 .field(name:"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: impl Iterator = 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: impl Iterator = 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: impl Iterator = 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: impl Iterator = 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: impl Iterator = 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: impl Iterator = 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(msg:"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(msg:"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(msg:"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(msg:"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: ::IntoIter = iterable.into_iter();
1417 let (low: usize, _) = iter.size_hint();
1418 let mut map: IndexMap = Self::with_capacity_and_hasher(n: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(iter:iterable.into_iter().map(|(&key: K, &value: V)| (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(n: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: &K, value: &V1)| other.get(key).map_or(default:false, |v: &V2| *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}
1948