(C++) Standard Template Library (STL) for Generic Programming

All of the Leetcode algorithm questions I recently solved involved vectors. When I learned C++ and OOP in school, we dealt with arrays most of the time. Since I’m not really used to vectors, I decided to self-study this topic and realized that vector is one of the types of STL. Therefore, I’m going to summarize the self-study note about STL that was provided in COMP 2012 (OOP) class.

---

The Standard Template Library (STL) is a collection of powerful, template-based, reusable codes.
It implements many general-purpose containers (data structures) together with algorithms.
To use STL, we need an understanding of the following 3 topics:

• containers
• iterators
• algorithms

---

STL containers

A container class is a class that holds a collection of homogeneous objects.
The object types need not be known when the container class is designed.

Containers in STL:

1. Sequence containers
   • Represent sequential data structures
   • Start from index/location 0
   • e.g. vector, list, deque
2. Associative containers
   • Non-sequential containers
   • Store (key, value) pairs
   • e.g. map, multimap, set, multiset
3. Container adaptors
   • adapted containers that support a limited set of container operations
   • e.g. priority-queue, queue, stack
4. Near-containers
   • Exhibit capabilities similar to those of the sequence containers, but do not support all their capabilities.
   • e.g. string

Sequence containers

Deque (double-ended queue)

• Unlike STL vector, its elements are not stored contiguously; it uses a sequence of chunks of fixed-size arrays.
• Like STL vector, its storage is automatically expanded or contracted as needed.
• Unlike queue, allows fast insertion and deletion at both ends.

Properties of sequence containers

Methods of deque

Element access for all:

• front(): first element
• back(): last element

Element access for vector and deque:

• []: subscript operator, index not checked.

Add/remove elements for all:

• push_back(): append element.
• pop_back(): remove last element.

Add/remove elements for list and deque:

• push_front(): insert element at the front.
• pop_front(): remove first element.

insert(p, x): insert an element x at position p. erase(p): remove an element at position p. clear(): erase all elements. size(): return the number of elements. empty(): return true if the sequence is empty. resize(int new_size): change size of the sequence (by assigning new memory space).

---

Container adaptors

Stack

Stack follows last-in first-out (LIFO) policy.

Major operations:

• top(): get the value of the top item.
• push(): add a new item to the top.
• pop(): remove an item from the top.
• empty()

Example codes

#include <iostream>
#include <stack>
using namespace std;

int main()
{
   // 1. Convert +ve decimal number to binary number using a stack
   stack<int> a;
   int x, number;

   while (cin >> number) {
      x=number;
      do {a.push(x%2); x/=2;} while (x>0);

      while (!a.empty()) {cout << a.top(); a.pop();}
   }

   return 0;

Algorithm to check balanced parenthesis

1. Scan the given character expression from left to right.
2. If a left parenthesis is read, push it onto a stack
3. If a right parenthesis is read, check if its matching left parenthesis is on the top of the stack.
4. If step 3 is true, pop the stack and continue.
5. If step 3 is false, return false and stop.
6. If the end of the expression is reached, check if the stack is empty.
7. If step 6 is true, return true otherwise false.

Queue

Queue follows first-in first-out (FIFO) policy.

Major operations:

• front(): get the value of the front item.
• enqueue(): add a new item to the back.
• dequeue(): remove an item from the front.
• empty(), size(), back(), push(), pop()

---

STL iterators: Generalized pointers

Iterators are generalized pointers. It helps us to traverse the elements of a sequence container sequentially.
STL sequence containers provide the begin() and end() to set an iterator to the beginning and end of a container.
For each kind of STL sequence container, there is an iterator type.

Iterators allow us to separate algorithms from containers when they are used with templates.

---

STL algorithms

STL also has algorithms that work with different containers. STL algorithms are implemented as global functions. e.g. find(Iterator first, Iterator last, const T& value)

find_if(Iterator first, Iterator last, bool predicate): iterator stops when a condition is satisfied.
The condition is called a predicate and is implemented by a boolean function.

Function pointer

C++ allows a function to be passed as argument to another function. We call this as passing the function pointer.

Examples

int larger(int x, int y) {return (x>y) ? x : y;}
int smaller(int x, int y) {return (x<y) ? x : y;}

int main() {
   int choice;
   cin >> choice;

   // choice==1 for larger function; other for smaller function
   int (*f) (int, int) = (choice == 1) ? larger : smaller;

   cout << f(3, 5) << endl;
   return 0;
}


// 2. Array of function pointers

// four functions: add, subtract, multiply, divide

int main()
{
   // Array of function pointers
   double (*f[]) (double x, double y) = { add, subtract, multiply, divide };

   int operation; double x, y;
   while (cin >> operation >> x >> y) {
      if (operation >= 0 && operation <= 3) { cout << f[operation](x, y); }
   }
   return 0;
}