que - vector c++ pdf

¿Es seguro push_back un elemento del mismo vector?

Question

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

Si el segundo push_back causa 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?

Answer 1

Ambos están 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) Añade una copia de t. Requiere: T debe ser CopiaInstable en X.
• a.push_back (rv) Añade una copia de rv. Requiere: T debe ser MoveInsertable en X.

Las implementaciones de push_back deben garantizar que se inserte una copia de v[0] . Por ejemplo, asumiendo una implementación que reasignaría antes de copiar, no anexaría seguramente una copia de v[0] y como tal violaría las especificaciones.

Answer 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. 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 se redimensiona. Entonces, si la capacity() > size() del vector capacity() > size() entonces está garantizado que funciona, de lo contrario se garantiza que es un comportamiento indefinido.

Answer 3

El estándar garantiza incluso su primer ejemplo para estar seguro. Citando a C ++ 11

[sequence.reqmts]

3 En las tablas 100 y 101 ... X denota una clase de contenedor de secuencia, a denota un valor de X contiene elementos de tipo T , ... t denota un lvalue o un valor de const de X::value_type

16 Tabla 101 ...

Expresión a.push_back(t) Tipo de retorno void Semántica operacional Añade una copia de t. Requiere: T debe ser CopyInsertable en X Container basic_string , deque , list , vector

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

Answer 4

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

El std::vector::push_back libc ++ llama a __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.
}

Answer 5

La primera versión definitivamente NO es segura:

Las operaciones en los iteradores obtenidos llamando a un contenedor de biblioteca estándar o una función miembro de cadena pueden acceder al contenedor subyacente, pero no deben modificarlo. [Nota: en particular, las operaciones de contenedores 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, que normalmente se piensa junto con el enhebrado ... pero la definición actual implica relaciones de "pasa antes", y no veo ninguna relación entre los múltiples efectos secundarios de push_back en juego aquí, es decir, la invalidación de referencia parece no estar definida como ordenada con respecto a la copia-construcción del nuevo elemento de cola.

Answer 6

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

Pero al menos parece ser seguro con Visual Studio 2010. Su implementación de push_back hace un manejo especial del caso cuando se push_back 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
                    ...
        }
    }

Answer 7

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

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

Ejemplos:

Given 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:

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

Answer 8

Sí, es seguro, y las implementaciones estándar de la biblioteca saltan a través de aros para que sea así.

Creo que los implementadores rastrean este requisito hasta el 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.

Answer 9

Es completamente seguro

En tu segundo ejemplo, tienes

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

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

Vector es responsable de esto, no tú.