c++ - ¿Tiene std:: vector*have*para mover objetos al aumentar la capacidad? O bien, ¿pueden los reasignadores "reasignar"?
realloc allocator (3)
Una pregunta diferente inspiró el siguiente pensamiento:
¿Tiene std::vector<T> que mover todos los elementos cuando aumenta su capacidad?
Por lo que yo entiendo, el comportamiento estándar es que el asignador subyacente solicite un trozo entero del nuevo tamaño, luego mueva todos los elementos viejos, luego destruya los elementos viejos y luego desasigne la memoria anterior.
Este comportamiento parece ser la única solución correcta posible dada la interfaz de asignador estándar. Pero me preguntaba, ¿tendría sentido modificar el asignador para ofrecer una función de reallocate(std::size_t) que devolvería un pair<pointer, bool> y podría realloc() al realloc() subyacente realloc() ? La ventaja de esto sería que, en el caso de que el sistema operativo realmente pueda extender la memoria asignada, entonces no tendría que pasar nada en absoluto. El booleano indica si la memoria se ha movido.
( std::realloc() quizás no sea la mejor opción, porque no necesitamos copiar datos si no podemos extenderlos. De hecho, preferiríamos algo como extend_or_malloc_new() . Edit: is_pod a is_pod -trait- la especialización basada nos permitiría usar el realloc real, incluida su copia bit a bit. Simplemente no en general.)
Parece una oportunidad perdida. En el peor de los casos, siempre podría implementar reallocate(size_t n) como return make_pair(allocate(n), true); , entonces no habría ninguna penalización
¿Hay algún problema que haga que esta característica sea inapropiada o indeseable para C ++?
Quizás el único contenedor que podría aprovechar esto es std::vector , pero de nuevo es un contenedor bastante útil.
Actualización: un pequeño ejemplo para aclarar. Cambio de resize() actual resize() :
pointer p = alloc.allocate(new_size);
for (size_t i = 0; i != old_size; ++i)
{
alloc.construct(p + i, T(std::move(buf[i])))
alloc.destroy(buf[i]);
}
for (size_t i = old_size; i < new_size; ++i)
{
alloc.construct(p + i, T());
}
alloc.deallocate(buf);
buf = p;
Nueva implementación:
pair<pointer, bool> pp = alloc.reallocate(buf, new_size);
if (pp.second) { /* as before */ }
else { /* only construct new elements */ }
Cuando std::vector<T> queda sin capacidad, tiene que asignar un nuevo bloque. Usted ha cubierto correctamente los motivos.
IMO tendría sentido aumentar la interfaz del asignador. Dos de nosotros lo intentamos para C ++ 11 y no pudimos obtener soporte para él: [1] [2]
Me convencí de que para que esto funcione, se necesitaría una API adicional de C-level. Fallé en obtener apoyo para eso también: [3]
En la mayoría de los casos, realloc no ampliará la memoria, sino que asignará un bloque separado y moverá los contenidos. Eso fue considerado al definir C ++ en primer lugar, y se decidió que la interfaz actual es más simple y no menos eficiente en el caso común.
En la vida real, en realidad hay pocos casos en los que realloc pueda crecer . En cualquier implementación donde malloc tiene diferentes tamaños de grupo, es probable que el nuevo tamaño (recuerde que los tamaños de vector deben crecer geométricamente) caiga en un grupo diferente. Incluso en el caso de grandes fragmentos que no están asignados desde ningún grupo de memoria, solo podrá crecer si las direcciones virtuales de mayor tamaño son gratuitas.
Tenga en cuenta que aunque realloc veces puede hacer crecer la memoria sin moverse , pero para cuando realloc ya podría haberse movido (mover en modo bit) la memoria, y ese movimiento binario causará un comportamiento indefinido para todos los tipos que no sean POD. No conozco ninguna implementación de asignador (POSIX, * NIX, Windows) en la que pueda preguntar al sistema si podrá crecer , pero fallará si requiere mudarse .
Sí, tienes razón en que la interfaz del asignador estándar no proporciona optimizaciones para los tipos de memcpy''able.
Ha sido posible determinar si un tipo puede ser memcpy''d utilizando la biblioteca de rasgos de tipo boost (no estoy seguro si lo proporcionan de la caja o uno tendría que construir un discriminador de tipo compuesto basado en los impulsores).
De todos modos, para aprovechar realloc() uno probablemente crearía un nuevo tipo de contenedor que puede aprovechar explícitamente esta optimización. Con la interfaz del asignador estándar actual no parece posible.