Eine std::advance Implementierung mit C++98, C++17 und C++20
Nach der std::advance-Implementierung auf Basis von Tag-Dispatching zeigt der Beitrag diesmal Umsetzungen von std::advance vor, die auf constexpr if und Concepts basieren.
- Rainer Grimm
Nach der std::advance-Implementierung auf Basis von Tag-Dispatching zeigt der Beitrag diesmal Umsetzungen von std::advance vor, die auf constexpr if und Concepts basieren.
In meinem letzten Artikel habe ich eine mögliche std::advance-Implementierung auf Basis von Tag-Dispatching (C++98) vorgestellt. Einer meiner Leser erwähnte, dass ich std::advance auch auf Basis von constexpr if (C++17) oder Concepts (C++20) implementieren kann. Stimmt! In diesem Artikel stelle ich zwei weitere Implementierungen von std::advance vor.
Eine kurze Erinnerung: std::advance(it, n) erhöht einen gegebenen Iterator it um n Elemente. Wenn n negativ ist, wird der Iterator dekrementiert. Abhängig vom Container und dem Iterator, der vom Container bereitgestellt wird, kommt die passende Version von std::advance zum Einsatz. Typsicherheit und Performanz sind die zwei Gründe für diese maßgeschneiderte Varianten. In meinem letzten Artikel "Softwaredesign mit Traits und Tag Dispatching" habe ich std::advance basierend auf Tag Dispatching implementiert. Bevor ich auf eine mögliche std::advance-Implementierung auf Basis von constexpr if (C++17) oder Concepts (C++20) eingehe, möchte ich noch einmal die auf Tag Dispatching basierend Implementierung (C++98) kurz vorstellen.
Tag Dispatching (C++98)
Ich nenne die Funktion advance_, um sie von std::advance zu unterscheiden.
// 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--) ++it; }
}
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';
}
Ohne weitere Umschweife: Hier ist die Ausgabe des Programms.
Die Details zu Tag Dispatching lassen sich in meinem vorherigen "Softwaredesign mit Traits und Tag Dispatching" nachlesen.
constexpr if (C++17)
constexpr if ermöglicht es, Quellcode bedingt zu übersetzen
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
}
Der Ausdruck in constexpr if muss ein Compilezeitprädikat sein: eine Funktion, die einen booleschen Wert zurückgibt und zur Compilezeit ausgeführt wird. In diesem Fall kommt die Type-Traits Funktions std::is_pointer zum Einsatz. Beide Zweige der constexpr if Kontrollstruktur (Zeilen 1 und 2) müssen gültig sein.
Die folgende Implementierung von std::advance ist eine Kopie von cppreference.com. Ich habe lediglich einige Zeilenmarkierungen hinzugefügt und die Funktion in advance_ umbenannt, damit sie mit dem Funktionsnamen in meinem vorherigen Programm advance_.cpp übereinstimmt. Folglich lässt sich die vorherige C++98-basierende durch diese neue Implementierung ersetzen:
// 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;
}
}
}
}
Diese Implementierung bestimmt die Iterator-Kategorie anhand des verwendeten Iterators (1) und fordert, dass die Iterator-Kategorie von std::input_iterator_tag abgeleitet ist (2). In (3) wird der Wert für die Inkrementierung des Iterators festgelegt. Jetzt kommt constexpr if ins Spiel. Je nach Typ des Iterators wird (4), (5) oder (6) verwendet. (4) erfordert einen std::random_access_iterator, (5) einen std::bidirectional_iterator und (6) nimmt die verbleibenden Iteratoren an.
Die folgende Grafik zeigt, welcher Container die Kompilierung welches constexpr if Zweigs auslöst:
Ehrlich gesagt ist die C++98-Version, die auf Tag Dispatching basiert, einfacher zu verstehen. Dazu springe ich drei Jahre vorwärts, um den Fortschritt mit Concepts umsetzen.
Concepts (C++20)
C++20 unterstützt die folgenden Concepts für Iteratoren:
std::input_or_output_iterator
std::input_iterator
std::output_iterator
std::forward_iterator
std::bidirectionaler_iterator
std::random_access_iterator
std::contiguous_iterator
Ein std::input_output_iterator unterstützt die Operationen ++It, It++ und *It. Sowohl std::input_iterator als auch std::output_iterator sind bereits ein std::input_or_output_iterator. Es gelten die folgende Beziehungen: Ein zusammenhängender Iterator (std::contiguous_iterator) ist ein Iterator mit wahlfreiem Zugriff (std::random_access_iterator), ein Iterator mit wahlfreiem Zugriff ist ein bidirektionaler Iterator (std::bidirectionaler_iterator) und ein bidirektionaler Iterator ist ein Vorwärts-Iterator (std::forward_iterator). Ein zusammenhängender Iterator setzt voraus, dass die Elemente des Containers zusammenhängend im Speicher abgelegt sind.
Dank Concepts ist die Implementierung von advance_ ziemlich einfach umzusetzen. Ich überlade lediglich advance_ auf den Concepts und verwende dabei Concepts als eingeschränkte Typparameter.
// 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--) ++it; }
}
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';
}
Die drei Varianten der Funktion advance_ werden für die Concepts std::input_iterator (1), std::bidirectional_iterator (2) und std::random_access_iterator (3) überladen. Der Compiler wählt die am besten passende Überladung aus. Das bedeutet, dass für eine std::forward_list (4) die auf dem Concept std::forward_iterator basierende Überladung, für eine std::list (5) die auf dem Concept std::bidirectional_iterator basierende Überladung und für einen std::vector (6) die auf dem Concept std::random_access_iterator basierende Überladung zum Einsatz kommt.
Der Vollständigkeit halber ist hier die Programmausgabe mit dem Compiler Explorer
Ich weiß nicht, welche Version von advance_ die Leserinnen und Leser bevorzuge: die auf Tag Dispatching basierende C++98-Implementierung, die auf constexpr if basierende C++17-Implementierung oder die auf Concepts basierende C++20-Implementierung. Vom Standpunkt der Lesbarkeit und Wartbarkeit ist die Concept basierende Version mein Favorit. Der Nachteil ist, dass diese Version einen C++20-Compiler verlangt. cppreference.com gibt einen schöne Überblick dazu, welcher C++-Compiler welche C++ Feature unterstützt.
Wie geht's weiter?
Nach diesem kurzen Zwischenspiel mit dem std::advance-Algorithmus, verbinde ich in meinem nächsten Artikel den dynamischen Polymorphismus (Objektorientierung) mit dem statischen Polymorphismus (Templates), um eine ziemlich anspruchsvolle Technik vorzustellen: Type Erasure.
Meine C++ Schulungen in 2022:
Dieses Jahr werde ich die folgenden offenen C++-Schulungen anbieten.
- Embedded Programmierung mit modernem C++: 28.06.2022 - 30.06.2022 (Termingarantie)
- C++20: 23.08.2022 - 25.08.2022 (Termingarantie)
- Clean Code: Best Practices für modernes C++: 11.10.2022 - 13.10.2022
- Design Pattern und Architekturpattern mit C++: 08.11.2022 - 10.11.2022 (Termingarantie)
Zum jetzigen Zeitpunkt geht ich davon aus, dass ich sie als Präsenzschulungen in der Nähe von Stuttgart durchführen kann. Weitere Informationen zu meinen C++ und Python Schulungen und meinem neuen Mentoringprogramm gibt es hier:
