使用方法: 在项目中导入头文件
MYLIB::OrderedList<int> lists;
MYLIB::OrderedList<double> dlists;

P.S: 迭代器有点小问题

//
// Author: Kotarou.
// Email: t.k@07.gs
// FileName: OrderedList.h
// Last modify: 28/05/2015
//

#ifndef __ORDEREDLIST_H__
#define __ORDEREDLIST_H__
#include 
namespace MYLIB
{
	template
	class OrderedList;
	
	template 
	class ListNode
	{
		friend class OrderedList;
		friend class OrderedList::iterator;
		
		private:
			T Element;
			ListNode *prev;
			ListNode *next;
		public:
			ListNode() : next(NULL), prev(NULL) {};
	};
	
	template
	class OrderedList
	{
		private:
			ListNode *head;
			ListNode *tail;
		public:
			OrderedList() : head(NULL), tail(NULL) {};
			
			~OrderedList()
			{
				// delete all elements
				ListNode *temp = NULL;
				while(head)
				{
					temp = head->next;
					delete head;
					head = temp;
				}
			};
			
			// insertion sort
			void insert(const T &Element)
			{
				ListNode *temp = new ListNode;
				temp->Element = Element;
				
				if(!head && !tail)
				{
					head = temp;
					tail = temp;
				}
				else
				{
					//if the Element smaller than head, insert it before the head
					if(temp->Element <= head->Element)
					{
						temp->next = head;
						head->prev = temp;
						head = temp;
						return;
					}
					
					//if the Element greater than tail, insert it after the tail
					if(temp->Element >= tail->Element)
					{
						temp->prev = tail;
						tail->next = temp;
						tail = temp;
						return;
					}
					
					//find a position to insert
					ListNode *cur = head;
					while(cur)
					{
						if(temp->Element <= cur->Element)
						{
							temp->prev = cur->prev;
							cur->prev->next = temp;
							temp->next = cur;
							cur->prev = temp;
							break;
						}
						
						cur = cur->next;
					}
				}
			};
			
			class iterator
			{
				private:
					ListNode *node;
					bool done;
				public:
					iterator() : node(NULL), done(false) {};
					iterator(ListNode *in) : node(in), done(false){};
					
					T& operator*() // dereference
					{ 
						return node->Element; 
					};
					
					const T& operator*() const 
					{
						return node->Element; 
					};
					
					iterator& operator++() // prefix
					{
						node = node->next;
						return *this;
					};
					
					iterator operator++(int) // postfix
					{
						iterator temp = *this;
						++(*this);
						return temp;
					};
					
					iterator& operator--() // prefix
					{
						node = node->prev;
						return *this;
					};
					
					iterator operator--(int) // postfix
					{
						iterator temp = *this;
						--(*this);
						return temp;
					};
					
					bool operator==(const iterator& x) const
					{
						return (node == x.node);
					};
					
					bool operator!=(const iterator &rv)
					{
						if((node == rv.node && node) && done)
							return false;							
						
						if(node == rv.node && node)
							done = true;
						
						return ( node );
					};
			};
			
			iterator begin()
			{
				return iterator(head);
			};
			
			iterator end() 
			{
				return iterator(tail);
			};
	};
}
#endif

一些进程调度算法的模拟.

输入参数:
./a.out 8 6 15 4

源代码:

