ایجاد یک صف اولیت با استفاده از اشیاء یک کلاس

[alimooghashang]

با سلام
من یه صف اولیت از نوع کلاسی که خودم ساختم میخوام ایجاد کنم
ولی صف به ترتیب نمیشه

من اینطوری صف رو تعریف کردم


class myclass{
public:
int a,b;
int c;
int d; // پارامتری که نشون دهنده بزرگی یا کوچکی شئی من هست
bool operator < (const myclass);
bool operator > (const myclass);
bool operator >= (const myclass);
bool operator <= (const myclass);
};



bool myclass::operator <(const myclass o)
{
if (d<o.d)
return true;

return false;
}

bool myclass::operator >(const myclass o)
{
if (d>o.d)
return true;

return false;
}

bool myclass::operator <=(const myclass o)
{
if (d<=o.d)
return true;

return false;
}

bool myclass::operator >=(const myclass o)
{
if (d>=o.d)
return true;

return false;
}


و وقتی که صف رو ایجاد میکنم بر حسب متغیر d هر شئی مرتب نمیشه
باید چکار کنم که این مرتب سازی در صف انجام بشه

توی مثال MSDN با int تعریف کرده ولی من میخوام شئی های کلاس خودم را داخل صف بریزم

اینم نحوه ساختن صفی از شئی های کلاس خودم



typedef priority_queue<myclass*, vector<myclass*>, greater<myclass*>> myclass_PR_QUEUE;

myclass_PR_QUEUE myclassqueue;


و داخل برنامه هم اینطوری عمل میکنم


void main()
{
myclass *c1 = new myclass;
c1->d=10;
myclassqueue.push(c1);

myclass *c2 = new myclass;
c2->d=15;
myclassqueue.push(c2);


myclass *c3 = new myclass;
c3->d=5;
myclassqueue.push(c3);

}
الان باید ترتیب قرار گرفتن صف اینطوری باشه
c2
c1
c3

که اینطوره

c2
c3
c1

البته این فقط یه مثال بود که بفهمین مشکل چیه!
ممنون میشم اگه کسی بتونه کمکم کنه!

[sh4mid]

سلام
موارد زیر وحی منزل نیست ولی بهتر است رعایت شود :قهقهه::قهقهه:
اول از همه وقتی یک کلاس رو می نویسید موارد زیر را در نظر بگیرید

نوشتن constructor
نوشتن copycostructor
نوشتن destructor
private کردن اعضا
بازتعریف عملگر>>(دلیلش را پایین نوشته ام)


دوباره می گم بهتره این موارد رو رعایت کنید بایدی در کار نیست(به موارد بالا میشود بازتعریف عملگر = رو هم اضافه کرد)

مثلا کلاس جدید همچین جیزی می شود



class MyClass
{
friend ostream& operator<< (ostream& , const MyClass&);

public:


MyClass():a(0),b(0),d(0){}
MyClass(int aval,int bval,int dval):a(aval),b(bval),d(dval){}
MyClass(const MyClass& dup):a(dup.a),b(dup.b),d(dup.d){}

const int GetPriority() const
{
return d;
}

void SetPriority(int val)
{
d=val;
}

private:
int a,b;
int d; //prio
};

همونطور که می دونید صف اولویت اینجوری تعریف میشه



template < class T, class Container = vector<T>,class Compare = less<typename Container::value_type> > class priority_queue;

که اولین مورد نوع عناصر موجود در صف رو تعیین میکنه
دومی میگه صف از چی استفاده کنه برای ذخیره و بازیابی عناصرش(پیش فرض vector ، البته از dequeue یا allocator خودمون هم میشه استفاده کرد )
و سومی کلاسی است که تعیین میکنه عناصر چطور مقایسه شوند(پیش فرض از less استفاده میکنه )

خوب بریم سر وقت کدت
چرا صفت رو اینجوری تعریف کردی؟:متفکر::متفکر:



priority_queue<myclass*, vector<myclass*>, greater<myclass*>>

