不知道要使用什麼數據結構

Question

我目前正在嘗試使用向量/結構的deques。結構簡單的例子...

struct job { 
    int id; 
    int time; 
} 

我希望能夠通過結構搜索找到的時間匹配工作，從結構中取出，並繼續檢查該結構的其他ID。示例代碼...

<vector> jobs; 
<deque> started; 

for (unsigned int i = 0; i < jobs.size(); i++) 
{ 
    if (jobs.at(i).time == time) 
    { 
     started.push_back(jobs.at(i)); 
     jobs.erase(jobs.begin() + i); 
     i--; 
    } 
} 

time++; 

這工作我怎麼想它，但它也似乎很哈克因爲我調整指數，每當我刪除，我認爲這只是因爲我不是知識淵博的應與數據結構。任何人都可以給我一些建議？

注 - 我不認爲這是重複的這篇文章已被標記爲，因爲我不想用我已有的東西有效地做一些事情。對我而言，考慮到每當我從中獲得所需的東西時，我都會減小Deque的大小，這似乎足夠有效。我希望得到的是一些關於如何確定什麼是最好的數據結構的建議，這些數據結構可能不是我處理它們時要處理的東西。

我也可能是錯的，我的用法很好，但似乎對我來說。

Answer 1

嗯，我一直知道this talk會派上用場！這裏的信息是「瞭解你的STL算法」。有了這個，讓我給你介紹一下std::stable_partition。

有一兩件事你可以做的是隻使用一個單一的載體，具體如下：

using namespace std; 
vector<job> jobs; 
// fill the vector with jobs 
auto startedJobsIter = stable_partition(begin(jobs), end(jobs), 
    [=time](job const &_job) { return _job.time == time; }); 

現在，begin(jobs)和startedJobsIter之間的一切滿足條件，而一切從startedJobsIter和end(jobs)沒有。

編輯

如果你不關心項目的相對排序，那麼你可以只使用std::partition，這可能是更高性能的，因爲它不會保留元素的相對順序在原始矢量中，但仍將其分成兩部分。

編輯2

下面是較舊的C++標準的適應性：

struct job_time_predicate { 
public: 
    job_time_predicate(int time) : time_(time) { } 
    bool operator()(job const &the_job) { return the_job.time == time_; } 
private: 
    int time_; 
}; 

int main() 
{ 
    using namespace std; 
    int time = 10; 
    vector<job> jobs; 
    // fill that vector 
    vector<job>::iterator startedJobsIter = 
     stable_partition(jobs.begin(), jobs.end(), job_time_predicate(time)); 
}