c ++将指针推入指针优先级队列会导致立即出现valgrind错误
c++ pushing pointer onto pointer priority queue causes immediate valgrind errors
我正在使用 C++ 实现 Huffman 代码,但是在构造过程中将指针推送到 class 指针的优先级队列导致如下所示的几种 valgrind 错误类型:
==1158== at 0x40508E: void std::__push_heap<__gnu_cxx::__normal_iterator<Node**, std::vector<Node*, std::allocator<Node*> > >, long, Node*, nodeCompare>(__gnu_cxx::__normal_iterator<Node**, std::vector<Node*, std::allocator<Node*> > >, long, long, Node*, nodeCompare) (stl_heap.h:182)
==1158== by 0x4034B5: void std::push_heap<__gnu_cxx::__normal_iterator<Node**, std::vector<Node*, std::allocator<Node*> > >, nodeCompare>(__gnu_cxx::__normal_iterator<Node**, std::vector<Node*, std::allocator<Node*> > >, __gnu_cxx::__normal_iterator<Node**, std::vector<Node*, std::allocator<Node*> > >, nodeCompare) (stl_heap.h:221)
==1158== by 0x4027AB: std::priority_queue<Node*, std::vector<Node*, std::allocator<Node*> >, nodeCompare>::push(Node* const&) (stl_queue.h:499)
==1158== by 0x40177A: HuffmanCode::HuffmanCode(std::map<char, int, std::less<char>, std::allocator<std::pair<char const, int> > >) (huffmanCodes.cpp:117)
==1158== by 0x401F78: main (huffmanCodes.cpp:188)
==1158== Uninitialised value was created by a stack allocation
==1158== at 0x404EF3: void std::__push_heap<__gnu_cxx::__normal_iterator<Node**, std::vector<Node*, std::allocator<Node*> > >, long, Node*, nodeCompare>(__gnu_cxx::__normal_iterator<Node**, std::vector<Node*, std::allocator<Node*> > >, long, long, Node*, nodeCompare) (stl_heap.h:178)
这是我认为与问题相关的代码:
struct nodeCompare{
bool operator()(Node const& n1, Node const& n2){
return n1.getFreq() > n2.getFreq();
}
};
// huffman code constructor, takes in character frequency map
HuffmanCode::HuffmanCode(map<char, int> m){
// creates priority_queue, creates leafs and adds them to the queue
priority_queue<Node*, vector<Node*>, nodeCompare> PQ;
for(auto item: m){
Node* temp = new Node(item.first, item.second, true);
PQ.push(temp); // causes error
}
// builds rest of tree upward until there is only a single element left (the root)
while(PQ.size() > 1){
Node* temp = new Node(false);
Node* left = PQ.top(); // causes error
PQ.pop();
Node* right = PQ.top();
PQ.pop();
temp->setLChild(left);
temp->setRChild(right);
temp->setFreq(left->getFreq() + right->getFreq());
PQ.push(temp); // causes error
}
项目中在此下方有更多代码,但我认为这是导致问题的原因。任何 help/insight 将不胜感激。
应该在节点比较中使用指针
struct nodeCompare{
bool operator()(Node* n1, Node* n2){
return n1->getFreq() > n2->getFreq();
}
};
我正在使用 C++ 实现 Huffman 代码,但是在构造过程中将指针推送到 class 指针的优先级队列导致如下所示的几种 valgrind 错误类型:
==1158== at 0x40508E: void std::__push_heap<__gnu_cxx::__normal_iterator<Node**, std::vector<Node*, std::allocator<Node*> > >, long, Node*, nodeCompare>(__gnu_cxx::__normal_iterator<Node**, std::vector<Node*, std::allocator<Node*> > >, long, long, Node*, nodeCompare) (stl_heap.h:182)
==1158== by 0x4034B5: void std::push_heap<__gnu_cxx::__normal_iterator<Node**, std::vector<Node*, std::allocator<Node*> > >, nodeCompare>(__gnu_cxx::__normal_iterator<Node**, std::vector<Node*, std::allocator<Node*> > >, __gnu_cxx::__normal_iterator<Node**, std::vector<Node*, std::allocator<Node*> > >, nodeCompare) (stl_heap.h:221)
==1158== by 0x4027AB: std::priority_queue<Node*, std::vector<Node*, std::allocator<Node*> >, nodeCompare>::push(Node* const&) (stl_queue.h:499)
==1158== by 0x40177A: HuffmanCode::HuffmanCode(std::map<char, int, std::less<char>, std::allocator<std::pair<char const, int> > >) (huffmanCodes.cpp:117)
==1158== by 0x401F78: main (huffmanCodes.cpp:188)
==1158== Uninitialised value was created by a stack allocation
==1158== at 0x404EF3: void std::__push_heap<__gnu_cxx::__normal_iterator<Node**, std::vector<Node*, std::allocator<Node*> > >, long, Node*, nodeCompare>(__gnu_cxx::__normal_iterator<Node**, std::vector<Node*, std::allocator<Node*> > >, long, long, Node*, nodeCompare) (stl_heap.h:178)
这是我认为与问题相关的代码:
struct nodeCompare{
bool operator()(Node const& n1, Node const& n2){
return n1.getFreq() > n2.getFreq();
}
};
// huffman code constructor, takes in character frequency map
HuffmanCode::HuffmanCode(map<char, int> m){
// creates priority_queue, creates leafs and adds them to the queue
priority_queue<Node*, vector<Node*>, nodeCompare> PQ;
for(auto item: m){
Node* temp = new Node(item.first, item.second, true);
PQ.push(temp); // causes error
}
// builds rest of tree upward until there is only a single element left (the root)
while(PQ.size() > 1){
Node* temp = new Node(false);
Node* left = PQ.top(); // causes error
PQ.pop();
Node* right = PQ.top();
PQ.pop();
temp->setLChild(left);
temp->setRChild(right);
temp->setFreq(left->getFreq() + right->getFreq());
PQ.push(temp); // causes error
}
项目中在此下方有更多代码,但我认为这是导致问题的原因。任何 help/insight 将不胜感激。
应该在节点比较中使用指针
struct nodeCompare{
bool operator()(Node* n1, Node* n2){
return n1->getFreq() > n2->getFreq();
}
};