News for hackers. Stuff that matters.
Re:Effortless Performance Improvements in C++: std:unordered... by sicp-enjoyer on Thursday March 02, 2023 @07:53AM (#34995060)
> so hash map will generally be faster in this regard.

Complexity is not a measure of runtime. The performance drawbacks for std::map have to do with cache, not O(log) vs O(1). log(billion) is 30. And that's exactly how many comparisons you have to do, not a constant multiple of that.

With an open addressing hash table, who knows how many steps you will need to find an element. It's even more questionable if it does linked list chaining.

> binary search tree.

It's usually a red black tree and maybe could be a b-tree? "Search tree" is accurate.

Re:Effortless Performance Improvements in C++: std:unordered... by masklinn on Thursday March 02, 2023 @08:14AM (#34995228)
> maybe could be a b-tree?

IIRC the complexity requirements of std::map preclude a b-tree (or require a binary tree). Though I don't remember the exact reasoning.

abseil's website makes the same claim, though also without justification:

> B-trees have a different implementation from STL std::map containers, which require binary trees commonly implemented as red-black trees.

Re:Effortless Performance Improvements in C++: std:unordered... by powersnail on Thursday March 02, 2023 @11:14AM (#34997612)
> It's usually a red black tree and maybe could be a b-tree? "Search tree" is accurate.

I mean, I haven’t write red black trees for a while, but it is a type of binary search tree, as far as I remember, isn’t it?

Re:Effortless Performance Improvements in C++: std:unordered... by sicp-enjoyer on Thursday March 02, 2023 @08:57PM (#35004870)
You are correct. Sorry if I am being pedantic. I was also trying to suggest it could be a b-tree but others have pointed out that it doesn't quite fit the spec.