k***x
发帖数: 6799 | 1 java里面貌似直接有hash table，C++的话看到leetcode那边很多是用STL里面的map来
代替的。这样的话查找还是O(1)么？
我怎么感觉如果map是按照key值来排序的话，这个查找复杂度更像是O(log(n))啊。 |
g****y
发帖数: 240 | 2 用unordered_map，这个相当于hashtable |
C***U
发帖数: 2406 | 3 那你就用hash_map啊。那个是hashtable.
【在 k***x 的大作中提到】
: java里面貌似直接有hash table，C++的话看到leetcode那边很多是用STL里面的map来
: 代替的。这样的话查找还是O(1)么？
: 我怎么感觉如果map是按照key值来排序的话，这个查找复杂度更像是O(log(n))啊。
|
i*********7
发帖数: 348 | 4 unordered_map吧。这个好一点，支持键域放任何形式的指针。 |
s*********6
发帖数: 261 | 5 STL的map是RB tree,查找的确是O(logN)
但是它的删除和插入也是O(logN)
这点hashtable没法做到吧 |
H****s
发帖数: 247 | 6 如 iversion 所说就用 unordered_map 这个就是C++ 里的hash_table
标准C++中不存在hash_map, 你得自己实现
【在 s*********6 的大作中提到】
: STL的map是RB tree,查找的确是O(logN)
: 但是它的删除和插入也是O(logN)
: 这点hashtable没法做到吧
|
s*****n
发帖数: 994 | 7 刚才google了一下unordered_map
http://www.cplusplus.com/reference/stl/unordered_map/operator[]
里面的这句话是什么语法？
for (auto& x: mymap) {
【在 H****s 的大作中提到】
: 如 iversion 所说就用 unordered_map 这个就是C++ 里的hash_table
: 标准C++中不存在hash_map, 你得自己实现
|
f*******n
发帖数: 12623 | 8 All these operations are O(1) average-case and O(N) worst-cast for hash
table.
【在 s*********6 的大作中提到】
: STL的map是RB tree,查找的确是O(logN)
: 但是它的删除和插入也是O(logN)
: 这点hashtable没法做到吧
|
f*******n
发帖数: 12623 | 9 unordered_map是TR1或C++11才有的。
hash_map是不标准，但是很早就在大多数的compiler里面包了
【在 H****s 的大作中提到】
: 如 iversion 所说就用 unordered_map 这个就是C++ 里的hash_table
: 标准C++中不存在hash_map, 你得自己实现
|
H****s
发帖数: 247 | 10 这个是C++11的新语法, 是 automatic type deduction
【在 s*****n 的大作中提到】
: 刚才google了一下unordered_map
: http://www.cplusplus.com/reference/stl/unordered_map/operator[]
: 里面的这句话是什么语法？
: for (auto& x: mymap) {
|
H****s
发帖数: 247 | 11 是的， 不过那样code 就是compiler/platform dependent 的啦!
【在 f*******n 的大作中提到】
: unordered_map是TR1或C++11才有的。
: hash_map是不标准，但是很早就在大多数的compiler里面包了
|
S**I
发帖数: 15689 | 12 C++11的这俩特性主流的C++ compiler现在应该都支持了。
【在 H****s 的大作中提到】
: 是的， 不过那样code 就是compiler/platform dependent 的啦!
|
