Vectors, Pairs and Maps

September 11, 2018

In this tutorial, we’ll learn about different types of containers in C++. In particular, we will learn about vectors, maps and pairs in C++.

Vectors

Earlier, you learnt about C++ Arrays. Vectors are like arrays, but they are more flexible. In particular, you might remember that it is not possible to change the size of a C++ array after it is declared. Vectors provide us the flexibility of inserting and deleting elements even after they are declared.

Declaring a Vector

Suppose you are taking a survey of 100 people and you have to store their age. To solve this problem in C++, you can create a vector of integers with 100 elements. For example:

#include <iostream>
#include <vector>
using namespace std;
int main() {
vector <int> age (100); // vector "age" with 100 ints
return 0;
}

Notice that we need to include the vector library first, otherwise we get an error. Also, we specify the data type of the vector elements in angle brackets, like so: <int>.

Here is another way to declare and initialize a vector:

// Empty vector of with elements of type "string"
vector <string> names;

Size

Let’s confirm how many elements there are in the vectors:

cout << age.size() << endl;
// Output - 100
cout << names.size() << endl;
// Output - 0

You can use the push_back() function to add a single element to your vector. For example:

// Empty vector of with elements of type "int"
vector <int> lottery;
lottery.push_back(3);   // vector is now {3}
lottery.push_back(42);  // vector is now {3, 42}
lottery.push_back(12);  // vector is now {3, 42, 12}
lottery.push_back(19);  // vector is now {3, 42, 12, 19}
lottery.push_back(30);  // vector is now {3, 42, 12, 19, 30}
lottery.push_back(59);  // vector is now {3, 42, 12, 19, 30, 59}

Displaying the vector

Here’s a for-loop to display all the elements of the vector.

cout << lottery.size() << endl;
for (int i = 0; i < lottery.size(); i++) {
cout << lottery[i] << " ";
}
cout << endl;

Output:

6
3 42 12 19 30 59

Ok! We can see that our push_back()s worked as expected.

Let’s put this in a function so we don’t have to keep repeating it.

void display_vector(vector <int> v) {
for (int i = 0; i < v.size(); i++)
cout << v[i] << " ";
cout << endl;
}

Accessing elements

Elements of a vector can be accessed using indexes (in same manner as we access arrays elements). For example:

// print first element of the vector (index 0)
cout << lottery[0] << endl;
// Output - 3
// print the last element of the vector (index 5)
cout << lottery[5] << endl;
// Output - 59
// update the value at index 3
lottery[3] = 17;
// vector is now {3, 42, 12, 17, 30, 59};
// take input from the user and insert at third element (index 2)
cin >> lottery[2];   // Suppose the input is 9
display_vector(lottery);
// Output - 3 42 9 17 30 59

Note: If you try to access vector elements outside of its bound, let’s say lottery[8], the compiler may not show any error. However, this may cause unexpected output (undefined behavior).

Handy, right?

Removing elements from the end

To delete the last element of vector, you can use pop_back():

// Suppose vector is {3, 42, 12, 19, 30, 59}
lottery.pop_back();   // vector is now {3, 42, 12, 19, 30}
lottery.pop_back();   // vector is now {3, 42, 12, 19}
cout << lottery.size() << endl;
display_vector(lottery);

Output:

4
3 42 12 19

See how 59 and 30 have been removed and the vector size has changed to 4.

Sorting, reversing, etc

Now, let’s see how to sort the vector. To sort a vector, we use the sort() function from the algorithm library.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void display_vector(vector <int> v) {
for (int i = 0; i < v.size(); i++)
cout << v[i] << " ";
cout << endl;
}
int main() {
// Empty vector of with elements of type "int"
vector <int> lottery;
lottery.push_back(3);   // vector is now {3}
lottery.push_back(42);  // vector is now {3, 42}
lottery.push_back(12);  // vector is now {3, 42, 12}
lottery.push_back(19);  // vector is now {3, 42, 12, 19}
lottery.push_back(30);  // vector is now {3, 42, 12, 19, 30}
lottery.push_back(59);  // vector is now {3, 42, 12, 19, 30, 59}
cout << "Before Sorting: ";
display_vector(lottery); // display the vector
sort(lottery.begin(), lottery.end()); // sort
cout << "After Sorting: ";
display_vector(lottery); // display the vector
return 0;
}

Output:

Before Sorting: 3 42 12 19 30 59
After Sorting: 3 12 19 30 42 59

As you can see, the numbers in your vector are now sorted from the lowest to highest value! But what’s going on in the following line?

sort(lottery.begin(), lottery.end());

The sort() function takes two arguments - the begin and end locations of the vector. For the lottery vector, we can access these locations using lottery.begin() and lottery.end(). These locations are of type iterator, and we’ll discuss them in more detail in the next section.

Maybe we want to reverse the order of the elements? Let’s do that!

reverse(lottery.begin(), lottery.end());
display_vector(lottery);
// Output - 59 42 30 19 12 3

See, reverse() is similar to sort() and has same arguments.

That worked like a charm!

Iterators

In the vectors section earlier, you briefly encountered iterators. Iterators are used to point at the memory addresses of STL containers like vectors, maps, etc. You saw that v.begin() and v.end() point to the starting and ending locations of vector v.

Let’s see how we can use an iterator (part of the <iterator> library) to iterate over a vector:

vector <int> :: iterator it;
for (it = lottery.begin(); it != lottery.end(); it++) {
cout << *it << " ";
}
cout << endl; 

Here’s what the above code is doing:

In line 1, we declare the iterator. The general syntax is

