programacion - que es un iterador c++

¿Mover un vector invalida los iteradores?

Question

Si tengo un iterador en el vector a , entonces muevo, construyo o muevo, asigno el vector b desde a , ¿ese iterador aún apunta al mismo elemento (ahora en el vector b )? Esto es lo que quiero decir en el código:

#include <vector>
#include <iostream>

int main(int argc, char *argv[])
{
    std::vector<int>::iterator a_iter;
    std::vector<int> b;
    {
        std::vector<int> a{1, 2, 3, 4, 5};
        a_iter = a.begin() + 2;
        b = std::move(a);
    }
    std::cout << *a_iter << std::endl; // Is a_iter valid here?
    return 0;
}

¿ a_iter sigue siendo válido ya que a se ha movido a b , o el iterador es invalidado por el movimiento? Como referencia, std::vector::swap no invalida los iteradores .

Answer 1

Como no hay nada que impida que un iterador mantenga una referencia o un puntero al contenedor original, diría que no puede confiar en que los iteradores permanezcan válidos a menos que encuentre una garantía explícita en el estándar.

Answer 2

Creo que la edición que cambió la construcción de movimientos para mover la asignación cambia la respuesta.

Al menos, si estoy leyendo la tabla 96 correctamente, la complejidad para la construcción de movimientos se da como "nota B", que es una complejidad constante para todo menos std::array . La complejidad para la asignación de movimiento, sin embargo, se da como lineal.

Como tal, la construcción de movimientos no tiene más remedio que copiar el puntero de la fuente, en cuyo caso es difícil ver cómo los iteradores podrían volverse inválidos.

Sin embargo, para la asignación de movimiento, la complejidad lineal significa que podría elegir mover elementos individuales de la fuente al destino, en cuyo caso los iteradores casi con certeza se volverán inválidos.

La posibilidad de asignación de movimiento de elementos se refuerza con la descripción: "Todos los elementos existentes de a se asignan o se destruyen". La parte "destruida" correspondería a la destrucción de los contenidos existentes y al "robo" del puntero de la fuente, pero el "movimiento asignado a" indicaría mover elementos individuales de la fuente al destino.

Answer 3

Si bien podría ser razonable suponer que los iterator siguen siendo válidos después de una move , no creo que el Estándar realmente lo garantice. Por lo tanto, los iteradores están en un estado indefinido después del move .

No hay ninguna referencia que pueda encontrar en el Estándar que indique específicamente que los iteradores que existían antes de un move siguen siendo válidos después del move .

En la superficie, parece ser perfectamente razonable suponer que un iterator se implementa típicamente como punteros en la secuencia controlada. Si ese es el caso, entonces los iteradores seguirían siendo válidos después del move .

Pero la implementación de un iterator está definida por la implementación. Es decir, siempre que el iterator en una plataforma particular cumpla con los requisitos establecidos por el Estándar, se puede implementar de cualquier manera. Podría, en teoría, implementarse como una combinación de un puntero a la clase vector junto con un índice. Si ese es el caso, entonces los iteradores se volverían inválidos después del move .

Si un iterator se implementa o no de esta manera es irrelevante. Podría implementarse de esta manera, por lo que sin una garantía específica del Estándar de que los iteradores posteriores al move sigan siendo válidos, no se puede suponer que sí lo son. Tenga en cuenta también que existe tal garantía para los iteradores después de un swap . Esto fue específicamente aclarado del Estándar anterior. Quizás fue simplemente un descuido del comité de Std no hacer una aclaración similar para los iteradores después de una move , pero en cualquier caso no hay tal garantía.

Por lo tanto, lo largo y lo corto es que no puede suponer que sus iteradores siguen siendo buenos después de un move .

EDITAR:

23.2.1 / 11 en el Borrador n3242 establece que:

A menos que se especifique lo contrario (ya sea explícitamente o definiendo una función en términos de otras funciones), invocar una función de miembro de contenedor o pasar un contenedor como argumento a una función de biblioteca no invalidará los iteradores ni cambiará los valores de los objetos dentro de ese contenedor .

