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

[Siapran]

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]

Actually the equality comparison would just be

return impl_.template equals<equal_key>(other.impl_);

[arximboldi]

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]

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]

You're right about values.