c++ - unordered_set - std:: unordered set

std:: unordered_set<T>:: insert(T &&): se mueve el argumento si existe

Question

Esta pregunta trata sobre la especificación de varias funciones en la Biblioteca estándar de C ++ 11, que toman sus argumentos como referencias de valor, pero no los consumen en todos los casos. Un ejemplo es std::unordered_set<T>::insert(T&&) .

Es bastante claro que este método utilizará el constructor de movimientos de T para construir el elemento dentro del contenedor, si aún no existe. Sin embargo, ¿qué pasa si el elemento ya existe en el contenedor? Estoy bastante seguro de que no hay razón para cambiar el objeto en el caso. Sin embargo, no encontré nada en el Estándar C ++ 11 que respalde mi reclamo.

Aquí hay un ejemplo para mostrar por qué esto podría ser interesante. El siguiente código lee las líneas de std :: cin y elimina la primera aparición de líneas duplicadas.

std::unordered_set<std::string> seen;
std::string line;
while (getline(std::cin, line)) {
    bool inserted = seen.insert(std::move(line)).second;
    if (!inserted) {
        /* Is it safe to use line here, i.e. can I assume that the
         * insert operation hasn''t changed the string object, because 
         * the string already exists, so there is no need to consume it. */
        std::cout << line << ''/n'';
    }
}

Al parecer, este ejemplo funciona con GCC 4.7. Pero no estoy seguro, si es correcto según la norma.

Answer 1

Encontré esta nota en el estándar (17.4.6.9):

[ Nota : Si un programa convierte un lvalue en un xvalue mientras le pasa ese lvalue a una función de la biblioteca (por ejemplo, llamando a la función con el argumento move(x) ), el programa está solicitando esa función para tratar ese lvalue como temporal. La implementación es libre de optimizar las comprobaciones de alias que puedan ser necesarias si el argumento fuera un valor l. - nota final]

Si bien no responde directamente a su pregunta, sí indica que efectivamente ha "dado" el argumento a la función de biblioteca como un temporal, por lo que no confiaría en su valor una vez que haya llamado insert . Por lo que puedo decir, una implementación de biblioteca tendría derecho a moverse desde el parámetro incluso si posteriormente determina que no va a mantener el valor en el contenedor.

Answer 2

Es correcto.

Por supuesto, cuando se trata de filosofía, cualquier cosa puede ser cuestionada, pero el compilador debe hacerlo de alguna manera.

La elección de los diseñadores fue que, para realizar un movimiento , debe haber un lugar al que ir . Si no hay tal lugar, el movimiento no ocurre.

Tenga en cuenta que cualquier función que tome un &&, asume que el parámetro es "temporal": si no "robó" los datos, el temporal se destruirá al final de la expresión. Si la temporalidad ha sido coaccionada (a través de std :: move), el objeto permanecerá allí en cualquier caso hasta que sea destruido por su propio alcance. Con o sin sus datos originales en su interior.

Answer 3

La semántica dada para la insert en contenedores asociativos no ordenados en §23.2.5 / Tabla 103 no especifica si el constructor de movimiento del argumento a insert se invoca si la inserción falla, la redacción solo se refiere a si ocurre la inserción:

a_uniq.insert(t)

Devoluciones: pair<iterator, bool>

Requiere: Si t es una expresión de valor no constante, T será MoveInsertable into X; de lo contrario, T será CopyInsertable en X

Efectos: inserta t si y solo si no hay ningún elemento en el contenedor con la clave equivalente a la clave de t . El componente bool del par devuelto indica si la inserción tiene lugar, y el componente iterador apunta al elemento con una clave equivalente a la clave de t .

Sin embargo, la especificación para emplace es más clara (también de la Tabla 103), y debería poder usarla en lugar de insert para obtener las garantías que desea:

a_uniq.emplace(args)

Devoluciones: pair<iterator, bool>

Requiere: T será EmplaceConstructible en X desde args.

Efectos: inserta un objeto t construido con std :: forward (args) ... si y solo si no hay ningún elemento en el contenedor con clave equivalente a la clave de t . El componente bool del par devuelto es verdadero si y solo si la inserción tiene lugar, y el componente iterador del par apunta al elemento con la clave equivalente a la clave de t .

Interpreto que esto significa ((Inserta un objeto t construido t ...) (si y solo si no hay ningún elemento en el contenedor ...)), es decir , tanto la inserción como la construcción solo deberían ocurrir si no hay un elemento coincidente. Ya en el contenedor. Si no se construye ningún objeto, la std::string que pasa nunca se pasará a un constructor de movimiento, y por lo tanto seguirá siendo válida después de la llamada emplace fallida.

gcc 4.7.0 no parece admitir unordered_set::emplace , pero está en el estándar (§23.5.6.1)

Como @NicolBolas señaló en los comentarios, y a pesar de lo anterior, es imposible implementar una función emplace que no construya una T si ya existe una entrada conflictiva.

Por lo tanto, la única forma de obtener la semántica que desea de una manera que cumpla con los estándares sería haciendo un find seguido, de manera condicional, de un insert o emplace .