std::iterator_traits help, please.

[flclempire]

Hi, I'm going through Scott Meyers "Effective C++, 3rd Edition", and it gives some of the vital details for using iterator traits, but 100% fails to detail HOW to instantiate the traits.

For example, if I create a custom container with a custom iterator, I know that I can make a nested class and make a typedef of the type of iterator the template class supports.

template <typename T>
class MyContainer
{
public:
//cons/dtors
class iterator
    {
        public:
        typedef std::bidirectional_iterator_tag iterator_category;
    };
private:
//impl details
};

I've checked out the iterator_traits class and I see how it simply copies the nested typedef into its own typedef.
The question I have is.... HOW?!
How the bonk do I link my class to the iterator_traits class?
WHY and HOW?
I've tried adding this to the end of my header to try and instantiate the custom traits class~

std::iterator_traits<MyClass>
//also tried
std::iterator_traits<MyClass<int>>
//tried both with defining names as well 

But they give directionless errors all over the place.

I've tried googling all around but only find text-book copied explanations (which makes me suspect most of the people responding with such don't understand how it works either).
I'm literally enraged at how the book could leave out how to friggin' instantiate all of this information....


Any help would be appreciated, especially a simple code sample showing how to use iterator_traits.
Thanks :(

[ne555]

How the bonk do I link my class to the iterator_traits class?

You define these types:
difference_type, value_type, pointer, reference, iterator_category

I've tried adding this to the end of my header to try and instantiate the custom traits class~
std::iterator_traits<MyClass<int> >

Not sure what do you want to do here.

[flclempire]

What exactly is the iterator_traits template struct for?
The book basically describes that you define the typedef in your custom container, and magically have it interact with the iterator_traits template.

How on earth does this work?

iterator_traits says that is checks for the "iterator_category" typedef in the custom container.
It then copys that typedef to its own typedef.

1. WHY?! What is the point of this?
2. How? I need a way for the iterator_traits class to interact with my custom class to copy the typedef, right?

Sorry to sound annoyed and ignorant of this, but the book fails completely on this subject.

[ne555]

Sorry, I didn't play with that. This is what I've got from reading /usr/include/c++/bits/stl_algo.h

By instance std::advance http://www.cplusplus.com/reference/std/iterator/advance/
You've got an optimised algorithm if you work with random access iterators.
So ¿how could you code that?

template<class Random_Access>
Random_Access _advance(Random_Access i, int n, std::random_access_iterator_tag){ 
//the tag is used to identify the function (dummy variable)
	std::cerr << "random" << std::endl;
	i += n;
	return i;
}

template<class Iter, class Tag>
Iter _advance(Iter i, int n, Tag){
	std::cerr << "common" << std::endl;
	for(; n>0; n--) ++i;
	return i;
}

template<class Iter>
Iter advance(Iter i, int n){ //wrapper
	typename std::iterator_traits<Iter>::iterator_category category; //creating an object of the corresponding tag
	return _advance(i,n,category); //call the 
}

Now ¿why typename std::iterator_traits<Iter>::/**/ instead of just typename Iter::/**/ ? Not sure.

http://www.cplusplus.com/reference/std/iterator/iterator_traits/

template <class Iterator> struct iterator_traits {
  typedef typename Iterator::difference_type difference_type;
  typedef typename Iterator::value_type value_type;
  typedef typename Iterator::pointer pointer;
  typedef typename Iterator::reference reference;
  typedef typename Iterator::iterator_category iterator_category;
}

The typedef is defining every tag to a type. That works because you defined those tags in a public scope.
¿what is the purpose of that class? Dunno, maybe is so you don't have to inherit from a big class.

¿how the typedef work? Like std::vector<int>::iterator it;
iterator is a nested class (inside vector), defined in public scope so you can create objects. Note that you are aware of the name.

Suppose now that you want to create a class container, or templatize a function to accept containers.
Because of the algorithms that you use, you ask for an iterator. (the principle with iterator_traits is the same)

template<class Container>
bool size(const Container &c){
  typedef typename c::iterator iterator;
  iterator beg=c.begin(), end=c.end()
  size_t n=0;
  for(; beg!=end; ++beg)
    ++n;
  return n;
}

Sorry if I wasn't clear.

[flclempire]

Thanks for replying, but thats not even close to helping me with iterator_traits specifically. I've already seen its definition, but it doesn't seem to actually do anything, nor does it have any interaction beyond the seemingly pointless temporary instantiation to get a tag.

I understand the point of instantiating the object here~

typename std::iterator_traits<Iter>::iterator_category category; //creating an object of the corresponding tag 

By why is the typename needed? I learned that typename is only necissary when a nest class is type dependant (of the template type). There is no dependancy in the nested iterator class.
I saw that he used the typename preface in the book too, he didn't explain it.

It would seem that most people don't see a reason to use iterator_traits. Most seem to wonder why you don't just use
iterator::/**/
as you mentioned.

Boy oh boy this isn't fun, lol.

[stereoMatching]

Most seem to wonder why you don't just use iterator::/**/

Because iterator_traits could make things more generic
Think about this, what if T is not a class type but a pointer?

[ne555]

that makes sense.

About the typename. There is dependency with respect to iterator_traits.

template<class Iter>
Iter advance(Iter i, int n){ //wrapper
	typename std::iterator_traits<Iter>::iterator_category category;

Iter is a generic class, so the compiler can't know that iterator_traits<Iter>::iterator_category exists
http://www.parashift.com/c++-faq-lite/templates.html#faq-35.18

[flclempire]

I really can't consider *any* of your explanations until someone gives me any working kind of idea of why iterator_traits exists, and how to interface correctly with it.
Please stop giving me references, I don't understand the fundamentals of what the class exists for, references therefor cannot help me.
Consider this snip~

template<class Random_Access>
Random_Access _advance(Random_Access i, int n, std::random_access_iterator_tag){ 
//the tag is used to identify the function (dummy variable)
	std::cerr << "random" << std::endl;
	i += n;
	return i;
}

Does this even have anything to do with iterator_traits?
How is the tag/dummy variable determined? Do I specifically pass its iterator::iterator_category?

A far more basic explanation of these things would be nice. You guys seem to have a knack for responding with minor quizzes, which when solved yield the answer. Yet you don't take into account that I have no idea of how this particular topic works, therefor I can't trip my memory and have an "Aha! I see!" moment. There is simply nothing there.

I would love to learn about the subject here, but virtually all documentation
*requires you to already know the subject before you can understand its explanations*.
Obviously that makes these explanations technically "references", not "explanations".

Thanks for putting up with me so far btw, learning template programming is just so frustrating.

[ne555]

http://www.sgi.com/tech/stl/iterator_traits.html (the description of its purpose is quite good)

If you are defining a new iterator type I, then you must ensure that iterator_traits<I> is defined properly. There are two ways to do this.
First, you can define your iterator so that it has nested types I::value_type, I::difference_type, and so on.
Second, you can explicitly specialize iterator_traits for your type.
The first way is almost always more convenient, however, especially since you can easily ensure that your iterator has the appropriate nested types just by inheriting from one of the base classes input_iterator, output_iterator, forward_iterator, bidirectional_iterator, or random_access_iterator.

However I think that the info is not updated. I could not use the second method as I cannot find those classes. there is an iterator class from which you can derive

How is the tag/dummy variable determined? Do I specifically pass its iterator::iterator_category?

You weren't supposed to have access to that function. The tag is determined in the advance wrapper (and then the corresponding function is called).

template<class Iter>
Iter advance(Iter i, int n){ //wrapper
	typename std::iterator_traits<Iter>::iterator_category category; //creating an object of the corresponding tag
	return _advance(i,n,category); //category has the info about the tag (that's its only purpose) so the appropriate function is called
}

int main(){
	vector<int>::iterator vit;
	list<int>::iterator lit;
	advance(vit, 42); //category will be of type random_access_iterator_tag
	advance(lit, 0); //category will be of type bidirectional_iterator_tag
}

It's like doing Iter::category() to obtain the category of the iterator, so you can choose what to do next.

[edit] This should be more clear

template<typename _Iter>
inline typename iterator_traits<_Iter>::iterator_category
__iterator_category(const _Iter&){
	return typename iterator_traits<_Iter>::iterator_category();
}

template<class Iter>
Iter advance(Iter i, int n){ //wrapper
	return _advance( i, n, __iterator_category(i) );
}

[/edit]


Another example:
Suppose that you want to print all the elements in a vector

vector<int> v;
std::copy( 
	v.begin(), 
	v.end(), 
	std::ostream_iterator<int> //note that you need to explicit the type of the contained objects
		(cout, " ")
);

So you try a function

template<class Iter, class Type>
void print(Iter beg, Iter end, Type){
	std::copy(
		beg, 
		end,
		ostream_iterator<
			Type
		> (cout, " ")
	);
}

The problem is ¿how will you call it? ¿what object will you use as the third parameter? ¿what if later you want to change the type of the objects (like a bignum)?

Instead of that, you could use iterator_traits to find that type

template<class Iter>
void print(Iter beg, Iter end, std::ostream &out = std::cout){ //range [)
	std::copy(
		beg, 
		end,
		ostream_iterator<
			typename iterator_traits<Iter>::value_type
		> (out, " ")
	);
}

[ne555]

How the bonk do I link my class to the iterator_traits class?

You can think of templates as interfaces.
If a class implements that interface, then it can be used as a replacement for the template.

So in order to define an iterator you must provide those nested types.
Later you will need to define the appropriate operators, like operator++ and operator*.

[flclempire]

Ok, I think I'm starting to get it.
So if the passed class was MyClass::iterator~

template<class Iter>
Iter advance(Iter i, int n){ //wrapper
	typename std::iterator_traits<Iter>::iterator_category category;
}

This call basically instantiates the iterator_traits<MyClass::iterator>. It then accesses the typedef named iterator_category of the newly created instantiation, assigning that typedef to "category". Further use of this function will refer to the first instantiation, not needing to create another, right?

Alternatively, I could define my own specialization like~

template <>
struct iterator_traits<MyClass::iterator>
{
//... tags and such...
}

Is my train of thought correct?

As for your further examples with copy using an ostream_iterator template, thats a bit advanced looking for my current template knowledge, but I think I see whats going on with it.

I get the basics of what iterator_traits is for, and how to interact with it, but I think it'll be a good long while before I get to the point where I can use it effectively :)
Thanks for taking time to help me, you've lifted an extremely depressing burden from my mind.

[ne555]

//typename std::iterator_traits<Iter>::iterator_category category;
random_access_iterator_tag category;

Note that category is an object, not a type.

I think the class is only defined once

Yes, you could specializate the template, but I don't think you should.
Besides only the tags are important there.

You're welcome :)