Vektor-Implementierung in C++
Dieser Artikel zeigt, wie Sie eine Klasse ähnlich wie std::vector in C++ implementieren.
Verwenden Sie die Funktionen malloc und realloc, um die benutzerdefinierte vector-Klasse in C++ zu implementieren
Der Container std::vector ist als dynamisches Array im C-Stil bekannt, das seine Elemente zusammenhängend speichert. Auch wenn die genaue Implementierung nicht erzwungen wird, werden einige Features des Containers von der Spezifikation gefordert. Ein Vektor sollte nämlich eine geordnete Datenstruktur sein und einen wahlfreien Zugriff auf ihre Elemente ermöglichen. Andere Funktionen können als die als Schnittstelle bereitgestellten öffentlichen Memberfunktionen ausgedrückt werden, von denen einige in den folgenden Beispielen implementiert werden. Beachten Sie, dass die eigentliche Implementierung von std::vector ziemlich umfangreich werden kann, daher zeigen wir nur einen Ausgangspunkt, von dem aus der Leser weitere Funktionen hinzufügen könnte.
Zuerst müssen wir eine MyVector-Klasse als Funktionsvorlage definieren, die jeden generischen Typ speichern kann. Dann können wir Kerndatenelemente wie den Zeiger auf das Elementarray und Integer-Objekte einschließen, um die Größe/Kapazität entsprechend zu speichern. Denken Sie daran, dass std::vector möglicherweise größere Speicherblöcke zuweisen kann, als gespeicherte Elemente für eine bessere Leistung benötigen. Diese zugewiesene Speichergröße wird als Kapazität des Vektors bezeichnet und wir speichern sie in einem cap-Datenelement. Wir weisen einen festen Betrag (20 Objekte) zu, sobald ein neues MyVector-Objekt erstellt wird und setzen die aktuellen Elemente auf Null.
Beachten Sie, dass wir die Funktion malloc verwenden, die in heutigem C++ als schädlich angesehen werden kann, aber bei vorsichtiger Verwendung Flexibilität und gute Leistung bietet. Zusätzlich kann der mit malloc allokierte Speicher mit der realloc-Funktion erweitert werden, die wir für die Größenänderung des Arrays benötigen.
Insgesamt enthält unsere Klasse drei Memberfunktionen und den Operator [], die die Basis für einen dynamischen Vektor bilden. Der folgende Beispielcode demonstriert die Funktionsimplementierungen push_back, size und operator[]. Die beiden letzteren sind recht intuitiv und einfach zu verstehen, während push_back möglicherweise einer Erklärung bedarf.
Beachten Sie, dass wir erst nach der Konstruktion des Objekts neue Speicherbereiche zuweisen müssen, wenn die Anzahl der Elemente die Kapazität überschreitet. Wir brauchen also für jedes Szenario in der Funktion push_back zwei separate Pfade, von denen einer die Funktion realloc aufruft, um den aktuellen Speicherblock zu erweitern. realloc akzeptiert zwei Parameter: den Zeiger auf den vorherigen Speicherbereich und die Größe des neuen Bereichs in Bytes. Wenn der Aufruf erfolgreich ist, wird ein gültiger Zeiger zurückgegeben, entweder der gleiche wie der vorherige Zeiger oder ein neuer, je nachdem, ob genügend Speicher im selben Block gefunden werden konnte. Andernfalls wird der Zeiger NULL zurückgegeben, um anzuzeigen, dass die Anfrage fehlgeschlagen ist.
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::string;
template <typename T>
class MyVector {
public:
MyVector() {
cap = alloc;
vector = (T *)malloc(sizeof(T) * alloc);
elem_num = 0;
};
void push_back(const T &data);
void pop_back();
[[nodiscard]] bool empty() const;
[[nodiscard]] size_t size() const;
[[nodiscard]] size_t capacity() const;
T &operator[](size_t pos);
~MyVector();
private:
T *vector = nullptr;
size_t cap;
size_t elem_num;
const int alloc = 20;
};
template <typename T>
MyVector<T>::~MyVector() {
free(vector);
}
template <typename T>
void MyVector<T>::push_back(const T &data) {
if (elem_num < cap) {
*(vector + elem_num) = data;
elem_num++;
} else {
vector = (T *)realloc(vector, sizeof(T) * cap * 2);
cap *= 2;
if (vector) {
*(vector + elem_num) = data;
elem_num++;
}
}
}
template <typename T>
void MyVector<T>::pop_back() {
if (empty()) return;
elem_num--;
}
template <typename T>
T &MyVector<T>::operator[](size_t pos) {
if (pos >= 0 && pos <= elems) return *(this->arr + pos);
throw std::out_of_range("Out of bounds element access");
}
template <typename T>
size_t MyVector<T>::capacity() const {
return cap;
}
template <typename T>
bool MyVector<T>::empty() const {
return elem_num == 0;
}
template <typename T>
size_t MyVector<T>::size() const {
return elem_num;
}
struct MyClass {
int num;
double num2;
};
int main() {
MyVector<MyClass> m1;
m1.push_back({1, 1.1});
m1.push_back({1, 1.2});
m1.push_back({1, 1.3});
m1.push_back({1, 1.4});
for (size_t i = 0; i < m1.size(); ++i) {
cout << m1[i].num << ", " << m1[i].num2 << endl;
}
cout << "/ ------------------- /" << endl;
m1.pop_back();
m1.pop_back();
for (size_t i = 0; i < m1.size(); ++i) {
cout << m1[i].num << ", " << m1[i].num2 << endl;
}
return EXIT_SUCCESS;
}
Ausgabe:
1, 1.1
1, 1.2
1, 1.3
1, 1.4
/ ------------------- /
1, 1.1
1, 1.2
Um die MyVector-Klasse zu testen, fügen wir Treibercode in die main-Funktion ein und definieren das benutzerdefinierte MyClass-Objekt zum Speichern als Elemente. Schließlich fügen wir die Funktion pop_back hinzu, die ein Element am Ende des Vektors entfernt. Die Funktion pop_back muss den Inhalt des Elements nicht aufheben oder löschen. Es kann bei jedem Aufruf einfach das Element elem_num um eins dekrementieren, und der nächste Aufruf von push_back schreibt die verworfene Elementposition neu. Es ist auch wichtig, die Speicherblöcke freizugeben, sobald das Objekt den Gültigkeitsbereich verlässt. Daher müssen wir einen Aufruf der Funktion free in einen Destruktor der Klasse einfügen.
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::string;
template <typename T>
class MyVector {
public:
MyVector() {
arr = new T[default_capacity];
cap = default_capacity;
elems = 0;
};
void push_back(const T &data);
void pop_back();
[[nodiscard]] bool empty() const;
[[nodiscard]] size_t size() const;
[[nodiscard]] size_t capacity() const;
T &operator[](size_t pos);
~MyVector();
private:
T *arr = nullptr;
size_t cap;
size_t elems;
const int default_capacity = 20;
};
template <typename T>
MyVector<T>::~MyVector() {
delete[] arr;
}
template <typename T>
void MyVector<T>::push_back(const T &data) {
if (elems < cap) {
*(arr + elems) = data;
elems++;
} else {
auto tmp_arr = new T[cap * 2];
cap *= 2;
for (int i = 0; i < elems; i++) {
tmp_arr[i] = arr[i];
}
delete[] arr;
arr = tmp_arr;
*(arr + elems) = data;
elems++;
}
}
template <typename T>
T &MyVector<T>::operator[](size_t pos) {
if (pos >= 0 && pos <= elems) return *(this->arr + pos);
throw std::out_of_range("Out of bounds element access");
}
template <typename T>
size_t MyVector<T>::size() const {
return elems;
}
template <typename T>
size_t MyVector<T>::capacity() const {
return cap;
}
template <typename T>
void MyVector<T>::pop_back() {
if (empty()) return;
elems--;
}
template <typename T>
bool MyVector<T>::empty() const {
return elems == 0;
}
struct MyClass {
string name;
double num;
};
int main() {
MyVector<MyClass> m1;
m1.push_back({"one", 1.1});
m1.push_back({"two", 1.2});
m1.push_back({"three", 1.3});
m1.push_back({"four", 1.4});
for (size_t i = 0; i < m1.size(); ++i) {
cout << m1[i].name << ", " << m1[i].num << endl;
}
cout << "/ ------------------- /" << endl;
m1.pop_back();
m1.pop_back();
for (size_t i = 0; i < m1.size(); ++i) {
cout << m1[i].name << ", " << m1[i].num << endl;
}
return EXIT_SUCCESS;
}
Ausgabe:
one, 1.1
two, 1.2
three, 1.3
four, 1.4
/ ------------------- /
one, 1.1
two, 1.2
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook