# Sorting using Priority Queue

Page 1 of 1

## 6 Replies - 14326 Views - Last Post: 20 April 2010 - 07:31 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=169097&amp;s=999d794d53807b8e7e77e72a6e49801a&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 Lachlan Davis

Reputation: -4
• Posts: 38
• Joined: 17-April 10

# Sorting using Priority Queue

Posted 19 April 2010 - 10:48 PM

How do I sort using the list header in C++

More specifically, how do I use the sort function in list when the objects im sorting contain multiple data fields

```struct Job {

int num; //Job number

int priority; //Job priority, 0-highest, 1-higher, 2-lower, 3-lowest

float start; //Job start time

float last;  //Job last time

};

```

I want to sort by start time. So how would I go about that?

Is This A Good Question/Topic? 0

## Replies To: Sorting using Priority Queue

### #2 muballitmitte

• D.I.C Regular

Reputation: 174
• Posts: 470
• Joined: 05-November 08

## Re: Sorting using Priority Queue

Posted 19 April 2010 - 11:03 PM

There are actually two ways you could handle this. One would be to use the STL sort function

sort (Iterator first, Iterator last, comparefunction);

and pass to it a function that compares two job objects on their start time

```bool compareJobs(Job& j1, Job &j2)
{
return j1.start < j2.start;
}

```

An alternative is to use the sort member of the STL list class (it uderstand that you use that)

```joblist.sort(compareJobs);

```

This post has been edited by muballitmitte: 19 April 2010 - 11:03 PM

### #3 Lachlan Davis

Reputation: -4
• Posts: 38
• Joined: 17-April 10

## Re: Sorting using Priority Queue

Posted 19 April 2010 - 11:20 PM

I tried that and got this....

[email protected]:~/203/2\$ g++ PQueue.cpp task1main.cpp -o jobs
PQueue.cpp: In member function ‘void PQueue::sortJobs()’:
PQueue.cpp:30: error: no matching function for call to ‘std::list<Job, std::allocator<Job> >::sort(<unresolved overloaded function type>)’
/usr/include/c++/4.4/bits/list.tcc:301: note: candidates are: void std::list<_Tp, _Alloc>::sort() [with _Tp = Job, _Alloc = std::allocator<Job>]
/usr/include/c++/4.4/bits/list.tcc:378: note: void std::list<_Tp, _Alloc>::sort(_StrictWeakOrdering) [with _StrictWeakOrdering = bool (PQueue::*)(Job&, Job&), _Tp = Job, _Alloc = std::allocator<Job>]

PQueue.cpp:
```#include "PQueue.h"
#include <list>
PQueue::PQueue()
{

}

PQueue::PQueue(const PQueue&)
{

}

PQueue::~PQueue()
{

}

{

jobs.push_back(j);

} //add a new job at the end of the queue

bool PQueue::compareJobs(Job& j1, Job &j2)
{
return j1.start < j2.start;
}

void PQueue::sortJobs()
{
jobs.sort(compareJobs);

} //Sort jobs according to the priority, start time and end time.

void PQueue::print()
{
for(it = jobs.begin(); it != jobs.end(); it++)
{
cout << (*it).num << ", ";
cout << (*it).priority << ", " << endl;
}
} //output jobs list

```

PQueue.h
```//One can only change the definition at the specified lines

#ifndef PRIORITYQUEUE

#define PRIORITYQUEUE

#include <list>

#include <iostream>

#include <fstream>

using namespace std;

struct Job {

int num; //Job number

int priority; //Job priority, 0-highest, 1-higher, 2-lower, 3-lowest

float start; //Job start time

float last;  //Job last time

};

class PQueue {

private:

list<Job> jobs;
list<Job>::iterator it;

public:

PQueue();

PQueue(const PQueue&);

~PQueue();

void addJob(const Job &); //add a new job at the end of the queue

void sortJobs(); //Sort jobs according to the priority, start time and end time.

void print(); //output jobs list
bool compareJobs(Job&, Job &);

};

#endif

```

main.cpp
```#include "PQueue.h"
#include <iostream>
#include <fstream>

using namespace std;

int main()
{
Job j;
PQueue pq;
ifstream ifs;
ifs.open("Jobs.txt");

if(ifs.good())
{
ifs >> j.num;
ifs.ignore(1);

while(!ifs.eof())
{

ifs >> j.priority;
ifs.ignore(1);
ifs >> j.start;
ifs.ignore(1);
ifs >> j.last;
ifs.ignore(1);

ifs >> j.num;
ifs.ignore(1);
}
}

pq.sortJobs();
pq.print();
}

```

Jobs.txt
```1, 1, 0.0, 0.5
2, 0, 0.2, 1.5
3, 1, 1.0, 4.5
4, 0, 0.5, 2.5

```

What have i done?

### #4 muballitmitte

• D.I.C Regular

Reputation: 174
• Posts: 470
• Joined: 05-November 08

## Re: Sorting using Priority Queue

Posted 19 April 2010 - 11:37 PM

define the compare function as global inside the header and it will work.

### #5 n8wxs

• --... ...-- -.. . -. ---.. .-- -..- ...

Reputation: 972
• Posts: 3,878
• Joined: 07-January 08

## Re: Sorting using Priority Queue

Posted 20 April 2010 - 01:28 AM

Here's one way:

```#include <iostream>
#include <fstream>
#include <iomanip>
#include <list>
#include <string>
#include <cctype>

using namespace std;

struct Job {
int num; //Job number
int priority; //Job priority, 0-highest, 1-higher, 2-lower, 3-lowest
float start; //Job start time
float last;  //Job last time
// constructor
Job (int a, int b, float s, float l) {
num = a;
priority = b;
start = s;
last = l;
}
};

bool compare_jobs(Job one, Job two)
{
if (one.start > two.start)
return false;

return true;
}

int _tmain(int argc, _TCHAR* argv[])
{
Job x(1,2,3,4);
Job y(1,2,5,4);
Job z(1,2,6,4);
Job w(1,2,7,4);
Job t(1,2,8,4);

list<Job> joblist;
list<Job>::iterator jobit;

joblist.push_back(t);
joblist.push_back(w);
joblist.push_back(x);
joblist.push_back(z);
joblist.push_back(y);

joblist.sort(compare_jobs);

cout << "Jobs in ascending start times: ";

for (jobit = joblist.begin(); jobit != joblist.end(); jobit++)
cout << (*jobit).start << ", ";

cout << endl;

cout << endl << "Hit ENTER key to continue...";
cin.clear();
cin.sync();
cin.get();

return 0;
}

```

Output:

Quote

Jobs in ascending start times: 3, 5, 6, 7, 8,

Hit ENTER key to continue...

See Sort elements in container

• Saucy!

Reputation: 6246
• Posts: 24,014
• Joined: 23-August 08

## Re: Sorting using Priority Queue

Posted 20 April 2010 - 05:55 AM

Merged duplicate topics.

### #7 Lachlan Davis

Reputation: -4
• Posts: 38
• Joined: 17-April 10

## Re: Sorting using Priority Queue

Posted 20 April 2010 - 07:31 PM

Thanks, I didn't mean to make duplicates.

Cheers for the help guys, It works great now. I'm loving the list class, it's great.