c++ - 不确定使用什么数据结构

Question

我目前正在尝试使用结构的 vector/双端队列。结构的简单例子...

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++;

这按我想要的方式工作，但它看起来也很老套，因为我在每次删除时都在调整索引，我认为这仅仅是因为我对数据结构的了解不多。谁能给我一些建议？

注意 - 我不认为这与这篇文章被标记的内容重复，因为我不想用我已有的东西高效地做一些事情。对我来说，考虑到我每次从中获得我需要的东西时都会减少双端队列的大小，这似乎足够有效。我所希望的是一些关于找出什么是我试图用双端队列处理的最佳数据结构的建议，这些数据结构可能不会在我处理它们时被处理。

我也可能是错的，我的用法很好，但对我来说似乎不太对。

Answer 1

嗯，我一直都知道this talk会派上用场的!这里的信息是“了解你的 STL 算法”。接下来，让我向您介绍 std::stable_partition。

您可以做的一件事是只使用一个 vector ，如下所示:

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，这可能会更高效，因为它不会保留项目的相对顺序原始 vector 中的元素，但仍会将其分为两部分。

编辑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));
}