Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is the use of first template parameter in priority_queue

Tags:

c++

For the std::priority_queue I assumed that the first template parameter specified the type and the second should be a container of that type. Example:

priority_queue<int, vector<int>> someQueue;

However, the following code compiles and seems to run fine:

class SomeClass
{
};

int main()
{
    priority_queue <SomeClass, vector<int>> pq;
    int x = 9;
    pq.push(x);
    int t = pq.top();
    cout << t << endl;
    pq.pop();
    return 0;
}

Is the above code invalid (i.e. giving UB)?

If it is valid - what is the first template parameter (i.e. someClass) used for in the priority_queue.

like image 546
Support Ukraine Avatar asked Dec 07 '15 07:12

Support Ukraine


People also ask

Which container class can be used as underlying container for Priority_queue?

Suitable underlying container classes for priority_queue include deque Class and the default vector Class or any other sequence container that supports the operations of front , push_back , and pop_back and a random-access iterator.

What is priority queue in C++?

A priority queue in c++ is a type of container adapter, which processes only the highest priority element, i.e. the first element will be the maximum of all elements in the queue, and elements are in decreasing order.

What is container in priority queue?

class T, class Container = std::vector<T>, class Compare = std::less<typename Container::value_type> > class priority_queue; A priority queue is a container adaptor that provides constant time lookup of the largest (by default) element, at the expense of logarithmic insertion and extraction.

How do you access the front element of the priority queue?

priority_queue::top() top() function is used to reference the top element of the priority queue. The top (by default) element is the largest element in C++ STL. However in other programming languages like java, by default a min heap is created and the top() gives the minimum element.


2 Answers

Freshly voted into the working paper in Jacksonville, via LWG issue 2566:

The first template parameter T of the container adaptors shall denote the same type as Container::value_type.

Writing std::priority_queue<SomeClass, std::vector<int>> accordingly results in undefined behavior.

like image 146
T.C. Avatar answered Nov 10 '22 21:11

T.C.


In the C++11 specification the section about std::priority_queue is §23.6.4. In it the first template argument is simply the default type used for the container and nothing else.

The actual value type is taken from the container.

The class is declared as

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

[Taken from this reference]

That declaration show how, when and where the first template argument is used.

like image 30
Some programmer dude Avatar answered Nov 10 '22 22:11

Some programmer dude