Alternative to multi_map (not multimap)

help
1

Crate "multi_map", which is 2 indices, one data item (not "multimap", which is one index with duplicates allowed) has just the semantics I need. Except for one thing. It doesn't have a "retain" iterator, for when I need to make a pass over all the data and discard some of it. So I have to write

pub fn garbage_collect(&mut self) {
        //  INEFFICIENT There is no "retain" function for multi-maps.
        //  So we have to do this the hard way.
        let key1_to_delete: Vec<K1> = self.cache.iter().filter(|(k1,(k2,v))| !v.retain()).map(|(k1,(k2,v))| k1.clone()).collect();
        for k1 in key1_to_delete { let _ = self.cache.remove(&k1); }
    }

which is O(N log N)) instead of O(N), because it makes one linear pass to find the items to delete, then deletes them with a hash lookup for each one.

multi_map isn't used much, and it was never really finished. Suggested alternatives?

2

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.