size（）関数がサブクラス化するときに乱れるpriority_queue 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としてインスタンス化されたとき、単一の要素がポップされた後に空（）が真であることを示しません。

Answer 1

undefined behaviorへようこそ。 popに電話すると、基になるベクトルのpop_backが呼び出されます。表101から、C++ 14標準でのオプションのシーケンスコンテナ操作a.pop_back()はa.empty()が必要ですfalseとなります。キューが空のときにpopに電話すると、その要件に違反します。

それ以降に表示されるものは、その未定義の動作の成果物であり、得られた値の入手方法を推論することはできません。