1 //! `IndexMap` is a hash table where the iteration order of the key-value
2 //! pairs is independent of the hash values of the keys.
3
4 #[cfg(not(has_std))]
5 use alloc::boxed::Box;
6 #[cfg(not(has_std))]
7 use std::vec::Vec;
8
9 pub use mutable_keys::MutableKeys;
10
11 #[cfg(feature = "rayon")]
12 pub use rayon::map as rayon;
13
14 use std::hash::BuildHasher;
15 use std::hash::Hash;
16 use std::hash::Hasher;
17 use std::iter::FromIterator;
18 use std::ops::RangeFull;
19
20 #[cfg(has_std)]
21 use std::collections::hash_map::RandomState;
22
23 use std::cmp::{max, Ordering};
24 use std::fmt;
25 use std::marker::PhantomData;
26 use std::mem::replace;
27
28 use equivalent::Equivalent;
29 use util::{enumerate, ptrdistance, third};
30 use {Bucket, Entries, HashValue};
31
hash_elem_using<B: BuildHasher, K: ?Sized + Hash>(build: &B, k: &K) -> HashValue32 fn hash_elem_using<B: BuildHasher, K: ?Sized + Hash>(build: &B, k: &K) -> HashValue {
33 let mut h = build.build_hasher();
34 k.hash(&mut h);
35 HashValue(h.finish() as usize)
36 }
37
38 /// A possibly truncated hash value.
39 ///
40 #[derive(Debug)]
41 struct ShortHash<Sz>(usize, PhantomData<Sz>);
42
43 impl<Sz> ShortHash<Sz> {
44 /// Pretend this is a full HashValue, which
45 /// is completely ok w.r.t determining bucket index
46 ///
47 /// - Sz = u32: 32-bit hash is enough to select bucket index
48 /// - Sz = u64: hash is not truncated
into_hash(self) -> HashValue49 fn into_hash(self) -> HashValue {
50 HashValue(self.0)
51 }
52 }
53
54 impl<Sz> Copy for ShortHash<Sz> {}
55 impl<Sz> Clone for ShortHash<Sz> {
56 #[inline]
clone(&self) -> Self57 fn clone(&self) -> Self {
58 *self
59 }
60 }
61
62 impl<Sz> PartialEq for ShortHash<Sz> {
63 #[inline]
eq(&self, rhs: &Self) -> bool64 fn eq(&self, rhs: &Self) -> bool {
65 self.0 == rhs.0
66 }
67 }
68
69 // Compare ShortHash == HashValue by truncating appropriately
70 // if applicable before the comparison
71 impl<Sz> PartialEq<HashValue> for ShortHash<Sz>
72 where
73 Sz: Size,
74 {
75 #[inline]
eq(&self, rhs: &HashValue) -> bool76 fn eq(&self, rhs: &HashValue) -> bool {
77 if Sz::is_64_bit() {
78 self.0 == rhs.0
79 } else {
80 lo32(self.0 as u64) == lo32(rhs.0 as u64)
81 }
82 }
83 }
84 impl<Sz> From<ShortHash<Sz>> for HashValue {
from(x: ShortHash<Sz>) -> Self85 fn from(x: ShortHash<Sz>) -> Self {
86 HashValue(x.0)
87 }
88 }
89
90 /// `Pos` is stored in the `indices` array and it points to the index of a
91 /// `Bucket` in self.core.entries.
92 ///
93 /// Pos can be interpreted either as a 64-bit index, or as a 32-bit index and
94 /// a 32-bit hash.
95 ///
96 /// Storing the truncated hash next to the index saves loading the hash from the
97 /// entry, increasing the cache efficiency.
98 ///
99 /// Note that the lower 32 bits of the hash is enough to compute desired
100 /// position and probe distance in a hash map with less than 2**32 buckets.
101 ///
102 /// The IndexMap will simply query its **current raw capacity** to see what its
103 /// current size class is, and dispatch to the 32-bit or 64-bit lookup code as
104 /// appropriate. Only the growth code needs some extra logic to handle the
105 /// transition from one class to another
106 #[derive(Copy)]
107 struct Pos {
108 index: u64,
109 }
110
111 impl Clone for Pos {
112 #[inline(always)]
clone(&self) -> Self113 fn clone(&self) -> Self {
114 *self
115 }
116 }
117
118 impl fmt::Debug for Pos {
fmt(&self, f: &mut fmt::Formatter) -> fmt::Result119 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
120 match self.pos() {
121 Some(i) => write!(f, "Pos({} / {:x})", i, self.index),
122 None => write!(f, "Pos(None)"),
123 }
124 }
125 }
126
127 impl Pos {
128 #[inline]
none() -> Self129 fn none() -> Self {
130 Pos { index: !0 }
131 }
132
133 #[inline]
is_none(&self) -> bool134 fn is_none(&self) -> bool {
135 self.index == !0
136 }
137
138 /// Return the index part of the Pos value inside `Some(_)` if the position
139 /// is not none, otherwise return `None`.
140 #[inline]
pos(&self) -> Option<usize>141 fn pos(&self) -> Option<usize> {
142 if self.index == !0 {
143 None
144 } else {
145 Some(lo32(self.index as u64))
146 }
147 }
148
149 /// Set the index part of the Pos value to `i`
150 #[inline]
set_pos<Sz>(&mut self, i: usize) where Sz: Size,151 fn set_pos<Sz>(&mut self, i: usize)
152 where
153 Sz: Size,
154 {
155 debug_assert!(!self.is_none());
156 if Sz::is_64_bit() {
157 self.index = i as u64;
158 } else {
159 self.index = i as u64 | ((self.index >> 32) << 32)
160 }
161 }
162
163 #[inline]
with_hash<Sz>(i: usize, hash: HashValue) -> Self where Sz: Size,164 fn with_hash<Sz>(i: usize, hash: HashValue) -> Self
165 where
166 Sz: Size,
167 {
168 if Sz::is_64_bit() {
169 Pos { index: i as u64 }
170 } else {
171 Pos {
172 index: i as u64 | ((hash.0 as u64) << 32),
173 }
174 }
175 }
176
177 /// “Resolve” the Pos into a combination of its index value and
178 /// a proxy value to the hash (whether it contains the hash or not
179 /// depends on the size class of the hash map).
180 #[inline]
resolve<Sz>(&self) -> Option<(usize, ShortHashProxy<Sz>)> where Sz: Size,181 fn resolve<Sz>(&self) -> Option<(usize, ShortHashProxy<Sz>)>
182 where
183 Sz: Size,
184 {
185 if Sz::is_64_bit() {
186 if !self.is_none() {
187 Some((self.index as usize, ShortHashProxy::new(0)))
188 } else {
189 None
190 }
191 } else {
192 if !self.is_none() {
193 let (i, hash) = split_lo_hi(self.index);
194 Some((i as usize, ShortHashProxy::new(hash as usize)))
195 } else {
196 None
197 }
198 }
199 }
200
201 /// Like resolve, but the Pos **must** be non-none. Return its index.
202 #[inline]
resolve_existing_index<Sz>(&self) -> usize where Sz: Size,203 fn resolve_existing_index<Sz>(&self) -> usize
204 where
205 Sz: Size,
206 {
207 debug_assert!(
208 !self.is_none(),
209 "datastructure inconsistent: none where valid Pos expected"
210 );
211 if Sz::is_64_bit() {
212 self.index as usize
213 } else {
214 let (i, _) = split_lo_hi(self.index);
215 i as usize
216 }
217 }
218 }
219
220 #[inline]
lo32(x: u64) -> usize221 fn lo32(x: u64) -> usize {
222 (x & 0xFFFF_FFFF) as usize
223 }
224
225 // split into low, hi parts
226 #[inline]
split_lo_hi(x: u64) -> (u32, u32)227 fn split_lo_hi(x: u64) -> (u32, u32) {
228 (x as u32, (x >> 32) as u32)
229 }
230
231 // Possibly contains the truncated hash value for an entry, depending on
232 // the size class.
233 struct ShortHashProxy<Sz>(usize, PhantomData<Sz>);
234
235 impl<Sz> ShortHashProxy<Sz>
236 where
237 Sz: Size,
238 {
new(x: usize) -> Self239 fn new(x: usize) -> Self {
240 ShortHashProxy(x, PhantomData)
241 }
242
243 /// Get the hash from either `self` or from a lookup into `entries`,
244 /// depending on `Sz`.
get_short_hash<K, V>(&self, entries: &[Bucket<K, V>], index: usize) -> ShortHash<Sz>245 fn get_short_hash<K, V>(&self, entries: &[Bucket<K, V>], index: usize) -> ShortHash<Sz> {
246 if Sz::is_64_bit() {
247 ShortHash(entries[index].hash.0, PhantomData)
248 } else {
249 ShortHash(self.0, PhantomData)
250 }
251 }
252 }
253
254 /// A hash table where the iteration order of the key-value pairs is independent
255 /// of the hash values of the keys.
256 ///
257 /// The interface is closely compatible with the standard `HashMap`, but also
258 /// has additional features.
259 ///
260 /// # Order
261 ///
262 /// The key-value pairs have a consistent order that is determined by
263 /// the sequence of insertion and removal calls on the map. The order does
264 /// not depend on the keys or the hash function at all.
265 ///
266 /// All iterators traverse the map in *the order*.
267 ///
268 /// The insertion order is preserved, with **notable exceptions** like the
269 /// `.remove()` or `.swap_remove()` methods. Methods such as `.sort_by()` of
270 /// course result in a new order, depending on the sorting order.
271 ///
272 /// # Indices
273 ///
274 /// The key-value pairs are indexed in a compact range without holes in the
275 /// range `0..self.len()`. For example, the method `.get_full` looks up the
276 /// index for a key, and the method `.get_index` looks up the key-value pair by
277 /// index.
278 ///
279 /// # Examples
280 ///
281 /// ```
282 /// use indexmap::IndexMap;
283 ///
284 /// // count the frequency of each letter in a sentence.
285 /// let mut letters = IndexMap::new();
286 /// for ch in "a short treatise on fungi".chars() {
287 /// *letters.entry(ch).or_insert(0) += 1;
288 /// }
289 ///
290 /// assert_eq!(letters[&'s'], 2);
291 /// assert_eq!(letters[&'t'], 3);
292 /// assert_eq!(letters[&'u'], 1);
293 /// assert_eq!(letters.get(&'y'), None);
294 /// ```
295 #[derive(Clone)]
296 #[cfg(has_std)]
297 pub struct IndexMap<K, V, S = RandomState> {
298 core: OrderMapCore<K, V>,
299 hash_builder: S,
300 }
301 #[derive(Clone)]
302 #[cfg(not(has_std))]
303 pub struct IndexMap<K, V, S> {
304 core: OrderMapCore<K, V>,
305 hash_builder: S,
306 }
307
308 // core of the map that does not depend on S
309 #[derive(Clone)]
310 struct OrderMapCore<K, V> {
311 pub(crate) mask: usize,
312 /// indices are the buckets. indices.len() == raw capacity
313 pub(crate) indices: Box<[Pos]>,
314 /// entries is a dense vec of entries in their order. entries.len() == len
315 pub(crate) entries: Vec<Bucket<K, V>>,
316 }
317
318 #[inline(always)]
desired_pos(mask: usize, hash: HashValue) -> usize319 fn desired_pos(mask: usize, hash: HashValue) -> usize {
320 hash.0 & mask
321 }
322
323 impl<K, V, S> Entries for IndexMap<K, V, S> {
324 type Entry = Bucket<K, V>;
325
into_entries(self) -> Vec<Self::Entry>326 fn into_entries(self) -> Vec<Self::Entry> {
327 self.core.entries
328 }
329
as_entries(&self) -> &[Self::Entry]330 fn as_entries(&self) -> &[Self::Entry] {
331 &self.core.entries
332 }
333
as_entries_mut(&mut self) -> &mut [Self::Entry]334 fn as_entries_mut(&mut self) -> &mut [Self::Entry] {
335 &mut self.core.entries
336 }
337
with_entries<F>(&mut self, f: F) where F: FnOnce(&mut [Self::Entry]),338 fn with_entries<F>(&mut self, f: F)
339 where
340 F: FnOnce(&mut [Self::Entry]),
341 {
342 let side_index = self.core.save_hash_index();
343 f(&mut self.core.entries);
344 self.core.restore_hash_index(side_index);
345 }
346 }
347
348 /// The number of steps that `current` is forward of the desired position for hash
349 #[inline(always)]
probe_distance(mask: usize, hash: HashValue, current: usize) -> usize350 fn probe_distance(mask: usize, hash: HashValue, current: usize) -> usize {
351 current.wrapping_sub(desired_pos(mask, hash)) & mask
352 }
353
354 enum Inserted<V> {
355 Done,
356 Swapped { prev_value: V },
357 RobinHood { probe: usize, old_pos: Pos },
358 }
359
360 impl<K, V, S> fmt::Debug for IndexMap<K, V, S>
361 where
362 K: fmt::Debug + Hash + Eq,
363 V: fmt::Debug,
364 S: BuildHasher,
365 {
fmt(&self, f: &mut fmt::Formatter) -> fmt::Result366 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
367 f.debug_map().entries(self.iter()).finish()?;
368 if cfg!(not(feature = "test_debug")) {
369 return Ok(());
370 }
371 writeln!(f)?;
372 for (i, index) in enumerate(&*self.core.indices) {
373 write!(f, "{}: {:?}", i, index)?;
374 if let Some(pos) = index.pos() {
375 let hash = self.core.entries[pos].hash;
376 let key = &self.core.entries[pos].key;
377 let desire = desired_pos(self.core.mask, hash);
378 write!(
379 f,
380 ", desired={}, probe_distance={}, key={:?}",
381 desire,
382 probe_distance(self.core.mask, hash, i),
383 key
384 )?;
385 }
386 writeln!(f)?;
387 }
388 writeln!(
389 f,
390 "cap={}, raw_cap={}, entries.cap={}",
391 self.capacity(),
392 self.raw_capacity(),
393 self.core.entries.capacity()
394 )?;
395 Ok(())
396 }
397 }
398
399 #[inline]
usable_capacity(cap: usize) -> usize400 fn usable_capacity(cap: usize) -> usize {
401 cap - cap / 4
402 }
403
404 #[inline]
to_raw_capacity(n: usize) -> usize405 fn to_raw_capacity(n: usize) -> usize {
406 n + n / 3
407 }
408
409 // this could not be captured in an efficient iterator
410 macro_rules! probe_loop {
411 ($probe_var: ident < $len: expr, $body: expr) => {
412 loop {
413 if $probe_var < $len {
414 $body
415 $probe_var += 1;
416 } else {
417 $probe_var = 0;
418 }
419 }
420 }
421 }
422
423 #[cfg(has_std)]
424 impl<K, V> IndexMap<K, V> {
425 /// Create a new map. (Does not allocate.)
new() -> Self426 pub fn new() -> Self {
427 Self::with_capacity(0)
428 }
429
430 /// Create a new map with capacity for `n` key-value pairs. (Does not
431 /// allocate if `n` is zero.)
432 ///
433 /// Computes in **O(n)** time.
with_capacity(n: usize) -> Self434 pub fn with_capacity(n: usize) -> Self {
435 Self::with_capacity_and_hasher(n, <_>::default())
436 }
437 }
438
439 impl<K, V, S> IndexMap<K, V, S> {
440 /// Create a new map with capacity for `n` key-value pairs. (Does not
441 /// allocate if `n` is zero.)
442 ///
443 /// Computes in **O(n)** time.
with_capacity_and_hasher(n: usize, hash_builder: S) -> Self where S: BuildHasher,444 pub fn with_capacity_and_hasher(n: usize, hash_builder: S) -> Self
445 where
446 S: BuildHasher,
447 {
448 if n == 0 {
449 IndexMap {
450 core: OrderMapCore {
451 mask: 0,
452 indices: Box::new([]),
453 entries: Vec::new(),
454 },
455 hash_builder,
456 }
457 } else {
458 let raw = to_raw_capacity(n);
459 let raw_cap = max(raw.next_power_of_two(), 8);
460 IndexMap {
461 core: OrderMapCore {
462 mask: raw_cap.wrapping_sub(1),
463 indices: vec![Pos::none(); raw_cap].into_boxed_slice(),
464 entries: Vec::with_capacity(usable_capacity(raw_cap)),
465 },
466 hash_builder,
467 }
468 }
469 }
470
471 /// Return the number of key-value pairs in the map.
472 ///
473 /// Computes in **O(1)** time.
len(&self) -> usize474 pub fn len(&self) -> usize {
475 self.core.len()
476 }
477
478 /// Returns true if the map contains no elements.
479 ///
480 /// Computes in **O(1)** time.
is_empty(&self) -> bool481 pub fn is_empty(&self) -> bool {
482 self.len() == 0
483 }
484
485 /// Create a new map with `hash_builder`
with_hasher(hash_builder: S) -> Self where S: BuildHasher,486 pub fn with_hasher(hash_builder: S) -> Self
487 where
488 S: BuildHasher,
489 {
490 Self::with_capacity_and_hasher(0, hash_builder)
491 }
492
493 /// Return a reference to the map's `BuildHasher`.
hasher(&self) -> &S where S: BuildHasher,494 pub fn hasher(&self) -> &S
495 where
496 S: BuildHasher,
497 {
498 &self.hash_builder
499 }
500
501 /// Computes in **O(1)** time.
capacity(&self) -> usize502 pub fn capacity(&self) -> usize {
503 self.core.capacity()
504 }
505
506 #[inline]
size_class_is_64bit(&self) -> bool507 fn size_class_is_64bit(&self) -> bool {
508 self.core.size_class_is_64bit()
509 }
510
511 #[inline(always)]
raw_capacity(&self) -> usize512 fn raw_capacity(&self) -> usize {
513 self.core.raw_capacity()
514 }
515 }
516
517 impl<K, V> OrderMapCore<K, V> {
518 // Return whether we need 32 or 64 bits to specify a bucket or entry index
519 #[cfg(not(feature = "test_low_transition_point"))]
size_class_is_64bit(&self) -> bool520 fn size_class_is_64bit(&self) -> bool {
521 usize::max_value() > u32::max_value() as usize
522 && self.raw_capacity() >= u32::max_value() as usize
523 }
524
525 // for testing
526 #[cfg(feature = "test_low_transition_point")]
size_class_is_64bit(&self) -> bool527 fn size_class_is_64bit(&self) -> bool {
528 self.raw_capacity() >= 64
529 }
530
531 #[inline(always)]
raw_capacity(&self) -> usize532 fn raw_capacity(&self) -> usize {
533 self.indices.len()
534 }
535 }
536
537 /// Trait for the "size class". Either u32 or u64 depending on the index
538 /// size needed to address an entry's indes in self.core.entries.
539 trait Size {
is_64_bit() -> bool540 fn is_64_bit() -> bool;
is_same_size<T: Size>() -> bool541 fn is_same_size<T: Size>() -> bool {
542 Self::is_64_bit() == T::is_64_bit()
543 }
544 }
545
546 impl Size for u32 {
547 #[inline]
is_64_bit() -> bool548 fn is_64_bit() -> bool {
549 false
550 }
551 }
552
553 impl Size for u64 {
554 #[inline]
is_64_bit() -> bool555 fn is_64_bit() -> bool {
556 true
557 }
558 }
559
560 /// Call self.method(args) with `::<u32>` or `::<u64>` depending on `self`
561 /// size class.
562 ///
563 /// The u32 or u64 is *prepended* to the type parameter list!
564 macro_rules! dispatch_32_vs_64 {
565 // self.methodname with other explicit type params,
566 // size is prepended
567 ($self_:ident . $method:ident::<$($t:ty),*>($($arg:expr),*)) => {
568 if $self_.size_class_is_64bit() {
569 $self_.$method::<u64, $($t),*>($($arg),*)
570 } else {
571 $self_.$method::<u32, $($t),*>($($arg),*)
572 }
573 };
574 // self.methodname with only one type param, the size.
575 ($self_:ident . $method:ident ($($arg:expr),*)) => {
576 if $self_.size_class_is_64bit() {
577 $self_.$method::<u64>($($arg),*)
578 } else {
579 $self_.$method::<u32>($($arg),*)
580 }
581 };
582 // functionname with size_class_is_64bit as the first argument, only one
583 // type param, the size.
584 ($self_:ident => $function:ident ($($arg:expr),*)) => {
585 if $self_.size_class_is_64bit() {
586 $function::<u64>($($arg),*)
587 } else {
588 $function::<u32>($($arg),*)
589 }
590 };
591 }
592
593 /// Entry for an existing key-value pair or a vacant location to
594 /// insert one.
595 pub enum Entry<'a, K: 'a, V: 'a> {
596 /// Existing slot with equivalent key.
597 Occupied(OccupiedEntry<'a, K, V>),
598 /// Vacant slot (no equivalent key in the map).
599 Vacant(VacantEntry<'a, K, V>),
600 }
601
602 impl<'a, K, V> Entry<'a, K, V> {
603 /// Computes in **O(1)** time (amortized average).
or_insert(self, default: V) -> &'a mut V604 pub fn or_insert(self, default: V) -> &'a mut V {
605 match self {
606 Entry::Occupied(entry) => entry.into_mut(),
607 Entry::Vacant(entry) => entry.insert(default),
608 }
609 }
610
611 /// Computes in **O(1)** time (amortized average).
or_insert_with<F>(self, call: F) -> &'a mut V where F: FnOnce() -> V,612 pub fn or_insert_with<F>(self, call: F) -> &'a mut V
613 where
614 F: FnOnce() -> V,
615 {
616 match self {
617 Entry::Occupied(entry) => entry.into_mut(),
618 Entry::Vacant(entry) => entry.insert(call()),
619 }
620 }
621
key(&self) -> &K622 pub fn key(&self) -> &K {
623 match *self {
624 Entry::Occupied(ref entry) => entry.key(),
625 Entry::Vacant(ref entry) => entry.key(),
626 }
627 }
628
629 /// Return the index where the key-value pair exists or will be inserted.
index(&self) -> usize630 pub fn index(&self) -> usize {
631 match *self {
632 Entry::Occupied(ref entry) => entry.index(),
633 Entry::Vacant(ref entry) => entry.index(),
634 }
635 }
636
637 /// Modifies the entry if it is occupied.
and_modify<F>(self, f: F) -> Self where F: FnOnce(&mut V),638 pub fn and_modify<F>(self, f: F) -> Self
639 where
640 F: FnOnce(&mut V),
641 {
642 match self {
643 Entry::Occupied(mut o) => {
644 f(o.get_mut());
645 Entry::Occupied(o)
646 }
647 x => x,
648 }
649 }
650
651 /// Inserts a default-constructed value in the entry if it is vacant and returns a mutable
652 /// reference to it. Otherwise a mutable reference to an already existent value is returned.
653 ///
654 /// Computes in **O(1)** time (amortized average).
or_default(self) -> &'a mut V where V: Default,655 pub fn or_default(self) -> &'a mut V
656 where
657 V: Default,
658 {
659 match self {
660 Entry::Occupied(entry) => entry.into_mut(),
661 Entry::Vacant(entry) => entry.insert(V::default()),
662 }
663 }
664 }
665
666 impl<'a, K: 'a + fmt::Debug, V: 'a + fmt::Debug> fmt::Debug for Entry<'a, K, V> {
fmt(&self, f: &mut fmt::Formatter) -> fmt::Result667 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
668 match *self {
669 Entry::Vacant(ref v) => f.debug_tuple(stringify!(Entry)).field(v).finish(),
670 Entry::Occupied(ref o) => f.debug_tuple(stringify!(Entry)).field(o).finish(),
671 }
672 }
673 }
674
675 /// A view into an occupied entry in a `IndexMap`.
676 /// It is part of the [`Entry`] enum.
677 ///
678 /// [`Entry`]: enum.Entry.html
679 pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
680 map: &'a mut OrderMapCore<K, V>,
681 key: K,
682 probe: usize,
683 index: usize,
684 }
685
686 impl<'a, K, V> OccupiedEntry<'a, K, V> {
key(&self) -> &K687 pub fn key(&self) -> &K {
688 &self.key
689 }
get(&self) -> &V690 pub fn get(&self) -> &V {
691 &self.map.entries[self.index].value
692 }
get_mut(&mut self) -> &mut V693 pub fn get_mut(&mut self) -> &mut V {
694 &mut self.map.entries[self.index].value
695 }
696
697 /// Put the new key in the occupied entry's key slot
replace_key(self) -> K698 pub(crate) fn replace_key(self) -> K {
699 let old_key = &mut self.map.entries[self.index].key;
700 replace(old_key, self.key)
701 }
702
703 /// Return the index of the key-value pair
index(&self) -> usize704 pub fn index(&self) -> usize {
705 self.index
706 }
into_mut(self) -> &'a mut V707 pub fn into_mut(self) -> &'a mut V {
708 &mut self.map.entries[self.index].value
709 }
710
711 /// Sets the value of the entry to `value`, and returns the entry's old value.
insert(&mut self, value: V) -> V712 pub fn insert(&mut self, value: V) -> V {
713 replace(self.get_mut(), value)
714 }
715
716 /// Remove the key, value pair stored in the map for this entry, and return the value.
717 ///
718 /// **NOTE:** This is equivalent to `.swap_remove()`.
remove(self) -> V719 pub fn remove(self) -> V {
720 self.swap_remove()
721 }
722
723 /// Remove the key, value pair stored in the map for this entry, and return the value.
724 ///
725 /// Like `Vec::swap_remove`, the pair is removed by swapping it with the
726 /// last element of the map and popping it off. **This perturbs
727 /// the postion of what used to be the last element!**
728 ///
729 /// Computes in **O(1)** time (average).
swap_remove(self) -> V730 pub fn swap_remove(self) -> V {
731 self.swap_remove_entry().1
732 }
733
734 /// Remove the key, value pair stored in the map for this entry, and return the value.
735 ///
736 /// Like `Vec::remove`, the pair is removed by shifting all of the
737 /// elements that follow it, preserving their relative order.
738 /// **This perturbs the index of all of those elements!**
739 ///
740 /// Computes in **O(n)** time (average).
shift_remove(self) -> V741 pub fn shift_remove(self) -> V {
742 self.shift_remove_entry().1
743 }
744
745 /// Remove and return the key, value pair stored in the map for this entry
746 ///
747 /// **NOTE:** This is equivalent to `.swap_remove_entry()`.
remove_entry(self) -> (K, V)748 pub fn remove_entry(self) -> (K, V) {
749 self.swap_remove_entry()
750 }
751
752 /// Remove and return the key, value pair stored in the map for this entry
753 ///
754 /// Like `Vec::swap_remove`, the pair is removed by swapping it with the
755 /// last element of the map and popping it off. **This perturbs
756 /// the postion of what used to be the last element!**
757 ///
758 /// Computes in **O(1)** time (average).
swap_remove_entry(self) -> (K, V)759 pub fn swap_remove_entry(self) -> (K, V) {
760 self.map.swap_remove_found(self.probe, self.index)
761 }
762
763 /// Remove and return the key, value pair stored in the map for this entry
764 ///
765 /// Like `Vec::remove`, the pair is removed by shifting all of the
766 /// elements that follow it, preserving their relative order.
767 /// **This perturbs the index of all of those elements!**
768 ///
769 /// Computes in **O(n)** time (average).
shift_remove_entry(self) -> (K, V)770 pub fn shift_remove_entry(self) -> (K, V) {
771 self.map.shift_remove_found(self.probe, self.index)
772 }
773 }
774
775 impl<'a, K: 'a + fmt::Debug, V: 'a + fmt::Debug> fmt::Debug for OccupiedEntry<'a, K, V> {
fmt(&self, f: &mut fmt::Formatter) -> fmt::Result776 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
777 f.debug_struct(stringify!(OccupiedEntry))
778 .field("key", self.key())
779 .field("value", self.get())
780 .finish()
781 }
782 }
783
784 /// A view into a vacant entry in a `IndexMap`.
785 /// It is part of the [`Entry`] enum.
786 ///
787 /// [`Entry`]: enum.Entry.html
788 pub struct VacantEntry<'a, K: 'a, V: 'a> {
789 map: &'a mut OrderMapCore<K, V>,
790 key: K,
791 hash: HashValue,
792 probe: usize,
793 }
794
795 impl<'a, K, V> VacantEntry<'a, K, V> {
key(&self) -> &K796 pub fn key(&self) -> &K {
797 &self.key
798 }
into_key(self) -> K799 pub fn into_key(self) -> K {
800 self.key
801 }
802 /// Return the index where the key-value pair will be inserted.
index(&self) -> usize803 pub fn index(&self) -> usize {
804 self.map.len()
805 }
insert(self, value: V) -> &'a mut V806 pub fn insert(self, value: V) -> &'a mut V {
807 if self.map.size_class_is_64bit() {
808 self.insert_impl::<u64>(value)
809 } else {
810 self.insert_impl::<u32>(value)
811 }
812 }
813
insert_impl<Sz>(self, value: V) -> &'a mut V where Sz: Size,814 fn insert_impl<Sz>(self, value: V) -> &'a mut V
815 where
816 Sz: Size,
817 {
818 let index = self.map.entries.len();
819 self.map.entries.push(Bucket {
820 hash: self.hash,
821 key: self.key,
822 value,
823 });
824 let old_pos = Pos::with_hash::<Sz>(index, self.hash);
825 self.map.insert_phase_2::<Sz>(self.probe, old_pos);
826 &mut { self.map }.entries[index].value
827 }
828 }
829
830 impl<'a, K: 'a + fmt::Debug, V: 'a> fmt::Debug for VacantEntry<'a, K, V> {
fmt(&self, f: &mut fmt::Formatter) -> fmt::Result831 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
832 f.debug_tuple(stringify!(VacantEntry))
833 .field(self.key())
834 .finish()
835 }
836 }
837
838 impl<K, V, S> IndexMap<K, V, S>
839 where
840 K: Hash + Eq,
841 S: BuildHasher,
842 {
843 // FIXME: reduce duplication (compare with insert)
entry_phase_1<Sz>(&mut self, key: K) -> Entry<K, V> where Sz: Size,844 fn entry_phase_1<Sz>(&mut self, key: K) -> Entry<K, V>
845 where
846 Sz: Size,
847 {
848 let hash = hash_elem_using(&self.hash_builder, &key);
849 self.core.entry_phase_1::<Sz>(hash, key)
850 }
851
852 /// Remove all key-value pairs in the map, while preserving its capacity.
853 ///
854 /// Computes in **O(n)** time.
clear(&mut self)855 pub fn clear(&mut self) {
856 self.core.clear();
857 }
858
859 /// Reserve capacity for `additional` more key-value pairs.
860 ///
861 /// FIXME Not implemented fully yet.
reserve(&mut self, additional: usize)862 pub fn reserve(&mut self, additional: usize) {
863 if additional > 0 {
864 self.reserve_one();
865 }
866 }
867
868 // First phase: Look for the preferred location for key.
869 //
870 // We will know if `key` is already in the map, before we need to insert it.
871 // When we insert they key, it might be that we need to continue displacing
872 // entries (robin hood hashing), in which case Inserted::RobinHood is returned
insert_phase_1<Sz>(&mut self, key: K, value: V) -> Inserted<V> where Sz: Size,873 fn insert_phase_1<Sz>(&mut self, key: K, value: V) -> Inserted<V>
874 where
875 Sz: Size,
876 {
877 let hash = hash_elem_using(&self.hash_builder, &key);
878 self.core.insert_phase_1::<Sz>(hash, key, value)
879 }
880
reserve_one(&mut self)881 fn reserve_one(&mut self) {
882 if self.len() == self.capacity() {
883 dispatch_32_vs_64!(self.double_capacity());
884 }
885 }
double_capacity<Sz>(&mut self) where Sz: Size,886 fn double_capacity<Sz>(&mut self)
887 where
888 Sz: Size,
889 {
890 self.core.double_capacity::<Sz>();
891 }
892
893 /// Insert a key-value pair in the map.
894 ///
895 /// If an equivalent key already exists in the map: the key remains and
896 /// retains in its place in the order, its corresponding value is updated
897 /// with `value` and the older value is returned inside `Some(_)`.
898 ///
899 /// If no equivalent key existed in the map: the new key-value pair is
900 /// inserted, last in order, and `None` is returned.
901 ///
902 /// Computes in **O(1)** time (amortized average).
903 ///
904 /// See also [`entry`](#method.entry) if you you want to insert *or* modify
905 /// or if you need to get the index of the corresponding key-value pair.
insert(&mut self, key: K, value: V) -> Option<V>906 pub fn insert(&mut self, key: K, value: V) -> Option<V> {
907 self.reserve_one();
908 if self.size_class_is_64bit() {
909 match self.insert_phase_1::<u64>(key, value) {
910 Inserted::Swapped { prev_value } => Some(prev_value),
911 Inserted::Done => None,
912 Inserted::RobinHood { probe, old_pos } => {
913 self.core.insert_phase_2::<u64>(probe, old_pos);
914 None
915 }
916 }
917 } else {
918 match self.insert_phase_1::<u32>(key, value) {
919 Inserted::Swapped { prev_value } => Some(prev_value),
920 Inserted::Done => None,
921 Inserted::RobinHood { probe, old_pos } => {
922 self.core.insert_phase_2::<u32>(probe, old_pos);
923 None
924 }
925 }
926 }
927 }
928
929 /// Insert a key-value pair in the map, and get their index.
930 ///
931 /// If an equivalent key already exists in the map: the key remains and
932 /// retains in its place in the order, its corresponding value is updated
933 /// with `value` and the older value is returned inside `(index, Some(_))`.
934 ///
935 /// If no equivalent key existed in the map: the new key-value pair is
936 /// inserted, last in order, and `(index, None)` is returned.
937 ///
938 /// Computes in **O(1)** time (amortized average).
939 ///
940 /// See also [`entry`](#method.entry) if you you want to insert *or* modify
941 /// or if you need to get the index of the corresponding key-value pair.
insert_full(&mut self, key: K, value: V) -> (usize, Option<V>)942 pub fn insert_full(&mut self, key: K, value: V) -> (usize, Option<V>) {
943 let entry = self.entry(key);
944 let index = entry.index();
945
946 match entry {
947 Entry::Occupied(mut entry) => (index, Some(entry.insert(value))),
948 Entry::Vacant(entry) => {
949 entry.insert(value);
950 (index, None)
951 }
952 }
953 }
954
955 /// Get the given key’s corresponding entry in the map for insertion and/or
956 /// in-place manipulation.
957 ///
958 /// Computes in **O(1)** time (amortized average).
entry(&mut self, key: K) -> Entry<K, V>959 pub fn entry(&mut self, key: K) -> Entry<K, V> {
960 self.reserve_one();
961 dispatch_32_vs_64!(self.entry_phase_1(key))
962 }
963
964 /// Return an iterator over the key-value pairs of the map, in their order
iter(&self) -> Iter<K, V>965 pub fn iter(&self) -> Iter<K, V> {
966 Iter {
967 iter: self.core.entries.iter(),
968 }
969 }
970
971 /// Return an iterator over the key-value pairs of the map, in their order
iter_mut(&mut self) -> IterMut<K, V>972 pub fn iter_mut(&mut self) -> IterMut<K, V> {
973 IterMut {
974 iter: self.core.entries.iter_mut(),
975 }
976 }
977
978 /// Return an iterator over the keys of the map, in their order
keys(&self) -> Keys<K, V>979 pub fn keys(&self) -> Keys<K, V> {
980 Keys {
981 iter: self.core.entries.iter(),
982 }
983 }
984
985 /// Return an iterator over the values of the map, in their order
values(&self) -> Values<K, V>986 pub fn values(&self) -> Values<K, V> {
987 Values {
988 iter: self.core.entries.iter(),
989 }
990 }
991
992 /// Return an iterator over mutable references to the the values of the map,
993 /// in their order
values_mut(&mut self) -> ValuesMut<K, V>994 pub fn values_mut(&mut self) -> ValuesMut<K, V> {
995 ValuesMut {
996 iter: self.core.entries.iter_mut(),
997 }
998 }
999
1000 /// Return `true` if an equivalent to `key` exists in the map.
1001 ///
1002 /// Computes in **O(1)** time (average).
contains_key<Q: ?Sized>(&self, key: &Q) -> bool where Q: Hash + Equivalent<K>,1003 pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
1004 where
1005 Q: Hash + Equivalent<K>,
1006 {
1007 self.find(key).is_some()
1008 }
1009
1010 /// Return a reference to the value stored for `key`, if it is present,
1011 /// else `None`.
1012 ///
1013 /// Computes in **O(1)** time (average).
get<Q: ?Sized>(&self, key: &Q) -> Option<&V> where Q: Hash + Equivalent<K>,1014 pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
1015 where
1016 Q: Hash + Equivalent<K>,
1017 {
1018 self.get_full(key).map(third)
1019 }
1020
1021 /// Return item index, key and value
get_full<Q: ?Sized>(&self, key: &Q) -> Option<(usize, &K, &V)> where Q: Hash + Equivalent<K>,1022 pub fn get_full<Q: ?Sized>(&self, key: &Q) -> Option<(usize, &K, &V)>
1023 where
1024 Q: Hash + Equivalent<K>,
1025 {
1026 if let Some((_, found)) = self.find(key) {
1027 let entry = &self.core.entries[found];
1028 Some((found, &entry.key, &entry.value))
1029 } else {
1030 None
1031 }
1032 }
1033
get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> where Q: Hash + Equivalent<K>,1034 pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
1035 where
1036 Q: Hash + Equivalent<K>,
1037 {
1038 self.get_full_mut(key).map(third)
1039 }
1040
get_full_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, &K, &mut V)> where Q: Hash + Equivalent<K>,1041 pub fn get_full_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, &K, &mut V)>
1042 where
1043 Q: Hash + Equivalent<K>,
1044 {
1045 self.get_full_mut2_impl(key).map(|(i, k, v)| (i, &*k, v))
1046 }
1047
get_full_mut2_impl<Q: ?Sized>( &mut self, key: &Q, ) -> Option<(usize, &mut K, &mut V)> where Q: Hash + Equivalent<K>,1048 pub(crate) fn get_full_mut2_impl<Q: ?Sized>(
1049 &mut self,
1050 key: &Q,
1051 ) -> Option<(usize, &mut K, &mut V)>
1052 where
1053 Q: Hash + Equivalent<K>,
1054 {
1055 if let Some((_, found)) = self.find(key) {
1056 let entry = &mut self.core.entries[found];
1057 Some((found, &mut entry.key, &mut entry.value))
1058 } else {
1059 None
1060 }
1061 }
1062
1063 /// Return probe (indices) and position (entries)
find<Q: ?Sized>(&self, key: &Q) -> Option<(usize, usize)> where Q: Hash + Equivalent<K>,1064 pub(crate) fn find<Q: ?Sized>(&self, key: &Q) -> Option<(usize, usize)>
1065 where
1066 Q: Hash + Equivalent<K>,
1067 {
1068 if self.is_empty() {
1069 return None;
1070 }
1071 let h = hash_elem_using(&self.hash_builder, key);
1072 self.core
1073 .find_using(h, move |entry| Q::equivalent(key, &entry.key))
1074 }
1075
1076 /// Remove the key-value pair equivalent to `key` and return
1077 /// its value.
1078 ///
1079 /// **NOTE:** This is equivalent to `.swap_remove(key)`, if you need to
1080 /// preserve the order of the keys in the map, use `.shift_remove(key)`
1081 /// instead.
1082 ///
1083 /// Computes in **O(1)** time (average).
remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where Q: Hash + Equivalent<K>,1084 pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
1085 where
1086 Q: Hash + Equivalent<K>,
1087 {
1088 self.swap_remove(key)
1089 }
1090
1091 /// Remove the key-value pair equivalent to `key` and return
1092 /// its value.
1093 ///
1094 /// Like `Vec::swap_remove`, the pair is removed by swapping it with the
1095 /// last element of the map and popping it off. **This perturbs
1096 /// the postion of what used to be the last element!**
1097 ///
1098 /// Return `None` if `key` is not in map.
1099 ///
1100 /// Computes in **O(1)** time (average).
swap_remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where Q: Hash + Equivalent<K>,1101 pub fn swap_remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
1102 where
1103 Q: Hash + Equivalent<K>,
1104 {
1105 self.swap_remove_full(key).map(third)
1106 }
1107
1108 /// Remove the key-value pair equivalent to `key` and return it and
1109 /// the index it had.
1110 ///
1111 /// Like `Vec::swap_remove`, the pair is removed by swapping it with the
1112 /// last element of the map and popping it off. **This perturbs
1113 /// the postion of what used to be the last element!**
1114 ///
1115 /// Return `None` if `key` is not in map.
1116 ///
1117 /// Computes in **O(1)** time (average).
swap_remove_full<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, K, V)> where Q: Hash + Equivalent<K>,1118 pub fn swap_remove_full<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, K, V)>
1119 where
1120 Q: Hash + Equivalent<K>,
1121 {
1122 let (probe, found) = match self.find(key) {
1123 None => return None,
1124 Some(t) => t,
1125 };
1126 let (k, v) = self.core.swap_remove_found(probe, found);
1127 Some((found, k, v))
1128 }
1129
1130 /// Remove the key-value pair equivalent to `key` and return
1131 /// its value.
1132 ///
1133 /// Like `Vec::remove`, the pair is removed by shifting all of the
1134 /// elements that follow it, preserving their relative order.
1135 /// **This perturbs the index of all of those elements!**
1136 ///
1137 /// Return `None` if `key` is not in map.
1138 ///
1139 /// Computes in **O(n)** time (average).
shift_remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where Q: Hash + Equivalent<K>,1140 pub fn shift_remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
1141 where
1142 Q: Hash + Equivalent<K>,
1143 {
1144 self.shift_remove_full(key).map(third)
1145 }
1146
1147 /// Remove the key-value pair equivalent to `key` and return it and
1148 /// the index it had.
1149 ///
1150 /// Like `Vec::remove`, the pair is removed by shifting all of the
1151 /// elements that follow it, preserving their relative order.
1152 /// **This perturbs the index of all of those elements!**
1153 ///
1154 /// Return `None` if `key` is not in map.
1155 ///
1156 /// Computes in **O(n)** time (average).
shift_remove_full<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, K, V)> where Q: Hash + Equivalent<K>,1157 pub fn shift_remove_full<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, K, V)>
1158 where
1159 Q: Hash + Equivalent<K>,
1160 {
1161 let (probe, found) = match self.find(key) {
1162 None => return None,
1163 Some(t) => t,
1164 };
1165 let (k, v) = self.core.shift_remove_found(probe, found);
1166 Some((found, k, v))
1167 }
1168
1169 /// Remove the last key-value pair
1170 ///
1171 /// Computes in **O(1)** time (average).
pop(&mut self) -> Option<(K, V)>1172 pub fn pop(&mut self) -> Option<(K, V)> {
1173 self.core.pop_impl()
1174 }
1175
1176 /// Scan through each key-value pair in the map and keep those where the
1177 /// closure `keep` returns `true`.
1178 ///
1179 /// The elements are visited in order, and remaining elements keep their
1180 /// order.
1181 ///
1182 /// Computes in **O(n)** time (average).
retain<F>(&mut self, mut keep: F) where F: FnMut(&K, &mut V) -> bool,1183 pub fn retain<F>(&mut self, mut keep: F)
1184 where
1185 F: FnMut(&K, &mut V) -> bool,
1186 {
1187 self.retain_mut(move |k, v| keep(k, v));
1188 }
1189
retain_mut<F>(&mut self, keep: F) where F: FnMut(&mut K, &mut V) -> bool,1190 pub(crate) fn retain_mut<F>(&mut self, keep: F)
1191 where
1192 F: FnMut(&mut K, &mut V) -> bool,
1193 {
1194 dispatch_32_vs_64!(self.retain_mut_sz::<_>(keep));
1195 }
1196
retain_mut_sz<Sz, F>(&mut self, keep: F) where F: FnMut(&mut K, &mut V) -> bool, Sz: Size,1197 fn retain_mut_sz<Sz, F>(&mut self, keep: F)
1198 where
1199 F: FnMut(&mut K, &mut V) -> bool,
1200 Sz: Size,
1201 {
1202 self.core.retain_in_order_impl::<Sz, F>(keep);
1203 }
1204
1205 /// Sort the map’s key-value pairs by the default ordering of the keys.
1206 ///
1207 /// See `sort_by` for details.
sort_keys(&mut self) where K: Ord,1208 pub fn sort_keys(&mut self)
1209 where
1210 K: Ord,
1211 {
1212 self.core.sort_by(key_cmp)
1213 }
1214
1215 /// Sort the map’s key-value pairs in place using the comparison
1216 /// function `compare`.
1217 ///
1218 /// The comparison function receives two key and value pairs to compare (you
1219 /// can sort by keys or values or their combination as needed).
1220 ///
1221 /// Computes in **O(n log n + c)** time and **O(n)** space where *n* is
1222 /// the length of the map and *c* the capacity. The sort is stable.
sort_by<F>(&mut self, compare: F) where F: FnMut(&K, &V, &K, &V) -> Ordering,1223 pub fn sort_by<F>(&mut self, compare: F)
1224 where
1225 F: FnMut(&K, &V, &K, &V) -> Ordering,
1226 {
1227 self.core.sort_by(compare)
1228 }
1229
1230 /// Sort the key-value pairs of the map and return a by value iterator of
1231 /// the key-value pairs with the result.
1232 ///
1233 /// The sort is stable.
sorted_by<F>(mut self, mut cmp: F) -> IntoIter<K, V> where F: FnMut(&K, &V, &K, &V) -> Ordering,1234 pub fn sorted_by<F>(mut self, mut cmp: F) -> IntoIter<K, V>
1235 where
1236 F: FnMut(&K, &V, &K, &V) -> Ordering,
1237 {
1238 self.core
1239 .entries
1240 .sort_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value));
1241 self.into_iter()
1242 }
1243
1244 /// Clears the `IndexMap`, returning all key-value pairs as a drain iterator.
1245 /// Keeps the allocated memory for reuse.
drain(&mut self, range: RangeFull) -> Drain<K, V>1246 pub fn drain(&mut self, range: RangeFull) -> Drain<K, V> {
1247 self.core.clear_indices();
1248
1249 Drain {
1250 iter: self.core.entries.drain(range),
1251 }
1252 }
1253 }
1254
key_cmp<K, V>(k1: &K, _v1: &V, k2: &K, _v2: &V) -> Ordering where K: Ord,1255 fn key_cmp<K, V>(k1: &K, _v1: &V, k2: &K, _v2: &V) -> Ordering
1256 where
1257 K: Ord,
1258 {
1259 Ord::cmp(k1, k2)
1260 }
1261
1262 impl<K, V, S> IndexMap<K, V, S> {
1263 /// Get a key-value pair by index
1264 ///
1265 /// Valid indices are *0 <= index < self.len()*
1266 ///
1267 /// Computes in **O(1)** time.
get_index(&self, index: usize) -> Option<(&K, &V)>1268 pub fn get_index(&self, index: usize) -> Option<(&K, &V)> {
1269 self.core.entries.get(index).map(Bucket::refs)
1270 }
1271
1272 /// Get a key-value pair by index
1273 ///
1274 /// Valid indices are *0 <= index < self.len()*
1275 ///
1276 /// Computes in **O(1)** time.
get_index_mut(&mut self, index: usize) -> Option<(&mut K, &mut V)>1277 pub fn get_index_mut(&mut self, index: usize) -> Option<(&mut K, &mut V)> {
1278 self.core.entries.get_mut(index).map(Bucket::muts)
1279 }
1280
1281 /// Remove the key-value pair by index
1282 ///
1283 /// Valid indices are *0 <= index < self.len()*
1284 ///
1285 /// Like `Vec::swap_remove`, the pair is removed by swapping it with the
1286 /// last element of the map and popping it off. **This perturbs
1287 /// the postion of what used to be the last element!**
1288 ///
1289 /// Computes in **O(1)** time (average).
swap_remove_index(&mut self, index: usize) -> Option<(K, V)>1290 pub fn swap_remove_index(&mut self, index: usize) -> Option<(K, V)> {
1291 let (probe, found) = match self
1292 .core
1293 .entries
1294 .get(index)
1295 .map(|e| self.core.find_existing_entry(e))
1296 {
1297 None => return None,
1298 Some(t) => t,
1299 };
1300 Some(self.core.swap_remove_found(probe, found))
1301 }
1302
1303 /// Remove the key-value pair by index
1304 ///
1305 /// Valid indices are *0 <= index < self.len()*
1306 ///
1307 /// Like `Vec::remove`, the pair is removed by shifting all of the
1308 /// elements that follow it, preserving their relative order.
1309 /// **This perturbs the index of all of those elements!**
1310 ///
1311 /// Computes in **O(n)** time (average).
shift_remove_index(&mut self, index: usize) -> Option<(K, V)>1312 pub fn shift_remove_index(&mut self, index: usize) -> Option<(K, V)> {
1313 let (probe, found) = match self
1314 .core
1315 .entries
1316 .get(index)
1317 .map(|e| self.core.find_existing_entry(e))
1318 {
1319 None => return None,
1320 Some(t) => t,
1321 };
1322 Some(self.core.shift_remove_found(probe, found))
1323 }
1324 }
1325
1326 // Methods that don't use any properties (Hash / Eq) of K.
1327 //
1328 // It's cleaner to separate them out, then the compiler checks that we are not
1329 // using Hash + Eq at all in these methods.
1330 //
1331 // However, we should probably not let this show in the public API or docs.
1332 impl<K, V> OrderMapCore<K, V> {
len(&self) -> usize1333 fn len(&self) -> usize {
1334 self.entries.len()
1335 }
1336
capacity(&self) -> usize1337 fn capacity(&self) -> usize {
1338 usable_capacity(self.raw_capacity())
1339 }
1340
clear(&mut self)1341 fn clear(&mut self) {
1342 self.entries.clear();
1343 self.clear_indices();
1344 }
1345
1346 // clear self.indices to the same state as "no elements"
clear_indices(&mut self)1347 fn clear_indices(&mut self) {
1348 for pos in self.indices.iter_mut() {
1349 *pos = Pos::none();
1350 }
1351 }
1352
first_allocation(&mut self)1353 fn first_allocation(&mut self) {
1354 debug_assert_eq!(self.len(), 0);
1355 let raw_cap = 8usize;
1356 self.mask = raw_cap.wrapping_sub(1);
1357 self.indices = vec![Pos::none(); raw_cap].into_boxed_slice();
1358 self.entries = Vec::with_capacity(usable_capacity(raw_cap));
1359 }
1360
1361 #[inline(never)]
1362 // `Sz` is *current* Size class, before grow
double_capacity<Sz>(&mut self) where Sz: Size,1363 fn double_capacity<Sz>(&mut self)
1364 where
1365 Sz: Size,
1366 {
1367 debug_assert!(self.raw_capacity() == 0 || self.len() > 0);
1368 if self.raw_capacity() == 0 {
1369 return self.first_allocation();
1370 }
1371
1372 // find first ideally placed element -- start of cluster
1373 let mut first_ideal = 0;
1374 for (i, index) in enumerate(&*self.indices) {
1375 if let Some(pos) = index.pos() {
1376 if 0 == probe_distance(self.mask, self.entries[pos].hash, i) {
1377 first_ideal = i;
1378 break;
1379 }
1380 }
1381 }
1382
1383 // visit the entries in an order where we can simply reinsert them
1384 // into self.indices without any bucket stealing.
1385 let new_raw_cap = self.indices.len() * 2;
1386 let old_indices = replace(
1387 &mut self.indices,
1388 vec![Pos::none(); new_raw_cap].into_boxed_slice(),
1389 );
1390 self.mask = new_raw_cap.wrapping_sub(1);
1391
1392 // `Sz` is the old size class, and either u32 or u64 is the new
1393 for &pos in &old_indices[first_ideal..] {
1394 dispatch_32_vs_64!(self.reinsert_entry_in_order::<Sz>(pos));
1395 }
1396
1397 for &pos in &old_indices[..first_ideal] {
1398 dispatch_32_vs_64!(self.reinsert_entry_in_order::<Sz>(pos));
1399 }
1400 let more = self.capacity() - self.len();
1401 self.entries.reserve_exact(more);
1402 }
1403
1404 // write to self.indices
1405 // read from self.entries at `pos`
1406 //
1407 // reinserting rewrites all `Pos` entries anyway. This handles transitioning
1408 // from u32 to u64 size class if needed by using the two type parameters.
reinsert_entry_in_order<SzNew, SzOld>(&mut self, pos: Pos) where SzNew: Size, SzOld: Size,1409 fn reinsert_entry_in_order<SzNew, SzOld>(&mut self, pos: Pos)
1410 where
1411 SzNew: Size,
1412 SzOld: Size,
1413 {
1414 if let Some((i, hash_proxy)) = pos.resolve::<SzOld>() {
1415 // only if the size class is conserved can we use the short hash
1416 let entry_hash = if SzOld::is_same_size::<SzNew>() {
1417 hash_proxy.get_short_hash(&self.entries, i).into_hash()
1418 } else {
1419 self.entries[i].hash
1420 };
1421 // find first empty bucket and insert there
1422 let mut probe = desired_pos(self.mask, entry_hash);
1423 probe_loop!(probe < self.indices.len(), {
1424 if self.indices[probe].is_none() {
1425 // empty bucket, insert here
1426 self.indices[probe] = Pos::with_hash::<SzNew>(i, entry_hash);
1427 return;
1428 }
1429 });
1430 }
1431 }
1432
pop_impl(&mut self) -> Option<(K, V)>1433 fn pop_impl(&mut self) -> Option<(K, V)> {
1434 let (probe, found) = match self.entries.last().map(|e| self.find_existing_entry(e)) {
1435 None => return None,
1436 Some(t) => t,
1437 };
1438 debug_assert_eq!(found, self.entries.len() - 1);
1439 Some(self.swap_remove_found(probe, found))
1440 }
1441
1442 // FIXME: reduce duplication (compare with insert)
entry_phase_1<Sz>(&mut self, hash: HashValue, key: K) -> Entry<K, V> where Sz: Size, K: Eq,1443 fn entry_phase_1<Sz>(&mut self, hash: HashValue, key: K) -> Entry<K, V>
1444 where
1445 Sz: Size,
1446 K: Eq,
1447 {
1448 let mut probe = desired_pos(self.mask, hash);
1449 let mut dist = 0;
1450 debug_assert!(self.len() < self.raw_capacity());
1451 probe_loop!(probe < self.indices.len(), {
1452 if let Some((i, hash_proxy)) = self.indices[probe].resolve::<Sz>() {
1453 let entry_hash = hash_proxy.get_short_hash(&self.entries, i);
1454 // if existing element probed less than us, swap
1455 let their_dist = probe_distance(self.mask, entry_hash.into_hash(), probe);
1456 if their_dist < dist {
1457 // robin hood: steal the spot if it's better for us
1458 return Entry::Vacant(VacantEntry {
1459 map: self,
1460 hash: hash,
1461 key: key,
1462 probe: probe,
1463 });
1464 } else if entry_hash == hash && self.entries[i].key == key {
1465 return Entry::Occupied(OccupiedEntry {
1466 map: self,
1467 key: key,
1468 probe: probe,
1469 index: i,
1470 });
1471 }
1472 } else {
1473 // empty bucket, insert here
1474 return Entry::Vacant(VacantEntry {
1475 map: self,
1476 hash: hash,
1477 key: key,
1478 probe: probe,
1479 });
1480 }
1481 dist += 1;
1482 });
1483 }
1484
1485 // First phase: Look for the preferred location for key.
1486 //
1487 // We will know if `key` is already in the map, before we need to insert it.
1488 // When we insert they key, it might be that we need to continue displacing
1489 // entries (robin hood hashing), in which case Inserted::RobinHood is returned
insert_phase_1<Sz>(&mut self, hash: HashValue, key: K, value: V) -> Inserted<V> where Sz: Size, K: Eq,1490 fn insert_phase_1<Sz>(&mut self, hash: HashValue, key: K, value: V) -> Inserted<V>
1491 where
1492 Sz: Size,
1493 K: Eq,
1494 {
1495 let mut probe = desired_pos(self.mask, hash);
1496 let mut dist = 0;
1497 let insert_kind;
1498 debug_assert!(self.len() < self.raw_capacity());
1499 probe_loop!(probe < self.indices.len(), {
1500 let pos = &mut self.indices[probe];
1501 if let Some((i, hash_proxy)) = pos.resolve::<Sz>() {
1502 let entry_hash = hash_proxy.get_short_hash(&self.entries, i);
1503 // if existing element probed less than us, swap
1504 let their_dist = probe_distance(self.mask, entry_hash.into_hash(), probe);
1505 if their_dist < dist {
1506 // robin hood: steal the spot if it's better for us
1507 let index = self.entries.len();
1508 insert_kind = Inserted::RobinHood {
1509 probe: probe,
1510 old_pos: Pos::with_hash::<Sz>(index, hash),
1511 };
1512 break;
1513 } else if entry_hash == hash && self.entries[i].key == key {
1514 return Inserted::Swapped {
1515 prev_value: replace(&mut self.entries[i].value, value),
1516 };
1517 }
1518 } else {
1519 // empty bucket, insert here
1520 let index = self.entries.len();
1521 *pos = Pos::with_hash::<Sz>(index, hash);
1522 insert_kind = Inserted::Done;
1523 break;
1524 }
1525 dist += 1;
1526 });
1527 self.entries.push(Bucket { hash, key, value });
1528 insert_kind
1529 }
1530
1531 /// phase 2 is post-insert where we forward-shift `Pos` in the indices.
insert_phase_2<Sz>(&mut self, mut probe: usize, mut old_pos: Pos) where Sz: Size,1532 fn insert_phase_2<Sz>(&mut self, mut probe: usize, mut old_pos: Pos)
1533 where
1534 Sz: Size,
1535 {
1536 probe_loop!(probe < self.indices.len(), {
1537 let pos = &mut self.indices[probe];
1538 if pos.is_none() {
1539 *pos = old_pos;
1540 break;
1541 } else {
1542 old_pos = replace(pos, old_pos);
1543 }
1544 });
1545 }
1546
1547 /// Return probe (indices) and position (entries)
find_using<F>(&self, hash: HashValue, key_eq: F) -> Option<(usize, usize)> where F: Fn(&Bucket<K, V>) -> bool,1548 fn find_using<F>(&self, hash: HashValue, key_eq: F) -> Option<(usize, usize)>
1549 where
1550 F: Fn(&Bucket<K, V>) -> bool,
1551 {
1552 dispatch_32_vs_64!(self.find_using_impl::<_>(hash, key_eq))
1553 }
1554
find_using_impl<Sz, F>(&self, hash: HashValue, key_eq: F) -> Option<(usize, usize)> where F: Fn(&Bucket<K, V>) -> bool, Sz: Size,1555 fn find_using_impl<Sz, F>(&self, hash: HashValue, key_eq: F) -> Option<(usize, usize)>
1556 where
1557 F: Fn(&Bucket<K, V>) -> bool,
1558 Sz: Size,
1559 {
1560 debug_assert!(self.len() > 0);
1561 let mut probe = desired_pos(self.mask, hash);
1562 let mut dist = 0;
1563 probe_loop!(probe < self.indices.len(), {
1564 if let Some((i, hash_proxy)) = self.indices[probe].resolve::<Sz>() {
1565 let entry_hash = hash_proxy.get_short_hash(&self.entries, i);
1566 if dist > probe_distance(self.mask, entry_hash.into_hash(), probe) {
1567 // give up when probe distance is too long
1568 return None;
1569 } else if entry_hash == hash && key_eq(&self.entries[i]) {
1570 return Some((probe, i));
1571 }
1572 } else {
1573 return None;
1574 }
1575 dist += 1;
1576 });
1577 }
1578
1579 /// Find `entry` which is already placed inside self.entries;
1580 /// return its probe and entry index.
find_existing_entry(&self, entry: &Bucket<K, V>) -> (usize, usize)1581 fn find_existing_entry(&self, entry: &Bucket<K, V>) -> (usize, usize) {
1582 debug_assert!(self.len() > 0);
1583
1584 let hash = entry.hash;
1585 let actual_pos = ptrdistance(&self.entries[0], entry);
1586 let probe = dispatch_32_vs_64!(self =>
1587 find_existing_entry_at(&self.indices, hash, self.mask, actual_pos));
1588 (probe, actual_pos)
1589 }
1590
1591 /// Remove an entry by shifting all entries that follow it
shift_remove_found(&mut self, probe: usize, found: usize) -> (K, V)1592 fn shift_remove_found(&mut self, probe: usize, found: usize) -> (K, V) {
1593 dispatch_32_vs_64!(self.shift_remove_found_impl(probe, found))
1594 }
1595
shift_remove_found_impl<Sz>(&mut self, probe: usize, found: usize) -> (K, V) where Sz: Size,1596 fn shift_remove_found_impl<Sz>(&mut self, probe: usize, found: usize) -> (K, V)
1597 where
1598 Sz: Size,
1599 {
1600 // index `probe` and entry `found` is to be removed
1601 // use Vec::remove, but then we need to update the indices that point
1602 // to all of the other entries that have to move
1603 self.indices[probe] = Pos::none();
1604 let entry = self.entries.remove(found);
1605
1606 // correct indices that point to the entries that followed the removed entry.
1607 // use a heuristic between a full sweep vs. a `probe_loop!` for every shifted item.
1608 if self.indices.len() < (self.entries.len() - found) * 2 {
1609 // shift all indices greater than `found`
1610 for pos in self.indices.iter_mut() {
1611 if let Some((i, _)) = pos.resolve::<Sz>() {
1612 if i > found {
1613 // shift the index
1614 pos.set_pos::<Sz>(i - 1);
1615 }
1616 }
1617 }
1618 } else {
1619 // find each following entry to shift its index
1620 for (offset, entry) in enumerate(&self.entries[found..]) {
1621 let index = found + offset;
1622 let mut probe = desired_pos(self.mask, entry.hash);
1623 probe_loop!(probe < self.indices.len(), {
1624 let pos = &mut self.indices[probe];
1625 if let Some((i, _)) = pos.resolve::<Sz>() {
1626 if i == index + 1 {
1627 // found it, shift it
1628 pos.set_pos::<Sz>(index);
1629 break;
1630 }
1631 }
1632 });
1633 }
1634 }
1635
1636 self.backward_shift_after_removal::<Sz>(probe);
1637
1638 (entry.key, entry.value)
1639 }
1640
1641 /// Remove an entry by swapping it with the last
swap_remove_found(&mut self, probe: usize, found: usize) -> (K, V)1642 fn swap_remove_found(&mut self, probe: usize, found: usize) -> (K, V) {
1643 dispatch_32_vs_64!(self.swap_remove_found_impl(probe, found))
1644 }
1645
swap_remove_found_impl<Sz>(&mut self, probe: usize, found: usize) -> (K, V) where Sz: Size,1646 fn swap_remove_found_impl<Sz>(&mut self, probe: usize, found: usize) -> (K, V)
1647 where
1648 Sz: Size,
1649 {
1650 // index `probe` and entry `found` is to be removed
1651 // use swap_remove, but then we need to update the index that points
1652 // to the other entry that has to move
1653 self.indices[probe] = Pos::none();
1654 let entry = self.entries.swap_remove(found);
1655
1656 // correct index that points to the entry that had to swap places
1657 if let Some(entry) = self.entries.get(found) {
1658 // was not last element
1659 // examine new element in `found` and find it in indices
1660 let mut probe = desired_pos(self.mask, entry.hash);
1661 probe_loop!(probe < self.indices.len(), {
1662 let pos = &mut self.indices[probe];
1663 if let Some((i, _)) = pos.resolve::<Sz>() {
1664 if i >= self.entries.len() {
1665 // found it
1666 pos.set_pos::<Sz>(found);
1667 break;
1668 }
1669 }
1670 });
1671 }
1672
1673 self.backward_shift_after_removal::<Sz>(probe);
1674
1675 (entry.key, entry.value)
1676 }
1677
backward_shift_after_removal<Sz>(&mut self, probe_at_remove: usize) where Sz: Size,1678 fn backward_shift_after_removal<Sz>(&mut self, probe_at_remove: usize)
1679 where
1680 Sz: Size,
1681 {
1682 // backward shift deletion in self.indices
1683 // after probe, shift all non-ideally placed indices backward
1684 let mut last_probe = probe_at_remove;
1685 let mut probe = probe_at_remove + 1;
1686 probe_loop!(probe < self.indices.len(), {
1687 if let Some((i, hash_proxy)) = self.indices[probe].resolve::<Sz>() {
1688 let entry_hash = hash_proxy.get_short_hash(&self.entries, i);
1689 if probe_distance(self.mask, entry_hash.into_hash(), probe) > 0 {
1690 self.indices[last_probe] = self.indices[probe];
1691 self.indices[probe] = Pos::none();
1692 } else {
1693 break;
1694 }
1695 } else {
1696 break;
1697 }
1698 last_probe = probe;
1699 });
1700 }
1701
retain_in_order_impl<Sz, F>(&mut self, mut keep: F) where F: FnMut(&mut K, &mut V) -> bool, Sz: Size,1702 fn retain_in_order_impl<Sz, F>(&mut self, mut keep: F)
1703 where
1704 F: FnMut(&mut K, &mut V) -> bool,
1705 Sz: Size,
1706 {
1707 // Like Vec::retain in self.entries; for each removed key-value pair,
1708 // we clear its corresponding spot in self.indices, and run the
1709 // usual backward shift in self.indices.
1710 let len = self.entries.len();
1711 let mut n_deleted = 0;
1712 for i in 0..len {
1713 let will_keep;
1714 let hash;
1715 {
1716 let ent = &mut self.entries[i];
1717 hash = ent.hash;
1718 will_keep = keep(&mut ent.key, &mut ent.value);
1719 };
1720 let probe = find_existing_entry_at::<Sz>(&self.indices, hash, self.mask, i);
1721 if !will_keep {
1722 n_deleted += 1;
1723 self.indices[probe] = Pos::none();
1724 self.backward_shift_after_removal::<Sz>(probe);
1725 } else if n_deleted > 0 {
1726 self.indices[probe].set_pos::<Sz>(i - n_deleted);
1727 self.entries.swap(i - n_deleted, i);
1728 }
1729 }
1730 self.entries.truncate(len - n_deleted);
1731 }
1732
sort_by<F>(&mut self, mut compare: F) where F: FnMut(&K, &V, &K, &V) -> Ordering,1733 fn sort_by<F>(&mut self, mut compare: F)
1734 where
1735 F: FnMut(&K, &V, &K, &V) -> Ordering,
1736 {
1737 let side_index = self.save_hash_index();
1738 self.entries
1739 .sort_by(move |ei, ej| compare(&ei.key, &ei.value, &ej.key, &ej.value));
1740 self.restore_hash_index(side_index);
1741 }
1742
save_hash_index(&mut self) -> Vec<usize>1743 fn save_hash_index(&mut self) -> Vec<usize> {
1744 // Temporarily use the hash field in a bucket to store the old index.
1745 // Save the old hash values in `side_index`. Then we can sort
1746 // `self.entries` in place.
1747 Vec::from_iter(
1748 enumerate(&mut self.entries).map(|(i, elt)| replace(&mut elt.hash, HashValue(i)).get()),
1749 )
1750 }
1751
restore_hash_index(&mut self, mut side_index: Vec<usize>)1752 fn restore_hash_index(&mut self, mut side_index: Vec<usize>) {
1753 // Write back the hash values from side_index and fill `side_index` with
1754 // a mapping from the old to the new index instead.
1755 for (i, ent) in enumerate(&mut self.entries) {
1756 let old_index = ent.hash.get();
1757 ent.hash = HashValue(replace(&mut side_index[old_index], i));
1758 }
1759
1760 // Apply new index to self.indices
1761 dispatch_32_vs_64!(self => apply_new_index(&mut self.indices, &side_index));
1762
1763 fn apply_new_index<Sz>(indices: &mut [Pos], new_index: &[usize])
1764 where
1765 Sz: Size,
1766 {
1767 for pos in indices {
1768 if let Some((i, _)) = pos.resolve::<Sz>() {
1769 pos.set_pos::<Sz>(new_index[i]);
1770 }
1771 }
1772 }
1773 }
1774 }
1775
1776 /// Find, in the indices, an entry that already exists at a known position
1777 /// inside self.entries in the IndexMap.
1778 ///
1779 /// This is effectively reverse lookup, from the entries into the hash buckets.
1780 ///
1781 /// Return the probe index (into self.indices)
1782 ///
1783 /// + indices: The self.indices of the map,
1784 /// + hash: The full hash value from the bucket
1785 /// + mask: self.mask.
1786 /// + entry_index: The index of the entry in self.entries
find_existing_entry_at<Sz>( indices: &[Pos], hash: HashValue, mask: usize, entry_index: usize, ) -> usize where Sz: Size,1787 fn find_existing_entry_at<Sz>(
1788 indices: &[Pos],
1789 hash: HashValue,
1790 mask: usize,
1791 entry_index: usize,
1792 ) -> usize
1793 where
1794 Sz: Size,
1795 {
1796 let mut probe = desired_pos(mask, hash);
1797 probe_loop!(probe < indices.len(), {
1798 // the entry *must* be present; if we hit a Pos::none this was not true
1799 // and there is a debug assertion in resolve_existing_index for that.
1800 let i = indices[probe].resolve_existing_index::<Sz>();
1801 if i == entry_index {
1802 return probe;
1803 }
1804 });
1805 }
1806
1807 use std::slice::Iter as SliceIter;
1808 use std::slice::IterMut as SliceIterMut;
1809 use std::vec::IntoIter as VecIntoIter;
1810
1811 /// An iterator over the keys of a `IndexMap`.
1812 ///
1813 /// This `struct` is created by the [`keys`] method on [`IndexMap`]. See its
1814 /// documentation for more.
1815 ///
1816 /// [`keys`]: struct.IndexMap.html#method.keys
1817 /// [`IndexMap`]: struct.IndexMap.html
1818 pub struct Keys<'a, K: 'a, V: 'a> {
1819 pub(crate) iter: SliceIter<'a, Bucket<K, V>>,
1820 }
1821
1822 impl<'a, K, V> Iterator for Keys<'a, K, V> {
1823 type Item = &'a K;
1824
1825 iterator_methods!(Bucket::key_ref);
1826 }
1827
1828 impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
next_back(&mut self) -> Option<&'a K>1829 fn next_back(&mut self) -> Option<&'a K> {
1830 self.iter.next_back().map(Bucket::key_ref)
1831 }
1832 }
1833
1834 impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {
len(&self) -> usize1835 fn len(&self) -> usize {
1836 self.iter.len()
1837 }
1838 }
1839
1840 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
1841 impl<'a, K, V> Clone for Keys<'a, K, V> {
clone(&self) -> Keys<'a, K, V>1842 fn clone(&self) -> Keys<'a, K, V> {
1843 Keys {
1844 iter: self.iter.clone(),
1845 }
1846 }
1847 }
1848
1849 impl<'a, K: fmt::Debug, V> fmt::Debug for Keys<'a, K, V> {
fmt(&self, f: &mut fmt::Formatter) -> fmt::Result1850 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1851 f.debug_list().entries(self.clone()).finish()
1852 }
1853 }
1854
1855 /// An iterator over the values of a `IndexMap`.
1856 ///
1857 /// This `struct` is created by the [`values`] method on [`IndexMap`]. See its
1858 /// documentation for more.
1859 ///
1860 /// [`values`]: struct.IndexMap.html#method.values
1861 /// [`IndexMap`]: struct.IndexMap.html
1862 pub struct Values<'a, K: 'a, V: 'a> {
1863 iter: SliceIter<'a, Bucket<K, V>>,
1864 }
1865
1866 impl<'a, K, V> Iterator for Values<'a, K, V> {
1867 type Item = &'a V;
1868
1869 iterator_methods!(Bucket::value_ref);
1870 }
1871
1872 impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
next_back(&mut self) -> Option<Self::Item>1873 fn next_back(&mut self) -> Option<Self::Item> {
1874 self.iter.next_back().map(Bucket::value_ref)
1875 }
1876 }
1877
1878 impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {
len(&self) -> usize1879 fn len(&self) -> usize {
1880 self.iter.len()
1881 }
1882 }
1883
1884 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
1885 impl<'a, K, V> Clone for Values<'a, K, V> {
clone(&self) -> Values<'a, K, V>1886 fn clone(&self) -> Values<'a, K, V> {
1887 Values {
1888 iter: self.iter.clone(),
1889 }
1890 }
1891 }
1892
1893 impl<'a, K, V: fmt::Debug> fmt::Debug for Values<'a, K, V> {
fmt(&self, f: &mut fmt::Formatter) -> fmt::Result1894 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1895 f.debug_list().entries(self.clone()).finish()
1896 }
1897 }
1898
1899 /// A mutable iterator over the values of a `IndexMap`.
1900 ///
1901 /// This `struct` is created by the [`values_mut`] method on [`IndexMap`]. See its
1902 /// documentation for more.
1903 ///
1904 /// [`values_mut`]: struct.IndexMap.html#method.values_mut
1905 /// [`IndexMap`]: struct.IndexMap.html
1906 pub struct ValuesMut<'a, K: 'a, V: 'a> {
1907 iter: SliceIterMut<'a, Bucket<K, V>>,
1908 }
1909
1910 impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
1911 type Item = &'a mut V;
1912
1913 iterator_methods!(Bucket::value_mut);
1914 }
1915
1916 impl<'a, K, V> DoubleEndedIterator for ValuesMut<'a, K, V> {
next_back(&mut self) -> Option<Self::Item>1917 fn next_back(&mut self) -> Option<Self::Item> {
1918 self.iter.next_back().map(Bucket::value_mut)
1919 }
1920 }
1921
1922 impl<'a, K, V> ExactSizeIterator for ValuesMut<'a, K, V> {
len(&self) -> usize1923 fn len(&self) -> usize {
1924 self.iter.len()
1925 }
1926 }
1927
1928 /// An iterator over the entries of a `IndexMap`.
1929 ///
1930 /// This `struct` is created by the [`iter`] method on [`IndexMap`]. See its
1931 /// documentation for more.
1932 ///
1933 /// [`iter`]: struct.IndexMap.html#method.iter
1934 /// [`IndexMap`]: struct.IndexMap.html
1935 pub struct Iter<'a, K: 'a, V: 'a> {
1936 iter: SliceIter<'a, Bucket<K, V>>,
1937 }
1938
1939 impl<'a, K, V> Iterator for Iter<'a, K, V> {
1940 type Item = (&'a K, &'a V);
1941
1942 iterator_methods!(Bucket::refs);
1943 }
1944
1945 impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V> {
next_back(&mut self) -> Option<Self::Item>1946 fn next_back(&mut self) -> Option<Self::Item> {
1947 self.iter.next_back().map(Bucket::refs)
1948 }
1949 }
1950
1951 impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {
len(&self) -> usize1952 fn len(&self) -> usize {
1953 self.iter.len()
1954 }
1955 }
1956
1957 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
1958 impl<'a, K, V> Clone for Iter<'a, K, V> {
clone(&self) -> Iter<'a, K, V>1959 fn clone(&self) -> Iter<'a, K, V> {
1960 Iter {
1961 iter: self.iter.clone(),
1962 }
1963 }
1964 }
1965
1966 impl<'a, K: fmt::Debug, V: fmt::Debug> fmt::Debug for Iter<'a, K, V> {
fmt(&self, f: &mut fmt::Formatter) -> fmt::Result1967 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1968 f.debug_list().entries(self.clone()).finish()
1969 }
1970 }
1971
1972 /// A mutable iterator over the entries of a `IndexMap`.
1973 ///
1974 /// This `struct` is created by the [`iter_mut`] method on [`IndexMap`]. See its
1975 /// documentation for more.
1976 ///
1977 /// [`iter_mut`]: struct.IndexMap.html#method.iter_mut
1978 /// [`IndexMap`]: struct.IndexMap.html
1979 pub struct IterMut<'a, K: 'a, V: 'a> {
1980 iter: SliceIterMut<'a, Bucket<K, V>>,
1981 }
1982
1983 impl<'a, K, V> Iterator for IterMut<'a, K, V> {
1984 type Item = (&'a K, &'a mut V);
1985
1986 iterator_methods!(Bucket::ref_mut);
1987 }
1988
1989 impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> {
next_back(&mut self) -> Option<Self::Item>1990 fn next_back(&mut self) -> Option<Self::Item> {
1991 self.iter.next_back().map(Bucket::ref_mut)
1992 }
1993 }
1994
1995 impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {
len(&self) -> usize1996 fn len(&self) -> usize {
1997 self.iter.len()
1998 }
1999 }
2000
2001 /// An owning iterator over the entries of a `IndexMap`.
2002 ///
2003 /// This `struct` is created by the [`into_iter`] method on [`IndexMap`]
2004 /// (provided by the `IntoIterator` trait). See its documentation for more.
2005 ///
2006 /// [`into_iter`]: struct.IndexMap.html#method.into_iter
2007 /// [`IndexMap`]: struct.IndexMap.html
2008 pub struct IntoIter<K, V> {
2009 pub(crate) iter: VecIntoIter<Bucket<K, V>>,
2010 }
2011
2012 impl<K, V> Iterator for IntoIter<K, V> {
2013 type Item = (K, V);
2014
2015 iterator_methods!(Bucket::key_value);
2016 }
2017
2018 impl<'a, K, V> DoubleEndedIterator for IntoIter<K, V> {
next_back(&mut self) -> Option<Self::Item>2019 fn next_back(&mut self) -> Option<Self::Item> {
2020 self.iter.next_back().map(Bucket::key_value)
2021 }
2022 }
2023
2024 impl<K, V> ExactSizeIterator for IntoIter<K, V> {
len(&self) -> usize2025 fn len(&self) -> usize {
2026 self.iter.len()
2027 }
2028 }
2029
2030 impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IntoIter<K, V> {
fmt(&self, f: &mut fmt::Formatter) -> fmt::Result2031 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2032 let iter = self.iter.as_slice().iter().map(Bucket::refs);
2033 f.debug_list().entries(iter).finish()
2034 }
2035 }
2036
2037 /// A draining iterator over the entries of a `IndexMap`.
2038 ///
2039 /// This `struct` is created by the [`drain`] method on [`IndexMap`]. See its
2040 /// documentation for more.
2041 ///
2042 /// [`drain`]: struct.IndexMap.html#method.drain
2043 /// [`IndexMap`]: struct.IndexMap.html
2044 pub struct Drain<'a, K, V>
2045 where
2046 K: 'a,
2047 V: 'a,
2048 {
2049 pub(crate) iter: ::std::vec::Drain<'a, Bucket<K, V>>,
2050 }
2051
2052 impl<'a, K, V> Iterator for Drain<'a, K, V> {
2053 type Item = (K, V);
2054
2055 iterator_methods!(Bucket::key_value);
2056 }
2057
2058 impl<'a, K, V> DoubleEndedIterator for Drain<'a, K, V> {
2059 double_ended_iterator_methods!(Bucket::key_value);
2060 }
2061
2062 impl<'a, K, V, S> IntoIterator for &'a IndexMap<K, V, S>
2063 where
2064 K: Hash + Eq,
2065 S: BuildHasher,
2066 {
2067 type Item = (&'a K, &'a V);
2068 type IntoIter = Iter<'a, K, V>;
into_iter(self) -> Self::IntoIter2069 fn into_iter(self) -> Self::IntoIter {
2070 self.iter()
2071 }
2072 }
2073
2074 impl<'a, K, V, S> IntoIterator for &'a mut IndexMap<K, V, S>
2075 where
2076 K: Hash + Eq,
2077 S: BuildHasher,
2078 {
2079 type Item = (&'a K, &'a mut V);
2080 type IntoIter = IterMut<'a, K, V>;
into_iter(self) -> Self::IntoIter2081 fn into_iter(self) -> Self::IntoIter {
2082 self.iter_mut()
2083 }
2084 }
2085
2086 impl<K, V, S> IntoIterator for IndexMap<K, V, S>
2087 where
2088 K: Hash + Eq,
2089 S: BuildHasher,
2090 {
2091 type Item = (K, V);
2092 type IntoIter = IntoIter<K, V>;
into_iter(self) -> Self::IntoIter2093 fn into_iter(self) -> Self::IntoIter {
2094 IntoIter {
2095 iter: self.core.entries.into_iter(),
2096 }
2097 }
2098 }
2099
2100 use std::ops::{Index, IndexMut};
2101
2102 impl<'a, K, V, Q: ?Sized, S> Index<&'a Q> for IndexMap<K, V, S>
2103 where
2104 Q: Hash + Equivalent<K>,
2105 K: Hash + Eq,
2106 S: BuildHasher,
2107 {
2108 type Output = V;
2109
2110 /// ***Panics*** if `key` is not present in the map.
index(&self, key: &'a Q) -> &V2111 fn index(&self, key: &'a Q) -> &V {
2112 if let Some(v) = self.get(key) {
2113 v
2114 } else {
2115 panic!("IndexMap: key not found")
2116 }
2117 }
2118 }
2119
2120 /// Mutable indexing allows changing / updating values of key-value
2121 /// pairs that are already present.
2122 ///
2123 /// You can **not** insert new pairs with index syntax, use `.insert()`.
2124 impl<'a, K, V, Q: ?Sized, S> IndexMut<&'a Q> for IndexMap<K, V, S>
2125 where
2126 Q: Hash + Equivalent<K>,
2127 K: Hash + Eq,
2128 S: BuildHasher,
2129 {
2130 /// ***Panics*** if `key` is not present in the map.
index_mut(&mut self, key: &'a Q) -> &mut V2131 fn index_mut(&mut self, key: &'a Q) -> &mut V {
2132 if let Some(v) = self.get_mut(key) {
2133 v
2134 } else {
2135 panic!("IndexMap: key not found")
2136 }
2137 }
2138 }
2139
2140 impl<K, V, S> FromIterator<(K, V)> for IndexMap<K, V, S>
2141 where
2142 K: Hash + Eq,
2143 S: BuildHasher + Default,
2144 {
2145 /// Create an `IndexMap` from the sequence of key-value pairs in the
2146 /// iterable.
2147 ///
2148 /// `from_iter` uses the same logic as `extend`. See
2149 /// [`extend`](#method.extend) for more details.
from_iter<I: IntoIterator<Item = (K, V)>>(iterable: I) -> Self2150 fn from_iter<I: IntoIterator<Item = (K, V)>>(iterable: I) -> Self {
2151 let iter = iterable.into_iter();
2152 let (low, _) = iter.size_hint();
2153 let mut map = Self::with_capacity_and_hasher(low, <_>::default());
2154 map.extend(iter);
2155 map
2156 }
2157 }
2158
2159 impl<K, V, S> Extend<(K, V)> for IndexMap<K, V, S>
2160 where
2161 K: Hash + Eq,
2162 S: BuildHasher,
2163 {
2164 /// Extend the map with all key-value pairs in the iterable.
2165 ///
2166 /// This is equivalent to calling [`insert`](#method.insert) for each of
2167 /// them in order, which means that for keys that already existed
2168 /// in the map, their value is updated but it keeps the existing order.
2169 ///
2170 /// New keys are inserted in the order they appear in the sequence. If
2171 /// equivalents of a key occur more than once, the last corresponding value
2172 /// prevails.
extend<I: IntoIterator<Item = (K, V)>>(&mut self, iterable: I)2173 fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iterable: I) {
2174 for (k, v) in iterable {
2175 self.insert(k, v);
2176 }
2177 }
2178 }
2179
2180 impl<'a, K, V, S> Extend<(&'a K, &'a V)> for IndexMap<K, V, S>
2181 where
2182 K: Hash + Eq + Copy,
2183 V: Copy,
2184 S: BuildHasher,
2185 {
2186 /// Extend the map with all key-value pairs in the iterable.
2187 ///
2188 /// See the first extend method for more details.
extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iterable: I)2189 fn extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iterable: I) {
2190 self.extend(iterable.into_iter().map(|(&key, &value)| (key, value)));
2191 }
2192 }
2193
2194 impl<K, V, S> Default for IndexMap<K, V, S>
2195 where
2196 S: BuildHasher + Default,
2197 {
2198 /// Return an empty `IndexMap`
default() -> Self2199 fn default() -> Self {
2200 Self::with_capacity_and_hasher(0, S::default())
2201 }
2202 }
2203
2204 impl<K, V1, S1, V2, S2> PartialEq<IndexMap<K, V2, S2>> for IndexMap<K, V1, S1>
2205 where
2206 K: Hash + Eq,
2207 V1: PartialEq<V2>,
2208 S1: BuildHasher,
2209 S2: BuildHasher,
2210 {
eq(&self, other: &IndexMap<K, V2, S2>) -> bool2211 fn eq(&self, other: &IndexMap<K, V2, S2>) -> bool {
2212 if self.len() != other.len() {
2213 return false;
2214 }
2215
2216 self.iter()
2217 .all(|(key, value)| other.get(key).map_or(false, |v| *value == *v))
2218 }
2219 }
2220
2221 impl<K, V, S> Eq for IndexMap<K, V, S>
2222 where
2223 K: Eq + Hash,
2224 V: Eq,
2225 S: BuildHasher,
2226 {
2227 }
2228
2229 #[cfg(test)]
2230 mod tests {
2231 use super::*;
2232 use util::enumerate;
2233
2234 #[test]
it_works()2235 fn it_works() {
2236 let mut map = IndexMap::new();
2237 assert_eq!(map.is_empty(), true);
2238 map.insert(1, ());
2239 map.insert(1, ());
2240 assert_eq!(map.len(), 1);
2241 assert!(map.get(&1).is_some());
2242 assert_eq!(map.is_empty(), false);
2243 }
2244
2245 #[test]
new()2246 fn new() {
2247 let map = IndexMap::<String, String>::new();
2248 println!("{:?}", map);
2249 assert_eq!(map.capacity(), 0);
2250 assert_eq!(map.len(), 0);
2251 assert_eq!(map.is_empty(), true);
2252 }
2253
2254 #[test]
insert()2255 fn insert() {
2256 let insert = [0, 4, 2, 12, 8, 7, 11, 5];
2257 let not_present = [1, 3, 6, 9, 10];
2258 let mut map = IndexMap::with_capacity(insert.len());
2259
2260 for (i, &elt) in enumerate(&insert) {
2261 assert_eq!(map.len(), i);
2262 map.insert(elt, elt);
2263 assert_eq!(map.len(), i + 1);
2264 assert_eq!(map.get(&elt), Some(&elt));
2265 assert_eq!(map[&elt], elt);
2266 }
2267 println!("{:?}", map);
2268
2269 for &elt in ¬_present {
2270 assert!(map.get(&elt).is_none());
2271 }
2272 }
2273
2274 #[test]
insert_full()2275 fn insert_full() {
2276 let insert = vec![9, 2, 7, 1, 4, 6, 13];
2277 let present = vec![1, 6, 2];
2278 let mut map = IndexMap::with_capacity(insert.len());
2279
2280 for (i, &elt) in enumerate(&insert) {
2281 assert_eq!(map.len(), i);
2282 let (index, existing) = map.insert_full(elt, elt);
2283 assert_eq!(existing, None);
2284 assert_eq!(Some(index), map.get_full(&elt).map(|x| x.0));
2285 assert_eq!(map.len(), i + 1);
2286 }
2287
2288 let len = map.len();
2289 for &elt in &present {
2290 let (index, existing) = map.insert_full(elt, elt);
2291 assert_eq!(existing, Some(elt));
2292 assert_eq!(Some(index), map.get_full(&elt).map(|x| x.0));
2293 assert_eq!(map.len(), len);
2294 }
2295 }
2296
2297 #[test]
insert_2()2298 fn insert_2() {
2299 let mut map = IndexMap::with_capacity(16);
2300
2301 let mut keys = vec![];
2302 keys.extend(0..16);
2303 keys.extend(128..267);
2304
2305 for &i in &keys {
2306 let old_map = map.clone();
2307 map.insert(i, ());
2308 for key in old_map.keys() {
2309 if map.get(key).is_none() {
2310 println!("old_map: {:?}", old_map);
2311 println!("map: {:?}", map);
2312 panic!("did not find {} in map", key);
2313 }
2314 }
2315 }
2316
2317 for &i in &keys {
2318 assert!(map.get(&i).is_some(), "did not find {}", i);
2319 }
2320 }
2321
2322 #[test]
insert_order()2323 fn insert_order() {
2324 let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23];
2325 let mut map = IndexMap::new();
2326
2327 for &elt in &insert {
2328 map.insert(elt, ());
2329 }
2330
2331 assert_eq!(map.keys().count(), map.len());
2332 assert_eq!(map.keys().count(), insert.len());
2333 for (a, b) in insert.iter().zip(map.keys()) {
2334 assert_eq!(a, b);
2335 }
2336 for (i, k) in (0..insert.len()).zip(map.keys()) {
2337 assert_eq!(map.get_index(i).unwrap().0, k);
2338 }
2339 }
2340
2341 #[test]
grow()2342 fn grow() {
2343 let insert = [0, 4, 2, 12, 8, 7, 11];
2344 let not_present = [1, 3, 6, 9, 10];
2345 let mut map = IndexMap::with_capacity(insert.len());
2346
2347 for (i, &elt) in enumerate(&insert) {
2348 assert_eq!(map.len(), i);
2349 map.insert(elt, elt);
2350 assert_eq!(map.len(), i + 1);
2351 assert_eq!(map.get(&elt), Some(&elt));
2352 assert_eq!(map[&elt], elt);
2353 }
2354
2355 println!("{:?}", map);
2356 for &elt in &insert {
2357 map.insert(elt * 10, elt);
2358 }
2359 for &elt in &insert {
2360 map.insert(elt * 100, elt);
2361 }
2362 for (i, &elt) in insert.iter().cycle().enumerate().take(100) {
2363 map.insert(elt * 100 + i as i32, elt);
2364 }
2365 println!("{:?}", map);
2366 for &elt in ¬_present {
2367 assert!(map.get(&elt).is_none());
2368 }
2369 }
2370
2371 #[test]
remove()2372 fn remove() {
2373 let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23];
2374 let mut map = IndexMap::new();
2375
2376 for &elt in &insert {
2377 map.insert(elt, elt);
2378 }
2379
2380 assert_eq!(map.keys().count(), map.len());
2381 assert_eq!(map.keys().count(), insert.len());
2382 for (a, b) in insert.iter().zip(map.keys()) {
2383 assert_eq!(a, b);
2384 }
2385
2386 let remove_fail = [99, 77];
2387 let remove = [4, 12, 8, 7];
2388
2389 for &key in &remove_fail {
2390 assert!(map.swap_remove_full(&key).is_none());
2391 }
2392 println!("{:?}", map);
2393 for &key in &remove {
2394 //println!("{:?}", map);
2395 let index = map.get_full(&key).unwrap().0;
2396 assert_eq!(map.swap_remove_full(&key), Some((index, key, key)));
2397 }
2398 println!("{:?}", map);
2399
2400 for key in &insert {
2401 assert_eq!(map.get(key).is_some(), !remove.contains(key));
2402 }
2403 assert_eq!(map.len(), insert.len() - remove.len());
2404 assert_eq!(map.keys().count(), insert.len() - remove.len());
2405 }
2406
2407 #[test]
remove_to_empty()2408 fn remove_to_empty() {
2409 let mut map = indexmap! { 0 => 0, 4 => 4, 5 => 5 };
2410 map.swap_remove(&5).unwrap();
2411 map.swap_remove(&4).unwrap();
2412 map.swap_remove(&0).unwrap();
2413 assert!(map.is_empty());
2414 }
2415
2416 #[test]
swap_remove_index()2417 fn swap_remove_index() {
2418 let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23];
2419 let mut map = IndexMap::new();
2420
2421 for &elt in &insert {
2422 map.insert(elt, elt * 2);
2423 }
2424
2425 let mut vector = insert.to_vec();
2426 let remove_sequence = &[3, 3, 10, 4, 5, 4, 3, 0, 1];
2427
2428 // check that the same swap remove sequence on vec and map
2429 // have the same result.
2430 for &rm in remove_sequence {
2431 let out_vec = vector.swap_remove(rm);
2432 let (out_map, _) = map.swap_remove_index(rm).unwrap();
2433 assert_eq!(out_vec, out_map);
2434 }
2435 assert_eq!(vector.len(), map.len());
2436 for (a, b) in vector.iter().zip(map.keys()) {
2437 assert_eq!(a, b);
2438 }
2439 }
2440
2441 #[test]
partial_eq_and_eq()2442 fn partial_eq_and_eq() {
2443 let mut map_a = IndexMap::new();
2444 map_a.insert(1, "1");
2445 map_a.insert(2, "2");
2446 let mut map_b = map_a.clone();
2447 assert_eq!(map_a, map_b);
2448 map_b.swap_remove(&1);
2449 assert_ne!(map_a, map_b);
2450
2451 let map_c: IndexMap<_, String> =
2452 map_b.into_iter().map(|(k, v)| (k, v.to_owned())).collect();
2453 assert_ne!(map_a, map_c);
2454 assert_ne!(map_c, map_a);
2455 }
2456
2457 #[test]
extend()2458 fn extend() {
2459 let mut map = IndexMap::new();
2460 map.extend(vec![(&1, &2), (&3, &4)]);
2461 map.extend(vec![(5, 6)]);
2462 assert_eq!(
2463 map.into_iter().collect::<Vec<_>>(),
2464 vec![(1, 2), (3, 4), (5, 6)]
2465 );
2466 }
2467
2468 #[test]
entry()2469 fn entry() {
2470 let mut map = IndexMap::new();
2471
2472 map.insert(1, "1");
2473 map.insert(2, "2");
2474 {
2475 let e = map.entry(3);
2476 assert_eq!(e.index(), 2);
2477 let e = e.or_insert("3");
2478 assert_eq!(e, &"3");
2479 }
2480
2481 let e = map.entry(2);
2482 assert_eq!(e.index(), 1);
2483 assert_eq!(e.key(), &2);
2484 match e {
2485 Entry::Occupied(ref e) => assert_eq!(e.get(), &"2"),
2486 Entry::Vacant(_) => panic!(),
2487 }
2488 assert_eq!(e.or_insert("4"), &"2");
2489 }
2490
2491 #[test]
entry_and_modify()2492 fn entry_and_modify() {
2493 let mut map = IndexMap::new();
2494
2495 map.insert(1, "1");
2496 map.entry(1).and_modify(|x| *x = "2");
2497 assert_eq!(Some(&"2"), map.get(&1));
2498
2499 map.entry(2).and_modify(|x| *x = "doesn't exist");
2500 assert_eq!(None, map.get(&2));
2501 }
2502
2503 #[test]
entry_or_default()2504 fn entry_or_default() {
2505 let mut map = IndexMap::new();
2506
2507 #[derive(Debug, PartialEq)]
2508 enum TestEnum {
2509 DefaultValue,
2510 NonDefaultValue,
2511 }
2512
2513 impl Default for TestEnum {
2514 fn default() -> Self {
2515 TestEnum::DefaultValue
2516 }
2517 }
2518
2519 map.insert(1, TestEnum::NonDefaultValue);
2520 assert_eq!(&mut TestEnum::NonDefaultValue, map.entry(1).or_default());
2521
2522 assert_eq!(&mut TestEnum::DefaultValue, map.entry(2).or_default());
2523 }
2524
2525 #[test]
keys()2526 fn keys() {
2527 let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
2528 let map: IndexMap<_, _> = vec.into_iter().collect();
2529 let keys: Vec<_> = map.keys().cloned().collect();
2530 assert_eq!(keys.len(), 3);
2531 assert!(keys.contains(&1));
2532 assert!(keys.contains(&2));
2533 assert!(keys.contains(&3));
2534 }
2535
2536 #[test]
values()2537 fn values() {
2538 let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
2539 let map: IndexMap<_, _> = vec.into_iter().collect();
2540 let values: Vec<_> = map.values().cloned().collect();
2541 assert_eq!(values.len(), 3);
2542 assert!(values.contains(&'a'));
2543 assert!(values.contains(&'b'));
2544 assert!(values.contains(&'c'));
2545 }
2546
2547 #[test]
values_mut()2548 fn values_mut() {
2549 let vec = vec![(1, 1), (2, 2), (3, 3)];
2550 let mut map: IndexMap<_, _> = vec.into_iter().collect();
2551 for value in map.values_mut() {
2552 *value *= 2
2553 }
2554 let values: Vec<_> = map.values().cloned().collect();
2555 assert_eq!(values.len(), 3);
2556 assert!(values.contains(&2));
2557 assert!(values.contains(&4));
2558 assert!(values.contains(&6));
2559 }
2560 }
2561