c++ - ¿El vector movido siempre está vacío?

c++11 language-lawyer

Question

Sé que, en general, el estándar impone pocos requisitos sobre los valores que se han movido desde:

N3485 17.6.5.15 [lib.types.movedfrom] / 1:

Los objetos de tipos definidos en la biblioteca estándar de C ++ se pueden mover desde (12.8). Las operaciones de movimiento pueden especificarse explícitamente o generarse implícitamente. A menos que se especifique lo contrario, dichos objetos movidos se colocarán en un estado válido pero no especificado.

No puedo encontrar nada acerca del vector que explícitamente lo excluya de este párrafo. Sin embargo, no puedo llegar a una implementación sensata que dé como resultado que el vector no esté vacío.

¿Hay algún estándar que implique esto que me falta o es similar al tratamiento de basic_string como un buffer contiguo en C ++ 03 ?

Answer 1

Dejé comentarios en este sentido sobre otras respuestas, pero tuve que salir corriendo antes de explicarlo por completo. El resultado de un vector movido siempre debe estar vacío, o en el caso de la asignación de movimiento, debe estar vacío o el estado del objeto anterior (es decir, un intercambio) porque de lo contrario no se pueden cumplir las reglas de invalidación del iterador, es decir, un movimiento no los invalida. Considerar:

std::vector<int> move;
std::vector<int>::iterator it;
{
std::vector<int> x(some_size);
it = x.begin();
move = std::move(x);
}
std::cout << *it;

Aquí puede ver que la invalidación del iterador expone la implementación del movimiento. El requisito de que este código sea legal, específicamente que el iterador sigue siendo válido, impide que la implementación realice una copia, almacenamiento de objetos pequeños o algo similar. Si se hizo una copia, it invalidará cuando se vacíe la opción opcional, y lo mismo es cierto si el vector usa algún tipo de almacenamiento basado en SSO. Básicamente, la única implementación posible razonable es intercambiar punteros o simplemente moverlos.

Por favor, vea las cotizaciones estándar sobre los requisitos para todos los contenedores:

X u(rv)
X u = rv

publicación: u será igual al valor que rv tenía antes de esta construcción

a = rv

a será igual al valor que rv tenía antes de esta asignación

La validez del iterador es parte del valor de un contenedor. Aunque el estándar no lo establece de manera inequívoca, podemos ver, por ejemplo, en

begin () devuelve un iterador que hace referencia al primer elemento en el contenedor. end () devuelve un iterador que es el valor pasado para el contenedor. Si el contenedor está vacío, entonces begin () == end ();

Cualquier implementación que realmente se movió de los elementos de la fuente en lugar de intercambiar la memoria sería defectuosa, por lo que sugiero que cualquier redacción estándar que diga lo contrario es un defecto, no menos importante porque el estándar no es de hecho muy claro en este punto . Estas citas son de N3691.

Answer 2

En muchas situaciones, la construcción de movimiento y la asignación de movimiento se pueden implementar delegando para swap , especialmente si no hay asignadores implicados. Hay varias razones para hacer eso:

• swap tiene que ser implementado de todos modos
• eficiencia del desarrollador porque se debe escribir menos código
• eficiencia del tiempo de ejecución porque se ejecutan menos operaciones en total

Aquí hay un ejemplo de movimiento-asignación. En este caso, el vector de movimiento no estará vacío, si el vector movido no estuviera vacío.

auto operator=(vector&& rhs) -> vector&
{
if (/* allocator is neither move- nor swap-aware */) {
swap(rhs);
} else {
...
}
return *this;
}

Answer 3

Llego tarde a esta fiesta y ofrezco una respuesta adicional porque no creo que ninguna otra respuesta en este momento sea completamente correcta.

Pregunta:

¿El vector movido siempre está vacío?

Responder:

Por lo general, pero no, no siempre.

Los detalles sangrientos:

vector no tiene un estado definido como estándar, como lo hacen algunos tipos (por ejemplo, se especifica que unique_ptr es igual a nullptr después de ser movido). Sin embargo, los requisitos para vector son tales que no hay demasiadas opciones.

La respuesta depende de si estamos hablando del constructor de movimiento de vector o el operador de asignación de movimiento. En el último caso, la respuesta también depende del asignador del vector .

vector<T, A>::vector(vector&& v)

Esta operación debe tener complejidad constante. Eso significa que no hay más opciones que robar recursos de v para construir *this , dejando v en un estado vacío. Esto es cierto sin importar cuál es el asignador A , ni cuál es el tipo T

Entonces, para el constructor de movimientos, sí, el vector movido siempre estará vacío. Esto no se especifica directamente, pero se sale del requisito de complejidad y del hecho de que no hay otra forma de implementarlo.

