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

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

Он делает выражение об амортизированной стоимости push_back и pop_back - O (1)

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

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

Ответы

Ответ 1

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

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

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

Ответ 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.modifiers]

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

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

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

Ответ 3

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

Ответ 4

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

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