C++ STL make_heap和pop_heap不工作

Question

我需要使用堆，所以我搜索有關STL的一個，但它似乎沒有工作，我寫了一些代碼來說明我的意思：

#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; 
}; 

，這就是我得到：

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

所以它不工作作爲一個堆，因爲沒有被返回的向量的最大元素權利。

或者我做錯了什麼？

Answer 1

您需要將comparator2傳遞給std::pop_heap，因爲這是您創建堆的方式。否則，它將爲指針使用默認的小於運算符，它只是比較指針值。

Answer 2

怎麼樣的std ::設置

#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 3

MSN的答案是正確的。然而，無論是一對夫婦的風格指南可以防止此錯誤：

• 聲明比較器上的參考，而不是對象的工作，爲operator<會。使用對象的vector，而不是指針。

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

  你可能真的需要指針的載體，在這種情況下，這並不適用。

• 使用std::priority_queue（從<queue>），它聯繫在一起爲你pop_heap和pop_back，記住你比較。這需要一個仿函數比較：

  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); 
  

• 最優雅的方式是讓本作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還可以採取預充式無序的容器，它會複製。

Answer 4

我有一個類似的問題，並能像這樣的東西來解決這個問題：

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;