¿Cómo mover eficientemente (algunos) elementos de un std :: map a otro?

8

Tengo dos std::map<>objetos ay me bgustaría mover ( extract+ insert) algunos elementos (nodos) de un mapa a otro según algún predicado p.

for (auto i = a.begin(); i != a.end(); ++i)
    if (p(*i))
        b.insert(a.extract(i))

Este código se divide en clang. Supongo que el problema es el incremento de idespués de que su nodo se haya extraído de a.

¿Es la forma correcta / única de solucionar esto usando un post-incremento ?, por ejemplo:

for (auto i = a.begin(); i != a.end();)
    if (p(*i))
        b.insert(a.extract(i++))
    else
        ++i;

EDITAR : eliminé la parte sobre "¿por qué esto funciona en gcc?", Porque no puedo reproducir esto en mi configuración actual. Estoy convencido de que solía hacerlo en algún momento, pero con gcc 9.2.1 obtengo un punto muerto (en lugar de un segfault). De cualquier manera, incrementar después extract()no funciona.

axxel
fuente
3
@Eljay En mi opinión, la nueva API de empalme de " controlador de nodo " del mapa en C ++ 17 está suficientemente especializada como para justificar su propia pregunta. Espero que esto no esté cerrado como un duplicado.
NicholasM
Posible duplicado de Eliminar elementos de std :: set mientras se itera . std::sety std::mapson muy similares, y por lo que puedo decir extracttiene las mismas implicaciones de invalidación que erase.
François Andrieux el
¿Qué versión de clang y gcc usaste? Para mí, usar clang 8.0 y gcc 7.4, ambos resultan en una segfault.
Balázs Kovacsics el
Me sorprende que este código funcione en cualquier compilador. No está manejando la invalidación
causada

Respuestas:

6

Supongo que el problema es el incremento de i después de que su nodo se haya extraído de a.

En efecto. La extracción invalida los iteradores del elemento extraído, y ies ese iterador. El comportamiento de incrementar o indirectamente a través de un iterador no válido no está definido.

¿Por qué esto aparentemente funciona en gcc pero no en clang?

Porque el comportamiento del programa no está definido.

¿Es la forma correcta / única de solucionar esto con un incremento posterior?

Es una forma correcta de solucionar esto. No es una manera particularmente mala. Si prefiere no repetir el incremento, un enfoque es usar una variable:

for (auto i = a.begin(); i != a.end();) {
    auto current = i++;
    if (p(*current)) {
        // moving is probably unnecessary
        b.insert(a.extract(std::move(current)));
    }
}
eerorika
fuente
Es una buena manera (razonablemente) suponiendo que copiar el estado del iterador es menos costoso que copiar el nodo.
Spencer el
@Spencer copiar un iterador suele ser trivial. Pero agregué un movimiento por si acaso.
eerorika
@Spencer currentse quedaría en un estado de mudanza . Cualquiera que sea ese estado no importará ya que ya no se usa después de eso.
Eerorika
@eeroika Gracias, miré tu código un poco más de cerca y me di cuenta de eso.
Spencer el
Me gusta su variable local mejor que tener dos icrements, pero sugeriría una mejora menor: limite el alcance currentutilizando la if (auto current = ++i; p(*current))sintaxis de c ++ 17s .
axxel