The Standard Template Library (STL) is a programmer's dream. It offers efficient ways to:

  • store
  • access
  • manipulate
  • view data

and is designed for maximum extensibility. Once a programmer has gotten over the initial syntax hurdles, they quickly learn to appreciate the STL's sheer power and flexibility.

Overview of STL

  • Containers: a collection of container classes. For example:

    • map: an associative collection of key/value pairs
    • vector: a growing list of elements.
  • Iterators: objects that view and modify ranges of stored data. Each STL container exports iterators. Iterators have a common interface, allowing the programmer to write code that operates on data stored in arbitrary containers.

  • Algorithms: functions that operate over ranges of data specified by iterators.

  • Adapters: objects which transform an object from one form into another. For instance:

    • stack adapter transforms a regular vector or list into a LIFO (Last In First Out) container.
    • istream_iterator transforms a standard C++ stream inot an STL iterator.
  • Functions: facilities for creating and modifying functions at runtime.

  • Allocators: allow clients of the container classes to customize how memory is allocated and deallocated, either for diagnostic or performance reasons.

Vectors

A std::vector is an object that represents a sequence of elements. The elements in a vector are indexed, meaning that they can have a well-defined position in the sequence.

#include <iostream>
#include <vector>  // Necessary to use vector
#include <string>
#include <sstream>
// Create a vector containing integers
std::vector<int> v = {7, 10, 15, 8, 98, 0};

Add two more integers to vector using push_back()

v.push_back(45);
v.push_back(56);

Helper function to iterate and print values of vector

void PrintVector(std::vector<int>& v){
    for(int n : v){
        std::cout << n << ' ';
        
    }
    
    std::cout << std::endl;
}
PrintVector(v)
7 10 15 8 98 0 45 56 

The storage of the vector is handled automatically, being expanded and contracted as needed. Vectors usually occupy more space than static arrays, because more memory is allocated to handle future growth. This way a vector does not need to reallocate each time an element is inserted, but only when the additional memory is exhausted.

Grow the vector, setting new elements to 0

v.resize(10);
PrintVector(v)
7 10 15 8 98 0 45 56 0 0 

The total amount of allocated memory can be queried using capacity() function. Extra memory can be returned to the system via a call to shrink_to_fit()

capacity(): returns the number of element that can be held in currently allocated storage

v.capacity()
12

shrink_to_fit(): reduces memory usage by freeing unused memory

v.shrink_to_fit()
v.capacity()
10

resize(): changes the number of elements stored. E.g; Grow the vector, setting new elements to 100**

v.resize(13, 100);
PrintVector(v);
7 10 15 8 98 0 45 56 0 0 100 100 100 
v.capacity()
20

pop_back(): removes the last element

v.pop_back();
PrintVector(v);
7 10 15 8 98 0 45 56 0 0 100 100 

NOTE: for detailed information about std::vector, check out the C++ reference.

deque

There are several aspects of the vector that can be troublesome in certain applications. In particular, the vector is only designed to grow in one direction; calling push_back() inserts elements at the end of the vector, and resize() always appends elements to the end.

A std:deque is an indexed sequence container that allows fast insertion and deletion at both its beginning and its end. As opposed to std:vector, the elements of a deque are not stored contiguously: typical implementations use a sequence of individually allocated fixed-size arrays, with additional bookkeeping, which means indexed access to deque must perform two pointer dereferences, compared to vector's indexed access which performs only one.

#include <iostream>
#include<deque>

Create a deque (pronounced "deck") containing integers

std::deque<int> d = {45, 48, 40, 79};
void PrintDeque(std::deque<int>& d){
    for(int n : d){
        std::cout << n << ' ';
        
    }
    
    std::cout << std::endl;
}
PrintDeque(d);
45 48 40 79 

Add an integer to the beginning and end of the queue

d.push_front(13);
d.push_back(25);
PrintDeque(d);
13 45 48 40 79 25 

A deque can do everything a vector can do and also unlike a vector, it is possible (and fast) to push_front and pop_front

NOTE: for detailed information about std::deque, check out the C++ reference or just type ?std::queue in a notebook cell to get live documentation.

Container Adapters

How can we implement stack and queue using the containers we have?

Stack

Stack is a type of container adapters with LIFO (Last In First Out) or FILO (First in, Last Out) data structure, where a new element is added at one end and (top) an element is removed from that end only.

Stack: just limit the functionality of a vector/deque to only allow push_back and pop_back.

The functions associated with stack are:

  • empty() -- Returns whether the stack is empty
  • size() -- Returns the size of the stack
  • top() -- Returns a reference to the top most element of the stack
  • push(g) -- Adds the element 'g' at the top of the stack
  • pop() -- Deletes the top most element of the stack
#include <stack>

Create a stack of integers

std::stack<int> s;

Helper function to show the stack

void ShowStack(std::stack<int> mystack){
    
    std::stack<int> s = mystack;
    while (!s.empty()){
        
        std::cout << '\t' << s.top();
        s.pop();
    }
    
    std::cout << std::endl;
}
ShowStack(s)

Push some elements onto the stack

s.push(10);
s.push(30);
s.push(20);
s.push(5);
ShowStack(s)
	5	20	30	10

Get stack size

s.size()
4

Get the top of the stack

s.top()
5

Pop top of the stack

s.pop();
ShowStack(s)
	20	30	10

Queue

Queue is a type of container adaptors which operate in a first in first out (FIFO) type of arrangement. Elements are inserted at the back (end) and are deleted from the front.

The functions supported by queue are:

  • empty() -- Returns whether the queue is empty
  • size() -- Returns the size of the queue
  • front() -- Returns a reference to the first element of the queue.
  • back() -- Returns a reference to the last element of the queue
  • push(g) -- Adds the element g at the end of the queue
  • pop() -- Deletes the first element of the queue.
#include <queue>

Create an empty queue

std::queue<int> q;

Helper function to show content of the queue

void ShowQueue(std::queue<int> myqueue){
    
    std::queue<int> q = myqueue;
    while (!q.empty()){
        
        std::cout << '\t' << q.front();
        q.pop();
    }
    
    std::cout << std::endl;
}
ShowQueue(q)

Add some elements to the queue

q.push(10);
q.push(20);
ShowQueue(q)
	10	20

Get queue size

q.size()
2

Get front of the queue

q.front()
10

Get back of the queue

q.back()
20

Pop front of the queue

q.pop()
ShowQueue(q)
	20