Usando El Operador [] De Manera Eficiente Con C++ unordered map

Question

Usando El Operador [] De Manera Eficiente Con C++ unordered map

En primer lugar, ¿podría alguien aclarar si en C++ el uso del operador [] junto con un unordered_map para búsquedas envuelve una llamada al método find (), o está usando 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 no está ya en el unordered_map estoy realizando una segunda búsqueda a través de la línea map[key] = value para reemplazar el valor predeterminado creado allí mediante el operador [] cuando una clave no está presente.

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

Aquí está el fragmento de 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;

31

c++unordered-map

Author: Adam Stelmaszczyk, 2011-08-01

Source

3 answers

Puede comprobar si existe un elemento, y insertar un nuevo elemento si no existe, con la función especial insert 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 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 true, o, devuelve el iterador donde estaba realmente el elemento, si el segundo elemento del par es falso.

9

Author: Diego Sevilla,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-08-01 11:50:54

En primer lugar, ¿podría alguien aclarar si en C++ el uso del operador [] junto con un unordered_map para búsquedas envuelve una llamada al método Find (), o está usando 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 sea utilizado internamente por find().

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.

(...) hay una manera (tal vez mediante el uso de punteros o algo) que solo podría realizar una mirada hacia arriba 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;

2

Author: Ferdinand Beyer,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-08-01 11:39:15

score 41 · Accepted Answer

operator[] insertará una entrada para usted con un valor construido por defecto, si uno no está ya 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() y insert(), porque puede ahorrar tener que volver a hash 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;

Nota que si el valor no existe en el mapa, operator[] predeterminada-construir e inserte uno. Así que aunque 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 default-construct + assign que para copy-or move-construct.

Sin embargo, con int, que por defecto 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 tal número mágico, has tengo dos opciones. Lo que debe usar depende de lo caro que sea para usted calcular el valor.

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

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

return value;

Pero si ya tienes el valor, puedes hacerlo de manera muy eficiente perhaps quizás ligeramente más eficiente que usar un número mágico de referencia + como arriba:

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 ítem fue insertado. De lo contrario, ya existía y no se hicieron modificaciones. El iterador devuelto apunta al valor insertado o existente en el mapa. Para su ejemplo simple, esta puede ser la mejor opción.