How is map searching for value at a given key [duplicate]

Question

When I access a value in std::map at a given key, does the map search for this value linearly by checking each key-value pair if the key match or does it access the requested value directly?

An std::map would be implemented as a tree. It would search the tree using the comparator to know where to look, using the key. — ChrisMM
– ChrisMM, Commented Jun 23, 2020 at 22:58
see also en.cppreference.com/w/cpp/container/map and en.cppreference.com/w/cpp/container/unordered_map — Kenny Ostrom
– Kenny Ostrom, Commented Jun 23, 2020 at 23:01

Gamification · Accepted Answer · 2020-06-23 23:03:39Z

Neither. It will have to search through an index to find the value, but it will do that in a way, that is much more efficient than a linear search.

Typically, this is implemented using a Red-black tree and search time will be logarithmic to the number of elements in the map.

Collectives™ on Stack Overflow

How is map searching for value at a given key [duplicate]

1 Answer 1

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Linked

Related