CODEWITHSUNDEEP
c++performancedictionary
Duck Dodgers
Duck Dodgers

Reputation: 339

Efficiently check element exists in map c++

I am aware of the .find() method to check whether or not an element exists in a map. But suppose i have a map -- map -- with about 2000 elements and I want to add an element to the list. I first have to check if the element exists. Isn't it a bit inefficient to use .find() because the iterator has to 'iterate' over element in the map? Is there a more efficient and less time consuming way to check whether or not an element exists in a map?

Upvotes: 1

Views: 617

Answers (2)

SergeyA
SergeyA

Reputation: 62563

If you really need to use 'find and insert' idiom (and that could be because you can't construct a value object for the same key twice under any circumstances) and you are concerned about twice logarithmic complexity, you'd have to use std::map::equal_range.

The way to do this would be first use equal_range with your key, and than use one of returned iterators as a hint to insert.

Upvotes: 0

juanchopanza
juanchopanza

Reputation: 227390

std::map has logarithmic look-up complexity, so you won't have to visit all the elements to determine whether an element is in the map.

On the other hand, you can make the look-up and insert operation more concise by using std::map::emplace or std::map::insert:

auto [iter, ok] = the_map.emplace(the_key, a_value);
if (ok) {
  // element was not in map so got inserted
}

This assumes that a_value either already exists, or that it is not an issue to construct it even if it does not end up being inserted into the map.

Upvotes: 3

Related Questions