What are data structures?

What are data structures? Chapter 9

In the previous chapter, we have learned the basic types that any programming language has. In this chapter, we are going to look at some new types, which are actually collections of the basic types. These are also known as data structures.

There are many different data structures, but two of them are by far the most used ones: arrays and maps.

Data Structure 1: Arrays (Lists / Vectors)

This data structure is an ordered collection of elements.

Imagine that you have a blog with a newsletter that people can sign up for. As people sign up, the list of people that have signed up needs to stored somewhere, in some format. This is what arrays are good for.

An array has an index that starts from 0 and gets bigger as you add more elements to it.

Going back to the newsletter example, let’s imagine that we just want to store a person’s first name when they sign up (obviously, you’d want to store their email address, but this isn’t meant to be realistic). You would create an empty array, and then add to that array the first name of each person, as they sign up.

Then, you can access the first person’s name by checking what the array’s value is at the index 0. In the same way, you could check the third person’s name by checking the value at index 2 (remember, we start counting the index at 0).

Python Lists

We’re going to look at arrays in Python first. Python calls them “lists”. Here’s what it would look like:

names = []

names.append("Jim")
names.append("Tom")
names.append("Bill")

print(names[0])
print(names[2])

On the first line, we created an empty list (or array) that we stored in the variable called names. Then, we called a function that works with lists that appends (adds at the end) the value that you give it. I know this last sentence doesn’t make complete sense, but we will learn about these kinds of functions soon!

After adding the 3 names, we print to the console the elements of the names array at index 0 and 2. This should print "Jim" and "Bill".

C++ Vectors

In C++, since we have to specify the type of each variable, we also need to do it for our arrays. This means that we need to tell the C++ compiler what the type for our array elements is going to be. Here’s what it would look like:

#include <iostream>
#include <string>
#include <vector>

using std::cout, std::string, std::vector, std::endl;

int main() {
    vector<string> names;
	
    names.push_back("Jim");
    names.push_back("Tom");
    names.push_back("Bill");
	
    cout << names[0] << endl;
    cout << names[2] << endl;
	
    return 0;
}

We first import iostream to be able to print things to our console using cout. Then, we import string because each element of our array is a string. Lastly, we import vector because this is the array type that we will use .

C++ actually has an array type, but the reason why we use vector instead the array type is because arrays in C++ make you specify the number of elements beforehand. This means that, once you have filled your array to the specified size, you can’t add more elements to it. Instead you can just replace existing elements with new values. On the other hand, vectors have an unlimited size, just like Python lists.

You might have noticed the weird using std::cout, std::string, std::vector, std::endl;. This is a line that removes the need to add std:: before things like string or cout. Its exact meaning is not important yet, but you will learn it at some point. If you’re curious now, try searching for something like “Why do we put std in front of cout in C++”.

The rest of the code is pretty similar to Python’s implementation, but do notice how we specified the type of elements in the vector by setting it between < and >.

The endl at the end of the printing commands are used to add a new line after printing each name (Python does this automatically).

Data Structure 2: Maps (Dictionaries)

Take everything you know about arrays, but instead of having an integer index which starts at 0, imagine that you’re allowed to make your own index.

This is what maps are. It’s an array which, instead of just setting the value of each element, you also set the “key” that leads to that value.

This key can be of any basic data type. This means that a map loses the ordering that an array has, because it’s no longer a bunch of integers incremented by one for the next element.

Let’s imagine that you now want to store information about a person.

Python Dictionaries

In Python, we use dictionaries to have a map data structure. Here’s what it looks like:

person1 = {}

person1["First Name"] = "Jim"
person1["Last Name"] = "Barry"
person1["Age"] = 34
person1["Is a parent?"] = False

print(person1["First Name"])
print(person1["Last Name"])
print(person1["Age"])
print(person1["Is a parent?"])

We first created an empty dictionary, and then added 4 key-value pairs. What you can notice here is that the values in the person1 dictionary are of different types. We have strings, an integer and a boolean. This is something we can’t do in C++. There, they all have to be of the same type.

C++ Maps

In C++, we’ll use only strings as values, because we need to tell the C++ compiler beforehand what the types of our keys and values are. Here’s what it looks like:

#include <iostream>
#include <string>
#include <map>

using std::cout, std::string, std::map, std::endl;

int main() {
    map<string, string> person1;
	
    person1["First Name"] = "Jim";
    person1["Last Name"] = "Barry";
    person1["Age"] = "34";
    person1["Is a parent?"] = "No";
	
    cout << person1["First Name"] << endl;
    cout << person1["Last Name"] << endl;
    cout << person1["Age"] << endl;
    cout << person1["Is a parent?"] << endl;
	
    return 0;
}

The implementation is similar to Python’s implementation. However, we can see that, when we declare the person1 map, we specify the two types corresponding to the type of the keys and the type of the values.

Since the values need to have the same type (strings, in this case), we set the values of Age and Is a parent? as strings instead of integer and boolean.

Combining Data Structures

Now, what if we want a list of people that have signed up for our newsletter, with extra information about each person. We can combine our array and map data structures together!

We could create an array where each of its element is a map.

Python List of Dictionaries

In Python, it would look like this:

people = []

person1 = {}
person2 = {}
person3 = {}

person1["First Name"] = "Jim"
person1["Email"] = "jim@mail.com"

person2["First Name"] = "Tom"
person2["Email"] = "tom@mail.com"

person3["First Name"] = "Bill"
person3["Email"] = "bill@mail.com"

people.append(person1)
people.append(person2)
people.append(person3)

print(people[0]["First Name"])
print(people[0]["Email"])

print(people[2]["First Name"])
print(people[2]["Email"])

We first create our empty list and dictionaries, fill the dictionaries, and then append them to the list.

C++ Vector of Maps

The equivalent code for C++ looks like this:

#include <iostream>
#include <string>
#include <vector>
#include <map>

using std::cout, std::string, std::vector, std::map, std::endl;

int main() {
    vector<map<string, string> > people; 

    map<string, string> person1;
    map<string, string> person2;
    map<string, string> person3;
	
    person1["First Name"] = "Jim";
    person1["Email"] = "jim@mail.com";
	
    person2["First Name"] = "Tom";
    person2["Email"] = "tom@mail.com";
	
    person3["First Name"] = "Bill";
    person3["Email"] = "bill@mail.com";
	
    people.push_back(person1);
    people.push_back(person2);
    people.push_back(person3);
	
    cout << people[0]["First Name"] << endl;
    cout << people[0]["Email"] << endl;
	
    cout << people[2]["First Name"] << endl;
    cout << people[2]["Email"] << endl;
	
    return 0;
}

The logic is identical to the Python code, but we need to notice how we declared the type of the vector. Each element of the vector has a map, which in turn is a key-value pair of string keys and string values.

These are the most crucial data types. Using them, and especially combining them, you can create quite complex data structures.


Next: Chapter 10 (WIP)

If you want to start from the beginning of the series, go to chapter 0.

By Radu

Software Engineer and Computational Scientist graduated from the Technical University of Munich. Worked at Shopify, DRW and Ubisoft.

Leave a comment

Your email address will not be published.

Join my mailing list to get an email whenever a new chapter comes out!