🔒 Locked

best std container for inserts / deletes ?

Started by graveyard filla Jan 3, 2005 at 3:08 AM 12 replies 2k views

Original Post

Jan 3, 2005 at 3:08 AM

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.

iMalc

Jan 3, 2005 at 4:13 AM

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.

Seriema

Jan 3, 2005 at 5:57 AM

"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::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

graveyard filla

Jan 3, 2005 at 12:30 PM

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!

ToohrVyk

Jan 3, 2005 at 12:46 PM

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.

graveyard filla

Jan 3, 2005 at 2:37 PM

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.

SiCrane

Jan 3, 2005 at 3:03 PM

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.

graveyard filla

Jan 3, 2005 at 4:41 PM

thanks a lot SiCrane.

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

stdext::hash_map.

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.

ajas95

Jan 3, 2005 at 4:53 PM

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.

Kylotan

Jan 3, 2005 at 4:56 PM

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.

markr

Jan 3, 2005 at 5:51 PM

It really doesn't matter about the runtime performance. Worry about that later.

Use the container which is right for the task in hand.

If you're storing an essentially unordered set of players belonging to a zone, why not use a std::set per zone?

You can remove elements from a set easily by value the find algorithm and removing using the resulting iterator (IIRC)

Mark

Shannon Barber

Jan 4, 2005 at 12:27 AM

If you're never performing any look-ups you don't need to keep track of the players, the fastest container is none at all!

SiCrane

Jan 12, 2005 at 5:46 PM

Quote:
Original post by graveyard filla
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

This is one of the worst choices in hashing functions you could have chosen. This creates a hash value based on the address of the PlayerID you're trying to insert into the hash_map. This is bad bad juju here. A hash value should be based on the value of the object used as a hash key. Unfortunately, using the address as a hash key can "work" for a while because of the way that hash_map is implemented. On the downside, it also collides up the wazoo even when it does work, which causes the hash_map performance to degenerate into that of a linked list.

Quote:

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?

A hashing function associates a integral value with the value of the object being hashed. A good hash function tries to create an even distribution of hash values for the set of values that will be hashed over the lifetime of your program. For more information you might want to read this article. IIRC, wikipedia had a decent entry on hashing as well, but I'm too lazy to look it up right now.

Quote:

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.

The stdext::hash_map class in MSVC takes as the third template argument a Traits class that is used to determine the hashing function. A valid hash traits class for a key type, Key, supports the following members:

struct MyTraits {   const size_t bucket_size = /* some value greater than 0 */;   const size_t min_buckets = /* some power of two greater than 0  */;   size_t operator()( const Key & Key ) const; // the hash function                                               // maps values of Key types to integral values   bool operator()(const Key & Key1, const Key & Key2) const; // ordering function                                                              // like a less than function};

Example of a hash traits class at work:

#include <hash_map>#include <string>#include <iostream>struct SomeStruct {  SomeStruct(int a, int b) : a_(a), b_(b) {}  int a_;  int b_;};struct MyTraits {   static const size_t bucket_size = 3;    static const size_t min_buckets = 32;   size_t operator()( const SomeStruct & Key ) const {     return (Key.a_ << 16) ^ Key.b_ + Key.a_;   }      bool operator()(const SomeStruct & Key1, const SomeStruct & Key2) const {     if (Key1.a_ < Key2.a_) return true;     if (Key1.a_ > Key2.a_) return false;     return (Key1.b_ < Key2.b_);   }};int main(int, char **) {  stdext::hash_map<SomeStruct, std::string, MyTraits> map;  SomeStruct s1(5, 3);  SomeStruct s2(4, 7);  SomeStruct s3(3, 1);  SomeStruct s4(5, 3);    map[s1] = "cow";  map[s2] = "pig";  map[s3] = "goat";  map[s4] = "oyster";  std::cout << map[s1] << std::endl;    return 0;}

Quote:

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?

It's something the user should take care of. One hashing function may work better than another for the same data type in two different applications.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.