¿Es seguro hacer retroceder un elemento del mismo vector?

126
vector<int> v;
v.push_back(1);
v.push_back(v[0]);

Si el segundo push_back provoca una reasignación, la referencia al primer entero en el vector ya no será válida. ¿Entonces esto no es seguro?

vector<int> v;
v.push_back(1);
v.reserve(v.size() + 1);
v.push_back(v[0]);

Esto lo hace seguro?

Neil Kirk
fuente
44
Una nota: actualmente hay una discusión en el foro de propuestas estándar. Como parte de esto, alguien dio un ejemplo de implementación depush_back . Otro póster notó un error en él , que no manejó adecuadamente el caso que usted describe. Nadie más, por lo que puedo decir, argumentó que esto no era un error. No digo que sea una prueba concluyente, solo una observación.
Benjamin Lindley
9
Lo siento, pero no sé qué respuesta aceptar, ya que todavía hay controversia sobre la respuesta correcta.
Neil Kirk
44
El quinto comentario me pidió que comentara esta pregunta en: stackoverflow.com/a/18647445/576911 . Lo estoy haciendo al votar cada respuesta que dice actualmente: sí, es seguro hacer retroceder un elemento del mismo vector.
Howard Hinnant
2
@BenVoigt: <shrug> Si no está de acuerdo con lo que dice el estándar, o incluso si está de acuerdo con el estándar, pero no cree que lo diga con suficiente claridad, esta es siempre una opción para usted: cplusplus.github.io/LWG/ lwg-active.html # submit_issue He tomado esta opción más veces de las que puedo recordar. A veces con éxito, a veces no. Si desea debatir lo que dice el estándar, o lo que debería decir, SO no es un foro efectivo. Nuestra conversación no tiene significado normativo. Pero puede tener la oportunidad de tener un impacto normativo siguiendo el enlace de arriba.
Howard Hinnant
2
@ Polaris878 Si push_back hace que el vector alcance su capacidad, el vector asignará un nuevo buffer más grande, copiará los datos antiguos y luego eliminará el buffer anterior. Luego insertará el nuevo elemento. El problema es que el nuevo elemento es una referencia a los datos en el búfer anterior que acaba de eliminarse. A menos que push_back haga una copia del valor antes de eliminarlo, será una mala referencia.
Neil Kirk

Respuestas:

31

Parece que http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-closed.html#526 abordó este problema (o algo muy similar) como un defecto potencial en el estándar:

1) Los parámetros tomados por referencia constante se pueden cambiar durante la ejecución de la función

Ejemplos:

Dado std :: vector v:

v.insert (v.begin (), v [2]);

v [2] se puede cambiar moviendo elementos del vector

La resolución propuesta fue que esto no era un defecto:

Se requiere vector :: insert (iter, value) para funcionar porque el estándar no da permiso para que no funcione.

Nate Kohl
fuente
Encuentro permiso en 17.6.4.9: "Si un argumento a una función tiene un valor no válido (como un valor fuera del dominio de la función o un puntero no válido para su uso previsto), el comportamiento no está definido". Si se produce la reasignación, todos los iteradores y referencias a elementos se invalidan, lo que significa que la referencia de parámetro que se pasa a la función también es inválida.
Ben Voigt
44
Creo que el punto es que la implementación es responsable de hacer la reasignación. Le corresponde garantizar que el comportamiento se defina si la entrada se define inicialmente. Dado que las especificaciones especifican claramente que push_back hace una copia, las implementaciones deben, a expensas del tiempo de ejecución quizás, almacenar en caché o copiar todos los valores antes de desasignarlos. Como en esta pregunta en particular no quedan referencias externas, no importa si los iteradores y las referencias están invalidados.
OlivierD
3
@NeilKirk Creo que esta debería ser la respuesta autorizada, también lo menciona Stephan T. Lavavej en Reddit utilizando esencialmente los mismos argumentos.
TemplateRex
v.insert(v.begin(), v[2]);no puede desencadenar una reasignación. Entonces, ¿cómo responde esto a la pregunta?
ThomasMcLeod
@ThomasMcLeod: sí, obviamente puede desencadenar una reasignación. Está expandiendo el tamaño del vector insertando un nuevo elemento.
Violet Giraffe
21

Sí, es seguro, y las implementaciones de bibliotecas estándar saltan los aros para que así sea.

Creo que los implementadores rastrean este requisito hasta 23.2 / 11 de alguna manera, pero no puedo entender cómo, y tampoco puedo encontrar algo más concreto. Lo mejor que puedo encontrar es este artículo:

http://www.drdobbs.com/cpp/copying-container-elements-from-the-c-li/240155771

La inspección de las implementaciones de libc ++ y libstdc ++ muestra que también son seguras.

