Einführung

Ziel: std::vector (oder ArrayList aus Java) selbst implementieren.
siehe https://isocpp.org/images/uploads/3-Tour-Abstr.pdf

Randbedingungen und Einschränkungen

beliebig viele Elemente (nicht zur Compile-Zeit bekannt)
- Build-in-Array und std::array gehen nicht, da Anzahl der Elemente zur Compile-Zeit bekannt sein muss
C++ erlaubt es nicht, zur Laufzeit Build-in-Array zu erstellen (da Größe zur Compile-Zeit bekannt sein muss)
- int n = zur_laufzeit_bestimmt(); int elemente[n]; geht nicht
beliebig viele Elemente können nicht auf dem Call-Stack platziert werden; jedes Call-Stack-Frame hat eine Maximalgröße (einige Megabyte)
daher muss der Speicher für die Elemente des dynamischen Arrays auf dem Heap (auch dynamischer Speicher genannt) platziert werden

Implementierung — Teil 1

dynamisches Array
- mit double-Elementen
- zunächst mit fester Größe, die beim Konstruieren festgelegt wird

Konstruktion

Speicher für Elemente (d. h., der Speicher, auf den MyVector::m_elems verweist) im dynamischen Speicher (Heap)
Verwaltungsstruktur (MyVector ansich) wird in dem Speicherbereich platziert, in dem die Variable angelegt wird (lokale Variable, globale Variable oder Heap-Variable)

class MyVector
{
private:
	double* m_elems;
	int m_size;
public:
	MyVector(int size) 
		: m_size{ size }
	{
		if (size < 0) { 
			throw std::length_error{ "Non-negative size required." };
		}
		m_elems = new double[size];
		for (int i = 0; i != size; ++i) { m_elems[i] = 0; }
	}
	
	int size() const { return m_size; }
}

Transclude of Drawing-2025-06-02-15.50.18.excalidraw

Zugriff auf Elemente mithilfe von index-basiertem Zugriffsoperator

double& operator[](int i) { 
	if (i<0 || size()<=i) { throw std::out_of_range{"MyVector[]"}; }
	return m_elems[i];
}

index-basierter Zugriffsoperator als const-Member-Function für konstanten Zugriff

const double& operator[](int i) const {
	if (i<0 || size()<=i) { throw std::out_of_range{"MyVector[]"}; }
	return m_elems[i];
}

Iterator-basierter Zugriff

begin() und end() wichtig für Zusammenspiel mit Algorithmen der Standardbibliothek und anderen Bibliotheken

double* begin() { return m_elems; }

Anwendung von Adressarithmetik, um `end()` zu implementieren

end() muss laut Konvention auf ein Element nach dem letzten Element verweisen:

Transclude of begin_end.excalidraw

double* end() { return begin() + size(); }

const-Member-Functions

nicht konstante Varianten von begin() und end():

double* begin() { return m_elems; }
double* end() { return begin() + size(); }

konstante Varianten von begin() und end():

const double* begin() const { return m_elems; }
const double* end() const { return begin() + size(); }

Speicherloch

Problem: nur der eigentliche Speicher des Objektes wird automatisch freigegeben (Compiler generiert entsprechenden Code); der dynamische Speicher (auf dem Heap) wird nicht automatisch freigegeben—es entsteht ein Speicherloch:

Transclude of Drawing-2025-06-02-16.01.31.excalidraw

==9391== 
==9391== HEAP SUMMARY:
==9391==     in use at exit: 80 bytes in 1 blocks
==9391==   total heap usage: 3 allocs, 2 frees, 73,808 bytes allocated
==9391== 
==9391== 80 bytes in 1 blocks are definitely lost in loss record 1 of 1
==9391==    at 0x4866AE8: operator new[](unsigned long) (in /usr/libexec/valgrind/vgpreload_memcheck-arm64-linux.so)
==9391==    by 0x10A48B: MyVector::MyVector(int) (MyVector.cpp:22)
==9391==    by 0x10A737: main (MyVector.cpp:50)
==9391== 
==9391== LEAK SUMMARY:
==9391==    definitely lost: 80 bytes in 1 blocks
==9391==    indirectly lost: 0 bytes in 0 blocks
==9391==      possibly lost: 0 bytes in 0 blocks
==9391==    still reachable: 0 bytes in 0 blocks
==9391==         suppressed: 0 bytes in 0 blocks
==9391== 
==9391== For lists of detected and suppressed errors, rerun with: -s

Destruktor

