{"id":6328,"date":"2022-03-21T10:51:48","date_gmt":"2022-03-21T10:51:48","guid":{"rendered":"https:\/\/www.modernescpp.com\/index.php\/softwaredesign-with-traits-and-tag-dispatching\/"},"modified":"2023-06-26T09:10:26","modified_gmt":"2023-06-26T09:10:26","slug":"softwaredesign-with-traits-and-tag-dispatching","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/softwaredesign-with-traits-and-tag-dispatching\/","title":{"rendered":"Software Design with Traits and Tag Dispatching"},"content":{"rendered":"

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.<\/p>\n

<\/p>\n

 \"PolicyAndTraits\"<\/p>\n

Tag dispatching is based on traits. Consequentially, I want to write a few words about traits.<\/p>\n

Traits<\/h2>\n

Traits are class templates that provide characteristics of a generic type. They can extract one or more characteristics of a class template.<\/p>\n

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

    \n
  1. Type Checks<\/a><\/li>\n
  2. Type Comparisons<\/a><\/li>\n
  3. std::is_base_of<\/code><\/a><\/li>\n
  4. Correctness<\/a><\/li>\n
  5. Performance<\/a><\/li>\n<\/ol>\n

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

    <\/p>\n

    \n
    template<\/span><<\/span>T><\/span> \r\nstruct<\/span> iterator_traits<<\/span>T*><\/span> { \r\n    using<\/span> difference_type =<\/span> std::<\/span>ptrdiff_t<\/span>; \r\n    using<\/span> value_type =<\/span> T; \r\n    using<\/span> pointer =<\/span> T*<\/span>; \r\n    using<\/span> reference =<\/span> T&<\/span>; \r\n    using<\/span> iterator_category =<\/span> std::<\/span>random_access_iterator_tag; \r\n};\r\n<\/pre>\n<\/div>\n
     <\/p>\n
    The iterator categories build the following hierarchy:<\/p>\n
    <\/p>\n
    \n
    struct<\/span> input_iterator_tag{}; \r\nstruct<\/span> output_iterator_tag{}; \r\nstruct<\/span> forward_iterator_tag:<\/span> public<\/span> input_iterator_tag{}; \r\nstruct<\/span> bidirectional_iterator_tag:<\/span> public<\/span> forward_iterator_tag{}; \r\nstruct<\/span> random_access_iterator_tag:<\/span> public<\/span> bidirectional_iterator_tag{}; \r\n<\/pre>\n<\/div>\n
     <\/p>\n
     The various iterator categories correspond to the container of the Standard Template Library.<\/p>\n
    \"IteratorCategories\"<\/p>\n
    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,<\/code> and std::string<\/code> support a random-access iterator but not std::list<\/code>.<\/p>\n<\/p>\n
    Tag Dispatching<\/h2>\n
    Now, I can apply tag dispatching and implement a fine-tailored advance_<\/code> algorithm optimized for the used container. First of all, std::advance<\/code><\/a> is already part of the standard template library:<\/p>\n
    <\/p>\n
    \n
    template<\/span><<\/span> class<\/span> InputIt<\/span>, class<\/span> Distance<\/span> ><\/span>\r\nvoid<\/span> advance( InputIt&<\/span> it, Distance n );            (until C++<\/span>17<\/span>)\r\ntemplate<\/span><<\/span> class<\/span> InputIt<\/span>, class<\/span> Distance<\/span> ><\/span>\r\nconstexpr void<\/span> advance( InputIt&<\/span> it, Distance n );  (since C++<\/span>17<\/span>)\r\n<\/pre>\n<\/div>\n
     <\/p>\n
    std::advance<\/code> increments a given iterator it<\/code> by n<\/code> elements. If n is negative, the iterator is decremented. Consequentially, the container providing the iterator must be, in this case, bidirectional.<\/p>\n
    Here is my implementation of advance_<\/code>:<\/p>\n
     <\/p>\n
    <\/p>\n
    \n
    \/\/ advance_.cpp<\/span>\r\n\r\n#include <iterator><\/span>\r\n#include <forward_list><\/span>\r\n#include <list><\/span>\r\n#include <vector><\/span>\r\n#include <iostream><\/span>\r\n\r\ntemplate<\/span> <<\/span>typename<\/span> InputIterator, typename<\/span> Distance><\/span>                    \r\nvoid<\/span> advance_impl(InputIterator&<\/span> i, Distance n, std::<\/span>input_iterator_tag) {\r\n    std::<\/span>cout <<<\/span> \"InputIterator used\"<\/span> <<<\/span> '\\n'<\/span>; \r\n    <\/span>if (n >= 0) { while (n--) ++it; }\r\n}\r\n\r\ntemplate<\/span> <<\/span>typename<\/span> BidirectionalIterator, typename<\/span> Distance><\/span>              <\/span>\r\nvoid<\/span> advance_impl(BidirectionalIterator&<\/span> i, Distance n, std::<\/span>bidirectional_iterator_tag) {\r\n    std::<\/span>cout <<<\/span> \"BidirectionalIterator used\"<\/span> <<<\/span> '\\n'<\/span>;\r\n    if<\/span> (n >=<\/span> 0<\/span>) \r\n        while<\/span> (n--<\/span>) ++<\/span>i;\r\n    else<\/span> \r\n        while<\/span> (n++<\/span>) --<\/span>i;\r\n}\r\n\r\ntemplate<\/span> <<\/span>typename<\/span> RandomAccessIterator, typename<\/span> Distance><\/span>             \r\nvoid<\/span> advance_impl(RandomAccessIterator&<\/span> i, Distance n, std::<\/span>random_access_iterator_tag) {\r\n    std::<\/span>cout <<<\/span> \"RandomAccessIterator used\"<\/span> <<<\/span> '\\n'<\/span>;\r\n    i +=<\/span> n;                                                             \/\/ (5)\r\n}\r\n\r\ntemplate<\/span> <<\/span>typename<\/span> InputIterator, typename<\/span> Distance><\/span>                    \/\/ (4)<\/span>\r\nvoid<\/span> advance_(InputIterator&<\/span> i, Distance n) {\r\n    typename<\/span> std::<\/span>iterator_traits<<\/span>InputIterator>::<\/span>iterator_category category;    \r\n    advance_impl(i, n, category);                                               \r\n}\r\n  \r\nint<\/span> main(){\r\n    \r\n    std::<\/span>cout <<<\/span> '\\n'<\/span>;\r\n    \r\n    std::<\/span>vector<<\/span>int<\/span>><\/span> myVec{0<\/span>, 1<\/span>, 2<\/span>, 3<\/span>, 4<\/span>, 5<\/span>, 6<\/span>, 7<\/span>, 8<\/span>, 9<\/span>};               \/\/ (1)<\/span>\r\n    auto<\/span> myVecIt =<\/span> myVec.begin();                                               \r\n    std::<\/span>cout <<<\/span> \"*myVecIt: \"<\/span> <<<\/span> *<\/span>myVecIt <<<\/span> '\\n'<\/span>;\r\n    advance_(myVecIt, 5<\/span>);\r\n    std::<\/span>cout <<<\/span> \"*myVecIt: \"<\/span> <<<\/span> *<\/span>myVecIt <<<\/span> '\\n'<\/span>;\r\n    \r\n    std::<\/span>cout <<<\/span> '\\n'<\/span>;\r\n    \r\n    std::<\/span>list<<\/span>int<\/span>><\/span> myList{0<\/span>, 1<\/span>, 2<\/span>, 3<\/span>, 4<\/span>, 5<\/span>, 6<\/span>, 7<\/span>, 8<\/span>, 9<\/span>};                \/\/ (2)<\/span>\r\n    auto<\/span> myListIt =<\/span> myList.begin();                                             \r\n    std::<\/span>cout <<<\/span> \"*myListIt: \"<\/span> <<<\/span> *<\/span>myListIt <<<\/span> '\\n'<\/span>;\r\n    advance_(myListIt, 5<\/span>);\r\n    std::<\/span>cout <<<\/span> \"*myListIt: \"<\/span> <<<\/span> *<\/span>myListIt <<<\/span> '\\n'<\/span>;\r\n    \r\n    std::<\/span>cout <<<\/span> '\\n'<\/span>;\r\n    \r\n    std::<\/span>forward_list<<\/span>int<\/span>><\/span> myForwardList{0<\/span>, 1<\/span>, 2<\/span>, 3<\/span>, 4<\/span>, 5<\/span>, 6<\/span>, 7<\/span>, 8<\/span>, 9<\/span>}; \/\/ (3)<\/span>\r\n    auto<\/span> myForwardListIt =<\/span> myForwardList.begin();                               \r\n    std::<\/span>cout <<<\/span> \"*myForwardListIt: \"<\/span> <<<\/span> *<\/span>myForwardListIt <<<\/span> '\\n'<\/span>;\r\n    advance_(myForwardListIt, 5<\/span>);\r\n    std::<\/span>cout <<<\/span> \"*myForwardListIt: \"<\/span> <<<\/span> *<\/span>myForwardListIt <<<\/span> '\\n'<\/span>;\r\n    \r\n    std::<\/span>cout <<<\/span> '\\n'<\/span>;\r\n    \r\n}\r\n<\/pre>\n<\/div>\n
     <\/p>\n
    I use in the example a std::vector<\/code> (line 1), a std::list<\/code> (line 2), and a std::forward_list<\/code> (line 3). A std::vector<\/code> supports a random-access iterator, a std::list<\/code> bidirectional iterator, and a std::forward_list<\/code> forward iterator. The call  std::<\/span>iterator_traits<<\/span>InputIterator>::<\/span>iterator_category category<\/code>; in the function advance_  <\/code>(line 4) determines the supported iterator category based on the given iterator. The final call advance_impl(i, n, category) <\/code>finally dispatches to the most specialized overload of the implementation function advance_impl.<\/code><\/p>\n
    To visualize the dispatch, I added a short message to implementation functions advance_imp<\/code>l.<\/p>\n
    \"advance<\/p>\n
    What are the advantages of such a fine-tuned advance implementation?<\/p>\n
      \n
    1. Type safety<\/strong>: The compiler decides which version of advance_impl<\/code> 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.<\/li>\n
    2. Performance<\/strong>: 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 +=<\/span> n<\/code> (line 5) is a constant operation.<\/li>\n<\/ol>\n
      What’s next?<\/h2>\n
      In my next post, I bridge dynamic polymorphism (object orientation) with static polymorphism (templates) to introduce a sophisticated technique: type erasure.<\/p>\n
      The Future of Modernes C++<\/h2>\n
      The type erasure post will be my last post about templates for now. To get the previous ones, use the TOC <\/a>or the category Templates<\/a>. 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<\/a>.<\/p>\n<\/p>\n
       <\/p>\n","protected":false},"excerpt":{"rendered":"
      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.<\/p>\n","protected":false},"author":21,"featured_media":6320,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[376],"tags":[422,423],"class_list":["post-6328","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-templates","tag-tag-dispatching","tag-traits"],"_links":{"self":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/6328","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/users\/21"}],"replies":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/comments?post=6328"}],"version-history":[{"count":1,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/6328\/revisions"}],"predecessor-version":[{"id":6676,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/6328\/revisions\/6676"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media\/6320"}],"wp:attachment":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media?parent=6328"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/categories?post=6328"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/tags?post=6328"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}