Considering that real O(1) operation in this case is a very complicated problem, and you prefer using the STL, I'd suggest something like the following data structures. Not that this does not satisfy your Big-Oh requirements, and it's not the most efficient way you can implement it even with the STL, but it's simple and efficient.
Your main data structure is a std::map. But in order to accelerate lookups to O(1), you can use an std::unordered_map like this:
using std::map, std::string, std::vector, std::unordered_map;
typedef map<string, vector<int> > TestTakersMap;
typedef unordered_map<string, TestTakersMap::iterator> LookupAccelerator;
Now your various operations will be:
- Add a new person: You insert into the map, but also you add the name and the iterator in the map where you inserted the new record into the unordered_map. O(log(N)).
- Look up a person: Using the unordered_map, you can get the iterator and the data for that person. Expected O(1).
- Add a new score: You find the person using the unordered_map, then use the iterator you got to append a new score. Amortized O(1).
- Printing out all names and scores: You iterator over the map itself and get the names in lexicographical order, with no added sort step. Can be considered O(S), where S is the total number of scores for all participants.
Note that in all this, your bottleneck will be your cache, and all this pointer chasing and jumping around in memory will not help you at all. Of course, this depends on several other factors, e.g., how many names you actually got, how many scores per person you have, how often you add a new person, how often you add a new score, how often you print out all the names and scores, how much more data you have and need per person and per test, etc.
UPDATE: You can do a basic operations like the following. The includes, etc. look like this:
#include <map>
#include <string>
#include <unordered_map>
#include <vector>
using std::map;
using std::string;
using std::unordered_map;
using std::vector;
This is a very simple class to do some of the operations you want. Note that I'm using C++11 features (auto, emplace, ...) but don't take this code as particularly good programming style; I can't vouch for that.
class TestScores
{
private:
typedef int ScoreType;
typedef vector<ScoreType> ScoreList;
typedef map<string, ScoreList> TestTakersMap;
typedef unordered_map<string, TestTakersMap::iterator> LookupAccelerator;
public:
bool hasName (string const & new_name) const
{
return m_lookup.end() != m_lookup.find (new_name);
}
// Returns true if the name is really new
bool addName (string const & new_name)
{
if (hasName(new_name))
return false; // name already in there
auto i = m_takers.emplace (new_name, vector<int>()).first;
m_lookup.emplace (new_name, i);
return true;
}
ScoreList const & getScores (string const & name) const
{
// This redirects to the private, non-const version
return const_cast<TestScores *>(this)->getScores(name);
}
void addScore (string const & name, ScoreType new_score)
{
getScores(name).push_back (new_score);
}
private:
// If the name doesn't already exist, it is added!
ScoreList & getScores (string const & name)
{
if (!hasName(name))
addName (name);
return m_lookup[name]->second;
}
private:
TestTakersMap m_takers;
LookupAccelerator m_lookup;
};
