La tarea dada es implementar una clase en C++ que se comporte como la clase Vector .
Los vectores son lo mismo que las arrays dinámicas con la capacidad de cambiar su tamaño automáticamente cuando se inserta o elimina un elemento, y el contenedor maneja automáticamente su almacenamiento. Los elementos vectoriales se colocan en almacenamiento contiguo para que se pueda acceder a ellos y recorrerlos mediante iteradores. En los vectores, los datos se insertan al final. Insertar al final toma un tiempo diferencial, ya que a veces puede ser necesario extender la array. Eliminar el último elemento lleva solo un tiempo constante porque no se cambia el tamaño. Insertar y borrar al principio o en el medio es lineal en el tiempo.
También podemos hacer que la clase de vector sea genérica usando plantillas.
Ciertas funciones asociadas al Vector que implementaremos son:
- void push(int data) : Esta función toma un elemento y lo inserta en el último. La complejidad del tiempo amortizado es O(1).
- void push(int data, int index): Inserta datos en el índice especificado. La complejidad del tiempo es O(1).
- int get(int index): Se utiliza para obtener el elemento en el índice especificado. La complejidad del tiempo es O(1).
- void pop(): Elimina el último elemento. La complejidad del tiempo es O(1).
- int size(): Devuelve el tamaño del vector, es decir, el número de elementos en el vector. La complejidad del tiempo es O(1).
- int getcapacity(): Devuelve la capacidad del vector. La complejidad del tiempo es O(1).
- void print(): se utiliza para imprimir elementos de array. La complejidad del tiempo es O(N), donde N es el tamaño del vector.
A continuación se muestra la implementación de nuestra propia clase Vector.
C++
// Self implementation of
// the Vector Class in C++
#include <bits/stdc++.h>
using namespace std;
template <typename T> class vectorClass {
// arr is the integer pointer
// which stores the address of our vector
T* arr;
// capacity is the total storage
// capacity of the vector
int capacity;
// current is the number of elements
// currently present in the vector
int current;
public:
// Default constructor to initialise
// an initial capacity of 1 element and
// allocating storage using dynamic allocation
vectorClass()
{
arr = new T[1];
capacity = 1;
current = 0;
}
//destructor to deallocate storage allocated by dynamic allocation
//to prevent memory leak
~ vectorClass()
{
delete [] arr;
}
// Function to add an element at the last
void push(T data)
{
// if the number of elements is equal to the
// capacity, that means we don't have space to
// accommodate more elements. We need to double the
// capacity
if (current == capacity) {
T* temp = new T[2 * capacity];
// copying old array elements to new array
for (int i = 0; i < capacity; i++) {
temp[i] = arr[i];
}
// deleting previous array
delete[] arr;
capacity *= 2;
arr = temp;
}
// Inserting data
arr[current] = data;
current++;
}
// function to add element at any index
void push(T data, int index)
{
// if index is equal to capacity then this
// function is same as push defined above
if (index == capacity)
push(data);
else
arr[index] = data;
}
// function to extract element at any index
T get(int index)
{
// if index is within the range
if (index < current)
return arr[index];
}
// function to delete last element
void pop() { current--; }
// function to get size of the vector
int size() { return current; }
// function to get capacity of the vector
int getcapacity() { return capacity; }
// function to print array elements
void print()
{
for (int i = 0; i < current; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
};
// Driver code
int main()
{
vectorClass<int> v;
vectorClass<char> v1;
v.push(10);
v.push(20);
v.push(30);
v.push(40);
v.push(50);
v1.push(71);
v1.push(72);
v1.push(73);
v1.push(74);
cout << "Vector size : " << v.size() << endl;
cout << "Vector capacity : " << v.getcapacity() << endl;
cout << "Vector elements : ";
v.print();
v.push(100, 1);
cout << "\nAfter updating 1st index" << endl;
cout << "Vector elements of type int : " << endl;
v.print();
// This was possible because we used templates
cout << "Vector elements of type char : " << endl;
v1.print();
cout << "Element at 1st index of type int: " << v.get(1)
<< endl;
cout << "Element at 1st index of type char: "
<< v1.get(1) << endl;
v.pop();
v1.pop();
cout << "\nAfter deleting last element" << endl;
cout << "Vector size of type int: " << v.size() << endl;
cout << "Vector size of type char: " << v1.size()
<< endl;
cout << "Vector capacity of type int : "
<< v.getcapacity() << endl;
cout << "Vector capacity of type char : "
<< v1.getcapacity() << endl;
cout << "Vector elements of type int: ";
v.print();
cout << "Vector elements of type char: ";
v1.print();
return 0;
}
Producción
Vector size : 5 Vector capacity : 8 Vector elements : 10 20 30 40 50 After updating 1st index Vector elements of type int : 10 100 30 40 50 Vector elements of type char : G H I J Element at 1st index of type int: 100 Element at 1st index of type char: H After deleting last element Vector size of type int: 4 Vector size of type char: 3 Vector capacity of type int : 8 Vector capacity of type char : 4 Vector elements of type int: 10 100 30 40 Vector elements of type char: G H I