3 ms·
Very interesting. This makes it sound like there should be a way to control `std::lower_bound` to switch to linear probing once it's narrowed the range down eno
by BenFrantzDale 8y ago
Very interesting. This makes it sound like there should be a way to control `std::lower_bound` to switch to linear probing once it's narrowed the range down enough. (In the specific example, "enough" is about 125 elements.)
Likewise for a hash table with separate chaining, wouldn't one better-than `std::unordered_set` way to do it be to keep the separate chains as a `std::vector` that is kept sorted, and then use `std::lower_bound` (or the above better version of it) to probe the table? Those separate tables are O(1) in size, so lookup and insertion are still O(1) on average. Worst case goes to O(n log n), but that doesn't seem too bad.
Related: Is there a widely-used "frozen set" C++ data structure? I'm picturing something that is constructed from a sequence but that internally is a sorted `std::vector<T>` that provides a set-like API but that uses `std::lower_bound` to find data. It's easy enough to write, but it seems like it should be in the standard or at least Boost.
- InfamousRece 8y agoThere is one in boost: https://www.boost.org/doc/libs/1_68_0/doc/html/container/non_standard_containers.html#container.non_standard_containers.flat_xxx https://www.boost.org/doc/libs/1_68_0/doc/html/container/non...
- BenFrantzDale 8y agoNice! https://www.boost.org/doc/libs/1_50_0/doc/html/boost/container/flat_set.html https://www.boost.org/doc/libs/1_50_0/doc/html/boost/contain... and https://www.boost.org/doc/libs/1_65_1/doc/html/boost/container/flat_map.html https://www.boost.org/doc/libs/1_65_1/doc/html/boost/contain... for reference.
- BenFrantzDale 8y agoInterestingly, when I dig deep into `find`, I wind up in `priv_lower_bound` which bisects to the bitter end rather than doing a linear find at the end. https://www.boost.org/doc/libs/1_50_0/boost/container/detail/flat_tree.hpp https://www.boost.org/doc/libs/1_50_0/boost/container/detail...
- yoklov 8y agoImplementing unordered map/set that way looses iterator/pointer stability, which is guaranteed by the current impl, unfortunately