iddqd/id_hash_map/
imp.rs

1use super::{
2    Entry, IdHashItem, IntoIter, Iter, IterMut, OccupiedEntry, RefMut,
3    VacantEntry, tables::IdHashMapTables,
4};
5use crate::{
6    DefaultHashBuilder,
7    errors::DuplicateItem,
8    internal::{ValidateCompact, ValidationError},
9    support::{
10        alloc::{Allocator, Global, global_alloc},
11        borrow::DormantMutRef,
12        item_set::ItemSet,
13        map_hash::MapHash,
14    },
15};
16use alloc::collections::BTreeSet;
17use core::{
18    fmt,
19    hash::{BuildHasher, Hash},
20};
21use equivalent::Equivalent;
22use hashbrown::hash_table;
23
24/// A hash map where the key is part of the value.
25///
26/// The storage mechanism is a fast hash table of integer indexes to items, with
27/// these indexes stored in a hash table. This allows for efficient lookups by
28/// the key and prevents duplicates.
29///
30/// # Examples
31///
32/// ```
33/// # #[cfg(feature = "default-hasher")] {
34/// use iddqd::{IdHashItem, IdHashMap, id_upcast};
35///
36/// // Define a struct with a key.
37/// #[derive(Debug, PartialEq, Eq, Hash)]
38/// struct MyItem {
39///     id: String,
40///     value: u32,
41/// }
42///
43/// // Implement IdHashItem for the struct.
44/// impl IdHashItem for MyItem {
45///     // Keys can borrow from the item.
46///     type Key<'a> = &'a str;
47///
48///     fn key(&self) -> Self::Key<'_> {
49///         &self.id
50///     }
51///
52///     id_upcast!();
53/// }
54///
55/// // Create an IdHashMap and insert items.
56/// let mut map = IdHashMap::new();
57/// map.insert_unique(MyItem { id: "foo".to_string(), value: 42 }).unwrap();
58/// map.insert_unique(MyItem { id: "bar".to_string(), value: 20 }).unwrap();
59///
60/// // Look up items by their keys.
61/// assert_eq!(map.get("foo").unwrap().value, 42);
62/// assert_eq!(map.get("bar").unwrap().value, 20);
63/// assert!(map.get("baz").is_none());
64/// # }
65/// ```
66#[derive(Clone)]
67pub struct IdHashMap<T, S = DefaultHashBuilder, A: Allocator = Global> {
68    pub(super) items: ItemSet<T, A>,
69    tables: IdHashMapTables<S, A>,
70}
71
72impl<T: IdHashItem, S: Default, A: Allocator + Default> Default
73    for IdHashMap<T, S, A>
74{
75    fn default() -> Self {
76        Self {
77            items: ItemSet::with_capacity_in(0, A::default()),
78            tables: IdHashMapTables::default(),
79        }
80    }
81}
82
83#[cfg(feature = "default-hasher")]
84impl<T: IdHashItem> IdHashMap<T> {
85    /// Creates a new, empty `IdHashMap`.
86    ///
87    /// # Examples
88    ///
89    /// ```
90    /// # #[cfg(feature = "default-hasher")] {
91    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
92    ///
93    /// #[derive(Debug, PartialEq, Eq, Hash)]
94    /// struct Item {
95    ///     id: String,
96    ///     value: u32,
97    /// }
98    ///
99    /// impl IdHashItem for Item {
100    ///     type Key<'a> = &'a str;
101    ///     fn key(&self) -> Self::Key<'_> {
102    ///         &self.id
103    ///     }
104    ///     id_upcast!();
105    /// }
106    ///
107    /// let map: IdHashMap<Item> = IdHashMap::new();
108    /// assert!(map.is_empty());
109    /// assert_eq!(map.len(), 0);
110    /// # }
111    /// ```
112    #[inline]
113    pub fn new() -> Self {
114        Self { items: ItemSet::new(), tables: IdHashMapTables::default() }
115    }
116
117    /// Creates a new `IdHashMap` with the given capacity.
118    ///
119    /// # Examples
120    ///
121    /// ```
122    /// # #[cfg(feature = "default-hasher")] {
123    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
124    ///
125    /// #[derive(Debug, PartialEq, Eq, Hash)]
126    /// struct Item {
127    ///     id: String,
128    ///     value: u32,
129    /// }
130    ///
131    /// impl IdHashItem for Item {
132    ///     type Key<'a> = &'a str;
133    ///     fn key(&self) -> Self::Key<'_> {
134    ///         &self.id
135    ///     }
136    ///     id_upcast!();
137    /// }
138    ///
139    /// let map: IdHashMap<Item> = IdHashMap::with_capacity(10);
140    /// assert!(map.capacity() >= 10);
141    /// assert!(map.is_empty());
142    /// # }
143    /// ```
144    pub fn with_capacity(capacity: usize) -> Self {
145        Self {
146            items: ItemSet::with_capacity_in(capacity, global_alloc()),
147            tables: IdHashMapTables::with_capacity_and_hasher_in(
148                capacity,
149                DefaultHashBuilder::default(),
150                global_alloc(),
151            ),
152        }
153    }
154}
155
156impl<T: IdHashItem, S: Clone + BuildHasher> IdHashMap<T, S> {
157    /// Creates a new, empty `IdHashMap` with the given hasher.
158    ///
159    /// # Examples
160    ///
161    /// ```
162    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
163    /// use std::collections::hash_map::RandomState;
164    ///
165    /// #[derive(Debug, PartialEq, Eq, Hash)]
166    /// struct Item {
167    ///     id: String,
168    ///     value: u32,
169    /// }
170    ///
171    /// impl IdHashItem for Item {
172    ///     type Key<'a> = &'a str;
173    ///     fn key(&self) -> Self::Key<'_> {
174    ///         &self.id
175    ///     }
176    ///     id_upcast!();
177    /// }
178    ///
179    /// let hasher = RandomState::new();
180    /// let map: IdHashMap<Item, _> = IdHashMap::with_hasher(hasher);
181    /// assert!(map.is_empty());
182    /// ```
183    pub const fn with_hasher(hasher: S) -> Self {
184        Self {
185            items: ItemSet::new(),
186            tables: IdHashMapTables::with_hasher_in(hasher, global_alloc()),
187        }
188    }
189
190    /// Creates a new `IdHashMap` with the given capacity and hasher.
191    ///
192    /// # Examples
193    ///
194    /// ```
195    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
196    /// use std::collections::hash_map::RandomState;
197    ///
198    /// #[derive(Debug, PartialEq, Eq, Hash)]
199    /// struct Item {
200    ///     id: String,
201    ///     value: u32,
202    /// }
203    ///
204    /// impl IdHashItem for Item {
205    ///     type Key<'a> = &'a str;
206    ///     fn key(&self) -> Self::Key<'_> {
207    ///         &self.id
208    ///     }
209    ///     id_upcast!();
210    /// }
211    ///
212    /// let hasher = RandomState::new();
213    /// let map: IdHashMap<Item, _> =
214    ///     IdHashMap::with_capacity_and_hasher(10, hasher);
215    /// assert!(map.capacity() >= 10);
216    /// assert!(map.is_empty());
217    /// ```
218    pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> Self {
219        Self {
220            items: ItemSet::with_capacity_in(capacity, global_alloc()),
221            tables: IdHashMapTables::with_capacity_and_hasher_in(
222                capacity,
223                hasher,
224                global_alloc(),
225            ),
226        }
227    }
228}
229
230#[cfg(feature = "default-hasher")]
231impl<T: IdHashItem, A: Clone + Allocator> IdHashMap<T, DefaultHashBuilder, A> {
232    /// Creates a new empty `IdHashMap` using the given allocator.
233    ///
234    /// Requires the `allocator-api2` feature to be enabled.
235    ///
236    /// # Examples
237    ///
238    /// Using the [`bumpalo`](https://docs.rs/bumpalo) allocator:
239    ///
240    /// ```
241    /// # #[cfg(all(feature = "default-hasher", feature = "allocator-api2"))] {
242    /// use iddqd::{IdHashMap, IdHashItem, id_upcast};
243    /// # use iddqd_test_utils::bumpalo;
244    ///
245    /// #[derive(Debug, PartialEq, Eq, Hash)]
246    /// struct Item {
247    ///     id: String,
248    ///     value: u32,
249    /// }
250    ///
251    /// impl IdHashItem for Item {
252    ///     type Key<'a> = &'a str;
253    ///     fn key(&self) -> Self::Key<'_> { &self.id }
254    ///     id_upcast!();
255    /// }
256    ///
257    /// // Define a new allocator.
258    /// let bump = bumpalo::Bump::new();
259    /// // Create a new IdHashMap using the allocator.
260    /// let map: IdHashMap<Item, _, &bumpalo::Bump> = IdHashMap::new_in(&bump);
261    /// assert!(map.is_empty());
262    /// # }
263    /// ```
264    pub fn new_in(alloc: A) -> Self {
265        Self {
266            items: ItemSet::with_capacity_in(0, alloc.clone()),
267            tables: IdHashMapTables::with_capacity_and_hasher_in(
268                0,
269                DefaultHashBuilder::default(),
270                alloc,
271            ),
272        }
273    }
274
275    /// Creates an empty `IdHashMap` with the specified capacity using the given
276    /// allocator.
277    ///
278    /// Requires the `allocator-api2` feature to be enabled.
279    ///
280    /// # Examples
281    ///
282    /// Using the [`bumpalo`](https://docs.rs/bumpalo) allocator:
283    ///
284    /// ```
285    /// # #[cfg(all(feature = "default-hasher", feature = "allocator-api2"))] {
286    /// use iddqd::{IdHashMap, IdHashItem, id_upcast};
287    /// # use iddqd_test_utils::bumpalo;
288    ///
289    /// #[derive(Debug, PartialEq, Eq, Hash)]
290    /// struct Item {
291    ///     id: String,
292    ///     value: u32,
293    /// }
294    ///
295    /// impl IdHashItem for Item {
296    ///     type Key<'a> = &'a str;
297    ///     fn key(&self) -> Self::Key<'_> { &self.id }
298    ///     id_upcast!();
299    /// }
300    ///
301    /// // Define a new allocator.
302    /// let bump = bumpalo::Bump::new();
303    /// // Create a new IdHashMap with capacity using the allocator.
304    /// let map: IdHashMap<Item, _, &bumpalo::Bump> = IdHashMap::with_capacity_in(10, &bump);
305    /// assert!(map.capacity() >= 10);
306    /// assert!(map.is_empty());
307    /// # }
308    /// ```
309    pub fn with_capacity_in(capacity: usize, alloc: A) -> Self {
310        Self {
311            items: ItemSet::with_capacity_in(capacity, alloc.clone()),
312            tables: IdHashMapTables::with_capacity_and_hasher_in(
313                capacity,
314                DefaultHashBuilder::default(),
315                alloc,
316            ),
317        }
318    }
319}
320
321impl<T: IdHashItem, S: Clone + BuildHasher, A: Clone + Allocator>
322    IdHashMap<T, S, A>
323{
324    /// Creates a new, empty `IdHashMap` with the given hasher and allocator.
325    ///
326    /// Requires the `allocator-api2` feature to be enabled.
327    ///
328    /// # Examples
329    ///
330    /// Using the [`bumpalo`](https://docs.rs/bumpalo) allocator:
331    ///
332    /// ```
333    /// # #[cfg(feature = "allocator-api2")] {
334    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
335    /// use std::collections::hash_map::RandomState;
336    /// # use iddqd_test_utils::bumpalo;
337    ///
338    /// #[derive(Debug, PartialEq, Eq, Hash)]
339    /// struct Item {
340    ///     id: String,
341    ///     value: u32,
342    /// }
343    ///
344    /// impl IdHashItem for Item {
345    ///     type Key<'a> = &'a str;
346    ///     fn key(&self) -> Self::Key<'_> {
347    ///         &self.id
348    ///     }
349    ///     id_upcast!();
350    /// }
351    ///
352    /// // Define a new allocator.
353    /// let bump = bumpalo::Bump::new();
354    /// let hasher = RandomState::new();
355    /// // Create a new IdHashMap with hasher using the allocator.
356    /// let map: IdHashMap<Item, _, &bumpalo::Bump> =
357    ///     IdHashMap::with_hasher_in(hasher, &bump);
358    /// assert!(map.is_empty());
359    /// # }
360    /// ```
361    pub fn with_hasher_in(hasher: S, alloc: A) -> Self {
362        Self {
363            items: ItemSet::new_in(alloc.clone()),
364            tables: IdHashMapTables::with_hasher_in(hasher, alloc),
365        }
366    }
367
368    /// Creates a new, empty `IdHashMap` with the given capacity, hasher, and
369    /// allocator.
370    ///
371    /// Requires the `allocator-api2` feature to be enabled.
372    ///
373    /// # Examples
374    ///
375    /// Using the [`bumpalo`](https://docs.rs/bumpalo) allocator:
376    ///
377    /// ```
378    /// # #[cfg(feature = "allocator-api2")] {
379    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
380    /// use std::collections::hash_map::RandomState;
381    /// # use iddqd_test_utils::bumpalo;
382    ///
383    /// #[derive(Debug, PartialEq, Eq, Hash)]
384    /// struct Item {
385    ///     id: String,
386    ///     value: u32,
387    /// }
388    ///
389    /// impl IdHashItem for Item {
390    ///     type Key<'a> = &'a str;
391    ///     fn key(&self) -> Self::Key<'_> {
392    ///         &self.id
393    ///     }
394    ///     id_upcast!();
395    /// }
396    ///
397    /// // Define a new allocator.
398    /// let bump = bumpalo::Bump::new();
399    /// let hasher = RandomState::new();
400    /// // Create a new IdHashMap with capacity and hasher using the allocator.
401    /// let map: IdHashMap<Item, _, &bumpalo::Bump> =
402    ///     IdHashMap::with_capacity_and_hasher_in(10, hasher, &bump);
403    /// assert!(map.capacity() >= 10);
404    /// assert!(map.is_empty());
405    /// # }
406    /// ```
407    pub fn with_capacity_and_hasher_in(
408        capacity: usize,
409        hasher: S,
410        alloc: A,
411    ) -> Self {
412        Self {
413            items: ItemSet::with_capacity_in(capacity, alloc.clone()),
414            tables: IdHashMapTables::with_capacity_and_hasher_in(
415                capacity, hasher, alloc,
416            ),
417        }
418    }
419}
420
421impl<T: IdHashItem, S: Clone + BuildHasher, A: Allocator> IdHashMap<T, S, A> {
422    #[cfg(feature = "daft")]
423    pub(crate) fn hasher(&self) -> &S {
424        self.tables.hasher()
425    }
426
427    /// Returns the allocator.
428    ///
429    /// Requires the `allocator-api2` feature to be enabled.
430    ///
431    /// # Examples
432    ///
433    /// Using the [`bumpalo`](https://docs.rs/bumpalo) allocator:
434    ///
435    /// ```
436    /// # #[cfg(all(feature = "default-hasher", feature = "allocator-api2"))] {
437    /// use iddqd::{IdHashMap, IdHashItem, id_upcast};
438    /// # use iddqd_test_utils::bumpalo;
439    ///
440    /// #[derive(Debug, PartialEq, Eq, Hash)]
441    /// struct Item {
442    ///     id: String,
443    ///     value: u32,
444    /// }
445    ///
446    /// impl IdHashItem for Item {
447    ///     type Key<'a> = &'a str;
448    ///     fn key(&self) -> Self::Key<'_> { &self.id }
449    ///     id_upcast!();
450    /// }
451    ///
452    /// // Define a new allocator.
453    /// let bump = bumpalo::Bump::new();
454    /// // Create a new IdHashMap using the allocator.
455    /// let map: IdHashMap<Item, _, &bumpalo::Bump> = IdHashMap::new_in(&bump);
456    /// let _allocator = map.allocator();
457    /// # }
458    /// ```
459    pub fn allocator(&self) -> &A {
460        self.items.allocator()
461    }
462
463    /// Returns the currently allocated capacity of the map.
464    ///
465    /// # Examples
466    ///
467    /// ```
468    /// # #[cfg(feature = "default-hasher")] {
469    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
470    ///
471    /// #[derive(Debug, PartialEq, Eq, Hash)]
472    /// struct Item {
473    ///     id: String,
474    ///     value: u32,
475    /// }
476    ///
477    /// impl IdHashItem for Item {
478    ///     type Key<'a> = &'a str;
479    ///     fn key(&self) -> Self::Key<'_> {
480    ///         &self.id
481    ///     }
482    ///     id_upcast!();
483    /// }
484    ///
485    /// let map: IdHashMap<Item> = IdHashMap::with_capacity(10);
486    /// assert!(map.capacity() >= 10);
487    /// # }
488    /// ```
489    pub fn capacity(&self) -> usize {
490        // items and tables.capacity might theoretically diverge: use
491        // items.capacity.
492        self.items.capacity()
493    }
494
495    /// Returns true if the map is empty.
496    ///
497    /// # Examples
498    ///
499    /// ```
500    /// # #[cfg(feature = "default-hasher")] {
501    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
502    ///
503    /// #[derive(Debug, PartialEq, Eq, Hash)]
504    /// struct Item {
505    ///     id: String,
506    ///     value: u32,
507    /// }
508    ///
509    /// impl IdHashItem for Item {
510    ///     type Key<'a> = &'a str;
511    ///     fn key(&self) -> Self::Key<'_> {
512    ///         &self.id
513    ///     }
514    ///     id_upcast!();
515    /// }
516    ///
517    /// let mut map = IdHashMap::new();
518    /// assert!(map.is_empty());
519    ///
520    /// map.insert_unique(Item { id: "foo".to_string(), value: 42 }).unwrap();
521    /// assert!(!map.is_empty());
522    /// # }
523    /// ```
524    #[inline]
525    pub fn is_empty(&self) -> bool {
526        self.items.is_empty()
527    }
528
529    /// Returns the number of items in the map.
530    ///
531    /// # Examples
532    ///
533    /// ```
534    /// # #[cfg(feature = "default-hasher")] {
535    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
536    ///
537    /// #[derive(Debug, PartialEq, Eq, Hash)]
538    /// struct Item {
539    ///     id: String,
540    ///     value: u32,
541    /// }
542    ///
543    /// impl IdHashItem for Item {
544    ///     type Key<'a> = &'a str;
545    ///     fn key(&self) -> Self::Key<'_> {
546    ///         &self.id
547    ///     }
548    ///     id_upcast!();
549    /// }
550    ///
551    /// let mut map = IdHashMap::new();
552    /// assert_eq!(map.len(), 0);
553    ///
554    /// map.insert_unique(Item { id: "foo".to_string(), value: 42 }).unwrap();
555    /// assert_eq!(map.len(), 1);
556    ///
557    /// map.insert_unique(Item { id: "bar".to_string(), value: 20 }).unwrap();
558    /// assert_eq!(map.len(), 2);
559    /// # }
560    /// ```
561    #[inline]
562    pub fn len(&self) -> usize {
563        self.items.len()
564    }
565
566    /// Iterates over the items in the map.
567    ///
568    /// Similar to [`HashMap`], the iteration order is arbitrary and not
569    /// guaranteed to be stable.
570    ///
571    /// # Examples
572    ///
573    /// ```
574    /// # #[cfg(feature = "default-hasher")] {
575    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
576    ///
577    /// #[derive(Debug, PartialEq, Eq, Hash)]
578    /// struct Item {
579    ///     id: String,
580    ///     value: u32,
581    /// }
582    ///
583    /// impl IdHashItem for Item {
584    ///     type Key<'a> = &'a str;
585    ///     fn key(&self) -> Self::Key<'_> {
586    ///         &self.id
587    ///     }
588    ///     id_upcast!();
589    /// }
590    ///
591    /// let mut map = IdHashMap::new();
592    /// map.insert_unique(Item { id: "foo".to_string(), value: 42 }).unwrap();
593    /// map.insert_unique(Item { id: "bar".to_string(), value: 20 }).unwrap();
594    ///
595    /// let mut values: Vec<u32> = map.iter().map(|item| item.value).collect();
596    /// values.sort();
597    /// assert_eq!(values, vec![20, 42]);
598    /// # }
599    /// ```
600    ///
601    /// [`HashMap`]: std::collections::HashMap
602    #[inline]
603    pub fn iter(&self) -> Iter<'_, T> {
604        Iter::new(&self.items)
605    }
606
607    /// Iterates over the items in the map, allowing for mutation.
608    ///
609    /// Similar to [`HashMap`], the iteration order is arbitrary and not
610    /// guaranteed to be stable.
611    ///
612    /// # Examples
613    ///
614    /// ```
615    /// # #[cfg(feature = "default-hasher")] {
616    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
617    ///
618    /// #[derive(Debug, PartialEq, Eq, Hash)]
619    /// struct Item {
620    ///     id: String,
621    ///     value: u32,
622    /// }
623    ///
624    /// impl IdHashItem for Item {
625    ///     type Key<'a> = &'a str;
626    ///     fn key(&self) -> Self::Key<'_> {
627    ///         &self.id
628    ///     }
629    ///     id_upcast!();
630    /// }
631    ///
632    /// let mut map = IdHashMap::new();
633    /// map.insert_unique(Item { id: "foo".to_string(), value: 42 }).unwrap();
634    /// map.insert_unique(Item { id: "bar".to_string(), value: 20 }).unwrap();
635    ///
636    /// for mut item in map.iter_mut() {
637    ///     item.value *= 2;
638    /// }
639    ///
640    /// assert_eq!(map.get("foo").unwrap().value, 84);
641    /// assert_eq!(map.get("bar").unwrap().value, 40);
642    /// # }
643    /// ```
644    ///
645    /// [`HashMap`]: std::collections::HashMap
646    #[inline]
647    pub fn iter_mut(&mut self) -> IterMut<'_, T, S, A> {
648        IterMut::new(&self.tables, &mut self.items)
649    }
650
651    /// Checks general invariants of the map.
652    ///
653    /// The code below always upholds these invariants, but it's useful to have
654    /// an explicit check for tests.
655    #[doc(hidden)]
656    pub fn validate(
657        &self,
658        compactness: ValidateCompact,
659    ) -> Result<(), ValidationError>
660    where
661        T: fmt::Debug,
662    {
663        self.items.validate(compactness)?;
664        self.tables.validate(self.len(), compactness)?;
665
666        // Check that the indexes are all correct.
667        for (&ix, item) in self.items.iter() {
668            let key = item.key();
669            let Some(ix1) = self.find_index(&key) else {
670                return Err(ValidationError::general(format!(
671                    "item at index {ix} has no key1 index"
672                )));
673            };
674
675            if ix1 != ix {
676                return Err(ValidationError::General(format!(
677                    "item at index {ix} has mismatched indexes: ix1: {ix1}",
678                )));
679            }
680        }
681
682        Ok(())
683    }
684
685    /// Inserts a value into the map, removing and returning the conflicting
686    /// item, if any.
687    ///
688    /// # Examples
689    ///
690    /// ```
691    /// # #[cfg(feature = "default-hasher")] {
692    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
693    ///
694    /// #[derive(Debug, PartialEq, Eq, Hash)]
695    /// struct Item {
696    ///     id: String,
697    ///     value: u32,
698    /// }
699    ///
700    /// impl IdHashItem for Item {
701    ///     type Key<'a> = &'a str;
702    ///     fn key(&self) -> Self::Key<'_> {
703    ///         &self.id
704    ///     }
705    ///     id_upcast!();
706    /// }
707    ///
708    /// let mut map = IdHashMap::new();
709    ///
710    /// // First insertion returns None
711    /// let old = map.insert_overwrite(Item { id: "foo".to_string(), value: 42 });
712    /// assert!(old.is_none());
713    ///
714    /// // Second insertion with same key returns the old value
715    /// let old = map.insert_overwrite(Item { id: "foo".to_string(), value: 100 });
716    /// assert_eq!(old.unwrap().value, 42);
717    /// assert_eq!(map.get("foo").unwrap().value, 100);
718    /// # }
719    /// ```
720    #[doc(alias = "insert")]
721    pub fn insert_overwrite(&mut self, value: T) -> Option<T> {
722        // Trying to write this function for maximal efficiency can get very
723        // tricky, requiring delicate handling of indexes. We follow a very
724        // simple approach instead:
725        //
726        // 1. Remove items corresponding to the key that is already in the map.
727        // 2. Add the item to the map.
728
729        let duplicate = self.remove(&value.key());
730
731        if self.insert_unique(value).is_err() {
732            // We should never get here, because we just removed all the
733            // duplicates.
734            panic!("insert_unique failed after removing duplicates");
735        }
736
737        duplicate
738    }
739
740    /// Inserts a value into the set, returning an error if any duplicates were
741    /// added.
742    ///
743    /// # Examples
744    ///
745    /// ```
746    /// # #[cfg(feature = "default-hasher")] {
747    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
748    ///
749    /// #[derive(Debug, PartialEq, Eq, Hash)]
750    /// struct Item {
751    ///     id: String,
752    ///     value: u32,
753    /// }
754    ///
755    /// impl IdHashItem for Item {
756    ///     type Key<'a> = &'a str;
757    ///     fn key(&self) -> Self::Key<'_> {
758    ///         &self.id
759    ///     }
760    ///     id_upcast!();
761    /// }
762    ///
763    /// let mut map = IdHashMap::new();
764    ///
765    /// // First insertion succeeds
766    /// assert!(
767    ///     map.insert_unique(Item { id: "foo".to_string(), value: 42 }).is_ok()
768    /// );
769    ///
770    /// // Second insertion with different key succeeds
771    /// assert!(
772    ///     map.insert_unique(Item { id: "bar".to_string(), value: 20 }).is_ok()
773    /// );
774    ///
775    /// // Third insertion with duplicate key fails
776    /// assert!(
777    ///     map.insert_unique(Item { id: "foo".to_string(), value: 100 }).is_err()
778    /// );
779    /// # }
780    /// ```
781    pub fn insert_unique(
782        &mut self,
783        value: T,
784    ) -> Result<(), DuplicateItem<T, &T>> {
785        let _ = self.insert_unique_impl(value)?;
786        Ok(())
787    }
788
789    /// Returns true if the map contains the given key.
790    ///
791    /// # Examples
792    ///
793    /// ```
794    /// # #[cfg(feature = "default-hasher")] {
795    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
796    ///
797    /// #[derive(Debug, PartialEq, Eq, Hash)]
798    /// struct Item {
799    ///     id: String,
800    ///     value: u32,
801    /// }
802    ///
803    /// impl IdHashItem for Item {
804    ///     type Key<'a> = &'a str;
805    ///     fn key(&self) -> Self::Key<'_> {
806    ///         &self.id
807    ///     }
808    ///     id_upcast!();
809    /// }
810    ///
811    /// let mut map = IdHashMap::new();
812    /// map.insert_unique(Item { id: "foo".to_string(), value: 42 }).unwrap();
813    ///
814    /// assert!(map.contains_key("foo"));
815    /// assert!(!map.contains_key("bar"));
816    /// # }
817    /// ```
818    pub fn contains_key<'a, Q>(&'a self, key1: &Q) -> bool
819    where
820        Q: ?Sized + Hash + Equivalent<T::Key<'a>>,
821    {
822        self.find_index(key1).is_some()
823    }
824
825    /// Gets a reference to the value associated with the given key.
826    ///
827    /// # Examples
828    ///
829    /// ```
830    /// # #[cfg(feature = "default-hasher")] {
831    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
832    ///
833    /// #[derive(Debug, PartialEq, Eq, Hash)]
834    /// struct Item {
835    ///     id: String,
836    ///     value: u32,
837    /// }
838    ///
839    /// impl IdHashItem for Item {
840    ///     type Key<'a> = &'a str;
841    ///     fn key(&self) -> Self::Key<'_> {
842    ///         &self.id
843    ///     }
844    ///     id_upcast!();
845    /// }
846    ///
847    /// let mut map = IdHashMap::new();
848    /// map.insert_unique(Item { id: "foo".to_string(), value: 42 }).unwrap();
849    ///
850    /// assert_eq!(map.get("foo").unwrap().value, 42);
851    /// assert!(map.get("bar").is_none());
852    /// # }
853    /// ```
854    pub fn get<'a, Q>(&'a self, key: &Q) -> Option<&'a T>
855    where
856        Q: ?Sized + Hash + Equivalent<T::Key<'a>>,
857    {
858        self.find_index(key).map(|ix| &self.items[ix])
859    }
860
861    /// Gets a mutable reference to the value associated with the given key.
862    ///
863    /// # Examples
864    ///
865    /// ```
866    /// # #[cfg(feature = "default-hasher")] {
867    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
868    ///
869    /// #[derive(Debug, PartialEq, Eq, Hash)]
870    /// struct Item {
871    ///     id: String,
872    ///     value: u32,
873    /// }
874    ///
875    /// impl IdHashItem for Item {
876    ///     type Key<'a> = &'a str;
877    ///     fn key(&self) -> Self::Key<'_> {
878    ///         &self.id
879    ///     }
880    ///     id_upcast!();
881    /// }
882    ///
883    /// let mut map = IdHashMap::new();
884    /// map.insert_unique(Item { id: "foo".to_string(), value: 42 }).unwrap();
885    ///
886    /// if let Some(mut item) = map.get_mut("foo") {
887    ///     item.value = 100;
888    /// }
889    ///
890    /// assert_eq!(map.get("foo").unwrap().value, 100);
891    /// assert!(map.get_mut("bar").is_none());
892    /// # }
893    /// ```
894    pub fn get_mut<'a, Q>(&'a mut self, key: &Q) -> Option<RefMut<'a, T, S>>
895    where
896        Q: ?Sized + Hash + Equivalent<T::Key<'a>>,
897    {
898        let (dormant_map, index) = {
899            let (map, dormant_map) = DormantMutRef::new(self);
900            let index = map.find_index(key)?;
901            (dormant_map, index)
902        };
903
904        // SAFETY: `map` is not used after this point.
905        let awakened_map = unsafe { dormant_map.awaken() };
906        let item = &mut awakened_map.items[index];
907        let hashes = awakened_map.tables.make_hash(item);
908        Some(RefMut::new(hashes, item))
909    }
910
911    /// Removes an item from the map by its key.
912    ///
913    /// # Examples
914    ///
915    /// ```
916    /// # #[cfg(feature = "default-hasher")] {
917    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
918    ///
919    /// #[derive(Debug, PartialEq, Eq, Hash)]
920    /// struct Item {
921    ///     id: String,
922    ///     value: u32,
923    /// }
924    ///
925    /// impl IdHashItem for Item {
926    ///     type Key<'a> = &'a str;
927    ///     fn key(&self) -> Self::Key<'_> {
928    ///         &self.id
929    ///     }
930    ///     id_upcast!();
931    /// }
932    ///
933    /// let mut map = IdHashMap::new();
934    /// map.insert_unique(Item { id: "foo".to_string(), value: 42 }).unwrap();
935    ///
936    /// let removed = map.remove("foo");
937    /// assert_eq!(removed.unwrap().value, 42);
938    /// assert!(map.is_empty());
939    ///
940    /// // Removing non-existent key returns None
941    /// assert!(map.remove("bar").is_none());
942    /// # }
943    /// ```
944    pub fn remove<'a, Q>(&'a mut self, key: &Q) -> Option<T>
945    where
946        Q: ?Sized + Hash + Equivalent<T::Key<'a>>,
947    {
948        let (dormant_map, remove_index) = {
949            let (map, dormant_map) = DormantMutRef::new(self);
950            let remove_index = map.find_index(key)?;
951            (dormant_map, remove_index)
952        };
953
954        // SAFETY: `map` is not used after this point.
955        let awakened_map = unsafe { dormant_map.awaken() };
956
957        let value = awakened_map
958            .items
959            .remove(remove_index)
960            .expect("items missing key1 that was just retrieved");
961
962        // Remove the value from the tables.
963        let Ok(item1) =
964            awakened_map.tables.key_to_item.find_entry(&value.key(), |index| {
965                if index == remove_index {
966                    value.key()
967                } else {
968                    awakened_map.items[index].key()
969                }
970            })
971        else {
972            // The item was not found.
973            panic!("we just looked this item up");
974        };
975
976        item1.remove();
977
978        Some(value)
979    }
980
981    /// Retrieves an entry by its key.
982    ///
983    /// Due to borrow checker limitations, this always accepts an owned key
984    /// rather than a borrowed form of it.
985    ///
986    /// # Examples
987    ///
988    /// ```
989    /// # #[cfg(feature = "default-hasher")] {
990    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
991    ///
992    /// #[derive(Debug, PartialEq, Eq, Hash)]
993    /// struct Item {
994    ///     id: String,
995    ///     value: u32,
996    /// }
997    ///
998    /// impl IdHashItem for Item {
999    ///     type Key<'a> = &'a str;
1000    ///     fn key(&self) -> Self::Key<'_> {
1001    ///         &self.id
1002    ///     }
1003    ///     id_upcast!();
1004    /// }
1005    ///
1006    /// let mut map = IdHashMap::new();
1007    ///
1008    /// // Use entry API for conditional insertion
1009    /// map.entry("foo").or_insert(Item { id: "foo".to_string(), value: 42 });
1010    /// map.entry("bar").or_insert(Item { id: "bar".to_string(), value: 20 });
1011    ///
1012    /// assert_eq!(map.len(), 2);
1013    /// # }
1014    /// ```
1015    pub fn entry<'a>(&'a mut self, key: T::Key<'_>) -> Entry<'a, T, S, A> {
1016        // Why does this always take an owned key? Well, it would seem like we
1017        // should be able to pass in any Q that is equivalent. That results in
1018        // *this* code compiling fine, but callers have trouble using it because
1019        // the borrow checker believes the keys are borrowed for the full 'a
1020        // rather than a shorter lifetime.
1021        //
1022        // By accepting owned keys, we can use the upcast functions to convert
1023        // them to a shorter lifetime (so this function accepts T::Key<'_>
1024        // rather than T::Key<'a>).
1025        //
1026        // Really, the solution here is to allow GATs to require covariant
1027        // parameters. If that were allowed, the borrow checker should be able
1028        // to figure out that keys don't need to be borrowed for the full 'a,
1029        // just for some shorter lifetime.
1030        let (map, dormant_map) = DormantMutRef::new(self);
1031        let key = T::upcast_key(key);
1032        {
1033            // index is explicitly typed to show that it has a trivial Drop impl
1034            // that doesn't capture anything from map.
1035            let index: Option<usize> = map
1036                .tables
1037                .key_to_item
1038                .find_index(&key, |index| map.items[index].key());
1039            if let Some(index) = index {
1040                drop(key);
1041                return Entry::Occupied(
1042                    // SAFETY: `map` is not used after this point.
1043                    unsafe { OccupiedEntry::new(dormant_map, index) },
1044                );
1045            }
1046        }
1047        let hash = map.make_key_hash(&key);
1048        Entry::Vacant(
1049            // SAFETY: `map` is not used after this point.
1050            unsafe { VacantEntry::new(dormant_map, hash) },
1051        )
1052    }
1053
1054    fn find_index<'a, Q>(&'a self, k: &Q) -> Option<usize>
1055    where
1056        Q: Hash + Equivalent<T::Key<'a>> + ?Sized,
1057    {
1058        self.tables.key_to_item.find_index(k, |index| self.items[index].key())
1059    }
1060
1061    fn make_hash(&self, item: &T) -> MapHash<S> {
1062        self.tables.make_hash(item)
1063    }
1064
1065    fn make_key_hash(&self, key: &T::Key<'_>) -> MapHash<S> {
1066        self.tables.make_key_hash::<T>(key)
1067    }
1068
1069    pub(super) fn get_by_index(&self, index: usize) -> Option<&T> {
1070        self.items.get(index)
1071    }
1072
1073    pub(super) fn get_by_index_mut(
1074        &mut self,
1075        index: usize,
1076    ) -> Option<RefMut<'_, T, S>> {
1077        let hashes = self.make_hash(&self.items[index]);
1078        let item = &mut self.items[index];
1079        Some(RefMut::new(hashes, item))
1080    }
1081
1082    pub(super) fn insert_unique_impl(
1083        &mut self,
1084        value: T,
1085    ) -> Result<usize, DuplicateItem<T, &T>> {
1086        let mut duplicates = BTreeSet::new();
1087
1088        // Check for duplicates *before* inserting the new item, because we
1089        // don't want to partially insert the new item and then have to roll
1090        // back.
1091        let key = value.key();
1092
1093        let entry = match self
1094            .tables
1095            .key_to_item
1096            .entry(key, |index| self.items[index].key())
1097        {
1098            hash_table::Entry::Occupied(slot) => {
1099                duplicates.insert(*slot.get());
1100                None
1101            }
1102            hash_table::Entry::Vacant(slot) => Some(slot),
1103        };
1104
1105        if !duplicates.is_empty() {
1106            return Err(DuplicateItem::__internal_new(
1107                value,
1108                duplicates.iter().map(|ix| &self.items[*ix]).collect(),
1109            ));
1110        }
1111
1112        let next_index = self.items.insert_at_next_index(value);
1113        entry.unwrap().insert(next_index);
1114
1115        Ok(next_index)
1116    }
1117
1118    pub(super) fn remove_by_index(&mut self, remove_index: usize) -> Option<T> {
1119        let value = self.items.remove(remove_index)?;
1120
1121        // Remove the value from the tables.
1122        let Ok(item) =
1123            self.tables.key_to_item.find_entry(&value.key(), |index| {
1124                if index == remove_index {
1125                    value.key()
1126                } else {
1127                    self.items[index].key()
1128                }
1129            })
1130        else {
1131            // The item was not found.
1132            panic!("we just looked this item up");
1133        };
1134
1135        item.remove();
1136
1137        Some(value)
1138    }
1139
1140    pub(super) fn replace_at_index(&mut self, index: usize, value: T) -> T {
1141        // We check the key before removing it, to avoid leaving the map in an
1142        // inconsistent state.
1143        let old_key =
1144            self.get_by_index(index).expect("index is known to be valid").key();
1145        if T::upcast_key(old_key) != value.key() {
1146            panic!(
1147                "must insert a value with \
1148                 the same key used to create the entry"
1149            );
1150        }
1151
1152        // Now that we know the key is the same, we can replace the value
1153        // directly without needing to tweak any tables.
1154        self.items.replace(index, value)
1155    }
1156}
1157
1158impl<'a, T, S: Clone + BuildHasher, A: Allocator> fmt::Debug
1159    for IdHashMap<T, S, A>
1160where
1161    T: IdHashItem + fmt::Debug,
1162    T::Key<'a>: fmt::Debug,
1163    T: 'a,
1164{
1165    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1166        let mut map = f.debug_map();
1167
1168        for item in self.iter() {
1169            let key = item.key();
1170
1171            // SAFETY:
1172            //
1173            // * Lifetime extension: for a type T and two lifetime params 'a and
1174            //   'b, T<'a> and T<'b> aren't guaranteed to have the same layout,
1175            //   but (a) that is true today and (b) it would be shocking and
1176            //   break half the Rust ecosystem if that were to change in the
1177            //   future.
1178            // * We only use key within the scope of this block before immediately
1179            //   dropping it. In particular, map.entry calls key.fmt() without
1180            //   holding a reference to it.
1181            let key: T::Key<'a> =
1182                unsafe { core::mem::transmute::<T::Key<'_>, T::Key<'a>>(key) };
1183
1184            map.entry(&key, item);
1185        }
1186        map.finish()
1187    }
1188}
1189
1190impl<T: IdHashItem + PartialEq, S: Clone + BuildHasher, A: Allocator> PartialEq
1191    for IdHashMap<T, S, A>
1192{
1193    fn eq(&self, other: &Self) -> bool {
1194        // Implementing PartialEq for IdHashMap is tricky because IdHashMap is
1195        // not semantically like an IndexMap: two maps are equivalent even if
1196        // their items are in a different order. In other words, any permutation
1197        // of items is equivalent.
1198        //
1199        // We also can't sort the items because they're not necessarily Ord.
1200        //
1201        // So we write a custom equality check that checks that each key in one
1202        // map points to the same item as in the other map.
1203
1204        if self.items.len() != other.items.len() {
1205            return false;
1206        }
1207
1208        // Walk over all the items in the first map and check that they point to
1209        // the same item in the second map.
1210        for item in self.items.values() {
1211            let k1 = item.key();
1212
1213            // Check that the indexes are the same in the other map.
1214            let Some(other_ix) = other.find_index(&k1) else {
1215                return false;
1216            };
1217
1218            // Check that the other map's item is the same as this map's
1219            // item. (This is what we use the `PartialEq` bound on T for.)
1220            //
1221            // Because we've checked that other_ix is Some, we know that it is
1222            // valid and points to the expected item.
1223            let other_item = &other.items[other_ix];
1224            if item != other_item {
1225                return false;
1226            }
1227        }
1228
1229        true
1230    }
1231}
1232
1233// The Eq bound on T ensures that the TriHashMap forms an equivalence class.
1234impl<T: IdHashItem + Eq, S: Clone + BuildHasher, A: Allocator> Eq
1235    for IdHashMap<T, S, A>
1236{
1237}
1238
1239/// The `Extend` implementation overwrites duplicates. In the future, there will
1240/// also be an `extend_unique` method that will return an error.
1241///
1242/// # Examples
1243///
1244/// ```
1245/// # #[cfg(feature = "default-hasher")] {
1246/// use iddqd::{IdHashItem, IdHashMap, id_upcast};
1247///
1248/// #[derive(Debug, PartialEq, Eq, Hash)]
1249/// struct Item {
1250///     id: String,
1251///     value: u32,
1252/// }
1253///
1254/// impl IdHashItem for Item {
1255///     type Key<'a> = &'a str;
1256///     fn key(&self) -> Self::Key<'_> {
1257///         &self.id
1258///     }
1259///     id_upcast!();
1260/// }
1261///
1262/// let mut map = IdHashMap::new();
1263/// map.insert_unique(Item { id: "foo".to_string(), value: 42 }).unwrap();
1264///
1265/// let new_items = vec![
1266///     Item { id: "foo".to_string(), value: 100 }, // overwrites existing
1267///     Item { id: "bar".to_string(), value: 20 },  // new item
1268/// ];
1269///
1270/// map.extend(new_items);
1271/// assert_eq!(map.len(), 2);
1272/// assert_eq!(map.get("foo").unwrap().value, 100); // overwritten
1273/// assert_eq!(map.get("bar").unwrap().value, 20); // new
1274///
1275/// # }
1276/// ```
1277impl<T: IdHashItem, S: Clone + BuildHasher, A: Allocator> Extend<T>
1278    for IdHashMap<T, S, A>
1279{
1280    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
1281        for item in iter {
1282            self.insert_overwrite(item);
1283        }
1284    }
1285}
1286
1287impl<'a, T: IdHashItem, S: Clone + BuildHasher, A: Allocator> IntoIterator
1288    for &'a IdHashMap<T, S, A>
1289{
1290    type Item = &'a T;
1291    type IntoIter = Iter<'a, T>;
1292
1293    /// Creates an iterator over references to the items in the map.
1294    ///
1295    /// # Examples
1296    ///
1297    /// ```
1298    /// # #[cfg(feature = "default-hasher")] {
1299    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
1300    ///
1301    /// #[derive(Debug, PartialEq, Eq, Hash)]
1302    /// struct Item {
1303    ///     id: String,
1304    ///     value: u32,
1305    /// }
1306    ///
1307    /// impl IdHashItem for Item {
1308    ///     type Key<'a> = &'a str;
1309    ///     fn key(&self) -> Self::Key<'_> {
1310    ///         &self.id
1311    ///     }
1312    ///     id_upcast!();
1313    /// }
1314    ///
1315    /// let mut map = IdHashMap::new();
1316    /// map.insert_unique(Item { id: "foo".to_string(), value: 42 }).unwrap();
1317    /// map.insert_unique(Item { id: "bar".to_string(), value: 20 }).unwrap();
1318    ///
1319    /// let mut values: Vec<u32> =
1320    ///     (&map).into_iter().map(|item| item.value).collect();
1321    /// values.sort();
1322    /// assert_eq!(values, vec![20, 42]);
1323    /// # }
1324    /// ```
1325    #[inline]
1326    fn into_iter(self) -> Self::IntoIter {
1327        self.iter()
1328    }
1329}
1330
1331impl<'a, T: IdHashItem, S: Clone + BuildHasher, A: Allocator> IntoIterator
1332    for &'a mut IdHashMap<T, S, A>
1333{
1334    type Item = RefMut<'a, T, S>;
1335    type IntoIter = IterMut<'a, T, S, A>;
1336
1337    /// Creates an iterator over mutable references to the items in the map.
1338    ///
1339    /// # Examples
1340    ///
1341    /// ```
1342    /// # #[cfg(feature = "default-hasher")] {
1343    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
1344    ///
1345    /// #[derive(Debug, PartialEq, Eq, Hash)]
1346    /// struct Item {
1347    ///     id: String,
1348    ///     value: u32,
1349    /// }
1350    ///
1351    /// impl IdHashItem for Item {
1352    ///     type Key<'a> = &'a str;
1353    ///     fn key(&self) -> Self::Key<'_> {
1354    ///         &self.id
1355    ///     }
1356    ///     id_upcast!();
1357    /// }
1358    ///
1359    /// let mut map = IdHashMap::new();
1360    /// map.insert_unique(Item { id: "foo".to_string(), value: 42 }).unwrap();
1361    /// map.insert_unique(Item { id: "bar".to_string(), value: 20 }).unwrap();
1362    ///
1363    /// for mut item in &mut map {
1364    ///     item.value *= 2;
1365    /// }
1366    ///
1367    /// assert_eq!(map.get("foo").unwrap().value, 84);
1368    /// assert_eq!(map.get("bar").unwrap().value, 40);
1369    /// # }
1370    /// ```
1371    #[inline]
1372    fn into_iter(self) -> Self::IntoIter {
1373        self.iter_mut()
1374    }
1375}
1376
1377impl<T: IdHashItem, S: Clone + BuildHasher, A: Allocator> IntoIterator
1378    for IdHashMap<T, S, A>
1379{
1380    type Item = T;
1381    type IntoIter = IntoIter<T, A>;
1382
1383    /// Consumes the map and creates an iterator over the owned items.
1384    ///
1385    /// # Examples
1386    ///
1387    /// ```
1388    /// # #[cfg(feature = "default-hasher")] {
1389    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
1390    ///
1391    /// #[derive(Debug, PartialEq, Eq, Hash)]
1392    /// struct Item {
1393    ///     id: String,
1394    ///     value: u32,
1395    /// }
1396    ///
1397    /// impl IdHashItem for Item {
1398    ///     type Key<'a> = &'a str;
1399    ///     fn key(&self) -> Self::Key<'_> {
1400    ///         &self.id
1401    ///     }
1402    ///     id_upcast!();
1403    /// }
1404    ///
1405    /// let mut map = IdHashMap::new();
1406    /// map.insert_unique(Item { id: "foo".to_string(), value: 42 }).unwrap();
1407    /// map.insert_unique(Item { id: "bar".to_string(), value: 20 }).unwrap();
1408    ///
1409    /// let mut values: Vec<u32> = map.into_iter().map(|item| item.value).collect();
1410    /// values.sort();
1411    /// assert_eq!(values, vec![20, 42]);
1412    /// # }
1413    /// ```
1414    #[inline]
1415    fn into_iter(self) -> Self::IntoIter {
1416        IntoIter::new(self.items)
1417    }
1418}
1419
1420/// The `FromIterator` implementation for `IdHashMap` overwrites duplicate
1421/// items.
1422///
1423/// # Examples
1424///
1425/// ```
1426/// # #[cfg(feature = "default-hasher")] {
1427/// use iddqd::{IdHashItem, IdHashMap, id_upcast};
1428///
1429/// #[derive(Debug, PartialEq, Eq, Hash)]
1430/// struct Item {
1431///     id: String,
1432///     value: u32,
1433/// }
1434///
1435/// impl IdHashItem for Item {
1436///     type Key<'a> = &'a str;
1437///     fn key(&self) -> Self::Key<'_> {
1438///         &self.id
1439///     }
1440///     id_upcast!();
1441/// }
1442///
1443/// let items = vec![
1444///     Item { id: "foo".to_string(), value: 42 },
1445///     Item { id: "bar".to_string(), value: 20 },
1446///     Item { id: "foo".to_string(), value: 100 }, // duplicate key, overwrites
1447/// ];
1448///
1449/// let map: IdHashMap<Item> = items.into_iter().collect();
1450/// assert_eq!(map.len(), 2);
1451/// assert_eq!(map.get("foo").unwrap().value, 100); // last value wins
1452/// assert_eq!(map.get("bar").unwrap().value, 20);
1453/// # }
1454/// ```
1455impl<T: IdHashItem, S: Default + Clone + BuildHasher, A: Allocator + Default>
1456    FromIterator<T> for IdHashMap<T, S, A>
1457{
1458    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
1459        let mut map = IdHashMap::default();
1460        for item in iter {
1461            map.insert_overwrite(item);
1462        }
1463        map
1464    }
1465}