Software Design with Traits and Tag Dispatching

Tag Dispatching enables it to choose a function based on the type characteristics. This decision takes place at compile time and is based on traits.

Tag dispatching is based on traits. Consequentially, I want to write a few words about traits.

Traits

Traits are class templates that provide characteristics of a generic type. They can extract one or more characteristics of a class template.

You may already assume it; the metafunctions from the type-traits library are typical examples of traits in C++. I have already written a few posts about them. Here are they:

1. Type Checks
2. Type Comparisons
3. std::is_base_of
4. Correctness
5. Performance

 Before I directly jump in this post in tag dispatching, I want to introduce the iterator traits. The following code snippet shows their partial specialization for pointers:

template<T> 
struct iterator_traits<T*> { 
    using difference_type = std::ptrdiff_t; 
    using value_type = T; 
    using pointer = T*; 
    using reference = T&; 
    using iterator_category = std::random_access_iterator_tag; 
};

The iterator categories build the following hierarchy:

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{}; 

 The various iterator categories correspond to the container of the Standard Template Library.

The following relation holds for the iterator categories and their support operations. A random-access iterator is a bidirectional iterator, and a bidirectional iterator is a forward iterator. This means std::array, std::vector, and std::string support a random-access iterator but not std::list.

Tag Dispatching

Now, I can apply tag dispatching and implement a fine-tailored advance_ algorithm optimized for the used container. First of all, std::advance is already part of the standard template library:

template< class InputIt, class Distance >
void advance( InputIt& it, Distance n );            (until C++17)
template< class InputIt, class Distance >
constexpr void advance( InputIt& it, Distance n );  (since C++17)

std::advance increments a given iterator it by n elements. If n is negative, the iterator is decremented. Consequentially, the container providing the iterator must be, in this case, bidirectional.

Here is my implementation of advance_:

// advance_.cpp

#include <iterator>
#include <forward_list>
#include <list>
#include <vector>
#include <iostream>

template <typename InputIterator, typename Distance>                    
void advance_impl(InputIterator& i, Distance n, std::input_iterator_tag) {
    std::cout << "InputIterator used" << '\n'; 
    if (n >= 0) { while (n--) ++it; }
}

template <typename BidirectionalIterator, typename Distance>              
void advance_impl(BidirectionalIterator& i, Distance n, std::bidirectional_iterator_tag) {
    std::cout << "BidirectionalIterator used" << '\n';
    if (n >= 0) 
        while (n--) ++i;
    else 
        while (n++) --i;
}

template <typename RandomAccessIterator, typename Distance>             
void advance_impl(RandomAccessIterator& i, Distance n, std::random_access_iterator_tag) {
    std::cout << "RandomAccessIterator used" << '\n';
    i += n;                                                             // (5)
}

template <typename InputIterator, typename Distance>                    // (4)
void advance_(InputIterator& i, Distance n) {
    typename std::iterator_traits<InputIterator>::iterator_category category;    
    advance_impl(i, n, category);                                               
}
  
int main(){
    
    std::cout << '\n';
    
    std::vector<int> myVec{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};               // (1)
    auto myVecIt = myVec.begin();                                               
    std::cout << "*myVecIt: " << *myVecIt << '\n';
    advance_(myVecIt, 5);
    std::cout << "*myVecIt: " << *myVecIt << '\n';
    
    std::cout << '\n';
    
    std::list<int> myList{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};                // (2)
    auto myListIt = myList.begin();                                             
    std::cout << "*myListIt: " << *myListIt << '\n';
    advance_(myListIt, 5);
    std::cout << "*myListIt: " << *myListIt << '\n';
    
    std::cout << '\n';
    
    std::forward_list<int> myForwardList{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; // (3)
    auto myForwardListIt = myForwardList.begin();                               
    std::cout << "*myForwardListIt: " << *myForwardListIt << '\n';
    advance_(myForwardListIt, 5);
    std::cout << "*myForwardListIt: " << *myForwardListIt << '\n';
    
    std::cout << '\n';
    
}

I use in the example a std::vector (line 1), a std::list (line 2), and a std::forward_list (line 3). A std::vector supports a random-access iterator, a std::list bidirectional iterator, and a std::forward_list forward iterator. The call std::iterator_traits<InputIterator>::iterator_category category; in the function advance_  (line 4) determines the supported iterator category based on the given iterator. The final call advance_impl(i, n, category) finally dispatches to the most specialized overload of the implementation function advance_impl.

To visualize the dispatch, I added a short message to implementation functions advance_impl.

What are the advantages of such a fine-tuned advance implementation?

1. Type safety: The compiler decides which version of advance_impl is used. Consequentially, you cannot invoke an implementation requiring a bidirectional iterator with a forward iterator. Backward iterating with a forward iterator is undefined behavior.
2. Performance: Putting a forward or bidirectional iterator n position further requires n increment operation. Its complexity is, therefore, linear. This observation does not hold for a random access iterator: Pointer arithmetic such as i += n (line 5) is a constant operation.

What's next?

In my next post, I bridge dynamic polymorphism (object orientation) with static polymorphism (templates) to introduce a sophisticated technique: type erasure.

The Future of Modernes C++

The type erasure post will be my last post about templates for now. To get the previous ones, use the TOC or the category Templates. Afterward, I will continue to write about C++20 and will peek into the C++23 future. If you have some exciting post ideas, please write me an e-mail: This email address is being protected from spambots. You need JavaScript enabled to view it..