Using the standard library

All too often, interviewers will ask you for an implementation of a linked list as if paying homage to your intro-to-programming professor's class. Indeed, this is a valuable exercise to gauge the proclivity to think algorithmically and to put those thoughts into code. Unless you're instructed otherwise by a professor or an interviewer, please use the standard library.

This chapter is about exploring the C++ Standard Library's commonly used headers. I will attempt to show how to use them effectively to solve common problems in C++. The C++ Standard Library is big, and I will not go over every header in it.

I intend to cover the following:

Containers

All containers in the C++ Standard Library have begin() and end() methods, which return iterators to the position of first element in the container and the position after the last element in the container, respectively.

std::vector<T>

The most fundamental container is the dynamically-sized array. In C++, we call this a vector.

Vectors can be found in the header <vector>.

Before discussing using std::vector, two terms must first be defined:

  • size: number of elements in the vector
  • capacity: amount of storage space allocated for the vector (in number of elements). c.capacity() >= c.size()

The follow code shows a few ways to construct a std::vector with elements of type int:

#include <vector>

int main() {
  std::vector<int> v; // Construct vector of size 0
  std::vector<int> v2(100); // Construct vector of size 100
  return 0;
}

To add an element to a std::vector, one will need to either call std::vector::push_back or assign with bracket notation.

Basically, std::vector::push_back will add an element to v at the position of v.end() and then will increment the size of v. If the size of v reaches the capacity of v, v will be reallocated which is an operation (but inserts are still amortized).

Assigning to index i with bracket notation is guaranteed , but will introduce undefined behavior if i >= v.size().

To retrieve an element of v at index i, there are two methods: bracket indexing (i.e., v[i]) or by calling std::vector::at (i.e., v.at(i)). Similar to bracket assignment, bracket indexing will introduce undefined behavior if i >= v.size(). Calling std::vector::at will throw an exception if i >= v.size(), making it a safer alternative. Both accesses are time.

The following code shows how to add elements of type double to a std::vector and print them:

#include <iostream>
#include <vector>

int main() {
  std::vector<double> v;
  v.push_back(1.5); // v = { 1.5 }
  v.push_back(2.5); // v = { 1.5, 2.5 }
  v.push_back(3.5); // v = { 1.5, 2.5, 3.5 }
  v[2] = 1.5;       // v = { 1.5, 2.5, 1.5 }

  for(std::size_t i = 0; i < v.size(); ++i) {
    std::cout << v[i] << " ";
  }

  std::cout << "\nTrying to access v.at(4): \n";
  try {
    std::cout << v.at(4) << std::endl;
  } catch(std::out_of_range &e) {
    std::cout << "Couldn't access v.at(4) because of " << e.what() << std::endl;
  }
  return 0;
}

Running the above code, we get the following output:

1.5 2.5 1.5 
Trying to access v.at(4): 
Couldn't access v.at(4) because of vector::_M_range_check: __n (which is 4) >= this->size() (which is 3)

This is what we expect, because we added 1.5, 2.5, and 3.5 to v then printed them all in order. We then attempted to access an index that is out of the bounds of the vector (i.e., 4 >= v.size()), so an exception was thrown (namely, std::out_of_range). This exception was caught and a nice message was printed instead of crashing the program.

v can be constructed with default value of "Hello" five times with the following construct:

std::vector<std::string> v(5, "Hello");

Two important methods to update both the size and capacity of a std::vector are std::vector::resize and std::vector::reserve, respectively.

More features of std::vector are available with C++11 or greater and will be covered later in this book.

Algorithms

IO