std :: vector изменить размер вниз - PullRequest
Новая
       36

std :: vector изменить размер вниз

29 голосов
/ 21 июля 2009

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

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

Я могу представить реализацию, которая выполняет обычные изменения емкости аля CLRS алгоритмы (например, удваивается при увеличении, уменьшается вдвое при уменьшении size to < capacity()/4). (Кормен Лизерсон Ривест Штейн)

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

Ответы [ 4 ]

42 голосов
/ 21 июля 2009

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

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

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

24 голосов
/ 21 июля 2009

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

Это из 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.modifiers] 

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

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

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

6 голосов
/ 21 июля 2009

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

0 голосов
/ 20 октября 2011

Поскольку я проверил 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()
}
...