Best way to store and retrieve this..?

Question

I've been trying all night, and talk of maps, arrays, vectors and hash_maps have filled my head. im just confused now. i posted a previous question here: http://stackoverflow.com/questions/1687085/c-map-really-slow

problem was fixed but it seems map's are still not fast enough. i need to keep adding data. data is added ALOT during run time. i got it all working now, and if i add 1 piece of data per step (per frame in the game) it works fine. but once i do 2 at a time, i see performance drops. i looked into this hash stuff but couldn't find alot on it. just an fyi, the number of items stores will probably never exceed 2000~ or so. so i guess it is fairly small scaled..

what im trying to store, as someone else put it, is this: "object with id 101 has a value of 4 for setting 1" or information[101][1] = 4; except that i just keep getting more and more objects (differet id's, which is the key value) added into the system with different settings (2nd key). - i dont know what the size of the array will be (thats why i didnt use arrays). looked into vectors but that confused the hell out of me. >_<

right now i have:

//declared as a class member
map<double,  map<int, double> > objIdMap;

//// lower down the page, in some function
map<int, double> objSettingsMap;
objSettingsMap[0] = value;
objSettingsMap[1] = value;
objSettingsMap[2] = value;
objSettingsMap[3] = value;
objIdMap[id] = objSettingsMap;
return(1);

or maybe it isnt the map's? is it normal for maps to perform slow like this when they're used so heavily? (i havnt included it in the code above, but on every step of the game every object with an id in objIdMap is accessing it to retrieve their objSettingsMap values. though the slow downs only occur when the above is executed more than once per step)..

so yea, what do you guys think is the best way to hold this data, and retrieve it etc? please provide example :( thanks

Answer 1

This is probably slow because you're copying an entire map object each time you do:

objIdMap[id] = objSettingsMap;

It's probably better to first insert an empty map into the larger map, and then insert the actual data.

map<int, double> objSettingsMap; 
objIdMap[id] = objSettingsMap; // insert the empty map so copying is fast

// Use a reference to the map so you don't have to keep looking it 
// up in the parent map
//
map<int, double>& mapref = objIdMap[id];
mapref[0] = value;
mapref[1] = value;
...etc..

Edit: You also say:

but on every step of the game every object with an id in objIdMap is accessing it to retrieve their objSettingsMap

When an object accesses its objSettingsMap, are you sure it's not making a copy of the map? Also, when you say the numbers start at 100000, do you mean you start counting from 100000? i.e. key1 = 100000, key2 = 100001, key3 = 100002, etc. Because if this is so, you can simply use a vector and subtract 100000 from each key.

Answer 2

It seems as though you really do not need to nest the maps like that. I would suggest defining a "settings" struct that holds the settings data you need to store.

struct Settings
{
    double setting1;
    double setting2;
    double settingN;
};

map<double,  Settings > objIdMap;

This way you do not have to add a whole map every time. That should help the performance. Maps are pretty good for accessing data, but if you are doing it a lot you should use an array or vector. If you know how to use maps, vectors should be easy to pick up.

vector<Settings> objects;

objects.push_back(Settings() );

objects[0].setting1 = 1234;

That is of course probably not a practical application of a vector, but it shows you how to add objects and access them. With vectors there is a hit when adding an object that causes the memory to be reallocated, but the access is immediate (aside from the memory needing to be cached).

If objects are being remove and added a lot I would suggest marking indexes for recycling. You can do this by simply keeping another vector that holds the indices of the objects that are no longer active. When adding check that list to see if there is an index to recycle. If the list is empty push back another. This way you are minimizing you removal and addition of objects, which are the most expensive operations.

Answer 3

Why isn't this just map<double, vector<double> >?