A confusing topic in Stroustrup's book

[Doug Mika]

So I am in the midst of reading Stroupstrup's book, The Programming Language 4th ed, and I came upon this little program to help us sort singly linked containers that do not provide random iterator access to the data. Basically, he writes an "adapter" (I hope I'm using the term correctly) to sort a singly linked list by copying the singly linked list into a vector, sorting the vector, and then copying back the vector into a singly linked list. The neat, and confusing part is some of the commands he uses, which I was hoping someone could explain:

void test(vector<string>& v, forward_list<int>& lst) {
sort(lst); //sort the singly linked list
}

He writes two helper functions that take an extra argument indicating whether the sort is to be used for singly-linked iterators or random iterators:
template<typename Ran> //for random access iterators
void sort_helper(Ran beg, Ran end, random_access_iterator_tag) //we can subscript into [beg:end)
{
sort(beg,end); //just sort it
}

and

template<typename For> //for forward iterators
void sort_helper(For beg, For end, forward_iterator_tag) //we can traverse [beg:end)
{
vector<decltype(*beg)> v {beg,end}; //initialize the vector
sort(v.begin(),v.end());
copy(v.begin(),v.end(),beg); //copy the elements back
}

QUESTION: I have never seen the paramters of a function be in the format "forward_iterator_tag", I have always only seen "Type instance" ie "int myInt". What is "forward_iterator_tag", and where is its type?

The selection of the helper function happens here:
template<typname C>
void sort(C& c) {
using Iter = Iterator_type<C>;
sort_helper(c.begin(),c.end(),Iterator_category<Iter>{});
}

QUESTION:
1)How would this sort template look if we were to not have using Iter = Iterator_type<C>;? What does this line do? - I have never seen it used in this context.
2)What is Iterator_type and Iterator_category? I searched for these on www.cplusplus.com but found nothing that would make it clear.

Thanks to all for reading something this long.

[Victor Bazarov]

'forward_iterator_tag' and 'random_access_iterator_tag' are the types
defined by the library. Those types are to what 'Iterator_category'
instantiations result into.

It's not all that difficult, really. 'Iterator_type<C>' makes 'Iter' to
be a particular type. Then it used as the argument to the
'Iterator_category' template. When you create an object of that
category, it creates an object of one of those '_tag' types. So, the
'sort_helper's third argument becomes either one type or the other, and
the compiler creates the code that calls either one 'sort_helper'
specialisation or the other (from the two which you/he defined).

When templates are concerned, start your tracing from the bottom.
Imagine yourself the compiler. Substitute 'sort(C& c)' with the call
made and try to understand what type is 'C' here. Now "process" the
body of that template function, with the specific 'C' in mind. The
'using' directive makes 'Iter' something particular. What is it? It's
something that arrives from 'Iterator_type' template. Take a look what
the 'Iterator_type' template gives when its argument is 'std::vector',
and what it gives when its argument is 'std::forward_list'.

And so on...

V
--
I do not respond to top-posted replies, please don't ask

[Doug Mika]

Let's stick with one question at a time:
what is "Iterator_type<C>"? Is it a reserved word like "decltype"? (No I think or I would have found it). Is it a template class? If so, what library is it in (www.cplusplus.com finds no such keyword Iterator_type)

[Paavo Helde]

Doug Mika <doug...@gmail.com> wrote in
news:269477dc-86b2-494b...@googlegroups.com:

