什麼是STL容器來執行元素之間的移除？

我需要選擇一個容器來容納指向我定義的類型的指針（Particle）。我正在使用預先分配的粒子Object Pool（其中包含預先分配在std :: vector上的對象）。什麼是STL容器來執行元素之間的移除？

我的粒子發射器在粒子池需要發射時要求粒子池（爲了避免遊戲中的粒子分配）。當一個粒子到期時，它返回到粒子對象池。你可以看到，當我迭代我的粒子參考容器（需要選擇一個）來更新它時，我將不得不檢查哪些粒子已經過期（lifetime <= 0.0）並將它們返回給粒子池，過期的顆粒可能在容器中的任何位置。

我一直在思考如何使用std::list，這裏的原因：

名單（據我所知）提供了在開始一定時間的插入和恆定時間去除在任何時候（假設你已經迭代到這一點）。

歡迎任何對我的系統的建議或改進，以便更好地適應您的容器建議。

EDIT：

爲了解釋自己好一點：

顆粒在發射極的壽命時間是不完全相同，這取決於一個範圍，例如，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 
     } 
    } 
}

來源

2011-03-10 Goles

對於順序容器，總是從'std :: vector'開始。然後配置文件，如果容器操作是一個問題，請嘗試另一個容器。 [通常你會發現自己堅持'std :: vector'。]（http://stackoverflow.com/questions/5056973/when-do-you-prefer-using-stdlistt-instead-of-stdvectort/5057001#5057001 ） – sbi 2011-03-10 19:34:05

「恆定時間」和std :: list的問題是常數很大！對於std :: vector，時間是可變的，但很小。你的選擇！ :-) – 2011-03-10 19:53:43

我並不完全按照你的算法，但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(); 
}

來源

2011-03-10 19:25:29

我認爲正確的術語是_amortized常量time_，但是，是的，從'std :: vector'開始，並且只有在使用另一個容器時分析後纔會有所改進。 [但是，我懷疑你會經常發現。]（http://stackoverflow.com/questions/5056973/when-do-you-prefer-using-stdlistt-instead-of-stdvectort/5057001#5057001） – sbi 2011-03-10 19:35:49

更好的會是使用'std :: swap（v [i]，v.back（））; v.pop_back（）;'，因爲'swap'是非拋出的，常量時間和便宜的（對於'swap'的所有非白癡實現）。 – GManNickG 2011-03-10 20:12:33

嘿，我編輯了我的文章。在一個元素上調整矢量大小的成本是多少？當然，這比刪除其中的元素要好，但如果我經常這樣做，那麼你認爲性能會受到太多影響嗎？（我將不得不介紹） – Goles 2011-03-10 20:15:57

假設你不需要直接索引（operator[]）和你只是正常遍歷容器，list聽起來就好了。您甚至可以使用splice在不進行內存分配或取消分配的情況下以恆定時間移動列表節點。

來源

2011-03-10 19:24:47

嘿，在那裏，我編輯了我的帖子，如果你認爲你的回覆仍然適用，那將會很棒:)。 – Goles 2011-03-10 20:17:03

聽起來就像std::list是要走的路。這是假設你肯定想在從中間移除對象的同時迭代列表。請注意，當您從中間移除時，大多數其他容器會使迭代器失效; std::list沒有。其它建議：

如果你關心空間（很多），你可以嘗試Boost.Intrusive
如果你願意使用非標準集裝箱，給slist（單鏈表，GCC支持）一試 - 它將節省空間，在刪除元素時節省一些（小）運行時成本，因爲您正在減少必須更新的指針數量。這與雙重鏈接的std::list相比較。

來源

2011-03-10 19:27:18 phooji

爲什麼不使用priority queue？這樣你就不必遍歷所有活動的粒子。

編輯：第二個想法：我不太確定這實際上可以工作，這取決於您的算法（我承認並沒有完全理解）。如果您在更改生命週期值在容器中，隊列可能根本不起作用。但是，如果你不改變這個值（例如你設置了插入它們時粒子過期的時間，然後只檢查第一個入口與當前時間），我仍然認爲這是你最好的選擇。（請注意，優先隊列只是默認內部使用std::vector的適配器。）

edit2：關於您的編輯。我建議不要每個粒子都存儲一個「壽命」值（它不斷減小直到不再是正值），而是存儲一個時間戳，表示粒子何時應該被移除。初始化粒子時，只需計算粒子何時到期（通過將當前時間添加到您的隨機「生命週期」）。這個值在粒子的生命週期中不會改變。在確定是否刪除粒子時，只需檢查當前時間是否大於到期時間戳。

來源

2011-03-10 19:29:15 user634618

+1：也是一個好主意 – phooji 2011-03-10 19:31:07

我編輯了我的帖子，生命週期值不會改變，但對於所有的粒子它不一樣。粒子壽命取決於隨機的「範圍」值，例如：5.0秒+ - 範圍（0.0,0.5）（其中範圍給出了給定參數之間的隨機數） – Goles 2011-03-10 20:14:11

是的，但看起來您可以確定「過期日期「，只需將您的（隨機）生命週期添加到當前時間，然後存儲結果。（到期日期在初始化之後不會改變，直到粒子從容器中移出）。優先級隊列將確保內部的所有粒子都是弱有序的，所以您只需彈出條目，直到最後的「到期日期」爲止。 – user634618 2011-03-10 20:25:12

我完全不理解，但;

一組粒子指針可以證明它也是值得的。插入日誌（n）刪除日誌（n）
如果你大多數迭代本地化可能會有很大的影響（我不知道stl列表在這方面效率如何，但stl向量肯定是更好的），它可能是值得標記而不是刪除

來源

2011-03-10 19:32:27

什麼是STL容器來執行元素之間的移除？

回答

相關問題