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时违反了该要求。

之后你看到的任何东西都是未定义行为的产物，你无法推断出你得到的值。