>> > template<typname C>
>> > void sort(C& c) {
>> > using Iter = Iterator_type<C>;
>

> Let's stick with one question at a time:
> what is "Iterator_type<C>"? Is it a reserved word like "decltype"?
> (No I think or I would have found it). Is it a template class? If
> so, what library is it in (www.cplusplus.com finds no such keyword
> Iterator_type)

It looks like a template class indeed. I understand this is an example from
a book. Most probably the book assumes this is defined earlier in the code.
Probably the book contains the definition of Iterator_type somewhere. Have
you looked in the book index?

Anyway, it looks like a helper class which is used for deducing the needed
iterator type from the container type, maybe even for such containers as C-
style arrays.

hth
Paavo

[Victor Bazarov]

It is not "a template class". There is no such thing as "a template
class". It is, in fact, a *class template*. It is not a reserved word.
It is a template that is defined somewhere. From what you have posted
I can only determine that it has at least one argument, that its
argument is a type, and I can conclude that it probably a special
constuct/template to be used in combination with other templates, like
the 'Iterator_category'.

Those are specialized for known containers somehow. You need to look
for more code (possibly in other sections/chapters) to see how they are
defined.

The Standard Library has similar templates/types defined:

namespace std {
struct input_iterator_tag { };
struct output_iterator_tag { };
struct forward_iterator_tag: public input_iterator_tag { };
struct bidirectional_iterator_tag: public forward_iterator_tag { };
struct random_access_iterator_tag
: public bidirectional_iterator_tag { };
}

For 'std::vector' its 'iterator' type is implementation-defined, but it
is such that its traits defined its category as 'random access',
probably. It's a bit more involved than the simplistic examples in the
book, but it's not impossible to follow all the definitions and unravel
them to see the relationships and how they are instantiated.

[Richard]

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

Doug Mika <doug...@gmail.com> spake the secret code
<be814919-657e-4f0f...@googlegroups.com> thusly:

>template<typename For> //for forward iterators
>void sort_helper(For beg, For end, forward_iterator_tag) //we can
>traverse [beg:end)
>{
> vector<decltype(*beg)> v {beg,end}; //initialize the vector
> sort(v.begin(),v.end());
> copy(v.begin(),v.end(),beg); //copy the elements back
>}
>
>QUESTION: I have never seen the paramters of a function be in the format
>"forward_iterator_tag", I have always only seen "Type instance" ie "int
>myInt". What is "forward_iterator_tag", and where is its type?

The 3rd argument in the snippet above is simply an unnamed argument of
type "forward_iterator_tag". As mentioned in other responses, the
standard library defines some types for the various iterators:
<http://en.cppreference.com/w/cpp/iterator/iterator_tags>

These types are called "tags" because they only exist to allow you to
select implementations of an algorithm based on the type of the tag.
In this case, the right implementation of the template function
sort_helper() is being selected for forward iterators through function
overloading.

>The selection of the helper function happens here:
>template<typname C>
>void sort(C& c) {
> using Iter = Iterator_type<C>;
> sort_helper(c.begin(),c.end(),Iterator_category<Iter>{});
>}

Here he is using his own "Iterator_category<Iter>{}" helper as a "meta
function" -- a thing that takes a type (in this case, the type of the
iterator Iter) and returns another type (in this case, the associated
iterator category type).

>QUESTION:
>1)How would this sort template look if we were to not have using Iter =
>Iterator_type<C>;? What does this line do? - I have never seen it used
>in this context.

Iterator_type<C> is also an invocation of his own little template meta
function. I don't have my 4th edition handy here, but I remember that
he is pretty good about making sure he describes these in the text before
using them.

>2)What is Iterator_type and Iterator_category? I searched for these on
>www.cplusplus.com but found nothing that would make it clear.

They are Bjarne's helpers that simplify things slightly by eliminating
a little syntax.
--
"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>

[Doug Mika]

Iterator_type<C> is a system template, but I can't find a description of it anywhere... (The book doesn't define it). Arrrgghhh it's frustrating, it's a neat example making this even more upsetting.

[Doug Mika]

Come to think of it, it may be one of his own constructs, but it certainly isn't in the book - at least Adobe's find didn't locate it in my digital copy of the book....argghhh

[Richard]

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

Now that I am home and have access to my 4th edition of "The C++
Programming Language", I looked up where the code you qouted appears.

It is in the middle of pg. 125, section 5.4.2.1 iterator_traits, the
first section in 5.4.2 Type Functions.

Doug Mika <doug...@gmail.com> spake the secret code
<be814919-657e-4f0f...@googlegroups.com> thusly:

>2)What is Iterator_type and Iterator_category? I searched for these on
>www.cplusplus.com but found nothing that would make it clear.

Did you continue reading after the code you quoted? At the bottom of
page 125, it provides the definitions for Iterator_type and
Iterator_category. (Aside: I find <http://en.cppreference.com/w/> a
much better online reference than cplusplus.com; it is more current
with the language and being a wiki it is constantly improved by many
people instead of whoever is "The C++ Resources Network".)

If this is your first exposure to C++, I might suggest that you start
with the much shorter book by Stroustrup "A Tour of C++".
<http://amzn.to/1FQxUd4> At only 192 pages, it is a much better
introduction to modern C++. While I like the detail provided in
"The C++ Programming Language", it frequently digresses into every
little nook and cranny of the language. Many of these digressions are
not necessary for a working knowledge of C++ on a day to day basis.o

After you have a working knowledge of the language, then you can
revisit all those nooks and crannies and discover the deeper insights
of template metaprogramming and the like. But if your experiences
so far as a programmer is the typical programming in a block
structured language like Java or C#, then diving right into the depths
of C++ can be confusing and overwhelming.

[woodb...@gmail.com]

