[c++] map vs. hash_map in C++

map is implemented from balanced binary search tree(usually a rb_tree), since all the member in balanced binary search tree is sorted so is map;

hash_map is implemented from hashtable.Since all the member in hashtable is unsorted so the members in hash_map(unordered_map) is not sorted.

hash_map is not a c++ standard library, but now it renamed to unordered_map(you can think of it renamed) and becomes c++ standard library since c++11 see this question Difference between hash_map and unordered_map? for more detail.

Below i will give some core interface from source code of how the two type map is implemented.

map:

The below code is just to show that, map is just a wrapper of an balanced binary search tree, almost all it's function is just invoke the balanced binary search tree function.

template <typename Key, typename Value, class Compare = std::less<Key>>
class map{
    // used for rb_tree to sort
    typedef Key    key_type;

    // rb_tree node value
    typedef std::pair<key_type, value_type> value_type;

    typedef Compare key_compare;

    // as to map, Key is used for sort, Value used for store value
    typedef rb_tree<key_type, value_type, key_compare> rep_type;

    // the only member value of map (it's  rb_tree)
    rep_type t;
};

// one construct function
template<typename InputIterator>
map(InputIterator first, InputIterator last):t(Compare()){
        // use rb_tree to insert value(just insert unique value)
        t.insert_unique(first, last);
}

// insert function, just use tb_tree insert_unique function
//and only insert unique value
//rb_tree insertion time is : log(n)+rebalance
// so map's  insertion time is also : log(n)+rebalance 
typedef typename rep_type::const_iterator iterator;
std::pair<iterator, bool> insert(const value_type& v){
    return t.insert_unique(v);
};

hash_map:

hash_map is implemented from hashtable whose structure is somewhat like this:

In the below code, i will give the main part of hashtable, and then gives hash_map.

// used for node list
template<typename T>
struct __hashtable_node{
    T val;
    __hashtable_node* next;
};

template<typename Key, typename Value, typename HashFun>
class hashtable{
    public:
        typedef size_t   size_type;
        typedef HashFun  hasher;
        typedef Value    value_type;
        typedef Key      key_type;
    public:
        typedef __hashtable_node<value_type> node;

        // member data is buckets array(node* array)
        std::vector<node*> buckets;
        size_type num_elements;

        public:
            // insert only unique value
            std::pair<iterator, bool> insert_unique(const value_type& obj);

};

Like map's only member is rb_tree, the hash_map's only member is hashtable. It's main code as below:

template<typename Key, typename Value, class HashFun = std::hash<Key>>
class hash_map{
    private:
        typedef hashtable<Key, Value, HashFun> ht;

        // member data is hash_table
        ht rep;

    public:
        // 100 buckets by default
        // it may not be 100(in this just for simplify)
        hash_map():rep(100){};

        // like the above map's insert function just invoke rb_tree unique function
        // hash_map, insert function just invoke hashtable's unique insert function
        std::pair<iterator, bool> insert(const Value& v){
                return t.insert_unique(v);
        };

};

Below image shows when a hash_map have 53 buckets, and insert some values, it's internal structure.

The below image shows some difference between map and hash_map(unordered_map), the image comes from How to choose between map and unordered_map?: