Cuando se asignan vectores, ¿usan memoria en el montón o en la pila?

151

¿Son ciertas todas las siguientes afirmaciones?

vector<Type> vect; //allocates vect on stack and each of the Type (using std::allocator) also will be on the stack

vector<Type> *vect = new vector<Type>; //allocates vect on heap and each of the Type will be allocated on stack

vector<Type*> vect; //vect will be on stack and Type* will be on heap. 

¿Cómo se asigna internamente la memoria Typeen un vectorcontenedor STL o en otro?

Phelodas
fuente
1
Posible duplicado de miembros
underscore_d

Respuestas:

222
vector<Type> vect;

asignará vector, es decir, la información del encabezado, en la pila, pero los elementos en la tienda gratuita ("montón").

vector<Type> *vect = new vector<Type>;

asigna todo en la tienda gratuita.

vector<Type*> vect;

asignará el vectoren la pila y un montón de punteros en la tienda gratuita, pero donde este punto está determinado por cómo los usa (podría señalar el elemento 0 a la tienda libre y el elemento 1 a la pila, por ejemplo).

Fred Foo
fuente
3
Pero tengo un escenario, donde obtengo una falla de segmentación cuando Type está creciendo en la segunda declaración. Supuse que se debía a que Type se estaba asignando en la pila.
Phelodas
44
@Phelodas: sin ver su código, esto es imposible de evaluar. Por favor abra una nueva pregunta.
Fred Foo
2
Acerca de, vector<Type> vect;dado que los elementos están en el montón y la información del encabezado está en la pila, cuando la información del encabezado se elimina de la memoria, como la función de retorno, ¿qué pasará con las memorias de los elementos? ¿Se reclaman con la información del encabezado o no? Si no lo son, ¿esto causará pérdida de memoria?
flyrain
3
@flyrain: los vectores se limpian después de sí mismos. Lea sobre RAII .
Fred Foo
1
@flyrain: eso debería funcionar. Por favor, publique una nueva pregunta con más detalles. Si publica el enlace aquí, podría echarle un vistazo.
Fred Foo
25
vector<Type> vect; //allocates vect on stack and each of the Type (using std::allocator) also will be on the stack

No, vectestará en la pila, pero la matriz que usa internamente para almacenar los elementos estará en el montón. Los artículos residirán en esa matriz.

vector<Type> *vect = new vector<Type>; //allocates vect on heap and each of the Type will be allocated on stack

No. Igual que el anterior, excepto que la vectorclase también estará en el montón.

vector<Type*> vect; //vect will be on stack and Type* will be on heap. 

vectestará en la pila, sus elementos (punteros a Type) estarán en el montón, y no se puede saber dónde estarán los Types a los que apuntan los punteros. Podría estar en la pila, podría estar en el montón, podría estar en los datos globales, podría estar en ninguna parte (es decir, NULLpunteros).

Por cierto, la implementación podría almacenar algunos vectores (típicamente de pequeño tamaño) en la pila por completo. No es que yo sepa de tal implementación, pero puede.

jpalecek
fuente
23

Suponiendo una implementación que realmente tiene una pila y un montón (C ++ estándar no requiere tener tales cosas), la única declaración verdadera es la última.

vector<Type> vect;
//allocates vect on stack and each of the Type (using std::allocator) also will be on the stack

Esto es cierto, excepto por la última parte ( Typeno estará en la pila). Imagina:

  void foo(vector<Type>& vec) {
     // Can't be on stack - how would the stack "expand"
     // to make the extra space required between main and foo?
     vec.push_back(Type());
  }

  int main() {
    vector<Type> bar;
    foo(bar);
  }

Igualmente:

 vector<Type> *vect = new vector<Type>; //allocates vect on heap and each of the Type will be allocated on stack

Verdadero, excepto la última parte, con un ejemplo de contador similar:

  void foo(vector<Type> *vec) {
     // Can't be on stack - how would the stack "expand"
     // to make the extra space required between main and foo?
     vec->push_back(Type());
  }

  int main() {
    vector<Type> *bar = new vector<Type>;
    foo(bar);
  }

Por:

vector<Type*> vect; //vect will be on stack and Type* will be on heap. 

Esto es cierto, pero tenga en cuenta aquí que los Type*punteros estarán en el montón, pero las Typeinstancias que señalan no necesitan ser:

  int main() {
    vector<Type*> bar;
    Type foo;
    bar.push_back(&foo);
  }
Flexo
fuente
¿en qué tipo de contexto no tendrías una pila? Entiendo que estás diciendo que el estándar no lo requiere, pero prácticamente hablando, ¿cuándo estarías sin una pila?
Nerdtron
3
@Nerdtron - IIRC en algunos microcontroladores pequeños tiene una pila de llamadas que puede almacenar nada más que la PC (contador de programa) en el punto de la última llamada, lista para un RET. Por lo tanto, su compilador podría elegir colocar el "almacenamiento automático" (para funciones no recursivas) en una ubicación fija con poca / ninguna relación con el flujo de ejecución. Podría aplanar con bastante sensatez todo el programa. Incluso para el caso recursivo, podría tener una política de "pila por función" o una pila separada para variables automáticas y direcciones de retorno, lo que hace que la frase "la pila" sea algo sin sentido.
Flexo
Puede utilizar la asignación basada en el montón para todo y tener una "pila de limpieza" que gestiona el almacenamiento automático (y posiblemente deletetambién).
Flexo
3

Solo esta afirmación es verdadera:

vector <Type*> vect; //vect will be on stack and Type* will be on heap.

Type* los punteros se asignan en el montón, porque la cantidad de punteros puede cambiar dinámicamente.

vect en este caso se asigna en la pila, porque lo definiste como una variable de pila local.

Alexei Khlebnikov
fuente
2
Tipo * no indica asignación de montón, simplemente un puntero a un objeto Tipo. Dicho esto, el vector almacena el puntero en el montón. int a = 5; int * ptr_to_a = & a; vector <int *> vec; vec.push_back (ptr_to_a); (ver la respuesta de jpalecek)
Matthew Russell
1

el vector tiene un interno allocatorque se encarga de asignar / desasignar memorias heappara vector element. Entonces, no importa cómo cree un vector, elementsiempre se asigna en el heap. En cuanto a los metadatos del vector, depende de la forma en que lo cree.

Bingo
fuente