Standard Template Library

Program's main objective is to manipulate data and generate results
requires ability to store, access and manipulate data

Components of STL

• Containers
• Iterators - step through container elements
• Algorithms - manipulate data
  Containers and iterators are declared as class templates

Sequence containers

Every object has a specific position

Predefined sequence containers
{cpp}vector, {cpp}deque, {cpp}list

Sequence container vector
logically - same as arrays
processed like array

All containers
use same names for common operations
have specific operations

Vector

Stores, manages objects in a dynamic array
Elements accessed randomly
Time-consuming item insertion - middle & beginning
Fast item insertion - end

#include <vector>
vector <int> intList
vector <string> strList;

// creates empty vector without any elements
vector <elemType> vecList;

// creates a vector vecList and initializes it to the elements of otherVecList. vecList and otherVecList are of the same type
vector <elemType> vecList (otherVecList);

// creates vecList of the size 'size'. vecList initialized using the default constructor
vector <elemType> vecList (size);

// creates vecList of size n, initialized using n copies of the element elem
vector <elemType> vecList (n, elem);

// creates vecList initialized to the elements in range [begin, range).
vector <elemType> vecList (begin, end);

Manipulating data in a vector

Basic operations

• Item insertion
• Item description
• Stepping through the elements

vecList.clear();
vecList.erase(position);
vecList.erase(begin, end);
vecList.insert(position, elem);
vecList.insert(position, n, elem);
vecList.insert(position, begin, end);
vecList.push_back(elem);
vecList.pop_back(elem);
vecList.resize(num);
vecList.resize(num, elem)

{cpp}.clear() does not remove data from memory, just changes vector size to 0.
{cpp}.erase() deletes data at the given indices, then moves the remaining to keep the vector integrity
{cpp}.insert() shifts data forward, to create the space for the new data

Declaring an Iterator to a Vector Container

{cpp}class vector contains {cpp}typedef iterator
declared as a public member

vector <int> intVec = {1, 3, 5, 7, 9};
vector <int>::iterator it;
for (it = intVec.begin(); it != intVec.end(); ++it)
	cout << *it << endl;
// *it dereferences the iterator to the value

Requirements for using {cpp}typedef iterator

• container name (vector)
• container element type
• scope resolution operator

vec.begin();     // returns iterator to position of the first elem
vec.end();       // returns iterator to memory after the last elem
vec.capacity();  // returns memory allocated to the vec
vec.empty();     // true is vec is empty
vec.size();      // current size (number of elems)
vec.max_size();  // max num of elements that can be inserted
vec.rbegin();    // reverse begin - ptr to the last elem in vec
vec.rend();      // reverse end - ptr to mem before first elem
vec.swap(vec2);  // swap elements of vec with vec2
vec.insert(pos, elem); // insert elem at pos. pos is an iterator
vec.erase(pos1, pos2); // delete data between pos1...pos2-1. 

Deque

Double ended queue

Doesn't save data in one consecutive block, but many smaller ones. Relies on a map to map all smaller blocks.

STL {cpp}stack adapter

STL {cpp}stack container is actually an adapter
Indicated by container type as one of its type parameters

stack <T, C<T> > stck;  // T is the elemType, C is container type
stck.push;  // push onto the stack
stck.pop;   // pop from the stack

If no container specified {cpp}stack <T> stck, default is deque, but its also possible to specify a vector of list as the container for the stack.

So basically we're creating a vector/list/deque but with only possible operations being {cpp}push and {cpp}pop

STL {cpp}queue adapter

queue <T, C<T> > qqe;

C may be any container supporting {cpp}push_back() and {cpp}pop_front()
The default container is {cpp}deque, but {cpp}list can be also used