Правильное управление векторной памятью

Question

Я создаю игру, и у меня есть вектор летающих пуль. Когда пуля закончена, я делаю bullets.erase (bullets.begin () + i); Тогда пуля исчезает. Однако это не похоже на получение стержня памяти. Если я создаю 5000 пуль, а затем создаю еще 5000, после того как они исчезнут, память останется прежней, но если я создам еще 5000, пока эти 5000 летят, это выделит новое пространство. Что мне нужно сделать, чтобы на самом деле освободить эту память?

Answer 1

Класс std::vector автоматически управляет внутренней памятью. Он будет расширяться, чтобы вмещать столько элементов, сколько вы поместите в него, но в целом он не будет уменьшаться сам по себе при удалении элементов (хотя, конечно, он освобождает память при разрушении).

У std::vector есть два соответствующих понятия «размер». Во-первых, это «зарезервированный» размер, который представляет собой объем памяти, выделенный системой для хранения векторных элементов. Второй - это «используемый» размер, который определяет, сколько элементов логически находится в векторе. Понятно, что зарезервированный размер должен быть не меньше используемого размера. Вы можете определить используемый размер с помощью метода size() (который, я уверен, вы уже знаете), а зарезервированный размер - с помощью метода capacity().

Обычно, когда используемые и зарезервированные размеры совпадают, и вы пытаетесь вставить новый элемент, вектор выделит новый внутренний буфер, в два раза превышающий предыдущий зарезервированный размер, и скопирует все существующие элементы в этот буфер. Это прозрачно для вас, за исключением того, что оно сделает недействительными любые итераторы, которые вы держите. Как я уже отмечал ранее, AFAIK, большинство реализаций STL никогда не уменьшают зарезервированный размер в ответ на удаление.

К сожалению, хотя вы можете заставить вектор увеличить его зарезервированный размер, используя метод reserve(), это не работает для уменьшения зарезервированной емкости. Насколько я могу судить, вам лучше всего сделать следующее:

std::vector<Bullet>(myVector).swap(myVector);

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

Теперь, поскольку создание этой временной копии является относительно дорогой операцией (т. Е. Она занимает намного больше процессорного времени, чем обычные операции чтения / вставки / удаления), вы не хотите делать это каждый раз, когда стираете элемент. По той же причине, поэтому вектор удваивает свой зарезервированный размер, а не увеличивает его на 1, когда вам нужно превысить существующий размер. Поэтому я бы порекомендовал, чтобы после того, как вы удалили относительно большое количество элементов и знаете, что в ближайшее время не добавите их еще больше, выполните «трюк» подкачки, чтобы уменьшить емкость.

Наконец, вы также можете рассмотреть возможность использования для этого чего-то отличного от std::vector. Стирание элементов из середины вектора, что, по-видимому, вы часто делаете, является медленной операцией по сравнению со многими другими типами структур данных (поскольку вектор должен скопировать все последующие элементы обратно в один слот, чтобы заполнить дыру) , Какая структура данных лучше всего подходит для ваших целей, зависит от того, что еще вы делаете с данными.

Answer 2

Во-первых, метод std :: vector erase не очень эффективен, он должен перемещать все элементы после удаленного. Если порядок векторных элементов (маркеров) не имеет значения, обмен удаленного маркера с последним маркером и удаление последнего маркера будут выполняться быстрее (поэтому вы получаете постоянную сложность вместо линейной сложности).

Во-вторых, в чем реальная проблема - после удаления 10000 элементов память не освобождается? Мы говорим о свободной памяти, сообщаемой операционной системой, или о свободном месте в куче? Возможно (и очень вероятно), что какой-то другой объект был выделен после положения данных вектора, поэтому невозможно просто освободить эту память для операционной системы; но его можно использовать для других вновь созданных объектов.

Answer 3

Я предлагаю вам взглянуть на эти две идиомы и выбрать ту, которая подходит вам больше всего:
Уменьшить, чтобы соответствовать
Очистить и свернуть

Answer 4

Так обычно ведет себя модель выделения памяти вектора для обеспечения амортизированной операции с постоянным временем push_back. В основном она пытается угадать, что вы можете захотеть заполнить стертую деталь новым элементом, чтобы она не освобождала память. Делая это, он может избежать постоянного распределения и освобождения. Чтобы обойти это, вы можете использовать трюк подкачки, чтобы освободить неиспользуемую векторную память. Вы должны заменить свой пустой вектор временным неназванным вектором, чтобы, когда временный вектор вышел из области видимости, он освободил память в своем деструкторе, что-то вроде: vector<int>(c).swap(c)

Answer 5

Может не избавиться от памяти.
Но в следующий раз, когда вам нужно добавить буллит, ему не нужно перераспределять больше места.
Он не будет повторно использовать память, из которой пришла стертая пуля.

Примечание:
Если вы стираете с середины контейнера относительно часто, вектор может быть неправильным контейнером. Это происходит потому, что если вы удалите элемент n, то все элементы из [n + 1, end) должны быть перемещены на один пробел в памяти.

Answer 6

Когда пуля закончена, я делаю bullets.erase (bullets.begin () + i);

Не делай этого.Если несколько кадров закончено на кадр, вы получите ужасную производительность, потому что не законченные маркеры будут копироваться снова и снова, что на самом деле не нужно.Вот что я хотел бы сделать:

#include <algorithm>
#include <functional>
#include <vector>

class Bullet
{
    // ...
public:
    bool is_finished() const;
};

int main()
{
    std::vector<Bullet> bullets;
    // ...
    bullets.erase(
        std::remove_if(
            bullets.begin(),
            bullets.end(),
            std::mem_fun_ref(&Bullet::is_finished)
        ),
        bullets.end()
    );
}

Этот подход перемещает каждую живую пулю не более одного раза.