Algorithmen I

Die Standardbibliothek stellt eine Vielzahl von Algorithmen zur Verfügung, um Daten in einem Container bzw. Range zu bearbeiten. Von vielen Algorithmen gibt zwei Formen:

• Die Ursprungsform, die für die Definition des zu bearbeitenden Bereichs Iteratoren (z.B. begin() und end()) verwendet. Diese Algorithmen liegen im Namensraum std.
• Die neuere Form, die Ranges verwendet und im Namensraum std::ranges liegt.

for_each_result std::for_each (iter first, iter last,
                               UFUNC fct, PRJ proj={});
for_each_result std::ranges::for_each (RANGE rng, UFUNC fct,
                                       PRJ proj={});

Sofern im C++-Standard definiert, werden nur noch die neueren Formen der Algorithmen beschrieben.

Um einen Algorithmus nicht zweimal aufführen zu müssen, wird bei der Angabe des Bereichs der Pseudo-Datentyp ITER_RNG verwendet wenn beide Formen zulässig sind.

for_each_result for_each (ITER_RNG irng, UFUNC fct, PRJ proj={});

Beachten Sie bei allen Ausführungen, dass beim Einsatz von Iteratoren das Bereichsende immer das (letzte+1) Element ist!

Ferner sollten Sie nicht vergessen, dass bei Verwendung von Ranges auch Projektionen möglich sind (siehe Ranges und Views). Diese werden bei den Algorithmen durch den Datentyp PRJ gekennzeichnet.

Für alle beschriebenen Algorithmen, mit Ausnahme der im nächsten Kapitel beschriebenen numerischen Algorithmen, ist die Header-Datei algorithm einzubinden.

Funktionsobjekte für Vergleiche

Für Algorithmen die Elemente vergleichen, wie z.B. max() oder copy_if(), stellt die Standardbibliothek im Namensraum std::ranges vordefinierte binäre Predicates zur Verfügung:

Um ein Predicate auf einen Algorithmus anzuwenden, ist es beim Aufruf des Algorithmus zu instanziieren.

std::ranges::max(data,std::ranges::less{});

Alternativ kann anstelle eines vordefinierten Predicates immer ein anwenderdefiniertes Predicate oder eine entsprechende Lambda-Funktion eingesetzt werden (siehe nachfolgendes Beispiel zu max()).

min/max Algorithmen

Die min/max Algorithmen liefern das kleinste/größte Datum zweier Daten bzw. das kleinste/größte Element in einem Bereich zurück. Werden die Algorithmen auf Objekte angewandt und keine Projektion verwendet, so muss die Klasse des Objekts den Operator < überladen.

const DTYP& max (const DTYP& val1, const DTYP& val2,
                               BPRED cmp={}, PRJ proj={});
const DTYP& max (ITER_RNG irng, BPRED cmp={}, PRJ proj={});

Liefert eine Referenz auf das
- größere Datum der beiden Daten val1 und val2
- auf das größte Element im Bereich irng
zurück. Der Vergleich erfolgt standardmäßig mit dem Predicate less{}. Anwenderdefinierte Predicates müssen true zurückliefern, wenn der erste übergebene Wert kleiner als der zweite Wert ist.

#include <print>
#include <vector>
#include <string>
#include <string_view>
#include <algorithm>

// Testklasse fuer max()
struct Data
{
    std::string name;
    int         id;
    Data(std::string_view _name, int _id) :name(_name), id(_id)
    {}
};

int main()
{
    // Lambda-Funktion, vergleicht absolute Werte
    auto absCmp = [](int val1, int val2)
        { return std::abs(val1) < std::abs(val2); };

    // Standardvergleich mit less{}
    auto imax = std::ranges::max(-12, 8);
    std::println("max(-12, 8): {}", imax);
    // Vergleich mit Lambda-Funktion
    imax = std::ranges::max(-12, 8, absCmp);
    std::println("max(-12, 8, absCmp): {}", imax);

    // Data-Vektor und int-Vektor definieren/initialisieren
    std::vector<Data>
        vec{ {"John",10}, {"Emilie", 20},{"Michelle",15} };
    std::vector<int> ivec{ 1,-4,5,10,-12 };

    // max-Element aus int-Vektor, Standard-Vergleich
    auto res = std::ranges::max(ivec);
    std::println("max(ivec): {}", res);

    // max-Element aus int Vektor,
    res = std::ranges::max(ivec, absCmp);
    std::println("max(ivec, absCmp): {}", res);

    // max-Element aus Data-Vektor, Standard-Vergleich
    // Verglichen werden die Elemente id (Projektion)
    auto res1 = std::ranges::max(vec, {}, &Data::id);
    std::println("max(vec, {{}}, &Data::id): {}", res1.id);

    // max-Element aus Data-Vektor,
    // Vergleich mit ranges-Funktionsobjekt
    // Verglichen werden die Elemente name (Projektion)
    res1 = std::ranges::max(vec, std::ranges::less{},
        &Data::name);
    std::println("max(vec, std::ranges::less{{}}: {}", res1.name);
}

