std::map vs.std::unordered_map 构建

这两个都叫map，但是之间的区别还是很大的。 先看看在构建时候的区别。

std::map 的定义【0】

template < class Key,                                     // map::key_type
           class T,                                       // map::mapped_type
           class Compare = less<Key>,                     // map::key_compare
           class Alloc = allocator<pair<const Key,T> >    // map::allocator_type
           > class map;

在构建 std::map 的时候， 需要 key 能实现 less 即 operator <。
***

std::unoreded_map 的定义【1】

template < class Key,                                    // unordered_map::key_type
           class T,                                      // unordered_map::mapped_type
           class Hash = hash<Key>,                       // unordered_map::hasher
           class Pred = equal_to<Key>,                   // unordered_map::key_equal
           class Alloc = allocator< pair<const Key,T> >  // unordered_map::allocator_type
           > class unordered_map;

在构建 std::unordered_map 的时候， 需要提供 hash<Key> 和 equal_to<Key>。
至于 Alloc 则是定义内存模型的，可以使用默认， 也可以自定义一个。具体参考【2】。

---

实例

#include <iostream>
#include <map>
#include <unordered_map>

// std::map
struct IAmMapKey
{
public:
    int d;

    // operator <
    bool operator<(const IAmMapKey& k) const
    {
        return d < k.d;
    }
    
    friend std::ostream& operator<<(std::ostream& o, const IAmMapKey& k);
};
std::ostream& operator<<(std::ostream& o, const IAmMapKey& k) {
    return o << k.d;    
}

// std::unordered_map
struct IAmUnorderedMapKey {
    int d;
    
    // operator ==
    bool operator==(const IAmUnorderedMapKey& up) const {
        return this->d == up.d;
    }
    
    friend std::ostream& operator<<(std::ostream& o, const IAmMapKey& k);
};
std::ostream& operator<<(std::ostream& o, const IAmUnorderedMapKey& k) {
    o << k.d;   
    return o;
}

// hash function
struct IAmUnorderedMapKeyHasher {
	  std::size_t operator()(const IAmUnorderedMapKey& k) const
	  {
		    return std::hash<std::size_t>()(k.d);
    }
};

using map_type = std::map<IAmMapKey, std::string>;
using unordered_map_type = std::unordered_map<IAmUnorderedMapKey, std::string, IAmUnorderedMapKeyHasher>;

int main() {
    // std::map
    map_type map;
    
    struct IAmMapKey mk;
    mk.d = 1;
    map[mk] = "I Am Map Value";
    
    // std::unordered_map
    unordered_map_type up;
    
    struct IAmUnorderedMapKey uk;
    uk.d = 1;
    up[uk] = "I Am Unordered_map Value";
    
    // output
    for (auto& x: map) std::cout << x.first << std::endl;
    for (auto& x: up) std::cout << x.first << std::endl;
    
    return 0;
}

输出

1
1

参考

【0】map
【1】unordered_map
【2】allocator