indexmap/map/
iter.rs

1use alloc::vec::{self, Vec};
2use core::{
3    fmt,
4    hash::{BuildHasher, Hash},
5    iter::FusedIterator,
6    mem::MaybeUninit,
7    ops::{Index, RangeBounds},
8    slice,
9};
10
11use super::{Bucket, HashValue, IndexMap, Slice};
12use crate::inner::{Core, ExtractCore};
13
14impl<'a, K, V, S> IntoIterator for &'a IndexMap<K, V, S> {
15    type Item = (&'a K, &'a V);
16    type IntoIter = Iter<'a, K, V>;
17
18    fn into_iter(self) -> Self::IntoIter {
19        self.iter()
20    }
21}
22
23impl<'a, K, V, S> IntoIterator for &'a mut IndexMap<K, V, S> {
24    type Item = (&'a K, &'a mut V);
25    type IntoIter = IterMut<'a, K, V>;
26
27    fn into_iter(self) -> Self::IntoIter {
28        self.iter_mut()
29    }
30}
31
32impl<K, V, S> IntoIterator for IndexMap<K, V, S> {
33    type Item = (K, V);
34    type IntoIter = IntoIter<K, V>;
35
36    fn into_iter(self) -> Self::IntoIter {
37        IntoIter::new(self.into_entries())
38    }
39}
40
41/// An iterator over the entries of an [`IndexMap`].
42///
43/// This `struct` is created by the [`IndexMap::iter`] method.
44/// See its documentation for more.
45pub struct Iter<'a, K, V> {
46    iter: slice::Iter<'a, Bucket<K, V>>,
47}
48
49impl<'a, K, V> Iter<'a, K, V> {
50    pub(super) fn new(entries: &'a [Bucket<K, V>]) -> Self {
51        Self {
52            iter: entries.iter(),
53        }
54    }
55
56    /// Returns a slice of the remaining entries in the iterator.
57    pub fn as_slice(&self) -> &'a Slice<K, V> {
58        Slice::from_slice(self.iter.as_slice())
59    }
60}
61
62impl<'a, K, V> Iterator for Iter<'a, K, V> {
63    type Item = (&'a K, &'a V);
64
65    iterator_methods!(Bucket::refs);
66}
67
68impl<K, V> DoubleEndedIterator for Iter<'_, K, V> {
69    double_ended_iterator_methods!(Bucket::refs);
70}
71
72impl<K, V> ExactSizeIterator for Iter<'_, K, V> {
73    fn len(&self) -> usize {
74        self.iter.len()
75    }
76}
77
78impl<K, V> FusedIterator for Iter<'_, K, V> {}
79
80// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
81impl<K, V> Clone for Iter<'_, K, V> {
82    fn clone(&self) -> Self {
83        Iter {
84            iter: self.iter.clone(),
85        }
86    }
87}
88
89impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Iter<'_, K, V> {
90    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
91        f.debug_list().entries(self.clone()).finish()
92    }
93}
94
95impl<K, V> Default for Iter<'_, K, V> {
96    fn default() -> Self {
97        Self {
98            iter: [].iter(),
99        }
100    }
101}
102
103/// A mutable iterator over the entries of an [`IndexMap`].
104///
105/// This `struct` is created by the [`IndexMap::iter_mut`] method.
106/// See its documentation for more.
107pub struct IterMut<'a, K, V> {
108    iter: slice::IterMut<'a, Bucket<K, V>>,
109}
110
111impl<'a, K, V> IterMut<'a, K, V> {
112    pub(super) fn new(entries: &'a mut [Bucket<K, V>]) -> Self {
113        Self {
114            iter: entries.iter_mut(),
115        }
116    }
117
118    /// Returns a slice of the remaining entries in the iterator.
119    pub fn as_slice(&self) -> &Slice<K, V> {
120        Slice::from_slice(self.iter.as_slice())
121    }
122
123    /// Returns a mutable slice of the remaining entries in the iterator.
124    ///
125    /// To avoid creating `&mut` references that alias, this is forced to consume the iterator.
126    pub fn into_slice(self) -> &'a mut Slice<K, V> {
127        Slice::from_mut_slice(self.iter.into_slice())
128    }
129}
130
131impl<'a, K, V> Iterator for IterMut<'a, K, V> {
132    type Item = (&'a K, &'a mut V);
133
134    iterator_methods!(Bucket::ref_mut);
135}
136
137impl<K, V> DoubleEndedIterator for IterMut<'_, K, V> {
138    double_ended_iterator_methods!(Bucket::ref_mut);
139}
140
141impl<K, V> ExactSizeIterator for IterMut<'_, K, V> {
142    fn len(&self) -> usize {
143        self.iter.len()
144    }
145}
146
147impl<K, V> FusedIterator for IterMut<'_, K, V> {}
148
149impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IterMut<'_, K, V> {
150    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
151        let iter = self.iter.as_slice().iter().map(Bucket::refs);
152        f.debug_list().entries(iter).finish()
153    }
154}
155
156impl<K, V> Default for IterMut<'_, K, V> {
157    fn default() -> Self {
158        Self {
159            iter: [].iter_mut(),
160        }
161    }
162}
163
164/// A mutable iterator over the entries of an [`IndexMap`].
165///
166/// This `struct` is created by the [`MutableKeys::iter_mut2`][super::MutableKeys::iter_mut2] method.
167/// See its documentation for more.
168pub struct IterMut2<'a, K, V> {
169    iter: slice::IterMut<'a, Bucket<K, V>>,
170}
171
172impl<'a, K, V> IterMut2<'a, K, V> {
173    pub(super) fn new(entries: &'a mut [Bucket<K, V>]) -> Self {
174        Self {
175            iter: entries.iter_mut(),
176        }
177    }
178
179    /// Returns a slice of the remaining entries in the iterator.
180    pub fn as_slice(&self) -> &Slice<K, V> {
181        Slice::from_slice(self.iter.as_slice())
182    }
183
184    /// Returns a mutable slice of the remaining entries in the iterator.
185    ///
186    /// To avoid creating `&mut` references that alias, this is forced to consume the iterator.
187    pub fn into_slice(self) -> &'a mut Slice<K, V> {
188        Slice::from_mut_slice(self.iter.into_slice())
189    }
190}
191
192impl<'a, K, V> Iterator for IterMut2<'a, K, V> {
193    type Item = (&'a mut K, &'a mut V);
194
195    iterator_methods!(Bucket::muts);
196}
197
198impl<K, V> DoubleEndedIterator for IterMut2<'_, K, V> {
199    double_ended_iterator_methods!(Bucket::muts);
200}
201
202impl<K, V> ExactSizeIterator for IterMut2<'_, K, V> {
203    fn len(&self) -> usize {
204        self.iter.len()
205    }
206}
207
208impl<K, V> FusedIterator for IterMut2<'_, K, V> {}
209
210impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IterMut2<'_, K, V> {
211    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
212        let iter = self.iter.as_slice().iter().map(Bucket::refs);
213        f.debug_list().entries(iter).finish()
214    }
215}
216
217impl<K, V> Default for IterMut2<'_, K, V> {
218    fn default() -> Self {
219        Self {
220            iter: [].iter_mut(),
221        }
222    }
223}
224
225/// An owning iterator over the entries of an [`IndexMap`].
226///
227/// This `struct` is created by the [`IndexMap::into_iter`] method
228/// (provided by the [`IntoIterator`] trait). See its documentation for more.
229#[derive(Clone)]
230pub struct IntoIter<K, V> {
231    iter: vec::IntoIter<Bucket<K, V>>,
232}
233
234impl<K, V> IntoIter<K, V> {
235    pub(super) fn new(entries: Vec<Bucket<K, V>>) -> Self {
236        Self {
237            iter: entries.into_iter(),
238        }
239    }
240
241    /// Returns a slice of the remaining entries in the iterator.
242    pub fn as_slice(&self) -> &Slice<K, V> {
243        Slice::from_slice(self.iter.as_slice())
244    }
245
246    /// Returns a mutable slice of the remaining entries in the iterator.
247    pub fn as_mut_slice(&mut self) -> &mut Slice<K, V> {
248        Slice::from_mut_slice(self.iter.as_mut_slice())
249    }
250}
251
252impl<K, V> Iterator for IntoIter<K, V> {
253    type Item = (K, V);
254
255    iterator_methods!(Bucket::key_value);
256}
257
258impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
259    double_ended_iterator_methods!(Bucket::key_value);
260}
261
262impl<K, V> ExactSizeIterator for IntoIter<K, V> {
263    fn len(&self) -> usize {
264        self.iter.len()
265    }
266}
267
268impl<K, V> FusedIterator for IntoIter<K, V> {}
269
270impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IntoIter<K, V> {
271    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
272        let iter = self.iter.as_slice().iter().map(Bucket::refs);
273        f.debug_list().entries(iter).finish()
274    }
275}
276
277impl<K, V> Default for IntoIter<K, V> {
278    fn default() -> Self {
279        Self {
280            iter: Vec::new().into_iter(),
281        }
282    }
283}
284
285/// A draining iterator over the entries of an [`IndexMap`].
286///
287/// This `struct` is created by the [`IndexMap::drain`] method.
288/// See its documentation for more.
289pub struct Drain<'a, K, V> {
290    iter: vec::Drain<'a, Bucket<K, V>>,
291}
292
293impl<'a, K, V> Drain<'a, K, V> {
294    pub(super) fn new(iter: vec::Drain<'a, Bucket<K, V>>) -> Self {
295        Self {
296            iter,
297        }
298    }
299
300    /// Returns a slice of the remaining entries in the iterator.
301    pub fn as_slice(&self) -> &Slice<K, V> {
302        Slice::from_slice(self.iter.as_slice())
303    }
304}
305
306impl<K, V> Iterator for Drain<'_, K, V> {
307    type Item = (K, V);
308
309    iterator_methods!(Bucket::key_value);
310}
311
312impl<K, V> DoubleEndedIterator for Drain<'_, K, V> {
313    double_ended_iterator_methods!(Bucket::key_value);
314}
315
316impl<K, V> ExactSizeIterator for Drain<'_, K, V> {
317    fn len(&self) -> usize {
318        self.iter.len()
319    }
320}
321
322impl<K, V> FusedIterator for Drain<'_, K, V> {}
323
324impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Drain<'_, K, V> {
325    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
326        let iter = self.iter.as_slice().iter().map(Bucket::refs);
327        f.debug_list().entries(iter).finish()
328    }
329}
330
331/// An iterator over the keys of an [`IndexMap`].
332///
333/// This `struct` is created by the [`IndexMap::keys`] method.
334/// See its documentation for more.
335pub struct Keys<'a, K, V> {
336    iter: slice::Iter<'a, Bucket<K, V>>,
337}
338
339impl<'a, K, V> Keys<'a, K, V> {
340    pub(super) fn new(entries: &'a [Bucket<K, V>]) -> Self {
341        Self {
342            iter: entries.iter(),
343        }
344    }
345}
346
347impl<'a, K, V> Iterator for Keys<'a, K, V> {
348    type Item = &'a K;
349
350    iterator_methods!(Bucket::key_ref);
351}
352
353impl<K, V> DoubleEndedIterator for Keys<'_, K, V> {
354    double_ended_iterator_methods!(Bucket::key_ref);
355}
356
357impl<K, V> ExactSizeIterator for Keys<'_, K, V> {
358    fn len(&self) -> usize {
359        self.iter.len()
360    }
361}
362
363impl<K, V> FusedIterator for Keys<'_, K, V> {}
364
365// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
366impl<K, V> Clone for Keys<'_, K, V> {
367    fn clone(&self) -> Self {
368        Keys {
369            iter: self.iter.clone(),
370        }
371    }
372}
373
374impl<K: fmt::Debug, V> fmt::Debug for Keys<'_, K, V> {
375    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
376        f.debug_list().entries(self.clone()).finish()
377    }
378}
379
380impl<K, V> Default for Keys<'_, K, V> {
381    fn default() -> Self {
382        Self {
383            iter: [].iter(),
384        }
385    }
386}
387
388/// Access [`IndexMap`] keys at indexed positions.
389///
390/// While [`Index<usize> for IndexMap`][values] accesses a map's values,
391/// indexing through [`IndexMap::keys`] offers an alternative to access a map's
392/// keys instead.
393///
394/// [values]: IndexMap#impl-Index<usize>-for-IndexMap<K,+V,+S>
395///
396/// Since `Keys` is also an iterator, consuming items from the iterator will
397/// offset the effective indices. Similarly, if `Keys` is obtained from
398/// [`Slice::keys`], indices will be interpreted relative to the position of
399/// that slice.
400///
401/// # Examples
402///
403/// ```
404/// use indexmap::IndexMap;
405///
406/// let mut map = IndexMap::new();
407/// for word in "Lorem ipsum dolor sit amet".split_whitespace() {
408///     map.insert(word.to_lowercase(), word.to_uppercase());
409/// }
410///
411/// assert_eq!(map[0], "LOREM");
412/// assert_eq!(map.keys()[0], "lorem");
413/// assert_eq!(map[1], "IPSUM");
414/// assert_eq!(map.keys()[1], "ipsum");
415///
416/// map.reverse();
417/// assert_eq!(map.keys()[0], "amet");
418/// assert_eq!(map.keys()[1], "sit");
419///
420/// map.sort_keys();
421/// assert_eq!(map.keys()[0], "amet");
422/// assert_eq!(map.keys()[1], "dolor");
423///
424/// // Advancing the iterator will offset the indexing
425/// let mut keys = map.keys();
426/// assert_eq!(keys[0], "amet");
427/// assert_eq!(keys.next().map(|s| &**s), Some("amet"));
428/// assert_eq!(keys[0], "dolor");
429/// assert_eq!(keys[1], "ipsum");
430///
431/// // Slices may have an offset as well
432/// let slice = &map[2..];
433/// assert_eq!(slice[0], "IPSUM");
434/// assert_eq!(slice.keys()[0], "ipsum");
435/// ```
436///
437/// ```should_panic
438/// use indexmap::IndexMap;
439///
440/// let mut map = IndexMap::new();
441/// map.insert("foo", 1);
442/// println!("{:?}", map.keys()[10]); // panics!
443/// ```
444impl<K, V> Index<usize> for Keys<'_, K, V> {
445    type Output = K;
446
447    /// Returns a reference to the key at the supplied `index`.
448    ///
449    /// ***Panics*** if `index` is out of bounds.
450    fn index(&self, index: usize) -> &K {
451        &self.iter.as_slice()[index].key
452    }
453}
454
455/// An owning iterator over the keys of an [`IndexMap`].
456///
457/// This `struct` is created by the [`IndexMap::into_keys`] method.
458/// See its documentation for more.
459pub struct IntoKeys<K, V> {
460    // We eagerly drop the values during construction so we can ignore them in
461    // `Clone`, but we keep uninit values so the bucket's size and alignment
462    // remain the same, and therefore the `Vec` conversion should be in-place.
463    iter: vec::IntoIter<Bucket<K, MaybeUninit<V>>>,
464}
465
466impl<K, V> IntoKeys<K, V> {
467    pub(super) fn new(entries: Vec<Bucket<K, V>>) -> Self {
468        // The original values will be dropped here.
469        // The hash doesn't matter, but "copying" it in-place is free.
470        let entries = entries
471            .into_iter()
472            .map(
473                |Bucket {
474                     hash,
475                     key,
476                     ..
477                 }| Bucket {
478                    hash,
479                    key,
480                    value: MaybeUninit::uninit(),
481                },
482            )
483            .collect::<Vec<_>>();
484        Self {
485            iter: entries.into_iter(),
486        }
487    }
488}
489
490impl<K: Clone, V> Clone for IntoKeys<K, V> {
491    fn clone(&self) -> Self {
492        let entries = self
493            .iter
494            .as_slice()
495            .iter()
496            .map(
497                |Bucket {
498                     key, ..
499                 }| Bucket {
500                    hash: HashValue(0),
501                    key: key.clone(),
502                    value: MaybeUninit::uninit(),
503                },
504            )
505            .collect::<Vec<_>>();
506        Self {
507            iter: entries.into_iter(),
508        }
509    }
510}
511
512impl<K, V> Iterator for IntoKeys<K, V> {
513    type Item = K;
514
515    iterator_methods!(Bucket::key);
516}
517
518impl<K, V> DoubleEndedIterator for IntoKeys<K, V> {
519    double_ended_iterator_methods!(Bucket::key);
520}
521
522impl<K, V> ExactSizeIterator for IntoKeys<K, V> {
523    fn len(&self) -> usize {
524        self.iter.len()
525    }
526}
527
528impl<K, V> FusedIterator for IntoKeys<K, V> {}
529
530impl<K: fmt::Debug, V> fmt::Debug for IntoKeys<K, V> {
531    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
532        let iter = self.iter.as_slice().iter().map(Bucket::key_ref);
533        f.debug_list().entries(iter).finish()
534    }
535}
536
537impl<K, V> Default for IntoKeys<K, V> {
538    fn default() -> Self {
539        Self {
540            iter: Vec::new().into_iter(),
541        }
542    }
543}
544
545/// An iterator over the values of an [`IndexMap`].
546///
547/// This `struct` is created by the [`IndexMap::values`] method.
548/// See its documentation for more.
549pub struct Values<'a, K, V> {
550    iter: slice::Iter<'a, Bucket<K, V>>,
551}
552
553impl<'a, K, V> Values<'a, K, V> {
554    pub(super) fn new(entries: &'a [Bucket<K, V>]) -> Self {
555        Self {
556            iter: entries.iter(),
557        }
558    }
559}
560
561impl<'a, K, V> Iterator for Values<'a, K, V> {
562    type Item = &'a V;
563
564    iterator_methods!(Bucket::value_ref);
565}
566
567impl<K, V> DoubleEndedIterator for Values<'_, K, V> {
568    double_ended_iterator_methods!(Bucket::value_ref);
569}
570
571impl<K, V> ExactSizeIterator for Values<'_, K, V> {
572    fn len(&self) -> usize {
573        self.iter.len()
574    }
575}
576
577impl<K, V> FusedIterator for Values<'_, K, V> {}
578
579// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
580impl<K, V> Clone for Values<'_, K, V> {
581    fn clone(&self) -> Self {
582        Values {
583            iter: self.iter.clone(),
584        }
585    }
586}
587
588impl<K, V: fmt::Debug> fmt::Debug for Values<'_, K, V> {
589    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
590        f.debug_list().entries(self.clone()).finish()
591    }
592}
593
594impl<K, V> Default for Values<'_, K, V> {
595    fn default() -> Self {
596        Self {
597            iter: [].iter(),
598        }
599    }
600}
601
602/// A mutable iterator over the values of an [`IndexMap`].
603///
604/// This `struct` is created by the [`IndexMap::values_mut`] method.
605/// See its documentation for more.
606pub struct ValuesMut<'a, K, V> {
607    iter: slice::IterMut<'a, Bucket<K, V>>,
608}
609
610impl<'a, K, V> ValuesMut<'a, K, V> {
611    pub(super) fn new(entries: &'a mut [Bucket<K, V>]) -> Self {
612        Self {
613            iter: entries.iter_mut(),
614        }
615    }
616}
617
618impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
619    type Item = &'a mut V;
620
621    iterator_methods!(Bucket::value_mut);
622}
623
624impl<K, V> DoubleEndedIterator for ValuesMut<'_, K, V> {
625    double_ended_iterator_methods!(Bucket::value_mut);
626}
627
628impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> {
629    fn len(&self) -> usize {
630        self.iter.len()
631    }
632}
633
634impl<K, V> FusedIterator for ValuesMut<'_, K, V> {}
635
636impl<K, V: fmt::Debug> fmt::Debug for ValuesMut<'_, K, V> {
637    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
638        let iter = self.iter.as_slice().iter().map(Bucket::value_ref);
639        f.debug_list().entries(iter).finish()
640    }
641}
642
643impl<K, V> Default for ValuesMut<'_, K, V> {
644    fn default() -> Self {
645        Self {
646            iter: [].iter_mut(),
647        }
648    }
649}
650
651/// An owning iterator over the values of an [`IndexMap`].
652///
653/// This `struct` is created by the [`IndexMap::into_values`] method.
654/// See its documentation for more.
655pub struct IntoValues<K, V> {
656    // We eagerly drop the keys during construction so we can ignore them in
657    // `Clone`, but we keep uninit keys so the bucket's size and alignment
658    // remain the same, and therefore the `Vec` conversion should be in-place.
659    iter: vec::IntoIter<Bucket<MaybeUninit<K>, V>>,
660}
661
662impl<K, V> IntoValues<K, V> {
663    pub(super) fn new(entries: Vec<Bucket<K, V>>) -> Self {
664        // The original keys will be dropped here.
665        // The hash doesn't matter, but "copying" it in-place is free.
666        let entries = entries
667            .into_iter()
668            .map(
669                |Bucket {
670                     hash,
671                     value,
672                     ..
673                 }| Bucket {
674                    hash,
675                    key: MaybeUninit::uninit(),
676                    value,
677                },
678            )
679            .collect::<Vec<_>>();
680        Self {
681            iter: entries.into_iter(),
682        }
683    }
684}
685
686impl<K, V: Clone> Clone for IntoValues<K, V> {
687    fn clone(&self) -> Self {
688        let entries = self
689            .iter
690            .as_slice()
691            .iter()
692            .map(
693                |Bucket {
694                     value, ..
695                 }| Bucket {
696                    hash: HashValue(0),
697                    key: MaybeUninit::uninit(),
698                    value: value.clone(),
699                },
700            )
701            .collect::<Vec<_>>();
702        Self {
703            iter: entries.into_iter(),
704        }
705    }
706}
707
708impl<K, V> Iterator for IntoValues<K, V> {
709    type Item = V;
710
711    iterator_methods!(Bucket::value);
712}
713
714impl<K, V> DoubleEndedIterator for IntoValues<K, V> {
715    double_ended_iterator_methods!(Bucket::value);
716}
717
718impl<K, V> ExactSizeIterator for IntoValues<K, V> {
719    fn len(&self) -> usize {
720        self.iter.len()
721    }
722}
723
724impl<K, V> FusedIterator for IntoValues<K, V> {}
725
726impl<K, V: fmt::Debug> fmt::Debug for IntoValues<K, V> {
727    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
728        let iter = self.iter.as_slice().iter().map(Bucket::value_ref);
729        f.debug_list().entries(iter).finish()
730    }
731}
732
733impl<K, V> Default for IntoValues<K, V> {
734    fn default() -> Self {
735        Self {
736            iter: Vec::new().into_iter(),
737        }
738    }
739}
740
741/// A splicing iterator for `IndexMap`.
742///
743/// This `struct` is created by [`IndexMap::splice()`].
744/// See its documentation for more.
745pub struct Splice<'a, I, K, V, S>
746where
747    I: Iterator<Item = (K, V)>,
748    K: Hash + Eq,
749    S: BuildHasher,
750{
751    map: &'a mut IndexMap<K, V, S>,
752    tail: Core<K, V>,
753    drain: vec::IntoIter<Bucket<K, V>>,
754    replace_with: I,
755}
756
757impl<'a, I, K, V, S> Splice<'a, I, K, V, S>
758where
759    I: Iterator<Item = (K, V)>,
760    K: Hash + Eq,
761    S: BuildHasher,
762{
763    #[track_caller]
764    pub(super) fn new<R>(map: &'a mut IndexMap<K, V, S>, range: R, replace_with: I) -> Self
765    where
766        R: RangeBounds<usize>,
767    {
768        let (tail, drain) = map.core.split_splice(range);
769        Self {
770            map,
771            tail,
772            drain,
773            replace_with,
774        }
775    }
776}
777
778impl<I, K, V, S> Drop for Splice<'_, I, K, V, S>
779where
780    I: Iterator<Item = (K, V)>,
781    K: Hash + Eq,
782    S: BuildHasher,
783{
784    fn drop(&mut self) {
785        // Finish draining unconsumed items. We don't strictly *have* to do this
786        // manually, since we already split it into separate memory, but it will
787        // match the drop order of `vec::Splice` items this way.
788        let _ = self.drain.nth(usize::MAX);
789
790        // Now insert all the new items. If a key matches an existing entry, it
791        // keeps the original position and only replaces the value, like `insert`.
792        while let Some((key, value)) = self.replace_with.next() {
793            // Since the tail is disjoint, we can try to update it first,
794            // or else insert (update or append) the primary map.
795            let hash = self.map.hash(&key);
796            if let Some(i) = self.tail.get_index_of(hash, &key) {
797                self.tail.as_entries_mut()[i].value = value;
798            } else {
799                self.map.core.insert_full(hash, key, value);
800            }
801        }
802
803        // Finally, re-append the tail
804        self.map.core.append_unchecked(&mut self.tail);
805    }
806}
807
808impl<I, K, V, S> Iterator for Splice<'_, I, K, V, S>
809where
810    I: Iterator<Item = (K, V)>,
811    K: Hash + Eq,
812    S: BuildHasher,
813{
814    type Item = (K, V);
815
816    fn next(&mut self) -> Option<Self::Item> {
817        self.drain.next().map(Bucket::key_value)
818    }
819
820    fn size_hint(&self) -> (usize, Option<usize>) {
821        self.drain.size_hint()
822    }
823}
824
825impl<I, K, V, S> DoubleEndedIterator for Splice<'_, I, K, V, S>
826where
827    I: Iterator<Item = (K, V)>,
828    K: Hash + Eq,
829    S: BuildHasher,
830{
831    fn next_back(&mut self) -> Option<Self::Item> {
832        self.drain.next_back().map(Bucket::key_value)
833    }
834}
835
836impl<I, K, V, S> ExactSizeIterator for Splice<'_, I, K, V, S>
837where
838    I: Iterator<Item = (K, V)>,
839    K: Hash + Eq,
840    S: BuildHasher,
841{
842    fn len(&self) -> usize {
843        self.drain.len()
844    }
845}
846
847impl<I, K, V, S> FusedIterator for Splice<'_, I, K, V, S>
848where
849    I: Iterator<Item = (K, V)>,
850    K: Hash + Eq,
851    S: BuildHasher,
852{
853}
854
855impl<I, K, V, S> fmt::Debug for Splice<'_, I, K, V, S>
856where
857    I: fmt::Debug + Iterator<Item = (K, V)>,
858    K: fmt::Debug + Hash + Eq,
859    V: fmt::Debug,
860    S: BuildHasher,
861{
862    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
863        // Follow `vec::Splice` in only printing the drain and replacement
864        f.debug_struct("Splice")
865            .field("drain", &self.drain)
866            .field("replace_with", &self.replace_with)
867            .finish()
868    }
869}
870
871/// An extracting iterator for `IndexMap`.
872///
873/// This `struct` is created by [`IndexMap::extract_if()`].
874/// See its documentation for more.
875pub struct ExtractIf<'a, K, V, F> {
876    inner: ExtractCore<'a, K, V>,
877    pred: F,
878}
879
880impl<K, V, F> ExtractIf<'_, K, V, F> {
881    #[track_caller]
882    pub(super) fn new<R>(core: &mut Core<K, V>, range: R, pred: F) -> ExtractIf<'_, K, V, F>
883    where
884        R: RangeBounds<usize>,
885        F: FnMut(&K, &mut V) -> bool,
886    {
887        ExtractIf {
888            inner: core.extract(range),
889            pred,
890        }
891    }
892}
893
894impl<K, V, F> Iterator for ExtractIf<'_, K, V, F>
895where
896    F: FnMut(&K, &mut V) -> bool,
897{
898    type Item = (K, V);
899
900    fn next(&mut self) -> Option<Self::Item> {
901        self.inner
902            .extract_if(|bucket| {
903                let (key, value) = bucket.ref_mut();
904                (self.pred)(key, value)
905            })
906            .map(Bucket::key_value)
907    }
908
909    fn size_hint(&self) -> (usize, Option<usize>) {
910        (0, Some(self.inner.remaining()))
911    }
912}
913
914impl<K, V, F> FusedIterator for ExtractIf<'_, K, V, F> where F: FnMut(&K, &mut V) -> bool {}
915
916impl<K, V, F> fmt::Debug for ExtractIf<'_, K, V, F>
917where
918    K: fmt::Debug,
919    V: fmt::Debug,
920{
921    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
922        f.debug_struct("ExtractIf").finish_non_exhaustive()
923    }
924}
indexmap/map/iter.rs

indexmap/map/
iter.rs
