title: C++ priority_queue pop() and top() discrepancy
body: <p>I'm having a hard time understanding why a priority_queue pop() call is not removing the top() element. The priority queue has a custom comparison structure so that lower numbers have higher priority (and therefore should be retrieved with top()).</p>
  
  <p>The debugging text (below) shows the top() element remains the same even after a pop().</p>
  
  <p>Even if we make the assumption that the comparison structure is somehow wrong, top() should change after pop(), right? What else can I look at to understand why this is happening. The priority_queue code itself is a little inscrutable to me at the moment...</p>
  
  <p>Note that this behavior is not consistent. There are other times when top() changes after a pop().</p>
  
  <p>Any ideas? Thanks!</p>
  
  <p>Debugging text (edited with top() shown before push():</p>
  
  <pre><code>size BEFORE push(): 1 TOP: [1488994840.745965281:0106996627] APPENDING: [1488994840.746157190:0106996627]
  size  AFTER push(): 2 TOP: [1488994840.745965281:0106996627]
  size BEFORE  pop(): 2 TOP: [1488994840.745965281:0106996627]
  size  AFTER  pop(): 1 TOP: [1488994840.745965281:0106996627] // &lt;- same top()!!
  </code></pre>
  
  <p>Where I push() to the priority_queue:</p>
  
  <pre><code>void Replica::appendPrepareOK(const PrepareOK &amp;prepareOK) {
      PendingPrepare tmpPrepareOK = prepareOK;
  
      lock_guard&lt;mutex&gt; lck (this-&gt;lockPendingPrepare);
  
      this-&gt;logprint(3, "size BEFORE push(): " + to_string(this-&gt;pendingPrepare.size()) + " APPENDING: " + to_string(tmpPrepareOK));
  
      this-&gt;pendingPrepare.push(tmpPrepareOK);
  
      this-&gt;logprint(3, "size  AFTER push(): " + to_string(this-&gt;pendingPrepare.size()) + " TOP: " + to_string(this-&gt;pendingPrepare.top()));
  }
  </code></pre>
  
  <p>Where I pop() from the priority_queue:</p>
  
  <pre><code>void Replica::sendPendingCmds() {
      ClockCommand *prepareCmd = NULL;
      PrepareOK *prepareOKCmd = NULL;
      Broadcast *broadcastCmd = NULL;
  
      {
          lock_guard&lt;mutex&gt; lck(this-&gt;lockPendingPrepare);
  
          if (! this-&gt;pendingPrepare.empty()) {
              this-&gt;logprint(3, "size BEFORE pop(): " + to_string(this-&gt;pendingPrepare.size()) + " TOP: " + to_string(this-&gt;pendingPrepare.top()));
  
              PendingPrepare firstCommand = this-&gt;pendingPrepare.top();
              this-&gt;pendingPrepare.pop();
  
              if (! this-&gt;pendingPrepare.empty()) {
                  this-&gt;logprint(3, "size  AFTER pop(): " + to_string(this-&gt;pendingPrepare.size()) + " TOP: " + to_string(this-&gt;pendingPrepare.top()));
              }
              else {
                  this-&gt;logprint(3, "size  AFTER pop(): " + to_string(this-&gt;pendingPrepare.size()));
              }
  </code></pre>
  
  <p>Definition of the priority_queue:</p>
  
  <pre><code>typedef priority_queue&lt;PendingPrepare, deque&lt;PendingPrepare&gt;, PendCompare&gt; pendQueue;
  </code></pre>
  
  <p>Custom PendCompare comparison class:</p>
  
  <pre><code>class PendCompare {
  public:
      bool operator() (const PendingPrepare &amp;a, const PendingPrepare &amp;b) const {
          if (a.prepareOK != NULL) {
              if (b.prepareOK != NULL) { return a.prepareOK-&gt;tsOK &gt; b.prepareOK-&gt;tsOK; }
              else if (b.prepare != NULL) { return a.prepareOK-&gt;tsOK &gt; b.prepare-&gt;ts; }
          }
          else if (a.prepare != NULL) {
              if (b.prepareOK != NULL) { return a.prepare-&gt;ts &gt; b.prepareOK-&gt;tsOK; }
              else if (b.prepare != NULL) { return a.prepare-&gt;ts &gt; b.prepare-&gt;ts; }
          }
  
          return false;
      }
  };
  </code></pre>
  
  <p>Relevant parts of the PendingPrepare struct:</p>
  
  <pre><code>struct PendingPrepare {
      ClockCommand* prepare = NULL;
      PrepareOK* prepareOK = NULL;
  
      void operator=(const PrepareOK &amp;b) {
          this-&gt;prepareOK = new PrepareOK(b);
      }
  };
  </code></pre>