iterator_traits

by skienzle

Why does this have to be so unneccessarily difficult, C++?

#The short answer

because raw pointers are also valid iterators.
Jup, that's really the only reason for the existance of the iterator_traits structures, but let's elaborate further.

Click here to see the Implementation

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

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

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

Quite a mess, isn't it? ;)

#The long answer

#Detour to the iterator struct

Yet another Implementation

template<
        class Categoty,
        class Type,
        class Distance = ptrdiff_t,
        class Pointer = Type*,
        class Reference = Type&
>
struct iterator
{
        typedef typename Type       value_type;
        typedef typename Distance   distance_type;
        typedef typename Pointer    pointer;
        typedef typename Reference  reference;
        typedef typename Category   iterator_category;
};

As you can see the iterator structure just has four typedefs of its template parameters.
It serves as an interface for the specific iterator implementations (e.g. the reverse_iterator, ...), so they are all guranteed to have those four typedefs.

Please note that (as you can see here) directly inheriting from iterator was deprecated in C++17.

The iterator_traits serve as a gateway between iterators and the functions inside the algorithm header.
However, as you can read here, all pointers are also considered valid random access iterators. This is why this is/has to be valid code:

int array[] = { 1, 5, 2, 4, 3 };
std::sort(array, array + 5);

Internally the std::sort function might need to access the typedefs of the iterators it was supplied with, but if you recall you can't simply extract typedefs from a fundamental type like a pointer.
This is where iterator_traits come into play, by providing the four typedefs every iterator has to have.

See the lower two structs of the implementation. The first is used for normal and the second for const pointers.

#Usage example

Let's take a look at how to use those iterator_traits in practice. Let's re-implement the std::distance function, shall we?

This function might also prove useful during your ft_containers ;)

After consulting the C++ reference we can see that there are two ways of implementing this function:

Through a call to the operator-, if it exists.
Through repeated calls to the operator++ and a counter.

Also, the function is prototyped as follows:

template<class Iter>
typename iterator_traits<Iter>::difference_type // <-- Return type
distance(Iter first, Iter last);

Note that the return type already utilizes iterator_traits to retrieve the difference_type.
Alright, I'll provide you with the generic implementation and a testing main for our distance function and you add the two specializations mentioned above.

Deal?

#generic ft::distance implementation

#include <iterator>

namespace ft {

template<class Iter>
typename std::iterator_traits<Iter>::difference_type
distance(Iter first, Iter last)
{
        return distance_impl(first, last,
        typename std::iterator_traits<Iter>::iterator_category());
}

} // namespace ft

#main.cpp

#include <iostream>
#include <iomanip>
#include <vector>
#include <array>
#include <map>

/* include your distance headerfile here */

#define RED "\033[31m"
#define GREEN "\033[32m"
#define BLUE "\033[34m"
#define RESET "\033[0m"

template<class Iter>
static void
print_test_case(const char* test_case, Iter begin, Iter end)
{
        std::cout << BLUE << std::setw(23) << std::left << test_case;
        if (ft::distance(begin, end) == std::distance(begin, end))
                std::cout << GREEN << "SUCCESS";
        else
                std::cout << RED << "FAIL";
        std::cout << RESET << '\n';
}

int main()
{
        std::vector<int> vec{2, 5, 3, 2};
        std::array<int, 4> arr{2, 1, 6, 9};
        std::map<int,int> map{ {2, 3}, {1, 5}, {4, 7} };

        int c_arr[] = { 1, 5, 2, 3, 6 };
        const int* const_c_arr = c_arr;

        print_test_case("Test 1 - vector<int>", begin(vec), end(vec));
        print_test_case("Test 2 - array<int>", begin(arr), end(arr));
        print_test_case("Test 3 - map<int,int>", begin(map), end(map));
        print_test_case("Test 4 - int*", c_arr, c_arr + 5);
        print_test_case("Test 5 - const int*", const_c_arr, const_c_arr + 5);
}

← Explainers

Found something to improve? Edit this page on Github!