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 mod core; 5 6 pub use crate::mutable_keys::MutableKeys; 7 8 #[cfg(feature = "rayon")] 9 pub use crate::rayon::map as rayon; 10 11 use crate::vec::{self, Vec}; 12 use ::core::cmp::Ordering; 13 use ::core::fmt; 14 use ::core::hash::{BuildHasher, Hash, Hasher}; 15 use ::core::iter::FromIterator; 16 use ::core::ops::{Index, IndexMut, RangeBounds}; 17 use ::core::slice::{Iter as SliceIter, IterMut as SliceIterMut}; 18 19 #[cfg(has_std)] 20 use std::collections::hash_map::RandomState; 21 22 use self::core::IndexMapCore; 23 use crate::equivalent::Equivalent; 24 use crate::util::third; 25 use crate::{Bucket, Entries, HashValue}; 26 27 pub use self::core::{Entry, OccupiedEntry, VacantEntry}; 28 29 /// A hash table where the iteration order of the key-value pairs is independent 30 /// of the hash values of the keys. 31 /// 32 /// The interface is closely compatible with the standard `HashMap`, but also 33 /// has additional features. 34 /// 35 /// # Order 36 /// 37 /// The key-value pairs have a consistent order that is determined by 38 /// the sequence of insertion and removal calls on the map. The order does 39 /// not depend on the keys or the hash function at all. 40 /// 41 /// All iterators traverse the map in *the order*. 42 /// 43 /// The insertion order is preserved, with **notable exceptions** like the 44 /// `.remove()` or `.swap_remove()` methods. Methods such as `.sort_by()` of 45 /// course result in a new order, depending on the sorting order. 46 /// 47 /// # Indices 48 /// 49 /// The key-value pairs are indexed in a compact range without holes in the 50 /// range `0..self.len()`. For example, the method `.get_full` looks up the 51 /// index for a key, and the method `.get_index` looks up the key-value pair by 52 /// index. 53 /// 54 /// # Examples 55 /// 56 /// ``` 57 /// use indexmap::IndexMap; 58 /// 59 /// // count the frequency of each letter in a sentence. 60 /// let mut letters = IndexMap::new(); 61 /// for ch in "a short treatise on fungi".chars() { 62 /// *letters.entry(ch).or_insert(0) += 1; 63 /// } 64 /// 65 /// assert_eq!(letters[&'s'], 2); 66 /// assert_eq!(letters[&'t'], 3); 67 /// assert_eq!(letters[&'u'], 1); 68 /// assert_eq!(letters.get(&'y'), None); 69 /// ``` 70 #[cfg(has_std)] 71 pub struct IndexMap<K, V, S = RandomState> { 72 core: IndexMapCore<K, V>, 73 hash_builder: S, 74 } 75 #[cfg(not(has_std))] 76 pub struct IndexMap<K, V, S> { 77 core: IndexMapCore<K, V>, 78 hash_builder: S, 79 } 80 81 impl<K, V, S> Clone for IndexMap<K, V, S> 82 where 83 K: Clone, 84 V: Clone, 85 S: Clone, 86 { clone(&self) -> Self87 fn clone(&self) -> Self { 88 IndexMap { 89 core: self.core.clone(), 90 hash_builder: self.hash_builder.clone(), 91 } 92 } 93 clone_from(&mut self, other: &Self)94 fn clone_from(&mut self, other: &Self) { 95 self.core.clone_from(&other.core); 96 self.hash_builder.clone_from(&other.hash_builder); 97 } 98 } 99 100 impl<K, V, S> Entries for IndexMap<K, V, S> { 101 type Entry = Bucket<K, V>; 102 103 #[inline] into_entries(self) -> Vec<Self::Entry>104 fn into_entries(self) -> Vec<Self::Entry> { 105 self.core.into_entries() 106 } 107 108 #[inline] as_entries(&self) -> &[Self::Entry]109 fn as_entries(&self) -> &[Self::Entry] { 110 self.core.as_entries() 111 } 112 113 #[inline] as_entries_mut(&mut self) -> &mut [Self::Entry]114 fn as_entries_mut(&mut self) -> &mut [Self::Entry] { 115 self.core.as_entries_mut() 116 } 117 with_entries<F>(&mut self, f: F) where F: FnOnce(&mut [Self::Entry]),118 fn with_entries<F>(&mut self, f: F) 119 where 120 F: FnOnce(&mut [Self::Entry]), 121 { 122 self.core.with_entries(f); 123 } 124 } 125 126 impl<K, V, S> fmt::Debug for IndexMap<K, V, S> 127 where 128 K: fmt::Debug, 129 V: fmt::Debug, 130 { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result131 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 132 if cfg!(not(feature = "test_debug")) { 133 f.debug_map().entries(self.iter()).finish() 134 } else { 135 // Let the inner `IndexMapCore` print all of its details 136 f.debug_struct("IndexMap") 137 .field("core", &self.core) 138 .finish() 139 } 140 } 141 } 142 143 #[cfg(has_std)] 144 impl<K, V> IndexMap<K, V> { 145 /// Create a new map. (Does not allocate.) 146 #[inline] new() -> Self147 pub fn new() -> Self { 148 Self::with_capacity(0) 149 } 150 151 /// Create a new map with capacity for `n` key-value pairs. (Does not 152 /// allocate if `n` is zero.) 153 /// 154 /// Computes in **O(n)** time. 155 #[inline] with_capacity(n: usize) -> Self156 pub fn with_capacity(n: usize) -> Self { 157 Self::with_capacity_and_hasher(n, <_>::default()) 158 } 159 } 160 161 impl<K, V, S> IndexMap<K, V, S> { 162 /// Create a new map with capacity for `n` key-value pairs. (Does not 163 /// allocate if `n` is zero.) 164 /// 165 /// Computes in **O(n)** time. 166 #[inline] with_capacity_and_hasher(n: usize, hash_builder: S) -> Self167 pub fn with_capacity_and_hasher(n: usize, hash_builder: S) -> Self { 168 if n == 0 { 169 IndexMap { 170 core: IndexMapCore::new(), 171 hash_builder, 172 } 173 } else { 174 IndexMap { 175 core: IndexMapCore::with_capacity(n), 176 hash_builder, 177 } 178 } 179 } 180 181 /// Create a new map with `hash_builder` with_hasher(hash_builder: S) -> Self182 pub fn with_hasher(hash_builder: S) -> Self { 183 Self::with_capacity_and_hasher(0, hash_builder) 184 } 185 186 /// Computes in **O(1)** time. capacity(&self) -> usize187 pub fn capacity(&self) -> usize { 188 self.core.capacity() 189 } 190 191 /// Return a reference to the map's `BuildHasher`. hasher(&self) -> &S192 pub fn hasher(&self) -> &S { 193 &self.hash_builder 194 } 195 196 /// Return the number of key-value pairs in the map. 197 /// 198 /// Computes in **O(1)** time. 199 #[inline] len(&self) -> usize200 pub fn len(&self) -> usize { 201 self.core.len() 202 } 203 204 /// Returns true if the map contains no elements. 205 /// 206 /// Computes in **O(1)** time. 207 #[inline] is_empty(&self) -> bool208 pub fn is_empty(&self) -> bool { 209 self.len() == 0 210 } 211 212 /// Return an iterator over the key-value pairs of the map, in their order iter(&self) -> Iter<'_, K, V>213 pub fn iter(&self) -> Iter<'_, K, V> { 214 Iter { 215 iter: self.as_entries().iter(), 216 } 217 } 218 219 /// Return an iterator over the key-value pairs of the map, in their order iter_mut(&mut self) -> IterMut<'_, K, V>220 pub fn iter_mut(&mut self) -> IterMut<'_, K, V> { 221 IterMut { 222 iter: self.as_entries_mut().iter_mut(), 223 } 224 } 225 226 /// Return an iterator over the keys of the map, in their order keys(&self) -> Keys<'_, K, V>227 pub fn keys(&self) -> Keys<'_, K, V> { 228 Keys { 229 iter: self.as_entries().iter(), 230 } 231 } 232 233 /// Return an iterator over the values of the map, in their order values(&self) -> Values<'_, K, V>234 pub fn values(&self) -> Values<'_, K, V> { 235 Values { 236 iter: self.as_entries().iter(), 237 } 238 } 239 240 /// Return an iterator over mutable references to the values of the map, 241 /// in their order values_mut(&mut self) -> ValuesMut<'_, K, V>242 pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> { 243 ValuesMut { 244 iter: self.as_entries_mut().iter_mut(), 245 } 246 } 247 248 /// Remove all key-value pairs in the map, while preserving its capacity. 249 /// 250 /// Computes in **O(n)** time. clear(&mut self)251 pub fn clear(&mut self) { 252 self.core.clear(); 253 } 254 255 /// Shortens the map, keeping the first `len` elements and dropping the rest. 256 /// 257 /// If `len` is greater than the map's current length, this has no effect. truncate(&mut self, len: usize)258 pub fn truncate(&mut self, len: usize) { 259 self.core.truncate(len); 260 } 261 262 /// Clears the `IndexMap` in the given index range, returning those 263 /// key-value pairs as a drain iterator. 264 /// 265 /// The range may be any type that implements `RangeBounds<usize>`, 266 /// including all of the `std::ops::Range*` types, or even a tuple pair of 267 /// `Bound` start and end values. To drain the map entirely, use `RangeFull` 268 /// like `map.drain(..)`. 269 /// 270 /// This shifts down all entries following the drained range to fill the 271 /// gap, and keeps the allocated memory for reuse. 272 /// 273 /// ***Panics*** if the starting point is greater than the end point or if 274 /// the end point is greater than the length of the map. drain<R>(&mut self, range: R) -> Drain<'_, K, V> where R: RangeBounds<usize>,275 pub fn drain<R>(&mut self, range: R) -> Drain<'_, K, V> 276 where 277 R: RangeBounds<usize>, 278 { 279 Drain { 280 iter: self.core.drain(range), 281 } 282 } 283 284 /// Splits the collection into two at the given index. 285 /// 286 /// Returns a newly allocated map containing the elements in the range 287 /// `[at, len)`. After the call, the original map will be left containing 288 /// the elements `[0, at)` with its previous capacity unchanged. 289 /// 290 /// ***Panics*** if `at > len`. split_off(&mut self, at: usize) -> Self where S: Clone,291 pub fn split_off(&mut self, at: usize) -> Self 292 where 293 S: Clone, 294 { 295 Self { 296 core: self.core.split_off(at), 297 hash_builder: self.hash_builder.clone(), 298 } 299 } 300 } 301 302 impl<K, V, S> IndexMap<K, V, S> 303 where 304 K: Hash + Eq, 305 S: BuildHasher, 306 { 307 /// Reserve capacity for `additional` more key-value pairs. 308 /// 309 /// Computes in **O(n)** time. reserve(&mut self, additional: usize)310 pub fn reserve(&mut self, additional: usize) { 311 self.core.reserve(additional); 312 } 313 314 /// Shrink the capacity of the map as much as possible. 315 /// 316 /// Computes in **O(n)** time. shrink_to_fit(&mut self)317 pub fn shrink_to_fit(&mut self) { 318 self.core.shrink_to_fit(); 319 } 320 hash<Q: ?Sized + Hash>(&self, key: &Q) -> HashValue321 fn hash<Q: ?Sized + Hash>(&self, key: &Q) -> HashValue { 322 let mut h = self.hash_builder.build_hasher(); 323 key.hash(&mut h); 324 HashValue(h.finish() as usize) 325 } 326 327 /// Insert a key-value pair in the map. 328 /// 329 /// If an equivalent key already exists in the map: the key remains and 330 /// retains in its place in the order, its corresponding value is updated 331 /// with `value` and the older value is returned inside `Some(_)`. 332 /// 333 /// If no equivalent key existed in the map: the new key-value pair is 334 /// inserted, last in order, and `None` is returned. 335 /// 336 /// Computes in **O(1)** time (amortized average). 337 /// 338 /// See also [`entry`](#method.entry) if you you want to insert *or* modify 339 /// or if you need to get the index of the corresponding key-value pair. insert(&mut self, key: K, value: V) -> Option<V>340 pub fn insert(&mut self, key: K, value: V) -> Option<V> { 341 self.insert_full(key, value).1 342 } 343 344 /// Insert a key-value pair in the map, and get their index. 345 /// 346 /// If an equivalent key already exists in the map: the key remains and 347 /// retains in its place in the order, its corresponding value is updated 348 /// with `value` and the older value is returned inside `(index, Some(_))`. 349 /// 350 /// If no equivalent key existed in the map: the new key-value pair is 351 /// inserted, last in order, and `(index, None)` is returned. 352 /// 353 /// Computes in **O(1)** time (amortized average). 354 /// 355 /// See also [`entry`](#method.entry) if you you want to insert *or* modify 356 /// 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>)357 pub fn insert_full(&mut self, key: K, value: V) -> (usize, Option<V>) { 358 let hash = self.hash(&key); 359 self.core.insert_full(hash, key, value) 360 } 361 362 /// Get the given key’s corresponding entry in the map for insertion and/or 363 /// in-place manipulation. 364 /// 365 /// Computes in **O(1)** time (amortized average). entry(&mut self, key: K) -> Entry<'_, K, V>366 pub fn entry(&mut self, key: K) -> Entry<'_, K, V> { 367 let hash = self.hash(&key); 368 self.core.entry(hash, key) 369 } 370 371 /// Return `true` if an equivalent to `key` exists in the map. 372 /// 373 /// Computes in **O(1)** time (average). contains_key<Q: ?Sized>(&self, key: &Q) -> bool where Q: Hash + Equivalent<K>,374 pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool 375 where 376 Q: Hash + Equivalent<K>, 377 { 378 self.get_index_of(key).is_some() 379 } 380 381 /// Return a reference to the value stored for `key`, if it is present, 382 /// else `None`. 383 /// 384 /// Computes in **O(1)** time (average). get<Q: ?Sized>(&self, key: &Q) -> Option<&V> where Q: Hash + Equivalent<K>,385 pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> 386 where 387 Q: Hash + Equivalent<K>, 388 { 389 if let Some(i) = self.get_index_of(key) { 390 let entry = &self.as_entries()[i]; 391 Some(&entry.value) 392 } else { 393 None 394 } 395 } 396 397 /// Return references to the key-value pair stored for `key`, 398 /// if it is present, else `None`. 399 /// 400 /// Computes in **O(1)** time (average). get_key_value<Q: ?Sized>(&self, key: &Q) -> Option<(&K, &V)> where Q: Hash + Equivalent<K>,401 pub fn get_key_value<Q: ?Sized>(&self, key: &Q) -> Option<(&K, &V)> 402 where 403 Q: Hash + Equivalent<K>, 404 { 405 if let Some(i) = self.get_index_of(key) { 406 let entry = &self.as_entries()[i]; 407 Some((&entry.key, &entry.value)) 408 } else { 409 None 410 } 411 } 412 413 /// Return item index, key and value get_full<Q: ?Sized>(&self, key: &Q) -> Option<(usize, &K, &V)> where Q: Hash + Equivalent<K>,414 pub fn get_full<Q: ?Sized>(&self, key: &Q) -> Option<(usize, &K, &V)> 415 where 416 Q: Hash + Equivalent<K>, 417 { 418 if let Some(i) = self.get_index_of(key) { 419 let entry = &self.as_entries()[i]; 420 Some((i, &entry.key, &entry.value)) 421 } else { 422 None 423 } 424 } 425 426 /// Return item index, if it exists in the map 427 /// 428 /// Computes in **O(1)** time (average). get_index_of<Q: ?Sized>(&self, key: &Q) -> Option<usize> where Q: Hash + Equivalent<K>,429 pub fn get_index_of<Q: ?Sized>(&self, key: &Q) -> Option<usize> 430 where 431 Q: Hash + Equivalent<K>, 432 { 433 if self.is_empty() { 434 None 435 } else { 436 let hash = self.hash(key); 437 self.core.get_index_of(hash, key) 438 } 439 } 440 get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> where Q: Hash + Equivalent<K>,441 pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> 442 where 443 Q: Hash + Equivalent<K>, 444 { 445 if let Some(i) = self.get_index_of(key) { 446 let entry = &mut self.as_entries_mut()[i]; 447 Some(&mut entry.value) 448 } else { 449 None 450 } 451 } 452 get_full_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, &K, &mut V)> where Q: Hash + Equivalent<K>,453 pub fn get_full_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, &K, &mut V)> 454 where 455 Q: Hash + Equivalent<K>, 456 { 457 if let Some(i) = self.get_index_of(key) { 458 let entry = &mut self.as_entries_mut()[i]; 459 Some((i, &entry.key, &mut entry.value)) 460 } else { 461 None 462 } 463 } 464 get_full_mut2_impl<Q: ?Sized>( &mut self, key: &Q, ) -> Option<(usize, &mut K, &mut V)> where Q: Hash + Equivalent<K>,465 pub(crate) fn get_full_mut2_impl<Q: ?Sized>( 466 &mut self, 467 key: &Q, 468 ) -> Option<(usize, &mut K, &mut V)> 469 where 470 Q: Hash + Equivalent<K>, 471 { 472 if let Some(i) = self.get_index_of(key) { 473 let entry = &mut self.as_entries_mut()[i]; 474 Some((i, &mut entry.key, &mut entry.value)) 475 } else { 476 None 477 } 478 } 479 480 /// Remove the key-value pair equivalent to `key` and return 481 /// its value. 482 /// 483 /// **NOTE:** This is equivalent to `.swap_remove(key)`, if you need to 484 /// preserve the order of the keys in the map, use `.shift_remove(key)` 485 /// instead. 486 /// 487 /// Computes in **O(1)** time (average). remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where Q: Hash + Equivalent<K>,488 pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> 489 where 490 Q: Hash + Equivalent<K>, 491 { 492 self.swap_remove(key) 493 } 494 495 /// Remove and return the key-value pair equivalent to `key`. 496 /// 497 /// **NOTE:** This is equivalent to `.swap_remove_entry(key)`, if you need to 498 /// preserve the order of the keys in the map, use `.shift_remove_entry(key)` 499 /// instead. 500 /// 501 /// Computes in **O(1)** time (average). remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)> where Q: Hash + Equivalent<K>,502 pub fn remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)> 503 where 504 Q: Hash + Equivalent<K>, 505 { 506 self.swap_remove_entry(key) 507 } 508 509 /// Remove the key-value pair equivalent to `key` and return 510 /// its value. 511 /// 512 /// Like `Vec::swap_remove`, the pair is removed by swapping it with the 513 /// last element of the map and popping it off. **This perturbs 514 /// the position of what used to be the last element!** 515 /// 516 /// Return `None` if `key` is not in map. 517 /// 518 /// Computes in **O(1)** time (average). swap_remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where Q: Hash + Equivalent<K>,519 pub fn swap_remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> 520 where 521 Q: Hash + Equivalent<K>, 522 { 523 self.swap_remove_full(key).map(third) 524 } 525 526 /// Remove and return the key-value pair equivalent to `key`. 527 /// 528 /// Like `Vec::swap_remove`, the pair is removed by swapping it with the 529 /// last element of the map and popping it off. **This perturbs 530 /// the position of what used to be the last element!** 531 /// 532 /// Return `None` if `key` is not in map. 533 /// 534 /// Computes in **O(1)** time (average). swap_remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)> where Q: Hash + Equivalent<K>,535 pub fn swap_remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)> 536 where 537 Q: Hash + Equivalent<K>, 538 { 539 match self.swap_remove_full(key) { 540 Some((_, key, value)) => Some((key, value)), 541 None => None, 542 } 543 } 544 545 /// Remove the key-value pair equivalent to `key` and return it and 546 /// the index it had. 547 /// 548 /// Like `Vec::swap_remove`, the pair is removed by swapping it with the 549 /// last element of the map and popping it off. **This perturbs 550 /// the position of what used to be the last element!** 551 /// 552 /// Return `None` if `key` is not in map. 553 /// 554 /// Computes in **O(1)** time (average). swap_remove_full<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, K, V)> where Q: Hash + Equivalent<K>,555 pub fn swap_remove_full<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, K, V)> 556 where 557 Q: Hash + Equivalent<K>, 558 { 559 if self.is_empty() { 560 return None; 561 } 562 let hash = self.hash(key); 563 self.core.swap_remove_full(hash, key) 564 } 565 566 /// Remove the key-value pair equivalent to `key` and return 567 /// its value. 568 /// 569 /// Like `Vec::remove`, the pair is removed by shifting all of the 570 /// elements that follow it, preserving their relative order. 571 /// **This perturbs the index of all of those elements!** 572 /// 573 /// Return `None` if `key` is not in map. 574 /// 575 /// Computes in **O(n)** time (average). shift_remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where Q: Hash + Equivalent<K>,576 pub fn shift_remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> 577 where 578 Q: Hash + Equivalent<K>, 579 { 580 self.shift_remove_full(key).map(third) 581 } 582 583 /// Remove and return the key-value pair equivalent to `key`. 584 /// 585 /// Like `Vec::remove`, the pair is removed by shifting all of the 586 /// elements that follow it, preserving their relative order. 587 /// **This perturbs the index of all of those elements!** 588 /// 589 /// Return `None` if `key` is not in map. 590 /// 591 /// Computes in **O(n)** time (average). shift_remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)> where Q: Hash + Equivalent<K>,592 pub fn shift_remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)> 593 where 594 Q: Hash + Equivalent<K>, 595 { 596 match self.shift_remove_full(key) { 597 Some((_, key, value)) => Some((key, value)), 598 None => None, 599 } 600 } 601 602 /// Remove the key-value pair equivalent to `key` and return it and 603 /// the index it had. 604 /// 605 /// Like `Vec::remove`, the pair is removed by shifting all of the 606 /// elements that follow it, preserving their relative order. 607 /// **This perturbs the index of all of those elements!** 608 /// 609 /// Return `None` if `key` is not in map. 610 /// 611 /// Computes in **O(n)** time (average). shift_remove_full<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, K, V)> where Q: Hash + Equivalent<K>,612 pub fn shift_remove_full<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, K, V)> 613 where 614 Q: Hash + Equivalent<K>, 615 { 616 if self.is_empty() { 617 return None; 618 } 619 let hash = self.hash(key); 620 self.core.shift_remove_full(hash, key) 621 } 622 623 /// Remove the last key-value pair 624 /// 625 /// Computes in **O(1)** time (average). pop(&mut self) -> Option<(K, V)>626 pub fn pop(&mut self) -> Option<(K, V)> { 627 self.core.pop() 628 } 629 630 /// Scan through each key-value pair in the map and keep those where the 631 /// closure `keep` returns `true`. 632 /// 633 /// The elements are visited in order, and remaining elements keep their 634 /// order. 635 /// 636 /// Computes in **O(n)** time (average). retain<F>(&mut self, mut keep: F) where F: FnMut(&K, &mut V) -> bool,637 pub fn retain<F>(&mut self, mut keep: F) 638 where 639 F: FnMut(&K, &mut V) -> bool, 640 { 641 self.core.retain_in_order(move |k, v| keep(k, v)); 642 } 643 retain_mut<F>(&mut self, keep: F) where F: FnMut(&mut K, &mut V) -> bool,644 pub(crate) fn retain_mut<F>(&mut self, keep: F) 645 where 646 F: FnMut(&mut K, &mut V) -> bool, 647 { 648 self.core.retain_in_order(keep); 649 } 650 651 /// Sort the map’s key-value pairs by the default ordering of the keys. 652 /// 653 /// See `sort_by` for details. sort_keys(&mut self) where K: Ord,654 pub fn sort_keys(&mut self) 655 where 656 K: Ord, 657 { 658 self.with_entries(|entries| { 659 entries.sort_by(|a, b| Ord::cmp(&a.key, &b.key)); 660 }); 661 } 662 663 /// Sort the map’s key-value pairs in place using the comparison 664 /// function `compare`. 665 /// 666 /// The comparison function receives two key and value pairs to compare (you 667 /// can sort by keys or values or their combination as needed). 668 /// 669 /// Computes in **O(n log n + c)** time and **O(n)** space where *n* is 670 /// the length of the map and *c* the capacity. The sort is stable. sort_by<F>(&mut self, mut cmp: F) where F: FnMut(&K, &V, &K, &V) -> Ordering,671 pub fn sort_by<F>(&mut self, mut cmp: F) 672 where 673 F: FnMut(&K, &V, &K, &V) -> Ordering, 674 { 675 self.with_entries(move |entries| { 676 entries.sort_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value)); 677 }); 678 } 679 680 /// Sort the key-value pairs of the map and return a by value iterator of 681 /// the key-value pairs with the result. 682 /// 683 /// The sort is stable. sorted_by<F>(self, mut cmp: F) -> IntoIter<K, V> where F: FnMut(&K, &V, &K, &V) -> Ordering,684 pub fn sorted_by<F>(self, mut cmp: F) -> IntoIter<K, V> 685 where 686 F: FnMut(&K, &V, &K, &V) -> Ordering, 687 { 688 let mut entries = self.into_entries(); 689 entries.sort_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value)); 690 IntoIter { 691 iter: entries.into_iter(), 692 } 693 } 694 695 /// Reverses the order of the map’s key-value pairs in place. 696 /// 697 /// Computes in **O(n)** time and **O(1)** space. reverse(&mut self)698 pub fn reverse(&mut self) { 699 self.core.reverse() 700 } 701 } 702 703 impl<K, V, S> IndexMap<K, V, S> { 704 /// Get a key-value pair by index 705 /// 706 /// Valid indices are *0 <= index < self.len()* 707 /// 708 /// Computes in **O(1)** time. get_index(&self, index: usize) -> Option<(&K, &V)>709 pub fn get_index(&self, index: usize) -> Option<(&K, &V)> { 710 self.as_entries().get(index).map(Bucket::refs) 711 } 712 713 /// Get a key-value pair by index 714 /// 715 /// Valid indices are *0 <= index < self.len()* 716 /// 717 /// Computes in **O(1)** time. get_index_mut(&mut self, index: usize) -> Option<(&mut K, &mut V)>718 pub fn get_index_mut(&mut self, index: usize) -> Option<(&mut K, &mut V)> { 719 self.as_entries_mut().get_mut(index).map(Bucket::muts) 720 } 721 722 /// Get the first key-value pair 723 /// 724 /// Computes in **O(1)** time. first(&self) -> Option<(&K, &V)>725 pub fn first(&self) -> Option<(&K, &V)> { 726 self.as_entries().first().map(Bucket::refs) 727 } 728 729 /// Get the first key-value pair, with mutable access to the value 730 /// 731 /// Computes in **O(1)** time. first_mut(&mut self) -> Option<(&K, &mut V)>732 pub fn first_mut(&mut self) -> Option<(&K, &mut V)> { 733 self.as_entries_mut().first_mut().map(Bucket::ref_mut) 734 } 735 736 /// Get the last key-value pair 737 /// 738 /// Computes in **O(1)** time. last(&self) -> Option<(&K, &V)>739 pub fn last(&self) -> Option<(&K, &V)> { 740 self.as_entries().last().map(Bucket::refs) 741 } 742 743 /// Get the last key-value pair, with mutable access to the value 744 /// 745 /// Computes in **O(1)** time. last_mut(&mut self) -> Option<(&K, &mut V)>746 pub fn last_mut(&mut self) -> Option<(&K, &mut V)> { 747 self.as_entries_mut().last_mut().map(Bucket::ref_mut) 748 } 749 750 /// Remove the key-value pair by index 751 /// 752 /// Valid indices are *0 <= index < self.len()* 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 position of what used to be the last element!** 757 /// 758 /// Computes in **O(1)** time (average). swap_remove_index(&mut self, index: usize) -> Option<(K, V)>759 pub fn swap_remove_index(&mut self, index: usize) -> Option<(K, V)> { 760 self.core.swap_remove_index(index) 761 } 762 763 /// Remove the key-value pair by index 764 /// 765 /// Valid indices are *0 <= index < self.len()* 766 /// 767 /// Like `Vec::remove`, the pair is removed by shifting all of the 768 /// elements that follow it, preserving their relative order. 769 /// **This perturbs the index of all of those elements!** 770 /// 771 /// Computes in **O(n)** time (average). shift_remove_index(&mut self, index: usize) -> Option<(K, V)>772 pub fn shift_remove_index(&mut self, index: usize) -> Option<(K, V)> { 773 self.core.shift_remove_index(index) 774 } 775 776 /// Swaps the position of two key-value pairs in the map. 777 /// 778 /// ***Panics*** if `a` or `b` are out of bounds. swap_indices(&mut self, a: usize, b: usize)779 pub fn swap_indices(&mut self, a: usize, b: usize) { 780 self.core.swap_indices(a, b) 781 } 782 } 783 784 /// An iterator over the keys of a `IndexMap`. 785 /// 786 /// This `struct` is created by the [`keys`] method on [`IndexMap`]. See its 787 /// documentation for more. 788 /// 789 /// [`keys`]: struct.IndexMap.html#method.keys 790 /// [`IndexMap`]: struct.IndexMap.html 791 pub struct Keys<'a, K, V> { 792 pub(crate) iter: SliceIter<'a, Bucket<K, V>>, 793 } 794 795 impl<'a, K, V> Iterator for Keys<'a, K, V> { 796 type Item = &'a K; 797 798 iterator_methods!(Bucket::key_ref); 799 } 800 801 impl<K, V> DoubleEndedIterator for Keys<'_, K, V> { next_back(&mut self) -> Option<Self::Item>802 fn next_back(&mut self) -> Option<Self::Item> { 803 self.iter.next_back().map(Bucket::key_ref) 804 } 805 } 806 807 impl<K, V> ExactSizeIterator for Keys<'_, K, V> { len(&self) -> usize808 fn len(&self) -> usize { 809 self.iter.len() 810 } 811 } 812 813 // FIXME(#26925) Remove in favor of `#[derive(Clone)]` 814 impl<K, V> Clone for Keys<'_, K, V> { clone(&self) -> Self815 fn clone(&self) -> Self { 816 Keys { 817 iter: self.iter.clone(), 818 } 819 } 820 } 821 822 impl<K: fmt::Debug, V> fmt::Debug for Keys<'_, K, V> { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result823 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 824 f.debug_list().entries(self.clone()).finish() 825 } 826 } 827 828 /// An iterator over the values of a `IndexMap`. 829 /// 830 /// This `struct` is created by the [`values`] method on [`IndexMap`]. See its 831 /// documentation for more. 832 /// 833 /// [`values`]: struct.IndexMap.html#method.values 834 /// [`IndexMap`]: struct.IndexMap.html 835 pub struct Values<'a, K, V> { 836 iter: SliceIter<'a, Bucket<K, V>>, 837 } 838 839 impl<'a, K, V> Iterator for Values<'a, K, V> { 840 type Item = &'a V; 841 842 iterator_methods!(Bucket::value_ref); 843 } 844 845 impl<K, V> DoubleEndedIterator for Values<'_, K, V> { next_back(&mut self) -> Option<Self::Item>846 fn next_back(&mut self) -> Option<Self::Item> { 847 self.iter.next_back().map(Bucket::value_ref) 848 } 849 } 850 851 impl<K, V> ExactSizeIterator for Values<'_, K, V> { len(&self) -> usize852 fn len(&self) -> usize { 853 self.iter.len() 854 } 855 } 856 857 // FIXME(#26925) Remove in favor of `#[derive(Clone)]` 858 impl<K, V> Clone for Values<'_, K, V> { clone(&self) -> Self859 fn clone(&self) -> Self { 860 Values { 861 iter: self.iter.clone(), 862 } 863 } 864 } 865 866 impl<K, V: fmt::Debug> fmt::Debug for Values<'_, K, V> { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result867 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 868 f.debug_list().entries(self.clone()).finish() 869 } 870 } 871 872 /// A mutable iterator over the values of a `IndexMap`. 873 /// 874 /// This `struct` is created by the [`values_mut`] method on [`IndexMap`]. See its 875 /// documentation for more. 876 /// 877 /// [`values_mut`]: struct.IndexMap.html#method.values_mut 878 /// [`IndexMap`]: struct.IndexMap.html 879 pub struct ValuesMut<'a, K, V> { 880 iter: SliceIterMut<'a, Bucket<K, V>>, 881 } 882 883 impl<'a, K, V> Iterator for ValuesMut<'a, K, V> { 884 type Item = &'a mut V; 885 886 iterator_methods!(Bucket::value_mut); 887 } 888 889 impl<K, V> DoubleEndedIterator for ValuesMut<'_, K, V> { next_back(&mut self) -> Option<Self::Item>890 fn next_back(&mut self) -> Option<Self::Item> { 891 self.iter.next_back().map(Bucket::value_mut) 892 } 893 } 894 895 impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> { len(&self) -> usize896 fn len(&self) -> usize { 897 self.iter.len() 898 } 899 } 900 901 /// An iterator over the entries of a `IndexMap`. 902 /// 903 /// This `struct` is created by the [`iter`] method on [`IndexMap`]. See its 904 /// documentation for more. 905 /// 906 /// [`iter`]: struct.IndexMap.html#method.iter 907 /// [`IndexMap`]: struct.IndexMap.html 908 pub struct Iter<'a, K, V> { 909 iter: SliceIter<'a, Bucket<K, V>>, 910 } 911 912 impl<'a, K, V> Iterator for Iter<'a, K, V> { 913 type Item = (&'a K, &'a V); 914 915 iterator_methods!(Bucket::refs); 916 } 917 918 impl<K, V> DoubleEndedIterator for Iter<'_, K, V> { next_back(&mut self) -> Option<Self::Item>919 fn next_back(&mut self) -> Option<Self::Item> { 920 self.iter.next_back().map(Bucket::refs) 921 } 922 } 923 924 impl<K, V> ExactSizeIterator for Iter<'_, K, V> { len(&self) -> usize925 fn len(&self) -> usize { 926 self.iter.len() 927 } 928 } 929 930 // FIXME(#26925) Remove in favor of `#[derive(Clone)]` 931 impl<K, V> Clone for Iter<'_, K, V> { clone(&self) -> Self932 fn clone(&self) -> Self { 933 Iter { 934 iter: self.iter.clone(), 935 } 936 } 937 } 938 939 impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Iter<'_, K, V> { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result940 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 941 f.debug_list().entries(self.clone()).finish() 942 } 943 } 944 945 /// A mutable iterator over the entries of a `IndexMap`. 946 /// 947 /// This `struct` is created by the [`iter_mut`] method on [`IndexMap`]. See its 948 /// documentation for more. 949 /// 950 /// [`iter_mut`]: struct.IndexMap.html#method.iter_mut 951 /// [`IndexMap`]: struct.IndexMap.html 952 pub struct IterMut<'a, K, V> { 953 iter: SliceIterMut<'a, Bucket<K, V>>, 954 } 955 956 impl<'a, K, V> Iterator for IterMut<'a, K, V> { 957 type Item = (&'a K, &'a mut V); 958 959 iterator_methods!(Bucket::ref_mut); 960 } 961 962 impl<K, V> DoubleEndedIterator for IterMut<'_, K, V> { next_back(&mut self) -> Option<Self::Item>963 fn next_back(&mut self) -> Option<Self::Item> { 964 self.iter.next_back().map(Bucket::ref_mut) 965 } 966 } 967 968 impl<K, V> ExactSizeIterator for IterMut<'_, K, V> { len(&self) -> usize969 fn len(&self) -> usize { 970 self.iter.len() 971 } 972 } 973 974 /// An owning iterator over the entries of a `IndexMap`. 975 /// 976 /// This `struct` is created by the [`into_iter`] method on [`IndexMap`] 977 /// (provided by the `IntoIterator` trait). See its documentation for more. 978 /// 979 /// [`into_iter`]: struct.IndexMap.html#method.into_iter 980 /// [`IndexMap`]: struct.IndexMap.html 981 pub struct IntoIter<K, V> { 982 pub(crate) iter: vec::IntoIter<Bucket<K, V>>, 983 } 984 985 impl<K, V> Iterator for IntoIter<K, V> { 986 type Item = (K, V); 987 988 iterator_methods!(Bucket::key_value); 989 } 990 991 impl<K, V> DoubleEndedIterator for IntoIter<K, V> { next_back(&mut self) -> Option<Self::Item>992 fn next_back(&mut self) -> Option<Self::Item> { 993 self.iter.next_back().map(Bucket::key_value) 994 } 995 } 996 997 impl<K, V> ExactSizeIterator for IntoIter<K, V> { len(&self) -> usize998 fn len(&self) -> usize { 999 self.iter.len() 1000 } 1001 } 1002 1003 impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IntoIter<K, V> { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1004 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 1005 let iter = self.iter.as_slice().iter().map(Bucket::refs); 1006 f.debug_list().entries(iter).finish() 1007 } 1008 } 1009 1010 /// A draining iterator over the entries of a `IndexMap`. 1011 /// 1012 /// This `struct` is created by the [`drain`] method on [`IndexMap`]. See its 1013 /// documentation for more. 1014 /// 1015 /// [`drain`]: struct.IndexMap.html#method.drain 1016 /// [`IndexMap`]: struct.IndexMap.html 1017 pub struct Drain<'a, K, V> { 1018 pub(crate) iter: vec::Drain<'a, Bucket<K, V>>, 1019 } 1020 1021 impl<K, V> Iterator for Drain<'_, K, V> { 1022 type Item = (K, V); 1023 1024 iterator_methods!(Bucket::key_value); 1025 } 1026 1027 impl<K, V> DoubleEndedIterator for Drain<'_, K, V> { 1028 double_ended_iterator_methods!(Bucket::key_value); 1029 } 1030 1031 impl<'a, K, V, S> IntoIterator for &'a IndexMap<K, V, S> { 1032 type Item = (&'a K, &'a V); 1033 type IntoIter = Iter<'a, K, V>; into_iter(self) -> Self::IntoIter1034 fn into_iter(self) -> Self::IntoIter { 1035 self.iter() 1036 } 1037 } 1038 1039 impl<'a, K, V, S> IntoIterator for &'a mut IndexMap<K, V, S> { 1040 type Item = (&'a K, &'a mut V); 1041 type IntoIter = IterMut<'a, K, V>; into_iter(self) -> Self::IntoIter1042 fn into_iter(self) -> Self::IntoIter { 1043 self.iter_mut() 1044 } 1045 } 1046 1047 impl<K, V, S> IntoIterator for IndexMap<K, V, S> { 1048 type Item = (K, V); 1049 type IntoIter = IntoIter<K, V>; into_iter(self) -> Self::IntoIter1050 fn into_iter(self) -> Self::IntoIter { 1051 IntoIter { 1052 iter: self.into_entries().into_iter(), 1053 } 1054 } 1055 } 1056 1057 /// Access `IndexMap` values corresponding to a key. 1058 /// 1059 /// # Examples 1060 /// 1061 /// ``` 1062 /// use indexmap::IndexMap; 1063 /// 1064 /// let mut map = IndexMap::new(); 1065 /// for word in "Lorem ipsum dolor sit amet".split_whitespace() { 1066 /// map.insert(word.to_lowercase(), word.to_uppercase()); 1067 /// } 1068 /// assert_eq!(map["lorem"], "LOREM"); 1069 /// assert_eq!(map["ipsum"], "IPSUM"); 1070 /// ``` 1071 /// 1072 /// ```should_panic 1073 /// use indexmap::IndexMap; 1074 /// 1075 /// let mut map = IndexMap::new(); 1076 /// map.insert("foo", 1); 1077 /// println!("{:?}", map["bar"]); // panics! 1078 /// ``` 1079 impl<K, V, Q: ?Sized, S> Index<&Q> for IndexMap<K, V, S> 1080 where 1081 Q: Hash + Equivalent<K>, 1082 K: Hash + Eq, 1083 S: BuildHasher, 1084 { 1085 type Output = V; 1086 1087 /// Returns a reference to the value corresponding to the supplied `key`. 1088 /// 1089 /// ***Panics*** if `key` is not present in the map. index(&self, key: &Q) -> &V1090 fn index(&self, key: &Q) -> &V { 1091 self.get(key).expect("IndexMap: key not found") 1092 } 1093 } 1094 1095 /// Access `IndexMap` values corresponding to a key. 1096 /// 1097 /// Mutable indexing allows changing / updating values of key-value 1098 /// pairs that are already present. 1099 /// 1100 /// You can **not** insert new pairs with index syntax, use `.insert()`. 1101 /// 1102 /// # Examples 1103 /// 1104 /// ``` 1105 /// use indexmap::IndexMap; 1106 /// 1107 /// let mut map = IndexMap::new(); 1108 /// for word in "Lorem ipsum dolor sit amet".split_whitespace() { 1109 /// map.insert(word.to_lowercase(), word.to_string()); 1110 /// } 1111 /// let lorem = &mut map["lorem"]; 1112 /// assert_eq!(lorem, "Lorem"); 1113 /// lorem.retain(char::is_lowercase); 1114 /// assert_eq!(map["lorem"], "orem"); 1115 /// ``` 1116 /// 1117 /// ```should_panic 1118 /// use indexmap::IndexMap; 1119 /// 1120 /// let mut map = IndexMap::new(); 1121 /// map.insert("foo", 1); 1122 /// map["bar"] = 1; // panics! 1123 /// ``` 1124 impl<K, V, Q: ?Sized, S> IndexMut<&Q> for IndexMap<K, V, S> 1125 where 1126 Q: Hash + Equivalent<K>, 1127 K: Hash + Eq, 1128 S: BuildHasher, 1129 { 1130 /// Returns a mutable reference to the value corresponding to the supplied `key`. 1131 /// 1132 /// ***Panics*** if `key` is not present in the map. index_mut(&mut self, key: &Q) -> &mut V1133 fn index_mut(&mut self, key: &Q) -> &mut V { 1134 self.get_mut(key).expect("IndexMap: key not found") 1135 } 1136 } 1137 1138 /// Access `IndexMap` values at indexed positions. 1139 /// 1140 /// # Examples 1141 /// 1142 /// ``` 1143 /// use indexmap::IndexMap; 1144 /// 1145 /// let mut map = IndexMap::new(); 1146 /// for word in "Lorem ipsum dolor sit amet".split_whitespace() { 1147 /// map.insert(word.to_lowercase(), word.to_uppercase()); 1148 /// } 1149 /// assert_eq!(map[0], "LOREM"); 1150 /// assert_eq!(map[1], "IPSUM"); 1151 /// map.reverse(); 1152 /// assert_eq!(map[0], "AMET"); 1153 /// assert_eq!(map[1], "SIT"); 1154 /// map.sort_keys(); 1155 /// assert_eq!(map[0], "AMET"); 1156 /// assert_eq!(map[1], "DOLOR"); 1157 /// ``` 1158 /// 1159 /// ```should_panic 1160 /// use indexmap::IndexMap; 1161 /// 1162 /// let mut map = IndexMap::new(); 1163 /// map.insert("foo", 1); 1164 /// println!("{:?}", map[10]); // panics! 1165 /// ``` 1166 impl<K, V, S> Index<usize> for IndexMap<K, V, S> { 1167 type Output = V; 1168 1169 /// Returns a reference to the value at the supplied `index`. 1170 /// 1171 /// ***Panics*** if `index` is out of bounds. index(&self, index: usize) -> &V1172 fn index(&self, index: usize) -> &V { 1173 self.get_index(index) 1174 .expect("IndexMap: index out of bounds") 1175 .1 1176 } 1177 } 1178 1179 /// Access `IndexMap` values at indexed positions. 1180 /// 1181 /// Mutable indexing allows changing / updating indexed values 1182 /// that are already present. 1183 /// 1184 /// You can **not** insert new values with index syntax, use `.insert()`. 1185 /// 1186 /// # Examples 1187 /// 1188 /// ``` 1189 /// use indexmap::IndexMap; 1190 /// 1191 /// let mut map = IndexMap::new(); 1192 /// for word in "Lorem ipsum dolor sit amet".split_whitespace() { 1193 /// map.insert(word.to_lowercase(), word.to_string()); 1194 /// } 1195 /// let lorem = &mut map[0]; 1196 /// assert_eq!(lorem, "Lorem"); 1197 /// lorem.retain(char::is_lowercase); 1198 /// assert_eq!(map["lorem"], "orem"); 1199 /// ``` 1200 /// 1201 /// ```should_panic 1202 /// use indexmap::IndexMap; 1203 /// 1204 /// let mut map = IndexMap::new(); 1205 /// map.insert("foo", 1); 1206 /// map[10] = 1; // panics! 1207 /// ``` 1208 impl<K, V, S> IndexMut<usize> for IndexMap<K, V, S> { 1209 /// Returns a mutable reference to the value at the supplied `index`. 1210 /// 1211 /// ***Panics*** if `index` is out of bounds. index_mut(&mut self, index: usize) -> &mut V1212 fn index_mut(&mut self, index: usize) -> &mut V { 1213 self.get_index_mut(index) 1214 .expect("IndexMap: index out of bounds") 1215 .1 1216 } 1217 } 1218 1219 impl<K, V, S> FromIterator<(K, V)> for IndexMap<K, V, S> 1220 where 1221 K: Hash + Eq, 1222 S: BuildHasher + Default, 1223 { 1224 /// Create an `IndexMap` from the sequence of key-value pairs in the 1225 /// iterable. 1226 /// 1227 /// `from_iter` uses the same logic as `extend`. See 1228 /// [`extend`](#method.extend) for more details. from_iter<I: IntoIterator<Item = (K, V)>>(iterable: I) -> Self1229 fn from_iter<I: IntoIterator<Item = (K, V)>>(iterable: I) -> Self { 1230 let iter = iterable.into_iter(); 1231 let (low, _) = iter.size_hint(); 1232 let mut map = Self::with_capacity_and_hasher(low, <_>::default()); 1233 map.extend(iter); 1234 map 1235 } 1236 } 1237 1238 impl<K, V, S> Extend<(K, V)> for IndexMap<K, V, S> 1239 where 1240 K: Hash + Eq, 1241 S: BuildHasher, 1242 { 1243 /// Extend the map with all key-value pairs in the iterable. 1244 /// 1245 /// This is equivalent to calling [`insert`](#method.insert) for each of 1246 /// them in order, which means that for keys that already existed 1247 /// in the map, their value is updated but it keeps the existing order. 1248 /// 1249 /// New keys are inserted in the order they appear in the sequence. If 1250 /// equivalents of a key occur more than once, the last corresponding value 1251 /// prevails. extend<I: IntoIterator<Item = (K, V)>>(&mut self, iterable: I)1252 fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iterable: I) { 1253 // (Note: this is a copy of `std`/`hashbrown`'s reservation logic.) 1254 // Keys may be already present or show multiple times in the iterator. 1255 // Reserve the entire hint lower bound if the map is empty. 1256 // Otherwise reserve half the hint (rounded up), so the map 1257 // will only resize twice in the worst case. 1258 let iter = iterable.into_iter(); 1259 let reserve = if self.is_empty() { 1260 iter.size_hint().0 1261 } else { 1262 (iter.size_hint().0 + 1) / 2 1263 }; 1264 self.reserve(reserve); 1265 iter.for_each(move |(k, v)| { 1266 self.insert(k, v); 1267 }); 1268 } 1269 } 1270 1271 impl<'a, K, V, S> Extend<(&'a K, &'a V)> for IndexMap<K, V, S> 1272 where 1273 K: Hash + Eq + Copy, 1274 V: Copy, 1275 S: BuildHasher, 1276 { 1277 /// Extend the map with all key-value pairs in the iterable. 1278 /// 1279 /// See the first extend method for more details. extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iterable: I)1280 fn extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iterable: I) { 1281 self.extend(iterable.into_iter().map(|(&key, &value)| (key, value))); 1282 } 1283 } 1284 1285 impl<K, V, S> Default for IndexMap<K, V, S> 1286 where 1287 S: Default, 1288 { 1289 /// Return an empty `IndexMap` default() -> Self1290 fn default() -> Self { 1291 Self::with_capacity_and_hasher(0, S::default()) 1292 } 1293 } 1294 1295 impl<K, V1, S1, V2, S2> PartialEq<IndexMap<K, V2, S2>> for IndexMap<K, V1, S1> 1296 where 1297 K: Hash + Eq, 1298 V1: PartialEq<V2>, 1299 S1: BuildHasher, 1300 S2: BuildHasher, 1301 { eq(&self, other: &IndexMap<K, V2, S2>) -> bool1302 fn eq(&self, other: &IndexMap<K, V2, S2>) -> bool { 1303 if self.len() != other.len() { 1304 return false; 1305 } 1306 1307 self.iter() 1308 .all(|(key, value)| other.get(key).map_or(false, |v| *value == *v)) 1309 } 1310 } 1311 1312 impl<K, V, S> Eq for IndexMap<K, V, S> 1313 where 1314 K: Eq + Hash, 1315 V: Eq, 1316 S: BuildHasher, 1317 { 1318 } 1319 1320 #[cfg(test)] 1321 mod tests { 1322 use super::*; 1323 use crate::util::enumerate; 1324 use std::string::String; 1325 1326 #[test] it_works()1327 fn it_works() { 1328 let mut map = IndexMap::new(); 1329 assert_eq!(map.is_empty(), true); 1330 map.insert(1, ()); 1331 map.insert(1, ()); 1332 assert_eq!(map.len(), 1); 1333 assert!(map.get(&1).is_some()); 1334 assert_eq!(map.is_empty(), false); 1335 } 1336 1337 #[test] new()1338 fn new() { 1339 let map = IndexMap::<String, String>::new(); 1340 println!("{:?}", map); 1341 assert_eq!(map.capacity(), 0); 1342 assert_eq!(map.len(), 0); 1343 assert_eq!(map.is_empty(), true); 1344 } 1345 1346 #[test] insert()1347 fn insert() { 1348 let insert = [0, 4, 2, 12, 8, 7, 11, 5]; 1349 let not_present = [1, 3, 6, 9, 10]; 1350 let mut map = IndexMap::with_capacity(insert.len()); 1351 1352 for (i, &elt) in enumerate(&insert) { 1353 assert_eq!(map.len(), i); 1354 map.insert(elt, elt); 1355 assert_eq!(map.len(), i + 1); 1356 assert_eq!(map.get(&elt), Some(&elt)); 1357 assert_eq!(map[&elt], elt); 1358 } 1359 println!("{:?}", map); 1360 1361 for &elt in ¬_present { 1362 assert!(map.get(&elt).is_none()); 1363 } 1364 } 1365 1366 #[test] insert_full()1367 fn insert_full() { 1368 let insert = vec![9, 2, 7, 1, 4, 6, 13]; 1369 let present = vec![1, 6, 2]; 1370 let mut map = IndexMap::with_capacity(insert.len()); 1371 1372 for (i, &elt) in enumerate(&insert) { 1373 assert_eq!(map.len(), i); 1374 let (index, existing) = map.insert_full(elt, elt); 1375 assert_eq!(existing, None); 1376 assert_eq!(Some(index), map.get_full(&elt).map(|x| x.0)); 1377 assert_eq!(map.len(), i + 1); 1378 } 1379 1380 let len = map.len(); 1381 for &elt in &present { 1382 let (index, existing) = map.insert_full(elt, elt); 1383 assert_eq!(existing, Some(elt)); 1384 assert_eq!(Some(index), map.get_full(&elt).map(|x| x.0)); 1385 assert_eq!(map.len(), len); 1386 } 1387 } 1388 1389 #[test] insert_2()1390 fn insert_2() { 1391 let mut map = IndexMap::with_capacity(16); 1392 1393 let mut keys = vec![]; 1394 keys.extend(0..16); 1395 keys.extend(128..267); 1396 1397 for &i in &keys { 1398 let old_map = map.clone(); 1399 map.insert(i, ()); 1400 for key in old_map.keys() { 1401 if map.get(key).is_none() { 1402 println!("old_map: {:?}", old_map); 1403 println!("map: {:?}", map); 1404 panic!("did not find {} in map", key); 1405 } 1406 } 1407 } 1408 1409 for &i in &keys { 1410 assert!(map.get(&i).is_some(), "did not find {}", i); 1411 } 1412 } 1413 1414 #[test] insert_order()1415 fn insert_order() { 1416 let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; 1417 let mut map = IndexMap::new(); 1418 1419 for &elt in &insert { 1420 map.insert(elt, ()); 1421 } 1422 1423 assert_eq!(map.keys().count(), map.len()); 1424 assert_eq!(map.keys().count(), insert.len()); 1425 for (a, b) in insert.iter().zip(map.keys()) { 1426 assert_eq!(a, b); 1427 } 1428 for (i, k) in (0..insert.len()).zip(map.keys()) { 1429 assert_eq!(map.get_index(i).unwrap().0, k); 1430 } 1431 } 1432 1433 #[test] grow()1434 fn grow() { 1435 let insert = [0, 4, 2, 12, 8, 7, 11]; 1436 let not_present = [1, 3, 6, 9, 10]; 1437 let mut map = IndexMap::with_capacity(insert.len()); 1438 1439 for (i, &elt) in enumerate(&insert) { 1440 assert_eq!(map.len(), i); 1441 map.insert(elt, elt); 1442 assert_eq!(map.len(), i + 1); 1443 assert_eq!(map.get(&elt), Some(&elt)); 1444 assert_eq!(map[&elt], elt); 1445 } 1446 1447 println!("{:?}", map); 1448 for &elt in &insert { 1449 map.insert(elt * 10, elt); 1450 } 1451 for &elt in &insert { 1452 map.insert(elt * 100, elt); 1453 } 1454 for (i, &elt) in insert.iter().cycle().enumerate().take(100) { 1455 map.insert(elt * 100 + i as i32, elt); 1456 } 1457 println!("{:?}", map); 1458 for &elt in ¬_present { 1459 assert!(map.get(&elt).is_none()); 1460 } 1461 } 1462 1463 #[test] reserve()1464 fn reserve() { 1465 let mut map = IndexMap::<usize, usize>::new(); 1466 assert_eq!(map.capacity(), 0); 1467 map.reserve(100); 1468 let capacity = map.capacity(); 1469 assert!(capacity >= 100); 1470 for i in 0..capacity { 1471 assert_eq!(map.len(), i); 1472 map.insert(i, i * i); 1473 assert_eq!(map.len(), i + 1); 1474 assert_eq!(map.capacity(), capacity); 1475 assert_eq!(map.get(&i), Some(&(i * i))); 1476 } 1477 map.insert(capacity, std::usize::MAX); 1478 assert_eq!(map.len(), capacity + 1); 1479 assert!(map.capacity() > capacity); 1480 assert_eq!(map.get(&capacity), Some(&std::usize::MAX)); 1481 } 1482 1483 #[test] shrink_to_fit()1484 fn shrink_to_fit() { 1485 let mut map = IndexMap::<usize, usize>::new(); 1486 assert_eq!(map.capacity(), 0); 1487 for i in 0..100 { 1488 assert_eq!(map.len(), i); 1489 map.insert(i, i * i); 1490 assert_eq!(map.len(), i + 1); 1491 assert!(map.capacity() >= i + 1); 1492 assert_eq!(map.get(&i), Some(&(i * i))); 1493 map.shrink_to_fit(); 1494 assert_eq!(map.len(), i + 1); 1495 assert_eq!(map.capacity(), i + 1); 1496 assert_eq!(map.get(&i), Some(&(i * i))); 1497 } 1498 } 1499 1500 #[test] remove()1501 fn remove() { 1502 let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; 1503 let mut map = IndexMap::new(); 1504 1505 for &elt in &insert { 1506 map.insert(elt, elt); 1507 } 1508 1509 assert_eq!(map.keys().count(), map.len()); 1510 assert_eq!(map.keys().count(), insert.len()); 1511 for (a, b) in insert.iter().zip(map.keys()) { 1512 assert_eq!(a, b); 1513 } 1514 1515 let remove_fail = [99, 77]; 1516 let remove = [4, 12, 8, 7]; 1517 1518 for &key in &remove_fail { 1519 assert!(map.swap_remove_full(&key).is_none()); 1520 } 1521 println!("{:?}", map); 1522 for &key in &remove { 1523 //println!("{:?}", map); 1524 let index = map.get_full(&key).unwrap().0; 1525 assert_eq!(map.swap_remove_full(&key), Some((index, key, key))); 1526 } 1527 println!("{:?}", map); 1528 1529 for key in &insert { 1530 assert_eq!(map.get(key).is_some(), !remove.contains(key)); 1531 } 1532 assert_eq!(map.len(), insert.len() - remove.len()); 1533 assert_eq!(map.keys().count(), insert.len() - remove.len()); 1534 } 1535 1536 #[test] remove_to_empty()1537 fn remove_to_empty() { 1538 let mut map = indexmap! { 0 => 0, 4 => 4, 5 => 5 }; 1539 map.swap_remove(&5).unwrap(); 1540 map.swap_remove(&4).unwrap(); 1541 map.swap_remove(&0).unwrap(); 1542 assert!(map.is_empty()); 1543 } 1544 1545 #[test] swap_remove_index()1546 fn swap_remove_index() { 1547 let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; 1548 let mut map = IndexMap::new(); 1549 1550 for &elt in &insert { 1551 map.insert(elt, elt * 2); 1552 } 1553 1554 let mut vector = insert.to_vec(); 1555 let remove_sequence = &[3, 3, 10, 4, 5, 4, 3, 0, 1]; 1556 1557 // check that the same swap remove sequence on vec and map 1558 // have the same result. 1559 for &rm in remove_sequence { 1560 let out_vec = vector.swap_remove(rm); 1561 let (out_map, _) = map.swap_remove_index(rm).unwrap(); 1562 assert_eq!(out_vec, out_map); 1563 } 1564 assert_eq!(vector.len(), map.len()); 1565 for (a, b) in vector.iter().zip(map.keys()) { 1566 assert_eq!(a, b); 1567 } 1568 } 1569 1570 #[test] partial_eq_and_eq()1571 fn partial_eq_and_eq() { 1572 let mut map_a = IndexMap::new(); 1573 map_a.insert(1, "1"); 1574 map_a.insert(2, "2"); 1575 let mut map_b = map_a.clone(); 1576 assert_eq!(map_a, map_b); 1577 map_b.swap_remove(&1); 1578 assert_ne!(map_a, map_b); 1579 1580 let map_c: IndexMap<_, String> = map_b.into_iter().map(|(k, v)| (k, v.into())).collect(); 1581 assert_ne!(map_a, map_c); 1582 assert_ne!(map_c, map_a); 1583 } 1584 1585 #[test] extend()1586 fn extend() { 1587 let mut map = IndexMap::new(); 1588 map.extend(vec![(&1, &2), (&3, &4)]); 1589 map.extend(vec![(5, 6)]); 1590 assert_eq!( 1591 map.into_iter().collect::<Vec<_>>(), 1592 vec![(1, 2), (3, 4), (5, 6)] 1593 ); 1594 } 1595 1596 #[test] entry()1597 fn entry() { 1598 let mut map = IndexMap::new(); 1599 1600 map.insert(1, "1"); 1601 map.insert(2, "2"); 1602 { 1603 let e = map.entry(3); 1604 assert_eq!(e.index(), 2); 1605 let e = e.or_insert("3"); 1606 assert_eq!(e, &"3"); 1607 } 1608 1609 let e = map.entry(2); 1610 assert_eq!(e.index(), 1); 1611 assert_eq!(e.key(), &2); 1612 match e { 1613 Entry::Occupied(ref e) => assert_eq!(e.get(), &"2"), 1614 Entry::Vacant(_) => panic!(), 1615 } 1616 assert_eq!(e.or_insert("4"), &"2"); 1617 } 1618 1619 #[test] entry_and_modify()1620 fn entry_and_modify() { 1621 let mut map = IndexMap::new(); 1622 1623 map.insert(1, "1"); 1624 map.entry(1).and_modify(|x| *x = "2"); 1625 assert_eq!(Some(&"2"), map.get(&1)); 1626 1627 map.entry(2).and_modify(|x| *x = "doesn't exist"); 1628 assert_eq!(None, map.get(&2)); 1629 } 1630 1631 #[test] entry_or_default()1632 fn entry_or_default() { 1633 let mut map = IndexMap::new(); 1634 1635 #[derive(Debug, PartialEq)] 1636 enum TestEnum { 1637 DefaultValue, 1638 NonDefaultValue, 1639 } 1640 1641 impl Default for TestEnum { 1642 fn default() -> Self { 1643 TestEnum::DefaultValue 1644 } 1645 } 1646 1647 map.insert(1, TestEnum::NonDefaultValue); 1648 assert_eq!(&mut TestEnum::NonDefaultValue, map.entry(1).or_default()); 1649 1650 assert_eq!(&mut TestEnum::DefaultValue, map.entry(2).or_default()); 1651 } 1652 1653 #[test] occupied_entry_key()1654 fn occupied_entry_key() { 1655 // These keys match hash and equality, but their addresses are distinct. 1656 let (k1, k2) = (&mut 1, &mut 1); 1657 let k1_ptr = k1 as *const i32; 1658 let k2_ptr = k2 as *const i32; 1659 assert_ne!(k1_ptr, k2_ptr); 1660 1661 let mut map = IndexMap::new(); 1662 map.insert(k1, "value"); 1663 match map.entry(k2) { 1664 Entry::Occupied(ref e) => { 1665 // `OccupiedEntry::key` should reference the key in the map, 1666 // not the key that was used to find the entry. 1667 let ptr = *e.key() as *const i32; 1668 assert_eq!(ptr, k1_ptr); 1669 assert_ne!(ptr, k2_ptr); 1670 } 1671 Entry::Vacant(_) => panic!(), 1672 } 1673 } 1674 1675 #[test] keys()1676 fn keys() { 1677 let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; 1678 let map: IndexMap<_, _> = vec.into_iter().collect(); 1679 let keys: Vec<_> = map.keys().copied().collect(); 1680 assert_eq!(keys.len(), 3); 1681 assert!(keys.contains(&1)); 1682 assert!(keys.contains(&2)); 1683 assert!(keys.contains(&3)); 1684 } 1685 1686 #[test] values()1687 fn values() { 1688 let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; 1689 let map: IndexMap<_, _> = vec.into_iter().collect(); 1690 let values: Vec<_> = map.values().copied().collect(); 1691 assert_eq!(values.len(), 3); 1692 assert!(values.contains(&'a')); 1693 assert!(values.contains(&'b')); 1694 assert!(values.contains(&'c')); 1695 } 1696 1697 #[test] values_mut()1698 fn values_mut() { 1699 let vec = vec![(1, 1), (2, 2), (3, 3)]; 1700 let mut map: IndexMap<_, _> = vec.into_iter().collect(); 1701 for value in map.values_mut() { 1702 *value *= 2 1703 } 1704 let values: Vec<_> = map.values().copied().collect(); 1705 assert_eq!(values.len(), 3); 1706 assert!(values.contains(&2)); 1707 assert!(values.contains(&4)); 1708 assert!(values.contains(&6)); 1709 } 1710 } 1711