Implementación de la clase std :: vector
Espero recibir sus comentarios sobre mi intento de replicar la funcionalidad de la clase vectorial. Especialmente tengo dudas sobre el constructor de copias y los métodos de cambio de tamaño. Creo que el constructor de copias podría causar una pérdida de memoria, pero no sé cómo mejorarlo. Implementé dos métodos de cambio de tamaño y ambos parecen funcionar, pero ¿cuál es mejor?
#include <iostream>
#include <type_traits>
#include <math.h>
template <typename T>
class Vector {
private:
T* m_Data;
size_t m_Size, m_Capacity;
public:
Vector(size_t cap = 2)
: m_Size(0), m_Capacity(cap) {
m_Data = new T[cap];
}
Vector(size_t size, size_t cap)
: m_Size(size), m_Capacity(cap) {
m_Data = new T[cap];
}
Vector(const std::initializer_list<T>& il)
: Vector(il.size(), il.size() * 2) {
int cnt = 0;
for (const auto& el : il)
m_Data[cnt++] = el;
}
// copy constructor, makes deep copy
Vector(const Vector& v)
: m_Size(v.size()), m_Capacity(v.capacity()) {
m_Data = new T[m_Capacity];
for (size_t i = 0; i < m_Size; i++) {
m_Data[i] = v[i];
}
}
~Vector() {
delete[] m_Data;
}
// void resize(size_t newCapacity) {
// T* newData = new T[newCapacity];
// m_Size = std::min(m_Size, newCapacity);
//
// for (size_t i = 0; i < m_Size; i++)
// newData[i] = std::move(m_Data[i]);
//
// delete[] m_Data;
// m_Data = newData;
// m_Capacity = newCapacity;
// }
void resize(size_t newCapacity) {
char* newData = new char[sizeof(T) * newCapacity];
m_Size = std::min(m_Size, newCapacity);
T* dst = reinterpret_cast<T*>(newData);
for (size_t i = 0; i < m_Size; i++)
new (dst + i) T(m_Data[i]);
delete[] m_Data;
m_Data = reinterpret_cast<T*>(newData);
m_Capacity = newCapacity;
}
void push_back(const T& n) {
if (m_Capacity <= m_Size)
resize(m_Capacity * 2);
m_Data[m_Size++] = n;
}
void push_back(const T&& n) {
if (m_Capacity <= m_Size)
resize(m_Capacity * 2);
m_Data[m_Size++] = std::move(n);
}
void pop_back() {
if (m_Size > 0)
m_Data[--m_Size].~T();
}
void clear() {
for (size_t i = 0; i < m_Size; i++)
m_Data[i].~T();
m_Size = 0;
}
size_t size() const {
return m_Size;
}
size_t capacity() const {
return m_Capacity;
}
bool empty() const {
return m_Size == 0;
}
const T& operator[](size_t index) const {
if (index >= m_Size)
throw "Index out of bounds";
return m_Data[index];
}
T& operator[](size_t index) {
if (index >= m_Size)
throw "Index out of bounds";
return m_Data[index];
}
Vector<T> operator+(const Vector& other) {
if (m_Size != other.size())
throw "Vectors are of different size";
Vector<T> v(m_Size);
for (size_t i = 0; i < m_Size; i++) {
v.push_back(m_Data[i] + other[i]);
}
return v;
}
};
template <
typename T,
typename = typename std::enable_if<std::is_arithmetic<T>::value, T>::type>
int norm(const Vector<T> v) {
int nrm = 0;
size_t n = v.size();
for (int i = 0; i < n; i++) {
nrm += v[i]*v[i];
}
return sqrt(nrm);
}
template <typename T>
std::ostream& operator<<(std::ostream& s, const Vector<T>& v) {
s << "[";
size_t n = v.size();
for (size_t i = 0; i < n; i++) {
s << v[i] << (i < n - 1 ? ", " : "");
}
s << "]";
return s;
}
int main(int argc, const char * argv[]) {
Vector<int>* a = new Vector<int> {1, 2, 3, 4, 5};
Vector<int> b = {5, 4, 3, 2, 6};
Vector<int> c = b;
return 0;
}
Gracias.
Respuestas
Sobre el constructor de copias y resize()
En el constructor de copia (y también en los otros constructores), asigna memoria usando new T[...], pero resize()asigna memoria con new char[sizeof(T) * ...]y luego usa la ubicación nueva para copiar los elementos antiguos. El primero es seguro, pero potencialmente llama a más constructores de lo esperado, el segundo tiene el problema de que puede tener capacidad no utilizada que nunca se inicializó correctamente, pero cuando deletelo haga, llamará al destructor en todos los elementos reservados.
Para estar seguro y evitar llamar al constructor de Tpara elementos reservados, haga lo siguiente de manera consistente:
- Úselo
char *m_Datapara realizar un seguimiento de la memoria asignada (puede mantenerla comoT *m_Data, pero debe tener cuidado de no llamar nuncadelete[] m_Datadirectamente) - Utilice siempre la ubicación
newal agregar elementos reales al vector - Utilice siempre "ubicación delete" al eliminar elementos reales del vector
Además, lo ideal es que desee std::moveelementos durante resize(), pero eso es complicado, especialmente si Tel constructor de movimientos puede lanzar excepciones.
Divergencia de std::vector
Como ya se discutió en los comentarios, su clase de vector es ligeramente diferente de std::vector. Esto se debe a los requisitos de la tarea. Fuera de las asignaciones de clase, también hay escenarios reales en los que no puede usar std::vector, pero en los que debe implementarlo usted mismo. En ese caso, desea mantener la interfaz lo más parecida posible a la de std::vector, para asegurarse de que su propia clase sea un reemplazo directo y no haya sorpresas.
Constructor reservando espacio frente a asignando elementos
Su constructor que toma un size_targumento lo usa para reservar espacio, pero no agrega ningún elemento al vector. Sin embargo, el constructor correspondiente de std::vectorutiliza el argumento para asignar elementos reales que se inicializan por defecto. Además, con tu clase:
Vector<int> v(4, 2);
Esto asigna solo espacio para dos elementos, que no están inicializados, y se establece m_Sizeen 4, lo que hace que los tamaños sean inconsistentes entre sí y permite que una llamada posterior operator[]()lea fuera de los límites sin arrojar un error. Contraste esto con:
std::vector<int> v(4, 2);
Esto asigna un vector de 4 elementos que están todos inicializados al valor 2. Entonces, un comportamiento bastante diferente.
Usar size_tpara contadores
En el constructor que toma una lista de inicializadores, usa int cnt, pero es intposible que an no sea lo suficientemente grande. Úselo de manera size_tconsistente para tamaños, recuentos e índices.
Puede asignar memoria en la lista de inicializadores de miembros
Solo tenga en cuenta que puede tener expresiones más complejas en la lista de inicializadores de miembros, incluidas aquellas con efectos secundarios como la asignación de memoria. Entonces puedes escribir:
Vector(size_t size, size_t cap)
: m_Data(new T[cap]), m_Size(size), m_Capacity(cap) {}
Realmente no importa en este caso, pero es una buena práctica hacer esto, ya que hay beneficios en algunos casos.
Lanzar usando un tipo de excepción adecuado
No throwutilice cadenas aleatorias, utilice un tipo adecuado para la excepción. Si tuviera que utilizar la biblioteca estándar, seleccione un tipo adecuado de
if (index >= m_Size)
throw std::out_of_range("Index out of bounds");
Si no puede usar la biblioteca estándar, al menos defina su propio tipo de excepción, de modo que una persona que llama pueda usar bloques de captura específicos. Por ejemplo, considere que es posible que desee hacer lo siguiente:
try {
Vector<int> v(100000); // might throw std::bad_alloc if `new` fails
Vector<int> w(10000);
v[100000] = 10; // out of range error
v += w; // vectors of different size
}
catch (std::bad_alloc &e) {
// out of memory
}
catch (std::out_of_bounds &e) {
// handle index out of bounds
}
catch (std::invalid_argument &e) {
// handle operator+[] with an argument of the wrong size
}
Si solo lanza una cadena, solo puede tener un catch-block, que luego tiene que analizar la cadena para averiguar qué está pasando.
Considere no hacer check in de límites operator[]()
La biblioteca estándar no realiza comprobaciones de límites cuando se usa operator[](), ya que tiene un impacto significativo en el rendimiento. Hay una función separada at(), que realiza comprobaciones de límites.
No es necesario escribir Vector<T>dentroVector
Dentro de la definición de la clase no es necesario escribir Vector<T>, solo escribir Vector.
Iteradores faltantes
Su clase no implementa iteradores, por lo que no puede escribir algo como:
Vector<int> v(10);
...
for (auto el: v) {
std::cout << el << "\n";
}
Es un buen ejercicio intentar implementar iteradores para su clase.