~MyVector() {
	delete[] m_elems;
}

Destruktor wird für lokale Variable automatisch am Ende deren Lebenszeit aufgerufen — d.h., am ende des Gültigkeitsbereichs (Scope)
Destruktor wird für alle nicht-primitiven Data-Member eines Objektes automatisch aufgerufen

Variante mit `std::unique_ptr`

class MyVector
{
private:
	std::unique_ptr<double[]> m_elems;
	int m_size;
public:
	MyVector(int size) : m_size{ size } {
		if (size < 0) {
			throw std::length_error{ "Non-negative size required." };
		}
		m_elems = std::make_unique<double[]>();
		for (int i = 0; i != size; ++i) { m_elems[i] = 0; }
	}
	// kein expliziter Destruktor notwendig
	~MyVector() = default;
}

wird std::unique_ptrverwendet, kann eigener Destruktor entfallen

Einschub: Eigene `unique_ptr`-Implementierung (`MyUniquePtr`) (Teil 1)

class MyUniquePtr { 
private:
	double* ptr = nullptr; 
public:
	explicit UniquePtr(double* p = nullptr) noexcept : ptr(p) {}
	// Destructor
	 ~UniquePtr() { delete ptr; }
     
     // TODO weitere Methoden
     
     // Dereference operators
     double& operator*() const { assert(*this()); return *ptr; }
     double* operator->() const noexcept { return ptr; }
     // raw pointer
     double* get() const noexcept { return ptr; }
     // Auf non-null prüfen
     explicit operator bool() const noexcept { return ptr != nullptr; }
};

Details `new` und `delete`

`new`

new führt zwei Schritte durch:
- 1. alloziert dynamischen Speicher (auch Heap genannt) für dort zu platzierendes Speicherobjekt oder—im Fall von Array (new[])—für die Speicherobjekte
  - Wird Speicher für Array alloziert, ist dieser Speicher ein zusammenhängender Speicherbereich—wie immer bei einem Array.
  - Ist nicht genügend (zusammenhängender) Speicher verfügbar, wirft new eine std::bad_alloc-Exception.
- 1. handelt es sich bei dem zu erzeugenden Speicherobjekt um eine Instanz einer Klasse, wird deren Default-Konstruktor aufgerufen.
new liefert Zeiger auf das (erste) Speicherobjekt im dynamischen Speicher

`delete`

kennt nur Zeiger auf Anfang des freizugebenden Speichers
- delete elems
Transclude of Drawing-2025-06-02-16.40.29.excalidraw

Kopieren

MyVector v1{3};
...
MyVector v2{v1}; // Kopierkonstruktion
MyVector v3 = v1; // ebenfalls Kopierkonstruktion

Problem beim Kopieren

Compiler erstellt Code, der jeden Daten-Member eines Objektes bitweise kopiert.
dieses Vorgehen führt bei Zeigern oft zu fehlerhaften Datenstrukturen
- Compiler kann nicht erkennen, ob Zeiger auf Daten zeigt, die kopiert statt referenziert werden müssen
  Transclude of kopieren_1.excalidraw
Compiler generiert für jede Klassen automatisch Kopier-Konstruktor
- shallow copy
- der tut bei Zeigern oft “das Falsche” (siehe oben)
für jeden nicht-primitiven und nicht Zeiger-Datentypen Daten-Member eines Objektes wird Kopier-Konstruktor aufgerufen
- existiert kein eigens implementierter Kopier-Konstruktor, wird ein impliziter Kopier-Konstruktor verwendet, der member-wise copying nutzt: Jeder Daten-Member wird unter Verwendung dessen Kopier-Konstrutor kopier.

Lösung: Kopier-Konstruktor

https://en.cppreference.com/w/cpp/language/copy_constructor.html

MyVector(const MyVector& orig) : m_elems{new double[orig.m_size]}, m_size{orig.m_size} {
    for (int i = 0; i < m_size; ++i) {
        m_elems[i] = orig.m_elems[i];
    }
}

Transclude of kopieren_2.excalidraw

Refactoring: `copy`-Algorithmus aus Standardbibliothek statt Schleife

https://en.cppreference.com/w/cpp/algorithm/copy

MyVector(const MyVector& orig)
	: m_elems{new double[orig.m_size]}, m_size{orig.m_size}
{
    std::copy(orig.begin(), orig.end(), begin());
}

Kopierzuweisung

https://en.cppreference.com/w/cpp/language/as_operator.html
Breymann: 14.1.1 Kopier-Zuweisungsoperator

MyVector v1{3};
...
MyVector v2{42};
...
v2 = v1; // Kopierzuweisung

wird kein Zuweisungsoperator implementiert, erstellt Compiler automatisch einen impliziten; wie beim Kopier-Konstruktor wird hier member-wise copy verwendet
- bei Zeigern ist ein member-wise copy (shallow copy) oft falsch

MyVector& operator=(const MyVector& orig)
{
    auto temp = new double[orig.m_size];
    std::copy(orig.begin(), orig.end(), temp);
 
    delete[] m_elems;
    m_elems = temp;
    m_size = orig.m_size;
 
    return *this;
}

temp wird verwendet, da new-Operator und std::copy() Exception werfen könnte

MyVector& operator=(const MyVector& orig)
{
    auto temp = new double[orig.m_size];
    try { std::copy(orig.begin(), orig.end(), temp); }
    catch(TODO) { delete[] temp; }
 
    delete[] m_elems;
    m_elems = temp;
    m_size = orig.m_size;
 
    return *this;
}

- dann wäre es allerdings besser, `std::unique_ptr` zu verwenden, um Speicherloch zu vermeiden, falls `std::copy` fehlschlägt (schlägt `new` fehl, entsteht gar kein neuer Heap-Speicher)

MyVector& operator=(const MyVector& orig)
{
    std::unique_ptr<double[]> temp = std::make_unique<double[]>(TODO);
    std::copy(orig.begin(), orig.end(), temp);
 
    delete[] m_elems;
    m_elems = temp;
    m_size = orig.m_size;
 
    return *this;
}

Kopier-Konstruktion und -Zuweisung müssen immer paarweise implementiert werden (Rule of 2)
- oft ist dann auch ein manuell implementierter Destruktor notwendig (Rule of 3)

Einschub: Eigene `unique_ptr`-Implementierung (`MyUniquePtr`) (Teil 2)

Kopier-Konstruktion und -Zuweisung verbieten:

class MyUniquePtr { 
private:
	double* ptr = nullptr; 
public:
	explicit UniquePtr(double* p = nullptr) noexcept : ptr(p) {}
	// Destructor
	~UniquePtr() { delete ptr; }
 
	MyUniquePtr(const MyUniquePtr&) = delete; // neu
	MyUniquePtr& operator=(const MyUniquePtr&) = delete; // neu
	 
	// TODO weitere Methoden
     
    // Dereference operators
    double& operator*() const { assert(*this()); return *ptr; }
    double* operator->() const noexcept { return ptr; }
    // raw pointer
    double* get() const noexcept { return ptr; }
    // Auf non-null prüfen
    explicit operator bool() const noexcept { return ptr != nullptr; }
};

Verschiebe-Semantik (move semantics)

Zwischenspiel: Additionsoperator

MyVector operator+(const MyVector& a, const MyVector& b)
{
	if ( a.size() != b.size() ) throw std::logic_error{"Unterschiedliche Groessen"};
	MyVector res{a.size()};
	for (int i = 0; i < a.size(); ++i)
		res[i] = a[i] + b[i];
	return res;
}

Problem: Nutzlose Zwischen-Ergebnisse

void f(const Vector& x, const Vector& y, const Vector& z)
{
	MyVector r;
	// ...
	r = x+y+z;
	// ...
}

TODO: That would be copying a Vector at least twice (one for each use of the + operator). If a Vector is large, say 10000 doubles, that could be embarrassing. The most embarrassing part is that res is never used again after the copy. We didn’t really want a copy, we just wanted to get the result out of a function: we wanted to move a Vector rather than to copy it. Fortunately, we can state that intent:

Verschiebe-Konstruktor

MyVector(MyVector&& a) noexcept
{
	m_elems = a.m_elems; // stiehlt die Elemente
	m_size = a.m_size;
	a.m_elems = nullptr; // Original hat keine Elemente mehr
	a.m_size = 0;
}

Transclude of verschieben_1.excalidraw

TODOs: Beispiele für die Anwendung; std::move

Verschiebe-Zuweisung

MyVector& operator=(MyVector&& other) noexcept
{
	if (this == &other) { return *this; }
	delete[] m_elems;
	m_elems = other.m_elems;
	m_size = other.m_size;
	other.m_elems = nullptr;
	other.m_size = 0;
 
	return *this;
}

TODOs: Beispiele für die Anwendung; std::move
Rule of 5

Einschub: Eigene `unique_ptr`-Implementierung (`MyUniquePtr`) (Teil 3)

Verschiebe-Konstruktion und -Zuweisung implementieren:

class MyUniquePtr { 
private:
	double* ptr = nullptr; 
public:
	explicit UniquePtr(double* p = nullptr) noexcept : ptr(p) {}
	// Destructor
	~UniquePtr() { delete ptr; }
 
	MyUniquePtr(const MyUniquePtr&) = delete;
	MyUniquePtr& operator=(const MyUniquePtr&) = delete;
	 
	MyUniquePtr(MyUniquePtr&& other)
	{
		ptr = other.ptr;
		other.ptr = nullptr;
		// besser: 
		// std::swap(ptr, other.ptr);
	}
	
	MyUniquePtr& operator=(const MyUniquePtr&& other)
	{
	   delete ptr;
	   std::swap(ptr, other.ptr);
	   return *this;
    }  
    
    // Dereference operators
    double& operator*() const { assert(*this()); return *ptr; }
    double* operator->() const noexcept { return ptr; }
    // raw pointer
    double* get() const noexcept { return ptr; }
    // Auf non-null prüfen
    explicit operator bool() const noexcept { return ptr != nullptr; }
};

Vollständige Klasse `MyVector`

class MyVector {
private:
	double* m_elems;
	int m_size;
public:
	MyVector(int size) : m_size(size)
	{
		if (size < 0) {
			throw std::length_error{ "Non-negative size required."};
		}
		m_elems = new double[m_size];
	}
 
	~MyVector() { delete[] m_elems; }
	
	MyVector(const MyVector& orig)
		: m_elems{new double[orig.m_size]}, m_size{orig.m_size}
	{
	    std::copy(orig.begin(), orig.end(), begin());
	}
 
	MyVector& operator=(const MyVector& orig)
	{
		if (this == &orig) {
			return *this;
		}
	    auto temp = new double[orig.m_size];
	    std::copy(orig.begin(), orig.end(), temp);
	
	    delete[] m_elems;
	    m_elems = temp;
	    m_size = orig.m_size;
	
	    return *this;
	}
 
	MyVector(MyVector&& a) noexcept
	{
		m_elems = a.m_elems; // stiehlt die Elemente
		m_size = a.m_size;
		a.m_elems = nullptr; // Original hat keine Elemente mehr
		a.m_size = 0;
	}
	
	MyVector& operator=(MyVector&& other) noexcept
	{
		if (this == &other) { return *this; }
		delete[] m_elems;
		m_elems = other.m_elems;
		m_size = other.m_size;
		other.m_elems = nullptr;
		other.m_size = 0;
	
		return *this;
	}
 
	int size() const { return m_size; }
 
	double& operator[](int i)
	{ 
		if (i<0 || size()<=i) { throw std::out_of_range{"MyVector[]"}; }
		return m_elems[i];
	}
	
	const double& operator[](int i) const
	{
		if (i<0 || size()<=i) { throw std::out_of_range{"MyVector[]"}; }
		return m_elems[i];
	}
 
	double* begin() { return m_elems; }
	const double* begin() const { return m_elems; }
	double* end() { return begin() + size(); }
	const double* end() const { return begin() + size(); }
};

Vollständige Klasse `MyVector` unter Verwendung von `std::unique_ptr` anstatt raw pointer

#include <cassert>
#include <memory>
#include <stdexcept>
 
class MyVector
{
private:
  std::unique_ptr<double[]> m_elems;
  int m_size;
 
public:
  MyVector(int size) : m_size(size)
  {
    if (size < 0) { throw std::length_error{ "Non-negative size required." }; }
    m_elems = std::unique_ptr<double[]>{ new double[m_size] };
  }
 
  ~MyVector() = default;
 
  MyVector(const MyVector &other) : m_elems{ new double[other.m_size] }, m_size{ other.m_size }
  {
    std::copy(other.begin(), other.end(), begin());
  }
 
  MyVector &operator=(const MyVector &other)
  {
    if (this == &other) { return *this; }
 
    m_elems.reset(new double[other.size()]);
    std::copy(other.begin(), other.end(), begin());
    m_size = other.m_size;
 
    return *this;
  }
 
  MyVector(MyVector &&other) noexcept : m_elems{ nullptr }, m_size{ 0 }
  {
    std::swap(other.m_elems, m_elems);
    std::swap(other.m_size, m_size);
  }
 
  MyVector &operator=(MyVector &&other) noexcept
  {
    if (this == &other) { return *this; }
    m_elems = std::move(other.m_elems);
    // assert(other.m_elems.get() == nullptr);
    m_size = other.m_size;
    other.m_size = 0;
 
    return *this;
  }
 
  [[nodiscard]] int size() const { return m_size; }
 
  [[nodiscard]] double &operator[](int i)
  {
    if (i < 0 || size() <= i) { throw std::out_of_range{ "MyVector[]" }; }
    return m_elems[i];
  }
 
  [[nodiscard]] const double &operator[](int i) const
  {
    if (i < 0 || size() <= i) { throw std::out_of_range{ "MyVector[]" }; }
    return m_elems[i];
  }
 
  [[nodiscard]] double *begin() { return m_elems.get(); }
  [[nodiscard]] const double *begin() const { return m_elems.get(); }
  [[nodiscard]] double *end() { return begin() + size(); }
  [[nodiscard]] const double *end() const { return begin() + size(); }
};

Templates

#include <stdexcept>
#include <algorithm>
 
template <typename T>
class MyVector {
private:
	T* m_elems;
	int m_size;
public:
	MyVector(int size);
	~MyVector();
	MyVector(const MyVector&);
	MyVector& operator=(const MyVector&);
	MyVector(MyVector&&) noexcept;
	MyVector& operator=(MyVector&&) noexcept;
 
	int size() const;
 
	T& operator[](int);
	const T& operator[](int) const;
 
	T* begin();
	const T* begin() const;
	T* end();
	const T* end() const;
};
 
template <typename T>
MyVector<T>::MyVector(int size) : m_size(size)
{
	if (size < 0) {
		throw std::length_error{ "Non-negative size required." };
	}
	m_elems = new T[m_size];
}
 
template <typename T>
MyVector<T>::~MyVector() { delete[] m_elems; }
 
template <typename T>
MyVector<T>::MyVector(const MyVector& orig)
	: m_elems{ new T[orig.m_size] }, m_size{ orig.m_size }
{
	std::copy(orig.begin(), orig.end(), begin());
}
 
template <typename T>
MyVector<T>& MyVector<T>::operator=(const MyVector& orig)
{
	if (this == &orig) {
		return *this;
	}
	auto temp = new T[orig.m_size];
	std::copy(orig.begin(), orig.end(), temp);
 
	delete[] m_elems;
	m_elems = temp;
	m_size = orig.m_size;
 
	return *this;
}
 
template <typename T>
MyVector<T>::MyVector(MyVector&& other) noexcept
	: m_elems{ other.m_elems }, m_size{ other.m_size }
{
	other.m_elems = nullptr;
	other.m_size = 0;
}
 
template <typename T>
MyVector<T>& MyVector<T>::operator=(MyVector&& other) noexcept
{
	if (this == &other) {
		return *this;
	}
	delete[] m_elems;
	m_elems = other.m_elems;
	m_size = other.m_size;
	other.m_elems = nullptr;
	other.m_size = 0;
 
	return *this;
}
 
template <typename T>
int MyVector<T>::size() const {
	return m_size;
}
 
template <typename T>
T& MyVector<T>::operator[](int i)
{
	if (i < 0 || size() <= i) {
		throw std::out_of_range{ "MyVector[]" };
	}
	return m_elems[i];
}
 
template <typename T>
const T& MyVector<T>::operator[](int i) const
{
	if (i < 0 || size() <= i) {
		throw std::out_of_range{ "MyVector[]" };
	}
	return m_elems[i];
}
 
template <typename T>
T* MyVector<T>::begin() {
	return m_elems;
}
 
template <typename T>
const T* MyVector<T>::begin() const {
	return m_elems;
}
 
template <typename T>
T* MyVector<T>::end() {
	return begin() + size();
}
 
template <typename T>
const T* MyVector<T>::end() const {
	return begin() + size();
}

Template-Instanziierung

MyVector<int> vi{10};
 
MyVector<double> vd{1};
 
MyVector<std::string> vs{10};
 
MyVector<MyVector<int>> vvi{10};

TODOs
- Link zu cppinsights

Einschub: Eigene `unique_ptr`-Implementierung (`MyUniquePtr`) (Teil 4)

Template-Klasse:

<template T>
class MyUniquePtr { 
private:
	T* ptr = nullptr; 
public:
	explicit UniquePtr(T* p = nullptr) noexcept : ptr(p) {}
	~UniquePtr() { delete ptr; }
 
	MyUniquePtr(const MyUniquePtr&) = delete;
	MyUniquePtr& operator=(const MyUniquePtr&) = delete;
	 
	MyUniquePtr(MyUniquePtr&& other)
	{
		std::swap(ptr, other.ptr);
	}
	
	MyUniquePtr& operator=(const MyUniquePtr&& other)
	{
	   delete ptr;
	   std::swap(ptr, other.ptr);
	   return *this;
    }  
    
    double& operator*() const { assert(*this()); return *ptr; }
    double* operator->() const noexcept { return ptr; }
    double* get() const noexcept { return ptr; }
    explicit operator bool() const noexcept { return ptr != nullptr; }
};

Einschränkung des Templates mit Concepts

Welche Voraussetzung stellt MyVector an Elementtypen (T)?

// Konzept: Erlaubt nur primitive Typen oder default-konstruierbare Klassen
template <typename T>
concept PrimitiveOrDefaultConstructible =
    std::is_fundamental_v<T> || std::is_default_constructible_v<T>;

Beispiel

struct NotDefaultConstructible {
	NotDefaultConstructible(int) {}
};

Verbesserung: Typparameter T mithilfe von Concept PrimitiveOrDefaultConstructible einschränken

template <PrimitiveOrDefaultConstructible T>
class MyVector {
    // ...
};

Alternative mit static_assert für ältere C++-Compiler ab C++11:

#include <type_traits>
 
template <typename T>
class MyVector {
    static_assert(
        std::is_fundamental_v<T> || std::is_default_constructible_v<T>,
        "MyVector<T>: T muss ein primitiver Datentyp oder eine Klasse mit Default-Konstruktor sein"
    );
 
    // ...
};

Implementierung — Teil 2

Problem von Implementierung Teil 1:

MyVector<T> stellt Bedingungen an Elementdatentyp T:
- T kann entweder primitiver Datentyp sein oder Klasse; ist T ein Klassentyp, benötigt T einen Default-Konstrutor für Konstruktion des Arrays im dynamischen Speicher (vgl. new T[] im MyVector-Konstrutor)
- Hinweis: Es können nur Klassentypen verwendet werden, die default-konstruierbar sind, da new den Speicher des Arrays mit T-Instanzen belegen muss—das ist folgt aus der Wertsemantik, die C++ verwendet.
Wunsch:
- MyVector, der mit beliebigen Datentypen umgehen kann (primitive, mit und ohne Default-Konstruktor)
Lösungsansatz: Allozierung des Heap-Speichers loslösen von Objektinstantiierung
- Wird ein Element zu einem MyVector-Objekt hinzugefügt, wird zunächst Heap-Speicher alloziert, ohne diesen mit einem (default-konstruierten) Objekt zu belegen (der Heap-Speicher enthält daher zunächst kein gültiges T-Objekt, sondern “Datenmüll”); anschließend wird das hinzuzufügende Element in den zuvor allozierten Heap-Speicher kopiert.
Konsequenz: new T[] kann nicht mehr verwendet werden, um Heap-Speicher zu allozieren (und anschließend zu initialisieren)
Vorgehen:
- MyVector:
  - beim Hinzufügen eines Elementes (ans Ende des MyVectors) wird
    - 1. Speicher auf dem Heap organisiert — dynamisch Array wird um ein Element erweitert
        Transclude of Drawing-2025-06-20-12.30.31.excalidraw

Ausbaustufe 1 — Der C-Ansatz mit `malloc`, `realloc` und `free`

Notwendige API-Änderung

Schlechte API:

MyVector v{10}; // reserviert nur Speicher für 10 Elemente, initalisiert Speicher aber nicht!!!
 
// Zugriff auf Element darf erst möglich werden, *nachdem* Element hinzugefügt wurde!
 
std::cout << v[0]; // Zugriff auf Speicher, der kein initialisiertes C_no_default_ctor-Element beinhaltet
 
v[0] = C_no_default_ctor{ 42 }; // Copy-Ctor funktioniert nicht
v[1] = C_no_default_ctor{ 42 };

Korrekte API:push_back(T)

  auto e = C_no_default_ctor{ 13 };
  v.push_back(e);
  v.push_back(C_no_default_ctor{ 42 });

// neue Konzepte:
// - malloc, realloc, free
// - Destruktor manuell aufrufen
#include <cassert>
#include <concepts>
#include <cstddef>
#include <cstdlib>
#include <new>
#include <type_traits>
#include <utility>
 
class C_with_default_ctor
{
public:
  C_with_default_ctor() : value{ 42 } {}
  int value;
};
 
class C_no_default_ctor
{
public:
  explicit C_no_default_ctor(int i) : value{ i } {}
 
  C_no_default_ctor(C_no_default_ctor const &other) = default;
  C_no_default_ctor &operator=(C_no_default_ctor const &other) = default;
 
  int value;
};
 
class MyVector
{
private:
  C_no_default_ctor *m_elems{ nullptr };
  size_t m_size{ 0 };
 
public:
  static_assert(std::is_copy_constructible_v<C_no_default_ctor>,
    "MyVector<T>: T muss ein primitiver Datentyp oder eine Klasse mit Kopier-Konstruktor sein");
 
  ~MyVector()
  {
    for (size_t i = 0; i < m_size; ++i) { (m_elems + i)->~C_no_default_ctor(); }
    free(m_elems);
  }
 
  // copy-Variante
  void push_back(C_no_default_ctor const &value)
  {
    {
      // Heap-Speicher für ein weiteres Element allozieren
      const int new_size_bytes = (m_size + 1) * sizeof(C_no_default_ctor);
      void *new_elems;
      if (m_elems == nullptr) {
        // noch keinen Speicher alloziert
        assert(m_size == 0);
        new_elems = malloc(new_size_bytes);
      } else {
        // bereits Speicher alloziert
        new_elems = realloc(m_elems, new_size_bytes);
      }
      if (new_elems == NULL) { throw std::bad_alloc{}; }
      m_elems = static_cast<C_no_default_ctor *>(new_elems);
    }
    // Element im vorher allozierten Heap-Speicher platzieren, indem dort eine Kopie
    // per Kopier-Konstruktor mithilfe von placement new erzeugt wird
    // (siehe https://en.cppreference.com/w/cpp/language/new.html#Placement_new)
    new (m_elems + m_size) C_no_default_ctor{ value };
    ++m_size;
  }
 
  // move-Variante
  void push_back(C_no_default_ctor &&value)
  {
    {
      const auto new_size_bytes = (m_size + 1) * sizeof(C_no_default_ctor);
      void *new_elems;
      if (m_elems == nullptr) {
        assert(m_size == 0);
        new_elems = malloc(new_size_bytes);
      } else {
        new_elems = realloc(m_elems, new_size_bytes);
      }
      if (new_elems == NULL) { throw std::bad_alloc{}; }
      m_elems = static_cast<C_no_default_ctor *>(new_elems);
    }
    new (m_elems + m_size) C_no_default_ctor(std::move(value));
    ++m_size;
  }
};
 
int main()
{
 
  MyVector v;
 
  // schlecht!
  // v[0] = C_no_default_ctor{ 42 };
  // v[1] = C_no_default_ctor{ 42 };
  // cout << v[0];
 
  // besser:
  auto e = C_no_default_ctor{ 13 };
  v.push_back(e);
  v.push_back(C_no_default_ctor{ 42 });
}

malloc
realloc
free
manueller Dtor-Aufruf
Transclude of Drawing-2025-06-23-15.50.02.excalidraw

Details `realloc`

Speicherbereich kann sicher ändern, falls zuvor (mit malloc oder realloc) allozierter Speicherbereich nicht auf geforderte Größe vergrößert werden kann
- das ist der Grund, warum Iteratoren auf Elemente ungültig werden können, wenn den Vektor verändernde Operationen durchgeführt werden
  Transclude of Drawing-2025-06-23-16.04.39.excalidraw

Optimierung bei Speicherreservierung

Statt dynamischen Speicher nur für das neu hinzuzufügende Element zu organisieren, wird Speicher für doppelt so viele Elemente wie bisher reserviert
- Grund: Speicherreservierung (egal ob mit new oder malloc) ist aufwendig
  - involviert sind Standardbibliothek und Betriebssystem
    - new T()→ void* operator new(sizeof(T))→malloc→

void* operator new(std::size_t size) { void* p = std::malloc(size); if (!p) throw std::bad_alloc(); return p; }

			- malloc() gets memory from the heap, which is managed by the operating system (OS) and the C runtime. There are two main mechanisms it uses:
				- `brk()` / `sbrk()`: These adjust the size of the process’s data segment (older mechanism).
				- `mmap()`: Modern allocators use mmap() to request memory pages from the OS, especially for large allocations.
			- The operating system:
				- Ultimately, the OS manages memory using virtual memory.
			    - It provides memory in pages (typically 4KB) via system calls like mmap().
			    - The OS decides where to map those pages into the process’s address space.
	- Umsetzung: neuer Zähler notwendig: `capacity`
