¿Std:: vector * tiene * que mover objetos al aumentar su capacidad? O, ¿pueden los asignadores "reasignar"?


Una pregunta diferente inspiró el siguiente pensamiento:{[17]]}

Hace std::vector<T> tiene para mover todos los elementos cuando aumenta su capacidad?

Por lo que entiendo, el comportamiento estándar es que el asignador subyacente solicite un trozo completo del nuevo tamaño, luego mueva todos los elementos antiguos, luego destruya los elementos antiguos y luego desasigne la memoria antigua.

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 reallocate(std::size_t) que devolvería un pair<pointer, bool> y podría mapearse al realloc() subyacente? La ventaja de esto sería que en el caso de que el sistema operativo puede realmente solo extender la memoria asignada, entonces no tendría que suceder ningún movimiento en absoluto. El booleano indicaría si la memoria se ha movido.

(std::realloc() tal vez no sea la mejor opción, porque no necesitamos copiar datos si no se puede extender. Así que, de hecho, preferiríamos algo como extend_or_malloc_new(). Editar: Quizás una especialización basada en rasgos is_pod nos permitiría usar el realloc real, incluyendo su copia bit a bit. Pero 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);, por lo que no habría ninguna penalización.

¿Hay algún problema que haga que esta característica sea inapropiada o indeseable para C++?

Tal vez el único contenedor que podría tomar ventaja de esto es std::vector, pero de nuevo que es un contenedor bastante útil.


Actualización: Un pequeño ejemplo para aclarar. Corriente 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 aplicación:

pair<pointer, bool> pp = alloc.reallocate(buf, new_size);

if (pp.second) { /* as before */ }
else           { /* only construct new elements */ }
Author: Community, 2011-11-04

3 answers

Cuando std::vector<T> se queda sin capacidad, tiene para asignar un nuevo bloque. Usted ha cubierto correctamente las razones.

IMO it 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 hacer que esto funcione, se necesitaría una API de nivel C adicional. Fallé en ganar apoyo para eso también: [3]

 39
Author: Howard Hinnant,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-06-24 21:38:49

En la mayoría de los casos, realloc no extenderá la memoria, sino que asignará un bloque separado y moverá el contenido. 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, hay realmente pocos casos donde realloces capaz de crecer. En cualquier implementación donde malloc tiene diferentes tamaños de grupo, es probable que el nuevo tamaño (recuerde que vector los tamaños deben crecer geométricamente) caerá en una piscina diferente. Incluso en el caso de trozos grandes que no se asignan de ningún grupo de memoria, solo podrá crecer si las direcciones virtuales de mayor tamaño están libres.

Tenga en cuenta que mientras que realloca veces puede hacer crecerla memoria sin mover, pero cuando reallocse complete, es posible que ya haya movido (mover en sentido bit) la memoria, y que el movimiento binario mover causará un comportamiento indefinido para todos los tipos que no sean POD. Me no conozco ninguna implementación de asignador (POSIX, *NIX, Windows) donde se pueda preguntar al sistema si será capaz de crecer, pero eso fallaría si requiere mover.

 9
Author: David Rodríguez - dribeas,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-11-04 00:06:27

Sí, tienes razón en que la interfaz de asignación estándar no proporciona optimizaciones para los tipos memcpy'abable.

Ha sido posible determinar si un tipo puede ser memcpy'd usando boost type traits library (no estoy seguro de si lo proporcionan fuera de la caja o uno tendría que construir un discriminador de tipo compuesto basado en los boost).

De todos modos, para aprovechar realloc() uno probablemente crearía un nuevo tipo de contenedor que pueda aprovechar explícitamente esto optimización. Con la interfaz de asignador estándar actual no parece ser posible.

 0
Author: Maxim Egorushkin,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-11-03 23:42:09