range-based for loops

[jeychenne]

This is a minor thing, but it's been bugging me for a little while. One of the differences with std::unordered_map is that value_type is const std::pair<Key,T> instead of std::pair<const Key,T>. Iterators allow us to work around this with the value() method, which gives us a mutable reference to the mapped type.

This works fine with traditional for loops and iterators.

for (auto it = map.begin(); it != map.end(); ++it) {
    auto &second = it.value();
    ...
}

However, range-based for loops don't work as nicely, and AFAIK the only way to get a mutable reference to the mapped type in that case is to const_cast it:

for (auto &value : map) {
    auto &second = const_cast<T&>(value.second);
    ...
}

I'm sure there's a reason why value_type has to be const (sorry if I missed it), but it's a bit unfortunate that we can't use range-based for loops as straightfordwardly as with std::unordered_map. Apart from that, great library! 👍

[Tessil]

The hash map stores std::pair<Key, T> instead of std::pair<const Key, T> so that the move-constructor can be called on the pair when the pair is moved inside the bucket array (not a problem with std::unordered_map as they move a pointer to a node and not the pair itself).

Regarding the iterator, it can't just return a mutable reference to std::pair<Key, T> because the client may then changes the key and render the map inconsistent. That's why the iterator returns const std::pair<Key, T>& and why you have to use value().

I don't know if there is a better way to do it without invoking undefined behavior. I have to store std::pair<Key, T> but I can not return a std::pair<const Key, T>& as it isn't a well-defined behavior. I could just return a mutable reference std::pair<Key, T>& instead of a const reference and trust the user to not modify the Key, but I find it too dangerous.

[phonometrica]

Thanks for the explanation. Yes, returning a mutable key doesn't sound like a good idea... My naive approach would be to store the data as std::aligned_storage and reinterpret_cast it to the appropriate type (std::pair<Key,T> internally, std::pair<const Key, T> otherwise), but since you seem to be using std::aligned_storage internally, I guess that's an option that you considered and discarded. Would this be undefined behavior? I can't think of a reasonable compiler doing anything but the right thing in this case, since the only thing that changes is the constness of the key.

[Tessil]

From what I understand it would be an undefined behavior, see this Stack Overflow post. It would probably work on most compilers but I'd like to avoid any undefined behavior in the code.

I have to check a bit how other open-adressing implementations manage this problem.

[jeychenne]

That's interesting... Then the only thing I can think of is to represent the value as std::pair<const Key, T> and to const_cast the key when it's moved, but I don't know if it's a workable solution and it would involve moving the key and the mapped type separately.

[Tessil]

That would be undefined behaviour, if you're storing a const Key you can't cast away the const like that to create a Key&. When using const_cast the object of the reference/pointer must originally be stored in a non-const way.

[Tessil]

I'll close the issue as I think the current solution is the safest, but if someone come with a better way, feel free to comment.