segmentation fault when deleting a map with struct being the keys

Question

In my code I have a struct that I use as a map key:

struct index{
  int x;
  int y;
  int z;
  bool operator<(const index &b){
    bool out = true;
    if ( x == b.x ){
      if ( y == b.y ){
        out = z < b.z;
      } else out = y < b.y;
    } else out = x < b.x;
    return out;
  }
};

and the map I use is:

map<index,set<std::pair<int, int> > > tBoxes;

When the program end it's run, and I it tries to free the memory, I get a segmentation fault when the program tries to delete the map. Using gdb I get:

#0  std::_Rb_tree<membrane::index, std::pair<membrane::index const, std::set<std::pair<int, int>, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > > >, std::_Select1st<std::pair<membrane::index const, std::set<std::pair<int, int>, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > > > >, std::less<membrane::index>, std::allocator<std::pair<membrane::index const, std::set<std::pair<int, int>, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > > > > >::_M_erase (this=0x63b900, 
    __x=0x404057eb274ede6c)
    at /usr/lib/gcc/x86_64-redhat-linux/4.1.2/../../../../include/c++/4.1.2/bits/stl_tree.h:1264
#1  0x000000000041ed2f in std::_Rb_tree<membrane::index, std::pair<membrane::index const, std::set<std::pair<int, int>, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > > >, std::_Select1st<std::pair<membrane::index const, std::set<std::pair<int, int>, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > > > >, std::less<membrane::index>, std::allocator<std::pair<membrane::index const, std::set<std::pair<int, int>, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > > > > >::_M_erase (
    this=0x63b900, __x=0x7d31110)
    at /usr/lib/gcc/x86_64-redhat-linux/4.1.2/../../../../include/c++/4.1.2/bits/stl_tree.h:1264
#2  0x000000000041ed2f in std::_Rb_tree<membrane::index, std::pair<membrane::index const, std::set<std::pair<int, int>, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > > >, std::_Select1st<std::pair<membrane::index const, std::set<std::pair<int, int>, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > > > >, std::less<membrane::index>, std::allocator<std::pair<membrane::index const, std::set<std::pair<int, int>, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > > > > >::_M_erase (
    this=0x63b900, __x=0x7d30e30)
    at /usr/lib/gcc/x86_64-redhat-linux/4.1.2/../../../../include/c++/4.1.2/bits/stl_tree.h:1264
#3  0x000000000041ed2f in std::_Rb_tree<membrane::index, std::pair<membrane::index const, std::set<std::pair<int, int>, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > > >, std::_Select1st<std::pair<membrane::index const, std::set<std::pair<int, int>, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > > > >, std::less<membrane::index>, std::allocator<std::pair<membrane::index const, std::set<std::pair<int, int>, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > > > > >::_M_erase (
    this=0x63b900, __x=0x7d30b50)
    at /usr/lib/gcc/x86_64-redhat-linux/4.1.2/../../../../include/c++/4.1.2/bits/stl_tree.h:1264
#4  0x000000000041ed2f in std::_Rb_tree<membrane::index, std::pair<membrane::index const, std::set<std::pair<int, int>, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > > >, std::_Select1st<std::pair<membrane::index const, std::set<std::pair<int, int>, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > > > >, std::less<membrane::index>, std::allocator<std::pair<membrane::index const, std::set<std::pair<int, int>, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > > > > >::_M_erase (
    this=0x63b900, __x=0x7d272c0)
    at /usr/lib/gcc/x86_64-redhat-linux/4.1.2/../../../../include/c++/4.1.2/bits/stl_tree.h:1264
#5  0x0000000000418237 in clear (this=0x63b3e0, 
    __in_chrg=<value optimized out>)
    at /usr/lib/gcc/x86_64-redhat-linux/4.1.2/../../../../include/c++/4.1.2/bits/stl_tree.h:692
#6  clear (this=0x63b3e0, __in_chrg=<value optimized out>)
    at /usr/lib/gcc/x86_64-redhat-linux/4.1.2/../../../../include/c++/4.1.2/bits/stl_map.h:501
#7  membrane::~membrane (this=0x63b3e0, __in_chrg=<value optimized out>)
    at memMC.cpp:135
#8  0x0000000000421658 in __tcf_5 () at main.cpp:7
#9  0x000000378ea334f5 in exit () from /lib64/libc.so.6
#10 0x000000378ea1d99b in __libc_start_main () from /lib64/libc.so.6
#11 0x0000000000402309 in _start ()

And using valgrind (running $valgrind -v --track-origins=yes --leak-check=yes --tool=massig --tool=memcheck --read-var-info=yes --log-file=error.txt ./mem) I get:

==2561==     in use at exit: 0 bytes in 0 blocks
==2561==   total heap usage: 3,346,323 allocs, 3,346,323 frees, 98,851,279 bytes allocated
==2561== 
==2561== All heap blocks were freed -- no leaks are possible
==2561== 
==2561== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 4 from 4)
--2561-- 
--2561-- used_suppression:      4 dl-hack3
==2561== 
==2561== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 4 from 4)

Which is annoying since it doesn't tell me anything.

I have tried to clear the map manually (while printing some output that may give some clues:

while (tBoxes.size() > 0){
   printf ("%i  ", (*tBoxes.begin()).first.x);
   printf ("%i  ", (*tBoxes.begin()).first.y);
   printf ("%i\n", (*tBoxes.begin()).first.z);
   while ((*tBoxes.begin()).second.size() > 0){
     printf ("a\n");      
     tgBit1 = (*tBoxes.begin()).second.begin();
     (*tBoxes.begin()).second.erase(tgBit1);
     printf ("b\n");
   }
   tBoxes.erase(tBoxes.begin());
 }
 tBoxes.clear();
 tNextBoxes.clear();

and all I could gather is that the delete crashes when I increment x to 1 from 0 and that It occur after I delete the content of the set.

Why is that happening and is there a way to clear a map apart from using clear()?

Edit:

I have found the bug. One of the vector I used was not set up correctly and in effect was of size 0. Yet, I still accessed element in that vector.

The vector is of double values and I use this value after dividing by a box size and rounding the result down to determine the tBox to put a pair in. I assume that I got an invalid value to use in the index. The question remains, why didn't the program crush when I tried to access this element...?

Answer 1

My guess is that there is some sort of heap/stack corruption occurring somewhere else in your program which only manifests itself when your map tries to access a bad pointer/iterator. Look at the last iterator that is erased (0x404057eb274ede6c) which looks suspicious compared with the previous iterator values (0x7d31110).

As to why Valgrind doesn't detect this corruption? I'm not very familiar with the tool but this question on SE points out another case where Valgrind fails to detect "obvious" bad behaviour and also suggests something else to help detect it.

I would try reducing the crash to as little code as possible. Create a small test case in another project and see if the crash still occurs. Run in debug mode and/or with additional memory checks to see if you can catch the memory corruption (assuming that's what it is).

Update for Edit:

Assuming you are using std::vector::operator[] then this method doesn't do any bounds checking and will happily let you try to access elements that don't exist. I believe this is specified to be undefined behaviour and, unfortunately, one possible result is that nothing happens.

If you wish or need to have bounds checking them use std::vector::at(), see this question for a few details. Typically you only use [] when you know the index used is in bounds, like in a iterative loop or when the index is checked manually.