Storing 5 Game Scores- Which STL Container?

This is a discussion on Storing 5 Game Scores- Which STL Container? within the C++ Programming forums, part of the General Programming Boards category; Hi, Say you're programming a game, and in this game, you have 5 players. Each player can have a score ...

  1. #1
    Registered User
    Join Date
    Sep 2007
    Posts
    127

    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.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

  3. #3
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    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.

  4. #4
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,412
    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.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  5. #5
    Registered User
    Join Date
    Apr 2006
    Posts
    2,021
    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.
    Last edited by King Mir; 08-21-2009 at 12:07 PM.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  6. #6
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,590
    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.
    Last edited by VirtualAce; 08-21-2009 at 05:05 PM.

  7. #7
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    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...
    "I am probably the laziest programmer on the planet, a fact with which anyone who has ever seen my code will agree." - esbo, 11/15/2008

    "the internet is a scary place to be thats why i dont use it much." - billet, 03/17/2010

  8. #8
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,590
    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.

  9. #9
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    >> 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.

  10. #10
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,590
    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.

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,294
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  12. #12
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    >> 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.

  13. #13
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    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.

  14. #14
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    Quote Originally Posted by Daved View Post
    >> 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.
    "I am probably the laziest programmer on the planet, a fact with which anyone who has ever seen my code will agree." - esbo, 11/15/2008

    "the internet is a scary place to be thats why i dont use it much." - billet, 03/17/2010

  15. #15
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    >> 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.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. include question
    By Wanted420 in forum C++ Programming
    Replies: 8
    Last Post: 10-17-2003, 03:49 AM
  2. I/O using a STL container
    By LA Mills in forum C++ Programming
    Replies: 5
    Last Post: 04-20-2003, 12:15 PM
  3. STL container question
    By PJYelton in forum C++ Programming
    Replies: 8
    Last Post: 12-16-2002, 07:40 PM
  4. Map Container & Sorting :: STL
    By kuphryn in forum C++ Programming
    Replies: 2
    Last Post: 09-09-2002, 06:01 PM
  5. Assign Character Arrays data from an STL Container
    By kuphryn in forum C++ Programming
    Replies: 5
    Last Post: 12-05-2001, 09:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21