title: Why is using a std::multiset as a priority queue faster than using a std::priority_queue?
body: <p>I try to replace std::multiset with std::priority_queue. But I was dissapointed with the speed results. Running time of the algorithm increase by 50%...</p>
  
  <p>Here are the corresponding commands:</p>
  
  <pre><code>top() = begin();
  pop() = erase(knn.begin());
  push() = insert();
  </code></pre>
  
  <p>I am surprised with the speed of priority_queue implementation, I expected different results (better for PQ)... Conceptually, the multiset is being used as a priority queue. Why are the priority queue and the multiset have such different performance, even with <code>-O2</code>?</p>
  
  <p>Average of ten results, MSVS 2010, Win XP, 32 bit, method findAllKNN2 () (see bellow, please)</p>
  
  <pre><code>MS
  N           time [s]
  100 000     0.5
  1 000 000   8
  
  PQ
  N           time [s]
  100 000     0.8
  1 000 000   12
  </code></pre>
  
  <p>What could cause these results? No other changes of the source code have been made... Thanks for your help...</p>
  
  <p><strong>MS Implementation:</strong></p>
  
  <pre><code>template &lt;typename Point&gt;
  struct TKDNodePriority
  {
      KDNode &lt;Point&gt; *node;
      typename Point::Type priority;
  
      TKDNodePriority() : node ( NULL ), priority ( 0 ) {}
      TKDNodePriority ( KDNode &lt;Point&gt; *node_, typename Point::Type priority_ ) : node ( node_ ), priority ( priority_ ) {}
  
      bool operator &lt; ( const TKDNodePriority &lt;Point&gt; &amp;n1 ) const
      {
              return priority &gt; n1.priority;
      }
  };
  
  template &lt;typename Point&gt;
  struct TNNeighboursList
  {
      typedef std::multiset &lt; TKDNodePriority &lt;Point&gt; &gt; Type;
  };
  </code></pre>
  
  <p>Method:</p>
  
  <pre><code>template &lt;typename Point&gt;
  template &lt;typename Point2&gt;
  void KDTree2D &lt;Point&gt;::findAllKNN2 ( const Point2 * point, typename TNNeighboursList &lt;Point&gt;::Type &amp; knn, unsigned int k, KDNode &lt;Point&gt; *node, const unsigned int depth ) const
  {
      if ( node == NULL )
      {
              return;
      }
  
      if ( point-&gt;getCoordinate ( depth % 2 ) &lt;= node-&gt;getData()-&gt;getCoordinate ( depth % 2 ) )
      {
      findAllKNN2 ( point, knn, k, node-&gt;getLeft(), depth + 1 );
      }
  
      else 
      {
              findAllKNN2 ( point, knn, k, node-&gt;getRight(), depth + 1 );
      }
  
  typename Point::Type dist_q_node = ( node-&gt;getData()-&gt;getX() - point-&gt;getX() ) * ( node-&gt;getData()-&gt;getX() - point-&gt;getX() ) +
                               ( node-&gt;getData()-&gt;getY() - point-&gt;getY() ) * ( node-&gt;getData()-&gt;getY() - point-&gt;getY() );
  
  if (knn.size() == k)
  {
      if (dist_q_node &lt; knn.begin()-&gt;priority )
      {
          knn.erase(knn.begin());
          knn.insert ( TKDNodePriority &lt;Point&gt; ( node,  dist_q_node ) );
      }
  }
  
  else
  {
      knn.insert ( TKDNodePriority &lt;Point&gt; ( node,  dist_q_node ) );
  }
  
  typename Point::Type dist_q_node_straight = ( point-&gt;getCoordinate ( node-&gt;getDepth() % 2 ) - node-&gt;getData()-&gt;getCoordinate ( node-&gt;getDepth() % 2 ) ) *
                                                  ( point-&gt;getCoordinate ( node-&gt;getDepth() % 2 ) - node-&gt;getData()-&gt;getCoordinate ( node-&gt;getDepth() % 2 ) ) ;
  
  typename Point::Type top_priority =  knn.begin()-&gt;priority;
  if ( knn.size() &lt; k ||  dist_q_node_straight &lt;  top_priority )
  {
              if ( point-&gt;getCoordinate ( node-&gt;getDepth() % 2 ) &lt; node-&gt;getData()-&gt;getCoordinate ( node-&gt;getDepth() % 2 ) )
              {
          findAllKNN2 ( point, knn, k, node-&gt;getRight(), depth + 1 );
      }
  
      else
      {
          findAllKNN2 ( point, knn, k, node-&gt;getLeft(), depth + 1 );
      }
  }
  }
  </code></pre>
  
  <p><strong>PQ implementation (slower, why?)</strong></p>
  
  <pre><code>template &lt;typename Point&gt;
  struct TKDNodePriority
  {
      KDNode &lt;Point&gt; *node;
      typename Point::Type priority;
  
      TKDNodePriority() : node ( NULL ), priority ( 0 ) {}
      TKDNodePriority ( KDNode &lt;Point&gt; *node_, typename Point::Type priority_ ) : node ( node_ ), priority ( priority_ ) {}
  
      bool operator &lt; ( const TKDNodePriority &lt;Point&gt; &amp;n1 ) const
      {
              return priority &gt; n1.priority;
      }
  };
  
  
  template &lt;typename Point&gt;
  struct TNNeighboursList
  { 
      typedef std::priority_queue&lt; TKDNodePriority &lt;Point&gt; &gt; Type;
  };
  </code></pre>
  
  <p>Method:</p>
  
  <pre><code>template &lt;typename Point&gt;
  template &lt;typename Point2&gt;
  void KDTree2D &lt;Point&gt;::findAllKNN2 ( const Point2 * point, typename TNNeighboursList &lt;Point&gt;::Type &amp; knn, unsigned int k, KDNode &lt;Point&gt; *node, const unsigned int depth ) const
  {
  
      if ( node == NULL )
      {
              return;
      }
  
      if ( point-&gt;getCoordinate ( depth % 2 ) &lt;= node-&gt;getData()-&gt;getCoordinate ( depth % 2 ) )
      {
      findAllKNN2 ( point, knn, k, node-&gt;getLeft(), depth + 1 );
      }
  
      else 
      {
              findAllKNN2 ( point, knn, k, node-&gt;getRight(), depth + 1 );
      }
  
  typename Point::Type dist_q_node = ( node-&gt;getData()-&gt;getX() - point-&gt;getX() ) * ( node-&gt;getData()-&gt;getX() - point-&gt;getX() ) +
                               ( node-&gt;getData()-&gt;getY() - point-&gt;getY() ) * ( node-&gt;getData()-&gt;getY() - point-&gt;getY() );
  
  if (knn.size() == k)
  {
      if (dist_q_node &lt; knn.top().priority )
      {
          knn.pop();
  
          knn.push ( TKDNodePriority &lt;Point&gt; ( node,  dist_q_node ) );
      }
  }
  
  else
  {
      knn.push ( TKDNodePriority &lt;Point&gt; ( node,  dist_q_node ) );
  }
  
  typename Point::Type dist_q_node_straight = ( point-&gt;getCoordinate ( node-&gt;getDepth() % 2 ) - node-&gt;getData()-&gt;getCoordinate ( node-&gt;getDepth() % 2 ) ) *
                                                  ( point-&gt;getCoordinate ( node-&gt;getDepth() % 2 ) - node-&gt;getData()-&gt;getCoordinate ( node-&gt;getDepth() % 2 ) ) ;
  
  typename Point::Type top_priority =  knn.top().priority;
  if ( knn.size() &lt; k ||  dist_q_node_straight &lt;  top_priority )
  {
              if ( point-&gt;getCoordinate ( node-&gt;getDepth() % 2 ) &lt; node-&gt;getData()-&gt;getCoordinate ( node-&gt;getDepth() % 2 ) )
              {
          findAllKNN2 ( point, knn, k, node-&gt;getRight(), depth + 1 );
      }
  
      else
      {
          findAllKNN2 ( point, knn, k, node-&gt;getLeft(), depth + 1 );
      }
  }
  }
  </code></pre>