• Advertisement
Sign in to follow this  

array, vector, or ... ?

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

Ok so Ive got a class called Player and I was originally going to make an array to contain all of them. I want to leave room for the possibility of up to 30,000 players at a time(I know its not very likely, but I dont want to have it my game set up to be able to handle it just in case). So I figured that a giant array might not be the most efficient way to do things. For example, if Bob does "/whisper John sup man" I would end up having to do a linear search through the array to find John and take it from there. Now, that could potentially take 30,000 iterations through the loop to find John. That hardly seems efficient. So I started thinking, and came up with an idea that would make it an average of 1000 times faster(maximum of 15 iterations through the loop vs the average of 15,000 it would be if there were 30000 players logged on). I later came to find out this method is actually fairly well known and is called binary searching. Ok so thats all fine and dandy but, in order for binary searching to work, it assumes that the players are all in alphabetical order. To maintain the alphabetical order, I would need to constantly be moving players around in the array and such which I figured could potentially also be an inefficient way of doing things. So then I got this idea of splitting my players into 26 different arrays. One for each letter of the alphabet. That way, instead of having to rearrange a giant array every time anyone logs on or off, I could just rearrange a smaller array containing a fraction of the players. Great! I thought... I then realized that I would have to declare 26 arrays that could each contain up to 30,000 of my Player class(Again I realize its highly unlikely that 30,000 players with the same first lettered name would be on, but you can't be too carefull). So I searched for a way to declare a dynamic array of classes. This led to my discovery of vectors. Ive yet to use vectors, but they sound pretty neat. Or at least they did untill I read this.
Quote:
For operations that involve inserting or removing elements at positions other than the end, they perform worse than deques and lists, and have less consistent iterators and references than lists.
and this
Quote:
Reallocations may be a costly operation in terms of performance, since they generally involve the entire storage space used by the vector to be copied to a new location. Therefore, whenever large increases in size are planned for a vector, it is recommended to explicitly indicate a capacity for the vector using member function vector::reserve
rearranging them in alphabetical order will involve me inserting and removing elements at positions other than the end almost constantly. as for setting the reserve... I dont see how thats much different then doing Player Players[30000] 26 times... So I have 2 questions. 1. Is there a way to declare a dynamic array of classes? 2. Is there a more efficient way to handle this?

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by nethackpro
2. Is there a more efficient way to handle this?


std::map< std::string, Player *>, where std::string is the name.

Share this post


Link to post
Share on other sites
And in general, you want to use a hash_map or hash_set, unless you need the maps to be sorted for some reason. Specifically, the cost of operations on map and set are O(lg N), whereas the cost of operations on hash_map and hash_set are O(1), which at 30,000 players will likely matter.

However, if you haven't encountered a data structure as basic as a hash table yet, chances are that trying to build a multi-player game is not what you should be doing; you'll just get frustrated by running into all kinds of problems that you're not yet prepared to deal with.

Share this post


Link to post
Share on other sites
Quote:
Original post by hplus0603
However, if you haven't encountered a data structure as basic as a hash table yet, chances are that trying to build a multi-player game is not what you should be doing; you'll just get frustrated by running into all kinds of problems that you're not yet prepared to deal with.


Im doing it for fun and as a learning experience. So it doesnt matter that much. So far Ive learned a ton, so its worth it.

Edit:
Also, running into problems doesnt frustrate me. It intrigues me. :)

Share this post


Link to post
Share on other sites
Quote:
Original post by nethackpro
So then I got this idea of splitting my players into 26 different arrays. One for each letter of the alphabet. That way, instead of having to rearrange a giant array every time anyone logs on or off, I could just rearrange a smaller array containing a fraction of the players.


Splitting up the array into smaller arrays based also results in much faster search times. This is a common technique called hashing. See this wikipedia article for more information about hash tables. Your use of the first letter of the name to do the splitting is an inefficient hash function.

Unless you want to re-invent the wheel, you should probably use an already existing implementation of the hash_map container hplus0603 mentioned.

Share this post


Link to post
Share on other sites
To be nit-picky, splaying out by first letter is a one-level 26-way trie (which is just a fancy word for this particular kind of tree). You could, if you wanted, make it so that the first 26 nodes point to 26 nodes each, each of which are indexed on the second letter. Repeat as needed. Each node needs one "data pointer" (which could be NULL), and 26 "children pointers." If you go all the way, you'll have a full trie of your players. The operation cost will then depend on the length of the name, which is better than depending on how many other players have a name with the same starting letter, but still worse than a hash table.

Hmm. It really sounds like what you need is a good data structures book!

Share this post


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

  • Advertisement