arximboldi / immer

Postmodern immutable and persistent data structures for C++ — value semantics at scale
https://sinusoid.es/immer
Boost Software License 1.0
2.51k stars 183 forks source link

Add a keys() method to immer::map. #154

Open Siapran opened 4 years ago

Siapran commented 4 years ago

Looking at my code, I end up needing to pass around collections of the keys of maps, without the values. Doing so right now is a O(n) operation, which is fine, I guess. But I believe it can be made into a O(1) operation easily.

Looking at the code, it looks like you could just return a sightly modified set with the same impl_, and change the project_value_ptr to return the first element of the original value pairs. Assuming the value_type of the original map is default constructible, you can just default construct the second element of the original value pairs for "mutating" operations. The only tricky part would be the equality comparison, since we're using the implementation's own diffing mechanism. Maybe fiddling around with the Equal and Hash parameters of hamts::champ to allow comparing for just the keys?

Siapran commented 4 years ago

Actually the equality comparison would just be

return impl_.template equals<equal_key>(other.impl_);
arximboldi commented 4 years ago

Hmm, that is possible and a good idea.

But be aware that the type of the return can not be set<K>, that would require some kind of non-cost-free type erasure. It thus needs to be something different (e.g. detail::key_set<K>). We could also do alike for values. Would that still be useful for you?

Siapran commented 4 years ago

oh yeah key_set is fine. how would that work for values though? keys have to be unique but values don't, how would that work with the shared implementation? you'd be able to iterate through it but I can't think of anything else off the top of my head...

arximboldi commented 4 years ago

You're right about values.