Thread: 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.

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.

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

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