我的priority_queue顺序错了 [英] my priority_queue order is wrong
本文介绍了我的priority_queue顺序错了的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我的程序有一个priority_queue无法正常工作！当我从那个priority_queue返回元素中弹出元素时没有任何顺序！
我写了两个类，第一个类是第二类的父类。
头等舱：
// ====================================== =====
class treeNode
{
public ：
treeNode（）; // 构造函数
treeNode（ int ）; // 构造函数
虚拟 void display（ void ） const ; // 在终端中显示树对象
朋友 bool operator <（ const treeNode&， const treeNode&）;
朋友 bool operator > ;（ const treeNode&， const treeNode&）;
int iterate;
treeNode * left;
treeNode * right;
};
treeNode :: treeNode（）
{
iterate = 1 ;
left = NULL;
right = NULL;
}
treeNode :: treeNode（ int i）
{
iterate = i;
left = NULL;
right = NULL;
}
bool operator <（ const treeNode& a， const treeNode& b）
{
< span class =code-keyword> if （a.iterate< b.iterate）
{
return 真;
}
其他
{
返回 假;
}
}
bool operator > （ const treeNode& a， const treeNode& b）
{
if （a.iterate> b.iterate）
{
return < span class =code-keyword> true ;
}
其他
{
返回 假;
}
}
void treeNode :: display（ void ） const
{
std :: cout<<迭代<< ENDL;
}
第二堂课：
// =================== ========================
class letter： public treeNode
{
public ：
letter（ ）; // 构造函数
letter（ char ）; // 构造函数
letter（ char ， int ）; // 构造函数
朋友 bool operator <（ const letter& ;， const letter&）;
朋友 bool operator > ;（ const letter&， const letter&）;
void display（ void ） const ; // 在终端显示字母对象
char 字符;
};
letter :: letter（）：treeNode（）
{
}
letter :: letter（ char ch）：character（ch），treeNode（ 1 ）
{
}
letter :: letter（ char ch， int i）：character（ch），treeNode（i）
{
}
bool operator <（ const letter& a， const letter& b）
{
< span class =code-keyword> if （a.iterate< b.iterate）
{
return 真;
}
其他
{
返回 假;
}
}
bool operator > （ const letter& a， const letter& b）
{
if （a.iterate> b.iterate）
{
return < span class =code-keyword> true ;
}
其他
{
返回 假;
}
}
void letter :: display（ void ） const
{
if （character = = ' \ n'）
{
std :: cout< < setw（ 8 ）<< new line<< ，<< setw（ 6 ）<<迭代<< ENDL;
}
else
{
if （字符== ' '）
{
std :: cout<< setw（ 8 ）<< space<< ，<< setw（ 6 ）<<迭代<< ENDL;
}
else
{
std :: cout<< setw（ 8 ）<<字符<< ，<< setw（ 6 ）<<迭代<< ENDL;
}
}
}
// ===== ====================================== < br $>
我写下面的函数用于读取文件，以了解文件中存在的每个字符的迭代次数，它是否正常工作我使用在下一个函数中。
// ===========================================
// 读取文件并查找每个字符的迭代次数
映射< char ，字母> countEachLetterInFile（string addOfFile）
{
string str;
letter * tempLetter;
map< char ，字母> letterMap;
map< char ，letter> :: iterator mapIter;
ifstream fp（addOfFile，ios :: in ）;
// 检查文件和文件路径的有效性
if （！fp）
{
cerr<< 打开文件时出错！<< ENDL;
退出（ 1 ）;
}
// 逐行读取文件
while （getline（fp，str））
{
str + = ' \ n';
// 按字符串逐字符移动
for （ int i = 0 ; i< str.size（ ）; i ++）
{
mapIter = letterMap.find（str.at（i））;
if （mapIter == letterMap.end（））
{
tempLetter = new letter（str.at（i））;
letterMap [str.at（i）] = * tempLetter;
delete [] tempLetter;
}
else
{
letterMap [str.at（i）]。iterate ++;
}
}
}
mapIter = letterMap.find（' \\\
'）;
if （mapIter！= letterMap.end（））
{
letterMap [' \ n']。iterate--;
}
return letterMap;
}
此函数出现问题，此函数是treeNode的priority_queue *。
我用地图填写（前一个函数的输出，地图中的值是正确的，没有任何问题）。
// ============== =============================
// 制作huffman树并返回< char，string>并保存< string，char>在文件中
map< char ，字符串> makeHuffmanTree（map< char ，letter> mapOfLetter）
{
treeNode * tempTreeNode;
map< char ，字符串> huffmanCode;
map< char ，letter> :: iterator mapIter;
priority_queue< treeNode *，vector< treeNode *> ;, greater< treeNode *> > letterPriorityQueue;
for （mapIter = mapOfLetter.begin（）; mapIter！= mapOfLetter.end（）; mapIter ++）
{
letterPriorityQueue.push（ new 字母（mapIter-> second.character，mapIter-> second.iterate））;
}
//
// 订单错误!!
//
//
std :: cout<< letterPriorityQueue.size（）<< ENDL;
int size = letterPriorityQueue.size（）;
for （ int i = 0 ; i< size; i ++）
{
letterPriorityQueue.top（） - > display（）;
letterPriorityQueue.pop（）;
}
/ * while（letterPriorityQueue.size（）> 2）
{
} * /
return huffmanCode;
}
地图价值：
http://open-mind.ir/wp-content/uploads/2015/03/11。 png [ ^ ]
当我读到priority_queue时：
http://open-mind.ir/wp-content/uploads/2015/03/2.png [<一个href =http://open-mind.ir/wp-content/uploads/2015/03/2.pngtarget =_ blanktitle =新窗口> ^ ]
指针。
试试这段代码：
试试这段代码：
#include < iostream >
#include < SP class =code-preprocessor> < vector >
#include < queue >
using namespace std;
class 信
{
char c;
int refs;
public ：
Letter（ char c， int refs）：c（c），refs（refs）{}
void show（）{cout<< c<< << refs<< endl;}
朋友 bool operator > （ const Letter& a， const Letter& b）;
朋友 class CmpLetter;
};
bool operator > （ const Letter& a， const Letter& b）
{
return （a.refs> b.refs）;
}
class CmpLetter
{
public ：
bool operator （）（Letter * const & pa，Letter * const & pb） const
{
return （pa-> refs> pb-> refs）;
}
};
int main（）
{
priority_queue<字母*，矢量< Letter *> ;,更大< Letter *> > PQ1;
priority_queue<字母*，矢量< Letter *> ;,CmpLetter> PQ2;
pq1.push（ new Letter（' a'， 5 ））;
pq1.push（ new Letter（' z'， 6 ））;
pq1.push（ new Letter（' 我， 10 ））;
pq1.push（ new Letter（' c'， 3 ））;
pq2.push（ new Letter（' a'， 5 ））;
pq2.push（ new Letter（' z'， 6 ））;
pq2.push（ new Letter（' 我， 10 ））;
pq2.push（ new Letter（' c'， 3 ））;
cout<< pq1<< ENDL;
while （pq1.size（）> 0）
{
pq1.top（） - > show（）;
pq1.pop（）;
}
cout<< pq2<< ENDL;
while （pq2.size（）> 0）
{
pq2.top（） - > show（）;
pq2.pop（）;
}
}
My program has a priority_queue that doesn''t work correctly ! when I pop element from that priority_queue return element with out any order!
I write two class , first class is parent of second class.
first class:
//===========================================
class treeNode
{
public:
treeNode(); //constructor
treeNode(int ); //constructor
virtual void display(void) const; //show tree object in terminal
friend bool operator <(const treeNode &, const treeNode &);
friend bool operator >(const treeNode &, const treeNode &);
int iterate;
treeNode *left;
treeNode *right;
};
treeNode::treeNode()
{
iterate = 1;
left = NULL;
right = NULL;
}
treeNode::treeNode(int i)
{
iterate = i;
left = NULL;
right = NULL;
}
bool operator <(const treeNode &a, const treeNode &b)
{
if (a.iterate < b.iterate)
{
return true;
}
else
{
return false;
}
}
bool operator >(const treeNode &a, const treeNode &b)
{
if (a.iterate > b.iterate)
{
return true;
}
else
{
return false;
}
}
void treeNode::display(void) const
{
std::cout << iterate << endl;
}
second class:
//===========================================
class letter : public treeNode
{
public:
letter(); //constructor
letter(char); //constructor
letter(char, int); //constructor
friend bool operator <(const letter &, const letter &);
friend bool operator >(const letter &, const letter &);
void display(void) const; //show letter object in terminal
char character;
};
letter::letter() : treeNode()
{
}
letter::letter(char ch) : character(ch), treeNode(1)
{
}
letter::letter(char ch, int i) : character(ch), treeNode(i)
{
}
bool operator <(const letter &a, const letter &b)
{
if (a.iterate < b.iterate)
{
return true;
}
else
{
return false;
}
}
bool operator >(const letter &a, const letter &b)
{
if (a.iterate > b.iterate)
{
return true;
}
else
{
return false;
}
}
void letter::display(void) const
{
if (character == '\n')
{
std::cout << setw(8) << "new line" << " , " << setw(6) << iterate << endl;
}
else
{
if (character == ' ')
{
std::cout << setw(8) << "space" << " , " << setw(6) << iterate << endl;
}
else
{
std::cout << setw(8) << character << " , " << setw(6) << iterate << endl;
}
}
}
//===========================================
I write below function for read a file to understand number of iteration of each character that exist in file , it work correctly and I use that in next function.
//===========================================
//read file and find number of iterate for each char
map< char, letter > countEachLetterInFile(string addOfFile)
{
string str;
letter *tempLetter;
map < char, letter > letterMap;
map < char, letter >::iterator mapIter;
ifstream fp(addOfFile, ios::in);
//check validatly of file and path of file
if (!fp)
{
cerr << "something wrong while opening file!" << endl;
exit(1);
}
//read file line by line
while (getline(fp, str))
{
str += '\n';
//move in string character by character
for (int i = 0; i < str.size(); i++)
{
mapIter = letterMap.find(str.at(i));
if (mapIter == letterMap.end())
{
tempLetter = new letter(str.at(i));
letterMap[str.at(i)] = *tempLetter;
delete[]tempLetter;
}
else
{
letterMap[str.at(i)].iterate++;
}
}
}
mapIter = letterMap.find('\n');
if (mapIter != letterMap.end())
{
letterMap['\n'].iterate--;
}
return letterMap;
}
problem occur in this function , in this function is a priority_queue of treeNode * .
I fill that with a map (output of previous function , values in map are correct and hasn''t any problem) .
//===========================================
//make huffman tree and return <char , string> and save <string , char> in file
map < char, string > makeHuffmanTree(map< char, letter > mapOfLetter)
{
treeNode *tempTreeNode;
map < char, string > huffmanCode;
map < char, letter >::iterator mapIter;
priority_queue<treeNode *, vector<treeNode *>, greater<treeNode *> > letterPriorityQueue;
for (mapIter = mapOfLetter.begin(); mapIter != mapOfLetter.end(); mapIter++)
{
letterPriorityQueue.push( new letter(mapIter->second.character, mapIter->second.iterate));
}
//
//wrong order !!
//
//
std::cout << letterPriorityQueue.size() << endl;
int size = letterPriorityQueue.size();
for (int i = 0; i < size; i++)
{
letterPriorityQueue.top()->display();
letterPriorityQueue.pop();
}
/*while (letterPriorityQueue.size() > 2)
{
}*/
return huffmanCode;
}
values in map :
http://open-mind.ir/wp-content/uploads/2015/03/11.png[^]
when I read priority_queue :
http://open-mind.ir/wp-content/uploads/2015/03/2.png[^]
解决方案
You are comparing pointers.
Try this code:
#include <iostream> #include <vector> #include <queue> using namespace std; class Letter { char c; int refs; public: Letter(char c, int refs):c(c),refs(refs){} void show(){cout << c << " " << refs << endl;} friend bool operator > (const Letter &a, const Letter & b); friend class CmpLetter; }; bool operator > (const Letter &a, const Letter & b) { return (a.refs > b.refs); } class CmpLetter { public: bool operator () ( Letter * const & pa, Letter * const & pb) const { return (pa->refs > pb->refs); } }; int main() { priority_queue< Letter *, vector<Letter*>, greater<Letter*> > pq1; priority_queue< Letter *, vector<Letter*>, CmpLetter > pq2; pq1.push(new Letter('a',5) ); pq1.push(new Letter('z',6) ); pq1.push(new Letter('i',10) ); pq1.push(new Letter('c',3) ); pq2.push(new Letter('a',5) ); pq2.push(new Letter('z',6) ); pq2.push(new Letter('i',10) ); pq2.push(new Letter('c',3) ); cout << "pq1" << endl; while (pq1.size()>0) { pq1.top()->show(); pq1.pop(); } cout << "pq2" << endl; while (pq2.size()>0) { pq2.top()->show(); pq2.pop(); } }
这篇关于我的priority_queue顺序错了的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
