Why does reusing std::map.find's returned iterator on an erased entry give a valid key and random value?

Question

I encountered a problem in my code, where I used the following sequence of map methods find(k), erase(k), find(k) and both times accessed the find's returned iterators first and second members.

This tought me to check properly against map.find(k) == map.end(). But what is happening behind the scenes if this is omitted?

Even though comparing find's returned iterator to .end() evaluates to true, it.first (old key) and it.second (random value) are still accessible.

Compiler version: g++ (Ubuntu 8.4.0-1ubuntu1~18.04) 8.4.0

Minimal working example

#include <stdio.h>
#include <map>

int main(int argc, char const *argv[])
{
  std::map<size_t, size_t> test_map;
  test_map.insert(std::pair<size_t, size_t>(1,2));
  test_map.insert(std::pair<size_t, size_t>(2,1));

  printf("map<size_t, size_t> with %lu key-value pairs: (1,2) and (2,1). 
    Iterating over map:\n", test_map.size());

  for (const auto &it : test_map)
  {
    printf("entry found - k: %lu, v: %lu\n", it.first, it.second);
  }

  size_t a = test_map.find(1)->first;
  size_t b = test_map.find(1)->second;
  printf("Called map.find(1): entry found - k: %lu, v: %lu\n", a, b);

  test_map.erase(1);
  printf("Called map.erase(1)\n");

  if(test_map.find(1) == test_map.end())
    printf("map.find(1) == test_map.end()\n");

  if(test_map.find(2) == test_map.end())
    printf("map.find(2) == test_map.end()\n");

  size_t c = test_map.find(1)->first;
  size_t d = test_map.find(1)->second;
  printf("Called map.find(1): entry found - k: %lu, v: %lu\n", c, d);

  printf("Iterating over map again:\n");
  for (const auto &it : test_map)
  {
    printf("entry found - k: %lu, v: %lu\n", it.first, it.second);
  }

  return 0;
}

Output

./map_test 
map<size_t, size_t> with 2 key-value pairs: (1,2) and (2,1). Iterating over map:
entry found - k: 1, v: 2
entry found - k: 2, v: 1
Called map.find(1): entry found - k: 1, v: 2
Called map.erase(1)
map.find(1) == test_map.end()
Called map.find(1): entry found - k: 1, v: 94380092077776 // k stays, v random
Iterating over map again:
entry found - k: 2, v: 1

It's [undefined behavior](https://en.cppreference.com/w/cpp/language/ub). Compilers can assume that you know what you're doing and would never dereference an invalid iterator, so when you do dereference an invalid iterator weird things can happen. — eesiraed, Apr 01 '20 at 18:35
That's nice of the compiler to hold me, the programmer, in such high regard. :) Is it the same behaviour as if freeing malloced space and accessing it afterwards? If so, any idea why the Key sticks to its old value and the Value doesn't? — Daniel, Apr 01 '20 at 18:45
Yes. I don't know exactly why you're getting that output, but analyzing why undefined behavior behaves a certain way usually isn't that useful. — eesiraed, Apr 01 '20 at 18:52
Thank your for your quick responses. Since it has been done in the comments, how should I conclude this SO question? — Daniel, Apr 01 '20 at 18:54
Honestly I probably should have posted my comment as an answer. If you want you can post an answer yourself and accept it. — eesiraed, Apr 01 '20 at 18:55
Relevant reading material: https://en.cppreference.com/w/cpp/language/ub read the linked to articles at the bottom as well. — Jesper Juhl, Apr 01 '20 at 19:08
@BessieTheCow Thank you, I will do that after a full night's sleep. — Daniel, Apr 01 '20 at 19:11

score 1 · Accepted Answer · edited Jun 20 '20 at 09:12

According to the documentation of std::map::end() (emphasis mine):

Returns an iterator to the element following the last element of the map.

This element acts as a placeholder; attempting to access it results in undefined behavior.

With reference to the Undefined Behavior:

Compilers are not required to diagnose undefined behavior (although many simple situations are diagnosed), and the compiled program is not required to do anything meaningful.

So, this is what you're seeing. The behavior is implementation-defined.

In your particular case of std::map, std::map::find() returns the iterator past-the-last-element and std::map::end() returns the same; hence, their comparison for testing.

The iterator past-the-last-element or std::map::end() returns a valid iterator but it is not dereferenceable. See: std::map::erase().

With reference to the Iterator Invalidation rules for associative containers, all the iterators are valid except the iterators/references to the erased element(s).

Read this SO thread for a summary of Iteration Invalidation (also, references to the relevant C++ standards' sections included).

Why does reusing std::map.find's returned iterator on an erased entry give a valid key and random value?

1 Answers1