Implémentation de vecteurs en C++
Cet article montrera comment implémenter une classe similaire à std::vector en C++.
Utilisez les fonctions malloc et realloc pour implémenter la classe vector personnalisée en C++
Le conteneur std::vector est connu comme un tableau dynamique de style C qui stocke ses éléments de manière contiguë. Même si l’implémentation exacte n’est pas appliquée, certaines fonctionnalités du conteneur sont requises par la spécification. A savoir, un vector doit être une structure de données ordonnée et fournir un accès aléatoire à ses éléments. D’autres fonctionnalités peuvent être exprimées sous forme de fonctions membres publiques exposées sous forme d’interface, dont certaines seront implémentées dans les exemples suivants. Notez que l’implémentation réelle de std::vector peut devenir assez étendue, nous démontrons donc simplement un point de départ à partir duquel le lecteur pourrait ajouter plus de fonctionnalités.
Dans un premier temps, nous devrons définir une classe MyVector comme modèle de fonction pouvant stocker n’importe quel type générique. Ensuite, nous pouvons inclure des membres de données de base comme le pointeur vers le tableau d’éléments et des objets entiers pour stocker la taille/capacité en conséquence. N’oubliez pas que std::vector peut allouer des morceaux de mémoire plus importants que les éléments stockés n’en ont besoin pour de meilleures performances. Cette taille mémoire allouée est appelée capacité du vecteur, et nous la stockons dans une donnée membre cap. Nous attribuons un montant fixe (objets 20) une fois qu’un nouvel objet MyVector est construit et définissons les éléments actuels à zéro.
Notez que nous utilisons la fonction malloc, qui peut être considérée comme nuisible dans le C++ contemporain, mais elle offre de la flexibilité et de bonnes performances si elle est utilisée avec prudence. De plus, la mémoire allouée avec malloc peut être étendue avec la fonction realloc, dont nous aurons besoin pour gérer le redimensionnement du tableau.
Au total, notre classe contient trois fonctions membres et l’opérateur [], qui constituent la base d’un vecteur dynamique. L’exemple de code suivant illustre les implémentations des fonctions push_back, size et operator[]. Les deux derniers sont assez intuitifs et simples à comprendre, tandis que push_back peut nécessiter quelques explications.
Notez que nous n’avons besoin d’allouer de nouvelles régions mémoire qu’une fois l’objet construit lorsque le nombre d’éléments dépasse la capacité. Ainsi, nous avons besoin de deux chemins séparés pour chaque scénario dans la fonction push_back, dont l’un invoquera la fonction realloc pour étendre le bloc mémoire courant. realloc accepte deux paramètres : le pointeur vers la région mémoire précédente et la taille de la nouvelle région en octets. Si l’appel réussit, un pointeur valide est renvoyé, soit le même que le pointeur précédent ou un nouveau selon si suffisamment de mémoire a pu être trouvée dans le même bloc. Sinon, le pointeur NULL est retourné pour indiquer que la requête a échoué.
#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;
}
Production:
1, 1.1
1, 1.2
1, 1.3
1, 1.4
/ ------------------- /
1, 1.1
1, 1.2
Afin de tester la classe MyVector, nous incluons du code de pilote dans la fonction main et définissons l’objet personnalisé MyClass à stocker en tant qu’éléments. Enfin, nous ajoutons la fonction pop_back qui supprime un élément à l’arrière du vecteur. La fonction pop_back n’a pas besoin de désallouer ou de supprimer le contenu de l’élément. Il peut simplement décrémenter le membre elem_num de un à chaque invocation, et le prochain appel push_back réécrira la position de l’élément supprimé. Il est également important de désallouer les blocs de mémoire une fois que l’objet est hors de portée. Ainsi, nous devons inclure un appel à la fonction free dans un destructeur de la classe.
#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;
}
Production:
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