Storing 5 Game Scores- Which STL Container?

Hi,

Say you're programming a game, and in this game, you have 5 players. Each player can have a score between 0 and 100, and is identified by a unique integer ID that's between 0 and 100. Their scores can sometimes be the same. You want to be able to output the scores from highest to lowest at any point in the game, and also sometimes check who is at the top/ bottom of the scoreboard.

Which STL container would be the best for this? I'm thinking a multimap, using the score for the key, and the ID for the mapped value. This way the scores would always be sorted whenever you wanted to access them.

Does this make sense or would another container be better?

Thanks.

I guess multimap works the way you have it there, but it "feels" wrong -- i.e., normally you would think of the ID as the key and the score as the value of that key -- since when a player scores a point, normally you would update the score for that player, rather than remove the player completely and then create a brand new player with a score one higher.

I would think that you would only need to go to the bother of sorting every single time something happens, just when people ask for the score? If so, just go with a map from ID -> score and sort when necessary with a function object.

I understand your intuition, tabstop, but I think making the ID a key here is unnecessary. I assume there is some other data structure with all the relevant information for each player, so the top scores container doesn't need to be keyed by player ID.

For this a multimap would be fine, but how do you determine who is listed first if two players have the same score? Is it allowed to be random (and change)? Or is it based on a specific criteria like who submitted their score first?

Because of that issue, I'd consider tabstop's suggestion of just sorting when you need to show the scores to be best. I'd just use a vector, and use stable_sort if the ordering of equal scores needs to remain stable. With a vector, it doesn't matter how you store the score/ID pairs, since you would write your own sorting criterion anyway.

I'd probably choose a vector of stdair for the convenience. I can quickly establish all manner of sort algorithms fron the value instead of they key. Meanwhile, I do tend to choose only maps when the key is a stronger element. When it is just a needed associative nuisance, I prefer the flexibility of vectors.

EDIT: Daved beat me to it.

I agree with multi-map, but instead of storing the player ID, store a pointer to the player object. Presumably a player has more than just an id, but also at least a name, and you may as well make it possible to look up that information by their score/ladder position.

EDIT:Daved makes some good points for a sorted vector.

Hash the names into an integer and store in a map - collisions would mean the names would have to be linked somehow so it would turn into a link list from that point on. Keep a list, vector, or stack that has map iterators and maintain it to get the ordering. That way you store the data in a container and use another container to just 'point' to the data you want.

You could also limit the high score list to a certain number of entries in which case an array would do just fine. C's quicksort algorithm would work just fine on an array with only 10 elements. Even a nasty bubble sort could make short work of a small array. You are only going to be sorting when you add a new name to the high score list which will be after gameplay. Personally I think a never-ending high score list is overkill and it should be limited to 10 entries.

std::map takes a comparator template argument. Why not create a comparator that sorts based on the value (i.e. score) instead of the key? Then you can just use the begin() & end() iterators to go from the highest score to lowest...

Either way you go sorting a high score list is not going to drag down the system such that you will notice it.

I think it's a moot point as to what you use here. Now if you were going to dynamically sort objects front to back in a game or something along those lines then using any sort from algorithm would be just plain ignorant. However sorting high scores is so simple and the point in the game where you would do it is not frame-rate dependent so again I don't think it matters what you do at the end of the day.

>> Why not create a comparator that sorts based on the value (i.e. score) instead of the key?

That doesn't make sense. By definition, the map is sorted by key. If you were to use a map (or a multimap in this case) you would make the key the score. It seems obvious that the player data isn't stored in this container, so there is no need to make the ID a key.

In other words, you are mapping the score to the player and using the ID to represent the player. The ID is the value.

I fail to see why a multi-map would ever be needed in this instance. If the name of the player is used as the key...or hashed into a key with a good hash function there is no need for a multi-map.

5 Items huh? It of course depends on your definition of "best", but vector should be the fastest, and with the least memory usage.
With such a small number of items, the simpler containers, and more simplistic of algorithms, outperform others.

>> If the name of the player is used as the key
Why would the name of the player be the key if the container is to be sorted by score? That's why a hash doesn't make sense. I think you're discussing the solution to a different problem than was presented by the OP.

What a mess, this topic. Everybody says something else. The truth is that it's really impossible to say which is best without knowing exactly how it's going to be used.
There are two issues in "better": easier to code, and faster.

Now, with only 5 elements, it gets even harder to say which is faster. True, a map may have O(log n) insertion and a vector O(1), or O(n) for anywhere but the end, but with only 5 elements, the constant we remove from big-O notation may be higher than 5 in one case and 1 in the lower case, making O(n) faster than O(1). It won't be the case in a vector, but theoretically it is possible.
And really, who cares about speed in this situation. Every computer can handle those several thousands of instructions needed in any case in a time you won't even be able to see as a user. So don't bother thinking about speed in this case.

The other way in which it can be better is that it can be easier to code with. This is what you should think about. But again it depends on how you would use it commonly. Would you often refer to a player by id? Would you only insert items, or also remove them, modify them?
I'd propose an std :: set of structures or classes (I prefer to use a struct for classes without functions and only public variables, whereas in classes I usually don't have any public variables but rather functions) with the player information, where the comparison sorts it first by score and then by secondary features you want the score to be sorted as. What if players have a tie? Which do you show first? Put that in the comparison function. If you want to show the scores, simply iterate over the set and display them one by one. If you want to add a player, insert a new struct, and it's done.
Now this solution might not be the best, as in easy to code. If you want to reference a player by name, you have to iterate over the entire set (though that's only about 3 lines of code). You can't modify the score, you'll have to remove it and re-insert it (not many more lines of code).
And again, speed is a non-issue in this case.

Originally Posted by Daved

>> If the name of the player is used as the key
Why would the name of the player be the key if the container is to be sorted by score? That's why a hash doesn't make sense. I think you're discussing the solution to a different problem than was presented by the OP.

Because the player names (or ID numbers) should be unique and therefore there can't be duplicate players in the map. A multimap would allow duplicate players.
If you don't mind having the same player show up with 5 different scores, then using the score as the key is fine.

>> If you don't mind having the same player show up with 5 different scores, then using the score as the key is fine.
I hadn't thought about that. I assumed that the check for that was done elsewhere, but if you do have to handle that situation then a multimap with score as key might not make as much sense. A multimap with player as key would still not be a good idea, though, since you would have to transfer the data to a separate container anyway to sort the score list.

>> The truth is that it's really impossible to say which is best without knowing exactly how it's going to be used.
Of course, but that's why everybody gives reasons for their suggestions. The OP can look at the reasons and (hopefully) understand which apply to the real situation and which do not.

Any scenario where only five elements are involved is more about finding the better theoretical solution. It would hard to make a bad solution for five pieces of data without doing it on purpose. Still, it's a worthy exercise to discuss pros and cons since you never know when you might decide that the high score list will be changed from five to ten, a hundred, or unlimited.