Jump to content
  • Advertisement
Sign in to follow this  
graveyard filla

best std container for inserts / deletes ?

This topic is 5003 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

hi, i am trying to figure out what is the best container for my situation. i am working on a 2d online RPG, specifically the server. the server keeps the players in "groups" based on their map. so, i have a Map class which has a container of type Player*. when a player leaves this map, we remove him from this container, and add him to his new Map's collection. currently this container is a std::set<>, although im not sure this is the best container for the job (for one thing, i am not doing any lookups..). so basically, i am constantly doing inserts and deletes. im also looping through the whole list sometimes and performing actions on it (note: i am NOT searching for anything, im just doing stuff with the Player, like adding his data to a packet). anyway, basically i need a container which can do fast inserts/ deletes from either begining/middle/end, and is also fast to loop through. now normally this screams to me "std::list", but i just want to be sure. ive been studying the STL docs for a little bit, and im really not positive if this is the best method. maybe an slist is more appropriate? i dont think i will ever need bi-directional iterators. however i think that erasing from the middle of an slist is slow? again, im not too sure. also, what about std::list::remove()? should i use this for removing the Player* from the list, or something else? the thing i dont like is that it is linear time - it will loop through the entire list and remove all items with that value. the problem is this list will always contain unique items (it holds pointers, and i dont plan on putting the Player twice in the list). so really, looping through the whole list is not nessasary. perhaps it would be faster to make my own remove() routine, by looping through the list and calling erase() when i find the item? also, im thinking that its a possibility that maybe hash_map/set might be faster for this, but i dont think so. the STL docs werent too clear about the complexity on these two (yes i know they are not standard, but my compiler supports them). thanks for any help.

Share this post


Link to post
Share on other sites
Advertisement
Actually, from the information you've provided it looks very much to me like a std::set is actually the best container for the job. A set is implemented as a red-black tree, which is actually quite fast. Much better than a list for random deletions.

Share this post


Link to post
Share on other sites
"basically i need a container which can do fast inserts/ deletes from either begining/middle/end, and is also fast to loop through"

std::list

"maybe an slist is more appropriate? i dont think i will ever need bi-directional iterators."

According to the SGI slist: You should usually use slist unless you actually need the extra functionality of list, because singly linked lists are smaller and faster than double linked lists.

"however i think that erasing from the middle of an slist is slow?"

More from SGI slist: (amortized) constant time insertion and removal of elements

Compared to sorted associative containers (map,set,etc): Erase element is constant time. Erase key is O(log(size()) + count(k)).

"what about std::list::remove()? should i use this for removing the Player* from the list"

use member functions when given, otherwise use something from < algorithm >.

"it will loop through the entire list and remove all items with that value. the problem is this list will always contain unique items (it holds pointers, and i dont plan on putting the Player twice in the list). so really, looping through the whole list is not nessasary"

Just combine a std::algorithm with the erase() function of your s/list, like this:

slist<Player*>::iterator player = std::find(playerList.begin(), playerList.end(), targetPlayerPtr); // or you could use std::find_if() together with a predicate functor
if( player != playerList.end() ) // found it!
playerList.erase( player );

done :)

in short: use slist if you can (and don't care that it's not standard), otherwise list. and ues the stl algorithms for your deletion purpose.

Here's a great site for STL info, besides MSDN of course: SGI, Table of Contents: the Standard Template Library

Share this post


Link to post
Share on other sites
hey guys,

thanks for the replies. after studying the docs some more, im not sure if a list or slist is the best container for the job. the thing about slist that bothers me is this:

Quote:

Slist provides the member functions insert_after and erase_after, which are constant time operations: you should always use insert_after and erase_after whenever possible. If you find that insert_after and erase_after aren't adequate for your needs, and that you often need to use insert and erase in the middle of the list, then you should probably use list instead of slist.


now, the main problem with std::list/slist is removals. for removing an arbitrary item from the list, this is actually kind of slow (unless i happen to have the iterator, e.g. im looping through the list and an object tells me "delete me", which is not the case..). even when using the std::find() combined with erase(), this is still at worst size() comparisons.

however, as iMalc suggested, removing from a std::set is actually quite fast. it is at worst logarithmic complexity. the problem is, doing an insert is also logarithmic complexity. actually, im not even sure if im reading this right. it says

"Average complexity for erase key is at most O(log(size()) + count(k))."

so, if i want to erase by key, this is actually worse then logarithmic time? im just not understanding this.. what is + count(k) mean? it says "k" is a key, so is this really O(log(size()) + size()) ? or, does count(k) mean "how many keys in the set are k", but, since its a unique container, shouldnt this always be one anyway?

for now, im going to assume it means logarithmic... so:

std::list : constant time inserts, linear deletes
std::set : logarithmic inserts, logarithmic deletes

