Published on

Walking through the basics of C++ by building the standard vector class from scratch (P2)

Authors

Previous: Exploring the standard vector library functions

Plan of attack

Now that we've explored the rich functionality of std::vector, it's time to embark on a hands-on journey of building our own vector class. Throughout this process, we'll delve into essential concepts and gradually construct a vector class that mirrors the capabilities of its standard counterpart.

  • We will divide our progress into the following milestones:
    • A static container of double elements.
    • A container that can shrink and expand in size automatically and upon request.
    • A container that can perform all essential operations.
    • A generic container.
    • A container that is compatible with the canonical C++ standard container.
    • Clean up and optimizations.

Milestone 1: A static container of double elements

If your knowledge in C++ classes it a bit rusty, you can take a look at C++ Classes article where I dwell in detail about classes.

Let's first layout our objectives with this milestone:

  • Vector can store double elements
  • Vector can be default constructed
  • We can specify the size of a vector and default initialize its elements
  • We can specify the size of a vector and initialize all its elements with a specific value
  • We can use an initializer list to initialize our vector
  • We can access elements at a specific index using 2 methods
  • We can access first and last element
  • We can inquire about the size and capacity of the vector
  • We can check if our vector is empty or not
  • We can access the underlying array of the vector
  • We can clear all elements of the vector

The Vector class

A class is an entity ties together representation of a data type and its operations. The representation of our vector class is: a pointer that points to double data, the current size of the data, and the capacity storage of data that the vector can store For vector operations, we will use the same names that the standard vector class uses. You can review back part 1 of this tutorial where we went through the existing standard vector.

Create a header file, name it Vector.h, then blast the code below into it.

#include <iostream>
#include <initializer_list>

class Vector {
public:
	// constructors
    Vector();                                // default constructor
    Vector(std::size_t);                     // default fill constructor
    Vector(std::size_t, double);             // fill constructor
    Vector(std::initializer_list<double>);   // initializer list constructor

	// accessors
	double& at(std::size_t);
	double& operator[](std::size_t);
	double& front();
	double& back();

	// storage
    double* data() const;
    std::size_t size() const;
    std::size_t capacity() const;
    bool empty() const;

	// modifiers
	void clear();

private:
    double* _data;
    std::size_t _size;
    std::size_t _capacity;
};

We will implement all our class member functions in the same file Vector.h.

Before you move on to the next section, try to implement all these functions yourself.

Constructors

Vector::Vector()
    : _data{new double[0]}, _size{0}, _capacity{0}
{}

Vector::Vector(std::size_t size)
    : _data{new double[size]}, _size{size}, _capacity{size}
{
    for (int i = 0; i < size; ++i) {
        _data[i] = {};
    }
}

Vector::Vector(std::size_t size, double val)
    : _data{new double[size]}, _size{size}, _capacity{size}
{
    for (int i = 0; i < size; ++i) {
        _data[i] = val;
    }
}

Vector::Vector(std::initializer_list<double> ilist)
    : _data{new double[ilist.size()]}, _size{ilist.size()}, _capacity{ilist.size()}
{
    int i = 0;
    for (auto& e : ilist)
    {
        *(_data + i) = e;
        ++i;
    }
}
  • Use member initializer lists to initialize class data members:
: _data{new double[10]}, _size{0}, _capacity{0}

I suggest to pause here for a moment, and read about Constructor's Members Initializer List as I explain them in full detail.

  • This line of code shows an initialization method that C++ provide to initialize a variable with its default value depending on its type, take a look at this article to learn about Initialization in C++:
        _data[i] = {};

_data{new double[size]}
  • Initializer list constructor allows us to use {}-form to pass elements
Vector::Vector(std::initializer_list<double> ilist)
    : _data{new double[ilist.size()]}, _size{ilist.size()}, _capacity{ilist.size()}

Here we use std::initializer_list to pass an array of objects to our constructor. Read this article where we explain List initialization for more details.

  • You will notice that all our storage member functions data, size, capacity and empty are all marked as const, and this is how we signal to the compiler that we are not planning on making an changes on the private data members.

The destructor

The Vector class is a container that models a handle-to-data to manage the resources acquired by the object during its lifetime, therefore, the Vector class is responsible for not only the acquisition of resources but also releasing them, which is known as RAII (Resource Acquisition is Initialization).

Now, let's modify the Vector class by adding a destructor:

#include <iostream>

class Vector {
public:
    // ...
    ~Vector();

    // ...
private:
    // ...
};

And, within that destructor, we will delete our resource handle _data, which will get invoked automatically when object goes out of scope:

Vector::~Vector() {
	delete[] _data;
}

Accessors

double& Vector::at(std::size_t idx) {
    if (idx > _size || idx < 0)
        throw std::out_of_range("index greater than the size or less than zero is not allowed");

    return *(_data + idx);
}

double& Vector::operator[](std::size_t idx) {
    return *(_data + idx);
}

double& Vector::front() {
    return *_data;                  // or, _data[0]
}

double& Vector::back() {
    return *(_data + (_size - 1));  // or, _data[_size - 1]
}

double* Vector::data() {
    return _data;
}

  • Notice that our accessors so far (except data()) return a reference type, and this is great to avoid making unnecessary copies of our elements, and just refer to the existing ones. This approach will make our code more efficient.

  • We have utilized exceptions to do bound checking here:

if (idx > _size || idx < 0)
        throw std::out_of_range("index greater than the size or less than zero is not allowed");

Check the official C++ documentation: Exceptions - cppreference.com
Also, read our article about Error Handling

  • Note how we overloaded the square brackets operator so that we can access our vector elements as if it's a built-in type
double& Vector::operator[](std::size_t idx) {
	// ...
}

For more information, read our article about Operator Overloading

size(), capacity() and empty()

Storage inquiry functions, so far, are pretty straight forward:

std::size_t Vector::size() {
    return _size;
}

std::size_t Vector::capacity() {
    return _capacity;
}

bool empty() {
    return _size == 0;
}

clear()

  • Note that clear() is only responsible for clearing the content of the vector. The memory remains attached to the vector. That isn't just likely either. It's required. In particular, if you were to add elements to the vector again after calling clear(), the vector must not reallocate until you add more elements than what was previously sized.

With that being said, simply, our implementation of clear() will be:

void clear() {
    _size = 0;
}

Next: Making the vector dynamic

Discuss on Twitter • View on GitHub