A std::advance Implementation with C++98, C++17, and C++20

Contents[Show]

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.

 advance

A short reminder: std::advance(it, n) increments a given iterator it by n elements. If n is negative, the iterator is decremented. Depending on the container and the iterator provided by the container, a fine-tailored version std::advance 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", I implemented my version std::advance based on tag dispatching. Before I dive into a possible std::advance implementation based on constexpr if (C++17), or concepts (C++20), I want to show once more the tag dispatching (C++98) implementation.

Tag Dispatching (C++98)

I call the function advance_ to distinguish it from std::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--) ++i; }
}

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

 

Without further ado. Here is the output of the program. 

advance

Read my previous post, "Software Design with Traits and Tag Dispatching" if you want to know the details.

constexpr if (C++17)

constexpr if enables it to conditionally compile source code.

template <typename T>
auto getValue(T t) {
    if constexpr (std::is_pointer_v<T>)      // (1)
        return *t; // deduces return type to int for T = int*
    else                                     // (2)
        return t;  // deduces return type to int for T = int
}

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. Both branches have (lines 1 and 2) to be valid.

The following implementation of std::advance is a copy from cppreference.com. I only renamed the function to advance_ to match the function name in my previous program advance_.cpp, and added a few line markers. Consequentially, you can replace the previous C++98 based implementation with the following one:

// implementation via constexpr if, available in C++17
template<class It, class Distance>
constexpr void advance_(It& it, Distance n)
{
    using category = typename std::iterator_traits<It>::iterator_category;           // (1)
    static_assert(std::is_base_of_v<std::input_iterator_tag, category>);             // (2)
 
    auto dist = typename std::iterator_traits<It>::difference_type(n);               // (3)
    if constexpr (std::is_base_of_v<std::random_access_iterator_tag, category>)      // (4)
        it += dist;
    else {
        while (dist > 0) {                                                           // (6)
            --dist;
            ++it;
        }
        if constexpr (std::is_base_of_v<std::bidirectional_iterator_tag, category>) { // (5)
            while (dist < 0) {
                ++dist;
                --it;
            }
        }
    }
}

 

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 (line 2). Line 3 determines the value for incrementing the iterator. Now, constexpr if comes into play.  Depending on the type of the iterator, line (4), line (5), or line (6) is used. Line (4) requires a std::random_access_iterator, line (5) a std::bidirectional_iterator, and line (6) takes the remaining iterators.

The following graphic shows which container triggers the compilation of which constexpr if branch:

IteratorCategories

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 using concepts.

Concepts (C++20)

C++20 supports the following concepts for iterators:

std::input_or_output_iterator
std::input_iterator
std::output_iterator
std::forward_iterator
std::bidirectional_iterator
std::random_access_iterator
std::contiguous_iterator

 

A std::input_output_iterator support the operations ++It, It++ , and *It. std::input_iterator and std::output_iterator are already std::input_or_output_iterator. 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.

Thanks to concepts, the implementation of advance_ is pretty straightforward. I overload advance_ on the concepts and use concepts as restricted type parameters.

// conceptsAdvance.cpp

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

template<std::input_iterator I>                              // (1)
void advance_(I& i, int n){
    std::cout << "InputIterator used" << '\n';
    if (n >= 0) { while (n--) ++i; }
}

template<std::bidirectional_iterator I>                       // (2)
void advance_(I& i, int n){
    std::cout << "BidirectionalIterator used" << '\n';
    if (n >= 0) 
        while (n--) ++i;
    else 
        while (n++) --i;
}

template<std::random_access_iterator I>                       // (3)
void advance_(I& i, int n){
    std::cout << "RandomAccessIterator used" << '\n';
    i += n;  
}

int main() {

    std::cout << '\n';

    std::forward_list forwList{1, 2, 3};
    std::forward_list<int>::iterator itFor = forwList.begin();
    advance_(itFor, 2);                                       // (4)

    std::list li{1, 2, 3};
    std::list<int>::iterator itBi = li.begin();
    advance_(itBi, 2);                                        // (5)

    std::vector vec{1, 2, 3};
    std::vector<int>::iterator itRa = vec.begin();
    advance_(itRa, 2);                                        // (6)

    std::cout << '\n';
}

 

The three variations of the function advance_ are overloaded on the concepts std::input_iterator (line 1), std::bidirectional_iterator (line 2), and std::random_access_iterator (line 3). The compiler chooses the best-fitting overload. This means that for a std::forward_list (line 4) the overload based on the concept std::forward_iterator, for a std::list (line 5) the overload based on the concept std::bidirectional_iterator, and for a std::vector (line 6) the overload based on the concept std::random_access_iterator is used.

For completeness, here is the program executed with Compiler Explorer.

concpetsAdvance

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. From a readability and maintainability point of view, the concepts-based version is my favorite. The disadvantage is that you need a C++20 compiler. cppreference.com provides you insight into the C++ compiler support of your C++ compiler.

What's next?

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.

 

Do you look for new C++ developer job opportunities? Give Jooble a try.

 

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, Louis St-Amour, Venkat Nandam, Jose Francisco, Douglas Tinkham, Kuchlong Kuchlong, Robert Blanch, Truels Wissneth, Kris Kafka, Mario Luoni, Neil Wang, 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, and Wolfgang Fütterer.

 

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

Comments   

0 #1 Guy Davidson 2022-04-04 09:04
Do you think the function signature would be more readable using the terse syntax? i.e.

void advance_(std::input_iterator auto& i, int n);

rather than

template void advance_(I& i, int n);

Or does that present a greater burden of explanation for this blog :-)
Quote
0 #2 Rainer 2022-05-10 16:54
Quoting Guy Davidson:


Or does that present a greater burden of explanation for this blog :-)


I intentionally used the restricted type parameters and not the abbreviated function templates syntax.

In general, I prefer the abbreviated function templates syntax.
Quote
0 #3 Jvr 2022-07-08 19:00
In (1) of the last example there's probably mistake. Since you declared itearator variable as "i" but than using ++it.
Quote

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 5705

Yesterday 6271

Week 11978

Month 22907

All 10366214

Currently are 153 guests and no members online

Kubik-Rubik Joomla! Extensions

Latest comments