Какой контейнер STL для удаления элементов между ними?

Question

Мне нужно выбрать контейнер для хранения указателей на определенный мной тип (Particle).Я использую предварительно выделенную частицу Object Pool (которая содержит объекты, предварительно выделенные в std :: vector).

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

Как вы можете видеть, пока я перебираю свой Ссылочный Контейнер Частиц (нужно выбрать один), чтобы обновить его, мне придется проверитькакие частицы истекли (lifetime <= 0.0) и вернули их обратно в пул частиц, частицы с истекшим сроком годности могут находиться в любом месте контейнера.

Я думал об использовании std::list, вот почему:

Список (AFAIK) обеспечивает постоянное добавление времени в начале и постоянное удаление времени в любой точке (при условии, что вы выполняли итерацию до этого момента).

Любые предложения или улучшения в моей системе вДля лучшего размещения вашего контейнера приветствуются предложения.

РЕДАКТИРОВАТЬ :

Чтобы объяснить себя немного лучше:

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

Алгоритм псевдокода:

    // Assume typedef std::container_type<Particle *> ParticleContainer

void update(float delta)
{   
    ParticleContainer::iterator particle = m_particles.begin();   

    for(; particle != m_particles.end(); ++particle)
    {
        updateParticle(*particle, delta);         //Update the particle

        if ( (*particle)->lifeTime <= 0.0 )
        {
            ParticlePool.markAsFree(*particle);   //Mark Particle as free in the object Pool
            m_particles.remove(*particle);        //Remove the Particle from my own ParticleContainer
        }   
    }
}

Answer 1

Я не совсем следую вашему алгоритму, но std::vector требуется для обеспечения амортизированного постоянного времени push_back. Он также может иметь лучшую локальность ссылки при итерации.

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

template <typename T>
void remove(std::vector<T> &v, size_t i)
{
    std::swap(v[i], v.back());
    v.pop_back();
}

Answer 2

Почему бы не использовать приоритетную очередь ? Таким образом, вам не придется перебирать все активные частицы.

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

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

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

Answer 3

Я не совсем понимаю, но;

• набор указателей частиц может оказаться достойным выполнения этой задачи.журнал вставки (n) журнал удаления (n)

• , если вы в основном выполняете итерацию, локальность может оказать большое влияние (я не уверен, насколько эффективны списки stl в этом отношении, но stlвекторы, безусловно, лучше в этом), и это может стоить пометки вместо удаления

Answer 4

Похоже, std::list это путь.Это предполагает, что вы определенно хотите перебрать список, удаляя объекты из середины.Обратите внимание, что большинство других контейнеров делают недействительными итераторы при удалении из середины;std::list нет.Дополнительные предложения:

• Если вам небезразлично пространство (много), вы можете попробовать Boost.Intrusive
• Если вы хотите использовать нестандартный контейнер, попробуйте slist (односвязный список; gcc поддерживает это) попытаться - это сэкономит место, сэкономит некоторые (небольшие) затраты времени выполнения при удалении элементов, так как вы уменьшаете количество указателей, которые должны быть обновлены.Это сравнивается с std::list, который вдвойне связан.

Answer 5

Предполагая, что вам не нужна прямая индексация (operator[]) и вы просто перебираете контейнеры, list звучит просто отлично.Вы даже можете использовать splice для перемещения узлов списка в постоянное время без выделения или освобождения памяти.