Projektionen mit Ranges

Ich habe meinen letzten Artikel "Die Ranges Bibliothek in C++20: Mehr Details" mit einem Vergleich von std::sort und std::ranges::sort beendet. Hier sind die beiden Überladungen von std::ranges::sort:

template <std::random_access_iterator I, std::sentinel_for<I> S,
         class Comp = ranges::less, class Proj = std::identity>
requires std::sortable<I, Comp, Proj>
constexpr I sort(I first, S last, Comp comp = {}, Proj proj = {});

template <ranges::random_access_range R, 
          class Comp = ranges::less, 
          class Proj = std::identity>
requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
constexpr ranges::borrowed_iterator_t<R> 
          sort(R&& r, Comp comp = {}, Proj proj = {});

Modernes C++ – Rainer Grimm

Rainer Grimm ist seit vielen Jahren als Softwarearchitekt, Team- und Schulungsleiter tätig. Er schreibt gerne Artikel zu den Programmiersprachen C++, Python und Haskell, spricht aber auch gerne und häufig auf Fachkonferenzen. Auf seinem Blog Modernes C++ beschäftigt er sich intensiv mit seiner Leidenschaft C++.

Wer sich die erste Überladung ansieht, wird feststellen, dass sie einen sortierbaren Range R, ein Prädikat Comp und eine Projektion Proj benötigt. Das Prädikat Comp verwendet standardmäßig ranges::less und die Projektion Proj die Identität std::identity, die ihre Argumente unverändert zurückgibt. std::identity, das mit C++20 hinzugefügt wurde, ist ein Funktionsobjekt, das in der Headerdatei <functional> definiert ist. Kurz gesagt, hier sind die Komponenten:

• Komparator: Comp (binäre Funktionen, die einen booleschen Wert zurückgeben)
• Projektion: Proj (Abbildung einer Menge in eine Teilmenge)
• Sentinel: std::sentinel_for<I> (ein spezieller Wert, der das Ende einer Sequenz anzeigt)
• Concepts: std::random_access_iterator, std::sortable<I, Comp, Proj> und std::sentinel_for<I>

Im Gegensatz dazu gibt die zweite Überladung keinen Iterator I zurück, sondern einen ranges::borrowed_iterator_t. Das ist natürlich auch ein Concept und garantiert, dass der zurückgegebene Iterator anschließend sicher verwendet werden kann. Folgerichtig nennen wir diesen Iterator einen sicheren Iterator. Mehr über std::ranges::borrowed_iterator_t werde ich in einem meiner nächsten Artikel schreiben.

Eine Projektion ist eine Abbildung einer Menge in eine Teilmenge. Was heißt das?

Projektion

Die Algorithmen der Ranges-Bibliothek arbeiten direkt auf dem Container. Das liegt daran, dass die Projektion standardmäßig std::identity ist. Im folgenden Beispiel wende ich eine Projektion auf den Datentyp PhoneBookEntry an.

// rangeProjection.cpp

#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
 
struct PhoneBookEntry{                                       // (1)
    std::string name;
    int number;
};

void printPhoneBook(const std::vector<PhoneBookEntry>& phoneBook){
    for (const auto& entry: phoneBook) std::cout 
      << "(" << entry.name << ", " << entry.number << ")";
    std::cout << "\n\n";
}
 
int main() {

    std::cout << '\n';

    std::vector<PhoneBookEntry> phoneBook{ {"Brown", 111}, 
      {"Smith", 444}, {"Grimm", 666}, {"Butcher", 222}, 
      {"Taylor", 555}, {"Wilson", 333} };

    // ascending by name (2)
    std::ranges::sort(phoneBook, {}, &PhoneBookEntry::name);   
    printPhoneBook(phoneBook);

    // descending by name (3)
    std::ranges::sort(phoneBook, std::ranges::greater() , 
                      &PhoneBookEntry::name);
    printPhoneBook(phoneBook);

    // ascending by number (4)    
    std::ranges::sort(phoneBook, {}, &PhoneBookEntry::number); 
    printPhoneBook(phoneBook);

    // descending by number (5)
    std::ranges::sort(phoneBook, std::ranges::greater(), 
                       &PhoneBookEntry::number);
    printPhoneBook(phoneBook);
    
}

