Vector

Hey folks! Today we are going to dive into the world of C++ vectors. In this blog, we will cover the basics of using vectors and explore the fundamental syntax of vectors. We will also touch upon some related techniques that you wonld not want to miss.

I would like to give a special thanks to @The Cherno for teaching me C++ through his C++ series on YouTube. Please subscribe to his channel if possible!

Brief intro

Vector is a powerful datatype in the C++ standard library that functions similarly to an array list. Although its name may suggest a relation to mathematical vectors, it is actually quite different. One of its notable features is the ability to dynamically change its size and query its current size. Let’s dive into the details.

Simple demo

Here is a simple demo to showcase the basic usage of vectors in C++. Most of the important points are explained in the comments:

cpp

#include<iostream>
#include<vector> // include the vector library to use vectors

// Define a struct called Vertex with three float values
struct Vertex
{
	float x, y, z;

    Vertex(float x, float y, float z)
        : x(x), y(y), z(z) // initialization list
    {}
};

// Define an overloaded operator<< function to allow printing of Vertex objects to std::cout
std::ostream& operator<<(std::ostream& stream, const Vertex vertex)
{
	stream << "(" << vertex.x << ", " << vertex.y << ", " << vertex.z << ")";
	return stream;
}

// Main function
int main()
{
	std::vector<Vertex> vertices; // create a vector of Vertex objects called vertices

	vertices.push_back({ 1, 2, 3 }); // add a new Vertex object with x=1, y=2, and z=3 to the end of the vector
	vertices.push_back({ 4, 5, 6 }); // add another Vertex object with x=4, y=5, and z=6 to the end of the vector

	// Loop through each element in the vector and print its value using the overloaded << operator
	for (int i = 0; i < vertices.size(); i++)
		std::cout << vertices[i] << std::endl;

	vertices.erase(vertices.begin() + 1); // remove the second element (index 1) from the vector

	// Loop through each element in the vector using a range-based for loop and print its value using the overloaded << operator
	for (Vertex& v : vertices)
		std::cout << v << std::endl;

	std::cin.get(); // wait for user input before closing the program
}

Here are some important things to keep in mind when using vectors in C++:
1. Make sure to include the vector library in your code so that you can use the vector class.
2. Add data to the end of the vector using the push_back() method.
3. Remove data using the erase() method with the index of the element you want to remove.
4. You can obtain the initial location of the vector by calling the begin() method.
5. Unlike Java, where a class is required to be the vector’s data type, in C++, we can use basic types such as int as the vector’s data type

In this demo, we’ve used some interesting techniques that are worth noting:
1. Overloading the << operator to customize output for the vector. (We will talk about overloading operator in another blog)
2. Copying data can be slow and inefficient, so using references (&) can help avoid this issue.
3. We are using a range-based for loop here, which Python programmers might find familiar.
4. The initialization list for Vertex class is defined within the class itself. (Further details about initialization lists may be discussed in a future blog post)

Optimization of vector

The above simple demo just show basic usage of vector, which can be slow and inefficient without any optimization.

Normal vectors have various limitations, but for today, we will focus on addressing the issue of copying to improve their performance.

Avoid copy

The best way to optimize is knowing the environment we are working with. Thus, we need to identify where the vector is being copied. Here is an example code:

cpp

#include<iostream>
#include<vector>

struct Vertex
{
	float x, y, z;

	Vertex(float x, float y, float z)
		: x(x), y(y), z(z)
	{}

	Vertex(const Vertex& vertex)
		: x(vertex.x), y(vertex.y), z(vertex.z)
	{
		// highlight that our vector is copied
		std::cout << "Copied!" << std::endl; 
	}
};

int main()
{
	std::vector<Vertex> vertices;
	vertices.push_back(Vertex(1, 2, 3));//line 23
	vertices.push_back(Vertex(4, 5, 6));
    vertices.push_back(Vertex(4, 5, 6));

	std::cin.get();
}

Running the above code, we get six “Copied” in the console.

Avoid copy result from reallocation

Once a vector’s capacity is exceeded, it needs to reallocate new memory which involves copying data to a new location, deleting old data, and adding new data. This process can be slow and inefficient, and it is where we begin the optimization process.

Every time the push_back() method is called, the vertices vector is reallocated due to its size not being sufficient. To optimize this, we can call the reserve() method to specify that the size of the vector should be 3, thereby avoiding unnecessary reallocations.

cpp

   ...// omit
   std::vector<Vertex> vertices;
   
   // state that the size should be 3
   vertices.reserve(3);

vertices.push_back(Vertex(1, 2, 3));
vertices.push_back(Vertex(4, 5, 6));
   vertices.push_back(Vertex(4, 5, 6));
...

In the given code, calling reserve(3) before adding the elements will optimize the performance by avoiding three unnecessary memory reallocations and copying.
After using the reserve() method, we will only get 3 “Copied”.

Avoid copy caused by constructing function

In the example code, lines 29-30 create a Vertex in the main scope using a constructor, and then copy it to the vector. This is inefficient and can be improved by using the emplace_back() method instead.
cpp
1
2
3
vertices.emplace_back(1, 2, 3);
vertices.emplace_back(4, 5, 6);
vertices.emplace_back(4, 5, 6);
The emplace_back() method pass parameters list directly to the constructor, avoiding unnecessary copy.

After applying the optimization mentioned above, rerun the code and you will observe that there are no “Copied” statements being printed in the console.