使用哪个排序的 STL 容器来通过特殊键进行快速插入和查找？
我有一些数据，每个数据项都有一个关联的键。密钥由两部分组成：我们称之为颜色和 ID。我想按颜色迭代容器以加快渲染速度，并且我还想仅通过 id 查找容器中的项目。
我尝试使用 std::map 来实现此目的
class MyKey {
public:
int color;
int id;
bool operator<(...)
bool operator==(...)
};
，但我无法提供 <运算符将保持数据按颜色排序，同时允许 map::find 单独处理 id （即没有有关颜色的信息）。
我希望插入和查找操作都很快（例如 O(log(n))）。
有什么想法可以使用什么样的容器来实现这个吗？
I have some data with a key associated with each data item. The key is made of two parts: let's call them color and id. I want to iterate the container by color to speed up rendering and I also want to find items in the container by id alone.
I tried using std::map for this with a key
class MyKey {
public:
int color;
int id;
bool operator<(...)
bool operator==(...)
};
But I cannot provide a < operator that would keep the data sorted by color and at the same time allow map::find to work on id alone (i.e. no information about color).
I want both the insert and find operations to be fast (e.g. O(log(n))).
Any ideas what kind of container I could use to implement this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
在此处修改示例来自 Boost.Multi_index 基于以下修改：
Adapt the example here from Boost.Multi_index based on the following modifications:
尝试 Boost.BiMap，它是一个有 2 个视图的地图。
否则还有更复杂的Boost.MultiIndex。
Try Boost.BiMap, it's a map with 2 views.
Otherwise there is the more complicated Boost.MultiIndex.
如果您宁愿自己编写而不是使用 Boost（在我看来很愚蠢），您可以创建一个包含两个地图的类。一个用于映射颜色，另一个用于映射 ID。映射值将是指针。您将为新类定义插入和查找操作。插入将
新一个数据结构并将指针插入到两个映射中。查找操作将根据需要使用任一地图来定位该项目。对于删除/删除操作有点棘手：您需要通过映射查找数据结构，然后将其从两个映射中删除，可能通过使用数据结构中的数据来查找另一个映射条目。If you'd rather write your own than use Boost (dumb in my opinion) you can make a class that holds two maps. One to map color and the other to map ID. The map values would be pointers. You'd define insert and find operations for your new class. The insert would
newa data struct and insert the pointer into both maps. The find operations would locate the item using either map as appropriate. For delete/remove operations it is a little trickier: you'd need to look up the data struct by a map, then remove it from both maps, probably by using the data in the data struct to find the other map entry.