max(-12, 8): 8
max(-12, 8, absCmp): -12
max(ivec): 10
max(ivec, absCmp): -12
max(vec, {}, &Data::id): 20
max(vec, std::ranges::less{}: Michelle

Sehen Sie sich in den Zeilen 44 und 50 an, wie mittels einer Projektion der größte Wert eines Klassenmember bestimmt wird. In Zeile 50 wird zusätzlich das für den Vergleich zu verwendende Predicate angegeben.

Es gibt einen weiteren Algorithmus max_element(), der für einen Bereich anstelle einer Referenz auf das größte Datum einen Iterator darauf zurückliefert.

const DTYP& min (const DTYP& val1, const DTYP& val2,
                                BPRED cmp={}, PRJ proj={});
const DTYP& min (ITER_RNG irng, BPRED cmp={}, PRJ proj={});

Liefert eine Referenz auf das
- kleinere Datum der beiden Daten val1 und val2
- auf das kleinste Element im Bereich irng
zurück. Der Vergleich erfolgt standardmäßig mit dem Predicate less{}. Anwenderdefinierte Predicates müssen true zurückliefern, wenn der erste übergebene Wert kleiner als der zweite Wert ist.

Auch hierfür gibt es einen weiteren Algorithmus min_element(), der für einen Bereich anstelle einer Referenz auf das kleinste Datum einen Iterator darauf zurückliefert.

minmax_result minmax (const DTYP& val1, const DTYP& val2,
                                          BPRED cmp={}, PRJ proj={});
minmax_result minmax (ITER_RNG irng, BPRED cmp={}, PRJ proj={});

Liefert
- das kleinere und größere Datum der beiden Daten val1 und val2
- das kleinste und größte Element im Bereich irng
in der Ergebnisstruktur minmax_result zurück. Das Member max enthält das größte Datum und das Member min das kleinste. Der Vergleich erfolgt standardmäßig mit dem Predicate less{}. Anwenderdefinierte Predicates müssen true zurückliefern, wenn der erste übergebene Wert kleiner als der zweite Wert ist.

#include <print>
#include <string>
#include <algorithm>
#include <vector>

// Testklasse
struct Data
{
    std::string name;
    int         id;
    Data(std::string_view _name, int _id) :name(_name), id(_id)
    {}
};

int main()
{
    // Data-Vektor und int-Vektor definieren/initialisieren
    std::vector<Data>
        vec{ {"John",10}, {"Emilie", 20},{"Michelle",15} };
    std::vector<int> ivec{ 1,-4,5,10,-12 };
    // Min/Max int-Vektor
    auto res = std::ranges::minmax(ivec);
    std::println("min: {}, max: {}", res.min, res.max);
    // Min/Max Data-Vektor
    // Es muss hier eine Projektion verwendet werden,
    // da fuer Data kein Operator < definiert ist
    auto res1 = std::ranges::minmax(vec, {}, &Data::name);
    std::println("min: {}, max: {}",
        res1.min.name, res1.max.name);
}

min: -12, max: 10
min: Emilie, max: Michelle

Beachten Sie den Kommentar in Zeile 25 sowie die Zugriffe auf das Ergebnis in Zeile 29.

Alternativ kann auch hier der Algorithmus minmax_element() anstelle von minmax() verwendet werden.

const DTYP& clamp (const DTYP& val, const DTYP& low,
                                    const DTYP& high, BPRED cmp={}, PRJ proj={});

Begrenzt den Wertebereich des Datums val auf den Bereich [low...high]. Als Returnwert liefert die Funktion
- wenn val<low: Referenz auf low
- wenn val>high: Referenz auf high
- ansonsten: Referenz auf val
Das Datum val wird nicht verändert.Der Vergleich erfolgt standardmäßig mit dem Predicate less{}. Anwenderdefinierte Predicates müssen true zurückliefern, wenn der erste übergebene Wert kleiner als der zweite Wert ist.

// Unter- und Obergrenze festlegen
int low = -5, high = 5;
// Gibt "-5,-5,-5,-4,-2,0,2,4,5,5," aus
for (int index=-10; index<10; index+=2)
    std::cout << std::clamp(index,low,high) << ',';

Übungen

minmax_01:

Lesen Sie aus der Hitparaden-Datei swr1_hitparade.csv die ersten 10 Titel ein und bestimmen Sie die niedrigste und höchste Position in der Hitparade jedes Titels.

Geben Sie den Titel, den Interpret sowie die niedrigste und höchste Position aus.

'25' von 'fantastischen vier': min: 0, max:667
'79' von 'lo & leduc': min: 0, max:985
'1973' von 'james blunt': min: 0, max:351
'1999' von 'prince': min: 0, max:582
'10. Jun' von 'bap': min: 0, max:813
'(don't fear) the reaper' von 'blue oeyster cult': min: 0, max:954
'(i can't help) falling in love' von 'ub40': min: 0, max:236
'(you want to) make a memory' von 'bon jovi': min: 0, max:529
'1000 gute gruende' von 'toten hosen': min: 0, max:930
'12sati' von 'e.t.': min: 0, max:881

Nicht-modifizierende sequenzielle Algorithmen

