EN.601.220: C++ Standard Template Library

C++ Standard Template Library

The Standard Template Library (STL)

Provides basic containers (data structures that hold data) and algorithms to make our programming jobs much easier!
First we use, then learn how to write, classes
First we do sequence containers: <vector>, <list>
Other provided containers include array, deque, forward_list, stack, queue, priority_queue, set, multiset, map, multimap, unordered_(set/multiset/map/multimap).
See the cplusplus.com STL library documentation for details (make sure to scroll down on the linked page, there is a master table of what containers can do what)

Sequence container common operations

mysequence.front() reference to 1st element
mysequence.back() reference to last element
mysequence.push_back(val) push val on back, return void
mysequence.pop_back() pop element and return void (use back() to get value before pop)

Requirements of base data type: copy constructor, = , == , <, default constructor for initialization

Basic template concepts

Templates define a class or function that can be used with multiple data types
The actual data type becomes in some sense a parameter
Example: vector<int> v; // declare v as a vector of ints
--put the type of vector elements in <> after the class name
(Looks very similar to Java's generics but is in fact different in subtle ways)

Vector Type

It's a smart array, an array with lots of extra features
Inserts and deletes at back are directly supported and are very efficient
Insert or delete in middle are possible but are slow -- have to shift elements
Can access elements with v[num] notation, but no range error checking
Using v.at(num) is like v[num] but with range checking -- use this!
When fills up, will automatically resize to add more memory and copy to new memory (like realloc)
Note that string is a lot like a vector of chars so a lot of vector will look like string

Advantages of using vector</code:

Good random access performance
Supports random access iterators
Supports all algorithms (discussed later)

Disadvantage: lacks fast insert/delete from middle.

Examples of declaring and using vectors:

vector<int> v;        // v is an empty vector of ints
vector<int>::size_type vsize;

const int SIZE=5;
int a[SIZE] = {2, 3, 4, 5, 6};
vector<int> v(a, a+SIZE);// initializes v to the contents of array a

vector<int> v(10);       // vector size 10, elements initialized to 0 default
vector<int> v2(10, 5);   // vector size 10, init to 5

if (v.empty())
        v.assign(10, 2);    // size 10, init to 2
v.assign(a, &a[SIZE]);
v.assign(v2.begin(), v2.end());

v.resize(25, 2);         // add elements init to 2, size 25
v.reserve(25);           // capacity 25, no init

Iterators

Object to help you move through a container, one item at a time
Iterators are general and flexible compared to just using integer index iteration: can iterate through all forms of C++ containers
Declare as e.g. vector<int>::iterator vi
vector<int>::iterator here is a type for vector iterators packaged with the vector class
Iterator works by moving a pointer to an element down the collection
const version vector<int>::const_iterator cvi that only allows reading of the underlying elements
vi = v.begin() - moves pointer to first element
vi = v.end() - moves to point after last element
Can do addition on iterators to advance through vectors

Example:

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

int main(void) {
    vector<double>; dv = {1.1,2.2,3.3,4.4,5.5};
    vector<double>::iterator di = dv.begin();
    di++;                  // di now points to 2.2
    di = di + 3;           // similar to pointer arithmetic on arrays; di now at the 5.5
    di = dv.erase(di);     // delete the item pointed to by di, make di point to next element in dv
    // dv now { 1.1 2.2 3.3 4.4 }
    dv.insert(di,3.3);     // insert before di; means at end since di at end now
    // dv now { 1.1 2.2 3.3 4.4 3.3 }

    di = dv.begin();
    while (di != dv.end()) { cout << *di << " "; di++; }
    cout << endl;
}

Lists

Under the hood it is an implementation of a doubly linked list
Efficient for insert/delete in the middle
Not as efficient for random access; no notation mylist[i]
Supported operations beyond vector ops: splice, merge, front(), push_front(val), pop_front(), remove(val), unique() (must sort first), reverse()

A few more STL details

When you have a vector of pointers to dynamically allocated objects, erasing the element does not delete the object pointed to
If an element is erased from a vector, any other iterators currently sitting further down the vector are invalidated -- the data got moved from under them!

Algorithms in STL

<algorithm> header contains a vast number of useful algorithms: find elements, move, swap, shuffle, sort, etc.
Warning: there are limitations on the types of iterators that the different algorithms will work on
All algorithms act on container elements (data inside), size doesn't change

Searching/sorting algorithms

void sort(is, ie)
void sort(is, ie, bool func(valtype, valtype))
iter find(is, ie, val)    // returns iter to 1st occurrence of val in range
iter find_if(is, ie, bool func(valtype))
bool binary_search(is, ie, val) // container must be sorted first
bool binary_search(is, ie, val, bool func(valtype, valtype))

Sorting Lists

For vectors and other containers you can use the sort fuction in <algorithm> but linked lists need a specialized sort method
list.sort() relies on < operator to be defined on the type of elements of the list
list.sort(cmp) uses predicate comparator function cmp, similar to C's qsort()

Example:

bool compare(const Card & x, const Card & y) { 
  return x.face  <  y.face;
}

sort(hand.begin(), hand.end(), compare);

Associative Containers, briefly

Associative containers are like array/vector except replace the sequential number indexing with an arbitrary key.
Examples: set, multiset, map, etc
They lack sequence-focused operators like front, back, push_front/back etc
They are still internally ordered so you can iterate over them with an iterator
Still can insert, erase, etc
Map
- Defines a finite function from any type to any type
- Each element of a map is a pair (domain,range)
- In a map each domain element maps to at most one range (use a multimap if you want to allow more than one range value)
- Array syntax overloaded for pleasant lookup/modification: myRating["Star Wars"] = GOOD;