3.2 Templates, Container und Iteratoren

In dieser Aufgabe soll der Umgang mit Template (am Beispiel einer Template Funktion) und mit Containern erarbeitet werden. Hierzu gehört der Zugriff auf Container über Iteratoren.

Direkter Link zum Git und JupyterHub.

Aufgabe A: Template Funktion

ToDo:

Setzen sie eine allgemeine Funktion um,

• die auf std::out den größeren von zwei übergebenen Werten ausgibt

• und den kleineren als Rückgabewert zurückliefert.

Als Hilfe können sie Erklärungen zu Templates hier nachlesen.

// Deklarieren und definieren sie die Funktion als Template Funktion
printMaxReturnMin();

Click to show

template <typename T>
T const &printMaxReturnMin(const T &lhs, const T &rhs) {
    T max;
    if (lhs > rhs) {
        max = lhs;
    } else {
        max = rhs;
    }
    std::cout << "max of the two is: " << max << std::endl;
    
    return lhs < rhs ? lhs : rhs;
}

#include <iostream>

// Testen der Template Funktion

int main () {
  int i = 39;
  int j = 20;
  auto k = printMaxReturnMin(i,j);

  double a = 13.5;
  double b = 20.7;
  auto c = printMaxReturnMin(a,b);
}

main()

Aufgabe B: Erweitern der Funktion auf einen vector

Die oben implementierte Funktion soll nun statt zwei Argumenten einen vector mit Elementen des Typs T erhalten.

ToDo:

Erweitern sie so die Funktion, dass

• auf std::out das größte Element des vectors ausgegeben wird

• und das kleinste als Rückgabewert zurückgliefert wird.

// Deklarieren und definieren sie die Funktion als Template Funktion
template <typename T>
returntype printMaxReturnMin(const std::vector<T>& elems);

Click to show

template <typename T>
T printMaxReturnMin(const std::vector<T>& elems) {
    T max = elems[0];
    T min = elems[0];
    for (const auto& elem : elems) {
        if (elem > max) {
            max = elem;
        }
        if (elem < min) {
            min = elem;
        }
    }
    std::cout << "max of the elements is: " << max << std::endl;

    return min;
}

#include <iostream>
#include <vector>

// Test of the function on vectors.

int main() {
    // Test with ints
    std::vector<int> intVec{ 4, 7, 2, 9, 1 };
    int smallestInt = printMaxReturnMin(intVec);
    std::cout << "smallest int is: " << smallestInt << std::endl;

    // Test with floats
    std::vector<float> floatVec{ 3.14f, 1.618f, 2.718f, 0.123f };
    float smallestFloat = printMaxReturnMin(floatVec);
    std::cout << "smallest float is: " << smallestFloat << std::endl;

    return 0;
}

main();

Nachfragen

Warum kann hier nicht weiter eine Referenz auf min zurück gegeben werden wie im obigen Fall?

Aufgabe C: Zugriffszeiten auf Container

Testen sie nun die Zugriffszeiten auf verschiedene sequentielle Container (vector, list, deque). Machen sie sich dazu auch einmal vertraut, wie diese unterschiedlich umgesetzt sind (siehe Referenz oder hier in der Übersicht im Kurs der Universität Münster.)

Nutzen sie den Code von oben zur Ermittlung von Laufzeiten und vergleichen sie die drei verschiedenen Typen für:

ToDo:

• push_back: einfügen am Ende des Containers,

• resize: Größe anpassen,

Hintergrund zur Allokation des Speichers für Vektor.

Diese Aufgabe müssen sie direkt im Terminal ausführen. Den Code implementieren sie im Unterordner 3_Aufgaben und dort 3_2_TemplatesContainer. Zum kompilieren und Testen:

1. Kompilieren: g++ -std=c++20 -o contcomp container_comparison.cpp

2. Ausführen: ./contcomp

#include <iostream>
#include <ctime>

int main() {
    int NUM = 10000000;
    std::clock_t start = std::clock();

    start = std::clock(); 
    for(int i = 0; i<NUM; ++i) {
        // TODO Entsprechende Funktion auf Container testen
    };
    dt = std::clock() - start;
    std::cout << "TODO Time für TODO " << float(dt)/CLOCKS_PER_SEC << " sec\n"; 
}

Übersicht Ergebnisse: Verwendung sequentielle Containers – Übersicht

Aufgabe	std::vector	std::deque	std::list
Einfügen/entfernen Element vorne	langsam	schnell	schnell
Einfügen/entfernen Element hinten	super schnell	sehr schnell	schnell
Indizierter Zugriff	super schnell	schnell	nicht möglich
Einfügen/entfernen Element in der Mitte	langsam	schnell	sehr schnell
Speichernutzung	gering	hoch	hoch
Verbinden (splicing, joining)	langsam	sehr langsam	schnell
Stabilität (iterators, concurrency)	schlecht	sehr schlecht	gut