vector_map/
lib.rs

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

vector_map/
lib.rs