On Friday, June 12, 2015 at 10:20:36 PM UTC-5, Richard wrote:
> [Please do not mail me a copy of your followup]
>
> Now that I am home and have access to my 4th edition of "The C++
> Programming Language", I looked up where the code you qouted appears.
>
> It is in the middle of pg. 125, section 5.4.2.1 iterator_traits, the
> first section in 5.4.2 Type Functions.
>
> Doug Mika <doug...@gmail.com> spake the secret code
> <be814919-657e-4f0f...@googlegroups.com> thusly:
>
> >2)What is Iterator_type and Iterator_category? I searched for these on
> >www.cplusplus.com but found nothing that would make it clear.
>

> (Aside: I find <http://en.cppreference.com/w/> a
> much better online reference than cplusplus.com; it is more current
> with the language and being a wiki it is constantly improved by many
> people instead of whoever is "The C++ Resources Network".)
>

Cplusplus.com has a link that says, "Spotted an error? contact us."
So they are asking users to help them improve the site.
I did get confused one time by cplusplus.com cause I couldn't
tell whether C++ 1998 or C++ 2011 was the default. I assumed it
would be the 2011 version and it turned out that was wrong. I looked
at cplusplus.com again yesterday and it looks like they still
default to the 1998 version of C++.

Brian
Ebenezer Enterprises - In G-d we trust.
http://webEbenezer.net

[Doug Mika]

I appreciate everyone's patience: so what you're trying to tell me is that the following is the definition of Iterator_type:

template<typename C>
using Iterator_type = typename C::iterator; //C's iterator type

Ok, I've heard of template functions, and template classes, but what would something like this be? A template followed by the "using" keyword? Could someone define what these two lines do, as precisely as possible?

[Victor Bazarov]

On 6/15/2015 1:13 PM, Doug Mika wrote:
>[..]

> I appreciate everyone's patience: so what you're trying to tell me
> is
that the following is the definition of Iterator_type:
>
> template<typename C>
> using Iterator_type = typename C::iterator; //C's iterator type
>
> Ok, I've heard of template functions, and template classes, but what
> would something like this be? A template followed by the "using"
> keyword? Could someone define what these two lines do, as precisely
> as possible?
>

It's called "an alias template", it essentially declares a name that can
act as a template-id. Alias templates are used to reduce the number of
template arguments that are needed to be specified thus narrowing down
the set of generated types. For instance, you can define your own
custom allocator to be used with all possible vectors you might want to
define later, and then say

template<class T>
using myvector = std::vector<T, myspecialallocator<T>>;

Then, when you say

myvector<int> vi;

it will be the same as saying

std::vector<int, myspecialallocator<int>> vi;

. It's kind of a typedef, but for templates.

[Richard]

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

Doug Mika <doug...@gmail.com> spake the secret code

<81fc80f4-2a3d-4e46...@googlegroups.com> thusly:

>I appreciate everyone's patience: so what you're trying to tell me is
>that the following is the definition of Iterator_type:
>
>template<typename C>
>using Iterator_type = typename C::iterator; //C's iterator type
>
>Ok, I've heard of template functions, and template classes, but what
>would something like this be? A template followed by the "using" keyword?
>Could someone define what these two lines do, as precisely as possible?

It's called a type alias and is new to C++11:

<http://en.cppreference.com/w/cpp/language/type_alias>

It is similar to, but more general than, typedef.

[A. Bolmarcich]

On 2015-06-12, Doug Mika <doug...@gmail.com> wrote:
[snip]

> template<typname C>
> void sort(C& c) {
> using Iter = Iterator_type<C>;
> sort_helper(c.begin(),c.end(),Iterator_category<Iter>{});
> }
>
> QUESTION:
> 1)How would this sort template look if we were to not have using Iter = Iterator_type<C>;? What does this line do? - I have never seen it used in this context.
> 2)What is Iterator_type and Iterator_category? I searched for these on www.cplusplus.com but found nothing that would make it clear.
>
> Thanks to all for reading something this long.

Other replies have answered those question. I think it is useful to add that
after the program defined aliases Iter, Iterator_type, and Iterator_category
are applied the third argument of the call to sort_helper is (including
namespace qualification)

typename std::iterator_traits(typename C::iterator)::iterator_category {}

It creates an object whose type corresponds to the iterator_category of
the iterator_traits of an iterator of a container of type C. The type of
that object is used to select which of the overloaded sort_helper function
templates to instantiate (at compile time) and call (at run time).

When C is a vector, the third argument is of type
std::random_access_iterator_tag. When C is a list, the third argument is of
type std::forward_iterator_tag.