CODEWITHSUNDEEP
c++data-structures
cpd1
cpd1

Reputation: 789

Not sure what data structure to use

I'm currently trying to work with vectors / deques of structures. Simple example of the structure...

struct job {
    int id;
    int time;
}

I want to be able to search through the structure to find the job that matches the time, remove it from the structure and continue to check for other ids in that structure. Sample code...

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

This works how I want it to but it also seems very hacky since I'm adjusting the index whenever I delete and I think it's simply because I'm not as knowledgeable as should be with data structures. Anyone able to give me some advice?

NOTE - I don't think this is a duplicate to what this post has been tagged to as I'm not looking to do something efficiently with what I already have. To me, it seems efficient enough considering I'm reducing the size of the deque each time I get what I need from it. What I was hoping for, is some advice on figuring out what is the best data structure for what I'm attempting to do with deques, which are likely not meant to be handled as I'm handling them.

I could also be wrong and my usage is fine but just seems off to me to.

Upvotes: 0

Views: 108

Answers (1)

Nasser Al-Shawwa
Nasser Al-Shawwa

Reputation: 3673

Well, I always knew that this talk would come in handy! The message here is "know your STL algorithms". With that, let me introduce you to std::stable_partition.

One thing you can do is use just one single vector, as follows:

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

Now, everything between begin(jobs) and startedJobsIter satisfy the condition, while everything from startedJobsIter and end(jobs) does not.

Edit

If you don't care about the relative ordering of the items, then you could just use std::partition, which could be even more performant, because it would not preserve the relative ordering of the elements in the original vector, but will still divide it into the two parts.

Edit 2

Here's an adaptation for older C++ standards:

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

Upvotes: 2

Related Questions