В каком контейнере STL выполнять удаление промежуточных элементов?

Мне нужно выбрать контейнер для хранения указателей на тип, который я определил (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
        }   
    }
}

c++ stl particles
person Goles    schedule 10.03.2011    source источник
comment
Для последовательного контейнера всегда начинайте с std::vector. Затем профилируйте, и если операции с контейнером вызывают проблемы, попробуйте другой контейнер. Обычно вы будете придерживаться std::vector.< /а>   -  person sbi    schedule 10.03.2011
comment
Проблема с константой времени и std::list заключается в том, что константа велика! С std::vector время переменное, но небольшое. Твой выбор! :-)   -  person Bo Persson    schedule 10.03.2011

Ответы (5)


arrow_upward
11
arrow_downward

Я не полностью следую вашему алгоритму, но 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();
}
person Fred Foo    schedule 10.03.2011
comment
Я думаю, что правильным термином является амортизированное постоянное время, но, да, начните с std::vector и изменяйте только после того, как профилирование покажет улучшения при использовании другого контейнера. Однако я сомневаюсь, что вы столкнетесь с этим часто. - person sbi; 10.03.2011
comment
Лучше было бы использовать std::swap(v[i], v.back()); v.pop_back();, потому что swap не бросает, постоянное время и дешево (для всех неидиотских реализаций swap). - person GManNickG; 10.03.2011
comment
Привет, я отредактировал свой пост. Какова стоимость изменения размера вектора на одном элементе? Конечно, это лучше, чем удаление промежуточного элемента, но все же, если я буду делать это часто, вы думаете, что производительность сильно пострадает? (Хотя мне придется профилировать) - person Goles; 10.03.2011
comment
@Mr.Gando, добавление одного элемента требует амортизированного постоянного времени. В типичной реализации перераспределение удваивает емкость вектора, поэтому оно требуется только каждый раз, когда количество элементов удваивается. - person Fred Foo; 10.03.2011
comment
Великолепно! Я искал быстрый и эффективный (постоянное время) способ удалить элемент с помощью произвольного доступа. Спасибо! - person Joel; 23.02.2012
comment
Я думаю, что ОП хотел иметь возможность нажимать на переднюю часть контейнера, а также постоянное стирание времени из середины. Я бы использовал это решение на std::deque, чтобы получить постоянный push_front. - person emsr; 23.04.2013
comment
@emsr: но если амортизированное постоянное время достаточно хорошо, то это будет работать, если итерация выполняется в обратном порядке. - person Fred Foo; 23.04.2013

arrow_upward
5
arrow_downward

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

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

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

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

person user634618    schedule 10.03.2011
comment
Я отредактировал свой пост, значение времени жизни не меняется, но оно не одинаково для всех частиц. Время жизни частицы зависит от случайного значения диапазона, например: 5,0 секунд +- диапазон (0,0, 0,5) (где диапазон дает случайное число между заданными параметрами) - person Goles; 10.03.2011
comment
да, но кажется, что вы можете определить дату истечения срока действия во время вставки, просто добавив свое (случайное) время жизни к текущему времени, а затем сохранив результат. (срок годности не меняется после инициализации до тех пор, пока частица не будет удалена из контейнера). приоритетная очередь будет следить за тем, чтобы все частицы внутри были слабо упорядочены, поэтому вам просто нужно выталкивать записи до тех пор, пока верхний срок действия не наступит в будущем. - person user634618; 10.03.2011

arrow_upward
0
arrow_downward

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

person Mark B    schedule 10.03.2011
comment
Привет, я отредактировал свой пост, было бы здорово, если бы вы подумали, что ваш ответ все еще актуален :). - person Goles; 10.03.2011

arrow_upward
0
arrow_downward

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

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

arrow_upward
0
arrow_downward

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

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

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

person Ronny Brendel    schedule 10.03.2011