C ++ STL make_heap and pop_heap not working

Question

I need to use a bunch, so I was looking for an STL file, but it doesn't seem to work, I wrote the code to explain what I mean:

#include <stdio.h> #include <stdlib.h> #include <vector> #include <algorithm> struct data { int indice; int tamanho; }; bool comparator2(const data* a, const data* b) { return (a->tamanho < b->tamanho); } int main() { std::vector<data*> mesas; data x1, x2, x3, x4, x5; x1.indice = 1; x1.tamanho = 3; x2.indice = 2; x2.tamanho = 5; x3.indice = 3; x3.tamanho = 2; x4.indice = 4; x4.tamanho = 6; x5.indice = 5; x5.tamanho = 4; mesas.push_back(&x1); mesas.push_back(&x2); mesas.push_back(&x3); mesas.push_back(&x4); mesas.push_back(&x5); make_heap(mesas.begin(), mesas.end(), comparator2); for(int i = 0 ; i < 5 ; i++) { data* mesa = mesas.front(); pop_heap(mesas.begin(),mesas.end()); mesas.pop_back(); printf("%d, %d\n", mesa->indice, mesa->tamanho); } return 0; }; 

and this is what I get:

 4, 6 2, 5 1, 3 3, 2 5, 4 

Therefore, it does not work like a heap, since the maximum element on the vector does not return correctly.

Or am I doing something wrong?

Answer 1

You need to pass comparator2 to std::pop_heap since you created the heap. Otherwise, it will use a default value less than the operator for pointers, which simply compares the values ​​of the pointer.

Answer 2

MSN's answer is correct. However, either of the two style guides can prevent this error:

• Declare the comparator to work with links, not objects, like operator< . Use vector objects, not pointers.

   bool comparator2(const data& a, const data& b) { return (a.tamanho < b.tamanho); } 

  You may need a pointer vector, in which case this does not apply.

• Use std::priority_queue (from <queue> ), which binds pop_heap and pop_back for you, remembering your comparator. This requires a comparator functor:

   struct comparator2 { bool operator()(const data& a, const data& b) { return (a.tamanho < b.tamanho); } }; std::priority_queue<data, vector<data>, comparator2> mesas; // or std::priority_queue<data, vector<data>, comparator2> mesas.push(x1); 

• The most elegant way is to make this the default comparison for data :

   struct data { int indice; int tamanho; friend bool operator<(const data& a, const data& b) { return (a.tamanho < b.tamanho); } }; std::priority_queue<data> mesas; mesas.push(x1); 

priority_queue can also accept a pre-filled unsorted container that it will copy.

Answer 3

How about std :: set

 #include <stdio.h> #include <stdlib.h> #include <vector> #include <algorithm> #include <set> struct data { // Always put constructors on. // When the constructor is finished the object is ready to be used. data(int i,int t) :indice(i) ,tamanho(t) {} int indice; int tamanho; // Add the comparator to the class. // Then you know where to look for it. bool operator<(data const& b) const { return (tamanho < b.tamanho); } }; int main() { std::set<data> mesas; // Dont declare all your variables on the same line. // One per line otherwise it is hard to read. data x1(1,3); data x2(2,5); data x3(3,2); data x4(4,6); data x5(5,4); mesas.insert(x1); mesas.insert(x2); mesas.insert(x3); mesas.insert(x4); mesas.insert(x5); // You don't actually need the variables. // You could have done it in place. mesas.insert(data(6,100)); // Use iterator to loop over containers. for(std::set<data>::iterator loop = mesas.begin(); loop != mesas.end(); ++loop) { printf("%d, %d\n", loop->indice, loop->tamanho); } return 0; }; 

Answer 4

I had a similar problem and I was able to solve it something like this:

 struct comparator2 { bool operator()(data const * const a, data const * const b) { return (a->tamanho < b->tamanho); } }; std::priority_queue<data*, std::vector<data*>, comparator2> mesas;