[sicp-enjoyer]

> 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.

[masklinn]

> 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.

[powersnail]

> 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?

[sicp-enjoyer]

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.