{"id":6333,"date":"2022-03-31T10:20:26","date_gmt":"2022-03-31T10:20:26","guid":{"rendered":"https:\/\/www.modernescpp.com\/index.php\/a-std-advance-implementation-with-c-98-c-17-and-c-20\/"},"modified":"2023-06-26T09:09:48","modified_gmt":"2023-06-26T09:09:48","slug":"a-std-advance-implementation-with-c-98-c-17-and-c-20","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/a-std-advance-implementation-with-c-98-c-17-and-c-20\/","title":{"rendered":"A std::advance Implementation with C++98, C++17, and C++20"},"content":{"rendered":"

In my last post, I presented a possible std::advance<\/code> implementation based on tag dispatching. One of my readers mentioned that I could also implement std::advance based on constexpr if<\/code>, or concepts. His right. So let’s do it.<\/p>\n

<\/p>\n

 \"\"<\/p>\n

A short reminder: std::advance(it, n)<\/code> increments a given iterator it<\/code> by n<\/code> elements. If n<\/code> is negative, the iterator is decremented. Depending on the container and the iterator provided by the container, a fine-tailored version std::advance<\/code> is used. The reason for this fine-tailored strategy is twofold: type safety and performance. In my last post, “Software Design with Traits and Tag Dispatching<\/a>“, I implemented my version std::advance<\/code> based on tag dispatching. Before I dive into a possible std::advance<\/code> implementation based on constexpr if (C++17) or concepts (C++20), I want to show once more the tag dispatching (C++98) implementation.<\/p>\n

Tag Dispatching (C++98)<\/h2>\n

I call the function advance_<\/code> to distinguish it from std::advance<\/code>.<\/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--) ++i; }\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
Without further ado. Here is the output of the program. <\/p>\n
\"advance<\/p>\n
Read my previous post, “Software Design with Traits and Tag Dispatching<\/a>” to know the details.<\/p>\n<\/p>\n
constexpr if<\/code> (C++17)<\/h2>\n
constexpr if<\/code> enables it to compile source code conditionally.<\/p>\n
\n
template<\/span> <<\/span>typename<\/span> T><\/span>\r\nauto<\/span> getValue(T t) {\r\n    if<\/span> constexpr (std::<\/span>is_pointer_v<<\/span>T><\/span>)      \/\/ (1)<\/span><\/em>\r\n        return<\/span> *<\/span>t; \/\/ deduces return type to int for T = int*<\/span>\r\n    else                                    <\/span> <\/span>\/\/ (2)<\/span><\/em><\/span>\r\n        return<\/span> t;  \/\/ deduces return type to int for T = int<\/span>\r\n}\r\n<\/pre>\n<\/div>\n
<\/p>\n
The expression in constexpr if has to be a compile-time predicate. A compile-time predicate is a function that returns a boolean and runs at compile time. I use, in this case, the type-traits function std::is_pointer.<\/code> Both branches have (lines 1 and 2) to be valid.<\/p>\n
<\/p>\n
\n
\/\/ implementation via constexpr if, available in C++17<\/span>\r\ntemplate<\/span><<\/span>class<\/span> It<\/span>, class<\/span> Distance<\/span>><\/span>\r\nconstexpr void<\/span> advance_(It&<\/span> it, Distance n)\r\n{\r\n    using<\/span> category =<\/span> typename<\/span> std::<\/span>iterator_traits<<\/span>It>::<\/span>iterator_category;           \/\/ (1)<\/span>\r\n    static_assert(std::<\/span>is_base_of_v<<\/span>std::<\/span>input_iterator_tag, category><\/span>);             \/\/ (2)<\/span>\r\n \r\n    auto<\/span> dist =<\/span> typename<\/span> std::<\/span>iterator_traits<<\/span>It>::<\/span>difference_type(n);               \/\/ (3)<\/span>\r\n    if<\/span> constexpr (std::<\/span>is_base_of_v<<\/span>std::<\/span>random_access_iterator_tag, category><\/span>)      \/\/ (4)<\/span>\r\n        it +=<\/span> dist;\r\n    else<\/span> {\r\n        while<\/span> (dist ><\/span> 0<\/span>) {                                                           \/\/ (6)<\/span><\/em>\r\n            --<\/span>dist;\r\n            ++<\/span>it;\r\n        }\r\n        if<\/span> constexpr (std::<\/span>is_base_of_v<<\/span>std::<\/span>bidirectional_iterator_tag, category><\/span>) { \/\/ (5)<\/span>\r\n            while<\/span> (dist <<\/span> 0<\/span>) {\r\n                ++<\/span>dist;\r\n                --<\/span>it;\r\n            }\r\n        }\r\n    }\r\n}\r\n<\/pre>\n<\/div>\n
 <\/p>\n