کدت رو Trace کردم ، وقتی از اشاره گر تو STL استفاده کنی ، بعضی اوقات نتایج عجیبی به دست می آید ،
موقع pop کردن , push کردن تو جابجایی عناصر اشتباه میکنه(نمی دونم چرا؟)

برای راحتی کار من صف جدید رو این جوری تعریف میکنم



typedef priority_queue<MyClass, vector<MyClass>, greater<vector<MyClass>::value_type > > PQ_Great;

عملگر ها رو هم اینجور تعریف میکنم




bool operator< (const MyClass& left, const MyClass &right)
{
return left.GetPriority() < right.GetPriority();
}

bool operator> (const MyClass& left, const MyClass &right)
{
return left.GetPriority() > right.GetPriority();
}


(دقت کن که اینا دیگه عضو کلاس نیستند)

مثال برای این مورد



pqgreat.push(MyClass(1,1,1));
pqgreat.push(MyClass(2,2,2));
pqgreat.push(MyClass(3,3,3));
pqgreat.push(MyClass(4,4,4));
pqgreat.push(MyClass(5,5,5));
pqgreat.push(MyClass(6,6,6));
pqgreat.push(MyClass(7,7,7));
pqgreat.push(MyClass(8,8,8));
pqgreat.push(MyClass(9,9,9));

while (!pqgreat.empty())
{
cout << pqgreat.top()<< endl;
pqgreat.pop();
}
cout << endl;

اینجا عملگر >> رو اینجوری تعریف کردم تا موقعی که cout می خواهد اونو چاپ کنه اونجوری که می خواهیم چاپ بشه



ostream& operator<< (ostream& os, const MyClass &m)
{
os<<"("<<m.a<<","<<m.b<<")["<<m.d<<"]";
return os;
}

البته به غیر از lessو greater میشه دو جور دیگه هم آرگومان سوم رو تعریف کرد

حالت اول:
تعریف یک کلاس یا struct که عملگر () رو بازتعریف کرده باشه مثل این حالت




class MyCompare
{
bool reverse;
public:
MyCompare(const bool& revparam=false)
{reverse=revparam;}
bool operator() (const MyClass& left, const MyClass& right) const
{
if (reverse) return (left.GetPriority()>right.GetPriority());
else return (left.GetPriority()<right.GetPriority());
}
};


حالت دوم:
تعریف یک کلاس یا struct که از binary_function مشتق شده باشه و عملگر () رو باز تعریف کرده باشه



struct MyCompare2: public binary_function<MyClass, MyClass, bool>
{
bool reverse;
public:
MyCompare2(const bool& revparam=false) {reverse=revparam;}
bool operator()(const MyClass& left, const MyClass& right) const
{
if (reverse) return (left.GetPriority()>right.GetPriority());
else return (left.GetPriority()<right.GetPriority());
}
};

البته خودم فرقشون رو زیاد نفهمیدم :قهقهه: :قهقهه:

حالا میتونیم همچین چیزهایی داشته باشیم




typedef priority_queue<MyClass, vector<MyClass>, MyCompare > PQ_Compare;
typedef priority_queue<MyClass, vector<MyClass>, MyCompare2 > PQ_Compare2;

PQ_Compare pqcompare=PQ_Compare(MyCompare());
PQ_Compare pqcompare_rev=PQ_Compare(MyCompare(true));
PQ_Compare2 pqcompare2=PQ_Compare2(MyCompare2());
PQ_Compare2 pqcompare2_rev=PQ_Compare2(MyCompare2(true));


کد نهایی




#include <iostream>
#include <queue>

using namespace std;


class MyClass
{
friend ostream& operator<< (ostream& , const MyClass&);

public:


MyClass():a(0),b(0),d(0){}
MyClass(int aval,int bval,int dval):a(aval),b(bval),d(dval){}
MyClass(const MyClass& dup):a(dup.a),b(dup.b),d(dup.d){}

const int GetPriority() const
{
return d;
}

void SetPriority(int val)
{
d=val;
}

private:
int a,b;
int d; //prio
};

