¿Es mejor llamar a vector :: reserve() antes de llamar a vector :: assign()?

Question

entiendo que es una buena práctica utilizar "reserva" para evitar reasignaciones innecesarios (Tema 14 del STL eficaz):

std::vector<int> v1; 
v1.reserve(1000); 

for (int i = 0; i < 1000; i++) 
    v1.push_back(i); 

¿Se aplica la misma regla cuando se llama a asignar?

std::vector<int> v2; 
//v2.reserve(v1.size()); // Better to do this? 
v2.assign(v1.begin(), v1.end()); 

Answer 1

En caso cuando v1 es std::vector usted realmente no lo necesita, ya que el compilador/STL sabe cuántos elementos van a estar allí en v2 (y se reserve la cantidad necesaria en sí antes de copiar los datos reales)

Para el caso genérico, sin embargo, puede tener sentido para reserve la cantidad necesaria de antemano, si el recipiente de entrada (v1) no sabe cuántos elementos están ahí, y tiene el número en cuestión.

Answer 2

si llamar reserve o no depende de:

• el tipo de iterador: para la entrada de iteradores la aplicación no puede adivinar el tamaño
• la calidad de la biblioteca: es posible que no se especializan para iteradores "mejores"
• si el rendimiento vale la disminución de la capacidad de mantenimiento

tomemos los 3 puntos en orden.

1) Iterador Tipo

El método assign toma dos iteradores que deben al menos ser conforme al modelo InputIterator. El problema es que este modelo representa fuentes puras (como los bytes que provienen de la red): puede consumir algo dos veces. Como resultado, dado dos InputIterator no es posible calcular la distancia entre ellos sin extraer también los datos (a menos que no desee los datos en absoluto, pero eso no es de lo que se trata asignar), por lo que no puede "reservar" primero .

Esto se ilustra por el hecho de que std::distance requiere al menos .

2) La calidad de la ejecución

No creo que el estándar de hecho obliga a los iteradores "mejores" (que al menos modelo ForwardIterator) que la aplicación de assign caminar por la gama dos veces. En un cálculo limitado por el ancho de banda de la memoria (imagínese leyendo esa información en una cinta, con un tiempo de rebobinado muy lento), esto realmente sería más costoso.

Sin embargo, muchas implementaciones (como libC++, véase más adelante) se especializarán assign por lo que, en presencia de ForwardIterator que llama std::distance primero en reservar la cantidad correcta de memoria si es necesario.

Nota: lo mismo se aplica a las inserciones en masa por cierto.

3) carga de mantenimiento

Quiero señalar que a pesar de la posible ganancia, usted es (tal vez sin saberlo) la duplicación de información aquí.

size_t size = std::distance(begin, end); 

if (begin != end) ++begin; // new line 

v.reserve(size); 
v.assign(begin, end); 

¿Ve cómo el aspecto de la nueva línea de repente hace que el código sea ligeramente incorrecto? No es que no funcione, pero la supuesta optimización ya no es tan correcta: ¡reserva demasiado ahora!

Personalmente, confío en que la implementación de mi biblioteca estándar hará lo correcto. Los chicos que los escriben tienen mucha más experiencia que yo.

Y si realmente es un cuello de botella identificado en su aplicación, siempre puede intentarlo. Simplemente escriba un método reserve_and_assign para que sea obvio lo que hace y mida si es mejor.

---

Para referencia, aquí es la implementación de libC++, taken here:

template <class _Tp, class _Allocator> 
template <class _InputIterator> 
typename enable_if 
< 
    __is_input_iterator <_InputIterator>::value && 
    !__is_forward_iterator<_InputIterator>::value, 
    void 
>::type 
vector<_Tp, _Allocator>::assign(_InputIterator __first, _InputIterator __last) 
{ 
    clear(); 
    for (; __first != __last; ++__first) 
     push_back(*__first); 
} 

template <class _Tp, class _Allocator> 
template <class _ForwardIterator> 
typename enable_if 
< 
    __is_forward_iterator<_ForwardIterator>::value, 
    void 
>::type 
vector<_Tp, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last) 
{ 
    typename iterator_traits<_ForwardIterator>::difference_type __new_size = _VSTD::distance(__first, __last); 
    if (static_cast<size_type>(__new_size) <= capacity()) 
    { 
     _ForwardIterator __mid = __last; 
     bool __growing = false; 
     if (static_cast<size_type>(__new_size) > size()) 
     { 
      __growing = true; 
      __mid = __first; 
      _VSTD::advance(__mid, size()); 
     } 
     pointer __m = _VSTD::copy(__first, __mid, this->__begin_); 
     if (__growing) 
      __construct_at_end(__mid, __last); 
     else 
      this->__destruct_at_end(__m); 
    } 
    else 
    { 
     deallocate(); 
     allocate(__recommend(static_cast<size_type>(__new_size))); 
     __construct_at_end(__first, __last); 
    } 
}