Die nicht-modifizierenden sequenziellen Algorithmen dienen zum sequenziellen Durchlaufen eines Bereichs und zum Suchen und Zählen von Elementen. Einen Algorithmus aus dieser Gruppe kennen Sie bereits, den for_each() Algorithmus.

for_each()

for_each_result for_each (ITER_RNG irng, UFUNC fct, PRJ proj={});

Ruft für jedes Element im Bereich irng die Funktion void fct(DTYP element) auf. Als Returnwert liefert for_each eine Struktur vom Typ for_each_result, die im Member fun einen Zeiger auf die Funktion fct enthält und im Member in einen Iterator auf das Bereichsende.

find und search

iter find (ITER_RNG irng, const DTYP& value, PRJ proj={});

Sucht im Bereich irng nach dem ersten Auftreten des Datums value und liefert einen Iterator darauf zurück. Wurde das Datum nicht gefunden, wird ein Iterator auf das Bereichsende zurückgeliefert.

iter find_if (ITER_RNG irng, UPRED ucmp, PRJ proj={});

Sucht im Bereich irng nach dem ersten Auftreten des Datums, für welches das Predicate ucmp true zurückliefert. Als Rückgabewert liefert die Funktion einen Iterator auf das gefundene Element. Wurde das Datum nicht gefunden, wird ein Iterator auf das Bereichsende zurückgeliefert. Für den Vergleich wird das Predicate bool ucmp(DTYP val) aufgerufen.

// Vektor mit Temperaturen,
// unguelige Messung ist mit -999 markiert
std::vector<int> temp {23,25,31,-999,28,21};
// Suche nach ungueltiger Messung
// Iterator verweist auf -999
auto invalTemp = std::ranges::find(temp,-999);
// Suche ersten Tag mit Temperatur 30 oder hoeher
// Iterator verweist auf 31
auto highTemp = std::ranges::find_if(temp,
                              [] (int& t) {return t >= 30;} );

iter find_first_of (ITER_RNG irng1, ITER_RNG irng2,
                            UPRED cmp={}, PRJ1 proj1={}, PRJ2 proj2={});

Sucht im Bereich irng1 nach einem beliebigen Element aus dem Bereich irng2. Der zurückgelieferte Iterator verweist auf das erste Element im durchsuchten Bereich, das einem der zu suchenden Elemente entspricht. Wird kein Element gefunden, verweist der Iterator auf das Bereichsende von irng1.
Für den Vergleich wird das Predicate bool cmp(DTYP val1, DTYP val2) aufgerufen. Es liefert true zurück, wenn val1==val2 ist. Standardmäßig erfolgt der Vergleich mit dem functor equal_to{}

// Vektor mit vollstaendigen Namen
std::vector<std::string> names
{ "Franz Mueller"s,"Agathe Lehmann"s,
  "Xaver Schmid"s, "Gustav Mustermann"s };
// Vektor mit dem zu suchenden Nachnamen
decltype(names) toSearch {"Schmid"s, "Lehmann"s};
// Suche ersten Namen der einen zu suchenden
// Nachnamen enthaelt
// iter verweist danach auf "Agathe Lehmann"
auto iter = std::ranges::find_first_of( names, toSearch,
              [] (const std::string& val, const std::string& cval) ->bool
              {
                  return val.find(cval) != std::string::npos;
              } );

range search (ITER_RANGE irng1, ITER_RANGE irng2, UPRED cmp={},
                        PRJ1 proj1={}, PRJ2 proj2={});

Sucht im Bereich irng1 nach dem ersten Auftreten der Elementfolge irng2 und liefert einen Bereich zurück, der die gesuchten Elemente enthält. Wird keine Elementfolge gefunden, ist der zurückgelieferte Bereich leer (range.empty()==true).
Für den Vergleich wird das Preidcate bool cmp(DTYP val1, DTYP val2) aufgerufen. Es liefert true zurück, wenn val1==val2 ist. Standardmäßig erfolgt der Vergleich mit dem functor equal_to{}.

#include <utility>
#include <vector>
#include <array>
#include <algorithm>
#include <print>

int main()
{
    // Datentyp fuer Messung
    // 1. Element gibt an, ob Messung gueltig
    using data = std::pair<bool,int>;
    // Vektor mit Messungen definieren
    std::vector<data> mreihe
    { {true,10}, {true,15}, {true,5},
      {false,5}, {false,5}, {true,12}
    };
    // Array mit Vergleichdaten definieren
    // Messreihe ist ungueltig, wenn zwei ungueltige
    // Messung nacheinander auftreten. Der Messwert
    // ist hierbei nicht relevant, da Auswertung
    // mittels Lambda-Ausdruck erfolgt
    std::array<data,2> inval{ {{false,0},{false,0}} };
    // Suche nach dem ersten Auftreten von zwei
    // ungueltigen Messungen hintereinander. Es
    // wird nur das Gueltig-Flag ausgewertet
    auto iter = std::ranges::search(mreihe,inval,
             [] (const data& val, const data& cval) ->bool
                   { return val.first == cval.first;}
                );
    // Fehlerstelle berechnen
    auto pos = std::ranges::distance(mreihe.begin(),
                                     iter.begin());
    std::println("Fehler an Stelle {}!\n", pos);
}

