Menu
I tried to understand iterator implementation, and while playing around with the source, I saw this statement:
typedef output_iterator_tag iterator_category;
I don't understand how this typedef work within the class? What's the side effect does it provide? Can anyone walk me through this?
860
An iterator is an object (like a pointer) that points to an element inside the container. We can use iterators to move through the contents of the container. They can be visualised as something similar to a pointer pointing to some location and we can access content at that particular location using them.
The primary purpose of an iterator is to allow a user to process every element of a container while isolating the user from the internal structure of the container. This allows the container to store elements in any manner it wishes while allowing the user to treat it as if it were a simple sequence or list.
An iterator is an object that allows you to step through the contents of another object, by providing convenient operations for getting the first element, testing when you are done, and getting the next element if you are not. In C, we try to design iterators to have operations that fit well in the top of a for loop.
The type of it is map<string,int>::iterator , which is a class with a bunch of operators overloaded. For some container types, Container::iterator may be a raw pointer type.
You need to read up on generic programming because you're not likely to get this answer.
"Output Iterator" is a concept that certain iterators match. Each iterator that is a realization of this concept has certain functionality associated with it. It's sort of like inheritance, but it isn't.
C++ doesn't have any such anything that represents concepts (was a proposed addition to C++0x but failed to make it). That being the case, we need various template constructs to allow us to associate a "tag" with an iterator type. By associating the output_iterator_tag type with an iterator we're claiming that our iterator type realizes the OutputIterator concept.
This becomes very important when you're trying to write algorithms that are as optimized as possible and also generic. For example, performing a sort with an iterator that can be incremented or decremented by an arbitrary value (other than 1 in other words) is more efficient than one that doesn't have this capability. Furthermore, in order to get a new iterator that's X distance from another can require different operations depending on the capabilities of the iterator. To write such an algorithm you use "tag dispatching". To explain this more fully, here's an implementation (untested) of std::advance that works both with iterators that have a += operator and ones that only have a ++ operator and is as fast as possible with both versions.
template < typename RandomAccessIterator >
RandomAccessIterator advance( RandomAccessIterator it
, int amount
, random_access_iterator_tag)
{ return it + amount; }
template < typename ForwardIterator >
ForwardIterator advance(ForwardIterator it, int amount, forward_iterator_tag)
{
for (;amount; --amount) ++it;
return it;
}
template < typename Iterator >
Iterator advance(Iterator it, int amount)
{
typedef typename std::iterator_traits<Iterator>::iterator_tag tag;
advance(it, amount, tag());
}
That's from memory so it's probably riddled with bugs (probably have a bunch of types wrong even)...but that's the idea. The iterator tags are types that are empty and also inherit from each other in exactly the same way as the concepts refine each other. For instance, a random access iterator IS a forward iterator. Thus random_access_iterator_tag is a derivative of forward_iterator_tag. Because of function overload resolution rules passing a random_access_iterator_tag to the function resolves to that version of the function rather than the forward_iterator_tag one.
Again, go read up on generic programming. It's essential to utilizing the full power of C++.
Oh, and finally... The typedef is there in the iterator's class definition because it's a nice, convenient place to put it. A default iterator_traits can the look for it there. You'll want to use iterator_traits rather than that definition though because raw pointers are iterators too and they can't have internal typedefs.
124
output_iterator_tag is an empty class. Its purpose is to allow algorithms to identify generic classifications of iterators which follow certain rules and provide particular operators. This allows for algorithms to provide a more specialized implementation of a given algorithm under certain conditions.
For example in VS2010's header, "std::distance"'s algorithm has two implementations depending on the 'iterator_category' typedef'd in the iterators passed in.
std::distance only requires an input iterator in order to calculate the distance between two iterators, but it might take linear 'O(n)' time to calculate the answer.
If however, the compiler figures out that a random access iterator is being used and can thereby take advantage of the subtraction operator to calculate the distance in constant time 'O(1)'.
I would recommend watching Stephan T. Lavavej's video where he goes a bit into type traits and their uses in the Standard Template Library.
24
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
