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}