Storage of a high score table, what kind of container?

Question

Say I have a high score table structured like

name score
name score
....

I need to do some file operations and manipulate certain areas of the file, and I thought the best way to do this would be to store it in a container that preserved the order of the file, do the data manipulation with the container, then output back to the file.

I considered using a map< std::string, int >, but a map wouldn't preserve the order of the file. Would a vector< pair< std::string, int >> be better, or is there some kind of ordered map I can use? I also need the container to repeat a name if necessary. I think a multimap keeps one key, but allows multiple values for that key, which isn't what I want since it wouldn't preserve order.

Answer 1

I also need the container to repeat a name if necessary.

So stick the same name into your vector-of-pairs twice. Is that really such a big deal?

Answer 2

Use the

std::vector< std::pair< std::string, int > >

solution.

Or even better, do a HighScoreEntry class, and have a std::vector< HighScoreEntry > -- then you'll be able to add additional data to it later, and embed score handling code in the class.

To add an entry, push the entry to the end of the vector, and run std::sort on it, just remember to write a comparison operator for HighScoreEntry.

class HighScoreEntry
{
public:
   std::string name;
   uint32 score;

   bool operator<(const HighScoreEntry& other) const
   {
       // code that determines ordering goes here
       return score < other.score
   }
};

Highscore table:

std::vector< HighScoreEntry > highscores;

Sorting:

std::sort( highscores.begin(), highscores.end() );

To preserve sort order for highscores that have the same score, use a timestamp, and add it to the comparator.

Answer 3

typedef std::pair<int, int> score_entry; // score, timestamp/serial
typedef std::map<score_entry, std::string, std::greater<score_entry> > score_map;

It's ordered by the score and timestamp/serial (in descending order), and allows duplicates of the same high score. (If you want earlier timestamp/serial to be listed first, put in negative numbers.)

Using a serial number instead of a timestamp means that you can allow duplicates without having to use multimap. Thanks to Steve Jessop for the suggestion!

Answer 4

If you want an ordered map, then you want it ordered by score, so it should be a multimap<int, string>, to preserve order and permit tied scores.

This strikes me as silly, though, not to mention it's not obvious what on earth is being "mapped". Container performance on a high-score table is very unlikely ever to matter, so I'd just use the vector of pair<string,int>.

Answer 5

Why use a priority_queue? Should make adding new scores easy as well.