[Bug libstdc++/25896] New: hash_map::erase, unordered_map::erase fail if key is inside the table

[mec at google dot com]

This happens with both hash_map and unordered_map and their related classes.  I
know that hash_map is not standard, and unordered_map is in TR1 so not
considered standard yet.

Here is a kernel of the problem:

  hash_map<string,int> c;
  c.insert(...);
  hash_map<string,int>::iterator it = c.find("...");
  c.erase(it->first);

This is deleting by key value, not by iterator.

it->first is a key value which belongs to the collection object.
hash_map::erase(const key&) takes the key by reference.  It delegates to its
rep object, which is a hashtable.  hashtable::ref looks like this in gcc 4.0.2:

  if (__first)
    {
      ...
      while (__next)
        {
          if (_M_equals(_M_get_key(__next->_M_val), __key))
            {
              ...
              _M_delete_node(__next);
              ...
            }
          ...
        }
     ...
    }

The actual key object is in a node of the hash table.  After deleting that
node, the while() loop keeps using the deleted __key value with every other
node in the same bucket.

The following gcc versions have this problem with the following classes:

  gcc 3.4.5
    hash_map, hash_multimap, hash_set, hash_multiset

  gcc 4.0.2
  gcc 4.1-20060106
  gcc 4.2-20060114
    hash_map, hash_multimap, hash_set, hash_multiset
    unordered_map, unordered_multimap, unordered_set, unordered_multiset

You could punt on hash_map and friends because they are non-standard, but it is
nasty to have a case where code compiles and links and runs and then a library
function reads a destroyed object.  unordered_map and friends will eventually
(probably) be standardized so they are more serious.


-- 
           Summary: hash_map::erase, unordered_map::erase fail if key is
                    inside the table
           Product: gcc
           Version: 4.0.2
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: mec at google dot com
 GCC build triplet: i686-pc-linux-gnu
  GCC host triplet: i686-pc-linux-gnu
GCC target triplet: i686-pc-linux-gnu


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=25896