Implementação de vetor em C++
Este artigo demonstrará como implementar uma classe semelhante a std::vector em C++.
Use as funções malloc e realloc para implementar a classe vector personalizada em C++
O contêiner std::vector é conhecido como um array dinâmico de estilo C que armazena seus elementos de forma contígua. Mesmo que a implementação exata não seja imposta, alguns recursos do contêiner são exigidos pela especificação. Ou seja, um vetor deve ser uma estrutura de dados ordenada e fornecer acesso aleatório aos seus elementos. Outros recursos podem ser expressos como as funções de membro públicas expostas como uma interface, algumas das quais implementaremos nos exemplos a seguir. Observe que a implementação real de std::vector pode se tornar bastante extensa, portanto, estamos apenas demonstrando um ponto de partida a partir do qual o leitor pode adicionar mais recursos.
Em primeiro lugar, precisaremos definir uma classe MyVector como um modelo de função que pode armazenar qualquer tipo genérico. Então, podemos incluir membros de dados centrais como o ponteiro para a matriz de elemento e objetos inteiros para armazenar o tamanho / capacidade de acordo. Lembre-se de que std::vector pode alocar pedaços maiores de memória do que os elementos armazenados precisam para melhor desempenho. Esse tamanho de memória alocado é chamado de capacidade do vetor, e nós o armazenamos em um membro de dados cap. Estamos alocando uma quantia fixa (objetos 20) uma vez que um novo objeto MyVector é construído e definido os elementos atuais para zero.
Observe que utilizamos a função malloc, que pode ser considerada prejudicial no C++ contemporâneo, mas fornece flexibilidade e bom desempenho se usada com cuidado. Além disso, a memória alocada com malloc pode ser expandida com a função realloc, que precisaremos para gerenciar o redimensionamento do array.
No total, nossa classe contém três funções-membro e o operador [], que formam a base de um vetor dinâmico. O código de exemplo a seguir demonstra as implementações das funções push_back, size e operator[]. Os dois últimos são bastante intuitivos e simples de entender, enquanto push_back pode precisar de alguma explicação.
Observe que só precisamos alocar novas regiões de memória uma vez que o objeto é construído, quando o número de elementos excede a capacidade. Portanto, precisamos de dois caminhos separados para cada cenário na função push_back, um dos quais invocará a função realloc para expandir o bloco de memória atual. realloc aceita dois parâmetros: o ponteiro para a região de memória anterior e o tamanho da nova região em bytes. Se a chamada for bem-sucedida, um ponteiro válido é retornado, o mesmo que o ponteiro anterior ou um novo, dependendo se memória suficiente pode ser encontrada no mesmo bloco. Caso contrário, o ponteiro NULL é retornado para denotar que a solicitação falhou.
#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;
}
Produção:
1, 1.1
1, 1.2
1, 1.3
1, 1.4
/ ------------------- /
1, 1.1
1, 1.2
Para testar a classe MyVector, incluímos algum código de driver na função main e definimos o objeto personalizado MyClass para armazenar como elementos. Finalmente, adicionamos a função pop_back que remove um elemento na parte de trás do vetor. A função pop_back não precisa desalocar ou excluir o conteúdo do elemento. Ele pode apenas decrementar o membro elem_num em um em cada invocação, e a próxima chamada push_back reescreverá a posição do elemento descartado. Também é importante desalocar os blocos de memória quando o objeto sai do escopo. Portanto, precisamos incluir uma chamada para a função free em um destruidor da 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;
}
Produção:
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