Implementación de vectores en C++
Este artículo demostrará cómo implementar una clase similar a std::vector en C++.
Utilice las funciones malloc y realloc para implementar la clase vector personalizada en C++
El contenedor std::vector se conoce como un array dinámica de estilo C que almacena sus elementos de forma contigua. Aunque no se aplica la implementación exacta, la especificación requiere algunas características del contenedor. Es decir, un vector debe ser una estructura de datos ordenada y proporcionar acceso aleatorio a sus elementos. Otras características se pueden expresar como las funciones miembro públicas expuestas como una interfaz, algunas de las cuales implementaremos en los siguientes ejemplos. Tenga en cuenta que la implementación real de std::vector puede volverse bastante extensa, por lo que solo estamos demostrando un punto de partida desde donde el lector podría agregar más funciones.
Al principio, necesitaremos definir una clase MyVector como una plantilla de función que puede almacenar cualquier tipo genérico. Luego, podemos incluir miembros de datos centrales como el puntero a el array de elementos y objetos enteros para almacenar el tamaño / capacidad en consecuencia. Recuerde que std::vector puede asignar trozos de memoria más grandes que los que necesitan los elementos almacenados para un mejor rendimiento. Este tamaño de memoria asignado se denomina capacidad del vector y lo almacenamos en un miembro de datos cap. Estamos asignando una cantidad fija (20 objetos) una vez que se construye un nuevo objeto MyVector y ponemos los elementos actuales a cero.
Tenga en cuenta que utilizamos la función malloc, que puede considerarse dañina en C++ contemporáneo, pero proporciona flexibilidad y buen rendimiento si se usa con precaución. Además, la memoria asignada con malloc se puede ampliar con la función realloc, que necesitaremos para gestionar el cambio de tamaño del array.
En total, nuestra clase contiene tres funciones miembro y el operador [], que forman la base de un vector dinámico. El siguiente código de ejemplo demuestra las implementaciones de las funciones push_back, size y operator[]. Los dos últimos son bastante intuitivos y fáciles de entender, mientras que push_back puede necesitar alguna explicación.
Tenga en cuenta que solo necesitamos asignar nuevas regiones de memoria una vez que se construye el objeto cuando el número de elementos excede la capacidad. Entonces, necesitamos dos rutas separadas para cada escenario en la función push_back, una de las cuales invocará la función realloc para expandir el bloque de memoria actual. realloc acepta dos parámetros: el puntero a la región de memoria anterior y el tamaño de la nueva región en bytes. Si la llamada es exitosa, se devuelve un puntero válido, ya sea el mismo que el puntero anterior o uno nuevo, dependiendo de si se pudo encontrar suficiente memoria en el mismo bloque. De lo contrario, se devuelve el puntero NULL para indicar que la solicitud falló.
#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;
}
Producción :
1, 1.1
1, 1.2
1, 1.3
1, 1.4
/ ------------------- /
1, 1.1
1, 1.2
Para probar la clase MyVector, incluimos algún código de controlador en la función main y definimos el objeto personalizado MyClass para almacenar como elementos. Finalmente, agregamos la función pop_back que elimina un elemento en la parte posterior del vector. La función pop_back no necesita desasignar o eliminar el contenido del elemento. Puede simplemente disminuir el miembro elem_num en uno en cada invocación, y la siguiente llamada push_back reescribirá la posición del elemento descartado. También es importante desasignar los bloques de memoria una vez que el objeto se sale de su alcance. Por lo tanto, necesitamos incluir una llamada a la función free en un destructor de la clase.
#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;
}
Producción :
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