Class derived from std::priority_queue does'nt use comparator predicate / template parameters

Question

I am not very familiar with deriving from templates, see the following:

class BCQueue_;

template<typename T,
         typename Sequence = std::vector<T>,
         typename Compare = std::less<typename Sequence::value_type> >
class FixedPriorityQueue : public std::priority_queue<T> {
    friend class BCQueue_; // to access private member maxSize_

public:

    FixedPriorityQueue(unsigned int maxSize) 
    : maxSize_(maxSize) {}

    // smallest item will be dropped if queue id full
    void insertWithOverflow(const T& x) {
        // ...
        this->push(x);
        // ...
    }
private:
    FixedPriorityQueue() {}

    const unsigned int maxSize_;
};

class ScoreLessThan : public std::binary_function<CCandidate *, CCandidate *, bool> {
public:

    bool operator()(
        const CCandidate * a, const CCandidate * b) const {
        std::wcout << a->score << " < " << b->score << std::endl;
        return a->score > b->score;
    }
};

class BCQueue_ : public FixedPriorityQueue<
    CCandidate *, std::vector<CCandidate *>, ScoreLessThan> {
public:
    BCQueue_(size_t maxSize)
    : FixedPriorityQueue(maxSize)   {}

    bool willInsert(float score) {
        return size() < maxSize_ || top()->score < score;
    }
};

BSQueue bc(20);
bs.insertWithOverflow(new CCandidate( ... ));
// ...

In the FixedPriorityQueue I have a method called insertWithOverflow that inserts elements (if the queue is full) by removing the smallest element. To keep things a little separated, I derive from FixedPriorityQueue. Basically all works fine, except that the comparator ScoreLessThan seems to be never called. When I top/pop the elements, they are not in the order (of the score) as I would expect them.

So that might be more a syntax/usage problem, please bear with me, but I could not find any answer to solve the question. I though by defining the template parameters all would work out. What I am missing here?

Thanks for the help!

Why did you choose inheritance? By doing so, you allow users to call the regular insert methods and overflow (actually grow the container), and you also might run into other issues, as `priority_queue` was not designed to be a base class. Prefer composition (or at the very least private inheritance) — David Rodríguez - dribeas, Apr 23 '13 at 15:18
@DavidRodríguez-dribeas: I know it is not very clean nor stable yet. Actually this class is used within another class, just by that enclosing class. But I will keep your comment in mind when I work things out. Thanks for the hint! — Andreas W. Wylach, Apr 23 '13 at 15:30

score 1 · Accepted Answer · edited May 23 '17 at 11:50

Here is the problem.

template<typename T,
         typename Sequence = std::vector<T>,
         typename Compare = std::less<typename Sequence::value_type> >
class FixedPriorityQueue : public std::priority_queue<T> {
//               Wrong base class ^^^^^^^^^^^^^^^^^^^^^^

Any FixedPriorityQueue<A,B,C> derives from std::priority_queue<A,(default),(default)>

Change it to have the base class use the same template arguments.

template<typename T,
         typename Sequence = std::vector<T>,
         typename Compare = std::less<typename Sequence::value_type> >
class FixedPriorityQueue : public std::priority_queue<T,Sequence,Compare> {

Warning: Some folks - wise from experience - will tell you never to derive from a standard library container class. (Read why)

In the interest of giving you some leeway, I will only warn you not to add an explicit destructor to your class or add member variables that have non-trivial destructors. Since your only member is an unsigned int, the code as shown will not have problems.

Yes, that was it! Thank you, I know it was something simple! — Andreas W. Wylach, Apr 23 '13 at 15:19
All i have in the FixedPriorityClass is this method called `insertWithOverflow`, nothing else. I define the queue with a certain size and just want the top score inserted elements. Up to now I can not think of a major problem. This class is only used within another class, in other words, it is a private nested class. Also David mentioned his concerns above, I will keep that in mind! Thank u guys for the lesson! — Andreas W. Wylach, Apr 23 '13 at 15:36

Class derived from std::priority_queue does'nt use comparator predicate / template parameters

1 Answers1