How to declare an stl::priority_queue with initial data and custom comparator?

Question

I need a priority_queue for my structs. I want to construct one using both initial data from an array and a custom comparator:

class mycomparison
{
public:
    mycomparison(const bool& maxOnTop=false, const int& compField = 0);
    ...
};

mergeRecord initialRecords[N]; // my array
mycomparison(false, field); // my custom comparator

std::priority_queue<mergeRecord, std::vector<mergeRecord>, mycomparison>
    recsHeap(???);

On the cplusplus reference, there is an example of how to initialize a priority_queue object with a comparator OR an array with initial values. How would I do both? I know I could insert them one by one, but this would cost O(nlogn) whereas passing them all at once is O(n).

TartanLlama · Accepted Answer · 2015-04-27 10:55:03Z

4

The range constructor for std::priority_queue allows you to pass a comparator function in as an optional argument:

template <class InputIterator>
priority_queue (InputIterator first, InputIterator last,
                const Compare& comp = Compare(),
                const Container& ctnr = Container());

So just call it like this:

std::priority_queue<mergeRecord,std::vector<mergeRecord>,mycomparison>
    recsHeap(std::begin(initialRecords), std::end(initialRecords), mycomparison(false,field));

edited Apr 27, 2015 at 10:55

answered Apr 27, 2015 at 10:50

TartanLlama

66.2k13 gold badges167 silver badges203 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Steephen · Accepted Answer · 2015-04-27 11:22:20Z

2

In below example std::greater<int> is the compare function and myints is an integer array. We can create a priority_queue my_priority_queue as follows:

int myints[]= {10,60,50,20};
std::priority_queue<int, std::vector<int>, std::greater<int> >
                            my_priority_queue(myints,myints+4);

In your example:

priority_queue<mergeRecord,std::vector<mergeRecord>,mycomparison>
 recsHeap (mergeRecord, mergeRecord+ kWayMerge,mycomparison(false,field));

edited Apr 27, 2015 at 11:22

answered Apr 27, 2015 at 10:54

Steephen

16k7 gold badges46 silver badges47 bronze badges

2 Comments

Savvas Parastatidis Over a year ago

I saw that example on cplusplus.com, I mentioned I wanted a comparator argument as well.

Steephen Over a year ago

@TartanLlama Thanks, that is valid. corrected the answer.

Collectives™ on Stack Overflow

How to declare an stl::priority_queue with initial data and custom comparator?

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related