Sebastian Redl
fuente
9
Algún respaldo realmente ayudaría aquí.
Chris
3
Es interesante, debo admitir que nunca había considerado el caso, pero de hecho parece bastante difícil de lograr. ¿También se cumple para vec.insert(vec.end(), vec.begin(), vec.end());?
Matthieu M.
2
@MatthieuM. No: la Tabla 100 dice: "pre: i y j no son iteradores en a".
Sebastian Redl
2
Estoy votando ahora ya que este es mi recuerdo también, pero se necesita una referencia.
bames53
3
Es 23.2 / 11 en la versión que está utilizando "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 miembro de contenedor o pasar un contenedor como argumento a una función de biblioteca no invalidará iteradores ao cambiar los valores de objetos dentro de ese contenedor ". ? Pero vector.push_backNO especifica lo contrario. "Provoca la reasignación si el nuevo tamaño es mayor que la capacidad anterior". y (en reserve) "La reasignación invalida todas las referencias, punteros e iteradores que hacen referencia a los elementos en la secuencia".
Ben Voigt
13

El estándar garantiza que incluso su primer ejemplo sea seguro. Citando C ++ 11

[secuencia.reqmts]

3 En las Tablas 100 y 101 ... Xdenota una clase de contenedor de secuencia, adenota un valor de Xelementos de tipo que contiene T, ... tdenota un valor l o un valor constante deX::value_type

16 Tabla 101 ...

a.push_back(t) Tipo de retorno de expresión void Semántica operacional Agrega una copia de t. Requiere: T debe estar CopyInsertableen X. Envase basic_string , deque, list,vector

Entonces, aunque no es exactamente trivial, la implementación debe garantizar que no invalidará la referencia al hacer el push_back .

Angew ya no está orgulloso de SO
fuente
77
No veo cómo esto garantiza que esto sea seguro.
jrok
44
@Angew: invalida absolutamente t, la única pregunta es si antes o después de hacer la copia. Tu última oración es ciertamente incorrecta.
Ben Voigt
44
@BenVoigt Dado que tcumple con las condiciones previas enumeradas, el comportamiento descrito está garantizado. No se permite que una implementación invalide una condición previa y luego la use como una excusa para no comportarse como se especifica.
bames53
8
@BenVoigt El cliente no está obligado a mantener la condición previa durante la llamada; solo para garantizar que se cumpla al inicio de la llamada.
bames53
66
@BenVoigt Ese es un buen punto, pero creo que es necesario que el functor que se pasa for_eachno invalide los iteradores. No puedo encontrar una referencia para for_each, pero veo en algunos algoritmos texto como "op y binary_op no invalidará iteradores o subranges".
bames53
7

No es obvio que el primer ejemplo es seguro, porque la implementación más simple de push_back sería reasignar primero el vector, si es necesario, y luego copiar la referencia.

Pero al menos parece seguro con Visual Studio 2010. Su implementación push_backhace un manejo especial del caso cuando empujas un elemento en el vector. El código está estructurado de la siguiente manera:

void push_back(const _Ty& _Val)
    {   // insert element at end
    if (_Inside(_STD addressof(_Val)))
        {   // push back an element
                    ...
        }
    else
        {   // push back a non-element
                    ...
        }
    }
Johan Råde
fuente
8
Me gustaría saber si la especificación requiere que esto sea seguro.
Nawaz
1
De acuerdo con la Norma, no se requiere que sea seguro. Sin embargo, es posible implementarlo de manera segura.
Ben Voigt
2
@BenVoigt Diría que es necesario estar seguro (vea mi respuesta).
Angew ya no está orgulloso de SO
2
@BenVoigt En el momento en que pasa la referencia, es válida.
Angew ya no está orgulloso de SO
44
@Angew: Eso no es suficiente. Debe pasar una referencia que permanezca válida durante la duración de la llamada, y esta no lo hace.
Ben Voigt
3

Esto no es una garantía del estándar, pero como otro punto de datos, v.push_back(v[0])es seguro para libc ++ de LLVM .

std::vector::push_backLlamadas de libc ++__push_back_slow_path cuando necesita reasignar memoria:

void __push_back_slow_path(_Up& __x) {
  allocator_type& __a = this->__alloc();
  __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), 
                                                  size(), 
                                                  __a);
  // Note that we construct a copy of __x before deallocating
  // the existing storage or moving existing elements.
  __alloc_traits::construct(__a, 
                            _VSTD::__to_raw_pointer(__v.__end_), 
                            _VSTD::forward<_Up>(__x));
  __v.__end_++;
  // Moving existing elements happens here:
  __swap_out_circular_buffer(__v);
  // When __v goes out of scope, __x will be invalid.
}
Nate Kohl
fuente
La copia no solo debe hacerse antes de desasignar el almacenamiento existente, sino también antes de pasar de los elementos existentes. Supongo que el movimiento de los elementos existentes se realiza __swap_out_circular_buffer, en cuyo caso esta implementación es realmente segura.
Ben Voigt
@BenVoigt: buen punto, y tienes razón en que el movimiento ocurre dentro __swap_out_circular_buffer. (He agregado algunos comentarios para tener en cuenta eso.)
Nate Kohl el
1

