Implementação da classe std :: vector
Estou ansioso para receber seus comentários sobre minha tentativa de replicar a funcionalidade da classe vetorial. Especialmente, tenho dúvidas sobre os métodos de construtor de cópia e redimensionamento. Acho que esse construtor de cópia pode causar vazamento de memória, mas não sei como torná-lo melhor. Implementei dois métodos de redimensionamento e ambos parecem funcionar, mas qual é realmente melhor?
#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;
}
Obrigado.
Respostas
Sobre o construtor de cópia e resize()
No construtor de cópia (e nos outros construtores também), você aloca memória usando new T[...], mas resize()aloca memória com new char[sizeof(T) * ...]e, em seguida, usa o posicionamento novo para copiar os elementos antigos. O primeiro é seguro, mas potencialmente chama mais construtores do que o esperado, o último tem o problema de que você pode ter capacidade não utilizada que nunca foi inicializada corretamente, mas quando você fizer deleteisso, você chamará o destruidor em todos os elementos reservados.
Para estar seguro e evitar chamar o construtor de Tpara elementos reservados, faça o seguinte de forma consistente:
- Use
char *m_Datapara controlar a memória alocada (você pode mantê-la comoT *m_Data, mas você deve ter cuidado para nunca chamardelete[] m_Datadiretamente) - Sempre use o posicionamento
newao adicionar elementos reais ao vetor - Sempre use "posicionamento delete" ao excluir elementos reais do vetor
Além disso, idealmente você deseja std::moveelementos durante resize(), mas isso é complicado, especialmente se To construtor de movimento pode lançar exceções.
Divergência de std::vector
Conforme já discutido nos comentários, sua classe vetorial é ligeiramente diferente de std::vector. Isso se deve aos requisitos da tarefa. Fora das atribuições de classe, também existem cenários reais onde você não pode usar std::vector, mas onde você mesmo deve implementá-lo. Nesse caso, você deseja manter a interface tanto quanto possível igual std::vectorà de, para garantir que sua própria classe seja uma substituição imediata e que não haja surpresas.
Construtor reservando espaço vs. alocação de elementos
Seu construtor que recebe um size_targumento o usa para reservar espaço, mas não adiciona nenhum elemento ao vetor. No entanto, o construtor correspondente de std::vectorusa o argumento para alocar elementos reais que são inicializados por padrão. Além disso, com sua classe:
Vector<int> v(4, 2);
Isso aloca espaço apenas para dois elementos, que não são inicializados, e é definido m_Sizecomo 4, tornando os tamanhos inconsistentes entre si e permitindo que uma chamada subsequente operator[]()leia fora dos limites sem gerar um erro. Compare isso com:
std::vector<int> v(4, 2);
Isso aloca um vetor de 4 elementos que são todos inicializados com o valor 2. Portanto, um comportamento bem diferente.
Use size_tpara contadores
No construtor que recebe uma lista de inicializadores, você usa int cnt, mas intpode não ser grande o suficiente. Use size_tconsistentemente para tamanhos, contagens e índices.
Você pode alocar memória na lista de inicializadores de membros
Apenas uma observação de que você pode ter expressões mais complexas na lista de inicializadores de membros, incluindo aquelas com efeitos colaterais, como alocação de memória. Então você pode escrever:
Vector(size_t size, size_t cap)
: m_Data(new T[cap]), m_Size(size), m_Capacity(cap) {}
Realmente não importa neste caso, mas é uma boa prática fazer isso, pois há benefícios em alguns casos.
Lance usando um tipo de exceção adequado
Não throwuse strings aleatórias, mas use um tipo apropriado para a exceção. Se você fosse usar a biblioteca padrão, selecione um tipo adequado
if (index >= m_Size)
throw std::out_of_range("Index out of bounds");
Se você não pode usar a biblioteca padrão, pelo menos defina seu próprio tipo de exceção, para que um chamador possa usar blocos catch específicos. Por exemplo, considere que você pode querer fazer o seguinte:
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
}
Se você apenas jogar uma string, você só pode ter um catchbloco, que então tem que analisar a string para descobrir o que está acontecendo.
Considere não fazer check-in de limites operator[]()
A biblioteca padrão não faz verificações de limites durante o uso operator[](), uma vez que tem um impacto significativo no desempenho. Há uma função separada at(), que faz verificações de limites.
Não há necessidade de escrever Vector<T>dentroVector
Dentro da definição de classe, você não precisa escrever Vector<T>, apenas escreva Vector.
Iteradores ausentes
Sua classe não implementa iteradores, então você não pode escrever algo como:
Vector<int> v(10);
...
for (auto el: v) {
std::cout << el << "\n";
}
É um bom exercício tentar implementar iteradores para sua classe.