vector<T, A>&
vector<T, A>::operator=(vector&& v)

Esto es considerablemente más complicado. Hay 3 casos principales:

Uno:

allocator_traits<A>::propagate_on_container_move_assignment::value == true

( propagate_on_container_move_assignment evalúa como true_type )

En este caso, el operador de asignación de movimiento destruirá todos los elementos en *this , desasignará la capacidad utilizando el asignador desde *this , moverá asignar los asignadores y luego transferirá la propiedad del búfer de memoria de v a *this . Excepto por la destrucción de elementos en *this , esta es una operación de complejidad O (1). Y típicamente (por ejemplo, en la mayoría, pero no en todos los algoritmos std ::), el lhs de una asignación de movimiento tiene empty() == true antes de la asignación de movimiento.

Nota: En C ++ 11 la propagate_on_container_move_assignment para std::allocator es false_type , pero esto ha sido cambiado a true_type para C ++ 1y (y == 4, esperamos).

En el caso Uno, el vector movido desde siempre estará vacío.

Dos:

allocator_traits<A>::propagate_on_container_move_assignment::value == false
&& get_allocator() == v.get_allocator()

( propagate_on_container_move_assignment evalúa como false_type , y los dos asignadores se comparan por igual)

En este caso, el operador de asignación de movimiento se comporta como en el caso uno, con las siguientes excepciones:

1. Los asignadores no tienen movimiento asignado.
2. La decisión entre este caso y el caso Tres ocurre en tiempo de ejecución, y el caso Tres requiere más de T , y también lo hace el caso Dos, aunque el caso Dos en realidad no ejecuta esos requisitos adicionales en T

En el caso Dos, el vector movido siempre estará vacío.

Tres:

allocator_traits<A>::propagate_on_container_move_assignment::value == false
&& get_allocator() != v.get_allocator()

( propagate_on_container_move_assignment evalúa como false_type , y los dos asignadores no se comparan por igual)

En este caso, la implementación no puede mover asignar los asignadores, ni puede transferir ningún recurso de v a *this (los recursos son el buffer de memoria). En este caso, la única forma de implementar el operador de asignación de movimiento es efectivamente:

typedef move_iterator<iterator> Ip;
assign(Ip(v.begin()), Ip(v.end()));

Es decir, mueva cada T individual de v a *this . La assign puede reutilizar tanto la capacity como el size en *this si está disponible. Por ejemplo, si *this tiene el mismo size que v la implementación puede mover, asigne cada T de v a *this . Esto requiere que T sea MoveAssignable . Tenga en cuenta que MoveAssignable no requiere que T tenga un operador de asignación de movimiento. Un operador de asignación de copias también será suficiente. MoveAssignable significa que T debe ser asignable desde un valor r T

Si el size de *this no es suficiente, entonces se deberá construir una nueva T en *this . Esto requiere que T sea MoveInsertable . Para cualquier asignador cuerdo que pueda pensar, MoveInsertable reduce a lo mismo que MoveConstructible , lo que significa que es construible a partir de un valor r T (no implica la existencia de un constructor de movimiento para T ).

En el caso Tres, el vector movido desde, en general, no estará vacío. Podría estar lleno de elementos movidos. Si los elementos no tienen un constructor de movimiento, esto podría ser equivalente a una asignación de copia. Sin embargo, no hay nada que obligue esto. El implementador es libre de hacer un trabajo extra y ejecutar v.clear() si así lo desea, dejando v vacío. No estoy al tanto de ninguna implementación que lo haga, ni conozco ningún motivo para que una implementación lo haga. Pero no veo nada que lo prohíba.

David Rodríguez informa que GCC 4.8.1 llama a v.clear() en este caso, dejando v vacío. libc ++ no lo hace, lo que deja v no está vacío. Ambas implementaciones son conformes.

Answer 4

Si bien puede no ser una implementación sensata en el caso general, una implementación válida del constructor / asignación de movimiento es simplemente copiar los datos de la fuente, dejando la fuente intacta. Además, para el caso de asignación, mover puede implementarse como intercambio, y el contenedor movido puede contener el valor anterior del contenedor movido .

La implementación del movimiento como copia realmente puede suceder si usamos asignadores polimórficos, como hacemos nosotros, y el asignador no se considera parte del valor del objeto (y por lo tanto, la asignación nunca cambia el asignador real que se está utilizando). En este contexto, una operación de movimiento puede detectar si el origen y el destino usan el mismo asignador. Si usan el mismo asignador, la operación de movimiento puede mover los datos de la fuente. Si utilizan diferentes asignadores, entonces el destino debe copiar el contenedor de origen.