Fehler an Stelle 3!

Übungen

search_01:

Vorgeben ist folgender Vektor mit Abflügen:

// Vektor mit Abflugdaten
// Uhrzeit, Ort, Flugnummer

struct fdata
{
   std::string time;
   std::string destination;
   std::string flightnr;
};
std::vector fluege
{ {"10:20"s, "Hamburg"s, "EW2046"s},
  {"10:40"s, "Atlanta"s, "DL117"s},
  {"10:45"s, "Frankfurt"s, "LH133"s},
  {"10:45"s, "Rom"s, "EW2884"s},
  {"10:50"s, "Kavala"s, "EW2688"s},
  {"11:00"s, "Istanbul"s, "TK1702"s} };

Suchen Sie den ersten Abflug nach 10:45 und geben dessen Daten aus.

Verschieben Sie den Abflug des Flugs nach Atlanta auf 10:48 und suchen dann erneut nach dem ersten Abflug nach 10:45.

Verwenden Sie kein filter-View um die gesuchten Abflüge zu finden.

Erster Flug nach 10:45 um 10:50: EW2688 nach Kavala
Erster Flug nach 10:45 um 10:48: DL117 nach Atlanta

count und xxx_of

diffIR count (ITER_RNG irng, const DTYP &value, PRJ proj={});

Zählt die Elemente im Bereich irng mit dem Datum value. Als Returnwert liefert die Funktion die Anzahl der gefundenen Elemente.

diffIT count_if (ITER_RNG irng, UPRED cmp, PRJ proj={});

Zählt die Elemente im Bereich irng für die das Predicate bool cmp(DTYP element) true zurückgibt.

bool all_of (ITER_RNG irng, UPRED cmp, PROJ prj={});
bool any_of (ITER_RNG irng, UPRED cmp, PROJ prj={});
bool none_of (ITER_RNG irng, UPRED cmp, PROJ prj={});

Prüft, ob für alle/mindestens einem/kein Element im Bereich irng das Predicate bool cmp(DTYP element) true zurückliefert.

#include <print>
#include <unordered_set>
#include <algorithm>
// Predicate, prueft ob Parameter eine gerade Zahl ist
bool IsEven(const int val)
{
    return (val & 0x01);
}
int main()
{
    // Auszuwertender Container
    std::unordered_multiset<int> mset {1,2,4,5,1,2};
    // Ermittle Anzahl der geraden Zahlen im Container
    auto evenCnt = std::ranges::count_if(mset, IsEven);
    std::println("Anzahl gerader Wert: {}",evenCnt);
    // Pruefe ob mindestens einmal der Wert 2 vorhanden ist
    int toCompare = 2;
    auto twos = std::ranges::any_of(mset,
                                     [=](int val)
                                     { return val == toCompare;}
                                     );
    std::println("{}er: {}",toCompare,twos);
}

Anzahl gerader Wert: 3
2er: true

Übungen

count_01:

Bestimmen Sie die Anzahl der Platzierungen für die ersten 10 Titel in der Datei swr1_hitparade.csv.

1 Plaetze: '25' von 'fantastischen vier'
5 Plaetze: '79' von 'lo & leduc'
2 Plaetze: '1973' von 'james blunt'
3 Plaetze: '1999' von 'prince'
2 Plaetze: '10. Jun' von 'bap'
17 Plaetze: '(don't fear) the reaper' von 'blue oeyster cult'
1 Plaetze: '(i can't help) falling in love' von 'ub40'
1 Plaetze: '(you want to) make a memory' von 'bon jovi'
13 Plaetze: '1000 gute gruende' von 'toten hosen'
1 Plaetze: '12sati' von 'e.t.'

Modifizierende sequenzielle Algorithmen

Modifizierende sequenzielle Algorithmen ersetzen Elemente eines Bereichs oder Teile davon.

copy

copy_result copy (ITER_RNG irng, iter dest);

Kopiert die Elemente aus dem Bereich irng in den Bereich beginnend ab der Position dest. Als Returnwert liefert die Funktion eine Struktur vom Typ copy_result. Das Member in verweist auf das nächste, nicht mehr kopierte Element im Bereich irng und das Member out auf das nächste Element nach den kopierten Elementen im Bereich dest.

copy_if_result copy_if (ITER_RNG irng, iter dest, UPRED cmp, PROJ prj={});

Kopiert die Elemente, für die das unäre Predicate bool cmp(DTYP element) true zurückliefert, aus dem Bereich irng in den Bereich beginnend ab der Position dest. Als Returnwert liefert die Funktion eine Struktur vom Typ copy_if_result. Das Member in verweist auf das nächste, nicht mehr kopierte Element im Bereich irng und das Member out auf das nächste Element nach den kopierten Elementen im Bereich dest.

copy_n_result copy_n (iter first, size_t count, iter dest);

Kopiert count Elemente ab der Position first in den Bereich beginnend ab der Position dest. Als Returnwert liefert die Funktion eine Struktur vom Typ copy_n_result. Das Member in verweist auf das nächste, nicht mehr kopierte Element im Bereich first und das Member out auf das nächste Element nach den kopierten Elementen im Bereich dest.

