part2.tex

\documentclass[aspectratio=169]{beamer}

\usepackage[utf8]{inputenc}
\usepackage{soul}
\usepackage{pdfpcnotes}
\usepackage{listings}
\usepackage{tikz}
\usepackage{booktabs}
\usepackage{minted}
\usepackage[ngerman]{babel}

\usetheme{Hannover}
\usecolortheme{dove}

\AtBeginSection[]{
  \begin{frame}
  \vfill
  \centering
  \begin{beamercolorbox}[sep=8pt,center,shadow=true,rounded=true]{title}
    \usebeamerfont{title}\insertsectionhead\par%
  \end{beamercolorbox}
  \vfill
  \end{frame}
}

\lstset{language=C++,
                basicstyle=\ttfamily,
                keywordstyle=\color{blue}\ttfamily,
                stringstyle=\color{red}\ttfamily,
                commentstyle=\color{purple}\ttfamily,
                morecomment=[l][\color{magenta}]{\#}
}


\title{Eine Einführung in modernes C++}
\subtitle{Teil 2 -- Fortgeschrittenes C++}
\author{Paul Nykiel}
\date{\today}

\begin{document}
\maketitle

\frame{
    \pnote{Sofort Fragen!}
    \pnote{Feedback erwünscht}
    \tableofcontents
}


\section{Design Pattern}
\begin{frame}
    \frametitle{Const-Correctness}
    \begin{itemize}
        \item Alles per Referenz: Super Effizient aber Fehlerquelle
            \pnote{Beispiel: ausversehen einfügen in Map, allgemeine Fehlerquelle immer nur minimale Rechte, Dokumentation}
            \pause
        \item Const-Referenzen
            \pnote{Ergänze Beispiel}
            \pause
        \item \lstinline{const int &a = b;}
            \pnote{Read-Only "nur anschauen"}
            \pause
        \item Const-Memberfunktionen
            \pnote{Beispiel getter}
            \pause
        \item \lstinline{int getX() const \{...}
            \pnote{Const am ende der Definition this ist in der Funktion konstant}
            \pause
        \item \lstinline{mutable}
            \pnote{Beispiel Log}
    \end{itemize}
\end{frame}

\begin{frame}
    \Huge{Beispiel: Const-Correctness}
    \pnote{const einfügen hello world}
\end{frame}

\begin{frame}
    \frametitle{RAII}
    \begin{itemize}
        \item Resource acquisition is initialization
            \pnote{Fehlerreduktion, Einfachheit, Exception Safety}
            \pause
        \item Objekt akquiriert Resourcen im Konstruktor und gibt sie im
            Destruktor frei
            \pnote{Bsp. Datei, Mutex, Vector. Vgl try catch finally java}
            \pause
        \item
            \lstinputlisting{examples/slides/raii.cpp}
            \pnote{Trailing return type, Const-Correctness, Objekte werden im Konstruktor initialisiert, alle Objekte werden im Konstruktor geschlossen} 
            \pause
        \item Auch bei eigenen Klassen anwenden, Klassen sollten nach Konstruktor in korrektem Zustand sein
            \pnote{Also keine init(), close() Methode, da Fehlerquelle}
    \end{itemize}
\end{frame}

\section{OOP in C++}

\begin{frame}
    \frametitle{Klassendeklaration}
    \lstinputlisting{examples/slides/class.h}
    \pnote{Hinweis unterschied Deklaration und Definition. Vererbung, Sichtbarkeit von Vererbung, public, private, Konstruktor, Trailing return type, const Const-Correctness}
\end{frame}

\begin{frame}
    \frametitle{Klassendefinition}
    \lstinputlisting{examples/slides/class.cpp}
    \pnote{Initializierung in Braced-Initializer, Super-Konstruktor, this als Pointer}
\end{frame}

\begin{frame}
    \frametitle{Namespaces}
    \lstinputlisting{examples/slides/namespace.cpp}
    \pause
    \begin{itemize}
        \item Struktur
            \pause
        \item Keinen Einfluss auf Sichtbarkeit
            \pause
        \item Namespaces nicht mit \lstinline{using} einbinden
            \pnote{Beispiel std::distance}
    \end{itemize}
\end{frame}

\begin{frame}
    \Huge{Beispiel: HelloWorld OOP}
\end{frame}

\section{Noch mehr C++}

\begin{frame}
    \frametitle{Casts und Null-Pointer}
    \begin{itemize}
        \item \lstinline{static\_cast<T>(a)}
            \pnote{Castet Typen in kompatible Typen (hier von a nach T), kompatibilität wird zur Compile Time gecheckt}
            \pause
        \item \lstinline{dynamic\_cast<T>(a)}
            \pnote{Castet zur Runtime, vor allem für Pointer und Polyphormismus, kann Null sein}
            \pause
        \item \lstinline{0}, \lstinline{NULL} und \lstinline{nullptr}
            \pnote{Abstammung aus C, Erklärung mit Überladung}
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Trailing return-type}
    \lstinputlisting{examples/slides/trailingreturn.cpp}
    \pnote{Mathematische Notation, oftmals einfacher zu lesen}
\end{frame}

\begin{frame}
    \frametitle{Type-Deduction}
    \lstinputlisting{examples/slides/typededuction.cpp}
    \pnote{Typ wird hergeleitet, oftmals Praktisch (vgl. Iterator), spart redundanz. Potentielle Fehlerquelle, z.B. Proxy klasse (vgl. std::vector<bool>)}
\end{frame}

\begin{frame}
    \frametitle{Kurzeinführung Templates als Generics}
    \lstinputlisting{examples/slides/template.cpp}
    \pnote{Definition von template mit Typen, Type Deduktion}
\end{frame}

\section{STL}

\begin{frame}
    \frametitle{STL}
    \begin{itemize}
        \item Standard Template Library
            \pnote{Standardlibrary, wird von der libc zur Verfügung gestellt, nicht immer existent z.B. MC, aber mit OS schon. Grob Aufteilung:}
            \pause
        \item Utility
            \pnote{String, Math, Date \& Time, Smart Pointer}
            \pause
        \item Container
            \pnote{Strukturierte Sammlung von Objekten}
            \pause
        \item Algorithmen
            \pnote{Standardalgorithmen oftmals mit Containern}
            \pause
        \item IO
            \pnote{Standard-IO, Dateizugriff}
            \pause
        \item Concurrency
            \pnote{Threads und Locking Mechanismen}
    \end{itemize}
    \pnote{Jeweils kleine Auswahl zeigen}
\end{frame}

\begin{frame}
    \frametitle{Container}
    \begin{figure}
        \centering
        \begin{tabular}{c|ccc}
            \toprule
            & Auf Element zugreifen & Element einfügen \\
            \midrule
            \lstinline{std::array<T, N>} & $\mathcal{O}(1)$ & X \\
            \lstinline{std::vector<T>} & $\mathcal{O}(1)$ & $\mathcal{O}(n)$ \\
            \lstinline{std::deque<T>} & $\mathcal{O}(1)$ & $\mathcal{O}(n)$ bzw. $\mathcal{O}(1)$ \\
            \lstinline{std::list<T>} & $\mathcal{O}(n)$ & $\mathcal{O}(1)$ \\
            \bottomrule
        \end{tabular}
    \end{figure}
    \pnote{Größe muss zu Compile-Time feststehen, wie Array in C nur Sicher, Zugriff O(1), Einfügen unmöglich}
    \pnote{Dynamisch angelegtes Array, Elemente können hinzugefügt werden aber nicht effizient, Zugriff O(1), Einfügen worst case O(n)}
    \pnote{Verlinkte Array-Liste, Zugriff O(1) (aber langsamer als vector), Einfügen an einem Ende O(1), Einfügen in der Mitte O(n)}
    \pnote{Einfach bzw. doppelt verkettete Liste, Zugriff O(1), Einfügen O(1)}

\end{frame}

\begin{frame}
    \frametitle{Iteratoren}
    \lstinputlisting{examples/slides/iterator.cpp}
    \pnote{Type deduction wäre möglich (auto). Wie Pointer nur abstrakt, z.B. auch bei Liste, zentrales Element für Container und Algorithmen,
        abstraktion von Container, wieso nicht at O(n) in Liste}
\end{frame}

\begin{frame}
    \frametitle{for-each}
    \lstinputlisting{examples/slides/foreach.cpp}
    \pnote{Deutlich kürzer, sicher beachte const Referenz, nur wenn Funktionen const}
\end{frame}

\begin{frame}
    \frametitle{Weitere Container und Aggregationstypen}
    \begin{itemize}
        \item Assoziative-Container: \lstinline{std::set<T>} und \lstinline{std::map<K, V>}
            \pnote{Menge und Abbildung von Key auf Value, finden von Elementen in O(log(n(), einfügen in O(log(n))}
            \pause
        \item Sammlung verschiedener Objekte: \lstinline{std::tuple<T...>} und \lstinline{std::pair<T1, T2>}
            \pnote{Sammlung von mehreren bzw. 2 Objekten von unterschiedlichem Typ. Typen und Anzahl müssen zu Compile-Time bekannt sein}
            \pause
        \item Objekt das nicht vorhanden sein muss: \lstinline{std::optional<T>}
            \pnote{Variable vom Typ T die nicht existieren muss, zum Beispiel als Return-Wert mit Fehler}
    \end{itemize}
\end{frame}

\section{Praxis}
\begin{frame}
    \Huge{Praxis: \pause Huffman-Codierer}
    \pnote{Begründung: Baum nicht als STL-Datenstrukur, trotzdem STL Container notwendig, Templates, Pointer, in unter 150 Zeilen lösbar}
\end{frame}

\begin{frame}
    \frametitle{Vorgehen}
    \begin{itemize}
        \item Datei einlesen
            \pnote{Streams nutzen}
            \pause
        \item Relative Häufigkeiten ($\approx$ Wahrscheinlichkeiten) berechnen (Byteweise)
            \pnote{Blockgröße 8-bit}
            \pause
        \item Huffman-Baum konstruieren
            \pause
            \pnote{Erstmal separate Template-Klasse für Baum, dann nutzen für Huffman}
            \begin{itemize}
                \item Menge aller Symbole mit zugehörigen Wahrscheinlichkeiten
                    \pnote{Nach passender Datenstruktur für Menge und Symbol mit Wahrscheinlichkeit fragen}
                    \pause
                \item Zwei Symbole geringster Wahrscheinlichkeit finden
                    \pnote{Effizienz, jedes mal suchen, ein mal sortieren?}
                    \pause
                \item Symbole aus Menge Entfernen
                    \pnote{Recherche wie in STL möglich}
                    \pause
                \item Zu neuem Knoten kombinieren
                    \pause
                \item Knoten zu Menge hinzufügen
                    \pause
            \end{itemize}
        \item Abbildung ausgeben
            \pnote{Durch Baum laufen, nach Format a -> 001}
            \pnote{Beispiel an Tafel!}
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Anforderungen}
    \begin{itemize}
        \item Eigene \lstinline{template} Klasse für Binärbäume
            \pause
        \item Vorgestellten Konzepte nutzen
            \pause
        \item Überlegt inwiefern der Code gut getestet werden kann (wir werden in Teil 3 Unittests ergänzen)
    \end{itemize}
\end{frame}
\end{document}