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.
4 pub use mutable_keys
::MutableKeys
;
7 use std
::hash
::BuildHasher
;
9 use std
::iter
::FromIterator
;
10 use std
::collections
::hash_map
::RandomState
;
11 use std
::ops
::RangeFull
;
13 use std
::cmp
::{max, Ordering}
;
15 use std
::mem
::{replace}
;
16 use std
::marker
::PhantomData
;
18 use util
::{third, ptrdistance, enumerate}
;
19 use equivalent
::Equivalent
;
25 fn hash_elem_using
<B
: BuildHasher
, K
: ?Sized
+ Hash
>(build
: &B
, k
: &K
) -> HashValue
{
26 let mut h
= build
.build_hasher();
28 HashValue(h
.finish() as usize)
31 /// A possibly truncated hash value.
34 struct ShortHash
<Sz
>(usize, PhantomData
<Sz
>);
36 impl<Sz
> ShortHash
<Sz
> {
37 /// Pretend this is a full HashValue, which
38 /// is completely ok w.r.t determining bucket index
40 /// - Sz = u32: 32-bit hash is enough to select bucket index
41 /// - Sz = u64: hash is not truncated
42 fn into_hash(self) -> HashValue
{
47 impl<Sz
> Copy
for ShortHash
<Sz
> { }
48 impl<Sz
> Clone
for ShortHash
<Sz
> {
50 fn clone(&self) -> Self { *self }
53 impl<Sz
> PartialEq
for ShortHash
<Sz
> {
55 fn eq(&self, rhs
: &Self) -> bool
{
60 // Compare ShortHash == HashValue by truncating appropriately
61 // if applicable before the comparison
62 impl<Sz
> PartialEq
<HashValue
> for ShortHash
<Sz
> where Sz
: Size
{
64 fn eq(&self, rhs
: &HashValue
) -> bool
{
68 lo32(self.0 as u64) == lo32(rhs
.0 as u64)
72 impl<Sz
> From
<ShortHash
<Sz
>> for HashValue
{
73 fn from(x
: ShortHash
<Sz
>) -> Self { HashValue(x.0) }
76 /// `Pos` is stored in the `indices` array and it points to the index of a
77 /// `Bucket` in self.core.entries.
79 /// Pos can be interpreted either as a 64-bit index, or as a 32-bit index and
82 /// Storing the truncated hash next to the index saves loading the hash from the
83 /// entry, increasing the cache efficiency.
85 /// Note that the lower 32 bits of the hash is enough to compute desired
86 /// position and probe distance in a hash map with less than 2**32 buckets.
88 /// The IndexMap will simply query its **current raw capacity** to see what its
89 /// current size class is, and dispatch to the 32-bit or 64-bit lookup code as
90 /// appropriate. Only the growth code needs some extra logic to handle the
91 /// transition from one class to another
99 fn clone(&self) -> Self { *self }
102 impl fmt
::Debug
for Pos
{
103 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
105 Some(i
) => write
!(f
, "Pos({} / {:x})", i
, self.index
),
106 None
=> write
!(f
, "Pos(None)"),
113 fn none() -> Self { Pos { index: !0 }
}
116 fn is_none(&self) -> bool { self.index == !0 }
118 /// Return the index part of the Pos value inside `Some(_)` if the position
119 /// is not none, otherwise return `None`.
121 fn pos(&self) -> Option
<usize> {
122 if self.index
== !0 { None }
else { Some(lo32(self.index as u64)) }
125 /// Set the index part of the Pos value to `i`
127 fn set_pos
<Sz
>(&mut self, i
: usize)
130 debug_assert
!(!self.is_none());
132 self.index
= i
as u64;
134 self.index
= i
as u64 | ((self.index
>> 32) << 32)
139 fn with_hash
<Sz
>(i
: usize, hash
: HashValue
) -> Self
148 index
: i
as u64 | ((hash
.0 as u64) << 32)
153 /// “Resolve” the Pos into a combination of its index value and
154 /// a proxy value to the hash (whether it contains the hash or not
155 /// depends on the size class of the hash map).
157 fn resolve
<Sz
>(&self) -> Option
<(usize, ShortHashProxy
<Sz
>)>
162 Some((self.index
as usize, ShortHashProxy
::new(0)))
168 let (i
, hash
) = split_lo_hi(self.index
);
169 Some((i
as usize, ShortHashProxy
::new(hash
as usize)))
176 /// Like resolve, but the Pos **must** be non-none. Return its index.
178 fn resolve_existing_index
<Sz
>(&self) -> usize
181 debug_assert
!(!self.is_none(), "datastructure inconsistent: none where valid Pos expected");
185 let (i
, _
) = split_lo_hi(self.index
);
193 fn lo32(x
: u64) -> usize { (x & 0xFFFF_FFFF) as usize }
195 // split into low, hi parts
197 fn split_lo_hi(x
: u64) -> (u32, u32) { (x as u32, (x >> 32) as u32) }
199 // Possibly contains the truncated hash value for an entry, depending on
201 struct ShortHashProxy
<Sz
>(usize, PhantomData
<Sz
>);
203 impl<Sz
> ShortHashProxy
<Sz
>
206 fn new(x
: usize) -> Self {
207 ShortHashProxy(x
, PhantomData
)
210 /// Get the hash from either `self` or from a lookup into `entries`,
211 /// depending on `Sz`.
212 fn get_short_hash
<K
, V
>(&self, entries
: &[Bucket
<K
, V
>], index
: usize) -> ShortHash
<Sz
> {
214 ShortHash(entries
[index
].hash
.0, PhantomData
)
216 ShortHash(self.0, PhantomData
)
221 /// A hash table where the iteration order of the key-value pairs is independent
222 /// of the hash values of the keys.
224 /// The interface is closely compatible with the standard `HashMap`, but also
225 /// has additional features.
229 /// The key-value pairs have a consistent order that is determined by
230 /// the sequence of insertion and removal calls on the map. The order does
231 /// not depend on the keys or the hash function at all.
233 /// All iterators traverse the map in *the order*.
235 /// The insertion order is preserved, with **notable exceptions** like the
236 /// `.remove()` or `.swap_remove()` methods. Methods such as `.sort_by()` of
237 /// course result in a new order, depending on the sorting order.
241 /// The key-value pairs are indexed in a compact range without holes in the
242 /// range `0..self.len()`. For example, the method `.get_full` looks up the
243 /// index for a key, and the method `.get_index` looks up the key-value pair by
249 /// use indexmap::IndexMap;
251 /// // count the frequency of each letter in a sentence.
252 /// let mut letters = IndexMap::new();
253 /// for ch in "a short treatise on fungi".chars() {
254 /// *letters.entry(ch).or_insert(0) += 1;
257 /// assert_eq!(letters[&'s'], 2);
258 /// assert_eq!(letters[&'t'], 3);
259 /// assert_eq!(letters[&'u'], 1);
260 /// assert_eq!(letters.get(&'y'), None);
263 pub struct IndexMap
<K
, V
, S
= RandomState
> {
264 core
: OrderMapCore
<K
, V
>,
268 // core of the map that does not depend on S
270 struct OrderMapCore
<K
, V
> {
271 pub(crate) mask
: usize,
272 /// indices are the buckets. indices.len() == raw capacity
273 pub(crate) indices
: Box
<[Pos
]>,
274 /// entries is a dense vec of entries in their order. entries.len() == len
275 pub(crate) entries
: Vec
<Bucket
<K
, V
>>,
279 fn desired_pos(mask
: usize, hash
: HashValue
) -> usize {
283 /// The number of steps that `current` is forward of the desired position for hash
285 fn probe_distance(mask
: usize, hash
: HashValue
, current
: usize) -> usize {
286 current
.wrapping_sub(desired_pos(mask
, hash
)) & mask
291 Swapped { prev_value: V }
,
298 impl<K
, V
, S
> fmt
::Debug
for IndexMap
<K
, V
, S
>
299 where K
: fmt
::Debug
+ Hash
+ Eq
,
303 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
304 try
!(f
.debug_map().entries(self.iter()).finish());
305 if cfg
!(not(feature
= "test_debug")) {
308 try
!(writeln
!(f
, ""));
309 for (i
, index
) in enumerate(&*self.core
.indices
) {
310 try
!(write
!(f
, "{}: {:?}", i
, index
));
311 if let Some(pos
) = index
.pos() {
312 let hash
= self.core
.entries
[pos
].hash
;
313 let key
= &self.core
.entries
[pos
].key
;
314 let desire
= desired_pos(self.core
.mask
, hash
);
315 try
!(write
!(f
, ", desired={}, probe_distance={}, key={:?}",
317 probe_distance(self.core
.mask
, hash
, i
),
320 try
!(writeln
!(f
, ""));
322 try
!(writeln
!(f
, "cap={}, raw_cap={}, entries.cap={}",
325 self.core
.entries
.capacity()));
331 fn usable_capacity(cap
: usize) -> usize {
336 fn to_raw_capacity(n
: usize) -> usize {
340 // this could not be captured in an efficient iterator
341 macro_rules
! probe_loop
{
342 ($probe_var
: ident
< $len
: expr
, $body
: expr
) => {
344 if $probe_var
< $len
{
354 impl<K
, V
> IndexMap
<K
, V
> {
355 /// Create a new map. (Does not allocate.)
356 pub fn new() -> Self {
357 Self::with_capacity(0)
360 /// Create a new map with capacity for `n` key-value pairs. (Does not
361 /// allocate if `n` is zero.)
363 /// Computes in **O(n)** time.
364 pub fn with_capacity(n
: usize) -> Self {
365 Self::with_capacity_and_hasher(n
, <_
>::default())
369 impl<K
, V
, S
> IndexMap
<K
, V
, S
>
371 /// Create a new map with capacity for `n` key-value pairs. (Does not
372 /// allocate if `n` is zero.)
374 /// Computes in **O(n)** time.
375 pub fn with_capacity_and_hasher(n
: usize, hash_builder
: S
) -> Self
382 indices
: Box
::new([]),
385 hash_builder
: hash_builder
,
388 let raw
= to_raw_capacity(n
);
389 let raw_cap
= max(raw
.next_power_of_two(), 8);
392 mask
: raw_cap
.wrapping_sub(1),
393 indices
: vec
![Pos
::none(); raw_cap
].into_boxed_slice(),
394 entries
: Vec
::with_capacity(usable_capacity(raw_cap
)),
396 hash_builder
: hash_builder
,
401 /// Return the number of key-value pairs in the map.
403 /// Computes in **O(1)** time.
404 pub fn len(&self) -> usize { self.core.len() }
406 /// Returns true if the map contains no elements.
408 /// Computes in **O(1)** time.
409 pub fn is_empty(&self) -> bool { self.len() == 0 }
411 /// Create a new map with `hash_builder`
412 pub fn with_hasher(hash_builder
: S
) -> Self
415 Self::with_capacity_and_hasher(0, hash_builder
)
418 /// Return a reference to the map's `BuildHasher`.
419 pub fn hasher(&self) -> &S
425 /// Computes in **O(1)** time.
426 pub fn capacity(&self) -> usize {
431 fn size_class_is_64bit(&self) -> bool
{
432 self.core
.size_class_is_64bit()
436 fn raw_capacity(&self) -> usize {
437 self.core
.raw_capacity()
441 impl<K
, V
> OrderMapCore
<K
, V
> {
442 // Return whether we need 32 or 64 bits to specify a bucket or entry index
443 #[cfg(not(feature = "test_low_transition_point"))]
444 fn size_class_is_64bit(&self) -> bool
{
445 usize::max_value() > u32::max_value() as usize &&
446 self.raw_capacity() >= u32::max_value() as usize
450 #[cfg(feature = "test_low_transition_point")]
451 fn size_class_is_64bit(&self) -> bool
{
452 self.raw_capacity() >= 64
456 fn raw_capacity(&self) -> usize {
461 /// Trait for the "size class". Either u32 or u64 depending on the index
462 /// size needed to address an entry's indes in self.core.entries.
464 fn is_64_bit() -> bool
;
465 fn is_same_size
<T
: Size
>() -> bool
{
466 Self::is_64_bit() == T
::is_64_bit()
472 fn is_64_bit() -> bool { false }
477 fn is_64_bit() -> bool { true }
480 /// Call self.method(args) with `::<u32>` or `::<u64>` depending on `self`
483 /// The u32 or u64 is *prepended* to the type parameter list!
484 macro_rules
! dispatch_32_vs_64
{
485 // self.methodname with other explicit type params,
487 ($self_
:ident
. $method
:ident
::<$
($t
:ty
),*>($
($arg
:expr
),*)) => {
488 if $self_
.size_class_is_64bit() {
489 $self_
.$method
::<u64, $
($t
),*>($
($arg
),*)
491 $self_
.$method
::<u32, $
($t
),*>($
($arg
),*)
494 // self.methodname with only one type param, the size.
495 ($self_
:ident
. $method
:ident ($
($arg
:expr
),*)) => {
496 if $self_
.size_class_is_64bit() {
497 $self_
.$method
::<u64>($
($arg
),*)
499 $self_
.$method
::<u32>($
($arg
),*)
502 // functionname with size_class_is_64bit as the first argument, only one
503 // type param, the size.
504 ($self_
:ident
=> $function
:ident ($
($arg
:expr
),*)) => {
505 if $self_
.size_class_is_64bit() {
506 $function
::<u64>($
($arg
),*)
508 $function
::<u32>($
($arg
),*)
513 /// Entry for an existing key-value pair or a vacant location to
515 pub enum Entry
<'a
, K
: 'a
, V
: 'a
> {
516 /// Existing slot with equivalent key.
517 Occupied(OccupiedEntry
<'a
, K
, V
>),
518 /// Vacant slot (no equivalent key in the map).
519 Vacant(VacantEntry
<'a
, K
, V
>),
522 impl<'a
, K
, V
> Entry
<'a
, K
, V
> {
523 /// Computes in **O(1)** time (amortized average).
524 pub fn or_insert(self, default: V
) -> &'a
mut V
{
526 Entry
::Occupied(entry
) => entry
.into_mut(),
527 Entry
::Vacant(entry
) => entry
.insert(default),
531 /// Computes in **O(1)** time (amortized average).
532 pub fn or_insert_with
<F
>(self, call
: F
) -> &'a
mut V
533 where F
: FnOnce() -> V
,
536 Entry
::Occupied(entry
) => entry
.into_mut(),
537 Entry
::Vacant(entry
) => entry
.insert(call()),
541 pub fn key(&self) -> &K
{
543 Entry
::Occupied(ref entry
) => entry
.key(),
544 Entry
::Vacant(ref entry
) => entry
.key(),
548 /// Return the index where the key-value pair exists or will be inserted.
549 pub fn index(&self) -> usize {
551 Entry
::Occupied(ref entry
) => entry
.index(),
552 Entry
::Vacant(ref entry
) => entry
.index(),
556 /// Modifies the entry if it is occupied.
557 pub fn and_modify
<F
>(self, f
: F
) -> Self
558 where F
: FnOnce(&mut V
),
561 Entry
::Occupied(mut o
) => {
569 /// Inserts a default-constructed value in the entry if it is vacant and returns a mutable
570 /// reference to it. Otherwise a mutable reference to an already existent value is returned.
572 /// Computes in **O(1)** time (amortized average).
573 pub fn or_default(self) -> &'a
mut V
577 Entry
::Occupied(entry
) => entry
.into_mut(),
578 Entry
::Vacant(entry
) => entry
.insert(V
::default()),
583 pub struct OccupiedEntry
<'a
, K
: 'a
, V
: 'a
> {
584 map
: &'a
mut OrderMapCore
<K
, V
>,
590 impl<'a
, K
, V
> OccupiedEntry
<'a
, K
, V
> {
591 pub fn key(&self) -> &K { &self.key }
592 pub fn get(&self) -> &V
{
593 &self.map
.entries
[self.index
].value
595 pub fn get_mut(&mut self) -> &mut V
{
596 &mut self.map
.entries
[self.index
].value
599 /// Put the new key in the occupied entry's key slot
600 pub(crate) fn replace_key(self) -> K
{
601 let old_key
= &mut self.map
.entries
[self.index
].key
;
602 replace(old_key
, self.key
)
605 /// Return the index of the key-value pair
606 pub fn index(&self) -> usize {
609 pub fn into_mut(self) -> &'a
mut V
{
610 &mut self.map
.entries
[self.index
].value
613 /// Sets the value of the entry to `value`, and returns the entry's old value.
614 pub fn insert(&mut self, value
: V
) -> V
{
615 replace(self.get_mut(), value
)
618 pub fn remove(self) -> V
{
619 self.remove_entry().1
622 /// Remove and return the key, value pair stored in the map for this entry
623 pub fn remove_entry(self) -> (K
, V
) {
624 self.map
.remove_found(self.probe
, self.index
)
629 pub struct VacantEntry
<'a
, K
: 'a
, V
: 'a
> {
630 map
: &'a
mut OrderMapCore
<K
, V
>,
636 impl<'a
, K
, V
> VacantEntry
<'a
, K
, V
> {
637 pub fn key(&self) -> &K { &self.key }
638 pub fn into_key(self) -> K { self.key }
639 /// Return the index where the key-value pair will be inserted.
640 pub fn index(&self) -> usize { self.map.len() }
641 pub fn insert(self, value
: V
) -> &'a
mut V
{
642 if self.map
.size_class_is_64bit() {
643 self.insert_impl
::<u64>(value
)
645 self.insert_impl
::<u32>(value
)
649 fn insert_impl
<Sz
>(self, value
: V
) -> &'a
mut V
652 let index
= self.map
.entries
.len();
653 self.map
.entries
.push(Bucket { hash: self.hash, key: self.key, value: value }
);
654 let old_pos
= Pos
::with_hash
::<Sz
>(index
, self.hash
);
655 self.map
.insert_phase_2
::<Sz
>(self.probe
, old_pos
);
656 &mut {self.map}
.entries
[index
].value
660 impl<K
, V
, S
> IndexMap
<K
, V
, S
>
664 // FIXME: reduce duplication (compare with insert)
665 fn entry_phase_1
<Sz
>(&mut self, key
: K
) -> Entry
<K
, V
>
668 let hash
= hash_elem_using(&self.hash_builder
, &key
);
669 self.core
.entry_phase_1
::<Sz
>(hash
, key
)
672 /// Remove all key-value pairs in the map, while preserving its capacity.
674 /// Computes in **O(n)** time.
675 pub fn clear(&mut self) {
679 /// Reserve capacity for `additional` more key-value pairs.
681 /// FIXME Not implemented fully yet.
682 pub fn reserve(&mut self, additional
: usize) {
688 // First phase: Look for the preferred location for key.
690 // We will know if `key` is already in the map, before we need to insert it.
691 // When we insert they key, it might be that we need to continue displacing
692 // entries (robin hood hashing), in which case Inserted::RobinHood is returned
693 fn insert_phase_1
<Sz
>(&mut self, key
: K
, value
: V
) -> Inserted
<V
>
696 let hash
= hash_elem_using(&self.hash_builder
, &key
);
697 self.core
.insert_phase_1
::<Sz
>(hash
, key
, value
)
700 fn reserve_one(&mut self) {
701 if self.len() == self.capacity() {
702 dispatch_32_vs_64
!(self.double_capacity());
705 fn double_capacity
<Sz
>(&mut self)
708 self.core
.double_capacity
::<Sz
>();
711 /// Insert a key-value pair in the map.
713 /// If an equivalent key already exists in the map: the key remains and
714 /// retains in its place in the order, its corresponding value is updated
715 /// with `value` and the older value is returned inside `Some(_)`.
717 /// If no equivalent key existed in the map: the new key-value pair is
718 /// inserted, last in order, and `None` is returned.
720 /// Computes in **O(1)** time (amortized average).
722 /// See also [`entry`](#method.entry) if you you want to insert *or* modify
723 /// or if you need to get the index of the corresponding key-value pair.
724 pub fn insert(&mut self, key
: K
, value
: V
) -> Option
<V
> {
726 if self.size_class_is_64bit() {
727 match self.insert_phase_1
::<u64>(key
, value
) {
728 Inserted
::Swapped { prev_value }
=> Some(prev_value
),
729 Inserted
::Done
=> None
,
730 Inserted
::RobinHood { probe, old_pos }
=> {
731 self.core
.insert_phase_2
::<u64>(probe
, old_pos
);
736 match self.insert_phase_1
::<u32>(key
, value
) {
737 Inserted
::Swapped { prev_value }
=> Some(prev_value
),
738 Inserted
::Done
=> None
,
739 Inserted
::RobinHood { probe, old_pos }
=> {
740 self.core
.insert_phase_2
::<u32>(probe
, old_pos
);
747 /// Insert a key-value pair in the map, and get their index.
749 /// If an equivalent key already exists in the map: the key remains and
750 /// retains in its place in the order, its corresponding value is updated
751 /// with `value` and the older value is returned inside `(index, Some(_))`.
753 /// If no equivalent key existed in the map: the new key-value pair is
754 /// inserted, last in order, and `(index, None)` is returned.
756 /// Computes in **O(1)** time (amortized average).
758 /// See also [`entry`](#method.entry) if you you want to insert *or* modify
759 /// or if you need to get the index of the corresponding key-value pair.
760 pub fn insert_full(&mut self, key
: K
, value
: V
) -> (usize, Option
<V
>) {
761 let entry
= self.entry(key
);
762 let index
= entry
.index();
765 Entry
::Occupied(mut entry
) => (index
, Some(entry
.insert(value
))),
766 Entry
::Vacant(entry
) => {
773 /// Get the given key’s corresponding entry in the map for insertion and/or
774 /// in-place manipulation.
776 /// Computes in **O(1)** time (amortized average).
777 pub fn entry(&mut self, key
: K
) -> Entry
<K
, V
> {
779 dispatch_32_vs_64
!(self.entry_phase_1(key
))
783 /// Return an iterator over the key-value pairs of the map, in their order
784 pub fn iter(&self) -> Iter
<K
, V
> {
786 iter
: self.core
.entries
.iter()
790 /// Return an iterator over the key-value pairs of the map, in their order
791 pub fn iter_mut(&mut self) -> IterMut
<K
, V
> {
793 iter
: self.core
.entries
.iter_mut()
797 /// Return an iterator over the keys of the map, in their order
798 pub fn keys(&self) -> Keys
<K
, V
> {
800 iter
: self.core
.entries
.iter()
804 /// Return an iterator over the values of the map, in their order
805 pub fn values(&self) -> Values
<K
, V
> {
807 iter
: self.core
.entries
.iter()
811 /// Return an iterator over mutable references to the the values of the map,
813 pub fn values_mut(&mut self) -> ValuesMut
<K
, V
> {
815 iter
: self.core
.entries
.iter_mut()
819 /// Return `true` if an equivalent to `key` exists in the map.
821 /// Computes in **O(1)** time (average).
822 pub fn contains_key
<Q
: ?Sized
>(&self, key
: &Q
) -> bool
823 where Q
: Hash
+ Equivalent
<K
>,
825 self.find(key
).is_some()
828 /// Return a reference to the value stored for `key`, if it is present,
831 /// Computes in **O(1)** time (average).
832 pub fn get
<Q
: ?Sized
>(&self, key
: &Q
) -> Option
<&V
>
833 where Q
: Hash
+ Equivalent
<K
>,
835 self.get_full(key
).map(third
)
838 /// Return item index, key and value
839 pub fn get_full
<Q
: ?Sized
>(&self, key
: &Q
) -> Option
<(usize, &K
, &V
)>
840 where Q
: Hash
+ Equivalent
<K
>,
842 if let Some((_
, found
)) = self.find(key
) {
843 let entry
= &self.core
.entries
[found
];
844 Some((found
, &entry
.key
, &entry
.value
))
850 pub fn get_mut
<Q
: ?Sized
>(&mut self, key
: &Q
) -> Option
<&mut V
>
851 where Q
: Hash
+ Equivalent
<K
>,
853 self.get_full_mut(key
).map(third
)
856 pub fn get_full_mut
<Q
: ?Sized
>(&mut self, key
: &Q
)
857 -> Option
<(usize, &K
, &mut V
)>
858 where Q
: Hash
+ Equivalent
<K
>,
860 self.get_full_mut2_impl(key
).map(|(i
, k
, v
)| (i
, &*k
, v
))
864 pub(crate) fn get_full_mut2_impl
<Q
: ?Sized
>(&mut self, key
: &Q
)
865 -> Option
<(usize, &mut K
, &mut V
)>
866 where Q
: Hash
+ Equivalent
<K
>,
868 if let Some((_
, found
)) = self.find(key
) {
869 let entry
= &mut self.core
.entries
[found
];
870 Some((found
, &mut entry
.key
, &mut entry
.value
))
877 /// Return probe (indices) and position (entries)
878 pub(crate) fn find
<Q
: ?Sized
>(&self, key
: &Q
) -> Option
<(usize, usize)>
879 where Q
: Hash
+ Equivalent
<K
>,
881 if self.len() == 0 { return None; }
882 let h
= hash_elem_using(&self.hash_builder
, key
);
883 self.core
.find_using(h
, move |entry
| { Q::equivalent(key, &entry.key) }
)
886 /// NOTE: Same as .swap_remove
888 /// Computes in **O(1)** time (average).
889 pub fn remove
<Q
: ?Sized
>(&mut self, key
: &Q
) -> Option
<V
>
890 where Q
: Hash
+ Equivalent
<K
>,
892 self.swap_remove(key
)
895 /// Remove the key-value pair equivalent to `key` and return
898 /// Like `Vec::swap_remove`, the pair is removed by swapping it with the
899 /// last element of the map and popping it off. **This perturbs
900 /// the postion of what used to be the last element!**
902 /// Return `None` if `key` is not in map.
904 /// Computes in **O(1)** time (average).
905 pub fn swap_remove
<Q
: ?Sized
>(&mut self, key
: &Q
) -> Option
<V
>
906 where Q
: Hash
+ Equivalent
<K
>,
908 self.swap_remove_full(key
).map(third
)
911 /// Remove the key-value pair equivalent to `key` and return it and
912 /// the index it had.
914 /// Like `Vec::swap_remove`, the pair is removed by swapping it with the
915 /// last element of the map and popping it off. **This perturbs
916 /// the postion of what used to be the last element!**
918 /// Return `None` if `key` is not in map.
919 pub fn swap_remove_full
<Q
: ?Sized
>(&mut self, key
: &Q
) -> Option
<(usize, K
, V
)>
920 where Q
: Hash
+ Equivalent
<K
>,
922 let (probe
, found
) = match self.find(key
) {
926 let (k
, v
) = self.core
.remove_found(probe
, found
);
930 /// Remove the last key-value pair
932 /// Computes in **O(1)** time (average).
933 pub fn pop(&mut self) -> Option
<(K
, V
)> {
937 /// Scan through each key-value pair in the map and keep those where the
938 /// closure `keep` returns `true`.
940 /// The elements are visited in order, and remaining elements keep their
943 /// Computes in **O(n)** time (average).
944 pub fn retain
<F
>(&mut self, mut keep
: F
)
945 where F
: FnMut(&K
, &mut V
) -> bool
,
947 self.retain_mut(move |k
, v
| keep(k
, v
));
950 pub(crate) fn retain_mut
<F
>(&mut self, keep
: F
)
951 where F
: FnMut(&mut K
, &mut V
) -> bool
,
953 dispatch_32_vs_64
!(self.retain_mut_sz
::<_
>(keep
));
956 fn retain_mut_sz
<Sz
, F
>(&mut self, keep
: F
)
957 where F
: FnMut(&mut K
, &mut V
) -> bool
,
960 self.core
.retain_in_order_impl
::<Sz
, F
>(keep
);
963 /// Sort the map’s key-value pairs by the default ordering of the keys.
965 /// See `sort_by` for details.
966 pub fn sort_keys(&mut self)
969 self.core
.sort_by(key_cmp
)
972 /// Sort the map’s key-value pairs in place using the comparison
973 /// function `compare`.
975 /// The comparison function receives two key and value pairs to compare (you
976 /// can sort by keys or values or their combination as needed).
978 /// Computes in **O(n log n + c)** time and **O(n)** space where *n* is
979 /// the length of the map and *c* the capacity. The sort is stable.
980 pub fn sort_by
<F
>(&mut self, compare
: F
)
981 where F
: FnMut(&K
, &V
, &K
, &V
) -> Ordering
,
983 self.core
.sort_by(compare
)
986 /// Sort the key-value pairs of the map and return a by value iterator of
987 /// the key-value pairs with the result.
989 /// The sort is stable.
990 pub fn sorted_by
<F
>(mut self, mut cmp
: F
) -> IntoIter
<K
, V
>
991 where F
: FnMut(&K
, &V
, &K
, &V
) -> Ordering
993 self.core
.entries
.sort_by(move |a
, b
| cmp(&a
.key
, &a
.value
, &b
.key
, &b
.value
));
997 /// Clears the `IndexMap`, returning all key-value pairs as a drain iterator.
998 /// Keeps the allocated memory for reuse.
999 pub fn drain(&mut self, range
: RangeFull
) -> Drain
<K
, V
> {
1000 self.core
.clear_indices();
1003 iter
: self.core
.entries
.drain(range
),
1008 fn key_cmp
<K
, V
>(k1
: &K
, _v1
: &V
, k2
: &K
, _v2
: &V
) -> Ordering
1014 impl<K
, V
, S
> IndexMap
<K
, V
, S
> {
1015 /// Get a key-value pair by index
1017 /// Valid indices are *0 <= index < self.len()*
1019 /// Computes in **O(1)** time.
1020 pub fn get_index(&self, index
: usize) -> Option
<(&K
, &V
)> {
1021 self.core
.entries
.get(index
).map(Bucket
::refs
)
1024 /// Get a key-value pair by index
1026 /// Valid indices are *0 <= index < self.len()*
1028 /// Computes in **O(1)** time.
1029 pub fn get_index_mut(&mut self, index
: usize) -> Option
<(&mut K
, &mut V
)> {
1030 self.core
.entries
.get_mut(index
).map(Bucket
::muts
)
1033 /// Remove the key-value pair by index
1035 /// Valid indices are *0 <= index < self.len()*
1037 /// Computes in **O(1)** time (average).
1038 pub fn swap_remove_index(&mut self, index
: usize) -> Option
<(K
, V
)> {
1039 let (probe
, found
) = match self.core
.entries
.get(index
)
1040 .map(|e
| self.core
.find_existing_entry(e
))
1042 None
=> return None
,
1045 Some(self.core
.remove_found(probe
, found
))
1049 // Methods that don't use any properties (Hash / Eq) of K.
1051 // It's cleaner to separate them out, then the compiler checks that we are not
1052 // using Hash + Eq at all in these methods.
1054 // However, we should probably not let this show in the public API or docs.
1055 impl<K
, V
> OrderMapCore
<K
, V
> {
1056 fn len(&self) -> usize { self.entries.len() }
1058 fn capacity(&self) -> usize {
1059 usable_capacity(self.raw_capacity())
1062 fn clear(&mut self) {
1063 self.entries
.clear();
1064 self.clear_indices();
1067 // clear self.indices to the same state as "no elements"
1068 fn clear_indices(&mut self) {
1069 for pos
in self.indices
.iter_mut() {
1074 fn first_allocation(&mut self) {
1075 debug_assert_eq
!(self.len(), 0);
1076 let raw_cap
= 8usize
;
1077 self.mask
= raw_cap
.wrapping_sub(1);
1078 self.indices
= vec
![Pos
::none(); raw_cap
].into_boxed_slice();
1079 self.entries
= Vec
::with_capacity(usable_capacity(raw_cap
));
1083 // `Sz` is *current* Size class, before grow
1084 fn double_capacity
<Sz
>(&mut self)
1087 debug_assert
!(self.raw_capacity() == 0 || self.len() > 0);
1088 if self.raw_capacity() == 0 {
1089 return self.first_allocation();
1092 // find first ideally placed element -- start of cluster
1093 let mut first_ideal
= 0;
1094 for (i
, index
) in enumerate(&*self.indices
) {
1095 if let Some(pos
) = index
.pos() {
1096 if 0 == probe_distance(self.mask
, self.entries
[pos
].hash
, i
) {
1103 // visit the entries in an order where we can simply reinsert them
1104 // into self.indices without any bucket stealing.
1105 let new_raw_cap
= self.indices
.len() * 2;
1106 let old_indices
= replace(&mut self.indices
, vec
![Pos
::none(); new_raw_cap
].into_boxed_slice());
1107 self.mask
= new_raw_cap
.wrapping_sub(1);
1109 // `Sz` is the old size class, and either u32 or u64 is the new
1110 for &pos
in &old_indices
[first_ideal
..] {
1111 dispatch_32_vs_64
!(self.reinsert_entry_in_order
::<Sz
>(pos
));
1114 for &pos
in &old_indices
[..first_ideal
] {
1115 dispatch_32_vs_64
!(self.reinsert_entry_in_order
::<Sz
>(pos
));
1117 let more
= self.capacity() - self.len();
1118 self.entries
.reserve_exact(more
);
1121 // write to self.indices
1122 // read from self.entries at `pos`
1124 // reinserting rewrites all `Pos` entries anyway. This handles transitioning
1125 // from u32 to u64 size class if needed by using the two type parameters.
1126 fn reinsert_entry_in_order
<SzNew
, SzOld
>(&mut self, pos
: Pos
)
1130 if let Some((i
, hash_proxy
)) = pos
.resolve
::<SzOld
>() {
1131 // only if the size class is conserved can we use the short hash
1132 let entry_hash
= if SzOld
::is_same_size
::<SzNew
>() {
1133 hash_proxy
.get_short_hash(&self.entries
, i
).into_hash()
1135 self.entries
[i
].hash
1137 // find first empty bucket and insert there
1138 let mut probe
= desired_pos(self.mask
, entry_hash
);
1139 probe_loop
!(probe
< self.indices
.len(), {
1140 if let Some(_
) = self.indices
[probe
].resolve
::<SzNew
>() {
1143 // empty bucket, insert here
1144 self.indices
[probe
] = Pos
::with_hash
::<SzNew
>(i
, entry_hash
);
1151 fn pop_impl(&mut self) -> Option
<(K
, V
)> {
1152 let (probe
, found
) = match self.entries
.last()
1153 .map(|e
| self.find_existing_entry(e
))
1155 None
=> return None
,
1158 debug_assert_eq
!(found
, self.entries
.len() - 1);
1159 Some(self.remove_found(probe
, found
))
1162 // FIXME: reduce duplication (compare with insert)
1163 fn entry_phase_1
<Sz
>(&mut self, hash
: HashValue
, key
: K
) -> Entry
<K
, V
>
1167 let mut probe
= desired_pos(self.mask
, hash
);
1169 debug_assert
!(self.len() < self.raw_capacity());
1170 probe_loop
!(probe
< self.indices
.len(), {
1171 if let Some((i
, hash_proxy
)) = self.indices
[probe
].resolve
::<Sz
>() {
1172 let entry_hash
= hash_proxy
.get_short_hash(&self.entries
, i
);
1173 // if existing element probed less than us, swap
1174 let their_dist
= probe_distance(self.mask
, entry_hash
.into_hash(), probe
);
1175 if their_dist
< dist
{
1176 // robin hood: steal the spot if it's better for us
1177 return Entry
::Vacant(VacantEntry
{
1183 } else if entry_hash
== hash
&& self.entries
[i
].key
== key
{
1184 return Entry
::Occupied(OccupiedEntry
{
1192 // empty bucket, insert here
1193 return Entry
::Vacant(VacantEntry
{
1204 // First phase: Look for the preferred location for key.
1206 // We will know if `key` is already in the map, before we need to insert it.
1207 // When we insert they key, it might be that we need to continue displacing
1208 // entries (robin hood hashing), in which case Inserted::RobinHood is returned
1209 fn insert_phase_1
<Sz
>(&mut self, hash
: HashValue
, key
: K
, value
: V
) -> Inserted
<V
>
1213 let mut probe
= desired_pos(self.mask
, hash
);
1216 debug_assert
!(self.len() < self.raw_capacity());
1217 probe_loop
!(probe
< self.indices
.len(), {
1218 let pos
= &mut self.indices
[probe
];
1219 if let Some((i
, hash_proxy
)) = pos
.resolve
::<Sz
>() {
1220 let entry_hash
= hash_proxy
.get_short_hash(&self.entries
, i
);
1221 // if existing element probed less than us, swap
1222 let their_dist
= probe_distance(self.mask
, entry_hash
.into_hash(), probe
);
1223 if their_dist
< dist
{
1224 // robin hood: steal the spot if it's better for us
1225 let index
= self.entries
.len();
1226 insert_kind
= Inserted
::RobinHood
{
1228 old_pos
: Pos
::with_hash
::<Sz
>(index
, hash
),
1231 } else if entry_hash
== hash
&& self.entries
[i
].key
== key
{
1232 return Inserted
::Swapped
{
1233 prev_value
: replace(&mut self.entries
[i
].value
, value
),
1237 // empty bucket, insert here
1238 let index
= self.entries
.len();
1239 *pos
= Pos
::with_hash
::<Sz
>(index
, hash
);
1240 insert_kind
= Inserted
::Done
;
1245 self.entries
.push(Bucket { hash: hash, key: key, value: value }
);
1250 /// phase 2 is post-insert where we forward-shift `Pos` in the indices.
1251 fn insert_phase_2
<Sz
>(&mut self, mut probe
: usize, mut old_pos
: Pos
)
1254 probe_loop
!(probe
< self.indices
.len(), {
1255 let pos
= &mut self.indices
[probe
];
1260 old_pos
= replace(pos
, old_pos
);
1266 /// Return probe (indices) and position (entries)
1267 fn find_using
<F
>(&self, hash
: HashValue
, key_eq
: F
) -> Option
<(usize, usize)>
1268 where F
: Fn(&Bucket
<K
, V
>) -> bool
,
1270 dispatch_32_vs_64
!(self.find_using_impl
::<_
>(hash
, key_eq
))
1273 fn find_using_impl
<Sz
, F
>(&self, hash
: HashValue
, key_eq
: F
) -> Option
<(usize, usize)>
1274 where F
: Fn(&Bucket
<K
, V
>) -> bool
,
1277 debug_assert
!(self.len() > 0);
1278 let mut probe
= desired_pos(self.mask
, hash
);
1280 probe_loop
!(probe
< self.indices
.len(), {
1281 if let Some((i
, hash_proxy
)) = self.indices
[probe
].resolve
::<Sz
>() {
1282 let entry_hash
= hash_proxy
.get_short_hash(&self.entries
, i
);
1283 if dist
> probe_distance(self.mask
, entry_hash
.into_hash(), probe
) {
1284 // give up when probe distance is too long
1286 } else if entry_hash
== hash
&& key_eq(&self.entries
[i
]) {
1287 return Some((probe
, i
));
1296 /// Find `entry` which is already placed inside self.entries;
1297 /// return its probe and entry index.
1298 fn find_existing_entry(&self, entry
: &Bucket
<K
, V
>) -> (usize, usize)
1300 debug_assert
!(self.len() > 0);
1302 let hash
= entry
.hash
;
1303 let actual_pos
= ptrdistance(&self.entries
[0], entry
);
1304 let probe
= dispatch_32_vs_64
!(self =>
1305 find_existing_entry_at(&self.indices
, hash
, self.mask
, actual_pos
));
1309 fn remove_found(&mut self, probe
: usize, found
: usize) -> (K
, V
) {
1310 dispatch_32_vs_64
!(self.remove_found_impl(probe
, found
))
1313 fn remove_found_impl
<Sz
>(&mut self, probe
: usize, found
: usize) -> (K
, V
)
1316 // index `probe` and entry `found` is to be removed
1317 // use swap_remove, but then we need to update the index that points
1318 // to the other entry that has to move
1319 self.indices
[probe
] = Pos
::none();
1320 let entry
= self.entries
.swap_remove(found
);
1322 // correct index that points to the entry that had to swap places
1323 if let Some(entry
) = self.entries
.get(found
) {
1324 // was not last element
1325 // examine new element in `found` and find it in indices
1326 let mut probe
= desired_pos(self.mask
, entry
.hash
);
1327 probe_loop
!(probe
< self.indices
.len(), {
1328 if let Some((i
, _
)) = self.indices
[probe
].resolve
::<Sz
>() {
1329 if i
>= self.entries
.len() {
1331 self.indices
[probe
] = Pos
::with_hash
::<Sz
>(found
, entry
.hash
);
1338 self.backward_shift_after_removal
::<Sz
>(probe
);
1340 (entry
.key
, entry
.value
)
1343 fn backward_shift_after_removal
<Sz
>(&mut self, probe_at_remove
: usize)
1346 // backward shift deletion in self.indices
1347 // after probe, shift all non-ideally placed indices backward
1348 let mut last_probe
= probe_at_remove
;
1349 let mut probe
= probe_at_remove
+ 1;
1350 probe_loop
!(probe
< self.indices
.len(), {
1351 if let Some((i
, hash_proxy
)) = self.indices
[probe
].resolve
::<Sz
>() {
1352 let entry_hash
= hash_proxy
.get_short_hash(&self.entries
, i
);
1353 if probe_distance(self.mask
, entry_hash
.into_hash(), probe
) > 0 {
1354 self.indices
[last_probe
] = self.indices
[probe
];
1355 self.indices
[probe
] = Pos
::none();
1366 fn retain_in_order_impl
<Sz
, F
>(&mut self, mut keep
: F
)
1367 where F
: FnMut(&mut K
, &mut V
) -> bool
,
1370 // Like Vec::retain in self.entries; for each removed key-value pair,
1371 // we clear its corresponding spot in self.indices, and run the
1372 // usual backward shift in self.indices.
1373 let len
= self.entries
.len();
1374 let mut n_deleted
= 0;
1379 let ent
= &mut self.entries
[i
];
1381 will_keep
= keep(&mut ent
.key
, &mut ent
.value
);
1383 let probe
= find_existing_entry_at
::<Sz
>(&self.indices
, hash
, self.mask
, i
);
1386 self.indices
[probe
] = Pos
::none();
1387 self.backward_shift_after_removal
::<Sz
>(probe
);
1388 } else if n_deleted
> 0 {
1389 self.indices
[probe
].set_pos
::<Sz
>(i
- n_deleted
);
1390 self.entries
.swap(i
- n_deleted
, i
);
1393 self.entries
.truncate(len
- n_deleted
);
1396 fn sort_by
<F
>(&mut self, mut compare
: F
)
1397 where F
: FnMut(&K
, &V
, &K
, &V
) -> Ordering
,
1399 // Temporarily use the hash field in a bucket to store the old index.
1400 // Save the old hash values in `side_index`. Then we can sort
1401 // `self.entries` in place.
1402 let mut side_index
= Vec
::from_iter(enumerate(&mut self.entries
).map(|(i
, elt
)| {
1403 replace(&mut elt
.hash
, HashValue(i
)).get()
1406 self.entries
.sort_by(move |ei
, ej
| compare(&ei
.key
, &ei
.value
, &ej
.key
, &ej
.value
));
1408 // Write back the hash values from side_index and fill `side_index` with
1409 // a mapping from the old to the new index instead.
1410 for (i
, ent
) in enumerate(&mut self.entries
) {
1411 let old_index
= ent
.hash
.get();
1412 ent
.hash
= HashValue(replace(&mut side_index
[old_index
], i
));
1415 // Apply new index to self.indices
1416 dispatch_32_vs_64
!(self => apply_new_index(&mut self.indices
, &side_index
));
1418 fn apply_new_index
<Sz
>(indices
: &mut [Pos
], new_index
: &[usize])
1421 for pos
in indices
{
1422 if let Some((i
, _
)) = pos
.resolve
::<Sz
>() {
1423 pos
.set_pos
::<Sz
>(new_index
[i
]);
1430 /// Find, in the indices, an entry that already exists at a known position
1431 /// inside self.entries in the IndexMap.
1433 /// This is effectively reverse lookup, from the entries into the hash buckets.
1435 /// Return the probe index (into self.indices)
1437 /// + indices: The self.indices of the map,
1438 /// + hash: The full hash value from the bucket
1439 /// + mask: self.mask.
1440 /// + entry_index: The index of the entry in self.entries
1441 fn find_existing_entry_at
<Sz
>(indices
: &[Pos
], hash
: HashValue
,
1442 mask
: usize, entry_index
: usize) -> usize
1445 let mut probe
= desired_pos(mask
, hash
);
1446 probe_loop
!(probe
< indices
.len(), {
1447 // the entry *must* be present; if we hit a Pos::none this was not true
1448 // and there is a debug assertion in resolve_existing_index for that.
1449 let i
= indices
[probe
].resolve_existing_index
::<Sz
>();
1450 if i
== entry_index { return probe; }
1454 use std
::slice
::Iter
as SliceIter
;
1455 use std
::slice
::IterMut
as SliceIterMut
;
1456 use std
::vec
::IntoIter
as VecIntoIter
;
1458 pub struct Keys
<'a
, K
: 'a
, V
: 'a
> {
1459 pub(crate) iter
: SliceIter
<'a
, Bucket
<K
, V
>>,
1462 impl<'a
, K
, V
> Iterator
for Keys
<'a
, K
, V
> {
1465 iterator_methods
!(Bucket
::key_ref
);
1468 impl<'a
, K
, V
> DoubleEndedIterator
for Keys
<'a
, K
, V
> {
1469 fn next_back(&mut self) -> Option
<&'a K
> {
1470 self.iter
.next_back().map(Bucket
::key_ref
)
1474 impl<'a
, K
, V
> ExactSizeIterator
for Keys
<'a
, K
, V
> {
1475 fn len(&self) -> usize {
1480 pub struct Values
<'a
, K
: 'a
, V
: 'a
> {
1481 iter
: SliceIter
<'a
, Bucket
<K
, V
>>,
1484 impl<'a
, K
, V
> Iterator
for Values
<'a
, K
, V
> {
1487 iterator_methods
!(Bucket
::value_ref
);
1490 impl<'a
, K
, V
> DoubleEndedIterator
for Values
<'a
, K
, V
> {
1491 fn next_back(&mut self) -> Option
<Self::Item
> {
1492 self.iter
.next_back().map(Bucket
::value_ref
)
1496 impl<'a
, K
, V
> ExactSizeIterator
for Values
<'a
, K
, V
> {
1497 fn len(&self) -> usize {
1502 pub struct ValuesMut
<'a
, K
: 'a
, V
: 'a
> {
1503 iter
: SliceIterMut
<'a
, Bucket
<K
, V
>>,
1506 impl<'a
, K
, V
> Iterator
for ValuesMut
<'a
, K
, V
> {
1507 type Item
= &'a
mut V
;
1509 iterator_methods
!(Bucket
::value_mut
);
1512 impl<'a
, K
, V
> DoubleEndedIterator
for ValuesMut
<'a
, K
, V
> {
1513 fn next_back(&mut self) -> Option
<Self::Item
> {
1514 self.iter
.next_back().map(Bucket
::value_mut
)
1518 impl<'a
, K
, V
> ExactSizeIterator
for ValuesMut
<'a
, K
, V
> {
1519 fn len(&self) -> usize {
1524 pub struct Iter
<'a
, K
: 'a
, V
: 'a
> {
1525 iter
: SliceIter
<'a
, Bucket
<K
, V
>>,
1528 impl<'a
, K
, V
> Iterator
for Iter
<'a
, K
, V
> {
1529 type Item
= (&'a K
, &'a V
);
1531 iterator_methods
!(Bucket
::refs
);
1534 impl<'a
, K
, V
> DoubleEndedIterator
for Iter
<'a
, K
, V
> {
1535 fn next_back(&mut self) -> Option
<Self::Item
> {
1536 self.iter
.next_back().map(Bucket
::refs
)
1540 impl<'a
, K
, V
> ExactSizeIterator
for Iter
<'a
, K
, V
> {
1541 fn len(&self) -> usize {
1546 pub struct IterMut
<'a
, K
: 'a
, V
: 'a
> {
1547 iter
: SliceIterMut
<'a
, Bucket
<K
, V
>>,
1550 impl<'a
, K
, V
> Iterator
for IterMut
<'a
, K
, V
> {
1551 type Item
= (&'a K
, &'a
mut V
);
1553 iterator_methods
!(Bucket
::ref_mut
);
1556 impl<'a
, K
, V
> DoubleEndedIterator
for IterMut
<'a
, K
, V
> {
1557 fn next_back(&mut self) -> Option
<Self::Item
> {
1558 self.iter
.next_back().map(Bucket
::ref_mut
)
1562 impl<'a
, K
, V
> ExactSizeIterator
for IterMut
<'a
, K
, V
> {
1563 fn len(&self) -> usize {
1568 pub struct IntoIter
<K
, V
> {
1569 pub(crate) iter
: VecIntoIter
<Bucket
<K
, V
>>,
1572 impl<K
, V
> Iterator
for IntoIter
<K
, V
> {
1575 iterator_methods
!(Bucket
::key_value
);
1578 impl<'a
, K
, V
> DoubleEndedIterator
for IntoIter
<K
, V
> {
1579 fn next_back(&mut self) -> Option
<Self::Item
> {
1580 self.iter
.next_back().map(Bucket
::key_value
)
1584 impl<K
, V
> ExactSizeIterator
for IntoIter
<K
, V
> {
1585 fn len(&self) -> usize {
1590 pub struct Drain
<'a
, K
, V
> where K
: 'a
, V
: 'a
{
1591 pub(crate) iter
: ::std
::vec
::Drain
<'a
, Bucket
<K
, V
>>
1594 impl<'a
, K
, V
> Iterator
for Drain
<'a
, K
, V
> {
1597 iterator_methods
!(Bucket
::key_value
);
1600 impl<'a
, K
, V
> DoubleEndedIterator
for Drain
<'a
, K
, V
> {
1601 double_ended_iterator_methods
!(Bucket
::key_value
);
1605 impl<'a
, K
, V
, S
> IntoIterator
for &'a IndexMap
<K
, V
, S
>
1609 type Item
= (&'a K
, &'a V
);
1610 type IntoIter
= Iter
<'a
, K
, V
>;
1611 fn into_iter(self) -> Self::IntoIter
{
1616 impl<'a
, K
, V
, S
> IntoIterator
for &'a
mut IndexMap
<K
, V
, S
>
1620 type Item
= (&'a K
, &'a
mut V
);
1621 type IntoIter
= IterMut
<'a
, K
, V
>;
1622 fn into_iter(self) -> Self::IntoIter
{
1627 impl<K
, V
, S
> IntoIterator
for IndexMap
<K
, V
, S
>
1632 type IntoIter
= IntoIter
<K
, V
>;
1633 fn into_iter(self) -> Self::IntoIter
{
1635 iter
: self.core
.entries
.into_iter(),
1640 use std
::ops
::{Index, IndexMut}
;
1642 impl<'a
, K
, V
, Q
: ?Sized
, S
> Index
<&'a Q
> for IndexMap
<K
, V
, S
>
1643 where Q
: Hash
+ Equivalent
<K
>,
1649 /// ***Panics*** if `key` is not present in the map.
1650 fn index(&self, key
: &'a Q
) -> &V
{
1651 if let Some(v
) = self.get(key
) {
1654 panic
!("IndexMap: key not found")
1659 /// Mutable indexing allows changing / updating values of key-value
1660 /// pairs that are already present.
1662 /// You can **not** insert new pairs with index syntax, use `.insert()`.
1663 impl<'a
, K
, V
, Q
: ?Sized
, S
> IndexMut
<&'a Q
> for IndexMap
<K
, V
, S
>
1664 where Q
: Hash
+ Equivalent
<K
>,
1668 /// ***Panics*** if `key` is not present in the map.
1669 fn index_mut(&mut self, key
: &'a Q
) -> &mut V
{
1670 if let Some(v
) = self.get_mut(key
) {
1673 panic
!("IndexMap: key not found")
1678 impl<K
, V
, S
> FromIterator
<(K
, V
)> for IndexMap
<K
, V
, S
>
1680 S
: BuildHasher
+ Default
,
1682 /// Create an `IndexMap` from the sequence of key-value pairs in the
1685 /// `from_iter` uses the same logic as `extend`. See
1686 /// [`extend`](#method.extend) for more details.
1687 fn from_iter
<I
: IntoIterator
<Item
=(K
, V
)>>(iterable
: I
) -> Self {
1688 let iter
= iterable
.into_iter();
1689 let (low
, _
) = iter
.size_hint();
1690 let mut map
= Self::with_capacity_and_hasher(low
, <_
>::default());
1696 impl<K
, V
, S
> Extend
<(K
, V
)> for IndexMap
<K
, V
, S
>
1700 /// Extend the map with all key-value pairs in the iterable.
1702 /// This is equivalent to calling [`insert`](#method.insert) for each of
1703 /// them in order, which means that for keys that already existed
1704 /// in the map, their value is updated but it keeps the existing order.
1706 /// New keys are inserted inserted in the order in the sequence. If
1707 /// equivalents of a key occur more than once, the last corresponding value
1709 fn extend
<I
: IntoIterator
<Item
=(K
, V
)>>(&mut self, iterable
: I
) {
1710 for (k
, v
) in iterable { self.insert(k, v); }
1714 impl<'a
, K
, V
, S
> Extend
<(&'a K
, &'a V
)> for IndexMap
<K
, V
, S
>
1715 where K
: Hash
+ Eq
+ Copy
,
1719 /// Extend the map with all key-value pairs in the iterable.
1721 /// See the first extend method for more details.
1722 fn extend
<I
: IntoIterator
<Item
=(&'a K
, &'a V
)>>(&mut self, iterable
: I
) {
1723 self.extend(iterable
.into_iter().map(|(&key
, &value
)| (key
, value
)));
1727 impl<K
, V
, S
> Default
for IndexMap
<K
, V
, S
>
1728 where S
: BuildHasher
+ Default
,
1730 /// Return an empty `IndexMap`
1731 fn default() -> Self {
1732 Self::with_capacity_and_hasher(0, S
::default())
1736 impl<K
, V1
, S1
, V2
, S2
> PartialEq
<IndexMap
<K
, V2
, S2
>> for IndexMap
<K
, V1
, S1
>
1742 fn eq(&self, other
: &IndexMap
<K
, V2
, S2
>) -> bool
{
1743 if self.len() != other
.len() {
1747 self.iter().all(|(key
, value
)| other
.get(key
).map_or(false, |v
| *value
== *v
))
1751 impl<K
, V
, S
> Eq
for IndexMap
<K
, V
, S
>
1761 use util
::enumerate
;
1765 let mut map
= IndexMap
::new();
1766 assert_eq
!(map
.is_empty(), true);
1769 assert_eq
!(map
.len(), 1);
1770 assert
!(map
.get(&1).is_some());
1771 assert_eq
!(map
.is_empty(), false);
1776 let map
= IndexMap
::<String
, String
>::new();
1777 println
!("{:?}", map
);
1778 assert_eq
!(map
.capacity(), 0);
1779 assert_eq
!(map
.len(), 0);
1780 assert_eq
!(map
.is_empty(), true);
1785 let insert
= [0, 4, 2, 12, 8, 7, 11, 5];
1786 let not_present
= [1, 3, 6, 9, 10];
1787 let mut map
= IndexMap
::with_capacity(insert
.len());
1789 for (i
, &elt
) in enumerate(&insert
) {
1790 assert_eq
!(map
.len(), i
);
1791 map
.insert(elt
, elt
);
1792 assert_eq
!(map
.len(), i
+ 1);
1793 assert_eq
!(map
.get(&elt
), Some(&elt
));
1794 assert_eq
!(map
[&elt
], elt
);
1796 println
!("{:?}", map
);
1798 for &elt
in ¬_present
{
1799 assert
!(map
.get(&elt
).is_none());
1805 let insert
= vec
![9, 2, 7, 1, 4, 6, 13];
1806 let present
= vec
![1, 6, 2];
1807 let mut map
= IndexMap
::with_capacity(insert
.len());
1809 for (i
, &elt
) in enumerate(&insert
) {
1810 assert_eq
!(map
.len(), i
);
1811 let (index
, existing
) = map
.insert_full(elt
, elt
);
1812 assert_eq
!(existing
, None
);
1813 assert_eq
!(Some(index
), map
.get_full(&elt
).map(|x
| x
.0));
1814 assert_eq
!(map
.len(), i
+ 1);
1817 let len
= map
.len();
1818 for &elt
in &present
{
1819 let (index
, existing
) = map
.insert_full(elt
, elt
);
1820 assert_eq
!(existing
, Some(elt
));
1821 assert_eq
!(Some(index
), map
.get_full(&elt
).map(|x
| x
.0));
1822 assert_eq
!(map
.len(), len
);
1828 let mut map
= IndexMap
::with_capacity(16);
1830 let mut keys
= vec
![];
1832 keys
.extend(128..267);
1835 let old_map
= map
.clone();
1837 for key
in old_map
.keys() {
1838 if !map
.get(key
).is_some() {
1839 println
!("old_map: {:?}", old_map
);
1840 println
!("map: {:?}", map
);
1841 panic
!("did not find {} in map", key
);
1847 assert
!(map
.get(&i
).is_some(), "did not find {}", i
);
1853 let insert
= [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23];
1854 let mut map
= IndexMap
::new();
1856 for &elt
in &insert
{
1857 map
.insert(elt
, ());
1860 assert_eq
!(map
.keys().count(), map
.len());
1861 assert_eq
!(map
.keys().count(), insert
.len());
1862 for (a
, b
) in insert
.iter().zip(map
.keys()) {
1865 for (i
, k
) in (0..insert
.len()).zip(map
.keys()) {
1866 assert_eq
!(map
.get_index(i
).unwrap().0, k
);
1872 let insert
= [0, 4, 2, 12, 8, 7, 11];
1873 let not_present
= [1, 3, 6, 9, 10];
1874 let mut map
= IndexMap
::with_capacity(insert
.len());
1877 for (i
, &elt
) in enumerate(&insert
) {
1878 assert_eq
!(map
.len(), i
);
1879 map
.insert(elt
, elt
);
1880 assert_eq
!(map
.len(), i
+ 1);
1881 assert_eq
!(map
.get(&elt
), Some(&elt
));
1882 assert_eq
!(map
[&elt
], elt
);
1885 println
!("{:?}", map
);
1886 for &elt
in &insert
{
1887 map
.insert(elt
* 10, elt
);
1889 for &elt
in &insert
{
1890 map
.insert(elt
* 100, elt
);
1892 for (i
, &elt
) in insert
.iter().cycle().enumerate().take(100) {
1893 map
.insert(elt
* 100 + i
as i32, elt
);
1895 println
!("{:?}", map
);
1896 for &elt
in ¬_present
{
1897 assert
!(map
.get(&elt
).is_none());
1903 let insert
= [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23];
1904 let mut map
= IndexMap
::new();
1906 for &elt
in &insert
{
1907 map
.insert(elt
, elt
);
1910 assert_eq
!(map
.keys().count(), map
.len());
1911 assert_eq
!(map
.keys().count(), insert
.len());
1912 for (a
, b
) in insert
.iter().zip(map
.keys()) {
1916 let remove_fail
= [99, 77];
1917 let remove
= [4, 12, 8, 7];
1919 for &key
in &remove_fail
{
1920 assert
!(map
.swap_remove_full(&key
).is_none());
1922 println
!("{:?}", map
);
1923 for &key
in &remove
{
1924 //println!("{:?}", map);
1925 let index
= map
.get_full(&key
).unwrap().0;
1926 assert_eq
!(map
.swap_remove_full(&key
), Some((index
, key
, key
)));
1928 println
!("{:?}", map
);
1930 for key
in &insert
{
1931 assert_eq
!(map
.get(key
).is_some(), !remove
.contains(key
));
1933 assert_eq
!(map
.len(), insert
.len() - remove
.len());
1934 assert_eq
!(map
.keys().count(), insert
.len() - remove
.len());
1938 fn remove_to_empty() {
1939 let mut map
= indexmap
! { 0 => 0, 4 => 4, 5 => 5 }
;
1940 map
.swap_remove(&5).unwrap();
1941 map
.swap_remove(&4).unwrap();
1942 map
.swap_remove(&0).unwrap();
1943 assert
!(map
.is_empty());
1947 fn swap_remove_index() {
1948 let insert
= [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23];
1949 let mut map
= IndexMap
::new();
1951 for &elt
in &insert
{
1952 map
.insert(elt
, elt
* 2);
1955 let mut vector
= insert
.to_vec();
1956 let remove_sequence
= &[3, 3, 10, 4, 5, 4, 3, 0, 1];
1958 // check that the same swap remove sequence on vec and map
1959 // have the same result.
1960 for &rm
in remove_sequence
{
1961 let out_vec
= vector
.swap_remove(rm
);
1962 let (out_map
, _
) = map
.swap_remove_index(rm
).unwrap();
1963 assert_eq
!(out_vec
, out_map
);
1965 assert_eq
!(vector
.len(), map
.len());
1966 for (a
, b
) in vector
.iter().zip(map
.keys()) {
1972 fn partial_eq_and_eq() {
1973 let mut map_a
= IndexMap
::new();
1974 map_a
.insert(1, "1");
1975 map_a
.insert(2, "2");
1976 let mut map_b
= map_a
.clone();
1977 assert_eq
!(map_a
, map_b
);
1979 assert_ne
!(map_a
, map_b
);
1981 let map_c
: IndexMap
<_
, String
> = map_b
.into_iter().map(|(k
, v
)| (k
, v
.to_owned())).collect();
1982 assert_ne
!(map_a
, map_c
);
1983 assert_ne
!(map_c
, map_a
);
1988 let mut map
= IndexMap
::new();
1989 map
.extend(vec
![(&1, &2), (&3, &4)]);
1990 map
.extend(vec
![(5, 6)]);
1991 assert_eq
!(map
.into_iter().collect
::<Vec
<_
>>(), vec
![(1, 2), (3, 4), (5, 6)]);
1996 let mut map
= IndexMap
::new();
2001 let e
= map
.entry(3);
2002 assert_eq
!(e
.index(), 2);
2003 let e
= e
.or_insert("3");
2004 assert_eq
!(e
, &"3");
2007 let e
= map
.entry(2);
2008 assert_eq
!(e
.index(), 1);
2009 assert_eq
!(e
.key(), &2);
2011 Entry
::Occupied(ref e
) => assert_eq
!(e
.get(), &"2"),
2012 Entry
::Vacant(_
) => panic
!()
2014 assert_eq
!(e
.or_insert("4"), &"2");
2018 fn entry_and_modify() {
2019 let mut map
= IndexMap
::new();
2022 map
.entry(1).and_modify(|x
| *x
= "2");
2023 assert_eq
!(Some(&"2"), map
.get(&1));
2025 map
.entry(2).and_modify(|x
| *x
= "doesn't exist");
2026 assert_eq
!(None
, map
.get(&2));
2030 fn entry_or_default() {
2031 let mut map
= IndexMap
::new();
2033 #[derive(Debug, PartialEq)]
2039 impl Default
for TestEnum
{
2040 fn default() -> Self {
2041 TestEnum
::DefaultValue
2045 map
.insert(1, TestEnum
::NonDefaultValue
);
2046 assert_eq
!(&mut TestEnum
::NonDefaultValue
, map
.entry(1).or_default());
2048 assert_eq
!(&mut TestEnum
::DefaultValue
, map
.entry(2).or_default());