¿std :: vector llama a la función de intercambio cuando está creciendo? ¿Siempre o solo para algunos tipos?

Question

Hasta donde yo sé, puedo usar un vector de vectores (std::vector< std::vector<int> >) y esto será bastante eficiente, porque internamente los elementos no se copiarán, sino que se intercambiarán, lo que es mucho más rápido, porque no incluye la copia de los búfers de memoria . ¿Estoy en lo cierto?

¿Cuándo hace exactamente std::vector el uso de la función de intercambio? No puedo encontrar nada al respecto en el C++ standard. ¿Sucede durante la reasignación del búfer?

Hice algunas pruebas para averiguarlo, pero fallé. La función de intercambio para mi tipo de datos personalizado no se llama en absoluto.

EDITAR: Aquí está mi test program.

Answer 1

No tengo enlaces para respaldar estas afirmaciones, pero hasta donde yo sé, la implementación de STL distribuida con Microsoft C++ utiliza algunas anotaciones mágicas internas no estándar para marcar vector (y otras colecciones de STL) como tener-desempeño- swap para que vector<vector<>> no copie los vectores internos, sino que los intercambie. Hasta VC9, es decir, en VC10 cambiarán a referencias rvalue. Creo que se supone que no puedes marcar tus propias clases de la misma manera que no hay una forma de compilación cruzada para hacerlo y tu código solo funcionará en la versión de compilación específica.

Editar: Tenía un rápido vistazo a la cabecera <vector> en VC9 y encontré esto:

// vector implements a performant swap 
template <class _Ty, class _Ax> 
    class _Move_operation_category<vector<_Ty, _Ax> > 
    { 
    public: 
     typedef _Swap_move_tag _Move_cat; 
    }; 

Sólo para el experimento, podría intentar especializarse esta clase para que el propietario de tipo, pero como ya he dicho, este es específico de la versión STL y se va en VC10

Answer 2

Lo que dice la norma, no sé exactamente. El valor predeterminado en stl es copiar, lo cual no es divertido si edita mucho vectores de vectores.

Sin embargo, el comportamiento que desea se implementa en Visual C++ en su aplicación TR1, disponible como una actualización para VS2008 (TR1 es una especie de preludio para el estándar C++ 0x). Compran su implementación stl de Dinkumware, como muchos otros proveedores de compiladores, por lo que puede esperar que esto aparezca en otros compiladores. Ver http://msdn.microsoft.com/en-us/library/bb982198.aspx.

Si usa GCC esto no le sirve, pero probablemente haya otros por aquí que puedan decirle.

[Editar] Leyendo después de la edición, descubrí que Microsoft afirma que la optimización swap() es su característica, no la de dinkimware. Al menos así es como leo esta entrada de blog: http://blogs.msdn.com/vcblog/archive/2008/01/08/q-a-on-our-tr1-implementation.aspx

Answer 3

std :: vector tradicionalmente copia-construye elementos en la nueva memoria al crecer, luego se destruyen los valores anteriores. Sin embargo, en el próximo C++ 0x con referencias rvalue y semántica de movimiento, std :: vector puede mover-construir elementos en la nueva memoria. Esto es mucho más eficiente. Si tiene un vector de cadenas u otro tipo de datos costosos de copiar, entonces, al moverlos, basicamente los copie a los datos retenidos y los marque como vacíos. Esto es muy barato en comparación con copiar y destruir, y resuelve eficazmente el costoso problema de reasignación de vectores para tipos de construcciones móviles. Es más o menos la optimización de intercambio que describió, integrada en el lenguaje.

Answer 4

No creo que se permita el uso del vector swap (encontrado por ADL). No está explícitamente prohibido que pueda encontrarlo, pero los requisitos del tipo de valor del vector son CopyConstructible y Assignable. Ninguno de estos tiene swap como una operación válida (incluso una opcional), o cualquier medio estándar para determinar si el intercambio está sobrecargado o no. Posiblemente podría usar std::swap (o una especialización, si existe) según corresponda, porque tiene los mismos requisitos en sus parámetros: CopyConstructible and Assignable (y especializaciones para UDT de funciones en namespace std debe implementar el comportamiento definido de la plantilla genérica) . Sin embargo, eso no ayuda con la reasignación, porque tendrías que construir algunos objetos "vacíos" para intercambiar, y el vector no puede decidir por su propia cuenta que su tipo de valor debe ser predecible, cuando el estándar no lo hace. no lo requieren

