Usando el operador [] de manera eficiente con C++ unordered_map

operator[] insertará una entrada para usted con un valor construido por defecto, si aún no hay uno 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())).first;
}

return *iter;

operator[] puede ser más rápido que hacer el trabajo manualmente con find() y insert() , porque puede evitar tener que volver a codificar la clave.

Una forma de evitar tener múltiples 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, operator[] construirá por defecto e insertará uno. Entonces, si bien esto evitará múltiples búsquedas, en realidad podría ser más lento si se usa con un tipo que es más lento para construir por defecto + asignar que para copiar o mover-construir.

Con int sin embargo, que se construye por defecto a bajo costo en 0, es posible que pueda tratar 0 como un número mágico que significa vacío. Parece que este podría ser el caso en tu ejemplo.

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

Primero, cuando codificar la clave es barato pero calcular el valor es caro, find() puede ser la mejor opción. Esto generará un hash 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;

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

return value;

Pero si ya tiene el valor, puede hacerlo de manera muy eficiente, quizás un poco más eficiente que usar una referencia + número mágico como se indicó anteriormente:

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

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.

Ambos pueden comprobar si existe un elemento, y insertar un nuevo elemento si no existe, con el especial insert función que devuelve un pair<iterator, bool> en el que el valor booleano le dice si el valor se ha insertado realmente. Por ejemplo, el código aquí:

  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 realmente estaba el elemento, si el segundo elemento del par es falso.

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

Tampoco hay garantía sobre cuál es más rápido. find() implica una sobrecarga en la construcción y 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.

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;