bool operator< (const MyClass& left, const MyClass &right)
{
return left.GetPriority() < right.GetPriority();
}

bool operator> (const MyClass& left, const MyClass &right)
{
return left.GetPriority() > right.GetPriority();
}

ostream& operator<< (ostream& os, const MyClass &m)
{
os<<"("<<m.a<<","<<m.b<<")["<<m.d<<"]";
return os;
}


class MyCompare
{
bool reverse;
public:
MyCompare(const bool& revparam=false)
{reverse=revparam;}
bool operator() (const MyClass& left, const MyClass& right) const
{
if (reverse) return (left.GetPriority()>right.GetPriority());
else return (left.GetPriority()<right.GetPriority());
}
};

struct MyCompare2: public binary_function<MyClass, MyClass, bool>
{
bool reverse;
public:
MyCompare2(const bool& revparam=false) {reverse=revparam;}
bool operator()(const MyClass& left, const MyClass& right) const
{
if (reverse) return (left.GetPriority()>right.GetPriority());
else return (left.GetPriority()<right.GetPriority());
}
};

typedef priority_queue<MyClass, vector<MyClass>, less <vector<MyClass>::value_type > > PQ_Less;
typedef priority_queue<MyClass, vector<MyClass>, greater<vector<MyClass>::value_type > > PQ_Great;
typedef priority_queue<MyClass, vector<MyClass>, MyCompare > PQ_Compare;
typedef priority_queue<MyClass, vector<MyClass>, MyCompare2 > PQ_Compare2;

int main()
{
PQ_Less pqless;
PQ_Great pqgreat;
PQ_Compare pqcompare=PQ_Compare(MyCompare());
PQ_Compare pqcompare_rev=PQ_Compare(MyCompare(true));
PQ_Compare2 pqcompare2=PQ_Compare2(MyCompare2());
PQ_Compare2 pqcompare2_rev=PQ_Compare2(MyCompare2(true));

pqless.push(MyClass(1,1,1));
pqless.push(MyClass(2,2,2));
pqless.push(MyClass(3,3,3));
pqless.push(MyClass(4,4,4));
pqless.push(MyClass(5,5,5));
pqless.push(MyClass(6,6,6));
pqless.push(MyClass(7,7,7));
pqless.push(MyClass(8,8,8));
pqless.push(MyClass(9,9,9));

while (!pqless.empty())
{
cout << pqless.top()<< endl;
pqless.pop();
}
cout << endl;


pqgreat.push(MyClass(1,1,1));
pqgreat.push(MyClass(2,2,2));
pqgreat.push(MyClass(3,3,3));
pqgreat.push(MyClass(4,4,4));
pqgreat.push(MyClass(5,5,5));
pqgreat.push(MyClass(6,6,6));
pqgreat.push(MyClass(7,7,7));
pqgreat.push(MyClass(8,8,8));
pqgreat.push(MyClass(9,9,9));

while (!pqgreat.empty())
{
cout << pqgreat.top()<< endl;
pqgreat.pop();
}
cout << endl;


pqcompare.push(MyClass(1,1,1));
pqcompare.push(MyClass(2,2,2));
pqcompare.push(MyClass(3,3,3));
pqcompare.push(MyClass(4,4,4));
pqcompare.push(MyClass(5,5,5));
pqcompare.push(MyClass(6,6,6));
pqcompare.push(MyClass(7,7,7));
pqcompare.push(MyClass(8,8,8));
pqcompare.push(MyClass(9,9,9));

while (!pqcompare.empty())
{
cout << pqcompare.top()<< endl;
pqcompare.pop();
}
cout << endl;


pqcompare_rev.push(MyClass(1,1,1));
pqcompare_rev.push(MyClass(2,2,2));
pqcompare_rev.push(MyClass(3,3,3));
pqcompare_rev.push(MyClass(4,4,4));
pqcompare_rev.push(MyClass(5,5,5));
pqcompare_rev.push(MyClass(6,6,6));
pqcompare_rev.push(MyClass(7,7,7));
pqcompare_rev.push(MyClass(8,8,8));
pqcompare_rev.push(MyClass(9,9,9));

while (!pqcompare_rev.empty())
{
cout << pqcompare_rev.top()<< endl;
pqcompare_rev.pop();
}
cout << endl;

pqcompare2.push(MyClass(1,1,1));
pqcompare2.push(MyClass(2,2,2));
pqcompare2.push(MyClass(3,3,3));
pqcompare2.push(MyClass(4,4,4));
pqcompare2.push(MyClass(5,5,5));
pqcompare2.push(MyClass(6,6,6));
pqcompare2.push(MyClass(7,7,7));
pqcompare2.push(MyClass(8,8,8));
pqcompare2.push(MyClass(9,9,9));

while (!pqcompare2.empty())
{
cout << pqcompare2.top()<< endl;
pqcompare2.pop();
}
cout << endl;

pqcompare2_rev.push(MyClass(1,1,1));
pqcompare2_rev.push(MyClass(2,2,2));
pqcompare2_rev.push(MyClass(3,3,3));
pqcompare2_rev.push(MyClass(4,4,4));
pqcompare2_rev.push(MyClass(5,5,5));
pqcompare2_rev.push(MyClass(6,6,6));
pqcompare2_rev.push(MyClass(7,7,7));
pqcompare2_rev.push(MyClass(8,8,8));
pqcompare2_rev.push(MyClass(9,9,9));

while (!pqcompare2_rev.empty())
{
cout << pqcompare2_rev.top()<< endl;
pqcompare2_rev.pop();
}
cout << endl;

system("pause");

return 0;
}

