C++ 0x/TR1还提供了unordered_map通常实现为哈希映射的方法.
差异是双重的:
关键类型.在有序映射中,密钥类型必须遵循严格的弱排序,并且条目按该顺序维护.在无序映射中,键类型必须是相等的,并且您必须提供一个哈希函数h,以便h(Key)返回size_t[感谢Steve Jessop的澄清].
访问复杂性:在有序映射中插入/删除/查找地图大小为n(log n).在无序映射中,它通常是"O(1)",但最坏情况的行为是O(n)(例如,如果所有键映射到相同的散列值).
因此,有序映射提供了总复杂性保证,而无序映射在良好情况下提供(更好)复杂性,具体取决于散列函数的质量.
无序地图的内部实现复杂性大于有序地图的内部实现复杂性,但您可以想象您获得了更好的访问复杂性,因为您获得的功能更少,即您无法免费进行排序.这是一个经典的权衡.
另一点:实际上,如果弱排序运算符计算起来很昂贵,就像字符串一样,无序映射实际上可能会快得多,因为对散列类型的比较非常快.另一方面,如果您的密钥类型是具有普通散列函数的密钥类型(如任何内置整数类型),并且如果您不需要排序,请考虑使用无序容器.
| 归档时间： |
|
| 查看次数： |
4587 次 |
| 最近记录： |