Vector Implementation in C++
This article will demonstrate how to implement a class similar to std::vector in C++.
Use malloc and realloc Functions to Implement Custom vector Class in C++
The std::vector container is known as a dynamic C-style array that stores its elements contiguously. Even though the exact implementation is not enforced, some features of the container are required by the specification. Namely, a vector should be an ordered data structure and provide random access to its elements. Other features can be expressed as the public member functions exposed as an interface, some of which we will implement in the following examples. Note that the actual std::vector implementation can get quite extensive, so we are just demonstrating a starting point from where the reader might add more features.
At first, we will need to define a MyVector class as a function template that can store any generic type. Then we can include core data members like the pointer to the element array and integer objects to store size/capacity accordingly. Remember that std::vector may allocate larger chunks of memory than stored elements need for better performance. This allocated memory size is called the capacity of the vector, and we store it in a cap data member. We are allocating a fixed amount (20 objects) once a new MyVector object is constructed and set the current elements to zero.
Notice that we utilize the malloc function, which may be considered harmful in contemporary C++, but it provides flexibility and good performance if used with caution. Additionally, the memory allocated with malloc can be expanded with the realloc function, which we will need to manage the resizing of the array.
In total, our class contains three member functions and [] operator, which form the basis for a dynamic vector. The following example code demonstrates push_back, size and operator[] function implementations. The latter two are quite intuitive and simple to understand, while push_back may need some explanation.
Note that we only need to allocate new memory regions once the object is constructed when the number of elements exceeds the capacity. So, we need two separate paths for each scenario in the push_back function, one of which will invoke the realloc function to expand the current memory block. realloc accepts two parameters: the pointer to the previous memory region and the size of the new region in bytes. If the call is successful, a valid pointer is returned, either the same as the previous pointer or a new one depending on if enough memory could be found in the same block. Otherwise, the NULL pointer is returned to denote the request failed.
#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;
}
Output:
1, 1.1
1, 1.2
1, 1.3
1, 1.4
/ ------------------- /
1, 1.1
1, 1.2
In order to test the MyVector class, we include some driver code in the main function and define MyClass custom object to store as elements. Finally, we add the pop_back function that removes an element at the back of the vector. The pop_back function does not need to deallocate or delete the element contents. It can just decrement elem_num member by one on each invocation, and the next push_back call will rewrite the discarded element position. It’s also important to deallocate the memory blocks once the object goes out of scope. Thus, we need to include a call to free function in a destructor of the class.
#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;
}
Output:
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