1

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?

5
  • 10
    if (it == mymap.end()) mymap.erase (it); has undefined behavior. You are not allowed to erase end() Commented Aug 10, 2022 at 14:33
  • 1
    I mean technically, since both if statements do the same thing (and are inverse booleans), the code is logically equivalent to mymap.erase(it);.
    – Rogue
    Commented Aug 10, 2022 at 14:34
  • 1
    "When I tried to erase the value of d it does nothing" How did you determine that nothing was done? Commented Aug 10, 2022 at 14:35
  • What don't you understand? Do you know what the end iterator is in general? Do you know what find returns?
    – Useless
    Commented Aug 10, 2022 at 14:35
  • An iterator is an "object" (not necessarily a pointer) that traverses your data structure. The end() iterator represents a position "one beyond" the last element in your datastructure (sometimes a guard position) and thus is not part of your datastructure (and does not refer to anything valid). Trying to do something with the end() iterator (other then comparing) is a programming error. Commented Aug 10, 2022 at 14:36

1 Answer 1

6

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.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.