c++ - 哪个排序的 STL 容器用于使用特殊键快速插入和查找？

Question

我有一些数据，每个数据项都有一个关联的键。 key 由两部分组成:我们称它们为颜色和 ID。我想按颜色迭代容器以加快渲染速度，我还想单独按 id 查找容器中的项目。

我尝试使用 std::map 来实现这一点

class MyKey {
public:
  int color;
  int id;
  bool operator<(...)
  bool operator==(...)
};

但我无法提供一个 < 运算符来保持数据按颜色排序，同时允许 map::find 单独处理 id(即没有关于颜色的信息)。

我希望插入和查找操作都快(例如 O(log(n)))。

知道我可以使用哪种容器来实现它吗？

Answer 1

改编示例here来自 Boost.Multi_index 基于以下修改:

typedef multi_index_container<
    MyKey,
    indexed_by<ordered_unique<identity<MyKey> >,
    ordered_non_unique<member<MyKey,int,&MyKey::color> >
  > 
> DataSet;