std :: vector redimensionar hacia abajo

Question

El estándar C++ parece no hacer ninguna declaración con respecto a los efectos secundarios sobre la capacidad resize(n), con n < size(), o clear().

Se hace una declaración acerca de coste amortizado de push_back y pop_back - O (1)

puedo imaginar una implementación que hace el tipo habitual de la capacidad cambia ala clrs algoritmos (por ejemplo, el doble cuando se amplía, reducir a la mitad cuando decreciente size to < capacity()/4). (Cormen Lieserson Rivest Stein)

¿Alguien tiene alguna referencia para las restricciones de implementación?

Answer 1

Llamar a resize() con un tamaño más pequeño no tiene ningún efecto sobre la capacidad de vector. No liberará la memoria.

La expresión estándar para liberar memoria de un vector es a swap() con un vector vacío temporal std::vector<T>().swap(vec);. Si quieres redimensionar hacia abajo, necesitarás copiar de tu vector original a un nuevo vector temporal local y luego cambiar el vector resultante con tu original.

Actualizado: C++ 11 añade una función miembro shrink_to_fit() para este propósito, que es una solicitud no vinculante para reducir capacity()-size().

Answer 2

En realidad, la norma especifique lo que debe suceder:

Esto es de vector, pero el tema es el mismo para todos los contenedores (list, deque, etc ...)

23,2 .4.2 capacidad vector [lib.vector.capacity]

void resize(size_type sz, T c = T());

6) Efectos:

if (sz > size()) 
    insert(end(), sz-size(), c); 
else if (sz < size()) 
    erase(begin()+sz, end()); 
else 
    ; //do nothing 

Es decir: si el tamaño especificado a resize es menor que el número de elementos, estos elementos serán borrados del contenedor. Con respecto a capacity(), esto depende de lo que erase() le haga.

no puede localizarlo en la norma, pero estoy bastante seguro de clear() se define como:

void clear() 
{ 
    erase(begin(), end()); 
} 

Por lo tanto, los efectos clear() tiene en capacity() también está relacionada con los efectos erase() tiene en él. De acuerdo con el estándar:

23.2.4.3 modificadores vectoriales [lib.vector.modificadores]

iterator erase(iterator position); 
iterator erase(iterator first, iterator last); 

4) Complejidad: El destructor de T se denomina el número de veces igual al número de los elementos borrados ....

Esto significa que los elementos será destruido, pero la memoria permanecerá intacta. erase() no tiene ningún efecto sobre la capacidad, por lo tanto, resize() y clear() tampoco tienen ningún efecto.

Answer 3

La capacidad nunca disminuirá. No estoy seguro si el estándar lo dice explícitamente, pero está implícito: los iteradores y las referencias a los elementos del vector no deben ser invalidados por resize(n) si n < capacity().

Answer 4

Como he comprobado para gcc (mingw), la única forma de obtener capacidad de vector libre es lo que dice mattnewport. Alternarlo con otro vector teporario. Este código lo hace para gcc.

template<typename C> void shrinkContainer(C &container) { 
    if (container.size() != container.capacity()) { 
     C tmp = container; 
     swap(container, tmp); 
    } 
    //container.size() == container.capacity() 
}