[alimooghashang]

نکاتی را که گفتین خیلی نکات سنجیده و بجایی بود
ممنونم که یاد اوری کردید!

چرا من صف رو اینطوری تعریف کردم با اشاره گر؟ بخاطر این بود که میخوام یک درخت جستجو تشکیل بدم و هر بار که فرزندان باید گسترش پیدا کنند و در صف قرار بگیرند معلوم نیست تاچه میزانی گسترش پیدا میکنند! بهمین خاطر اشاره گر گرفتم که هر دفعه یه شئی جدید بسازم و از همه مهمتر بتونم پدر اون رو مشخص کنم!

این کلاسی که من نوشتم نمونه بود بخاطر اینکه فقط مشکل این صف رو بفهمم وگرنه کد این نیست!

[alimooghashang]

و یه سوال
من ترجیه میدم اپراتور ها رو داخل کلاس تعریف کنم!
ایرادی داره؟
فرقش با اینکه شما خارج از کلاس تعریف کردید چیه؟

[sh4mid]

خب
شما مي خواهيد يک BST تشکيل دهيد که Node هاش صف هست يا صفي که اعضاش اشاره گره؟:متفکر:
بماند بريم سر وقت تعريف دوباره صف
اول از همه



typedef MyClass* PMyClass;

بعد



typedef priority_queue<PMyClass, vector<PMyClass>, less <vector<PMyClass>::value_type > > PQ_Less;
typedef priority_queue<PMyClass, vector<PMyClass>, greater<vector<PMyClass>::value_type > > PQ_Great;
typedef priority_queue<PMyClass, vector<PMyClass>, MyCompare > PQ_Compare;
typedef priority_queue<PMyClass, vector<PMyClass>, MyCompare2 > PQ_Compare2;


و



ostream& operator<< (ostream& os, const PMyClass m)
{
os<<"("<<m->GetA()<<","<<m->GetB()<<")["<<m->GetPriority()<<"]";
return os;
}

دوتا کلاس MyCompareو MyCompare2 هم اينجوري ميشوند