This implementation determines the iterator category based on the used iterator (line 1) and asserts that the iterator category is derived from std::input_iterator_tag<\/code> (line 2). Line 3 determines the value for incrementing the iterator. Now, constexpr if<\/code> it comes into play.  Depending on the type of the iterator, line (4), line (5), or line (6) is used. Line (4) requires std::random_access_iterator,<\/code> line (5) std::bidirectional_iterator<\/code>, and line (6) takes the remaining iterators.<\/p>\n
The following graphic shows which container triggers the compilation of which constexpr if<\/code> branch:<\/p>\n
\"IteratorCategories\"<\/p>\n
Honestly, the C++98 version based on tag dispatching is easier to understand. Let me jump one more three years into the future and implement advance<\/code> using concepts.<\/p>\n
Concepts (C++20)<\/h2>\n
C++20 supports the following concepts for iterators:<\/p>\n
<\/p>\n
\n
std::<\/span>input_or_output_iterator\r\nstd::<\/span>input_iterator\r\nstd::<\/span>output_iterator\r\nstd::<\/span>forward_iterator\r\nstd::<\/span>bidirectional_iterator\r\nstd::<\/span>random_access_iterator\r\nstd::<\/span>contiguous_iterator\r\n<\/pre>\n<\/div>\n
 <\/p>\n
A std::input_output_iterator<\/code> support the operations ++It, It++<\/code> , and *It. std::input_iterator<\/code> and std::output_iterator<\/code> are already std::input_or_output_iterator.<\/code> The following relations hold: A contiguous iterator is a random-access iterator, a random-access iterator is a bidirectional iterator, and a bidirectional iterator is a forward iterator. A contiguous iterator requires that the container elements are stored contiguously in memory.<\/p>\n
Thanks to concepts, the implementation of advance_ is pretty straightforward. I overload advance_ on the concepts and use concepts as restricted type parameters.<\/p>\n
<\/p>\n
\n
\/\/ conceptsAdvance.cpp<\/span>\r\n\r\n#include <concepts><\/span>\r\n#include <iostream><\/span>\r\n#include <forward_list><\/span>\r\n#include <list><\/span>\r\n#include <vector><\/span>\r\n\r\ntemplate<\/span><<\/span>std::<\/span>input_iterator I>                              \/\/ (1)<\/span><\/span>\r\nvoid<\/span> advance_(I&<\/span> i, int<\/span> n){\r\n    std::<\/span>cout <<<\/span> \"InputIterator used\"<\/span> <<<\/span> '\\n'<\/span>;\r\n    <\/span>if (n >= 0) { while (n--) ++i; }\r\n}\r\n\r\ntemplate<\/span><<\/span>std::<\/span>bidirectional_iterator I>                       \/\/ (2)<\/span><\/span>\r\nvoid<\/span> advance_(I&<\/span> i, int<\/span> n){\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>std::<\/span>random_access_iterator I>                       \/\/ (3)<\/span><\/span>\r\nvoid<\/span> advance_(I&<\/span> i, int<\/span> n){\r\n    std::<\/span>cout <<<\/span> \"RandomAccessIterator used\"<\/span> <<<\/span> '\\n'<\/span>;\r\n    i +=<\/span> n;  \r\n}\r\n\r\nint<\/span> main() {\r\n\r\n    std::<\/span>cout <<<\/span> '\\n'<\/span>;\r\n\r\n    std::<\/span>forward_list forwList{1<\/span>, 2<\/span>, 3<\/span>};\r\n    std::<\/span>forward_list<<\/span>int<\/span>>::<\/span>iterator itFor =<\/span> forwList.begin();\r\n    advance_(itFor, 2<\/span>);                                       \/\/ (4)<\/em>\r\n<\/span>\r\n    std::<\/span>list li{1<\/span>, 2<\/span>, 3<\/span>};\r\n    std::<\/span>list<<\/span>int<\/span>>::<\/span>iterator itBi =<\/span> li.begin();\r\n    advance_(itBi, 2<\/span>);                                        \/\/ (5)<\/em><\/span>\r\n\r\n    std::<\/span>vector vec{1<\/span>, 2<\/span>, 3<\/span>};\r\n    std::<\/span>vector<<\/span>int<\/span>>::<\/span>iterator itRa =<\/span> vec.begin();\r\n    advance_(itRa, 2<\/span>);                                        \/\/ (6)<\/em>\r\n<\/span>\r\n    std::<\/span>cout <<<\/span> '\\n'<\/span>;\r\n}\r\n<\/pre>\n<\/div>\n
 <\/p>\n
