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

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.

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.

Read my previous post, “Software Design with Traits and Tag Dispatching” to know the details.

Modernes C++ Mentoring

"Fundamentals for C++ Professionals" (open)

"Design Patterns and Architectural Patterns with C++" (open)

"C++20: Get the Details" (open)

"Concurrency with Modern C++" (open)

"Generic Programming (Templates) with C++": October 2024

"Embedded Programming with Modern C++": October 2024

"Clean Code: Best Practices for Modern C++": March 2025

Do you want to stay informed: Subscribe.

`constexpr if` (C++17)

constexpr if enables it to compile source code conditionally.

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 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, line (5) std::bidirectional_iterator, and line (6) takes the remaining iterators.

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

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 with 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.

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

Post Views: 5,310

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, 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, Stephen Kelley, Kyle Dean, Tusar Palauri, 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, Bhavith C Achar, Marco Parri Empoli, Philipp Lenk, Charles-Jianye Chen, Keith Jeffery, Matt Godbolt, and Honey Sukesan.

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
My special thanks to SHAVEDYAKS