Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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
{
public:
    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() );
        }

private:
    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();
            c.pop();
        }
        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;
}
share|improve this question

migrated from stackoverflow.com Dec 3 '12 at 13:53

This question came from our site for professional and enthusiast programmers.

    
flipped_compare is actually called std::more. –  Barnabas Szabolcs Dec 1 '12 at 16:08
    
@BarnabasSzabolcs: What is std::more? Do you have a reference because I can't find it. –  Blastfurnace Dec 1 '12 at 16:30
1  
@Blastfurnace: I think he is talking about std::greater. –  Mankarse Dec 1 '12 at 18:32
    
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 –  Barnabas Szabolcs Dec 2 '12 at 3:48

1 Answer 1

up vote 4 down vote accepted

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.
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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