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

Welcome to this tutorial on building a dynamic array, also known as a vector, in C++. Before diving in, it's assumed that you have a grasp of fundamental C++ or C concepts like variables, primitive types, loops, and if-conditions, arrays and pointers. If these basics are unfamiliar to you, it's recommended to explore introductory C++ courses on platforms like YouTube before proceeding with this tutorial.

What is a Vector?

A vector is a linear data structure that stores elements sequentially. While it shares similarities with an array, a vector offers a crucial advantage: it can dynamically resize itself when it approaches its maximum capacity. Unlike static arrays, users of the vector class don't need to concern themselves with managing the size of the array. The vector class takes care of resizing automatically.

Vectors are a common feature in the standard libraries of various programming languages, although they might go by different names, such as "dynamic array" in some contexts.

Now, let's embark on the journey of building a vector class from scratch. This tutorial will guide you through each step, explaining the concepts and code implementation along the way. By the end, you'll not only have a functional vector class but also a deeper understanding of dynamic arrays and their inner workings. Let's get started!

Exploring std::vector functionality

Introduction

The vector class is provided as part of the C++ standard, so you can directly use it in your actual programs without the need to build it from scratch. Here we give a broad overview of the vector class offered by the The STL before we implement our own:

You can find the C++ standard documentation of the vector class header here

Before using the vector class, you must include its header file:

#include <vector>

Here are different ways to create a vector object:

std::vector<int> v1 = {1, 2, 3, 4};
std::vector<double> v2({1.1, 1.2});
std::vector<char> v3{};// empty vector that can hold chars

std is a namespace in which all standard library facilities reside, <int> is a template argument that specifies the type of data that the vector will hold, and {1, 2, 3, 4}, {1.1, 1.2} are initialiazer lists.

Initializing a vector object

There are different ways to initialize a vector object and here are some of them:

An empty vector:

std::vector<int> vec1{};
std::vector<double> vec2;

Populate a vector with a specific value

std::vector<int> vec1(5, 10); // vec1 = {10, 10, 10, 10, 10}

Populate a vector with a default value of a type:

std::vector<int> ivec2(5);  // populate the vector with 5 zeros
std::vector<double> dvec2(5); // populate the vector with 5 zeros
std::vector<std::string> svec2(5); // populate the vector with 5 empty strings ("")
std::vector<char> cvec2(5 // populate the vector with 5 null terminating characters

Initialize a vector with a range:

int a[5] = {0, 1, 2, 3, 4};
std::vector<int> vec3(a, a+5); // vec3 = {0, 1, 2, 3, 4}

Initializing a vector using another vector (copying):

std::vector<int> vec2 = {0, 1, 2, 3, 4};
std::vector<int> vec3(vec2); // vec3 = {0, 1, 2, 3, 4}

// or
std::vector<int> vec4 = {0, 1, 2, 3, 4};
std::vector<int> vec5 = vec4; // vec5 = {0, 1, 2, 3, 4}

Accessing vector elements

The vector class provides different ways to access the elements of a vector object:

operator[] and at()

This is the same conventional method to access elements of a static array, and conveniently the vector elements can be accessed the same way by specifying the index of an element within the square brackets:

std::vector<int> vec2 = {0, 1, 2, 3, 4};
std::cout << vec2[0] << ", " << vec[1] << std::endl; // 0, 1

The only problem with this way of accessing elements is that when you try to access elements that are outside of the range of the vector, the compiler will not complain about it, and it will give you a garbage value.

at() works the same as the operator[] except that it performs range (or bound) checking, and your program will throw an error if you tried to access an index that is outside of the range of defined values of the vector:

int a[5] = {0, 1, 2, 3, 4};
std::vector<int> vec3(a, a+5);

// using try/catch to capture the error
try
{
	std::cout << "Trying to access 40th element of vec3 despite only declaring 5 elements! \n";
	std::cout << "vec3[4] = " << vec3.at(40) << std::endl;
}

catch(const std::exception& e)
{
	std::cerr << e.what() << '\n';
}

front() and back()

As the name of the methods suggest, they enable you to access the first and last elements of a vector:

std::vector<int> vec3 = {0, 1, 2, 3, 4};
std::cout << "vec3.front() == 0? " << (vec3.front() == 0? "yes\n" : "no\n");   \\ yes
std::cout << "vec3.back() == 4? " << (vec3.back() == 4? "yes\n" : "no\n");     \\yes

data()

This method gives you direct access to the underlying array stored within a vector object:

std::vector<char> vec4 = {'A', 'C'};
char* data = vec4.data();
std::cout << "data[0] = " << data[0] << std::endl; // vec4[0] = 'A'

Inquiring about vector storage

The vector class provides us with handy methods to learn about the storage consumed by the vector, and these methods are:

Understanding the size and capacity of a vector is crucial for efficient memory management:

// size and capacity
std::size_t size = myVector.size();
std::size_t capacity = myVector.capacity();

// resizing
myVector.resize(8); // Resize to 8 elements

Modifier methods

Push Back and Pop Back:

myVector.push_back(42); // Add an element to the end
myVector.pop_back();    // Remove the last element

Insert and erase

myVector.insert(myVector.begin() + 2, 99);  // Insert 99 at index 2
myVector.erase(myVector.begin() + 4);       // Erase element at index 4

Comparison

You can compare 2 vectors by using the comparison operators >, <, >=, ... etc.

std::vector<int> anotherVector = {1, 2, 3, 4, 5};
if (myVector == anotherVector) {
    // Vectors are equal
}

Next: Building The Vector Class