copy_backward_result copy_backward (ITER_RNG irng, iter dest_end);

Kopiert die Elemente aus dem Bereich irng so in den Zielbereich, dass das zuletzt kopierte Element auf der Position dest_end zu liegen kommt. Als Returnwert liefert die Funktion eine Struktur vom Typ copy_backward_result. Das Member in verweist auf das nächste, nicht mehr kopierte Element im Bereich irng und das Member out auf das Element vor den kopierten Elementen im Bereich dest_end.

Für den Zielbereich kann bei den meisten copy-Algorithmen außer einem Iterator auch ein Inserter angegeben werden, um die kopierten Elemente einzufügen anstatt die bisherigen Elemente zu ersetzen. Wird ein Iterator als Ziel verwendet, muss der Ziel-Container groß genug sein, um die zu kopierenden Elemente aufnehmen zu können.

Überlappen sich der Quell- und Zielbereich, ist der Inhalt des Zielbereichs bei allen copy-Algorithmen nicht definiert.

Übungen

acopy_01:

Schreiben Sie ein Programm zur Artikelverwaltung eines Kaufhauses. Jeder Artikel enthält eine Artikelnummer und eine Artikelbeschreibung. Die Artikelnummer setzt sich aus einer 2-stelligen Kennzeichnung für die Artikelgruppe und einer 4-stelligen vorlaufenden Nummer zusammensetzt.

Folgende Artikel sind vorrätig:

10'0919 Lego-Technik
20'0454 Kochtoepfe
20'0562 Besteck
10'2333 Puppen
30'4234 Herren-Oberbekleidung
30'2342 Damen-Oberbekleidung
20'7535 Porzellan
10'5634 PC Spiele

Geben Sie die Liste aller Artikel aus.

Erstellen Sie für jede Artikelgruppe eine eigene Artikelliste und geben diese aus.

Zusatz: Versuchen Sie eine Artikelgruppe auszugeben, ohne dass eine eigene Artikelliste hierfür definiert wird.

Lagerliste:
Artikel-Nr: 100919, Artikel: Lego-Technik
Artikel-Nr: 200454, Artikel: Kochtoepfe
Artikel-Nr: 200562, Artikel: Besteck
Artikel-Nr: 102333, Artikel: Puppen
Artikel-Nr: 304234, Artikel: Herren-Oberbekleidung
Artikel-Nr: 302342, Artikel: Damen-Oberbekleidung
Artikel-Nr: 207535, Artikel: Porzellan
Artikel-Nr: 105634, Artikel: PC Spiele

Artikelgruppe 10'0000
Artikel-Nr: 100919, Artikel: Lego-Technik
Artikel-Nr: 102333, Artikel: Puppen Artikel-Nr:
105634, Artikel: PC Spiele

Artikelgruppe 20'0000
Artikel-Nr: 200454, Artikel: Kochtoepfe
Artikel-Nr: 200562, Artikel: Besteck
Artikel-Nr: 207535, Artikel: Porzellan

Artikelgruppe 30'0000
Artikel-Nr: 304234, Artikel: Herren-Oberbekleidung
Artikel-Nr: 302342, Artikel: Damen-Oberbekleidung

move

move_result move (ITER_RNG irng, iter dest);

Verschiebt die Elemente aus dem Bereich irng in den Bereich beginnend ab der Position dest. Als Returnwert liefert die Funktion eine Struktur vom Typ move_result. Das Member in verweist auf das nächste, nicht mehr verschobene Element im Bereich irng und das Member out auf das nächste Element nach den verschobenen Elementen im Bereich dest.

move_backward_result move_backward (ITER_RNG irng, iter2 dest);

Verschiebt die Elemente aus dem Bereich irng so, dass das letzte verschobene Element auf der Position dest zu liegen kommt. Als Returnwert liefert die Funktion eine Struktur vom Typ move_backward_result. Das Member in verweist auf das nächste, nicht mehr verschobene Element im Bereich irng und das Member out auf das Element vor den verschobenen Elementen im Bereich dest.

fill

iter fill (ITER_RNG irng, const DTYP& value);

Weist den Elementen in Bereich irng das Datum value zu. Als Returnwert liefert die Funktion einen Iterator auf das nächste Element nach den überschriebenen Elementen.

iter fill_n (iter first, size_t count, const DTYP& value);

Weist count Elementen, beginnend ab Position first, das Datum value zu. Als Returnwert liefert die Funktion einen Iterator auf das nächste Element nach dem letzten zugewiesenen Element.

remove

range remove (ITER_RNG irng, const DTYP& value, PRJ proj={});

Entfernt im Bereich irng alle Elemente mit dem Datum value. Die entfernten Elemente werden lediglich an das Ende des Bereichs irng verschoben. Die physikalische Größe des bearbeiteten Bereiches ändert sich nicht. Die Funktion liefert als Rückgabewert den Bereich mit den 'entfernten' Elementen. Sollen die Elemente auch physikalisch entfernt werden, ist nach remove() die Methode erase() des Containers aufzurufen (siehe Beispiel).

