考虑到在这种情况下真正的O(1)操作是一个非常复杂的问题，并且您更喜欢使用 STL，我建议使用以下数据结构。并不是说这不能满足您的 Big-Oh 要求，即使使用 STL，这也不是实现它的最有效方式，但它简单而高效。
您的主要数据结构是std::map. 但是为了加速查找到 O(1)，你可以使用std::unordered_map这样的：
using std::map, std::string, std::vector, std::unordered_map;
typedef map<string, vector<int> > TestTakersMap;
typedef unordered_map<string, TestTakersMap::iterator> LookupAccelerator;
现在您的各种操作将是：
- 添加一个新人：您插入到地图中，但您也在地图中添加名称和迭代器，您将新记录插入到 unordered_map 中。O(log(N))。
- 查找一个人：使用 unordered_map，您可以获得该人的迭代器和数据。预期 O(1)。
- 添加新分数：您使用 unordered_map 找到该人，然后使用您获得的迭代器附加新分数。摊销 O(1)。
- 打印出所有名称和分数：您迭代地图本身并按字典顺序获取名称，无需添加排序步骤。可以认为是O(S)，其中S是所有参与者的得分总数。
请注意，在所有这一切中，您的瓶颈将是您的缓存，所有这些在内存中追逐和跳跃的指针对您毫无帮助。当然，这取决于其他几个因素，例如，您实际获得了多少名字，每个人有多少分数，添加新人的频率，添加新分数的频率，打印所有姓名和分数，每个人和每个测试您拥有和需要多少数据等。
更新：您可以执行如下基本操作。包含等如下所示：
#include <map>
#include <string>
#include <unordered_map>
#include <vector>
using std::map;
using std::string;
using std::unordered_map;
using std::vector;
这是一个非常简单的类来做一些你想要的操作。请注意，我使用的是 C++11 功能（auto, emplace, ...），但不要将此代码视为特别好的编程风格；我不能保证这一点。
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;
};