#include 
#include 
#include 
#include 
#include 
using namespace std;
// some global value
int gMaxTimeInc, gMaxBurstTime;
int gNumProcesses, gTimeSlice;
struct Process
{
int ID;
int ArriveTime;
int WaitingTime;
int BurstTime;
int RunningTime;
int TurnAroundTime;
};
typedef deque dProcess;
void printResult(deque&, string*);
bool praseInput(int, const char**);
void getNextProcess(int&, int&);
bool isDigital(const char*);
char ganttChart(int);
dProcess generateJobQueue();
dProcess FCFS(dProcess, string&);
dProcess RR(dProcess, string&);
dProcess RAND(dProcess, string&);
dProcess SJF(dProcess, string&);
dProcess SRTF(dProcess, string&);
bool sortQueue (const Process &i,const Process &j) { return (i.ID list;
list.push_back(FCFS(Jobs,buffer[0]));
list.push_back(RR(Jobs,buffer[1]));
list.push_back(SJF(Jobs,buffer[2]));
list.push_back(SRTF(Jobs,buffer[3]));
list.push_back(RAND(Jobs,buffer[4]));
printResult(list, buffer);
}
else
{
cerr << "Invalid Argument, Try again.\n";
exit(EXIT_FAILURE);
}
return 0;
}
dProcess RAND(dProcess Jobs, string &chartBuffer)
{
unsigned long Time = 0;
bool done = false;
// get the job Queue.
dProcess ReadyQueue;
dProcess EndQueue;
Process* CPU = NULL;
//main loop for RAND.
for(; !done; ++Time)
{
//check the job queue, move job to the ready queue
for(dProcess::iterator it = Jobs.begin(); it != Jobs.end();)
{
if(Time >= it->ArriveTime)
{
ReadyQueue.push_back(*it);
it = Jobs.erase(it);
}
else
++it;
}
// move finished process to EndQueue
if(CPU && CPU->RunningTime == CPU->BurstTime)
{
CPU->TurnAroundTime += Time;
EndQueue.push_back(*CPU);
CPU = NULL;
}
//make the readyqueue randomly
random_shuffle(ReadyQueue.begin(), ReadyQueue.end());
// if all job finished, set done to true, skip all code.
if(EndQueue.size() == gNumProcesses)
{
done = true;
continue;
}
// check the ReadyQueue, move the first Process into CPU
if(CPU == NULL)
{
// if nothing in readyQueue, print -
if(!ReadyQueue.empty())
{
CPU = &ReadyQueue.front();
ReadyQueue.pop_front();
}
else
{
chartBuffer += "-";
continue;
}
}
else
{
for(dProcess::iterator it = ReadyQueue.begin(); it != ReadyQueue.end(); ++it)
{
if(it->ArriveTime != Time)
++it->WaitingTime;
}
}
if(CPU->RunningTime != CPU->BurstTime)
{
++CPU->RunningTime;
chartBuffer += ganttChart(CPU->ID);
}
}
return EndQueue;
}
dProcess SRTF(dProcess Jobs, string &chartBuffer)
{
unsigned long Time = 0;
bool done = false;
// get the job Queue.
dProcess ReadyQueue;
dProcess EndQueue;
Process* CPU = NULL;
//main loop for SRTF.
for(; !done; ++Time)
{
//check the job queue, move job to the ready queue
for(dProcess::iterator it = Jobs.begin(); it != Jobs.end();)
{
if(Time >= it->ArriveTime)
{
ReadyQueue.push_back(*it);
it = Jobs.erase(it);
}
else
++it;
}
// move finished process to EndQueue
if(CPU && CPU->RunningTime == CPU->BurstTime)
{
CPU->TurnAroundTime += Time;
EndQueue.push_back(*CPU);
CPU = NULL;
}
// if all job finished, set done to true, skip all code.
if(EndQueue.size() == gNumProcesses)
{
done = true;
continue;
}
//sort the ready queue
sort(ReadyQueue.begin(), ReadyQueue.end(), sortForSRTF);
// check the ReadyQueue, move the first Process into CPU
if(CPU == NULL)
{
// if nothing in readyQueue, print -
if(!ReadyQueue.empty())
{
CPU = &ReadyQueue.front();
ReadyQueue.pop_front();
}
else
{
chartBuffer += "-";
continue;
}
}
else
{
// check the ready queue.
if(!ReadyQueue.empty())
{
Process temp = ReadyQueue.front();
if(sortForSRTF(temp, *CPU))
{
ReadyQueue.push_back(*CPU);
CPU = &ReadyQueue.front();
ReadyQueue.pop_front();
}
}
for(dProcess::iterator it = ReadyQueue.begin(); it != ReadyQueue.end(); ++it)
{
if(it->ArriveTime != Time)
++it->WaitingTime;
}
}
if(CPU->RunningTime != CPU->BurstTime)
{
++CPU->RunningTime;
chartBuffer += ganttChart(CPU->ID);
}
}
sort(EndQueue.begin(), EndQueue.end(), sortQueue);
return EndQueue;
}
dProcess SJF(dProcess Jobs, string &chartBuffer)
{
unsigned long Time = 0;
bool done = false;
// get the job Queue.
dProcess ReadyQueue;
dProcess EndQueue;
Process* CPU = NULL;
//main loop for SJF.
for(; !done; ++Time)
{
//check the job queue, move job to the ready queue
for(dProcess::iterator it = Jobs.begin(); it != Jobs.end();)
{
if(Time >= it->ArriveTime)
{
ReadyQueue.push_back(*it);
it = Jobs.erase(it);
}
else
++it;
}
//sort the ready queue
sort(ReadyQueue.begin(), ReadyQueue.end(), sortForSJF);
// move finished process to EndQueue
if(CPU && CPU->RunningTime == CPU->BurstTime)
{
CPU->TurnAroundTime += Time;
EndQueue.push_back(*CPU);
CPU = NULL;
}
// if all job finished, set done to true, skip all code.
if(EndQueue.size() == gNumProcesses)
{
done = true;
continue;
}
// check the ReadyQueue, move the first Process into CPU
if(CPU == NULL)
{
// if nothing in readyQueue, print -
if(!ReadyQueue.empty())
{
CPU = &ReadyQueue.front();
ReadyQueue.pop_front();
}
else
{
chartBuffer += "-";
continue;
}
}
else
{
for(dProcess::iterator it = ReadyQueue.begin(); it != ReadyQueue.end(); ++it)
{
if(it->ArriveTime != Time)
++it->WaitingTime;
}
}
if(CPU->RunningTime != CPU->BurstTime)
{
++CPU->RunningTime;
chartBuffer += ganttChart(CPU->ID);
}
}
sort(EndQueue.begin(), EndQueue.end(), sortQueue);
return EndQueue;
}
dProcess RR(dProcess Jobs, string &chartBuffer)
{
unsigned long Time = 0;
bool done = false;
// get the job Queue.
dProcess ReadyQueue;
dProcess EndQueue;
Process* CPU = NULL;
//main loop for FCFS.
for(; !done; ++Time)
{
//check the job queue, move job to the ready queue
for(dProcess::iterator it = Jobs.begin(); it != Jobs.end();)
{
if(Time >= it->ArriveTime)
{
ReadyQueue.push_back(*it);
it = Jobs.erase(it);
}
else
++it;
}
// move finished process to EndQueue
if(CPU && CPU->RunningTime == CPU->BurstTime)
{
CPU->TurnAroundTime += Time;
EndQueue.push_back(*CPU);
CPU = NULL;
}
// push process back to the readyqueue
if(CPU && CPU->RunningTime != CPU->BurstTime && CPU->RunningTime % gTimeSlice == 0)
{
ReadyQueue.push_back(*CPU);
CPU = NULL;
}
// if all job finished, set done to true, skip all code.
if(EndQueue.size() == gNumProcesses)
{
done = true;
continue;
}
// check the ReadyQueue, move the first Process into CPU
if(CPU == NULL)
{
// if nothing in readyQueue, print -
if(!ReadyQueue.empty())
{
CPU = &ReadyQueue.front();
ReadyQueue.pop_front();
}
else
{
chartBuffer += "-";
continue;
}
}
else
{
for(dProcess::iterator it = ReadyQueue.begin(); it != ReadyQueue.end(); ++it)
{
if(it->ArriveTime != Time)
++it->WaitingTime;
}
}
if(CPU->RunningTime != CPU->BurstTime)
{
++CPU->RunningTime;
chartBuffer += ganttChart(CPU->ID);
}
}
sort(EndQueue.begin(),EndQueue.end(),sortQueue);
return EndQueue;
}
dProcess FCFS(dProcess Jobs, string &chartBuffer)
{
unsigned long Time = 0;
bool done = false;
// get the job Queue.
dProcess ReadyQueue;
dProcess EndQueue;
Process* CPU = NULL;
//main loop for FCFS.
for(; !done; ++Time)
{
//check the job queue, move job to the ready queue
for(dProcess::iterator it = Jobs.begin(); it != Jobs.end();)
{
if(Time >= it->ArriveTime)
{
ReadyQueue.push_back(*it);
it = Jobs.erase(it);
}
else
++it;
}
// move finished process to EndQueue
if(CPU && CPU->RunningTime == CPU->BurstTime)
{
CPU->TurnAroundTime += Time;
EndQueue.push_back(*CPU);
CPU = NULL;
}
// if all job finished, set done to true, skip all code.
if(EndQueue.size() == gNumProcesses)
{
done = true;
continue;
}
// check the ReadyQueue, move the first Process into CPU
if(CPU == NULL)
{
// if nothing in readyQueue, print -
if(!ReadyQueue.empty())
{
CPU = &ReadyQueue.front();
ReadyQueue.pop_front();
}
else
{
chartBuffer += "-";
continue;
}
}
else
{
for(dProcess::iterator it = ReadyQueue.begin(); it != ReadyQueue.end(); ++it)
{
if(it->ArriveTime != Time)
++it->WaitingTime;
}
}
if(CPU->RunningTime != CPU->BurstTime)
{
++CPU->RunningTime;
chartBuffer += ganttChart(CPU->ID);
}
}
return EndQueue;
}
void getNextProcess(int &ArrivalTime, int &BurstTime)
{
static int PrevTime=-1;
if(PrevTime == -1)
PrevTime = ArrivalTime = 0;
else
ArrivalTime = PrevTime + 1 + rand() % gMaxTimeInc;
BurstTime = 1 + rand() % gMaxBurstTime;
PrevTime = ArrivalTime;
}
dProcess generateJobQueue()
{
dProcess JobQueue;
for(int i = 0; i < gNumProcesses; ++i)
{
Process temp;
temp.ID = i;
temp.WaitingTime = 0;
temp.RunningTime = 0;
getNextProcess(temp.ArriveTime, temp.BurstTime);
temp.TurnAroundTime = 0 - temp.ArriveTime;
JobQueue.push_back(temp);
}
return JobQueue;
}
bool praseInput(int num, const char **input)
{
if(num < 5)
return false;
if(isDigital(input[1]) && isDigital(input[2]) && isDigital(input[3]) && isDigital(input[4]))
{
gNumProcesses = atoi(input[1]);
gMaxTimeInc = atoi(input[2]);
gMaxBurstTime = atoi(input[3]);
gTimeSlice = atoi(input[4]);
return true;
}
return false;
}
bool isDigital(const char *num)
{
size_t len = strlen(num);
for(size_t i = 0; i < len; ++i)
{
if(!isdigit(num[i]))
return false;
}
return true;
}
char ganttChart(int index)
{
while(index >= 62)
index -= 62;
if(index >= 0 && index <= 9)
return 48 + index;
else if(index >= 10 && index <= 35)
return 55 + index;
else if(index >= 36 && index <= 61)
return 61 + index;
return 0;
}
void printResult(deque &Queue, string *ChartArray)
{
printf("%16s%11s%13s%12s%12s\n","FCFS", "RR", "SJF", "SRTF", "RAND");
printf("%8s%5s%5s%7s%5s%7s%5s%7s%5s%7s%5s\n", "BT", "WT", "TT", "WT", "TT", "WT", "TT", "WT", "TT", "WT", "TT");
int waiting[5] = {}, turn[5] = {};
dProcess dp[5];
for(int i = 0; i < 5; ++i)
{
dp[i] = Queue.front();
Queue.pop_front();
}
for(int i = 0; i < gNumProcesses; ++i)
{
printf("P%-5d", i);
Process ps;
for(int j = 0; j < 5; ++j)
{
ps = dp[j].front();
dp[j].pop_front();
waiting[j] += ps.WaitingTime;
turn[j] += ps.TurnAroundTime;
if(j == 0)
printf("%-5d", ps.BurstTime);
printf("%-5d%-7d", ps.WaitingTime, ps.TurnAroundTime);
}
printf("\n");
}
printf("%-11s", "Average:");
for(int i = 0; i < 5; ++i)
{
printf("%-5d%-7d", waiting[i] / gNumProcesses, turn[i] / gNumProcesses);
}
printf("\n\n%-6s%s\n", "FCFS:", ChartArray[0].c_str());
printf("%-6s%s\n", "RR:", ChartArray[1].c_str());
printf("%-6s%s\n", "SJF:", ChartArray[2].c_str());
printf("%-6s%s\n", "SRTF:", ChartArray[3].c_str());
printf("%-6s%s\n", "RAND:", ChartArray[4].c_str());
}

运行结果: