CODEWITHSUNDEEP
c++data-structuresstructstdpriority-queue
scheiflo
scheiflo

Reputation: 130

std::priority_queue complex types?

I want to use a std::priority_queue with complex types:

typedef struct
{
uint8_t data;
    uint64_t moredata;
}myData;

typedef struct
{
    boost::mutex someQueueLock;
    std::priority_queue<myData> myQueue; //does not work
}

I don't want to use a queue full of pointers (priority_queue) because the pointers can get invalid.

Is this even possible? Or should I use another std container?

Upvotes: 0

Views: 555

Answers (2)

Alex Shtoff
Alex Shtoff

Reputation: 2640

You need to define your own comparison function, so that the priority_queue will know which items have higher priority.

bool MyCompare(const myData& left, const myData& right)
{
    // todo: return true if left has higher priority than right
}

std::priority_queue<myData, std::vector<myData>, MyCompare> queue;

Upvotes: 1

billz
billz

Reputation: 45410

std::priority_queue uses operator< to sort elements by default, it requires elements to be strict weak ordered

You need to define operator< function for myData type

bool operator<(const myData& lhs, const myData& rhs)
{
    return lhs.data < rhs.data;
}

§ 23.6.4.1 Class template priority_queue

Any sequence container with random access iterator and supporting operations front(), push_back() and pop_back() can be used to instantiate priority_queue. In particular, vector (23.3.6) and deque (23.3.3) can be used. Instantiating priority_queue also involves supplying a function or function object for mak- ing priority comparisons; the library assumes that the function or function object defines a strict weak ordering (25.4).

§ 25.4

All the operations in 25.4 have two versions: one that takes a function object of type Compare and one that uses an operator<.

Upvotes: 2

Related Questions