What is the use of first template parameter in priority_queue

Question

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.

Nice find. It allows you to write `priority_queue`, I suppose. It's not used anywhere else, and I don't see any requirements on it in the standard. — T.C., Dec 07 '15 at 08:00
If you see e.g. [this `std::priority_queue` reference](http://en.cppreference.com/w/cpp/container/priority_queue) you will see that the types used for the stored data actually uses the types from the container, not the provided first template argument. If it's supposed to be like that and what the specification says I don't know. — Some programmer dude, Dec 07 '15 at 08:02
The firsrt parameter is the element type in second parameter. So i think this `priority_queue > pq;` is wrong. please refer:http://www.cplusplus.com/reference/queue/priority_queue/ — BlackMamba, Dec 07 '15 at 08:02
@JoachimPileborg - yes but if my code just give me a priority_queue of intergers (stored in a vector) what is then the use/purpose of the first template parameter, i.e. `SomeClass` ? I guess it must have some use since it is there. Actually I expected a compile error for the code but it just compiled fine. — Support Ukraine, Dec 07 '15 at 08:05
Yikes! That looks so wrong. I get the same behaviour with a reasonably new clang. — juanchopanza, Dec 07 '15 at 08:06
STL: ["Definitely a defect, of the form “that’s so bizarre, the LWG forgot to forbid it”."](https://twitter.com/StephanTLavavej/status/673955902701998080) Off to LWG we go... — T.C., Dec 07 '15 at 20:12
@T.C. - Thanks for the update - quite interesting to read the comment from STL. Do you plan to forward it to LWG? — Support Ukraine, Dec 07 '15 at 21:20

Some programmer dude · Answer 1 · 2015-12-07T08:07:23.823

5

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.

edited Dec 07 '15 at 08:07

answered Dec 07 '15 at 08:05

Some programmer dude

400,186
35
402
621

2

So the first parameter is only used when I don't specify a container myself - is that it? – Support Ukraine Dec 07 '15 at 08:07
6

To me, that violates the principle of least astonishment. – juanchopanza Dec 07 '15 at 08:41
@JoachimPileborg - I feel sure that you are rigth but can you elaborate a bit more on the last sentence in your answer. I can't see how I'm supposed to read the template and reach that conclusion. I just see the same `T` twice. – Support Ukraine Dec 07 '15 at 08:47
@StillLearning In the declaration you have three template arguments: `class T`, `class Container = std::vector` and `class Compare = ...`. The first argument, `class T`, is for the type that should be stored in the priority queue. The second argument, `class Container` uses the first argument for a default declaration (works just like default function arguments), and says that the default type for `Container` (if it's not specified) is `std::vector` where `T` is taken from the first template argument. – Some programmer dude Dec 07 '15 at 08:55
@JoachimPileborg - I understand the meaning of what you write but still I can't see how I should get that understanding from reading the template. As you write - quote: `The first argument, class T, is for the type that should be stored in the priority queue` but in my example it isn't because the second parameter kind of overwrites the first. The template doesn't let me know this feature is possible. – Support Ukraine Dec 07 '15 at 21:24
@StillLearning The first argument is used for the second argument *if you don't provide the second argument yourself*. You know how default arguments to function works? It's the same think with template default arguments. – Some programmer dude Dec 08 '15 at 01:48

score 5 · Accepted Answer · answered Mar 06 '16 at 04:58

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.

What is the use of first template parameter in priority_queue

2 Answers2

Linked