vecmap/map/
impls.rs

1use super::VecMap;
2use alloc::vec::Vec;
3use core::borrow::Borrow;
4use core::ops::{Index, IndexMut};
5
6impl<K, V> Default for VecMap<K, V> {
7    fn default() -> Self {
8        VecMap::new()
9    }
10}
11
12impl<K, V, Q> Index<&Q> for VecMap<K, V>
13where
14    K: Borrow<Q>,
15    Q: Eq + ?Sized,
16{
17    type Output = V;
18
19    fn index(&self, key: &Q) -> &V {
20        self.get(key).expect("VecMap: key not found")
21    }
22}
23
24impl<K, V, Q> IndexMut<&Q> for VecMap<K, V>
25where
26    K: Borrow<Q>,
27    Q: Eq + ?Sized,
28{
29    fn index_mut(&mut self, key: &Q) -> &mut V {
30        self.get_mut(key).expect("VecMap: key not found")
31    }
32}
33
34impl<K, V> Index<usize> for VecMap<K, V> {
35    type Output = V;
36
37    fn index(&self, index: usize) -> &V {
38        self.get_index(index)
39            .expect("VecMap: index out of bounds")
40            .1
41    }
42}
43
44impl<K, V> IndexMut<usize> for VecMap<K, V> {
45    fn index_mut(&mut self, index: usize) -> &mut V {
46        self.get_index_mut(index)
47            .expect("VecMap: index out of bounds")
48            .1
49    }
50}
51
52impl<K, V> Extend<(K, V)> for VecMap<K, V>
53where
54    K: Eq,
55{
56    fn extend<I>(&mut self, iterable: I)
57    where
58        I: IntoIterator<Item = (K, V)>,
59    {
60        self.base
61            .extend(iterable.into_iter().map(|(k, v)| crate::Slot::new(k, v)));
62    }
63}
64
65impl<'a, K: Clone + Eq, V: Clone> Extend<(&'a K, &'a V)> for VecMap<K, V> {
66    fn extend<I>(&mut self, iterable: I)
67    where
68        I: IntoIterator<Item = (&'a K, &'a V)>,
69    {
70        self.extend(
71            iterable
72                .into_iter()
73                .map(|(key, value)| (key.clone(), value.clone())),
74        );
75    }
76}
77
78impl<'a, K: Clone + Eq, V: Clone> Extend<&'a (K, V)> for VecMap<K, V> {
79    fn extend<I>(&mut self, iterable: I)
80    where
81        I: IntoIterator<Item = &'a (K, V)>,
82    {
83        self.extend(
84            iterable
85                .into_iter()
86                .map(|(key, value)| (key.clone(), value.clone())),
87        );
88    }
89}
90
91impl<Item, K, V> FromIterator<Item> for VecMap<K, V>
92where
93    Self: Extend<Item>,
94{
95    fn from_iter<I: IntoIterator<Item = Item>>(iter: I) -> Self {
96        let mut map = VecMap::new();
97        map.extend(iter);
98        map
99    }
100}
101
102impl<K, V> From<Vec<(K, V)>> for VecMap<K, V>
103where
104    K: Eq,
105{
106    /// Constructs map from a vector of `(key → value)` pairs.
107    ///
108    /// When the input contains duplicate keys, the first insertion position is
109    /// kept and the last associated value wins — the same rule as
110    /// [`insert`][VecMap::insert], [`extend`][Extend::extend], and
111    /// [`FromIterator`].
112    ///
113    /// **Note**: This conversion has a quadratic complexity because the
114    /// conversion preserves order of elements while at the same time having to
115    /// make sure no duplicate keys exist. To avoid it, sort and deduplicate
116    /// the vector and use [`VecMap::from_vec_unchecked`] instead.
117    fn from(mut vec: Vec<(K, V)>) -> Self {
118        crate::dedup_keep_last_value(&mut vec, |lhs, rhs| lhs.0 == rhs.0);
119        // SAFETY: We've just deduplicated the elements.
120        unsafe { Self::from_vec_unchecked(vec) }
121    }
122}
123
124impl<K, V> From<&[(K, V)]> for VecMap<K, V>
125where
126    K: Clone + Eq,
127    V: Clone,
128{
129    fn from(slice: &[(K, V)]) -> Self {
130        VecMap::from_iter(slice)
131    }
132}
133
134impl<K, V> From<&mut [(K, V)]> for VecMap<K, V>
135where
136    K: Clone + Eq,
137    V: Clone,
138{
139    fn from(slice: &mut [(K, V)]) -> Self {
140        // False-positive, we're re-slicing on purpose to go from `&mut [(K, V)]` to `&[(K, V)]`.
141        #[allow(clippy::redundant_slicing)]
142        VecMap::from_iter(&slice[..])
143    }
144}
145
146impl<K, V, const N: usize> From<[(K, V); N]> for VecMap<K, V>
147where
148    K: Eq,
149{
150    fn from(arr: [(K, V); N]) -> Self {
151        VecMap::from_iter(arr)
152    }
153}
154
155impl<K, V> PartialEq for VecMap<K, V>
156where
157    K: Eq,
158    V: PartialEq,
159{
160    fn eq(&self, other: &Self) -> bool {
161        self.base == other.base
162    }
163}
164
165impl<K, V> Eq for VecMap<K, V>
166where
167    K: Eq,
168    V: Eq,
169{
170}
171
172#[cfg(test)]
173mod test {
174    use super::*;
175    extern crate alloc;
176    use alloc::vec;
177
178    fn map_via_inserts<'a>(pairs: &[(&'a str, i32)]) -> VecMap<&'a str, i32> {
179        let mut map = VecMap::new();
180        for &(key, value) in pairs {
181            map.insert(key, value);
182        }
183        map
184    }
185
186    #[test]
187    fn constructor_parity_with_insert() {
188        let input = vec![("a", 1), ("b", 2), ("a", 3)];
189        let expected = map_via_inserts(&[("a", 1), ("b", 2), ("a", 3)]);
190
191        assert_eq!(VecMap::from(input.clone()), expected);
192        assert_eq!(input.into_iter().collect::<VecMap<_, _>>(), expected);
193        assert_eq!(VecMap::from([("a", 1), ("b", 2), ("a", 3)]), expected);
194        assert_eq!(expected.get(&"a"), Some(&3));
195        assert_eq!(expected.as_slice(), &[("a", 3), ("b", 2)]);
196    }
197
198    #[test]
199    fn extend_parity_with_insert() {
200        let mut via_extend = VecMap::new();
201        via_extend.extend([("a", 1), ("b", 2), ("a", 3)]);
202
203        let via_insert = map_via_inserts(&[("a", 1), ("b", 2), ("a", 3)]);
204        assert_eq!(via_extend, via_insert);
205    }
206
207    #[test]
208    fn insert_at_existing_key() {
209        let mut map = VecMap::from([("a", 1), ("b", 2), ("c", 3)]);
210        assert_eq!(map.insert_at(3, "a", 4), Some((0, 1)));
211        assert_eq!(map.as_slice(), &[("b", 2), ("c", 3), ("a", 4)]);
212        assert_eq!(map.insert_at(3, "a", 5), Some((2, 4)));
213        assert_eq!(map.as_slice(), &[("b", 2), ("c", 3), ("a", 5)]);
214        assert_eq!(map.insert_at(1, "a", 6), Some((2, 5)));
215        assert_eq!(map.as_slice(), &[("b", 2), ("a", 6), ("c", 3)]);
216    }
217
218    #[test]
219    #[should_panic(expected = "should be <= len")]
220    fn insert_at_existing_key_out_of_bounds() {
221        let mut map = VecMap::from([("a", 1), ("b", 2)]);
222        map.insert_at(3, "a", 3);
223    }
224
225    #[test]
226    fn eq() {
227        assert_ne!(VecMap::from([("a", 1)]), VecMap::from([]));
228        assert_ne!(VecMap::from([("a", 1)]), VecMap::from([("b", 2)]));
229        assert_eq!(VecMap::from([("a", 1)]), VecMap::from([("a", 1)]));
230        assert_ne!(VecMap::from([("a", 1)]), VecMap::from([("a", 1), ("b", 2)]));
231        assert_eq!(
232            VecMap::from([("a", 1), ("b", 2)]),
233            VecMap::from([("a", 1), ("b", 2)])
234        );
235        assert_eq!(
236            VecMap::from([("a", 1), ("b", 2)]),
237            VecMap::from([("b", 2), ("a", 1)])
238        );
239    }
240}
vecmap/map/impls.rs

vecmap/map/
impls.rs