range remove_if (ITER_RNG irng, UPRED cmp, PROJ prj={});

Wie remove(), nur wird für den Vergleich das Predicate cmp aufgerufen. Liefert das Predicate bool cmp(DTYP element) true zurück, wird das übergebene Element entfernt/verschoben.

#include <print>
#include <vector>
#include <algorithm>

int main()
{
    // Auszuwertender Container
    std::vector<int> mvect {1,2,4,5,1,2};
    std::print("Elemente:");
    for (auto elem : mvect)
        std::print("{}, ", elem);
    std::println("\nGroesse:{}", mvect.size());
    // Alle Elemente mit dem Wert 1 ans Ende schieben
    auto srng = std::ranges::remove(mvect, 1);
    std::print("Elemente nach remove():");
    for (auto elem: mvect)
        std::print("{}, ", elem);
    std::print("\nNur gueltige Elemente:");
    for (auto iter=mvect.begin(); iter != srng.begin(); iter++)
        std::print("{}, ", *iter);
    std::println("\nGroesse:{}", mvect.size());
    // nun alle Elemente zwischen logischem Containerende
    // und physikalischem Containerende löschen
    mvect.erase(srng.begin(),srng.end());
    std::print("Elemente nach erase():");
    for (auto elem: mvect)
        std::print("{}, ", elem);
    std::println("\nGroesse:{}\n", mvect.size());
}

Elemente:1, 2, 4, 5, 1, 2,
Groesse:6
Elemente nach remove():2, 4, 5, 2, 1, 2,
Nur gueltige Elemente:2, 4, 5, 2,
Groesse:6
Elemente nach erase():2, 4, 5, 2,
Groesse:4

replace

iter replace (ITER_RNG irng, const DTYP& oval, const DTYP& nval, PROJ = prj{});

Ersetzt im Bereich irng alle Daten oval durch das Datum nval. Als Rückgabewert liefert die Funktion einen Iterator auf das Ende des Bereichs irng.

iter replace_if (ITER_RNG irng, UPRED cmp, const DTYP& nval, PROJ = prj{});

Ersetzt im Bereich irng alle Daten, für das Predicate bool cmp(DTYP element) true zurückliefert, durch das Datum nval. Als Rückgabewert liefert die Funktion einen Iterator auf das Ende des Bereichs irng.

replace_copy_result replace_copy (ITER_RNG irng, iter dest, const DTYP& oval,
                                                         const DTYP& nval, PROJ prj={});

Kopiert alle Elemente im Bereich irng in den Bereich beginnend ab dest und ersetzt dabei das Datum oval durch das Datum nval. Als Returnwert liefert die Funktion eine Struktur vom Typ replace_copy_result. Das Member in verweist auf das nächste, nicht mehr kopierte Element im Bereich irng und das Member out auf das nächste Element nach den kopierten Elementen im Bereich dest.

replace_copy_if_result replace_copy_if (ITER_RNG irng, iter dest, UPRED cmp,
                                                                 const DTYP& nval, PROJ prj={});

Kopiert alle Elemente im Bereich irng in den Bereich beginnend ab dest und ersetzt dabei alle Daten, für die das Predicate bool cmp(DTYP element) true liefert, durch das Datum nval. Als Returnwert liefert die Funktion eine Struktur vom Typ replace_copy_if_result. Das Member in verweist auf das nächste, nicht mehr kopierte Element im Bereich irng und das Member out auf das nächste Element nach den kopierten Elementen im Bereich dest.

unique

range unique (ITER_RNG irng, UPRED cmp={}, PROJ prj={});

Entfernt unmittelbar aufeinanderfolgende gleichwertige Elemente im Bereich irng. Die entfernten Elemente werden nur an das Ende des Bereichs irng verschoben und nicht gelöscht. D.h., die physikalische Größe des bearbeiteten Containers ändert sich nicht.

Als Rückgabewert liefert die Funktion einen Bereich mit den 'entfernten' Elementen. Sollen die Elemente physikalisch entfernt werden, ist nach unique() die Methode erase() des Containers aufzurufen. Für den Vergleich wird das Predicate bool cmp(DTYP val1,, DTYP val2) aufgerufen. Es liefert true zurück, wenn val1==val2 ist. Standardmäßig erfolgt der Vergleich mit dem functor equal_to{}.

unique_copy_result unique_copy (ITER_RNG irng, iter dest, UPRED cmp={}, PROJ prj={});

Kopiert die Elemente aus dem Bereich irng in den Bereich beginnend ab der Position dest. Bei unmittelbar aufeinanderfolgenden gleichwertigen Elementen wird nur das erste Element übernommen.

Als Rückgabewert liefert die Funktion eine Struktur vom Typ unique_copy_result. Das Member in verweist auf das Ende des Bereichs irng und das Member out auf das Element nach den kopierten Elementen im Bereich dest. Für den Vergleich wird das Predicate bool cmp(DTYP val1,, DTYP val2) aufgerufen. Es liefert true zurück, wenn val1==val2 ist. Standardmäßig erfolgt der Vergleich mit dem functor equal_to{}.

generate und transform

iter generate (ITER_RNG irng, func gen);

Ruft für jedes Element im Bereich irng die Funktion DTYP gen() auf und übernimmt das von ihr zurückgelieferte Datum. Die Funktion gen hat keine Parameter und ihr Returntyp muss sich in den Datentyp der Elemente im Bereich irng konvertieren lassen. Als Rückgabewert liefert die Funktion einen Iterator auf das Ende des Bereichs irng.

iter generate_n (iter first, size_t count, func gen);

Ruft für count Elemente beginnend ab der Position first die Funktion DTYP gen() auf und übernimmt das von ihr zurückgelieferte Datum. Die Funktion gen hat keine Parameter und ihr Returntyp muss sich in den Datentyp der Elemente im Bereich irng konvertieren lassen. Als Returnwert liefert die Funktion einen Iterator auf das nächste Element nach den zugewiesenen Daten.

#include <print>
#include <vector>
#include <algorithm>

// Generatorfunktion
// Liefert 2er Potenzen zurueck
int Twos()
{
    static int counter = -1;
    counter++;
    return 1<<counter;
}
int main()
{
    // Vector mit 8 Elementen definieren
    std::vector<int> vect(8);
    // Elemente mit 2er Potenzen belegen
    std::ranges::generate(vect, Twos);
    // Elemente ausgeben
    std::print("2er Potenzen: ");
    for (auto elem : vect)
        std::print("{},", elem);
}

2er Potenzen: 1,2,4,8,16,32,64,128,

unary_transform_result transform (ITER_RNG irng, iter dest, UFUNC fct, PROJ prj={});

Übergibt jedes Element im Bereich irng an die Funktion DTYP fct(DTYP element) und legt das von ihr zurückgelieferte Datum im Bereich beginnend ab dest ab.

Als Rückgabewert liefert die Funktion eine Struktur vom Typ unary_transform_result. Das Member in verweist auf das Ende des Bereichs irng und das Member out verweist auf das Element nach dem zuletzt abgelegten Element im Bereich dest.

binary_transform_result transform (ITER_RNG rng1, ITER_RNG rng2, iter dest,
                                                            BFUNC fct, PROJ prj={});

Übergibt ein Elementenpaar aus den Bereichen rng1 und rng2 an die Funktion DTYP fct(DTYP1 rng1_val, DTYP2 rng2_val) und legt das von ihr zurückgelieferte Datum im Bereich beginnend ab dest ab. Die Funktion fct erhält im ersten Parameter Daten aus dem Bereich irng1 und im zweiten Parameter Daten aus dem Bereich irng2. Der Returntyp von fct muss sich in den Datentyp der Elemente im Bereich beginnend ab dest konvertieren lassen.

Als Rückgabewert liefert die Funktion eine Struktur vom Typ binary_transform_result. Die Member in1 und in2 verweisen auf das nächste nicht verarbeitete Element im Bereich irng1 bzw. irng2 und das Member out verweist auf das nächste nicht-transformierte Elemente im Bereich dest.

#include <print>
#include <vector>
#include <algorithm>

int main()
{
    // Ausgangsvektor mit Aktienkursdaten
    std::vector<float> stock 
                  {103.23f, 103.80f, 102.50f, 102.50f};
    // Zielvektor mit Kursdifferenzen
    std::vector<float> delta;

    // Berechne die Kursdiffenzen
    // Die binaere Fkt ist hier als Lambda implementiert
        std::ranges::transform(
              stock.begin()+1, stock.end(),
              stock.begin(), stock.end(),
              back_inserter(delta),
              [] (float aktKurs, float vorKurs)
              {
                 return aktKurs-vorKurs;
              });
        std::print("Kursdifferenzen: ");
        for (auto elem : delta)
            std::print("{:.2f}, ", elem);
}

Kursdifferenzen: 0.57, -1.30, 0.00,

Übungen

modalg_01:

Vorgegeben ist folgender Vektor mit den Tankdaten eines KFZs:

// Vektor mit Tankdaten
// 1. Pair-Element: gefahrene Kilomenter
// 2. Pair-Element: getankter Treibstoff (ltr)
using TANKDATEN = std::pair<int,int>;
std::vector<TANKDATEN> tankdaten
         {{340,25},{450,32},{240,18},{650,44}};

Es ist der Verbrauch pro gefahrene 100 km zu berechnen und in einem Vektor abzuspeichern. Geben Sie die Verbräuche mit max. 2 Nachkommastellen aus.

Geben Sie den minimalen und maximalen Verbrauch pro 100km aus.

Berechnete Verbraeuche: 7.35, 7.11, 7.50, 6.77,
Min/Max Verbrauch: 6.77, 7.50

Partitionierungsalgorithmen

Die Partitionierungsalgorithmen dienen zum Aufteilen eines Bereichs in zwei Teilbereiche.

partition

range partition (ITER_RNG irng, UPRED cmp, PROJ prj={});

Teilt den Bereich irng in zwei Teilbereiche auf. Der erste Teilbereich enthält die Elemente, für die das Predicate bool cmp(DTYP val) true zurückliefert und der zweite Teilbereich die Elemente, für die false zurückgeliefert wird. Die Reihenfolge der Elemente in den Teilbereichen ist nicht definiert.

