• Home
  • /
  • Blog
  • /
  • A std::advance Implementation with C++98, C++17, and C++20

March 31, 2022

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. 

advance

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

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:

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

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

 

Leave a Reply


Your email address will not be published. Required fields are marked

{"email":"Email address invalid","url":"Website address invalid","required":"Required field missing"}

Related Posts