Re: [問題] 請教一下有關刪除deque的問題
※ 引述《jokingfish (ㄚ魚!!)》之銘言:
: 開發平台(Platform): (Ex: VC++, GCC, Linux, ...)
: VC++
: 問題(Question):
: 目前的程式實作上有大量的三角網格,會即時增加/刪除
: 三角網格個人是用deque去存的
: 增加是用.push_back() 還OK
: 刪除若用.erase() 會很慢.....超級慢
: 所以目前用的是一個變通的方法,還算堪用.....
: 每個三角網格多用一個flag 紀錄該網格有沒有被刪掉
: 一定時間後,再跑迴圈COPY還在的三角網格至另一串deque,把被刪掉的網格給濾掉
: 但是覺得這辦法很....蠢......><|||
: 對資料結構運算速度這塊沒這麼熟,想請教是否有能更迅速 方便的方法
: 請不吝賜教 謝謝
deque<Node> queue;
/**
放入N個Node
**/
int right = queue.size();
while(queue不等於空) {
while(right-- > 0) {
Node oldNode = queue[0];
queue.pop_front();
// 作了一些運算產生新Node 或 原本的舊 Node 要保留 在這邊做
// 以下只是舉例
if(oldNode不刪) {
queue.push_back(oldNode);
}
}
right = queue.size();
}
這是BFS使用C++ STL deque 的雛形。
而另一種比較慢的方法...
deque<Node> thisQueue;
while(thisQueue 不等於空) {
deque<Node> nextQueue;
deque<Node>::iterator it = thisQueue.begin();
while(it != thisQueue.end()) {
nextQueue.push_back(*it);
++it;
}
thisQueue.swap(nextQueue);
}
看了這些,相信你會有一些靈感。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.32.177.97
※ 編輯: bleed1979 來自: 114.32.177.97 (08/06 20:49)
討論串 (同標題文章)
本文引述了以下文章的的內容:
完整討論串 (本文為第 2 之 2 篇):