Custom vector in c ++
What do you need to know for implementation?
Pointers
Move semantics (optional stage)
rValue and lValue of the link (Optional step)
Templates
Iterators (Optional Stage)
Overriding Operators
Introduction
I will be using c ++ 20. Also, this article is broken down into stages:
First step
First you need to create template class… For this it is used template
template<typename T>
class Vector {
};
Next, we determine which fields will contain the class:
Pointer to the memory area where the array will be located.
Vector size (size)
Maximum vector size (capacity)
With the first and second points, everything is clear. And what is the third one for? In answering this question, you need to remember that vector – this is a dynamic array… Therefore, in order not to allocate new memory each time you add an element, you need to allocate it with a margin.
template<typename T>
class Vector {
private:
T* arr_;
size_t size_{};
size_t capacity_{};
};
You also need to add class constructor…
template<typename T>
class Vector {
public:
Vector() {
arr_ = new T[1];
capacity_ = 1;
}
private:
T* arr_;
size_t size_{};
size_t capacity_{};
};
Second phase
Now you need to add these methods:
Method that checks if the list is empty
Method for getting the size of a vector
Method for obtaining the maximum vector size
New memory allocation method
Item adding method
Item removal method
1) Method that checks if the list is empty
[[nodiscard]] bool isEmpty() const {
return size_ == 0;
}
2) Method for obtaining the size of a vector
[[nodiscard]] size_t size() const {
return size_;
}
3) Method for obtaining the maximum vector size
[[nodiscard]] size_t capacity() const {
return capacity_;
}
4) Method of allocating new memory
We will create a new array arr_
with size capacity * 2to allocate more memory. But before that you need to write the previous array arr_
to another pointer tmp
… Then we fill in the free cells of the array arr_
cells tmp. Don’t forget to remove the pointer tmp
so that there is no memory leak.
void addMemory() {
capacity_ *= 2;
T* tmp = arr_;
arr_ = new T[capacity_];
for (size_t i = 0; i < size_; ++i) arr_[i] = tmp[i];
delete[] tmp;
}
5) Method of adding element
First you need to check if there are free cells. If they are not present, we call addMemory()
… Next, we write the element to the index size_
and increase size_
by 1.
void pushBack(const T& value) {
if (size_ >= capacity_) addMemory();
arr_[size_++] = value;
}
6) Element removal method
Here it is necessary to clarify that this method will have one argument – the index of the element to be removed…
To delete an element in the beginning or in the middle, you need to move all elements that are to the right of this one by 1 cell. And then reduce size_
by 1. If this element is at the end of the array, we simply decrease size_
by 1.
void remove(size_t index) {
for (size_t i = index + 1; i < size_; ++i) {
arr_[i - 1] = arr_[i];
}
--size_;
}
Third stage
In this step we will add:
1) Index reversal operator
There should be two such operators:
Operator that returns a regular item reference
Operator that returns a constant reference to an element
T& operator[](size_t index) {
return arr_[index];
}
const T& operator[](size_t index) const {
return arr_[index];
}
2) Destructor
The destructor is needed so that, after leaving the scope, the vector itself deletes the pointer.
~Vector() {
delete[] arr_;
}
3) Operator for writing to a stream
It is needed so that we can output the entire vector to the console, files, etc.
template<typename T>
inline std::ostream& operator<<(std::ostream& os, const Vector<T>& vec) {
for (size_t i = 0; i < vec.size(); ++i) os << vec[i] << " ";
return os;
}
Additional stage
Here we add:
1) Iterators
They are needed for algorithms from the library. algorithm
and also for the cycle for each
T* begin() {
return &arr_[0];
}
const T* begin() const {
return &arr_[0];
}
T* end() {
return &arr_[size_];
}
const T* end() const {
return &arr_[size_];
}
2) Constructors with move semantics
This is necessary for the vector to copy and move correctly.
When we copy a vector, we must remember to pass all the elements of the vector other
into the current vector using a loop for
…
When do we call the constructor with lvalue reference, then we delete the current pointer arr_
and move all information about the other vector to the current vector.
Vector(Vector& other) {
if (this != &other) {
delete[] arr_;
arr_ = new T[other.capacity_];
for (size_t i = 0; i < other.size_; ++i) arr_[i] = other.arr_[i];
size_ = other.size_;
capacity_ = other.capacity_;
}
}
Vector(Vector&& other) noexcept {
if (this != &other) {
delete[] arr_;
arr_ = other.arr_;
size_ = other.size_;
capacity_ = other.capacity_;
other.arr_ = nullptr;
other.size_ = other.capacity_ = 0;
}
}
3) Assignment operators
This is the same as copy constructors and constructors with move semantics, only operators.
Vector& operator=(Vector& other) {
if (this != &other) {
delete[] arr_;
arr_ = new T[other.capacity_];
for (size_t i = 0; i < other.size_; ++i) arr_[i] = other.arr_[i];
size_ = other.size_;
capacity_ = other.capacity_;
}
return *this;
}
Vector& operator=(Vector&& other) noexcept {
if (this != &other) {
delete[] arr_;
arr_ = other.arr_;
size_ = other.size_;
capacity_ = other.capacity_;
other.arr_ = nullptr;
other.size_ = other.capacity_ = 0;
}
return *this;
}
Outcomes
You now understand how a vector works in C ++. The complete code can be found on github…