vector_map/
lib.rs

1#![no_std]
2#[cfg(feature = "serde_impl")]
3pub mod serde;
4pub mod set;
5
6use core::{
7    iter::FromIterator,
8    ops::{Index, IndexMut},
9};
10
11extern crate alloc;
12
13use alloc::vec::{self, Vec};
14
15/// A std::vec::Vec based Map, motivated by the fact that, for some key types,
16/// iterating over a vector can be faster than other methods for small maps.
17///
18/// Most of the operations on this map implementation work in O(n), including
19/// some of the ones that are O(1) in HashMap. However, optimizers can work magic with
20/// contiguous arrays like Vec, and so for small sets (up to 256 elements for integer keys,
21/// for example), iterating through a vector actually yields better performance than the
22/// less branch- and cache-predictable hash maps.
23///
24/// To keep item removal fast, this container doesn't form guaranties on item ordering,
25/// nor on the stability of the ordering.
26///
27/// The good news about that is that you're free to mutate keys if your use-case requires that,
28/// though I wouldn't recommend it: the underlying vector can be accessed through the unsafe part
29/// of the API, in hopes to discourage you from using it.
30///
31/// Checking equality between maps is defined as "both maps are the same set", and performs worst
32/// for maps that are permutations of each other.
33#[derive(Clone)]
34pub struct VecMap<K, V> {
35    keys: Vec<K>,
36    values: Vec<V>,
37}
38
39// #[invariant(self.keys.len() == self.values.len())]
40impl<K, V> VecMap<K, V> {
41    pub fn new() -> Self
42    where
43        K: PartialEq,
44    {
45        Self::with_capacity(0)
46    }
47
48    pub fn with_capacity(capacity: usize) -> Self
49    where
50        K: PartialEq,
51    {
52        VecMap {
53            keys: Vec::with_capacity(capacity),
54            values: Vec::with_capacity(capacity),
55        }
56    }
57
58    pub fn len(&self) -> usize {
59        self.keys.len()
60    }
61
62    pub fn is_empty(&self) -> bool {
63        self.len() == 0
64    }
65
66    pub fn capacity(&self) -> usize {
67        self.keys.capacity().min(self.values.capacity())
68    }
69
70    pub fn clear(&mut self) {
71        self.keys.clear();
72        self.values.clear();
73    }
74
75    #[inline]
76    fn position<Q: PartialEq<K> + ?Sized>(&self, key: &Q) -> Option<usize> {
77        self.keys.iter().position(|k| key == k)
78    }
79
80    pub fn contains_key<Q: PartialEq<K> + ?Sized>(&self, key: &Q) -> bool {
81        self.position(key).is_some()
82    }
83
84    pub fn get<'l, Q: PartialEq<K> + ?Sized>(&'l self, key: &Q) -> Option<&'l V> {
85        self.position(key).map(|p| &self.values[p])
86    }
87
88    pub fn get_mut<'l, Q: PartialEq<K> + ?Sized>(&'l mut self, key: &Q) -> Option<&'l mut V> {
89        self.position(key).map(move |p| &mut self.values[p])
90    }
91
92    pub fn insert(&mut self, key: K, mut value: V) -> Option<V>
93    where
94        K: PartialEq,
95    {
96        if let Some(position) = self.position(&key) {
97            core::mem::swap(&mut value, &mut self.values[position]);
98            Some(value)
99        } else {
100            self.keys.push(key);
101            self.values.push(value);
102            None
103        }
104    }
105
106    pub fn drain(&mut self) -> Drain<'_, K, V> {
107        Drain {
108            iter: self.keys.drain(..).zip(self.values.drain(..)),
109        }
110    }
111
112    pub fn reserve(&mut self, additional: usize) {
113        self.keys.reserve(additional);
114        self.values.reserve(additional);
115    }
116
117    pub fn shrink_to_fit(&mut self) {
118        self.keys.shrink_to_fit();
119        self.values.shrink_to_fit();
120    }
121
122    pub fn get_key_value<'l, Q: PartialEq<K> + ?Sized>(
123        &'l self,
124        key: &Q,
125    ) -> Option<(&'l K, &'l V)> {
126        self.position(key).map(|p| (&self.keys[p], &self.values[p]))
127    }
128
129    pub fn remove<Q: PartialEq<K> + ?Sized>(&mut self, key: &Q) -> Option<V> {
130        if let Some(index) = self.position(key) {
131            self.keys.swap_remove(index);
132            Some(self.values.swap_remove(index))
133        } else {
134            None
135        }
136    }
137
138    pub fn entry(&mut self, key: K) -> Entry<'_, K, V>
139    where
140        K: PartialEq,
141    {
142        match self
143            .keys()
144            .enumerate()
145            .find(|(_, k)| &&key == k)
146            .map(|(n, _)| n)
147        {
148            Some(index) => Entry::Occupied(OccupiedEntry { map: self, index }),
149            None => Entry::Vacant(VacantEntry { map: self, key }),
150        }
151    }
152
153    pub fn remove_entry<Q: PartialEq<K> + ?Sized>(&mut self, key: &Q) -> Option<(K, V)> {
154        if let Some(index) = self.position(key) {
155            Some((self.keys.swap_remove(index), self.values.swap_remove(index)))
156        } else {
157            None
158        }
159    }
160
161    pub fn retain<F: FnMut(&K, &mut V) -> bool>(&mut self, mut f: F) {
162        for i in (0..self.len()).rev() {
163            if !f(&self.keys[i], &mut self.values[i]) {
164                self.keys.swap_remove(i);
165                self.values.swap_remove(i);
166            }
167        }
168    }
169
170    pub fn iter(&self) -> Iter<'_, K, V> {
171        Iter {
172            iter: self.keys.iter().zip(self.values.iter()),
173        }
174    }
175
176    pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
177        IterMut {
178            iter: self.keys.iter().zip(self.values.iter_mut()),
179        }
180    }
181
182    pub fn sort(&mut self)
183    where
184        K: Ord,
185    {
186        let mut indices: Vec<usize> = (0..self.len()).collect();
187        indices.sort_unstable_by_key(|i| &self.keys[*i]);
188        reorder_vec(&mut self.keys, indices.iter().copied());
189        reorder_vec(&mut self.values, indices.iter().copied());
190    }
191
192    /// Much faster than `self == other`, but will return false if the order of the data isn't identical.
193    /// # Safety
194    /// Note that for the order of data with two `VecMap`s to be identical, they must either have been both sorted,
195    /// or they must have undergone the insertion and removal of keys in the same order.
196    pub unsafe fn identical(&self, other: &Self) -> bool
197    where
198        K: PartialEq,
199        V: PartialEq,
200    {
201        self.keys == other.keys && self.values == other.values
202    }
203
204    pub fn keys(&self) -> Keys<'_, K, V> {
205        Keys {
206            iter: self.keys.iter(),
207            _phantom: Default::default(),
208        }
209    }
210
211    pub fn values(&self) -> Values<'_, K, V> {
212        Values {
213            iter: self.values.iter(),
214            _phantom: Default::default(),
215        }
216    }
217
218    /// Returns a slice containing all keys in the map.
219    ///
220    /// The order is arbitrary and may change when items are inserted or removed.
221    #[cfg(feature = "expose_pair_of_slices")]
222    pub fn keys_as_slice(&self) -> &[K] {
223        &self.keys
224    }
225
226    /// Returns a slice containing all values in the map.
227    ///
228    /// The order is arbitrary and may change when items are inserted or removed.
229    #[cfg(feature = "expose_pair_of_slices")]
230    pub fn values_as_slice(&self) -> &[V] {
231        &self.values
232    }
233
234    /// Returns a mutable slice containing all values in the map.
235    ///
236    /// The order is arbitrary and may change when items are inserted or removed.
237    #[cfg(feature = "expose_pair_of_slices")]
238    pub fn values_as_slice_mut(&mut self) -> &mut [V] {
239        &mut self.values
240    }
241}
242
243impl<K: PartialEq, V> Default for VecMap<K, V> {
244    fn default() -> Self {
245        Self::new()
246    }
247}
248
249impl<K: core::fmt::Debug, V: core::fmt::Debug> core::fmt::Debug for VecMap<K, V> {
250    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
251        f.debug_map().entries(self.iter()).finish()
252    }
253}
254
255fn reorder_vec<T>(vec: &mut [T], order: impl Iterator<Item = usize>) {
256    use core::mem::MaybeUninit;
257    let mut buffer: Vec<MaybeUninit<T>> = vec.iter().map(|_| MaybeUninit::uninit()).collect();
258    for (from, to) in order.enumerate() {
259        core::mem::swap(&mut vec[to], unsafe { &mut *(buffer[from].as_mut_ptr()) });
260    }
261    for i in 0..vec.len() {
262        core::mem::swap(&mut vec[i], unsafe { &mut *(buffer[i].as_mut_ptr()) });
263    }
264}
265
266impl<K: PartialEq, V: PartialEq> PartialEq for VecMap<K, V> {
267    fn eq(&self, other: &Self) -> bool {
268        if self.len() != other.len() {
269            return false;
270        }
271        for (key, value) in self.iter() {
272            match other.get(key) {
273                Some(v) if value == v => {}
274                _ => return false,
275            }
276        }
277        true
278    }
279}
280
281impl<'a, K: PartialEq + Copy + 'a, V: Copy + 'a> Extend<(&'a K, &'a V)> for VecMap<K, V> {
282    fn extend<T: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: T) {
283        for (key, value) in iter.into_iter() {
284            self.insert(*key, *value);
285        }
286    }
287}
288
289impl<K: PartialEq, V> Extend<(K, V)> for VecMap<K, V> {
290    fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
291        for (key, value) in iter.into_iter() {
292            self.insert(key, value);
293        }
294    }
295}
296
297impl<K: PartialEq, V> FromIterator<(K, V)> for VecMap<K, V> {
298    fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
299        let iterator = iter.into_iter();
300        let lower = iterator.size_hint().0;
301        let mut this = Self::with_capacity(lower);
302        this.extend(iterator);
303        this
304    }
305}
306
307impl<'a, Q: PartialEq<K> + ?Sized, K, V> Index<&'a Q> for VecMap<K, V> {
308    type Output = V;
309    fn index(&self, key: &'a Q) -> &Self::Output {
310        self.get(key).unwrap()
311    }
312}
313
314impl<'a, Q: PartialEq<K> + ?Sized, K, V> IndexMut<&'a Q> for VecMap<K, V> {
315    fn index_mut(&mut self, key: &'a Q) -> &mut Self::Output {
316        self.get_mut(key).unwrap()
317    }
318}
319
320impl<'a, K, V> IntoIterator for &'a VecMap<K, V> {
321    type Item = (&'a K, &'a V);
322    type IntoIter = Iter<'a, K, V>;
323    fn into_iter(self) -> Self::IntoIter {
324        self.iter()
325    }
326}
327
328impl<'a, K, V> IntoIterator for &'a mut VecMap<K, V> {
329    type Item = (&'a K, &'a mut V);
330    type IntoIter = IterMut<'a, K, V>;
331    fn into_iter(self) -> Self::IntoIter {
332        self.iter_mut()
333    }
334}
335
336impl<K, V> IntoIterator for VecMap<K, V> {
337    type Item = (K, V);
338    type IntoIter = IntoIter<K, V>;
339    fn into_iter(self) -> Self::IntoIter {
340        IntoIter {
341            iter: self.keys.into_iter().zip(self.values),
342        }
343    }
344}
345
346#[derive(Clone)]
347pub struct IntoIter<K, V> {
348    iter: core::iter::Zip<vec::IntoIter<K>, vec::IntoIter<V>>,
349}
350
351impl<K, V> Iterator for IntoIter<K, V> {
352    type Item = (K, V);
353
354    fn next(&mut self) -> Option<(K, V)> {
355        self.iter.next()
356    }
357
358    fn size_hint(&self) -> (usize, Option<usize>) {
359        self.iter.size_hint()
360    }
361}
362
363impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
364    fn next_back(&mut self) -> Option<(K, V)> {
365        self.iter.next_back()
366    }
367}
368
369impl<K, V> ExactSizeIterator for IntoIter<K, V> {
370    fn len(&self) -> usize {
371        self.iter.len()
372    }
373}
374
375/// A view into a single occupied location in a `VecMap`.
376///
377/// See [`VecMap::entry`](struct.VecMap.html#method.entry) for details.
378pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
379    map: &'a mut VecMap<K, V>,
380    index: usize,
381}
382
383/// A view into a single vacant location in a `VecMap`.
384///
385/// See [`VecMap::entry`](struct.VecMap.html#method.entry) for details.
386pub struct VacantEntry<'a, K: 'a, V: 'a> {
387    map: &'a mut VecMap<K, V>,
388    key: K,
389}
390
391/// A view into a single entry in a `VecMap`.
392///
393/// See [`VecMap::entry`](struct.VecMap.html#method.entry) for details.
394pub enum Entry<'a, K: 'a, V: 'a> {
395    /// An occupied entry.
396    Occupied(OccupiedEntry<'a, K, V>),
397
398    /// A vacant entry.
399    Vacant(VacantEntry<'a, K, V>),
400}
401use Entry::*;
402impl<'a, K, V> Entry<'a, K, V> {
403    /// Ensures that the entry is occupied by inserting the given value if it is vacant.
404    ///
405    /// Returns a mutable reference to the entry's value.
406    pub fn or_insert(self, default: V) -> &'a mut V {
407        match self {
408            Occupied(entry) => entry.into_mut(),
409            Vacant(entry) => entry.insert(default),
410        }
411    }
412
413    /// Ensures that the entry is occupied by inserting the the result of the given function if it
414    /// is vacant.
415    ///
416    /// Returns a mutable reference to the entry's value.
417    pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
418        match self {
419            Occupied(entry) => entry.into_mut(),
420            Vacant(entry) => entry.insert(default()),
421        }
422    }
423
424    /// Ensures that the entry is occupied by inserting the default value if it is vacant.
425    ///
426    /// Returns a mutable reference to the entry's value.
427    pub fn or_default(self) -> &'a mut V
428    where
429        V: Default,
430    {
431        self.or_insert_with(Default::default)
432    }
433}
434
435impl<'a, K, V> OccupiedEntry<'a, K, V> {
436    /// Returns a reference to the entry's value.
437    pub fn get(&self) -> &V {
438        &self.map.values[self.index]
439    }
440
441    /// Returns a mutable reference to the entry's value.
442    pub fn get_mut(&mut self) -> &mut V {
443        &mut self.map.values[self.index]
444    }
445
446    /// Returns a mutable reference to the entry's value with the same lifetime as the map.
447    pub fn into_mut(self) -> &'a mut V {
448        &mut self.map.values[self.index]
449    }
450
451    /// Replaces the entry's value with the given one and returns the previous value.
452    pub fn insert(&mut self, value: V) -> V {
453        core::mem::replace(self.get_mut(), value)
454    }
455
456    /// Removes the entry from the map and returns its value.
457    pub fn remove(self) -> V {
458        self.map.keys.swap_remove(self.index);
459        self.map.values.swap_remove(self.index)
460    }
461}
462
463impl<'a, K, V> VacantEntry<'a, K, V> {
464    /// Inserts the entry into the map with the given value.
465    ///
466    /// Returns a mutable reference to the entry's value with the same lifetime as the map.
467    pub fn insert(self, value: V) -> &'a mut V {
468        self.map.keys.push(self.key);
469        self.map.values.push(value);
470        self.map.values.last_mut().unwrap()
471    }
472}
473
474/// A draining iterator over a `VecMap`.
475///
476/// See [`VecMap::drain`](struct.VecMap.html#method.drain) for details.
477pub struct Drain<'a, K: 'a, V: 'a> {
478    iter: core::iter::Zip<vec::Drain<'a, K>, vec::Drain<'a, V>>,
479}
480
481/// An iterator yielding references to a `VecMap`'s keys and their corresponding values.
482///
483/// See [`VecMap::iter`](struct.VecMap.html#method.iter) for details.
484#[derive(Clone)]
485pub struct Iter<'a, K: 'a, V: 'a> {
486    iter: core::iter::Zip<core::slice::Iter<'a, K>, core::slice::Iter<'a, V>>,
487}
488
489/// An iterator yielding references to a `VecMap`'s keys and mutable references to their
490/// corresponding values.
491///
492/// See [`VecMap::iter_mut`](struct.VecMap.html#method.iter_mut) for details.
493pub struct IterMut<'a, K: 'a, V: 'a> {
494    iter: core::iter::Zip<core::slice::Iter<'a, K>, core::slice::IterMut<'a, V>>,
495}
496
497/// An iterator yielding references to a `VecMap`'s keys in arbitrary order.
498///
499/// See [`VecMap::keys`](struct.VecMap.html#method.keys) for details.
500pub struct Keys<'a, K: 'a, V> {
501    iter: core::slice::Iter<'a, K>,
502    _phantom: core::marker::PhantomData<V>,
503}
504
505impl<'a, K, V> Clone for Keys<'a, K, V> {
506    fn clone(&self) -> Self {
507        Keys {
508            iter: self.iter.clone(),
509            _phantom: Default::default(),
510        }
511    }
512}
513
514/// An iterator yielding references to a `VecMap`'s values in arbitrary order.
515///
516/// See [`VecMap::values`](struct.VecMap.html#method.values) for details.
517pub struct Values<'a, K, V: 'a> {
518    iter: core::slice::Iter<'a, V>,
519    _phantom: core::marker::PhantomData<K>,
520}
521
522impl<'a, K, V> Clone for Values<'a, K, V> {
523    fn clone(&self) -> Self {
524        Values {
525            iter: self.iter.clone(),
526            _phantom: Default::default(),
527        }
528    }
529}
530
531macro_rules! impl_iter {
532    ($typ:ty, $item:ty) => {
533        impl<'a, K, V> Iterator for $typ {
534            type Item = $item;
535
536            fn next(&mut self) -> Option<Self::Item> {
537                self.iter.next()
538            }
539
540            fn size_hint(&self) -> (usize, Option<usize>) {
541                self.iter.size_hint()
542            }
543        }
544
545        impl<'a, K, V> DoubleEndedIterator for $typ {
546            fn next_back(&mut self) -> Option<Self::Item> {
547                self.iter.next_back()
548            }
549        }
550
551        impl<'a, K, V> ExactSizeIterator for $typ {
552            fn len(&self) -> usize {
553                self.iter.len()
554            }
555        }
556    };
557}
558impl_iter! {Drain<'a,K,V>,  (K,V)}
559impl_iter! {Iter<'a,K,V>,  (&'a K, &'a V)}
560impl_iter! {IterMut<'a,K,V>,  (&'a K, &'a mut V)}
561impl_iter! {Keys<'a,K,V>,  &'a K}
562impl_iter! {Values<'a,K,V>,  &'a V}
563
564#[test]
565fn reorder() {
566    let n = 128;
567    let m = 128;
568    let expected: Vec<usize> = (0..n).collect();
569    let mut test = expected.clone();
570    for _ in 0..m {
571        let rands: Vec<usize> = test.iter().map(|_| rand::random()).collect();
572        test.sort_by_key(|x| rands[*x]);
573        let mut indices: Vec<usize> = (0..test.len()).collect();
574        indices.sort_unstable_by_key(|i| test[*i]);
575        reorder_vec(&mut test, indices.into_iter());
576        assert_eq!(test, expected);
577    }
578    for _ in 0..m {
579        let mut map: VecMap<usize, f32> = VecMap::with_capacity(n);
580        for _ in 0..n {
581            map.insert(rand::random(), rand::random());
582        }
583        let clone = map.clone();
584        map.sort();
585        let mut map_iter = map.iter();
586        let first = *map_iter.by_ref().take(1).next().unwrap().0;
587        assert!(map_iter
588            .fold(Some(first), |acc, (k, _v)| {
589                let k = *k;
590                match acc {
591                    Some(v) if v < k => Some(k),
592                    _ => None,
593                }
594            })
595            .is_some());
596        assert_eq!(map, clone);
597    }
598}
599
600#[test]
601fn unsized_key_queries() {
602    let mut map = VecMap::<String, u8>::new();
603    map.insert("foo".to_owned(), 1);
604    map.insert("bar".to_owned(), 2);
605
606    assert_eq!(&map["bar"], &2);
607}
vector_map/lib.rs

vector_map/
lib.rs
