c++ - 排序数据结构，允许在排序键上重复，但在亚线性时间内替换另一个键上的重复项

Question

这个问题与语言无关，但我专门寻找使用 C++ STL 容器的解决方案。我有一个这样的结构。

struct User {
   int query_count;
   std::string user_id;
}

std::multiset<User> users; //currently using

我使用带有比较器的多重集，该比较器按 query_count 排序。这允许我用相同的 query_count 对多个条目进行排序。现在，如果我想避免 user_id 重复，我需要扫描数据并删除条目并创建一个新条目，耗时 O(n)。我正在想办法在亚线性时间内做到这一点。我正在考虑基于按 user_id 排序的 map 的解决方案，但是当我试图找到最大的 query_count 时，我将不得不扫描所有数据。

编辑:要求是插入、删除、更新(删除/插入)、获得最高的 query_count、在亚线性时间内找到 user_id。

我更喜欢使用标准的 STL 容器，但简单的修改就可以了。有什么办法可以达到我的要求吗？

总结:

答案的总结是，要使用 ootb 解决方案，我可以使用 boost 双向映射。

如果我坚持使用 STL，那么它必须是同时使用两个映射的组合，并针对用户的每次插入仔细更新它们。

Answer 1

这听起来像是 boost 的 multi_index 的工作:http://www.boost.org/doc/libs/1_57_0/libs/multi_index/doc/tutorial/

你可以根据用户id设置一个索引来轻松防止重复(你根据这个插入)，然后在查询计数上设置另一个排序索引来轻松定位最大值。