Vectors

Containers

The C++ standard library contains several containers. As the name suggests, these are classes that act as containers for storing data. There is a specific C++ array class (note that these are not the same as C-like arrays). As is the case with C-like arrays, once an array has been created, it is difficult to change the size and modify the contents by removing or adding in new element. There is another type of container that exists called vector. This class is useful as it is possible to remove specific element and add in extra elements very easily. The class handles increasing or decreasing the size of the array.

It can be used by including the following header.

#include <vector>

Creating a vector

The example below demonstrates how to create an empty vector. Note this example is for an int vector, but it possible to create vectors for other data types, custom struct's and classes such as complex.

  // create an empty vector
  std::vector<int> v;

  // add some values (push_back() adds values to the end)
  v.push_back(2);
  v.push_back(9);
  v.push_back(8);
  v.push_back(3);
  v.push_back(4);
  v.push_back(1);
  v.push_back(5);
  v.push_back(7);
  v.push_back(6);
  v.push_back(0);

  // get the size
  std::cout << "The vector has " << v.size() << " elements.\n";

  // we can access specific elements
  std::cout << "Element 2 is " << v[2] << std::endl;

This will produce the following output.

The vector has 10 elements.
Element 2 is 8

Iterators

By now you should be familiar with iterating through things such as arrays. This is typically done using a for loop to iterate through an index and then using that index to select a specific element. The example below is for a string.

  // create a string
  std::string alphabet = "abcdefghijklmnopqrstuvwxyz";

  // the 'old' C-like way of iterating over the string would be
  // something like this
  for (unsigned int i = 0; i < alphabet.size(); i++) {
    std::cout << alphabet[i] << std::endl;
  }

There is actually a more powerful 'C++' way that can be used for all container classes. This involves using an iterator from the C++ Standard Template Library (STL). This is demonstrated below.

// the 'new' C++ way of iterating through a container (e.g. string, array)
  // is to use an 'standard template library' (STL) iterator
  for (std::string::iterator i = alphabet.begin(); i < alphabet.end(); i++) {
    std::cout << *i << std::endl;
  }

Here we create a string iterator. When using an array or vector, we must create the relevant iterator type. We can then use the begin and end methods to easily get bounds of the container and since the iterator is of the same type as the element we can then use it directly using the * operator (a bit like de-referencing a pointer).

The code below shows how to iterate through the vector we created earlier.

std::cout << "The contents are:\n";
  // iterate through and print values
  for (std::vector<int>::iterator i = v.begin(); i < v.end(); i++) {
    std::cout << *i << std::endl;
  }

This would then produce the following output.

The contents are:
2
9
8
3
4
1
5
7
6
0

Popping elements

It is easy to remove the last element.

// we can easy delete the last element
  v.pop_back();

  std::cout << "The contents are now:\n";
  // iterate through and print values
  for (std::vector<int>::iterator i = v.begin(); i < v.end(); i++) {
    std::cout << *i << std::endl;
  }

Which would produce the following output.

The contents are now:
2
9
8
3
4
1
5
7
6

Sorting

Another advantage of using C++ containers is that it becomes easy to sort the elements. This can be done using the sort function. Note that to use this the algorithm header file must be included.

  // we can use the 'sort' method from <algorithm> to sort values
  std::sort(v.begin(), v.end());
  std::cout << "The contents are now:\n";
  // iterate through and print values
  for (std::vector<int>::iterator i = v.begin(); i < v.end(); i++) {
    std::cout << *i << std::endl;
  }

We can simply pass in the beginning and end of the vector and the sort algorithm will arrange the elements in ascending order. The following output would be produced.

The contents are now:
1
2
3
4
5
6
7
8
9

To sort the elements in descending order, a custom sorting function must be created. This is just a simple function that takes in two values of the correct datatype. It then just returns true or false depending on which of the two arguments is the largest.

bool sort_descending(int i, int j) { return i > j; }

We can then pass this function into the sort function to sort the elements in descending order.

std::sort(v.begin(), v.end(), sort_descending);
  std::cout << "The contents are now:\n";
  // iterate through and print values
  for (std::vector<int>::iterator i = v.begin(); i < v.end(); i++) {
    std::cout << *i << std::endl;
  }

If this code was then executed, the following output would be produced.

The contents are now:
9
8
7
6
5
4
3
2
1

Inserting and erasing specific elements

We have seen that we can use the push_back() and pop_back() methods in order to add and remove elements to/from the end of the vector. We can also insert and erase elements (or ranges of elements) from specific places in the vector. To erase:

 // we can also erase elements by specifying either a single element
  v.erase(v.begin());  // delete the first element (0)
  // or by specifying a range (0,1,2,3)
  v.erase(v.begin(), v.begin() + 3);
  std::cout << "The contents are now:\n";
  // iterate through and print values
  for (std::vector<int>::iterator i = v.begin(); i < v.end(); i++) {
    std::cout << *i << std::endl;
  }

This would produce the following output.

The contents are now:
5
4
3
2
1

Similarly, we can insert values in specific places.

 // it is also possible to insert values at the specified position
  v.insert(v.begin(), 6);
  v.insert(v.end(), 0);
  std::cout << "The contents are now:\n";
  // iterate through and print values
  for (std::vector<int>::iterator i = v.begin(); i < v.end(); i++) {
    std::cout << *i << std::endl;
  }

This would produce the following output.

The contents are now:
6
5
4
3
2
1
0