unordered_set - Uso eficiente del operador[] con C++ unordered_map

unordered_map c++ example

Question

En primer lugar, ¿podría alguien aclarar si en C ++ el uso del operador [] junto con un mapa desordenado para las búsquedas ajusta una llamada al método find (), o está utilizando el operador [] más rápido que find ()?

En segundo lugar, en el siguiente fragmento de código sospecho que en los casos en que la clave aún no está en el map[key] = value ordenado, estoy realizando una segunda consulta mediante el map[key] = value línea map[key] = value para reemplazar el valor predeterminado creado allí usando el operador [] cuando una tecla no está presente.

¿Es eso cierto? Si es así, ¿hay una forma (quizás mediante el uso de punteros o algo) de que solo pueda realizar una búsqueda en cualquier caso (tal vez almacenando la dirección donde colocar un valor / leer un valor desde) y ¿Aún logras la misma funcionalidad? Obviamente, esto sería una mejora de eficiencia útil si es así.

Aquí está el extracto del código modificado:

    int stored_val = map[key]; // first look up. Does this wrap ->find()??

    // return the corresponding value if we find the key in the map - ie != 0
    if (stored_val) return stored_val;

    // if not in map
    map[key] = value; 
       /* second (unnecessary?) look up here to find position for newly 
          added key entry */

   return value;

Answer 1

En primer lugar, ¿podría alguien aclarar si en C ++ el uso del operador [] junto con un unordered_map for searchups envuelve una llamada al método Find (), o está utilizando el operador [] más rápido que Find ()?

No hay ninguna regla para eso. Una implementación de [] podría usar find() , podría realizar la búsqueda por sí misma o podría delegar la búsqueda a algún método privado que también es utilizado por find() internamente.

Tampoco hay garantía sobre cuál es más rápido. find() implica una sobrecarga en la construcción y la devolución de un iterador, mientras que [] probablemente será más lento si la clave no existe, ya que inserta un nuevo valor en este caso.

(...) ¿hay alguna forma (tal vez mediante el uso de punteros o algo así) de que solo realice una búsqueda en cualquier caso (...)

Si la clave no está en el mapa, [] insertará un nuevo valor construido por defecto y devolverá una referencia . Por lo tanto, podría almacenar esa referencia para guardar la segunda búsqueda:

int& stored_val = map[key];  // Note the reference

if (stored_val) return stored_val;

// Use the reference to save a second lookup.
stored_val = value; 

return value;

Answer 2

Puede verificar si existe un elemento e insertar un nuevo elemento si no existe, con la función de insert especial que devuelve un pair<iterator, bool> en el que el valor booleano le indica si el valor se ha insertado realmente. Por ejemplo, el código here :

  unordered_map<char, int> mymap;
  pair<unordered_map<char,int>::iterator,bool> ret;

  // first insert function version (single parameter):;
  mymap.insert ( pair<char,int>(''z'',200) );
  ret=mymap.insert (pair<char,int>(''z'',500) ); 
  if (ret.second==false)
  {
    cout << "element ''z'' already existed";
    cout << " with a value of " << ret.first->second << endl;
  }

El código aquí inserta el par <''z'',200> en el mapa si no existe. Devuelve el iterador donde se inserta si el valor del segundo elemento del par devuelto es verdadero, o, devuelve el iterador donde estaba realmente el elemento, si el segundo elemento del par es falso.

Answer 3

operator[] insertará una entrada para usted con un valor construido por defecto, si es que uno ya no está allí. Es equivalente a, pero probablemente se implementará de manera más eficiente que:

iterator iter = map.find(key);

if(iter == map.end())
{
    iter = map.insert(value_type(key, int())).second;
}

return iter;

operator[] puede ser más rápido que hacer el trabajo manualmente con find() e insert() , ya que puede ahorrar tener que volver a manipular la clave.

Una forma en que puede evitar tener varias búsquedas en su código es tomar una referencia al valor:

int &stored_val = map[key];

// return the corresponding value if we find the key in the map - ie != 0
if (stored_val) return stored_val;

// if not in map
stored_val = value;

return value;

Tenga en cuenta que si el valor no existe en el mapa, el operator[] construirá por defecto e insertará uno. Entonces, si bien esto evitará las búsquedas múltiples, en realidad podría ser más lento si se usa con un tipo que es más lento de construir por defecto + asignar que de construir-copiar o mover.

Sin embargo, con int , que a bajo costo se construye a 0, es posible que pueda tratar 0 como un número mágico que significa vacío. Esto parece que podría ser el caso en su ejemplo.

Si no tienes ese número mágico, tienes dos opciones. Lo que debe usar depende de lo caro que sea para usted calcular el valor.

Primero, cuando la clave es barata, pero calcular el valor es costoso, find() puede ser la mejor opción. Esto duplicará dos veces pero solo calculará el valor cuando sea necesario:

iterator iter = map.find(key);

// return the corresponding value if we find the key in the map
if(iter != map.end()) return iter->second;

// if not in map
map.insert(value_type(key, value));

return value;

Pero si ya tiene el valor, puede hacerlo de manera muy eficiente, tal vez un poco más eficiente que usar un número mágico de referencia como el anterior:

pair<iterator,bool> iter = map.insert(value_type(key, value));
return iter->second;

Si el bool devuelto por map.insert(value_type) es verdadero, el elemento fue insertado. De lo contrario, ya existía y no se hicieron modificaciones. El iterador devolvió puntos al valor insertado o existente en el mapa. Para su ejemplo simple, esta puede ser la mejor opción.