container_type <data_type> :: iterator name;

Then, we initialize it to lottery.begin(), which is the beginning position of your vector. Then, as we increment it with it++, which will update it to point towards next element of your vector. We keep traversing the vector till it has reached the end of the vector lottery.end().

Now, we need to use the * operator to access a value from an iterator. The * operator says, “give me the value stored at this location”. Hence, cout << *it << " "; prints the value at the current location it is pointing to.

Pair

The pair is also a C++ container like vectors and arrays. It is defined in the <utility> library. As the name pair suggests, it can hold two elements. Its usefulness comes from the fact that the data elements can be of two different types.

Declaring a Pair

Let’s create a pair where the first element is an integer and the second is a string:

#include <iostream>
#include <string>
#include <utility>
using namespace std;
int main() {
pair <string, int> p;
p.first = "Roger Federer";
p.second = 37;
cout << p.first << " - " << p.second << endl;
// Output: Roger Federer - 37
return 0;
}

We state the data-types in angle brackets <> as before. We access the first and second element of a pair p as p.first and p.second.

We can also use the the make_pair() function to change the value of a pair:

pair <string, int> p;
p = make_pair("Roger Federer", 37);
cout << p.first << " - " << p.second << endl;

Declaring a Pair with initialization

We can initialize pairs in the following ways:

pair <int, char> p2(1, 'a');  // different data types
pair <int, int>  p3(1, 10);   // same data type
pair <int, int>  p4(p3);      // copy of p3

Maps

A map is similar to a vector, but you access values by looking up a key instead of a numeric index. Map is part of the <map> library.

Declaring a map and accessing elements

Let’s define a map where the keys are of type string and the values of of type int. In general, the syntax for declaring a map is:

map <key_type, value_type> name;

Lets see an example. We will start by declaring an empty map, and then add elements to it (as we did for the lottery vector):

#include <iostream>
#include <string>
#include <map>
using namespace std;
int main() {
map <string, int> age;
age["Alice"] = 23;
age["Bob"] = 18;
age["Charlie"] = 28;
age["Eve"] = 22;
cout << age["Bob"] << endl; // Output - 18
cout << age["Eve"] << endl; // Output - 22
return 0;
}

In the program above, we declare a map called age. Then, we added some key—value pairs to it.

As you can see, we access the value of individual keys with this syntax:

age["Alice"]

See, it’s similar to an array. But you don’t need to remember the index – just the key.

Size

You can use the .size() function to see the total number of key—value pairs in the map (same as vectors):

cout << age.size() << endl;
// Output - 4

Iterating over all key—value pairs

Let’s define a function to display all the key—value pairs of a map:

void display_map(map <string, int> m) {
map <string, int> :: iterator it;
for (it = m.begin(); it != m.end(); it++) {
cout << (*it).first << " " << (*it).second << endl;
}
cout << endl;
}

Above, we are iterating over a map using iterators (as you did previously with vectors). But what’s going on with (*it).first and (*it).second?

Since you are iterating over a map which is a bunch of key—value pairs, when you do *it you get a pair. In particular, since this is a <string, int> map, you get a <string, int> pair.

So, your iterator is pointing to a pair and to access the value from the iterator, we use * operator, and to get the first and second value from the pair, we use the dot operator.

The * operator followed by the . operator can be shortened to the -> operator. So, you can also access the first and second elements of the pairs as:

cout << it->first << " " << it->second << endl;

Now that you know how to iterate over the elements of a map and print its values, let’s call the display_map() function from main():

display_map(age);

Output:

Alice 23
Bob 18
Charlie 28
Eve 22

Awesome! You can now see what’s in your map!

Invalid keys and default values

What happens if you ask C++ the value of a key that doesn’t exist? Let’s try it and see!

cout << age["ThisWasNeverInserted"] << endl;
// Output - 0

Interesting! If a key is not present in the map and we access it, C++ creates the key with a default value. If the value of type int, the default value is 0.

Let’s confirm that C++ did actually add a new key—value pair.

display_map(age);

Output:

Alice 23
Bob 18
Charlie 28
Eve 22
ThisWasNeverInserted 0

Confirmed!

We can also confirm the existence of key-value pair by another method.

We do this with the help of find(key) function. This function will return the iterator pointing at key’s memory address, if the key is present. If it is not, then it will return the iterator pointing at the end of the map i.e. map.end().

For example:

if (age.find("FunnyKey") != age.end()) {
cout << "Found!" << endl;
}
else {
cout << "Doesn't exist!" << endl;
}
// Output - Doesn't exist!
display_map(age);
// Confirm that this time, the key "FunnyKey" wasn't added to the map

Deleting elements

Use the erase() function for deleting elements.

age.erase("Bob");
display_map(age);

Output:

Alice 23
Charlie 28
Eve 22
ThisWasNeverInserted 0

When should you use a map or a vector?

Well, that’s a good point to ponder. Just have a solution in mind before looking at the answer in the next line.

• Do you just need an ordered sequence of items? Go for a vector.
• Do you need to associate values with keys, so you can look them up efficiently (by key) later on? Use a map.

Summary

Awesome! You know a lot about programming now. In this tutorial you learnt about:

• vectors – Vectors are sequence containers similar to arrays, with the additional flexibility the elements can be inserted / deleted
• pairs – a pair of values which may be of different types
• maps – container which stores key–value pairs
• iterators - Iterators point to a location. C++ containers such as vectors and maps define .begin() and .end() iterators, which allows us to iterate over all values in the container.

Time for some coding exercises!