Curiosity & Efficiency C++
Hello,
I am just here to see if any of you can jog my memory or give me any good ideas. In the current game I am making I have two rather large std::lists that each contain different sets of data but pertain to each other.
Lets say I start with list 1 and iterate through it. For each object I come upon I have to then take that and iterate through list two in order to find its cousin. Anyway, this obviously doesn't seem to efficient. If you have two list of 100 object each thats around 10000 iterations at max and 5000 on average! ... Scary as I have much more than 100 lol
Anyway, does anyone have any good ideas how to do this efficiently or even a better way to handle the data.
Sort one list into a vector, and use binary search to find the "cousin". BTW, std::lists are rarely the best tool for the job. Their iterator invalidation semantics are virtually the only thing they have going for them. std::vector is much more useful.
[Edit]Re-reading your post I may have misunderstood. The following is only useful if you have 1:1 pairings that are added at the same time
You should look into a std::map. It is an associative array that relates a value of one type with that of another - once you've found your first value you also have your second.
Depending on your needs you might actually want a hashtable. Hashtables are very efficient for lookups and insertions and if that's primarily what you're doing it might be the right choice.
You should look into a std::map. It is an associative array that relates a value of one type with that of another - once you've found your first value you also have your second.
Depending on your needs you might actually want a hashtable. Hashtables are very efficient for lookups and insertions and if that's primarily what you're doing it might be the right choice.
Unfortunately I need to be able to remove objects at random spots and thats supposed to be much more efficient using a list. So I guess I have a dilemma:
1. Use lists and do my 1000s of iterations.
2. Sort one of them to a vector and then search
3. Use vectors and deal with inefficient removal
Hmmm Decisions lol
1. Use lists and do my 1000s of iterations.
2. Sort one of them to a vector and then search
3. Use vectors and deal with inefficient removal
Hmmm Decisions lol
well, if space isn't an issue you could use a map to tie the two lists together.
i.e.
that's obviously a pretty contrived example, but you get the idea.
i.e.
class Player{//lots of player data//...int PlayerID;}class NPC{// lots of NPC data}std::list<Player> players;std::list<NPC> npcs;std::map<int, NPC> victims;// add a playerPlayer p;players.push_back(p);NPC badGuy;npcs.push_back(badGuy);// player kills bad guyvictims[p.PlayerID] = &badGuy// later on print a list of players and their victimsfor (std::list<Player>::iterator i = players.begin(); i != players.end() ++i){ PrintScore(*i, victims[i->PlayerID]);}
that's obviously a pretty contrived example, but you get the idea.
Quote:Original post by trixsJust pop the last element of the vector and use it to overwrite whichever element you want to remove.
Unfortunately I need to be able to remove objects at random spots and thats supposed to be much more efficient using a list.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement