\section{Beispiel 3}
Für die Implementierung der Funktionen wurde die STL-Funktion lower\_bound, die ein Iterator zur Position liefert, wo das einzufügende Element kleiner als das darauffolgende Element ist. Daraufhin wird für den jeweiligen Behälter zur Verüfung gestellte insert()-Methode zum Einfügen des übergebenen Wertes zur zuvor ermittelten Iteratorposition benutzt.
Es wurden zwei Testmodi erstellt, bei der per Zufallsgenerator erstellte Initialwerte mit zufälligen Werten in die jeweiligen Behälter einsortiert werden. Im zweiten Testmodi werden aufsteigende Zahlen in den Behälter geschrieben und absteigende Zahlen in die Behjälter einsortiert, sodass für die ersten Iterationen bis zum Ende des jeweiligen Behälters gesucht werden muss; für die späteren Iterationen müssen die Werte in den vorderen Bereichen einsortiert werden.\\

Somit kann geschlussfolgert werden, dass im Worst-Case für beide Container-Typen O(n) beträgt, weil da alle Elemente dursucht werden müssen und O(1) im Best-Case. Aufgrund der Speicherabbildung des Vektors muss allerdings zum Einfügen im schlechtesten Fall O(n) an Laufzeitkomplexität einberechnet werden, da in diesem Fall die nachfolgenden Werte verschoben werden müssen bzw. falls nicht genug Speicher allokiert wurde, eine Neu-Allokation und einer Kopieraktion durchgeführt werden. Die Liste muss nach dem Finden der geeigneten Stelle in der Struktur nur mehr O(1) aufwenden, da das jewielige Element nur zwischen den Knoten eingehängt werden muss.\\

Rein rechenrisch ergibt somit für den Vektor die asymptotische Laufzeitkomplexität zum Suchen der geeigneten Position und zum Einfügen des gewünschten Elementes:\\
$ O(n) + O(n) = 2 * O(n)  $

Für die Liste beträgt jene Komplexität hingegen nur:
$ O(n) + O(1) $

Wenn man nur diese Zahlen betrachtet, müsste der Vektor als Behälter für die verlangte Operation zweimal länger brauchen als die Liste. Doch die Messungen haben ergeben, dass der Vektor im Mittel stets schneller als die Liste ist. Bei steigender Größe bzw. Länge wächst der Vorteil von den Vektoren sogar weiter.\\

Begründet kann dies durch die Speicherabbildung der Vektoren erklärt werden, jedes Element im Vektor ist hinterinander im Speicher abgebildet, sodass die Cache-Lokalität erhöht wird und sehr viele Cache-Hits anstatt von Cache-Misses erhalten wird. Da der Cache-Speicher vielfach schneller als der Hauptspeicher ist, ist der Vektor somit in den meisten Fällen schneller als die Liste. Bei der Liste hingegen existiert keine direkte Abfolge im Speicher, sodass jene Elemente nicht durchgehend in der Cache-Zeile zu finden sind und sind somit büerall im Heap verteilt. Dies macht somit auch für den Compiler schwierig bzw. nicht möglich Techniken wie die Prefetching-Technik oder Auto-Vektorisierung auf die Liste anzuwenden, was aber beim Vektor sehr wohl der Fall ist und von diversen weiteren Optimierungen profitiert.