I was searching for a free implementation of a "bounded" priority queue. The algorithm has been discussed many times on Stack Overflow. I took a shot and wrote a STL-like bounded_priority_queue class (which implements the most efficient algorithm using a priority_queue with a "flipped" compare as the underlying container).

I do have some questions:

  1. Any comments on my interface? I couldn't think of anything more fine-grained than pop_all(). I provided a constructor that takes in an iterator range, since std::partial_sort can only be called using random access iterators.

  2. Any comments on my implementation? I tried to mimic the style of the STL that comes with MSVC. (It's not my natural style.)

  3. Is flipped_compare part of the STL? It feels like it should be there somewhere.

  4. Is there any way to more succinctly implement the dispatch for bidir & random_access iterators? I couldn't come up with any way without explicit defining partial specializations of _pop_all() for both iterator categories.

  5. Any reason why std::priority_queue defines the _Container template parameter before the _Pr template parameter? As a user, I would probably want specialize _Pr more frequently than _Container. (I kept the same order, but I don't like it.)

Here's the code (feel free to copy):

#include <queue>
#include <iterator>

template < typename _Ty, typename _Pr = std::less<_Ty> >
struct flipped_compare {
    flipped_compare() : comp() {}
    explicit flipped_compare(const _Pr& _Pred) : comp(_Pred) {}
    bool operator()(const _Ty& l, const _Ty& r) { return comp(r,l); }
    _Pr comp;

template < typename _Ty, typename _Container = std::vector<_Ty>,
    typename _Pr = std::less<_Ty> >
class bounded_priority_queue
    typedef _Ty value_type;
    typedef typename _Container::size_type size_type;

    explicit bounded_priority_queue(size_type _Max_size)
        : max_sz(_Max_size) {}

    bounded_priority_queue(size_type _Max_size, const _Pr& _Pred)
        : c( flipped_compare<_Ty,_Pr>(_Pred) ), max_sz(_Max_size) {}

    template <typename _InIt>
    bounded_priority_queue(size_type _Max_size, _InIt _First, _InIt _Last)
        : max_sz(_Max_size)
            for (; _First != _Last; ++_First) push( *_First );

    template <typename _InIt>
    bounded_priority_queue(size_type _Max_size, _InIt _First,
        _InIt _Last, _Pr _Pred)
        : c( flipped_compare<_Ty,_Pr>(_Pred) ), max_sz(_Max_size)
            for (; _First != _Last; ++_First) push( *_First );

    size_type max_size() const { return max_sz; }

    size_type size() const { return c.size(); }

    void push(const value_type& _Val)
        if ( size() < max_size() ) c.push(_Val);
        else if ( comp(c.top(), _Val) ) { c.pop(); c.push(_Val); }

    template <typename _OutIt>
    void pop_all(_OutIt _Dest)
        _pop_all( _Dest,
            typename std::iterator_traits<_OutIt>::iterator_category() );

    template <typename _OutIt, typename _Tag>
    void _pop_all(_OutIt _Dest, _Tag)
        std::vector<_Ty> tmp( size() );
        _pop_all2( tmp.begin() );
        std::copy( tmp.begin(), tmp.end(), _Dest );

    template <typename _OutIt>
    void _pop_all(_OutIt _Dest, std::bidirectional_iterator_tag)
        _pop_all2( _Dest );

    template <typename _OutIt>
    void _pop_all(_OutIt _Dest, std::random_access_iterator_tag)
        _pop_all2( _Dest );

    template <typename _BidIt>
    void _pop_all2(_BidIt _Dest)
        _BidIt _First = _Dest;
        while ( !c.empty() ) {
            *_Dest++ = c.top();
        std::reverse( _First, _Dest );

    std::priority_queue< _Ty, _Container, flipped_compare<_Ty, _Pr> > c;
    _Pr comp;
    size_type max_sz;

#include <list>
#include <iostream>

int main (int argc, char* argv[])
    int K = 20, N = 500;
    std::list<int> l;
    std::generate_n( std::back_inserter(l), N, &std::rand );
    bounded_priority_queue<int> q( K, l.begin(), l.end() );
    q.pop_all( std::ostream_iterator<int>( std::cout, " " ) );
    return 0;
  • \$\begingroup\$ flipped_compare is actually called std::more. \$\endgroup\$
    – Barnabas Szabolcs
    Dec 1, 2012 at 16:08
  • \$\begingroup\$ @BarnabasSzabolcs: What is std::more? Do you have a reference because I can't find it. \$\endgroup\$ Dec 1, 2012 at 16:30
  • 1
    \$\begingroup\$ @Blastfurnace: I think he is talking about std::greater. \$\endgroup\$
    – Mankarse
    Dec 1, 2012 at 18:32
  • \$\begingroup\$ oops, that's embarrassing. I was so sure because I happened to use it before, and I was so wrong telling std::more. :( It is std::greater. Sorry \$\endgroup\$
    – Barnabas Szabolcs
    Dec 2, 2012 at 3:48
  • \$\begingroup\$ why do you need flipped_compare, shouldn't it be just std::less for a priority queue , which has the maximum element as top() ? and is pop(),push() if the element to insert is smaller < top(), the most efficient way?, can that not be combined somehow? \$\endgroup\$
    – Gabriel
    Jun 16, 2015 at 9:51

1 Answer 1


First of all: names starting with an underscore followed by a capital letter are reserved for the implementation. You may not use them. Ever.

You might also want to specify whether you're interested in all advice, or only that relevant to C++03; I don't see much C++11 could do here, but it's generally an important distinction.

Now, comments:

  • Why not have flipped_compare::operator() be const? Not very significant, but looks like it'd work.
  • I suggest using std::less<typename _Container::value_type> as your default _Pr, as that's what std::priority_queue does.
  • The constructors should probably be implemented in terms of std::for_each or somesuch.
  • Your indentation is inconsistent.
  • Swap is a fairly important omission, in my opinion.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.