## Ausbaustufe 2 — Der bessere C++-Ansatz mit `new` Placement-`new`
```cpp
template<typename T> class MyVector
{
private:
  T *m_elems{ nullptr };
  size_t m_size{ 0 };
  size_t m_capacity{ 0 };

  void destroy_elements()
  {
    for (size_t i = 0; i < m_size; ++i) { m_elems[i].~T(); }
  }

  void deallocate() { ::operator delete(static_cast<void *>(m_elems)); }

  void ensure_capacity(size_t min_capacity)
  {
    if (min_capacity <= m_capacity) return;

    size_t new_capacity = std::max(2 * m_capacity, min_capacity);
    auto *new_storage_bytes = ::operator new(sizeof(T) * new_capacity);
    T *new_storage = static_cast<T *>(new_storage_bytes);

    for (size_t i = 0; i < m_size; ++i) {
      new (new_storage + i) T(std::move(m_elems[i]));
      m_elems[i].~T();
    }

    deallocate();
    m_elems = new_storage;
    m_capacity = new_capacity;
  }

public:
  MyVector() = default;

  MyVector(const MyVector &other)
    : m_elems(static_cast<T *>(::operator new(sizeof(T) * other.m_size))), m_size(other.m_size),
      m_capacity(other.m_size)
  {
    for (size_t i = 0; i < m_size; ++i) { new (m_elems + i) T(other.m_elems[i]); }
  }

  MyVector &operator=(const MyVector &other)
  {
    if (this == &other) { return *this; }

    // Step 1: Allocate and copy elements from other
    T *new_elems = static_cast<T *>(::operator new(sizeof(T) * other.m_size));
    size_t i = 0;
    try {
      for (; i < other.m_size; ++i) { new (new_elems + i) T(other.m_elems[i]); }
    } catch (...) {
      // Destroy partially constructed elements
      for (size_t j = 0; j < i; ++j) { new_elems[j].~T(); }
      ::operator delete(new_elems);
      throw;// Re-throw the exception
    }

    // Step 2: Destroy current elements and release old memory
    destroy_elements();
    deallocate();

    // Step 3: Assign new data
    m_elems = new_elems;
    m_size = other.m_size;
    m_capacity = other.m_size;

    return *this;
  }

  MyVector(MyVector &&other) noexcept : m_elems(other.m_elems), m_size(other.m_size), m_capacity(other.m_capacity)
  {
    other.m_elems = nullptr;
    other.m_size = 0;
    other.m_capacity = 0;
  }

  MyVector &operator=(MyVector &&other) noexcept
  {
    if (this == &other) { return *this; }

    destroy_elements();
    deallocate();

    m_elems = other.m_elems;
    m_size = other.m_size;
    other.m_elems = nullptr;
    other.m_size = 0;

    return *this;
  }

  ~MyVector()
  {
    destroy_elements();
    deallocate();
  }

  [[nodiscard]] size_t size() const { return m_size; }
  [[nodiscard]] size_t capacity() const { return m_capacity; }

  T &operator[](size_t i)
  {
    if (i < 0 || i >= m_size) { throw std::out_of_range("Index out of bounds"); }
    return m_elems[i];
  }

  const T &operator[](size_t i) const
  {
    if (i < 0 || i >= m_size) { throw std::out_of_range("Index out of bounds"); }
    return m_elems[i];
  }

  void push_back(const T &value)
  {
    ensure_capacity(m_size + 1);
    new (m_elems + m_size) T(value);
    ++m_size;
  }

  void push_back(T &&value)
  {
    ensure_capacity(m_size + 1);
    new (m_elems + m_size) T(std::move(value));
    ++m_size;
  }

  void resize(size_t new_size, const T &default_value)
  {
    if (new_size < 0) { throw std::length_error("Size must be non-negative"); }

    if (new_size > m_size) {
      ensure_capacity(new_size);
      for (size_t i = m_size; i < new_size; ++i) { new (m_elems + i) T(default_value); }
    } else {
      for (size_t i = new_size; i < m_size; ++i) { m_elems[i].~T(); }
    }

    m_size = new_size;
  }

  [[nodiscard]] T *begin() { return m_elems; }
  [[nodiscard]] T *end() { return m_elems + m_size; }
  [[nodiscard]] const T *begin() const { return m_elems; }
  [[nodiscard]] const T *end() const { return m_elems + m_size; }
};

Quartz 4

Explorer

Dynamische Liste