c++ - 最快的 C++ map ？

Question

纠正我我错了，但 std::map 是一个有序映射，因此每次我插入一个值时，映射都会使用一种算法在内部对其项目进行排序，这需要一些时间。

我的应用程序会定期获取有关某些项目的信息。

这个应用程序保留了一个这样定义的 map :

::std::map<DWORD, myItem*>

起初，所有项目都被视为应用程序的"new"项目。正在分配一个“Item”对象并将其添加到此映射中，并将其 id 和指向它的指针相关联。

当它不是"new"项目(只是此对象的更新)时，我的应用应该使用给定的 id 在 map 上找到该对象并进行更新。

大多数时候我都会收到更新。

我的问题是:
有没有更快的 map 实现，还是我应该继续使用这个？
我最好使用 unordered_map 吗？

Answer 1

Am I better use unordered_map?

可能。

std:map 在 O(log n) 时提供一致的性能，因为它需要实现为平衡树。但是 std:unordered_map 将被实现为一个哈希表，它可能会给你 O(1) 的性能(良好的哈希函数和跨哈希桶的键分布)，但它可能是 O(n)(一切在一个哈希桶中并转移到一个列表中)。人们通常会期望介于这些极端之间。

因此，您可以始终保持合理的性能 (O(log n))，或者您需要确保所有内容都对齐，以便通过哈希获得良好的性能。

与任何此类问题一样:您需要在采用一种方法之前进行衡量。除非您的数据集很大，否则您可能会发现没有显着差异。