0

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?

michalt38
  • 1,193
  • 8
  • 17
  • 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 Jun 23 '20 at 22:58
  • see also https://en.cppreference.com/w/cpp/container/map and https://en.cppreference.com/w/cpp/container/unordered_map – Kenny Ostrom Jun 23 '20 at 23:01

1 Answers1

2

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.

Gamification
  • 787
  • 5
  • 20