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