Standard Template Library (STL)

The STL is a collection of powerful, template-based, reusable codes. It implements many general-purpose containers (data structures) together with algorithms that work on them.

STL Containers

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

Different Types of Containers:

Type of Container	STL Containers
Sequence	vector list deque
Associative	map set multimap multiset
Adaptors	priority_queue queue stack
Near-containers	bitset valarray string

Containers in the same category have similar public member functions algorithms.

• Sequence containers: Represent sequential data structures.
• Associative containers: Non-sequential containers. Store (key, value) pairs.
• Container adaptors: Adapted containers that support a limited set of container operations.
• "Near-containers" C-like pointer-based arrays: Exhibit capabilities similar to those of the sequence containers, but do not support all their capabilities.

Sequence Container Classes

Container	Descriptions	Access	Add/Remove
vector	1D array	$O(1)$	$O(1)$ at the end, $O(n)$ in front/middle
list	doubly-linked list	$O(1)$ at front/end, $O(n)$ in the middle	$O(1)$ (if no need to search for position? )
deque	double-ended queue	$O(1)$ random access	$O(1) at front/back, $O(n)$ in the middle

• 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.
• List operations are fast for list, but also available for vector and deque:
  • insert(p, x): Insert an element x at position p.
  • erase(p): Remove an element at position p.
  • clear(): Erase all elements.
• Miscellaneous Operations:
  • size(): Return the number of elements.
  • empty(): Return true if the sequence is empty.
  • resize(int new_size): Change size of the sequence.
• Comparison operators == != < etc. are also defined.

Container Adaptors: Stack and Queue

Some shared methods of stack and queue: empty() size() push() pop()

Some methods of stack: top()

Some methods of queue: front() back()

STL Iterators

Iterators

Iterators are generalized pointers.

For each kind of STL sequence container, there is an iterator type. E.g.,

• list<int>::iterator list<int>::const_iterator
• vector<string>::iterator vector<string>::const_iterator
• deque<double>::iterator deque<double>::const_iterator

STL sequence containers provide the begin() and end() to set an iterator to the beginning and end of a container.

A function find() that makes use of iterators:

template <class Iterator, class T>
Iterator find(Iterator begin, Iterator end, const T& value)
{
    while (begin != end && *begin != value)
        ++begin;
    return begin;
}

A function find_if() that makes use of iterators and accept a function as condition:

template <class Iterator, class Predicate>
Iterator find_if(Iterator first, Iterator last, Predicate predicate)
{
    while (first != last && !predicate(*first))
        ++first;
    return first;
}

The functions above work for all content types.

Some other useful functions: count_if for_each transform ...

Many of them can take function objects as input.

Function Objects

STL function objects are a generalization of function pointers.

An object that can be called like a function is called a function object, functoid, or functor.

Function pointers and lambdas are just two example of function objects.

An object can be called if it supports operator().

A function object must have at least operator() overloaded, and they may have other member functions/data.

Function objects are more powerful than function pointers, since they can have data members and therefore carry around information or internal states.

A function object (or a function) that returns a boolean value (of type bool) is called a predicate.

Example:

// ...
class Greater_Than
{
    private:
    int limit;
    public:
    Greater_Than(int a) : limit(a) { }
    bool operator()(int value) { return value > limit; }
};
int main() 
{
    // ...
    Greater_Than g(350);
    p = find_if( x.begin(), x.end(), g );
}

Others

Friend operator<<

It is possible to declare a friend operator<< inside a class definition and define the function later.

// file: friend-operator.cpp
#include <iostream>
using namespace std;

class A {
    private: int a = 1;
    public: friend ostream& operator<<(ostream& os, const A& a);
};

ostream& operator<<(ostream& os, const A& a) {
    os << a.a;
    return os;
}

int main() {
    A a;
    cout << a << endl;
    return 0;
}

g++ friend-operator.cpp -o friend-operator

Execution result: 1

typedef Keyword

typedef is a keyword used to introduce a synonym for an existing type expression: typedef <a type expression> <type-synonym>

The code below is ok:

// file: typename.cpp
typedef int NUMBER;
NUMBER main() { return 0; }

Function Pointers

Consider the function:

template <typename T>
inline const T& larger(const T& a, const T& b) {
    return a > b ? a : b;
}

Then the type of the function pointer of the template larger is: inline const T& (*)(const T&, const T&)

Here are some weird things that function pointers can do:

#include <iostream>
using namespace std;

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

int main()
{
    int choice;
    cout << "Choice: (1 for larger; others for smaller): ";
    cin >> choice;

    int (*f)(int, int) = (choice == 1) ? larger : smaller;

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

You can even create an array of function pointers:

#include <iostream>
using namespace std;
double add(double x, double y) { return x+y; }
double subtract(double x, double y) { return x-y; }
double multiply(double x, double y) { return x*y; }
double divide(double x, double y) { return x/y; }

int main()
{
    double (*f[])(double x, double y) // Array of function pointers
        = { add, subtract, multiply, divide };
    
    int operation; double x, y;
    cout << "Enter 0:+, 1:-, 2:*, 3:/, then 2 numbers: ";
    while (cin >> operation >> x >> y) 
    {
        if (operation >= 0 && operation <= 3)
            cout << f[operation](x, y) << endl;
        cout << "Enter 0:+, 1:-, 2:*, 3:/, then 2 numbers: ";
    }
    return 0;
}