Als Returnwert liefert die Funktion den Bereich, der die Elemente enthält, für die das Predicate false zurückgeliefert hat.

#include <print>
#include <vector>
#include <algorithm>

int main()
{
    // Vektor mit 10 ints definieren und mittels
    // generate() mit aufsteigenden Werten fuellen
    std::vector<int> vect(10);
    std::ranges::generate(vect,
        []() {static int count = 1; return count++; });
    // Vektordaten nach gerader/ungerader Zahl sortieren
    auto res = std::ranges::partition(vect,
        [](int data)
        {
            return ((data & 0x01) == 0);
        });
    // Gerade Zahlen ausgeben
    std::print("Gerade Zahlen: ");
    std::ranges::for_each(vect.begin(), res.begin(),
        [](int val) {std::print("{}, ", val); });
    // Ungerade Zahlen ausgeben
    std::print("\nUngerade Zahlen: ");
    std::ranges::for_each(res,
        [](int val) {std::print("{}, ", val); });
}

Gerade Zahlen: 10, 2, 8, 4, 6,
Ungerade Zahlen: 5, 7, 3, 9, 1,

range stable_partition (ITER_RNG irng, UPRED cmp, PROJ prj={});

Wie partition(), jedoch wird die Reihenfolge der Elemente innerhalb der Teilbereiche nicht verändert.

bool is_partitioned (ITER_RNG irng, UPRED cmp, PROJ prj={});

Prüft, ob der Bereich irng entsprechend des Predicates cmp partitioniert ist. Liefert true zurück, wenn der Bereich partitioniert ist.

Übungen

part_01:

Vorgegeben ist folgender Vektor mit Automobil-Hersteller:

// Herstellerdaten
struct Hersteller
{
   std::string name;
   std::string land;
};
// Vektor mit Autohersteller
std::vector<Hersteller> hvect
{ { "VW","Deutschland" },
  { "Hyundai","Suedkorea" },
  {"Nissan","Japan"},
  {"BMW","Deutschland"},
  {"General Motors","USA"},
  {"Porsche","Deutschland"} };

Geben Sie die Herstellerdaten aus.

Sortieren Sie die Daten so, dass die Automobil-Hersteller aus Deutschland zu Beginn des Vektors zu liegen kommen.

Geben Sie deutschen Automobil-Hersteller und im Anschluss daran die nicht-deutschen Automobil-Hersteller aus.

Hersteller: VW, Land: Deutschland
Hersteller: Hyundai, Land: Suedkorea
Hersteller: Nissan, Land: Japan
Hersteller: BMW, Land: Deutschland
Hersteller: General Motors, Land: USA
Hersteller: Porsche, Land: Deutschland

Deutsche Autohersteller:
Hersteller: VW, Land: Deutschland
Hersteller: BMW, Land: Deutschland
Hersteller: Porsche, Land: Deutschland

Nicht-deutsche Autohersteller:
Hersteller: Hyundai, Land: Suedkorea
Hersteller: Nissan, Land: Japan
Hersteller: General Motors, Land: USA

Weitere Partitionierungsalgorithmen

partition_copy_result partition_copy (ITER_RNG irng, iter1 dest1, iter2 dest2, UPRED cmp, PROJ prj={});

Kopiert die Elemente des Bereichs irng in zwei Bereiche, beginnend ab dest1 bzw. dest2. Der erste Bereich enthält die Elemente, für die das Predicate bool cmp(DTYP element) true zurückliefert und der zweite Bereich die Elemente, für die false zurückgeliefert wird.

Als Rückgabewert liefert die Funktion eine Struktur vom Typ partition_copy_result. Das Member in verweist auf das Ende des zu kopierenden Bereichs irng und die Member out1 und out2 verweisen auf das Ende der kopierten Elemente in dest1 bzw. dest2.

#include <print>
#include <vector>
#include <algorithm>

int main()
{
    // Lambda-Ausdruck, liefert true bei gerade Zahl
    auto IsEven = [](int data) { return ((data&0x01) == 0); };

    // Vektor mit den Ausgangsdaten
    std::vector<int> vect {1,2,3,4,5,6,7,8};
    // Vektoren fuer gerade und gerade Zahlen
    std::vector<int> evenVect;
    std::vector<int> oddVect;

    // Kopiere gerade Zahlen in Vektor evenVect und
    // ungerade Zahlen in oddVect
    std::ranges::partition_copy(vect,
                        back_inserter(evenVect),
                        back_inserter(oddVect),
                        IsEven);
    std::println("Gerade Zahlen: ");
    for (auto elem : evenVect)
        std::print("{},", elem);
    std::println("\nUngerade Zahlen: ");
    for (auto elem : oddVect)
        std::print("{},", elem);
}

Gerade Zahlen: 2,4,6,8,
Ungerade Zahlen: 1,3,5,7,

iter partition_point (ITER_RNG irng, UPRED cmp, PROJ prj={});

Sucht innerhalb des Bereichs irng das erste Element, für das das Predicate bool cmp(DTYP element) den Wert false liefert.