初始化STL優先隊列

我仍然對STL中的優先隊列感到困惑。這裏是我想實現的目標，比如說：我有一個名爲Record的結構，它包含一個字符串字和一個int計數器。例如：我有很多這些記錄（在示例程序中，只有5個），現在我想保留前N個記錄（在示例中，3）。初始化STL優先隊列

現在我知道我可以在記錄超載運營<，並把所有的記錄在一個載體，然後初始化像priority_queue：

priority_queue< Record, vector<Record>, less<Record> > myQ (myVec.begin(),myVec.end());

但是，我的理解，這是不容易控制矢量myVec的大小，因爲它沒有按照我的意願排序。

我真的不明白，爲什麼下面不能工作：

struct Record 
{ 
    string word; 
    int count; 
    Record(string _word, int _count): word(_word), count(_count) { }; 
    /* 
     bool operator<(const Record& rr) 
     { 
      return this->count>rr.count; 
     } 
    */ 
    bool operator() (const Record& lhs, const Record& rhs) 
    { 
     return lhs.count>rhs.count; 
    } 
}; 

void test_minHeap() 
{ 
    priority_queue<Record> myQ; 
    Record arr_rd[] = {Record("William", 8), 
         Record("Helen", 4), 
         Record("Peter", 81), 
         Record("Jack", 33), 
         Record("Jeff", 64)}; 
    for(int i = 0; i < 5; i++) 
    { 
     if(myQ.size() < 3) 
     { 
      myQ.push(arr_rd[i]); 
     } 
     else 
     { 
      if(myQ.top().count > arr_rd[i].count) 
       continue; 
      else 
      { 
       myQ.pop(); 
       myQ.push(arr_rd[i]); 
      } 
     } 
    } 

    while(!myQ.empty()) 
    { 
     cout << myQ.top().word << "--" << myQ.top().count << endl; 
     myQ.pop(); 
    } 
}

編輯：感謝您的輸入，現在我知道了working.However，我寧願如果有人可以解釋爲什麼第一個版本的運算符<過載工作，第二個（註釋掉）將無法工作，並有一長串編譯器錯誤。

friend bool operator< (const Record& lhs, const Record& rhs) 
{ 
    return lhs.count>rhs.count; 
} 

/* 
bool operator<(const Record& rRecord) 
{ 
    return this->count>rRecord.count; 
} 
    */

來源

2011-10-27 WilliamLou

你實現你沒有'operator'''重載'Record' - 它被註釋掉了。 –

，因爲我不想在我的帖子中選擇第一種方式。我重載operator（），而不是 – WilliamLou

'operator（）'是函數調用操作符，並且您重載了它，使其變爲零。如果您想訂購對象，請重載適當的比較操作符。 –

std::priority_queue不能神奇地知道如何對元素進行排序。你必須告訴它如何去做。這樣做的方法是給priority_queue一個仿函數類型，當用兩個對象調用函數時，返回第一個參數是否「小於」第二個參數，但是您想要定義它。此仿函數是priority_queue的模板參數。

默認參數是std::less<type>，這要求type（您放入隊列中）的重載operator<。如果沒有，那麼你必須提供一個，否則你必須提供一個適當的比較函子。

例如：

struct Comparator 
{ 
    bool operator()(const Record& lhs, const Record& rhs) 
    { 
    return lhs.count>rhs.count; 
    } 
}; 

std::priority_queue<Record, std::vector<Record>, Comparator> myQ;

不只有超負荷的工作Record的原因是因爲你沒有告訴priority_queue，這是比較。此外，用於比較的類型需要默認構造，以便priority_queue可以隨意創建和銷燬對象。

雖然說實話，我不知道爲什麼你不要把它們粘在std::set如果你想排序它們。或者在std::vector的項目上運行std::sort。

來源

2011-10-27 07:17:50

您的代碼確實工作，有兩個小的變化：中Record::operator<()

取消註釋的定義，因爲這是由優先級隊列的默認比較需要的。
將聲明更改爲bool operator<(const Record &) const（請注意額外的const），因爲優先隊列必須使用對const對象的引用進行比較。

另外，聲明它作爲一個自由函數，類定義之外：

bool operator<(const Record &l, const Record &r) {return l.count > r.count;}

或定義自己的仿函數，並且規定，在適當的模板參數：

struct CompareRecords 
{ 
    bool operator()(const Record &l, const Record &r) {return l.count > r.count;} 
}; 

typedef priority_queue<Record, vector<Record>, CompareRecords> RecordQueue;

來源

2011-10-27 07:36:28

初始化STL優先隊列

回答

相關問題