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.

No, i guess. `#0` to `#7` are the errors I get .. from `gdb a.out` followed by `run` and `backtrace` — Sunil Kundal, Feb 14 '14 at 14:27
How much is `trainSize`? If it is more than 8 then `vec_mdmap_it` will go beyond `vec_mdmap` borders. If it is less than or equal to 8, are you sure that `vec_mdmap_it` isn't avanced elsewhere inside the for loop? — eerorika, Feb 14 '14 at 15:12
`trainsize` could be 5000, but I clearly update the `vec_mdmap_sz` and also add new copies of `mdmap` to the extended portion of `vec_mdmap` AFAIK — Sunil Kundal, Feb 14 '14 at 15:14
I think there might be a problem with your initialization of `vector`. I _think_ what you are trying to do is initialize each `vector` with 8 copies of a default-constructed `InnerMap` or `MiddleMap`. If that's the case, it will suffice to have `vector vec_inmap(8);` and similarly for `MiddleMap`. No need to `resize` or `insert`. What you are actually doing is default construction each `vector` (so that it has 0 elements), _`resize()` expands the `vector`s to 8 default-constructed elements each_, then you _additionally_ insert 8 copies of your default constructed `___Map` at the ends — Nicu Stiurca, Feb 14 '14 at 15:15
of both `vector`s, ending up with 16 default-constructed elements in each vector. — Nicu Stiurca, Feb 14 '14 at 15:15
@SchighSchagh do u imply I do not need to manually insert the default constructed `___Map` in the vectors after resizing? & what do mean by `___Map` syntax? — Sunil Kundal, Feb 14 '14 at 15:22
@SchighSchagh I removed the lines wherever I am inserting copies of `inmap` and `mdmap` in the vectors. But still I get the same error : 0x0804f706 in __gnu_cxx::new_allocator >::construct (this=0xbffff07f, __p=0x8098850, __val=...) at /usr/include/c++/4.6/ext/new_allocator.h:108 108 { ::new((void *)__p) _Tp(__val); } — Sunil Kundal, Feb 14 '14 at 15:29
@Sunil Kundal, ah sorry, I didn't notice that you were adding elements to that vector afterwards. However, I believe that is the key to the problem. I've added an answer. — eerorika, Feb 14 '14 at 15:32
@SunilKundal Sorry, `___Map` was just meant as shorthand for either `InnerMap` or `MiddlMap` since my comment was already way too long. — Nicu Stiurca, Feb 14 '14 at 15:37
@SchighSchagh @user2079303 thankyou both, the problem is solved ! Neither do I need to refill the `vector` with instances after positive resizing, nor do I have to use the possibly corrupted `vector::iterator vec_inmap_it` after the resizing. — Sunil Kundal, Feb 14 '14 at 15:45

score 2 · Answer 1 · answered Feb 14 '14 at 14:37

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

answered Feb 14 '14 at 14:37

Zuko

2,764
30
30

1

http://stackoverflow.com/questions/16445957/can-raw-pointers-be-used-instead-of-iterators-with-stl-algorithms-for-containers is a good place to visit. – Zuko Feb 14 '14 at 15:08

eerorika · Accepted Answer · 2014-02-14T15:53:06.857

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);
    }
...

edited Feb 14 '14 at 15:53

answered Feb 14 '14 at 15:29

eerorika

232,697
12
197
326

Actually, if you resize a vector, only the `end` iterator is always invalidated. Other iterators are only invalidated if the vector had to re-allocate storage. For instance, if you `reserve()` a bunch of elements, create some iterators, then `resize` to a size <= reserved size, no re-allocation will be necessary and non-end pointers will still be valid. – Nicu Stiurca Feb 14 '14 at 15:42
Hi someone please upvote the @user2079303 's answer. – Sunil Kundal Feb 14 '14 at 15:59

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

2 Answers2

Linked