The three variations of the function advance_<\/code> are overloaded with the concepts std::input_iterator<\/code> (line 1), std::bidirectional_iterator<\/code> (line 2), and std::random_access_iterator<\/code> (line 3). The compiler chooses the best-fitting overload. This means that for a std::forward_list<\/code> (line 4) the overload based on the concept std::forward_iterator<\/code>, for a std::list<\/code> (line 5) the overload based on the concept std::bidirectional_iterator<\/code>, and for a std::vector<\/code> (line 6) the overload based on the concept std::random_access_iterator<\/code> is used.<\/p>\n
\"concpetsAdvance\"<\/p>\n
I don’t know which version of advance_ you prefer. The tag dispatching-based C++98 implementation, the constexpr if based C++17 implementation, or the concepts-based C++20 implementation. The concepts-based version is my favorite from a readability and maintainability point of view. The disadvantage is that you need a C++20 compiler. cppreference.com<\/a> provides you insight into the C++ compiler support of your C++ compiler.<\/p>\n
What’s next?<\/h2>\n
After this short interplay with the advance algorithm, I bridge in my next post dynamic polymorphism (object orientation) with static polymorphism (templates) to introduce a pretty sophisticated technique: type erasure.<\/span><\/p>\n
 <\/p>\n
Do you look for new C++ developer job opportunities? Give Jooble <\/a>a try. <\/strong><\/p>\n
 <\/p><\/p>\n","protected":false},"excerpt":{"rendered":"
In my last post, I presented a possible std::advance implementation based on tag dispatching. One of my readers mentioned that I could also implement std::advance based on constexpr if, or concepts. His right. So let’s do it.<\/p>\n","protected":false},"author":21,"featured_media":6331,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[376],"tags":[415,421,422],"class_list":["post-6333","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-templates","tag-concepts","tag-constexpr-if","tag-tag-dispatching"],"_links":{"self":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/6333","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=6333"}],"version-history":[{"count":1,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/6333\/revisions"}],"predecessor-version":[{"id":6675,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/6333\/revisions\/6675"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media\/6331"}],"wp:attachment":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media?parent=6333"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/categories?post=6333"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/tags?post=6333"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
For completeness, here is the program executed with Compiler Explorer<\/a>.<\/p>\n
The following implementation of std::advance<\/code> is a copy from cppreference.com<\/a>. I only renamed the function to advance_<\/code> to match the function name in my previous program advance_.cpp,<\/code> and added a few line markers. Consequentially, you can replace the previous C++98-based implementation with the following one:<\/p>\n