Choosing the type parameters in generic programming

Question

I came across this piece of code in cpp ref

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

What exactly is the purpose of using typename Container::value_type in the above declaration? Will the following not work?

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

In a nutshell; `class` and `typename` can mostly be used interchangeably, but in a few situations `typename` is required, so if you just stick to `typename` you should be good :-) — Jesper Juhl, Mar 23 '18 at 16:40
@miradulo yes you are right. I'm not wondering why typename is used there. I'm wondering why is used instead of — Sanket, Mar 23 '18 at 16:45
Worth noting that since C++17, it is undefined behavior if `T` and `Container::value_type` are not the same type, as cppref alludes to. This was voted in [LWG 2566](http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#2566) because of issues like [this question points out](https://stackoverflow.com/questions/34128782/what-is-the-use-of-first-template-parameter-in-priority-queue). — miradulo, Mar 23 '18 at 16:45
The title of this question is quite misleading if what you are asking is why there is a mismatch of template parameter types. — xaxxon, Mar 23 '18 at 17:00
So just to clarify: your question isn't about template types or parameterization (as in the title), _or_ about the subtle differences between `typename` and `class` as in your first paragraph. It's just about the practical reason `std::priority_queue` is declared that way? — Useless, Mar 23 '18 at 17:38
Possible duplicate of [Where and why do I have to put the "template" and "typename" keywords?](https://stackoverflow.com/questions/610245/where-and-why-do-i-have-to-put-the-template-and-typename-keywords) — chtz, Mar 23 '18 at 17:52

463035818_is_not_an_ai · Accepted Answer · 2018-03-23T19:15:30.743

7

This is to be more generic: Container is a parameter and it might be a container (parametrized on T) whose value_type is different from T. From the top of my head I dont know a good example, but naively there is also no reason to put that constraint on the used Container (ie value_type must be T in your version).

For the sake of the example, lets say you have a strange_container whose value_type is std::pair<T,T> and you want to instantiate the template with

priority_queue<T,strange_container<T>>

then your default Compare = std::less<T> wouldnt work with that container, while Compare = std::less<typename Container::value_type> would correctly compare pairs.

Note that the above doesnt apply since C++17, as (from cppref):

The behavior is undefined if T is not the same type as Container::value_type. (since C++17)

So it seems like the signature was choosen with maximum genericity in mind and only later it was realized that this degree of freedom wasnt the best choice. And actually there are good reasons to require value_type and T to be the same, see eg here for more on this.

edited Mar 23 '18 at 19:15

answered Mar 23 '18 at 16:36

463035818_is_not_an_ai

109,796
11
89
185

I understood why typename is needed there. But my confusion is over the use of instead of just using – Sanket Mar 23 '18 at 16:43
1

I was just about to add an example like the one you just added. Another good example is a hashmap which usually takes a `value_type` and `key_type`, but the hash function relies on the `key_type`, not the `value_type` or both, so `std::hash` will be specialized using `typename Map::key_type`, instead of say `std::pair`. In the OP's case, `T` could refer to a `std::pair`, but `std::less` may only be specialized for `K` – smac89 Mar 23 '18 at 16:53
1

@user463035818 not my DV but from what I understand your example is undefined behavior since C++17. – miradulo Mar 23 '18 at 16:54
1

@miradulo yeah just noticed it and added at note – 463035818_is_not_an_ai Mar 23 '18 at 16:55
@Sanket you should update your question to make it clear what you are asking, as this answer seems to be answering the question that is asked in the title. – xaxxon Mar 23 '18 at 16:59
@xaxxon how does it answer the question in the title? I thought I am ignoring the question in the title but rather answering the question about why the signature is not just using `std::less` as proposed by OP – 463035818_is_not_an_ai Mar 23 '18 at 17:03

Choosing the type parameters in generic programming

1 Answers1