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.

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.

"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

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!

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.

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.

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 _WIN32namespace 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.