orlp / slotmap

Slotmap data structure for Rust
zlib License
1.12k stars 70 forks source link

Can iterators of SlotMap and SecondaryMap safely be joined? #121

Open NeverGivinUp opened 5 months ago

NeverGivinUp commented 5 months ago

Iterators very explicitly say, that the visit key-value pairs "in arbitrary order". Is this "arbitrary order" consistent between a SlotMapand its dependent SecondaryMaps, so they can be joined (assuming they contain exactly the same keys in the same version)?

Is the following guaranteed to work, or is it working just an accident?

        let mut a = SlotMap::new();
        let mut b = SecondaryMap::new();
        let mut c = SecondaryMap::new();

        let idx0 = a.insert(0);
        let idx1 = a.insert(1);
        let idx2 = a.insert(2);

        b.insert(idx0, 0);
        b.insert(idx1, 1);
        b.insert(idx2, 2);

        c.insert(idx0, 0);
        c.insert(idx1, 1);
        c.insert(idx2, 2);

        c.remove(idx1);
        b.remove(idx1);
        a.remove(idx1);

        for (((a_key, a_val), (b_key, b_val)), (c_key, c_val)) in a.iter().zip(b.iter_mut()).zip(c.iter()) {
            assert_eq!(a_key, b_key);
            assert_eq!(a_key, c_key);
            assert_eq!(a_val, b_val);
            assert_eq!(a_val, c_val);
        }
orlp commented 2 months ago

At the moment this is not guaranteed but should work. For a DenseSlotMap it won't work. I'd like to guarantee this actually works in slotmap 2.0.

NeverGivinUp commented 2 months ago

That's great. Indexing in a FxHashMap with slot-map keys is about the same speed as indexing in a SecondaryMap. But iterating a SecondaryMap is so much faster than iterating a FxHashMap. Since performance is the only reason I use slot-maps not having to index into a secondary map while iterating is very important for me. Looking forward to slotmap 2.0, then. Do you already have any estimates wtr. publication date and the amount of API changes?