indexmap/map/
iter.rs

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

indexmap/map/
iter.rs
