std :: vector resize down

Question

Стандарт C++, по-видимому, не дает никаких пояснений относительно побочных эффектов по емкости либо resize(n), с n < size(), либо clear().

Это делает заявление о амортизированной стоимости push_back и pop_back - O (1)

Я могу представить себе реализацию, которая делает обычный вид емкости изменяется ала КСПС алгоритмов (например, двойные при увеличении, вдвое сократить время уменьшение size to < capacity()/4). (Cormen Lieserson Rivest Stein)

У кого-нибудь есть ссылка на любые ограничения по реализации?

Answer 1

Вызов resize() с меньшим размером не влияет на емкость vector. Это не освободит память.

Стандартная идиома для освобождения памяти от vector является swap() его с пустой временной vector: std::vector<T>().swap(vec);. Если вы хотите изменить размер вниз, вам нужно будет скопировать исходный вектор в новый локальный временный вектор и затем поменять полученный вектор на ваш оригинал.

Обновлено: C++ 11 добавлена ​​функция члена shrink_to_fit() для этой цели, это необязательный запрос, чтобы уменьшить capacity() к size().

Answer 2

На самом деле, стандарт делает указать, что должно произойти:

Это из vector, но тема та же для всех контейнеров (list, deque и т.д ...)

23,2 .4.2 вектор емкости [lib.vector.capacity]

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

6) Эффекты:

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

То есть: Если размер, указанный в resize меньше, чем число элементов, эти элементы будут удалены из контейнера. Что касается capacity(), это зависит от того, что делает erase().

Я не могу найти его в стандарте, но я уверен, что clear() определяется как:

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

Таким образом, эффекты clear() имеет на capacity() также связана с эффектами erase() имеет на него. В соответствии со стандартом:

23.2.4.3 векторные модификаторы [lib.vector.модификаторы]

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

4) Сложность: Деструктор Т называется число раз, равное числу элементов стертых ....

Это означает, что элементы будет разрушена, но память останется неповрежденной. erase() не влияет на мощность, поэтому resize() и clear() также не действуют.

Answer 3

Емкость не снизится. Я не уверен, что стандарт указывает это явно, но подразумевается: итераторы и ссылки на элементы вектора не должны быть аннулированы resize(n), если n < capacity().

Answer 4

Как я проверял на gcc (mingw), единственный способ освободить векторную емкость - это то, что говорит mattnewport. Сворачивание его с другим вектором вектора. Этот код делает это для gcc.

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