bind2nd with templates

[Paul]

The below code undoubtedly has many problems. For example, I don't think the recursion always terminates. However, I have a specific question about one aspect of it. Then I will correct it from an algorithmic point of view.
I don't understand why typename needs to preface std::iterator_traits in order for it to compile.
After all, I can write std::vector<RandomaccessIterator> vec; without complaint. Why does typename need to be repeated? I would have thought that template <typename RandomaccessIterator> is sufficient.

Thank you very much for your help,

Paul

#include<algorithm>
#include <iterator>
#include<functional>
template <typename RandomaccessIterator>
void quicksort(RandomaccessIterator begin, RandomaccessIterator end)
{
if (begin != end)
{
RandomaccessIterator pivot = std::partition( begin, end, bind2nd( std::less < typename std::iterator_traits < RandomaccessIterator>::value_type >(), *begin));
quicksort( begin, pivot);
RandomaccessIterator new_pivot = begin;
quicksort(++new_pivot, end);
}
}


int main()
{

}

[Richard]

[Please do not mail me a copy of your followup]

Paul <peps...@gmail.com> spake the secret code
<711942fd-ff24-49ab...@googlegroups.com> thusly:

>I don't understand why typename needs to preface std::iterator_traits in
>order for it to compile.

You're accessing a nested name of a type inside a template type. For the
compiler to understand that the nested name is a type (and not a data
member or method member), it needs the typename keyword.

This Stack Overflow post seems to explain it pretty well in more detail
<http://stackoverflow.com/a/613132/139855>
--
"The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
The Computer Graphics Museum <http://computergraphicsmuseum.org>
The Terminals Wiki <http://terminals.classiccmp.org>
Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>

[Paul]

On Thursday, July 9, 2015 at 8:04:14 PM UTC+1, Richard wrote:
> [Please do not mail me a copy of your followup]
>
> Paul <peps...@gmail.com> spake the secret code
> <711942fd-ff24-49ab...@googlegroups.com> thusly:
>
> >I don't understand why typename needs to preface std::iterator_traits in
> >order for it to compile.
>
> You're accessing a nested name of a type inside a template type. For the
> compiler to understand that the nested name is a type (and not a data
> member or method member), it needs the typename keyword.
>
> This Stack Overflow post seems to explain it pretty well in more detail
> <http://stackoverflow.com/a/613132/139855>

Thanks, Richard. In other words, you need one typename declaration (not sure if "declaration" is the right word here. Feel free to correct if not) to state that <Type> refers to a type and another typename declaration to state that x<Type>::SomethingElse also refers to a type.

Paul

[Richard]

[Please do not mail me a copy of your followup]

Paul <peps...@gmail.com> spake the secret code

<d1eb8ca9-f225-4ca4...@googlegroups.com> thusly:

Sure, let's go back and look at your code, reformatted slightly:

template <typename RandomAccessIterator>
// 1st use of typename keyword
void quicksort(RandomAccessIterator begin, RandomAccessIterator end)
{
if (begin != end)
{
typdef
typename std::iterator_traits<RandomAccessIterator>::value_type
// 2nd use of typename keyword
iterator_value_type;
RandomAccessIterator pivot = std::partition(begin, end,
bind2nd(std::less<iterator_value_type>(), *begin));
quicksort( begin, pivot);
RandomAccessIterator new_pivot = begin;
quicksort(++new_pivot, end);
}
}

(Here, I've introduced a local typedef for the value type of the random
access iterator that we got from std::iterator_traits.)

When you write a template function, you have to tell the template
mechanism what kind of template arguments are supplied to your template
function. It was always allowed that you could write 'typename' or
'class' to indicate that the argument was expected to be a type and not
an integral constant. 'class' seemed to be more commonly used in the
past and over time the community has shifted to favoring the 'typename'
because it is more intention-revealing than 'class'. (The supplied
type need not be a class, it could be a builtin type like int, or it
could be a struct or union.) This is how typename is used in the
first location in your code.

In the second location, we're instantiating a template with a type
argument. That type argument comes from a nested name inside another
template, in this case the other template is std::iterator_traits and
the nested name is value_type. Here we need to use typename to tell
the compiler that the nested name refers to a type and not a function
or data member. (Note that the nested name needn't be a name
introduced by a typedef but it often is. It could be a nested class
or struct or union as well.)

[Paul]

Thanks.

Now might be a good time to reveal the corrected code. Feedback is welcome.
Thanks again,

Paul

template <typename RandomAccessIterator>
// 1st use of typename keyword
void quicksort(RandomAccessIterator begin, RandomAccessIterator end)
{
if (begin != end)
{

//typedef

typename std::iterator_traits<RandomAccessIterator>::value_type
// 2nd use of typename keyword
iterator_value_type;
RandomAccessIterator pivot = std::partition(begin, end,
bind2nd(std::less<iterator_value_type>(), *begin));
quicksort( begin, pivot);

quicksort((begin == pivot ? ++begin : pivot),end);
}
}