std::map 键最快的类型？
我想使用图的分区作为 std::map 的关键，
我可以将其表示为节点的 std 向量。或者我可以将其转换为更紧凑的“自定义”二进制格式（位集？）或字符串表示形式。
为了简单起见，我们可以说图的分区没有固有的顺序。
就插入和查找而言，这将是最快的（请注意，该映射的大小约为十亿个节点）
I would like to use the partitions of a graph as the key to a std::map
I could represent this as a std vector of nodes. Or I could convert it into a more compact 'custom' binary format (bitset?), or a string representation.
For simplicitiy's sake, we can say there is no inherent order to partitions of a graph.
Which will be fastest in terms of insertions and lookups (note the size of this map will be in the order of a billion nodes)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
保留您的密钥类型，但使用 boost 的
unordered_map并为您的图形分区编写您自己的hash()函数。例如，如果顺序无关紧要，您可以以顺序不变的方式对每个节点进行散列。如果您发布现在的编码方式，我们可以提供更多帮助。
Keep your key type, but use boost's
unordered_mapand write your ownhash()function for your graph partition.For example, if order doesn't matter, you can hash each node in a way that is invariant to order. If you post how you are encoding it now, we can help more with this.
如果您要拥有那么多条目并且性能至关重要，我建议一定要使用
unordered_map。如果您使用的是 C++1x，它位于标准库中；否则你可以从 boost 获取它。
如果性能确实至关重要，您可以进一步使用 Boost::侵入式。它包含标准库容器的“侵入式”版本：它们复制您插入的值的指针而不是值本身。如果值很大，您将获得很大的性能优势。
If you're going to have that many entries and performance is critical, I would suggest to definitely use
unordered_map.If you are using C++1x it's in the standard library; otherwise you can get it from boost.
If performance is really critical you can go even further and use boost::intrusive. It contains "intrusive" versions of the standard library containers: they copy the pointers of the values you insert instead of the values themselves. If the values are large you'll get a big performance benefit.
可靠地回答这个问题的唯一方法是回答任何优化问题的唯一方法：尝试一下并看看。
也就是说，我怀疑两者之间会有很大差异，只要有一个可以使用的有效比较运算符。
The only way to reliably answer this question is the only way to answer ANY optimization question: Try it and see.
That said, I doubt there'd be much difference between the two, so long as there is an efficient comparison operator you can use.