Sorting a Queue of Structs

Question

I currently have a queue that holds a user specified number of structs called Process. Process is made up of a pid, burst, and arrival. I would like to sort the queue by arrival, but I don't have the faintest idea of where to begin. Here is some pseudocode to help illustrate what I'm trying to say:

struct Process{
    int pid;
    int burst;
    int arrival;
};

void function(int numProcesses){
    queue<Process> readyQueue;

    // The following loop is a shortened version of my code
    for(int i=0; i<numProcesses;i++){
        readyQueue.push(aProcess);
    }

    // This is where I need help!
    // sort(readyQueue);
}

I'd be appreciative of anyone who could point me in right direction on how to do this, or if it is even possible. Thanks!

Jerry Coffin · Accepted Answer · 2012-11-08 00:40:47Z

3

Mostly you need to define operator< for your class:

struct Process{
    int pid;
    int burst;
    int arrival;

    bool operator<(Process const &other) { return arrival < other.arrival; }
};

Once you've done that, std::sort will work fine:

std::sort(std::begin(readyQueue), std::end(readyQueue));

answered Nov 8, 2012 at 0:40

Jerry Coffin

494k83 gold badges656 silver badges1.2k bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Rick_Sch Over a year ago

This is exactly what I've been looking for! I'm very new to anything other than standard arrays. Could you possibly explain how I would call sort? Please and thank you VERY much.

Jerry Coffin Over a year ago

@Rick_Sch: I've included a sample call to std::sort. Minor point: depending on the age of compiler you're using, you may need to use readyQueue.begin() instead of std::begin(readyQueue) (and likewise for end).

Rick_Sch Over a year ago

One last thing (I hope): I get this error when I try to do that readyQueue.begin() method: error: ‘class std::queue<Process, std::deque<Process, std::allocator<Process> > >’ has no member named ‘begin’ BUT I also get this error if I try the begin(readyQueue) method: ‘begin’ was not declared in this scope

user515430 Over a year ago

You cannot traverse a queue. You can push and pop, but no iteration through a queue.

Jerry Coffin Over a year ago

Sorry -- hadn't noticed that you were using an actual queue. Easiest to just use an std::deque instead. You may not care about inserting and deleting at both ends, but do care about its giving random access to the contents.

BenMorel · Accepted Answer · 2014-01-14 11:28:46Z

3

You can sort using the standard library std::sort from the '' header. You can either provide a comparator or define an less operators.

struct Process{
    int pid;
    int burst;
    int arrival;
};

    bool operator<(const Process& a, const Process& b) {
          return a.arrival < b.arrival;
    }

    void function(int numProcesses){
        std::dequeue<Process> readyQueue;

        // The following loop is a shortened version of my code
        for(int i=0; i<numProcesses;i++){
             readyQueue.push_back(aProcess);
         }
        std::sort(readyQueue.begin(), readyQueue.end());       
    }

http://en.cppreference.com/w/cpp/algorithm/sort

edited Jan 14, 2014 at 11:28

BenMorel

37k52 gold badges208 silver badges339 bronze badges

answered Nov 8, 2012 at 0:40

111111

16.3k6 gold badges49 silver badges64 bronze badges

1 Comment

billz Over a year ago

He wants process sorted by arrival

paddy · Accepted Answer · 2012-11-08 00:43:59Z

0

You should use std::priority_queue instead... Otherwise you'll have to sort the queue every time you push something onto it.

Note that you still need to define operator<

answered Nov 8, 2012 at 0:43

paddy

63.7k7 gold badges68 silver badges109 bronze badges

2 Comments

Rick_Sch Over a year ago

I had thought of doing that, but this queue will only ever be added to once, so a priority queue didn't seem necessary.

didierc Over a year ago

see this question for a debate on the merits of these solutions speed wise.

bitmask · Accepted Answer · 2012-11-08 00:45:55Z

0

You want to implement a calendar queue. Don't use the queue data structure for that but a set:

struct Process{
    int pid;
    int burst;
    int arrival;
    bool operator<(Process const& other) const {
      if (arrival == other.arrival) {
        if (pid == other.pid)
          return this < &other;
        return pid < other.pid;
      }
      return arrival < other.arrival;
    }
};

void func() {
  std::set<Process> myQueue;
}

There is no need to explicitly sort, the set will keep the contents sorted at all times and you can always remove the first by eraseing the begin() iterator.

answered Nov 8, 2012 at 0:45

bitmask

35.2k17 gold badges107 silver badges174 bronze badges

Collectives™ on Stack Overflow

Sorting a Queue of Structs

4 Answers 4

5 Comments

1 Comment

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

5 Comments

1 Comment

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related