La primera versión definitivamente NO es segura:

Las operaciones en iteradores obtenidas llamando a un contenedor de biblioteca estándar o una función de miembro de cadena pueden acceder al contenedor subyacente, pero no lo modificarán. [Nota: en particular, las operaciones de contenedor que invalidan los iteradores entran en conflicto con las operaciones en los iteradores asociados con ese contenedor. - nota final]

de la sección 17.6.5.9


Tenga en cuenta que esta es la sección sobre carreras de datos, en la que las personas normalmente piensan junto con el enhebrado ... pero la definición real implica relaciones "pasa antes", y no veo ninguna relación de orden entre los múltiples efectos secundarios de push_backin jugar aquí, es decir, la invalidación de referencia parece no definirse como ordenada con respecto a la construcción de copia del nuevo elemento de cola.

Ben Voigt
fuente
1
Debe entenderse que es una nota, no una regla, por lo que explica una consecuencia de la regla anterior ... y las consecuencias son idénticas para las referencias.
Ben Voigt
55
El resultado de v[0]no es un iterador, del mismo modo, push_back()no toma un iterador. Entonces, desde la perspectiva de un abogado de idiomas, su argumento es nulo. Lo siento. Sé que la mayoría de los iteradores son punteros, y el punto de invalidar un iterador es prácticamente el mismo que para las referencias, pero la parte del estándar que usted cita, es irrelevante para la situación en cuestión.
cmaster - reinstalar a monica el
-1. Es una cita completamente irrelevante y no la responde de todos modos. El comité dice que x.push_back(x[0])es SEGURO.
Nawaz
0

Es completamente seguro

En tu segundo ejemplo tienes

v.reserve(v.size() + 1);

lo cual no es necesario porque si el vector sale de su tamaño, implicará el reserve.

Vector es responsable de estas cosas, no tú.

Zaffy
fuente
-1

Ambos son seguros ya que push_back copiará el valor, no la referencia. Si está almacenando punteros, eso todavía es seguro en lo que respecta al vector, pero solo sepa que tendrá dos elementos de su vector apuntando a los mismos datos.

Sección 23.2.1 Requisitos generales del contenedor

dieciséis
  • a.push_back (t) Agrega una copia de t. Requiere: T será CopyInsertable en X.
  • a.push_back (rv) Agrega una copia de rv. Requiere: T será MoveInsertable en X.

Por lo tanto, las implementaciones de push_back deben garantizar que se inserte una copia de v[0] . Por contraejemplo, suponiendo una implementación que se reasignaría antes de copiar, seguramente no agregaría una copia v[0]y, como tal, violaría las especificaciones.

OlivierD
fuente
2
push_backsin embargo, también cambiará el tamaño del vector, y en una implementación ingenua esto invalidará la referencia antes de que se realice la copia. Entonces, a menos que pueda respaldar esto con una cita del estándar, lo consideraré incorrecto.
Konrad Rudolph el
44
Por "esto", ¿te refieres al primer o al segundo ejemplo? push_backcopiará el valor en el vector; pero (por lo que puedo ver) eso podría suceder después de la reasignación, en cuyo punto la referencia desde la que intenta copiar ya no es válida.
Mike Seymour
1
push_backrecibe su argumento por referencia .
bames53
1
@OlivierD: Tendría que (1) asignar nuevo espacio (2) copiar el nuevo elemento (3) mover-construir los elementos existentes (4) destruir los elementos movidos desde (5) liberar el almacenamiento anterior, en ESE orden - para que la primera versión funcione.
Ben Voigt
1
@BenVoigt ¿por qué si un contenedor requeriría que un tipo sea CopyInsertable si va a ignorar por completo esa propiedad?
OlivierD
-2

Desde 23.3.6.5/1: Causes reallocation if the new size is greater than the old capacity. If no reallocation happens, all the iterators and references before the insertion point remain valid.

Como estamos insertando al final, no se invalidarán las referencias si el vector no cambia de tamaño. Entonces, si el vector está capacity() > size()garantizado para funcionar, de lo contrario se garantiza que será un comportamiento indefinido.

Mark B
fuente
Creo que la especificación realmente garantiza que esto funcione en cualquier caso. Aunque estoy esperando una referencia.
bames53
No hay mención de iteradores o seguridad de iterador en la pregunta.
OlivierD
3
@OlivierD la parte del iterador es superflua aquí: estoy interesado en la referencesparte de la cita.
Mark B
2
En realidad, está garantizado que es seguro (vea mi respuesta, semántica de push_back).
Angew ya no está orgulloso de SO