Curiosity & Efficiency C++

This topic is 3985 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

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.

Share on other sites
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.

Share on other sites
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.

Share on other sites
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

Share on other sites
well, if space isn't an issue you could use a map to tie the two lists together.

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.

Share on other sites
Quote:
 Original post by trixsUnfortunately I need to be able to remove objects at random spots and thats supposed to be much more efficient using a list.
Just pop the last element of the vector and use it to overwrite whichever element you want to remove.

Share on other sites
A couple good ideas.

Thanks! Time to do some testing :)

1. 1
2. 2
Rutin
16
3. 3
4. 4
5. 5

• 26
• 11
• 9
• 9
• 11
• Forum Statistics

• Total Topics
633702
• Total Posts
3013450
×