当键是对象的一部分时最合适的关联 STL 容器 [C++]

Question

我有一个这样的类：

struct Thing
{
    unsigned index;
    // more data members
};

我使用 std::map 来包含我的 Thing。调用代码看起来像这样：

Thing myThing(/*...*/);
std::map<Thing> things;
things[myThing.index] = myThing;
// ...
Thing &thing3 = things[3];

我想知道是否有一种方法可以直接使用 Thing::index 而无需隐式地将其复制到 pair::first 中。

我想我需要提供某种 Thing 比较运算符，但这没关系。 std::set 可能有效，但我需要整个 Thing 对象作为键：

std::set<Thing> things;
Thing &thing3 = *things.find(Thing(3));

除了将 Thing 重构为 std： :pair，我可以用STL做得更好吗？

Answer 1

我不明白为什么

inline bool operator<(const Thing& a,const Thing& b) {
  return (a.index<b.index);
}

std::set<Thing> things;  // Uses comparison operator above

Thing &thing3 = *things.find(Thing(3));

不完全按照你的意愿去做。没有索引字段的重复/复制，并且键比较与映射方法一样高效；有什么理由不喜欢呢？

根据下面的评论更新：

如果 Thing 太重量级以至于您不想复制它，那么您最终可能会得到更像这样的代码：

inline bool operator<(const shared_ptr<Thing>& a,const shared_ptr<Thing>& b) {
  return (a->index < b->index);
}

std::set<shared_ptr<Thing>> things;  // Uses comparison operator above

shared_ptr<Thing> key3(new Thing(3));   

Thing &thing3 = *things.find(key3);

虽然恕我直言，重写指针值比较是相当邪恶的最好采用更详细的方式，将显式“比较”参数设置为模板参数。

需要记住的一件事（根据我自己对重量级对象的大优先级队列的经验）：基于 std::pair> 的容器可能比基于 std::pair> 的容器具有显着的优势std::pair 因为前者的遍历仅触及键（例如find）与后者相比可以更加提高缓存效率，这也会将大量不需要/不相关的heavyweight_object字节提取到缓存中（当然取决于细节和数量，但事实上，这种效果很容易完全淹没复制密钥的相对较小的成本）。

Answer 2

使用私有继承或组合包装映射，重新导出访问器并根据所需功能实现插入。我建议在 key getter 上对你的新类型进行patametrize - 一个函子，它返回给定存储类型对象的键。

Answer 3

我记得 boost::flyweight支持 密钥提取器以避免在可以轻松从对象中获取密钥时为密钥保留额外的存储空间。

我并不建议在 map 或 unordered_map 足够的所有情况下使用 Flyweight，我很难相信这些类不支持类似的密钥提取模式，虽然我在文档或谷歌中找不到任何提及。无论哪种情况，这都可能对您有帮助

Answer 4

使用对象的内存地址作为映射中的键怎么样？

std::map< void*, std::shared_ptr<MyObject> > myMap;
myMap.insert( std::pair<void*, std::shared_ptr<MyObject> >(object.get(), object) );

因此，您不需要将密钥存储在对象中，我认为这是一个坏主意，因为密钥与对象状态没有任何关系。