Esto podría llevar a concluir que los iteradores son válidos después de un move , pero no estoy de acuerdo. En su código de ejemplo, a_iter era un iterador en el vector a . Después del move , ese contenedor, a ciertamente ha sido cambiado. Mi conclusión es que la cláusula anterior no se aplica en este caso.

Answer 4

tl; dr: Sí, mover un std::vector<T, A> posiblemente invalide los iteradores

_{El caso común (con std::allocator in place) es que la invalidación no ocurre pero no hay garantía y el cambio de compiladores o incluso la próxima actualización del compilador puede hacer que el código se comporte incorrectamente si confía en el hecho de que su implementación actualmente no lo hace invalidar los iteradores.}

En la asignación de movimiento :

La cuestión de si los iteradores std::vector pueden seguir siendo válidos después de la asignación de movimiento se conecta con el conocimiento del asignador de la plantilla vectorial y depende del tipo de asignador (y posiblemente las instancias respectivas de los mismos).

En cada implementación que he visto, mover-asignación de un std::vector<T, std::allocator<T>> ¹ no invalidará los iteradores o punteros. Sin embargo, hay un problema cuando se trata de hacer uso de esto, ya que el estándar simplemente no puede garantizar que los iteradores sigan siendo válidos para cualquier asignación de movimiento de una instancia std::vector en general, porque el contenedor es consciente del asignador.

Los asignadores personalizados pueden tener estado y si no se propagan en la asignación de movimiento y no se comparan iguales, el vector debe asignar almacenamiento para los elementos movidos utilizando su propio asignador.

Dejar:

std::vector<T, A> a{/*...*/};
std::vector<T, A> b;
b = std::move(a);

Ahora si

1. std::allocator_traits<A>::propagate_on_container_move_assignment::value == false &&
2. std::allocator_traits<A>::is_always_equal::value == false && ( posiblemente a partir de c ++ 17 )
3. a.get_allocator() != b.get_allocator()

entonces b asignará nuevo almacenamiento y moverá elementos de uno por uno a ese almacenamiento, invalidando así todos los iteradores, punteros y referencias.

La razón es que el cumplimiento de la condición anterior 1. prohíbe la asignación de movimiento del asignador en el movimiento del contenedor. Por lo tanto, tenemos que lidiar con dos instancias diferentes del asignador. Si esos dos objetos asignador ahora no se comparan igual ( 2 ) ni se comparan igual, entonces ambos asignan- tes tienen un estado diferente. Un asignador x puede no ser capaz de desasignar la memoria de otro asignador que tiene un estado diferente y, por lo tanto, un contenedor con asignador x no puede simplemente robar memoria de un contenedor que asignó su memoria a través de y .

Si el asignador se propaga en la asignación de movimiento o si ambos asignadores se comparan por igual, es muy probable que una implementación elija simplemente hacer su propia información porque puede estar seguro de poder desasignar el almacenamiento correctamente.

¹ : std::allocator_traits<std::allocator<T>>::propagate_on_container_move_assignment y std::allocator_traits<std::allocator<T>>::is_always_equal ambos son tipdefs para std::true_type (para cualquier std::true_type no especializado) std::allocator ).

En movimiento de construcción :

std::vector<T, A> a{/*...*/};
std::vector<T, A> b(std::move(a));

El constructor de movimiento de un contenedor con reconocimiento de asignador moverá -construirá su instancia de asignador desde la instancia de asignación del contenedor desde el cual se mueve la expresión actual. Por lo tanto, se garantiza la capacidad adecuada de desasignación y la memoria puede (y de hecho será) robada porque la construcción de movimiento tiene (a excepción de std::array ) una complejidad constante.

Nota: Todavía no hay garantía de que los iteradores permanezcan válidos incluso para la construcción de movimientos.

En intercambio :

Exigir que los iteradores de dos vectores sigan siendo válidos después de un intercambio (ahora simplemente apuntando al respectivo contenedor intercambiado) es fácil porque el intercambio solo tiene un comportamiento definido si

1. std::allocator_traits<A>::propagate_on_container_swap::value == true ||
2. a.get_allocator() == b.get_allocator()

Por lo tanto, si los asignadores no se propagan en el intercambio y si no se comparan iguales, el intercambio de los contenedores es un comportamiento indefinido en primer lugar.