stlkrn icon indicating copy to clipboard operation
stlkrn copied to clipboard

Implement unordered container support, xhash no floating point

Open jxy-s opened this issue 2 years ago • 1 comments

This PR will add support for unordered containers (unordered_map, unordered_multimap, unordered_set, and unordered_multiset).

To do this I must patch xhash from the MSVC STL to eliminate the floating point arithmetic. I do this by copying xhash out of the MSVC STL and applying changes under the _XHASH_NO_FLOATING_POINT define. I then directly include the patched version through jxy/unordered_map.hpp and jxy/unordered_set.hpp defining _XHASH_NO_FLOATING_POINT to 1 before doing so.

The solution here isn't ideal. I would much rather PR this into MSVC directly. I have a branch that does this for MSVC (https://github.com/microsoft/STL/compare/main...jxy-s:xhash-no-floating-point) and I will engage with the MSVC community on it. However, the likelihood of this happening in a timely manner (if at all) is slim - it is, understandably, simply not a priority for them.

jxy-s avatar Sep 18 '21 18:09 jxy-s

MSVC STL's hash containers are currently implemented in a bad manner - e.g. the are base on doubly linked lists while singly linked lists are preferred. Unfortunately, we can't achieve improvement in representation at this moment due to ABI compatibility.

It seems to me that the switching to return uint64_t for load_factor() is already ABI-breaking (and... non-conforming). So given ABI compatibility with the existing MSVC STL is not (and probably shouldn't be) concerned, I think it's better not to resue MSVC STL's <xhash> - or at least to resuse it with more changes.

frederick-vs-ja avatar Jan 13 '24 06:01 frederick-vs-ja