subclassing priority_queue時size（）函數搞亂了C++

Question

我已經修改了這個stackoverflow的代碼q/a來適應我的需要。 How to make STL's priority_queue fixed-size。它工作得很好，但隊列空時隊列大小有問題。在正常的priority_queue中，我注意到pop（）即使在隊列爲空時也會繼續工作，但隊列仍會註冊爲空。我想這是最好的功能，我可以希望不嚴重修改stl priority_queue代碼。這是我修改priority_queue：

#include <queue> 
#include <algorithm> 

template<class T, 
       class Container = std::vector<T>, 
       class Compare = std::less<typename Container::value_type> 
> class fixed_priority_queue : public std::priority_queue<T,Container,Compare> { 
    public : 
    //FIXME pass comparator as function pointer 
    fixed_priority_queue(unsigned int size) : 
     std::priority_queue<T,Container,Compare>(),fixed_size(size) {} 
    void inline push(const T &x) { 
     // If we've reached capacity, find the FIRST smallest object and replace 
     // it if 'x' is larger' 
     if(this->size() == fixed_size) 
     { 
     // 'c' is the container used by priority_queue and is a protected member. 
     std::vector<Msg*>::iterator beg = this->c.begin(); 
     std::vector<Msg*>::iterator end = this->c.end(); 
     std::vector<Msg*>::iterator min = std::min_element(beg, end, 
      this->comp); 
     if(x > *min) 
     { 
      *min = x; 
      // Re-make the heap, since we may have just invalidated it. 
      std::make_heap(beg, end); 
     } 
     } 
     // Otherwise just push the new item. 
     else   
     { 
     //fixed_priority_queue<T,Container,Compare>::push(x); 
     std::priority_queue<T,Container,Compare>::push(x); 
     }  
    } 
    private : 
    //FIXME pass comparator as function pointer 
     fixed_priority_queue() : std::priority_queue<T,Container,Compare>() 
     {fixed_size = 10;} // Default size 10.  
     const unsigned int fixed_size; 
     // Prevent heap allocation 
     void * operator new (size_t); 
     void * operator new[] (size_t); 
     void operator delete (void *); 
     void operator delete[] (void *); 
}; 

這裏是我的自定義比較功能：

class MsgCmp { 
    public: 
    bool operator() (const Msg *m1, const Msg *m2) const { 
     return m1->get_type() < m2->get_type(); 
    } 
}; 

我把它從另一個文件如下：

// Construct with fixed_size parameter 
    fixed_priority_queue <Msg*,vector<Msg*>,MsgCmp> q(2); 

    q.push(&smsg); 
    q.push(&dmsg); 

    cout << "queue size: " << q.size() << endl; 
    cout <<q.top()->repr()<<endl; 
    cout << "popping top element" << endl; 
    q.pop(); 
    cout << "queue size: " << q.size() << endl; 
    cout <<q.top()->repr()<<endl; 
    cout << "popping top element" << endl; 
    q.pop(); 
    cout << "empty?\t" << q.empty() << endl; 
    cout << "queue size: " << q.size() << endl; 

    cout << "pushing dynamic element" << endl; 
    q.push(&new_dmsg); 
    cout << "pushing dynamic element" << endl; 
    q.push(&dmsg); 
    cout << "pushing static element" << endl; 
    q.push(&smsg); 

    cout << "queue size: " << q.size() << endl; 
    cout <<q.top()->repr()<<endl; 
    cout << "popping top element" << endl; 
    q.pop(); 
    cout << "empty?\t" << q.empty() << endl; 
    cout << "queue size: " << q.size() << endl; 
    cout <<q.top()->repr()<<endl; 
    cout << "popping top element" << endl; 
    q.pop(); 
    cout << "empty?\t" << q.empty() << endl; 
    cout << "queue size: " << q.size() << endl; 
    cout <<q.top()->repr()<<endl; 
    cout << "popping top element" << endl; 
    q.pop(); 
    cout << "empty?\t" << q.empty() << endl; 
    cout << "queue size: " << q.size() << endl; 

這裏是輸出。我用'＃'註釋輸出。我的隊列排序按類型，與具有較高優先級類型：

queue size: 2 
type 1 
7,5,3,1,3,9,5, 
popping top element 
queue size: 1 
type 0 
5,3,1,3,9,5,7,4,8,0, 
popping top element 
empty? 1 
queue size: 0 
pushing dynamic element # type 1 
pushing dynamic element # type 1 
pushing static element # type 0 
# so far the output is consistent with the intended functionality 
queue size: 2 
type 0 # As you can see, the sorting is no longer correct. 
# Maybe this is related, maybe not. 
5,3,1,3,9,5,7,4,8,0, 
popping top element 
empty? 0 
queue size: 1 
type 1 
7,5,3,1,3,9,5, 
popping top element 
empty? 1 
queue size: 0 
# Queue is empty, but still showing top element. This is also true of 
# STL priority_queues, though. 
type 1 
7,5,3,1,3,9,5, 
popping top element 
# For some reason, the queue is no longer empty. 
empty? 0 
# Psychobilly freakout. 
queue size: 18446744073709551615 

這樣看來，如果隊列的大小參數以某種方式給予垃圾值後隊列爲空。可能與此有關，我的隊列在實例化爲1時，在彈出單個元素後不會顯示empty（）爲真。

Answer 1

歡迎來到undefined behavior的世界。當您致電pop時，它會調用pop_back作爲底層向量。從表101 - C++ 14標準a.pop_back()中的可選順序容器操作要求a.empty()應爲false。當隊列爲空時，您調用pop時違反了該要求。

之後你看到的任何東西都是未定義行爲的產物，你無法推斷出你得到的值。