子类化 priority_queue c++ 时 size() 函数搞砸了

size() function messing up when subclassing priority_queue c++

我已经修改了这个 Whosebug 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() 为真。

欢迎来到 undefined behavior 的世界。当您调用 pop 时,它会在基础向量上调用 pop_back。来自 Table 101 — C++14 标准中的可选序列容器操作 a.pop_back() 要求 a.empty() 应为 false。当队列为空时调用 pop 就违反了该要求。

在那之后你看到的任何东西都是那个未定义行为的产物,你无法推断你是如何得到你得到的值的。