6 Replies - 7065 Views - Last Post: 20 April 2010 - 07:31 PM Rate Topic: -----

#1 Lachlan Davis  Icon User is offline

  • New D.I.C Head

Reputation: -4
  • View blog
  • 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  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 174
  • View blog
  • 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

Was This Post Helpful? 0
  • +
  • -

#3 Lachlan Davis  Icon User is offline

  • New D.I.C Head

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

Re: Sorting using Priority Queue

Posted 19 April 2010 - 11:20 PM

I tried that and got this....

ljd173@mega-pc12:~/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()
{

}

             

void PQueue::addJob(const Job &j)
{
	
	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);

			pq.addJob(j);

			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?
Was This Post Helpful? 0
  • +
  • -

#4 muballitmitte  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 174
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

#5 n8wxs  Icon User is offline

  • --... ...-- -.. . -. ---.. .-- -..- ...
  • member icon

Reputation: 972
  • View blog
  • 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
Was This Post Helpful? 0
  • +
  • -

#6 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6036
  • View blog
  • Posts: 23,421
  • Joined: 23-August 08

Re: Sorting using Priority Queue

Posted 20 April 2010 - 05:55 AM

Merged duplicate topics.
Was This Post Helpful? -1
  • +
  • -

#7 Lachlan Davis  Icon User is offline

  • New D.I.C Head

Reputation: -4
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1