map реализовано из balanced binary search tree (обычно rb_tree), поскольку все члены в balanced binary search tree отсортированы, как и карта;
hash_map реализовано из hashtable.Поскольку все члены в hashtable не отсортированы, поэтому члены в hash_map(unordered_map) не отсортированы.
hash_map не является стандартной библиотекой c ++, но теперь она переименована в unordered_map (можно подуматьона переименовывается) и становится стандартной библиотекой c ++, поскольку c ++ 11 см. этот вопрос Разница между hash_map и unordered_map? для более подробной информации.
Ниже я приведу некоторый основной интерфейс из исходного кода о том, как реализована карта двух типов.
map:
Приведенный ниже код просто показывает, что картапросто обертка balanced binary search tree, почти вся ее функция - просто вызывать функцию balanced binary search tree.
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 реализовано из hashtableчья структура примерно такова:
В приведенном ниже коде я дам основную часть hashtable, а затем выдаст 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);
};
Как и у map's только член rb_tree, у hash_map's только член hashtable.Это основной код, как показано ниже:
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);
};
};
На рисунке ниже показано, что у hash_map есть 53 сегмента, и при вставке некоторых значений это внутренняя структура.
На изображении ниже показано некоторое различие между картой и hash_map (unordered_map), изображение получено с Как выбрать между картой и unordered_map? :
