AMC*_*der 3 c++ stl std data-structures
C++中是否有一个带O(1)查找的数据结构？
A std::map有O(log(n))查找时间(对吗？).
我从std优先考虑的事情(所以不是Boost pls).此外,如果有,它是如何工作的？
编辑:好的,我猜不清楚.我想关联价值观,有点像map.所以我想要类似的东西std::map<int,string>,find并且insert应该采取O(1).
Sca*_*nth 10
数组有O(1)查找.c ++ 11的Hashtable(std :: unordered_map)具有O(1)查找.(摊销,但或多或少不变.)
我还想提一下,像地图这样的基于树的数据结构具有很大的优势,而且只有log(n),这通常是不够的.
回答你的编辑 - >你可以逐字地将数组的索引与其中一个值相关联.哈希表也是关联的,但是很难获得完美的哈希(每个键映射到1个值).
还有一件值得一提的事:阵列具有很好的缓存性能(由于局部性,又称.元素彼此相邻,因此可以通过prefecthing引擎预取缓存).树木,不是那么多.使用合理数量的元素,哈希性能可能比渐近性能更重要.