which is better for my situation? (remember: every time i do an insert, i do a delete, and vice versa) i would think this would be a common problem among us game developers - having to constantly switch the container an object is in, for things like space partitioning and stuff.

thanks for anymore help!

Share this post


Link to post
Share on other sites
Well, first of all I have to say that I'll be assuming the following:

- You don't remove a lot of objects at the same time, and removal happens infrequently (same for insertion).

- You don't need to remove an object immediately (you can wait a little).

- You perform often enough a complete pass through all the objects.

What I would do is use a list, and whenever I "remove" an object from the map, I add that object to a set instead. Then, when I do a complete pass through the map, I check for each object if it is present in the set, and if it is, I also erase it (I have an iterator to it).

Alternatively, if you can, a better option would be to add a "remove" flag on the objects, if it is set, remove them, and unset the flag before adding it to somewhere else. Not a good solution if you want to keep per-map removal states, though.

Finally, if you're into nonstandard containers, you could always use a hash_set (see SGI) for O(1) insertion/removal, although you might get some overhead for iterating through it (about as much as a set, though).

EDIT: oh, and I forgot, players moving from one map to another is something that happens very infrequently when compared to other cases. The best you could do right now is use a generic solution and easy to code, and once your game is advanced enough, profile it to determine if a better solution is needed, and if necessary what the best solution is.

Share this post


Link to post
Share on other sites
ToohrVyk,

thanks for the reply. you are right - this most likely will not become a bottleneck, and theres no need for a less intuative but faster solution to this problem (at least not yet). im going to just keep it as a set for now.

btw, are you sure that std::hash_set is constant insert and removal? because i dont see mention of this in the SGI docs (when you click on the functions to read the complexities, it just points back to the map/set "associate/unique associative" pages.

Share this post


Link to post
Share on other sites
If you're using a non-standard container supplied with your compiler, you might want to check your compiler's documentation. IIRC, you're using MSVC 2003, which has a wonderful set of documentation packaged with it. In particular it has this to say about hash_set:
Quote:

The main advantage of hashing over sorting is greater efficiency; a successful hashing performs insertions, deletions, and finds in constant average time....

Of course, even if you don't bother to install the documentation, the same information is available online.

On the other hand, keep in mind that the quoted paragraph says "successful hashing". If you choose a bad hashing function, all those functions can be linear in time.

Share this post


Link to post
Share on other sites
thanks a lot SiCrane.

i actually had a problem with using the stdext::hash_map. i tried doing this:

stdext::hash_map<PlayerID,Player*>.

however, this gave me a compile error in the "xhash" standard file. specifically at the "return" line of this function:


template<class _Kty> inline
size_t hash_value(const _Kty& _Keyval)
{ // hash _Keyval to size_t value one-to-one
return ((size_t)_Keyval ^ _HASH_SEED);
}


it gave an error about casting from PlayerID to size_t. now, my hash_map's which have a POD type as the key work perfect. but when trying to use a PlayerID as a key, i got this error. a PlayerID has 2 members : an unsigned long and an unsigned short. (it is a IP and Port combo that identifes a player uniquely on the network)

anyway, after talking in the IRC channel with snk_kid (thanks ALOT snk_kid!!), he helped me get this error sorted. apparently the MS implementation of this container is kind of screwy. i had to make a specialization of this function, which looks like this:


#ifdef _WIN32
namespace stdext {

template<>
inline size_t hash_value(const PlayerID& _Keyval) {
return (reinterpret_cast<size_t>(&_Keyval) ^ _HASH_SEED);
}
};
#endif


now, using this, it compiles.

anyway, i guess the reason im posting this is a few things. for one thing, you said that i should choose a good "hashing function". what is a hashing function exactly? is this the one you are talking about? because on the MS compiler, it does not have a "hasher" as one of the template parameters, unlike in the SGI docs. is this the type of thing the compiler should take care of, or the user? can i trust the compiler to make an "optimial" hasher? and last, is there any way to tell if mine is optimal or not?

thanks a lot for anymore help.

Share this post


Link to post
Share on other sites
Quote:
"Average complexity for erase key is at most O(log(size()) + count(k))."


I'm willing to bet it has to do with the occasional need to rebalance the tree after insertions and deletions.

Share this post


Link to post
Share on other sites
Quote:
Original post by graveyard filla
hi,

i am trying to figure out what is the best container for my situation. i am working on a 2d online RPG, specifically the server. the server keeps the players in "groups" based on their map. so, i have a Map class which has a container of type Player*. when a player leaves this map, we remove him from this container, and add him to his new Map's collection.


Use any class you want to.

Until you hit 100,000 players, or have players leaving the map more than 50 times a second, you could implement this with a random search through a large array and it would still be efficient enough.

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!