Alternative to nested maps in standard namespace

Question

I have nested map of type:

std::map<int,std::map<pointer,pointer>>

I am iterating over the map each time/per frame and doing updates on it.So basically I have 2 nested if loops. i have an array and i need to sort the data with 2 attributes. First attribute is integer which is the first key, then second attribute is a pointer which is a key of nested map inside the main map. so my code is something like:

iterator = outermap.find();
if(iterator!=outermap.end()){
    value = iterator->second;
    it1 = value.find();
    if(it1!=value.end(){
        value1 = it1->second;
        // do something
    }
    else{
        // do something and add new value
    }
}
else {
   // do something and add the values
}

This is really slow and causing my application to drop frame rate. Is there any alternative to this? Can we use hash codes and linked list to achieve the same?

Could you explain your scenario a bit more? Iterating over maps doesn't require `if`s. How many elements? Do you need them ordered? [mcve]? — Mat, May 27 '16 at 04:43

score 3 · Answer 1 · edited May 23 '17 at 11:52

You can use std::unordered_map, it will hash the keys so finds complete faster. Using value = iterator->second is copying your entire map to the 'value' variable. Using a reference avoids unnecessary copying and is better for performance, eg: auto & value = iterator->second.

Also std::map is guaranteed to be ordered. This can be used to your advantage since your keys are integers for the outermost map.

score 2 · Answer 2 · answered May 27 '16 at 06:12

Firstly, your question is a bit vague, so this may or may not fit your problem.

Now, you have a map<int, map<pointer, pointer>>, but you never operate on the inner map itself. All you do is look up a value by an int and a pointer. This is also exactly what you should do instead, use an aggregate of those two as key in a map. The type for that is pair<int, pointer>, the map then becomes a map<pair<int, pointer>, pointer>.

One more note: You seem to know the keys to search in the map in advance. If the check whether the element exists is not just for safety, you could also use the overloaded operator[] of the map. The lookup then becomes outermap[ikey][pkey] and returns a default-initialized pointer (so probably a null pointer, it pointer really is a pointer). For the suggested combined map, the lookup would be outermap[make_pair(ikey, pkey)].

Alternative to nested maps in standard namespace

2 Answers2