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<int>, I suppose. It's not used anywhere else, and I don't see any requirements on it in the standard. — T.C.
– T.C., Commented Dec 7, 2015 at 8:00
If you see e.g. this std::priority_queue reference 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
– Some programmer dude, Commented Dec 7, 2015 at 8:02
The firsrt parameter is the element type in second parameter. So i think this priority_queue <SomeClass, vector<int>> pq; is wrong. please refer:cplusplus.com/reference/queue/priority_queue — BlackMamba
– BlackMamba, Commented Dec 7, 2015 at 8: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. — 4386427
– 4386427, Commented Dec 7, 2015 at 8:05
STL: "Definitely a defect, of the form “that’s so bizarre, the LWG forgot to forbid it”." Off to LWG we go... — T.C.
– T.C., Commented Dec 7, 2015 at 20:12

T.C. · Accepted Answer · 2016-03-06 04:58:49Z

5

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.

answered Mar 6, 2016 at 4:58

T.C.

139k18 gold badges306 silver badges440 bronze badges

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

Comments

Some programmer dude · Accepted Answer · 2015-12-07 08:07:23Z

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 7, 2015 at 8:07

answered Dec 7, 2015 at 8:05

Some programmer dude

411k36 gold badges420 silver badges655 bronze badges

6 Comments

4386427 Over a year ago

So the first parameter is only used when I don't specify a container myself - is that it?

juanchopanza Over a year ago

To me, that violates the principle of least astonishment.

4386427 Over a year ago

@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.

Some programmer dude Over a year ago

@StillLearning In the declaration you have three template arguments: class T, class Container = std::vector<T> 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<T> where T is taken from the first template argument.

4386427 Over a year ago

@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.

|

Collectives™ on Stack Overflow

What is the use of first template parameter in priority_queue

2 Answers 2

Comments

6 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

6 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related