Priority_queue functor use C++

Question

I have stumbled upon some weird use of priority_queue, I would love to obtain some proper explanation of why on earth it's plausibile/valid to use something like this in priority_queue declaration:

typedef priority_queue<RandomContainer, **vector<RandomContainer>**, FunctorName> NewQueueName;

Let's say we've got some struct called SPerson:

struct SPerson { int age; string name; string surname; };

and some functor which will be helpful to sort all elements of queue accordingly to our likeing:

struct TheWayILike { bool operator()(const SPerson &name1, const SPerson &name2) { if(name1.name > name2.name) return true; if(name1.name < name2.name) return false; return false; } };

Now we can declare our priority_queue which will be based upon elements from the struct and which will be ordered by functor called TheWayILike.

priority_queue<SPerson, TheWayILike>

or shorter way by using typedef and single name like so:

 typedef priority_queue<SPerson, TheyWayILike> newNameForPQ;

but somehow it's wrong and I have to add following line: vector

Question:

Why on earth do I have to squize my personally customized data types into vector ?

Why it must be a vector and why should I use it anyway ?

Why do I need to fill my data into vector ? I haven't read about it in official priority_queue documentation, so I would love to obtain some easy to understand explanation for rookie programmer.

Cheers!

The Container is only a template parameter. It tells priority_queue what to use internally, you do not have to provide an instance of this container! In other words, create your queue like so: priority_queue<SPerson, vector<SPerson>, TheWayILike> myPQ and push your SPerson elements in it: myPQ.push(a); myPQ.push(b); ... — Daniel L
– Daniel L, Commented Oct 17, 2014 at 20:10

Columbo · Accepted Answer · 2014-10-17 19:51:20Z

3

You dont' have to. But look at the declaration of the priority_queue class template:

template< class T, class Container = std::vector<T>, class Compare = std::less<typename Container::value_type> > class priority_queue;

You can't provide a custom comparator type argument unless you also provide the underlying container to hold the data in. The author of the line above decided vector was the best choice. Any other container that fits the requirements can also be used, e.g. deque, but vector proves to be best for most applications so it is the default.

answered Oct 17, 2014 at 19:51

Columbo

61.3k8 gold badges163 silver badges204 bronze badges

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

4 Comments

aruisdante Over a year ago

Specifically, the container needs to fulfill a specific API and support random-access iterators, which vector and deque both do.

Jamie Randall Over a year ago

So basically I can't use ONLY basic struct, as a container that will be used in priority_queue, but I have to reassign/copy all data from struct to vector, deque or any other container before using priority_queue ? Is that right ?

Columbo Over a year ago

If you want to use the priority_queue type of the line above, yes. If you can use your "own" priority_queue specialization and your container fulfills the requirements, you can just let it use your container type and move your container object into the priority_queue.

Benjamin Lindley Over a year ago

@JamieRandall: You make it sound as if there is a bunch of extra work being done because you are using a custom type with a custom comparator. There is not. The only thing you have to do differently is in how you declare the priority_queue (the template parameters you provide). After that, the rest of the work is all being done by the priority_queue, and it is the exact same amount of work that is done for any other type with any other comparator.

Collectives™ on Stack Overflow

Priority_queue functor use C++

1 Answer 1

4 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Related