[FIXED] What exactly happens when we write if(mp.find()==mp.end())

Issue

I'm currently learning hashmap, I'm facing trouble understanding the iterators, while using it in if statements.

For example,

int main ()
{
  std::map<char,int> mymap;
  std::map<char,int>::iterator it;
  mymap['a']=50;
  mymap['b']=100;
  mymap['c']=150;
  mymap['d']=200;

  it = mymap.find('d');
  if (it == mymap.end())
    mymap.erase (it);
  if (it != mymap.end())
    mymap.erase (it);
}
    

I am able to understand what happens in the second if statement. Can anyone explain what exactly does the first if statement will do? When I tried to erase the value of d it does nothing. Can someone explain the difference between the two if statements?

Solution

From std::map::erase

The iterator pos must be valid and dereferenceable. Thus the end() iterator (which is valid, but is not dereferenceable) cannot be used as a value for pos.

Since the below part of the code fails to comply with the above

if (it == mymap.end())
    mymap.erase (it);

the program will have undefined behavior in case it == mymap.end() - which means that it could do just about anything, including nothing or crashing. Avoid undefined behavior like the plague.

---

The other part is the correct way to do it. Make sure that it is not the end() iterator before using it to erase an element.

if (it != mymap.end())
    mymap.erase (it);

---

Can someone explain the difference between the two if statements?

it = mymap.find('d'); searches for 'd' in the map. If 'd' is found, it returns an iterator to the place in the map where the key 'd' was found. If 'd' is not found, it returns the end() iterator. The end() iterator in all standard containers (possible exception: basic_string), and even plain arrays, isn't dereferenceable. Using an array to illustrate:

int a[] = {7,8,9};

Memory layout:

addr   a+0 a+1 a+2 a+3
      +---+---+---+---
value | 7 | 8 | 9 | (out of bounds)
      +---+---+---+---
        ^           ^
        |           |
std::begin(a)   std::end(a)

The end() iterator for a plain array points one step after the last element and dereferencing it would mean that you peek out of bounds, with undefined behavior as a result. It's similar for maps, only that the memory layout isn't as simple as for plain arrays.

The difference between the two if statements is therefore that one makes sure that the iterator can be deferenced before using it to erase - and the other makes sure that the iterator is not an iterator that should be deferenced (or used with erase), before using it with erase anyway.

Answered By - Ted Lyngmo

Answer Checked By - David Marino (PHPFixing Volunteer)