Software Design with Traits and Tag Dispatching

Contents[Show]

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.

 PolicyAndTraits

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.

IteratorCategories

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.

 

Rainer D 6 P2 540x540Modernes C++ Mentoring

Stay informed about my mentoring programs. Subscribe for the news.

 

 

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 a bidirectional iterator, and a std::forward_list a 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.

advance

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 iterator or a 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 pretty 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 continue to write about C++20 and will peek into the C++23 future. If you have some interesting post ideas, please write me an e-mail: This email address is being protected from spambots. You need JavaScript enabled to view it..

Thanks a lot to my Patreon Supporters: Matt Braun, Roman Postanciuc, Tobias Zindl, Marko, G Prvulovic, Reinhold Dröge, Abernitzke, Frank Grimm, Sakib, Broeserl, António Pina, Sergey Agafyin, Андрей Бурмистров, Jake, GS, Lawton Shoemake, Animus24, Jozo Leko, John Breland, Venkat Nandam, Jose Francisco, Douglas Tinkham, Kuchlong Kuchlong, Robert Blanch, Truels Wissneth, Kris Kafka, Mario Luoni, Friedrich Huber, lennonli, Pramod Tikare Muralidhara, Peter Ware, Daniel Hufschläger, Alessandro Pezzato, Evangelos Denaxas, Bob Perry, Satish Vangipuram, Andi Ireland, Richard Ohnemus, Michael Dunsky, Leo Goodstadt, John Wiederhirn, Yacob Cohen-Arazi, Florian Tischler, Robin Furness, Michael Young, Holger Detering, Bernd Mühlhaus, Matthieu Bolt, Stephen Kelley, Kyle Dean, Tusar Palauri, Dmitry Farberov, Juan Dent, George Liao, Daniel Ceperley, Jon T Hess, Stephen Totten, Wolfgang Fütterer, Matthias Grün, and Phillip Diekmann.

 

Thanks in particular to Jon Hess, Lakshman, Christian Wittenhorst, Sherhy Pyton, Dendi Suhubdy, Sudhakar Belagurusamy, Richard Sargeant, Rusty Fleming, Ralf Abramowitsch, John Nebel, Mipko, and Alicja Kaminska.

 

 

My special thanks to Embarcadero CBUIDER STUDIO FINAL ICONS 1024 Small

 

My special thanks to PVS-Studio PVC Logo

 

Seminars

I'm happy to give online seminars or face-to-face seminars worldwide. Please call me if you have any questions.

Bookable (Online)

German

Standard Seminars (English/German)

Here is a compilation of my standard seminars. These seminars are only meant to give you a first orientation.

New

Contact Me

Modernes C++,

RainerGrimmDunkelBlauSmall

 

Mentoring

Stay Informed about my Mentoring

 

English Books

Course: Modern C++ Concurrency in Practice

Course: C++ Standard Library including C++14 & C++17

Course: Embedded Programming with Modern C++

Course: Generic Programming (Templates)

Course: C++ Fundamentals for Professionals

Interactive Course: The All-in-One Guide to C++20

Subscribe to the newsletter (+ pdf bundle)

Blog archive

Source Code

Visitors

Today 5434

Yesterday 6352

Week 30360

Month 51107

All 10972568

Currently are 220 guests and no members online

Kubik-Rubik Joomla! Extensions

Latest comments