phoneBook (1) hat Strukturen vom Typ PhoneBookEntry (1). Dieser besteht aus einem Namen und einer Nummer. Dank der Projektionen kann das PhoneBook aufsteigend nach Namen (2), absteigend nach Namen (3), aufsteigend nach Nummern (4) und absteigend nach Nummern (5) sortiert werden. Die leeren geschweiften Klammern im Ausdruck std::ranges::sort(phoneBook, {}, &PhoneBookEntry::name) bewirken die Standardkonstruktion des Sortierkriteriums, das in diesem Fall std::ranges::less ist.

Wenn deine Projektion anspruchsvoller ist, lässt sich ein Callable wie einen Lambda-Ausdruck verwenden.

// rangeProjectionCallable.cpp

#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
 
struct PhoneBookEntry{ 
    std::string name;
    int number;
};

void printPhoneBook(const std::vector<PhoneBookEntry>& phoneBook){
    for (const auto& entry: phoneBook) std::cout << "(" 
      << entry.name << ", " << entry.number << ")";
    std::cout << "\n\n";
}
 
int main() {

    std::cout << '\n';

    std::vector<PhoneBookEntry> phoneBook{ {"Brown", 111}, 
      {"Smith", 444}, {"Grimm", 666}, {"Butcher", 222}, 
      {"Taylor", 555}, {"Wilson", 333} };

    // (1)
    std::ranges::sort(phoneBook, {}, &PhoneBookEntry::name);
    printPhoneBook(phoneBook);

    // (2)
    std::ranges::sort(phoneBook, {}, [](auto p)
      { return p.name; } );
    printPhoneBook(phoneBook);

    // (3)
    std::ranges::sort(phoneBook, {}, [](auto p) {
        return std::to_string(p.number) + p.name; 
    });
    printPhoneBook(phoneBook);

    // (4)
    std::ranges::sort(phoneBook, [](auto p, auto p2) {
        return std::to_string(p.number) + p.name < 
               std::to_string(p2.number) + p2.name; 
    });
    printPhoneBook(phoneBook);
    
}

std::ranges::sort in (1) verwendet das Attribut PhoneBookEntry::name als Projektion. (2) zeigt den entsprechenden Lambda-Ausdruck [](auto p){ return p.name; } als Projektion. Die Projektion in (3) ist etwas anspruchsvoller. Sie verwendet die String-Version der Zahl, die mit p.name verknüpft wird. Man kann natürlich auch die String-Version der Zahl und den p.name direkt als Sortierkriterium verwenden. In diesem Fall ist der Algorithmusaufruf in (3) einfacher zu lesen als der in (4). Ich möchte dies betonen: (3) verwendet eine Projektion als Sortierkriterium, aber (4) ist ein parametrisierter std::ranges::sort Aufruf mit einem binären Prädikat, das durch den Lambda-Ausdruck gegeben ist.

Die meisten Ranges-Algorithmen unterstützen Projektionen.

Wie geht's weiter?

In meinem nächsten Beitrag werde ich über Sentinels schreiben. Sie geben das Ende eines Ranges an und können als verallgemeinerte End-Iteratoren betrachtet werden.

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, Vorort bei Herrenberg)
• C++20: 23.08.2022 - 25.08.2022 (Termingarantie, Vorort bei Herrenberg)
• Clean Code: Best Practices für modernes C++: 11.10.2022 - 13.10.2022 (Vorort bei Herrenberg)
• Design Pattern und Architekturpattern mit C++: 08.11.2022 - 10.11.2022 (Termingarantie, Vorort bei Herrenberg)

(rme)