class MyCompare
{
bool reverse;
public:
MyCompare(const bool& revparam=false)
{reverse=revparam;}
bool operator() (const MyClass& left, const MyClass& right) const
{
if (reverse) return (left.GetPriority()>right.GetPriority());
else return (left.GetPriority()<right.GetPriority());
}
bool operator() (const PMyClass left, const PMyClass right) const
{
if (reverse) return (left->GetPriority()>right->GetPriority());
else return (left->GetPriority()<right->GetPriority());
}
};

struct MyCompare2: public binary_function<MyClass, MyClass, bool>
{
bool reverse;
public:
MyCompare2(const bool& revparam=false) {reverse=revparam;}
bool operator()(const MyClass& left, const MyClass& right) const
{
if (reverse) return (left.GetPriority()>right.GetPriority());
else return (left.GetPriority()<right.GetPriority());
}
bool operator() (const PMyClass left, const PMyClass right) const
{
if (reverse) return (left->GetPriority()>right->GetPriority());
else return (left->GetPriority()<right->GetPriority());
}
};


البته مي توانيد تعاريف زير را حذف کنيد



bool operator() (const MyClass& left, const MyClass& right) const
{
if (reverse) return (left.GetPriority()>right.GetPriority());
else return (left.GetPriority()<right.GetPriority());
}

bool operator()(const MyClass& left, const MyClass& right) const
{
if (reverse) return (left.GetPriority()>right.GetPriority());
else return (left.GetPriority()<right.GetPriority());
}

و در نهايت




int main()
{
PQ_Less pqless;
PQ_Great pqgreat;
PQ_Compare pqcompare=PQ_Compare(MyCompare());
PQ_Compare pqcompare_rev=PQ_Compare(MyCompare(true));
PQ_Compare2 pqcompare2=PQ_Compare2(MyCompare2());
PQ_Compare2 pqcompare2_rev=PQ_Compare2(MyCompare2(true));

PMyClass pmycls1=new MyClass(1,1,1);
PMyClass pmycls2=new MyClass(2,2,2);
PMyClass pmycls3=new MyClass(3,3,3);
PMyClass pmycls4=new MyClass(4,4,4);


pqless.push(pmycls1);
pqless.push(pmycls2);
pqless.push(pmycls3);
pqless.push(pmycls4);


while(!pqless.empty())
{
cout<<pqless.top()<<endl;
pqless.pop();
}

cout<<"-----------------"<<endl;

pqgreat.push(pmycls1);
pqgreat.push(pmycls2);
pqgreat.push(pmycls3);
pqgreat.push(pmycls4);


while(!pqgreat.empty())
{
cout<<pqgreat.top()<<endl;
pqgreat.pop();
}

cout<<"-----------------"<<endl;

pqcompare.push(pmycls1);
pqcompare.push(pmycls2);
pqcompare.push(pmycls3);
pqcompare.push(pmycls4);


while(!pqcompare.empty())
{
cout<<pqcompare.top()<<endl;
pqcompare.pop();
}

cout<<"-----------------"<<endl;

pqcompare_rev.push(pmycls1);
pqcompare_rev.push(pmycls2);
pqcompare_rev.push(pmycls3);
pqcompare_rev.push(pmycls4);


while(!pqcompare_rev.empty())
{
cout<<pqcompare_rev.top()<<endl;
pqcompare_rev.pop();
}

cout<<"-----------------"<<endl;

delete pmycls1;
delete pmycls2;
delete pmycls3;
delete pmycls4;



system("pause");

return 0;
}


اميدوارم کارتو راه بندازه :لبخند:



و يه سوال
من ترجيه ميدم اپراتور ها رو داخل کلاس تعريف کنم!
ايرادي داره؟
فرقش با اينکه شما خارج از کلاس تعريف کرديد چيه؟

فرقي ندارند ، Compiler من قاطي کرده بود ، اونجوري رو قبول نمي کرد اين طوري نوشتم

[alimooghashang]

خب من مشکلم با حذف کردن اشاره گرها و تبدیل به شئی ساده حل شد!
الان صف به صورت کمتر اول اولویت بندی میشه!
ممنون از راهنمایی شما!