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:

  1. Pointer to the memory area where the array will be located.

  2. Vector size (size)

  3. 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 vectorthis 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 tmpso 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 argumentthe 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:

  1. Operator that returns a regular item reference

  2. 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. algorithmand 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

Similar Posts

Leave a Reply

Your email address will not be published. Required fields are marked *