c++ : filling map of maps via map instance allocation from a vector of maps

Question

part 2 to my : https://stackoverflow.com/questions/21780627/c-map-of-maps-typedef-doubts-queries

I then move ahead to create vectors (resizeable) of InnerMap, MiddlMap and do the following:

InnerMap inmap;
vector<InnerMap> vec_inmap;
vec_inmap.resize (8);
int vec_inmap_sz = 8;
vec_inmap.insert (vec_inmap.end (), 8, inmap);
vector<InnerMap>::iterator vec_inmap_it = vec_inmap.begin ();
InnerMap::iterator inmap_it;

MiddlMap mdmap, curr_mdmap;
vector<MiddlMap> vec_mdmap;
vec_mdmap.resize (8);
int vec_mdmap_sz = 8;
vec_mdmap.insert (vec_mdmap.end (), 8, mdmap);
vector<MiddlMap>::iterator vec_mdmap_it = vec_mdmap.begin ();
MiddlMap::iterator mdmap_it;

OuterMap otmap;
OuterMap::iterator otmap_it;

i.e. I store (empty) copies of inmap and mdmap (Q. is it that these copies are by reference ?) in the respective vectors, and then pick up these later from the vectors through the respective vector iterators, and then fill the maps accordingly. Here is how:

for (i = 0; i != trainSize; i++) {
...
if (curr_key_otmap != int_key) {
    otmap[int_key] = *vec_mdmap_it;
    vec_mdmap_it++;
    mdmap_count++;
    if (mdmap_count == vec_mdmap_sz) {
        vec_mdmap_sz += 8;
        vec_mdmap.resize (vec_mdmap_sz);
        vec_mdmap.insert (vec_mdmap.end(), 8, mdmap);
    }
    curr_key_otmap = int_key;
    curr_mdmap = otmap[curr_key_otmap];
}

mdmap_it = curr_mdmap.find (int_val);
if (mdmap_it == curr_mdmap.end ()) {
    curr_mdmap[int_val] = *vec_inmap_it;       <--
    curr_mdmap[int_val][char_str] = 1;

    vec_inmap_it++;
    inmap_count++;

    if (inmap_count == vec_inmap_sz) {
        vec_inmap_sz += 8;
        vec_inmap.resize (vec_inmap_sz);
        vec_inmap.insert (vec_inmap.end(), 8, inmap);
    }
} else {
    inmap_it = (*mdmap_it).second.find (char_str);
    if (inmap_it == (*mdmap_it).second.end ()) {
        (*mdmap_it).second[char_str] = 1;
    } else {
        (*mdmap_it).second[char_str] += 1;
    }
}
...
} //for ends

over the course of run time .. i get the following error at the <--ed line: could someone elaborate?

Program received signal SIGSEGV, Segmentation fault.
0x0804f9d4 in __gnu_cxx::new_allocator<std::pair<char* const, int> >::construct (this=0xbffff06f, __p=0x8057428, __val=...)
at /usr/include/c++/4.6/ext/new_allocator.h:108
108       { ::new((void *)__p) _Tp(__val); }


#0    0x0804fa2a in __gnu_cxx::new_allocator<std::pair<char* const, int> >::construct (this=0xbffff1bf, __p=0x8057428, __val=...)
at /usr/include/c++/4.6/ext/new_allocator.h:108
#1  0x0804f3e4 in std::_Rb_tree<char*, std::pair<char* const, int>, std::_Select1st<std::pair<char* const, int> >, std::less<char*>, std::allocator<std::pair<char* const, int> > >::_M_create_node (this=0x8098d1c, __x=...) at /usr/include/c++/4.6/bits/stl_tree.h:381
#2  0x0804e25f in std::_Rb_tree<char*, std::pair<char* const, int>, std::_Select1st<std::pair<char* const, int> >, std::less<char*>, std::allocator<std::pair<char* const, int> > >::_M_clone_node (this=0x8098d1c, __x=0xfffffffd) at /usr/include/c++/4.6/bits/stl_tree.h:427
#3  0x0804c645 in std::_Rb_tree<char*, std::pair<char* const, int>, std::_Select1st<std::pair<char* const, int> >, std::less<char*>, std::allocator<std::pair<char* const, int> > >::_M_copy (this=0x8098d1c, __x=0xfffffffd, __p=0x8098d20) at /usr/include/c++/4.6/bits/stl_tree.h:1036
#4  0x0804bda5 in std::_Rb_tree<char*, std::pair<char* const, int>, std::_Select1st<std::pair<char* const, int> >, std::less<char*>, std::allocator<std::pair<char* const, int> > >::operator= (this=0x8098d1c, __x=...) at /usr/include/c++/4.6/bits/stl_tree.h:945
#5  0x0804a714 in std::map<char*, int, std::less<char*>, std::allocator<std::pair<char* const, int> > >::operator= (this=0x8098d1c, __x=...)
at /usr/include/c++/4.6/bits/stl_map.h:255
#6  0x080493ff in MyProg::classify (trainData=..., testsData=...) at my_prog.cpp:83 <-- this is the line I marked
#7  0x08049c72 in main () at my_prog.cpp:200

Please ask me for edits/clarifications if anything is undecipherable.

Answer 1

When you resize a vector, all iterators to that vector become invalid unless that space was already allocated with vector::reserve before the iterators were created. This is because if there is no available memory after currently allocated block, the data will be copied elsewhere. If the relocation happens, on next iteration, vec_inmap_it will then be pointing to unallocated memory that may have been overwritten. Thus undefined behaviour.

// inside for loop
if (mdmap_it == curr_mdmap.end ()) {
    curr_mdmap[int_val] = *vec_inmap_it; // here you dereference vec_inmap_it
    curr_mdmap[int_val][char_str] = 1;

    vec_inmap_it++;
    inmap_count++;

    if (inmap_count == vec_inmap_sz) {
        vec_inmap_sz += 8;
        vec_inmap.resize (vec_inmap_sz); // here you resize the vector, vec_inmap_it is now invalid
        vec_inmap.insert (vec_inmap.end(), 8, inmap);
    }
...

Answer 2

You know what, your code is too big that i can't get it all but i think you should have this

 vector<InnerMap*>::iterator vec_inmap_it = vec_inmap.begin ();
 //instead of 
 vector<InnerMap>::iterator vec_inmap_it = vec_inmap.begin ();

try it