mapa vs hash_map en C ++

Tengo una pregunta con hash_mapy mapen C ++. Entiendo que mapestá en STL, pero hash_mapno es un estándar. ¿Cuál es la diferencia entre los dos?

Se implementan de formas muy diferentes.

hash_map( unordered_mapen TR1 y Boost; utilícelos en su lugar) use una tabla hash donde la clave está codificada en un espacio en la tabla y el valor se almacena en una lista vinculada a esa clave.

map se implementa como un árbol de búsqueda binario balanceado (generalmente un árbol rojo / negro).

An unordered_mapdebería ofrecer un rendimiento ligeramente mejor para acceder a elementos conocidos de la colección, pero maptendrá características útiles adicionales (por ejemplo, se almacena en orden ordenado, lo que permite recorrerlos de principio a fin). unordered_mapserá más rápido al insertar y eliminar que a map.

hash_mapera una extensión común proporcionada por muchas implementaciones de bibliotecas. Esa es exactamente la razón por la que se renombró unordered_mapcuando se agregó al estándar C ++ como parte de TR1. map generalmente se implementa con un árbol binario balanceado como un árbol rojo-negro (las implementaciones varían, por supuesto). hash_mapy unordered_mapgeneralmente se implementan con tablas hash. Por tanto, el orden no se mantiene. unordered_mapinsertar / eliminar / consulta será O (1) (tiempo constante) donde mapa será O (log n) donde n es el número de elementos en la estructura de datos. Entonces unordered_mapes más rápido, y si no le importa el orden de los artículos, debe preferirlo map. A veces se desea mantener el orden (ordenado por clave) y para eso mapsería la elección.

Algunas de las diferencias clave están en los requisitos de complejidad.

• A maprequiere O(log(N))tiempo para las operaciones de inserción y búsqueda, ya que se implementa como una estructura de datos de árbol rojo-negro .

• An unordered_maprequiere un tiempo 'promedio' de O(1)para inserciones y búsquedas, pero se le permite tener un tiempo en el peor de los casos de O(N). Esto se debe a que se implementa utilizando la estructura de datos de la tabla hash .

Entonces, por lo general, unordered_mapserá más rápido, pero dependiendo de las claves y la función hash que almacene, puede empeorar mucho.

La especificación de C ++ no dice exactamente qué algoritmo debe usar para los contenedores STL. Sin embargo, impone ciertas restricciones a su rendimiento, lo que excluye el uso de tablas hash mapy otros contenedores asociativos. (Se implementan más comúnmente con árboles rojo / negro). Estas restricciones requieren un mejor rendimiento en el peor de los casos para estos contenedores que el que pueden ofrecer las tablas hash.

Sin embargo, muchas personas realmente quieren tablas hash, por lo que los contenedores asociativos STL basados ​​en hash han sido una extensión común durante años. En consecuencia, agregaron unordered_mapy demás a versiones posteriores del estándar C ++.

mapse implementa desde balanced binary search tree(generalmente a rb_tree), ya que todos los miembros de balanced binary search treeestán ordenados, por lo tanto, map;

hash_mapse implementa desde. hashtableDado que todos los miembros de hashtableno están ordenados, los miembros de hash_map(unordered_map)no están ordenados.

hash_mapno es una biblioteca estándar de c ++, pero ahora se le cambió el nombre a unordered_map(puede pensar en que se le cambió el nombre) y se convierte en una biblioteca estándar de c ++ desde c ++ 11 ver esta pregunta ¿ Diferencia entre hash_map y unordered_map? para más detalles.

A continuación, daré una interfaz básica del código fuente de cómo se implementa el mapa de dos tipos.

mapa:

El siguiente código es solo para mostrar que, map es solo un envoltorio de balanced binary search tree, casi toda su función es simplemente invocar la balanced binary search treefunción.

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_mapse implementa a partir de hashtablecuya estructura es algo así:

En el siguiente código, daré la parte principal de hashtabley luego daré 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);

};

Como map'ses rb_treeel hash_map'súnico miembro , el único miembro es hashtable. Es el código principal de la siguiente manera:

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);
        };

};

La imagen de abajo muestra cuando un hash_map tiene 53 cubos e inserta algunos valores, su estructura interna.

La siguiente imagen muestra alguna diferencia entre mapa y hash_map (unordered_map), la imagen proviene de ¿Cómo elegir entre mapa y unordered_map? :

No sé qué da, pero hash_map tarda más de 20 segundos en borrar () 150K claves enteras sin firmar y valores flotantes. Solo estoy ejecutando y leyendo el código de otra persona.

Así es como incluye hash_map.

#include "StdAfx.h"
#include <hash_map>

Leí esto aquí https://bytes.com/topic/c/answers/570079-perfomance-clear-vs-swap

diciendo que clear () es el orden de O (N). Eso para mí es muy extraño, pero así es.