• entries
    146
  • comments
    436
  • views
    197613

Type Traits, Part 3

Sign in to follow this  
Washu

114 views

iterator_traits
There are a last few details that I would like to cover in relation to traits. The first is iterator traits, what are they, and how can you use them.

Iterator traits are used primarily by the algorithms in the standard library which take ranges. Since the standard library is designed to be generic, the majority of the algorithms take pairs of iterators that it uses to operate on that range of elements. Iterators are generic pointer like objects. Their behavior closely resembles that of pointers, including the dereference, increment, decrement and comparison operators. Because they they are generic, standard algorithms can take many different types of iterators, including actual pointers.

Every iterator has a category that it fits in. The categories are hierarchical in nature. They are described using iterator tags. Each tag describes the requirements that an iterator described using that tag must meet. Since the tags describe a logical progression of functionality, they are arranged in an inheritance tree where the most derived tag represents an iterator with the most functionality.

  • input_iterator_tag
    This is one of simplest iterator types, The iterator can move forward (through pre-and-post increment), It may retrieve values, but it may not store values (read only).

  • output_iterator_tag
    This is one of simplest iterator types, The iterator can move forward (through pre-and-post increment), It may store values, but it may not retrieve values (write only).

  • forward_iterator_tag
    This iterator is forward moving (through pre-and-post increment), it may also store and retrieve values from the underlying container.

  • bidirectional_iterator_tag
    This iterator can move both forward and backwards (through pre-and-post increment/decrement), it has all of the functionality of a forward iterator. The list, set, multiset, map, and multimap containers all provide bidirectional iterators.

  • random_access_iterator_tag
    The move versatile of iterators in terms of functionality, but the most limiting in terms of containers that can provide it. Random access iterators can move through a container at will. They provide all of the functionality of bidirectional iterators, but also have the ability to reposition themselves to arbitrary points within the container. This type of iterator is provided by the vector, deque, string, and array or pointer types.


So, now that we know the various types of iterators that containers will provide, how can we obtain these tags? Well, that's actually simple enough. There is a class called iterator_traits. When passed an iterator as a template argument, it provides a typedef that indicates the iterator type, called std::iterator_traits::iterator_catagory.

Of what use are these traits to us? The first is that it allows us to optimize our algorithms. Take for instance a sorting algorithm. Should the range of iterators you are presented with be random access iterators then it would make sense to use a quick-sort or an intro-sort. On the other hand, if they were bidirectional iterators then it would make sense to use something more like a merge sort. By using these traits, you can select at compile-time which algorithm will suit your iterators (and hence the underlying container) best. You can see an example of this in my first entry on traits, where I used a version of the copy for random access iterators that was specialized to allow for loop unrolling on the part of the compiler. While not quite as optimized as the memcpy/memmove copy functions, it still gave the compiler a chance to provide further optimizations (in this case, it could unroll the for loop). You will also note that there is a generic fall back method in case they aren't random access iterators.

The iterator traits structure looks like the following:

template<class Iterator>
struct iterator_traits {
typedef typename Iterator::iterator_category iterator_category;
typedef typename Iterator::value_type value_type;
typedef typename Iterator::difference_type difference_type;
typedef typename Iterator::pointer pointer;
typedef typename Iterator::reference reference;
};
template<class Type>
struct iterator_traits {
typedef random_access_iterator_tag iterator_category;
typedef Type value_type;
typedef ptrdiff_t difference_type;
typedef Type *pointer;
typedef Type& reference;
};
template<class Type>
struct iterator_traits<const Type*> {
typedef random_access_iterator_tag iterator_category;
typedef Type value_type;
typedef ptrdiff_t difference_type;
typedef const Type *pointer;
typedef const Type& reference;
};



As you can see, it is specialized for pointers and constant pointers, otherwise it would break as the std::iterator_traits attempts to obtain the information from a series of typedefs that non-pointer iterators have (as seen from the first std::iterator_traits structure).

Exercises:
1)Using iterator traits write a min_of_set function that will take two iterators and return the value of the smallest element from that range [start, end). The function signature should look something like: template value_type min_of_set(Itor start, Itor end);.
2)Using the remove_all_pointers from the exercise in the previous journal, along with remove_all_extents, write a function that will print out the base type of an element passed to it. For instance: int *****p; PrintType(p); should print "int".
Sign in to follow this  


1 Comment


Recommended Comments

Apologies for the late reply, Senpai! Been under a lot of work pressure recently.

Here's the source, I'm not sure if there's a catch or not, but these worked for the simple test cases I tried them on.


template <typename iterator_type>
typename iterator_type::value_type min_of_set(iterator_type start, iterator_type end)
{
iterator_type::value_type min_value = *start;
for(iterator_type current = start + 1; current != end; current++)
{
if(min_value > *current)
min_value = *current;
}

return min_value;
}

template <typename T>
void print_type(const T& value)
{
typedef typename remove_all_pointers<typename remove_all_extents<T>::type>::type type;
std::cout<< typeid(type).name();
}

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now