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 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:
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:
The iterator categories build the following hierarchy:
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
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:
std::advance increments a given iterator
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
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
To visualize the dispatch, I added a short message to implementation functions
What are the advantages of such a fine-tuned advance implementation?
- Type safety: The compiler decides which version of
advance_implis used. Consequentially, you cannot invoke an implementation requiring a bidirectional iterator with a forward iterator. Backward iterating with a forward iterator is undefined behavior.
- 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.
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: Rainer.Grimm@modernescpp.de.
Thanks a lot to my Patreon Supporters: Matt Braun, Roman Postanciuc, Tobias Zindl, G Prvulovic, Reinhold Dröge, Abernitzke, Frank Grimm, Sakib, Broeserl, António Pina, Sergey Agafyin, Андрей Бурмистров, Jake, GS, Lawton Shoemake, 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, 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, Phillip Diekmann, Ben Atakora, Ann Shatoff, Rob North, and Bhavith C Achar.
Thanks, in particular, to Jon Hess, Lakshman, Christian Wittenhorst, Sherhy Pyton, Dendi Suhubdy, Sudhakar Belagurusamy, Richard Sargeant, Rusty Fleming, John Nebel, Mipko, Alicja Kaminska, Slavko Radman, and David Poole.
|My special thanks to Embarcadero|
|My special thanks to PVS-Studio|
|My special thanks to Tipi.build|
|My special thanks to Take Up Code|
I’m happy to give online seminars or face-to-face seminars worldwide. Please call me if you have any questions.
- Embedded Programmierung mit modernem C++ 12.12.2023 – 14.12.2023 (Präsenzschulung, Termingarantie)
Standard Seminars (English/German)
Here is a compilation of my standard seminars. These seminars are only meant to give you a first orientation.
- C++ – The Core Language
- C++ – The Standard Library
- C++ – Compact
- C++11 and C++14
- Concurrency with Modern C++
- Design Pattern and Architectural Pattern with C++
- Embedded Programming with Modern C++
- Generic Programming (Templates) with C++
- Clean Code with Modern C++
- Phone: +49 7472 917441
- Mobil:: +49 176 5506 5086
- Mail: schulung@ModernesCpp.de
- German Seminar Page: www.ModernesCpp.de
- Mentoring Page: www.ModernesCpp.org
Modernes C++ Mentoring,