纠正我我错了,但 std::map 是一个有序映射,因此每次我插入一个值时,映射都会使用一种算法在内部对其项目进行排序,这需要一些时间。
我的应用程序会定期获取有关某些项目的信息。
这个应用程序保留了一个这样定义的 map :
::std::map<DWORD, myItem*>
起初,所有项目都被视为应用程序的"new"项目。正在分配一个“Item”对象并将其添加到此映射中,并将其 id 和指向它的指针相关联。
当它不是"new"项目(只是此对象的更新)时,我的应用应该使用给定的 id 在 map 上找到该对象并进行更新。
大多数时候我都会收到更新。
我的问题是:
有没有更快的 map 实现,还是我应该继续使用这个?
我最好使用 unordered_map 吗?
最佳答案
Am I better use unordered_map?
可能。
std:map
在 O(log n) 时提供一致的性能,因为它需要实现为平衡树。但是 std:unordered_map
将被实现为一个哈希表,它可能会给你 O(1) 的性能(良好的哈希函数和跨哈希桶的键分布),但它可能是 O(n)(一切在一个哈希桶中并转移到一个列表中)。人们通常会期望介于这些极端之间。
因此,您可以始终保持合理的性能 (O(log n)),或者您需要确保所有内容都对齐,以便通过哈希获得良好的性能。
与任何此类问题一样:您需要在采用一种方法之前进行衡量。除非您的数据集很大,否则您可能会发现没有显着差异。
关于c++ - 最快的 C++ map ?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3198112/