indexmap/map/core/raw_entry_v1.rs
1//! Opt-in access to the experimental raw entry API.
2//!
3//! This module is designed to mimic the raw entry API of [`HashMap`][std::collections::hash_map],
4//! matching its unstable state as of Rust 1.75. See the tracking issue
5//! [rust#56167](https://github.com/rust-lang/rust/issues/56167) for more details.
6//!
7//! The trait [`RawEntryApiV1`] and the `_v1` suffix on its methods are meant to insulate this for
8//! the future, in case later breaking changes are needed. If the standard library stabilizes its
9//! `hash_raw_entry` feature (or some replacement), matching *inherent* methods will be added to
10//! `IndexMap` without such an opt-in trait.
11
12use super::{IndexMapCore, OccupiedEntry};
13use crate::{Equivalent, HashValue, IndexMap};
14use core::fmt;
15use core::hash::{BuildHasher, Hash};
16use core::marker::PhantomData;
17use core::mem;
18
19/// Opt-in access to the experimental raw entry API.
20///
21/// See the [`raw_entry_v1`][self] module documentation for more information.
22#[expect(private_bounds)]
23pub trait RawEntryApiV1<K, V, S>: Sealed {
24 /// Creates a raw immutable entry builder for the [`IndexMap`].
25 ///
26 /// Raw entries provide the lowest level of control for searching and
27 /// manipulating a map. They must be manually initialized with a hash and
28 /// then manually searched.
29 ///
30 /// This is useful for
31 /// * Hash memoization
32 /// * Using a search key that doesn't work with the [`Equivalent`] trait
33 /// * Using custom comparison logic without newtype wrappers
34 ///
35 /// Unless you are in such a situation, higher-level and more foolproof APIs like
36 /// [`get`][IndexMap::get] should be preferred.
37 ///
38 /// Immutable raw entries have very limited use; you might instead want
39 /// [`raw_entry_mut_v1`][Self::raw_entry_mut_v1].
40 ///
41 /// # Examples
42 ///
43 /// ```
44 /// use core::hash::BuildHasher;
45 /// use indexmap::map::{IndexMap, RawEntryApiV1};
46 ///
47 /// let mut map = IndexMap::new();
48 /// map.extend([("a", 100), ("b", 200), ("c", 300)]);
49 ///
50 /// for k in ["a", "b", "c", "d", "e", "f"] {
51 /// let hash = map.hasher().hash_one(k);
52 /// let i = map.get_index_of(k);
53 /// let v = map.get(k);
54 /// let kv = map.get_key_value(k);
55 /// let ikv = map.get_full(k);
56 ///
57 /// println!("Key: {} and value: {:?}", k, v);
58 ///
59 /// assert_eq!(map.raw_entry_v1().from_key(k), kv);
60 /// assert_eq!(map.raw_entry_v1().from_hash(hash, |q| *q == k), kv);
61 /// assert_eq!(map.raw_entry_v1().from_key_hashed_nocheck(hash, k), kv);
62 /// assert_eq!(map.raw_entry_v1().from_hash_full(hash, |q| *q == k), ikv);
63 /// assert_eq!(map.raw_entry_v1().index_from_hash(hash, |q| *q == k), i);
64 /// }
65 /// ```
66 fn raw_entry_v1(&self) -> RawEntryBuilder<'_, K, V, S>;
67
68 /// Creates a raw entry builder for the [`IndexMap`].
69 ///
70 /// Raw entries provide the lowest level of control for searching and
71 /// manipulating a map. They must be manually initialized with a hash and
72 /// then manually searched. After this, insertions into a vacant entry
73 /// still require an owned key to be provided.
74 ///
75 /// Raw entries are useful for such exotic situations as:
76 ///
77 /// * Hash memoization
78 /// * Deferring the creation of an owned key until it is known to be required
79 /// * Using a search key that doesn't work with the [`Equivalent`] trait
80 /// * Using custom comparison logic without newtype wrappers
81 ///
82 /// Because raw entries provide much more low-level control, it's much easier
83 /// to put the `IndexMap` into an inconsistent state which, while memory-safe,
84 /// will cause the map to produce seemingly random results. Higher-level and more
85 /// foolproof APIs like [`entry`][IndexMap::entry] should be preferred when possible.
86 ///
87 /// Raw entries give mutable access to the keys. This must not be used
88 /// to modify how the key would compare or hash, as the map will not re-evaluate
89 /// where the key should go, meaning the keys may become "lost" if their
90 /// location does not reflect their state. For instance, if you change a key
91 /// so that the map now contains keys which compare equal, search may start
92 /// acting erratically, with two keys randomly masking each other. Implementations
93 /// are free to assume this doesn't happen (within the limits of memory-safety).
94 ///
95 /// # Examples
96 ///
97 /// ```
98 /// use core::hash::BuildHasher;
99 /// use indexmap::map::{IndexMap, RawEntryApiV1};
100 /// use indexmap::map::raw_entry_v1::RawEntryMut;
101 ///
102 /// let mut map = IndexMap::new();
103 /// map.extend([("a", 100), ("b", 200), ("c", 300)]);
104 ///
105 /// // Existing key (insert and update)
106 /// match map.raw_entry_mut_v1().from_key("a") {
107 /// RawEntryMut::Vacant(_) => unreachable!(),
108 /// RawEntryMut::Occupied(mut view) => {
109 /// assert_eq!(view.index(), 0);
110 /// assert_eq!(view.get(), &100);
111 /// let v = view.get_mut();
112 /// let new_v = (*v) * 10;
113 /// *v = new_v;
114 /// assert_eq!(view.insert(1111), 1000);
115 /// }
116 /// }
117 ///
118 /// assert_eq!(map["a"], 1111);
119 /// assert_eq!(map.len(), 3);
120 ///
121 /// // Existing key (take)
122 /// let hash = map.hasher().hash_one("c");
123 /// match map.raw_entry_mut_v1().from_key_hashed_nocheck(hash, "c") {
124 /// RawEntryMut::Vacant(_) => unreachable!(),
125 /// RawEntryMut::Occupied(view) => {
126 /// assert_eq!(view.index(), 2);
127 /// assert_eq!(view.shift_remove_entry(), ("c", 300));
128 /// }
129 /// }
130 /// assert_eq!(map.raw_entry_v1().from_key("c"), None);
131 /// assert_eq!(map.len(), 2);
132 ///
133 /// // Nonexistent key (insert and update)
134 /// let key = "d";
135 /// let hash = map.hasher().hash_one(key);
136 /// match map.raw_entry_mut_v1().from_hash(hash, |q| *q == key) {
137 /// RawEntryMut::Occupied(_) => unreachable!(),
138 /// RawEntryMut::Vacant(view) => {
139 /// assert_eq!(view.index(), 2);
140 /// let (k, value) = view.insert("d", 4000);
141 /// assert_eq!((*k, *value), ("d", 4000));
142 /// *value = 40000;
143 /// }
144 /// }
145 /// assert_eq!(map["d"], 40000);
146 /// assert_eq!(map.len(), 3);
147 ///
148 /// match map.raw_entry_mut_v1().from_hash(hash, |q| *q == key) {
149 /// RawEntryMut::Vacant(_) => unreachable!(),
150 /// RawEntryMut::Occupied(view) => {
151 /// assert_eq!(view.index(), 2);
152 /// assert_eq!(view.swap_remove_entry(), ("d", 40000));
153 /// }
154 /// }
155 /// assert_eq!(map.get("d"), None);
156 /// assert_eq!(map.len(), 2);
157 /// ```
158 fn raw_entry_mut_v1(&mut self) -> RawEntryBuilderMut<'_, K, V, S>;
159}
160
161impl<K, V, S> RawEntryApiV1<K, V, S> for IndexMap<K, V, S> {
162 fn raw_entry_v1(&self) -> RawEntryBuilder<'_, K, V, S> {
163 RawEntryBuilder { map: self }
164 }
165
166 fn raw_entry_mut_v1(&mut self) -> RawEntryBuilderMut<'_, K, V, S> {
167 RawEntryBuilderMut { map: self }
168 }
169}
170
171/// A builder for computing where in an [`IndexMap`] a key-value pair would be stored.
172///
173/// This `struct` is created by the [`IndexMap::raw_entry_v1`] method, provided by the
174/// [`RawEntryApiV1`] trait. See its documentation for more.
175pub struct RawEntryBuilder<'a, K, V, S> {
176 map: &'a IndexMap<K, V, S>,
177}
178
179impl<K, V, S> fmt::Debug for RawEntryBuilder<'_, K, V, S> {
180 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
181 f.debug_struct("RawEntryBuilder").finish_non_exhaustive()
182 }
183}
184
185impl<'a, K, V, S> RawEntryBuilder<'a, K, V, S> {
186 /// Access an entry by key.
187 pub fn from_key<Q>(self, key: &Q) -> Option<(&'a K, &'a V)>
188 where
189 S: BuildHasher,
190 Q: ?Sized + Hash + Equivalent<K>,
191 {
192 self.map.get_key_value(key)
193 }
194
195 /// Access an entry by a key and its hash.
196 pub fn from_key_hashed_nocheck<Q>(self, hash: u64, key: &Q) -> Option<(&'a K, &'a V)>
197 where
198 Q: ?Sized + Equivalent<K>,
199 {
200 let hash = HashValue(hash as usize);
201 let i = self.map.core.get_index_of(hash, key)?;
202 self.map.get_index(i)
203 }
204
205 /// Access an entry by hash.
206 pub fn from_hash<F>(self, hash: u64, is_match: F) -> Option<(&'a K, &'a V)>
207 where
208 F: FnMut(&K) -> bool,
209 {
210 let map = self.map;
211 let i = self.index_from_hash(hash, is_match)?;
212 map.get_index(i)
213 }
214
215 /// Access an entry by hash, including its index.
216 pub fn from_hash_full<F>(self, hash: u64, is_match: F) -> Option<(usize, &'a K, &'a V)>
217 where
218 F: FnMut(&K) -> bool,
219 {
220 let map = self.map;
221 let i = self.index_from_hash(hash, is_match)?;
222 let (key, value) = map.get_index(i)?;
223 Some((i, key, value))
224 }
225
226 /// Access the index of an entry by hash.
227 pub fn index_from_hash<F>(self, hash: u64, mut is_match: F) -> Option<usize>
228 where
229 F: FnMut(&K) -> bool,
230 {
231 let hash = HashValue(hash as usize);
232 let entries = &*self.map.core.entries;
233 let eq = move |&i: &usize| is_match(&entries[i].key);
234 self.map.core.indices.find(hash.get(), eq).copied()
235 }
236}
237
238/// A builder for computing where in an [`IndexMap`] a key-value pair would be stored.
239///
240/// This `struct` is created by the [`IndexMap::raw_entry_mut_v1`] method, provided by the
241/// [`RawEntryApiV1`] trait. See its documentation for more.
242pub struct RawEntryBuilderMut<'a, K, V, S> {
243 map: &'a mut IndexMap<K, V, S>,
244}
245
246impl<K, V, S> fmt::Debug for RawEntryBuilderMut<'_, K, V, S> {
247 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
248 f.debug_struct("RawEntryBuilderMut").finish_non_exhaustive()
249 }
250}
251
252impl<'a, K, V, S> RawEntryBuilderMut<'a, K, V, S> {
253 /// Access an entry by key.
254 pub fn from_key<Q>(self, key: &Q) -> RawEntryMut<'a, K, V, S>
255 where
256 S: BuildHasher,
257 Q: ?Sized + Hash + Equivalent<K>,
258 {
259 let hash = self.map.hash(key);
260 self.from_key_hashed_nocheck(hash.get(), key)
261 }
262
263 /// Access an entry by a key and its hash.
264 pub fn from_key_hashed_nocheck<Q>(self, hash: u64, key: &Q) -> RawEntryMut<'a, K, V, S>
265 where
266 Q: ?Sized + Equivalent<K>,
267 {
268 self.from_hash(hash, |k| Q::equivalent(key, k))
269 }
270
271 /// Access an entry by hash.
272 pub fn from_hash<F>(self, hash: u64, is_match: F) -> RawEntryMut<'a, K, V, S>
273 where
274 F: FnMut(&K) -> bool,
275 {
276 match OccupiedEntry::from_hash(&mut self.map.core, hash, is_match) {
277 Ok(inner) => RawEntryMut::Occupied(RawOccupiedEntryMut {
278 inner,
279 hash_builder: PhantomData,
280 }),
281 Err(map) => RawEntryMut::Vacant(RawVacantEntryMut {
282 map,
283 hash_builder: &self.map.hash_builder,
284 }),
285 }
286 }
287}
288
289/// Raw entry for an existing key-value pair or a vacant location to
290/// insert one.
291pub enum RawEntryMut<'a, K, V, S> {
292 /// Existing slot with equivalent key.
293 Occupied(RawOccupiedEntryMut<'a, K, V, S>),
294 /// Vacant slot (no equivalent key in the map).
295 Vacant(RawVacantEntryMut<'a, K, V, S>),
296}
297
298impl<K: fmt::Debug, V: fmt::Debug, S> fmt::Debug for RawEntryMut<'_, K, V, S> {
299 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
300 let mut tuple = f.debug_tuple("RawEntryMut");
301 match self {
302 Self::Vacant(v) => tuple.field(v),
303 Self::Occupied(o) => tuple.field(o),
304 };
305 tuple.finish()
306 }
307}
308
309impl<'a, K, V, S> RawEntryMut<'a, K, V, S> {
310 /// Return the index where the key-value pair exists or may be inserted.
311 #[inline]
312 pub fn index(&self) -> usize {
313 match self {
314 Self::Occupied(entry) => entry.index(),
315 Self::Vacant(entry) => entry.index(),
316 }
317 }
318
319 /// Inserts the given default key and value in the entry if it is vacant and returns mutable
320 /// references to them. Otherwise mutable references to an already existent pair are returned.
321 pub fn or_insert(self, default_key: K, default_value: V) -> (&'a mut K, &'a mut V)
322 where
323 K: Hash,
324 S: BuildHasher,
325 {
326 match self {
327 Self::Occupied(entry) => entry.into_key_value_mut(),
328 Self::Vacant(entry) => entry.insert(default_key, default_value),
329 }
330 }
331
332 /// Inserts the result of the `call` function in the entry if it is vacant and returns mutable
333 /// references to them. Otherwise mutable references to an already existent pair are returned.
334 pub fn or_insert_with<F>(self, call: F) -> (&'a mut K, &'a mut V)
335 where
336 F: FnOnce() -> (K, V),
337 K: Hash,
338 S: BuildHasher,
339 {
340 match self {
341 Self::Occupied(entry) => entry.into_key_value_mut(),
342 Self::Vacant(entry) => {
343 let (key, value) = call();
344 entry.insert(key, value)
345 }
346 }
347 }
348
349 /// Modifies the entry if it is occupied.
350 pub fn and_modify<F>(mut self, f: F) -> Self
351 where
352 F: FnOnce(&mut K, &mut V),
353 {
354 if let Self::Occupied(entry) = &mut self {
355 let (k, v) = entry.get_key_value_mut();
356 f(k, v);
357 }
358 self
359 }
360}
361
362/// A raw view into an occupied entry in an [`IndexMap`].
363/// It is part of the [`RawEntryMut`] enum.
364pub struct RawOccupiedEntryMut<'a, K, V, S> {
365 inner: OccupiedEntry<'a, K, V>,
366 hash_builder: PhantomData<&'a S>,
367}
368
369impl<K: fmt::Debug, V: fmt::Debug, S> fmt::Debug for RawOccupiedEntryMut<'_, K, V, S> {
370 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
371 f.debug_struct("RawOccupiedEntryMut")
372 .field("key", self.key())
373 .field("value", self.get())
374 .finish_non_exhaustive()
375 }
376}
377
378impl<'a, K, V, S> RawOccupiedEntryMut<'a, K, V, S> {
379 /// Return the index of the key-value pair
380 #[inline]
381 pub fn index(&self) -> usize {
382 self.inner.index()
383 }
384
385 /// Gets a reference to the entry's key in the map.
386 ///
387 /// Note that this is not the key that was used to find the entry. There may be an observable
388 /// difference if the key type has any distinguishing features outside of `Hash` and `Eq`, like
389 /// extra fields or the memory address of an allocation.
390 pub fn key(&self) -> &K {
391 self.inner.key()
392 }
393
394 /// Gets a mutable reference to the entry's key in the map.
395 ///
396 /// Note that this is not the key that was used to find the entry. There may be an observable
397 /// difference if the key type has any distinguishing features outside of `Hash` and `Eq`, like
398 /// extra fields or the memory address of an allocation.
399 pub fn key_mut(&mut self) -> &mut K {
400 &mut self.inner.get_bucket_mut().key
401 }
402
403 /// Converts into a mutable reference to the entry's key in the map,
404 /// with a lifetime bound to the map itself.
405 ///
406 /// Note that this is not the key that was used to find the entry. There may be an observable
407 /// difference if the key type has any distinguishing features outside of `Hash` and `Eq`, like
408 /// extra fields or the memory address of an allocation.
409 pub fn into_key(self) -> &'a mut K {
410 &mut self.inner.into_bucket().key
411 }
412
413 /// Gets a reference to the entry's value in the map.
414 pub fn get(&self) -> &V {
415 self.inner.get()
416 }
417
418 /// Gets a mutable reference to the entry's value in the map.
419 ///
420 /// If you need a reference which may outlive the destruction of the
421 /// [`RawEntryMut`] value, see [`into_mut`][Self::into_mut].
422 pub fn get_mut(&mut self) -> &mut V {
423 self.inner.get_mut()
424 }
425
426 /// Converts into a mutable reference to the entry's value in the map,
427 /// with a lifetime bound to the map itself.
428 pub fn into_mut(self) -> &'a mut V {
429 self.inner.into_mut()
430 }
431
432 /// Gets a reference to the entry's key and value in the map.
433 pub fn get_key_value(&self) -> (&K, &V) {
434 self.inner.get_bucket().refs()
435 }
436
437 /// Gets a reference to the entry's key and value in the map.
438 pub fn get_key_value_mut(&mut self) -> (&mut K, &mut V) {
439 self.inner.get_bucket_mut().muts()
440 }
441
442 /// Converts into a mutable reference to the entry's key and value in the map,
443 /// with a lifetime bound to the map itself.
444 pub fn into_key_value_mut(self) -> (&'a mut K, &'a mut V) {
445 self.inner.into_bucket().muts()
446 }
447
448 /// Sets the value of the entry, and returns the entry's old value.
449 pub fn insert(&mut self, value: V) -> V {
450 self.inner.insert(value)
451 }
452
453 /// Sets the key of the entry, and returns the entry's old key.
454 pub fn insert_key(&mut self, key: K) -> K {
455 mem::replace(self.key_mut(), key)
456 }
457
458 /// Remove the key, value pair stored in the map for this entry, and return the value.
459 ///
460 /// **NOTE:** This is equivalent to [`.swap_remove()`][Self::swap_remove], replacing this
461 /// entry's position with the last element, and it is deprecated in favor of calling that
462 /// explicitly. If you need to preserve the relative order of the keys in the map, use
463 /// [`.shift_remove()`][Self::shift_remove] instead.
464 #[deprecated(note = "`remove` disrupts the map order -- \
465 use `swap_remove` or `shift_remove` for explicit behavior.")]
466 pub fn remove(self) -> V {
467 self.swap_remove()
468 }
469
470 /// Remove the key, value pair stored in the map for this entry, and return the value.
471 ///
472 /// Like [`Vec::swap_remove`][alloc::vec::Vec::swap_remove], the pair is removed by swapping it
473 /// with the last element of the map and popping it off.
474 /// **This perturbs the position of what used to be the last element!**
475 ///
476 /// Computes in **O(1)** time (average).
477 pub fn swap_remove(self) -> V {
478 self.inner.swap_remove()
479 }
480
481 /// Remove the key, value pair stored in the map for this entry, and return the value.
482 ///
483 /// Like [`Vec::remove`][alloc::vec::Vec::remove], the pair is removed by shifting all of the
484 /// elements that follow it, preserving their relative order.
485 /// **This perturbs the index of all of those elements!**
486 ///
487 /// Computes in **O(n)** time (average).
488 pub fn shift_remove(self) -> V {
489 self.inner.shift_remove()
490 }
491
492 /// Remove and return the key, value pair stored in the map for this entry
493 ///
494 /// **NOTE:** This is equivalent to [`.swap_remove_entry()`][Self::swap_remove_entry],
495 /// replacing this entry's position with the last element, and it is deprecated in favor of
496 /// calling that explicitly. If you need to preserve the relative order of the keys in the map,
497 /// use [`.shift_remove_entry()`][Self::shift_remove_entry] instead.
498 #[deprecated(note = "`remove_entry` disrupts the map order -- \
499 use `swap_remove_entry` or `shift_remove_entry` for explicit behavior.")]
500 pub fn remove_entry(self) -> (K, V) {
501 self.swap_remove_entry()
502 }
503
504 /// Remove and return the key, value pair stored in the map for this entry
505 ///
506 /// Like [`Vec::swap_remove`][alloc::vec::Vec::swap_remove], the pair is removed by swapping it
507 /// with the last element of the map and popping it off.
508 /// **This perturbs the position of what used to be the last element!**
509 ///
510 /// Computes in **O(1)** time (average).
511 pub fn swap_remove_entry(self) -> (K, V) {
512 self.inner.swap_remove_entry()
513 }
514
515 /// Remove and return the key, value pair stored in the map for this entry
516 ///
517 /// Like [`Vec::remove`][alloc::vec::Vec::remove], the pair is removed by shifting all of the
518 /// elements that follow it, preserving their relative order.
519 /// **This perturbs the index of all of those elements!**
520 ///
521 /// Computes in **O(n)** time (average).
522 pub fn shift_remove_entry(self) -> (K, V) {
523 self.inner.shift_remove_entry()
524 }
525
526 /// Moves the position of the entry to a new index
527 /// by shifting all other entries in-between.
528 ///
529 /// This is equivalent to [`IndexMap::move_index`]
530 /// coming `from` the current [`.index()`][Self::index].
531 ///
532 /// * If `self.index() < to`, the other pairs will shift down while the targeted pair moves up.
533 /// * If `self.index() > to`, the other pairs will shift up while the targeted pair moves down.
534 ///
535 /// ***Panics*** if `to` is out of bounds.
536 ///
537 /// Computes in **O(n)** time (average).
538 #[track_caller]
539 pub fn move_index(self, to: usize) {
540 self.inner.move_index(to);
541 }
542
543 /// Swaps the position of entry with another.
544 ///
545 /// This is equivalent to [`IndexMap::swap_indices`]
546 /// with the current [`.index()`][Self::index] as one of the two being swapped.
547 ///
548 /// ***Panics*** if the `other` index is out of bounds.
549 ///
550 /// Computes in **O(1)** time (average).
551 #[track_caller]
552 pub fn swap_indices(self, other: usize) {
553 self.inner.swap_indices(other);
554 }
555}
556
557/// A view into a vacant raw entry in an [`IndexMap`].
558/// It is part of the [`RawEntryMut`] enum.
559pub struct RawVacantEntryMut<'a, K, V, S> {
560 map: &'a mut IndexMapCore<K, V>,
561 hash_builder: &'a S,
562}
563
564impl<K, V, S> fmt::Debug for RawVacantEntryMut<'_, K, V, S> {
565 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
566 f.debug_struct("RawVacantEntryMut").finish_non_exhaustive()
567 }
568}
569
570impl<'a, K, V, S> RawVacantEntryMut<'a, K, V, S> {
571 /// Return the index where a key-value pair may be inserted.
572 pub fn index(&self) -> usize {
573 self.map.len()
574 }
575
576 /// Inserts the given key and value into the map,
577 /// and returns mutable references to them.
578 pub fn insert(self, key: K, value: V) -> (&'a mut K, &'a mut V)
579 where
580 K: Hash,
581 S: BuildHasher,
582 {
583 let h = self.hash_builder.hash_one(&key);
584 self.insert_hashed_nocheck(h, key, value)
585 }
586
587 /// Inserts the given key and value into the map with the provided hash,
588 /// and returns mutable references to them.
589 pub fn insert_hashed_nocheck(self, hash: u64, key: K, value: V) -> (&'a mut K, &'a mut V) {
590 let hash = HashValue(hash as usize);
591 self.map.insert_unique(hash, key, value).muts()
592 }
593
594 /// Inserts the given key and value into the map at the given index,
595 /// shifting others to the right, and returns mutable references to them.
596 ///
597 /// ***Panics*** if `index` is out of bounds.
598 ///
599 /// Computes in **O(n)** time (average).
600 #[track_caller]
601 pub fn shift_insert(self, index: usize, key: K, value: V) -> (&'a mut K, &'a mut V)
602 where
603 K: Hash,
604 S: BuildHasher,
605 {
606 let h = self.hash_builder.hash_one(&key);
607 self.shift_insert_hashed_nocheck(index, h, key, value)
608 }
609
610 /// Inserts the given key and value into the map with the provided hash
611 /// at the given index, and returns mutable references to them.
612 ///
613 /// ***Panics*** if `index` is out of bounds.
614 ///
615 /// Computes in **O(n)** time (average).
616 #[track_caller]
617 pub fn shift_insert_hashed_nocheck(
618 self,
619 index: usize,
620 hash: u64,
621 key: K,
622 value: V,
623 ) -> (&'a mut K, &'a mut V) {
624 let hash = HashValue(hash as usize);
625 self.map.shift_insert_unique(index, hash, key, value);
626 self.map.entries[index].muts()
627 }
628}
629
630trait Sealed {}
631
632impl<K, V, S> Sealed for IndexMap<K, V, S> {}