Jump to content
  • Advertisement
Sign in to follow this  
trixs

Curiosity & Efficiency C++

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
Share on other sites
[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.

Share this post


Link to post
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 this post


Link to post
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 player
Player p;
players.push_back(p);

NPC badGuy;
npcs.push_back(badGuy);

// player kills bad guy
victims[p.PlayerID] = &badGuy;


// later on print a list of players and their victims
for (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 this post


Link to post
Share on other sites
Quote:
Original post by trixs
Unfortunately 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 this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!