map est mis en œuvre à partir de balanced binary search tree (généralement un rb_tree ), puisque tous les membres de balanced binary search tree est triée, la carte l'est aussi ;
hash_map est mis en œuvre à partir de hashtable Puisque tous les membres de hashtable n'est pas trié, donc les membres dans hash_map(unordered_map) n'est pas trié.
hash_map n'est pas une bibliothèque standard c++, mais elle est maintenant renommée en unordered_map (on peut penser qu'il a été renommé) et devient la bibliothèque standard c++ depuis c++11 ; voir cette question Différence entre hash_map et unordered_map ? pour plus de détails.
Ci-dessous, je vais donner une interface de base du code source de la façon dont la carte à deux types est mise en œuvre.
carte :
Le code ci-dessous est juste pour montrer que, la carte est juste un emballage d'un balanced binary search tree la quasi-totalité de sa fonction est d'invoquer la fonction balanced binary search tree fonction.
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 est mis en œuvre à partir de hashtable dont la structure est un peu comme ceci :
![enter image description here]()
Dans le code ci-dessous, je vais donner la partie principale de hashtable et donne ensuite 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);
};
Comme map's Le seul membre est rb_tree le hash_map's Le seul membre est hashtable . Son code principal est le suivant :
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);
};
};
L'image ci-dessous montre la structure interne d'un hash_map lorsqu'il a 53 buckets, et qu'il insère des valeurs.
![enter image description here]()
L'image ci-dessous montre quelques différences entre map et hash_map(unordered_map), l'image provient de Comment choisir entre map et unordered_map ? :
![enter image description here]()