Creo que es razonable suponer que si una operación no es necesaria para su tipo T, entonces no se realizará, incluso si el compilador de alguna manera determina psíquicamente que existe. En C++, el hecho de que algo tenga las funciones correctas definidas para implementar una interfaz no significa que pretenda implementar la semántica de esa interfaz.No es hasta que lo pase en un contexto que exige la semántica que afirma que el comportamiento de las funciones es el esperado para la interfaz. La norma no exige un swap de buen comportamiento para el tipo de valor de vector, por lo que la implementación de vector no puede suponer que solo porque se define swap, es mejor que operator=.

Esa es solo mi interpretación de la intención de la especificación, sin embargo, no encuentro nada definitivo de ninguna manera.

23.2.4.3/4 da una pista. Cuando se habla de erase, dice: "el operador de asignación de T se llama el número de veces igual al número de elementos en el vector después de los elementos borrados". Por lo tanto, el vector está explícitamente prohibido usar swap para desplazarse hacia adelante al final del vector después de un borrado: debe usar operator=. Lo tomo como una fuerte pista de que la expectativa de los autores es usar operator= para todo, de lo contrario no habrían sido tan descuidados como para prohibir swap en el único caso en el que realmente se puede usar sin necesidad de un constructor predeterminado.

También veo el punto de Microsoft, descrito por usted y jdv, que para los contenedores de contenedores, se obtiene una gran ganancia del intercambio. Siempre que la "magia de plantilla" sea tal que no interfiera con los programas C++ bien formados, no hay nada de malo en una implementación que proporcione un medio para que los tipos digan vector para intercambiar.

Por ejemplo, posiblemente tengan una plantilla de rasgos de tipo con doble subrayado en el nombre. Los efectos de usar ese nombre están definidos por la implementación, por lo que todas las apuestas están desactivadas. El estándar de C++ no dice nada sobre cómo se comporta std :: vector en los programas que se especializan en esa plantilla. Una vez que haya utilizado un nombre reservado en su programa, la implementación puede definir vector para usar operator=, swap o aubergine para todos los cuidados estándar.

Answer 5

cuando tiene un vector bastante grande y desea liberarlo, puede usar la función de intercambio para cambiarlo por un vector vacío. Esta es una forma muy eficiente de liberar espacio en la memoria al usar el contenedor STL.

Answer 6

Básicamente, usted está pidiendo lo que sucede cuando se hace lo siguiente:

vector<int> v; 
v.reserve(100); 

Podemos mirar a lo libstdC++ hace en este caso como un example.

template<typename _Tp, typename _Alloc> void vector<_Tp, _Alloc>::reserve(size_type __n) { 
    if (__n > this->max_size()) 
     __throw_length_error(__N("vector::reserve")); 
    if (this->capacity() >= __n) 
     return; 

    const size_type __old_size = size(); 
    pointer __tmp = _M_allocate_and_copy(__n, 
     _GLIBCXX_MAKE_MOVE_ITERATOR(this->_M_impl._M_start), 
     _GLIBCXX_MAKE_MOVE_ITERATOR(this->_M_impl._M_finish)); 
    std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, _M_get_Tp_allocator()); 
    _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage - this->_M_impl._M_start); 
    this->_M_impl._M_start = __tmp; 
    this->_M_impl._M_finish = __tmp + __old_size; 
    this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; 
} 

La llamada importante aquí es _M_allocate_and_copy

template<typename _ForwardIterator> pointer _M_allocate_and_copy(size_type __n, _ForwardIterator __first, _ForwardIterator __last) { 
    pointer __result = this->_M_allocate(__n); 
    std::__uninitialized_copy_a(__first, __last, __result, _M_get_Tp_allocator()); 
    return __result; 
} 

La llamada importante aquí es std::__uninitialized_copy_a

template<typename _InputIterator, typename _ForwardIterator, typename _Allocator> _ForwardIterator __uninitialized_copy_a(_InputIterator __first, _InputIterator __last, _ForwardIterator __result, _Allocator& __alloc) { 
    _ForwardIterator __cur = __result; 
    for (; __first != __last; ++__first, ++__cur) 
     __alloc.construct(&*__cur, *__first); 
    return __cur; 
} 

Esto está llamando construct. Como puede ver, está usando el constructor de copia.

void construct (pointer p, const_reference val) { 
    new ((void*)p) T (val); 
} 

Por lo tanto, cuando un reallocate sucede, cada elemento en el vector tiene el constructor de copia invocado.

Answer 7

Desafortunadamente, el uso de la función de intercambio se pasó por alto cuando se habla estándar C++ 0x.

En mi opinión intercambio debería ser función básica conocida a nivel del lenguaje. Resuelve muchos racionales para agregar referencias rvalue al lenguaje.

Volviendo std :: vector de función o la asignación temporal de intercambio podría utilizar en lugar de la copia. Los contenedores podrían usarlo para optimizar la reasignación.

Alas. :(