STL Part I

Introduction to STL

Containers expose the iterator interface and the Algorithms work on the iterators.

std::vector

Example of iterating through a vector is below. Iterator behaves like an enhanced pointer.

#include <iostream>
using namespace std;

int main()
{
    vector<int> nums;
    nums.push_back(3);
    nums.push_back(1);
    nums.push_back(2);

    vector<int>::iterator first = nums.begin();
    vector<int>::iterator onePastLast = nums.end();

    for(vector<int>::iterator i = first; i != onePastLast; i++)
    {
        cout << "Next Element is " << *i << endl;
    }

    //sorting a vector
    sort(first,onePastLast); //after sorting 1,2,3
}

Types of containers

• Sequence containers(array and linked list): vector, deque, list, forward list, and array
• Associative containers (binary tree) : set, multiset, map, and multimap
• Unordered containers (hash table) : unordered set/multiset, unordered map/multimap

Sequence containers

A vector is a dynamic array that grows in a single direction. It has a size() member function that returns the size. Vector can be accessed using the indexing operator []. However using that operator
provides no range check. Use vec.at(2) which can throw index out of range exception. C++11 style of traversing a vector is:

for(auto& v : vec)
{
    cout << "Element is "<< v << endl;
}

empty() can check if the container is empty. size provides the size of the container. clear() removes all items in the container. swap swaps the contents of two containers.

Performance chracteristics of vectors

• O(1) insert/remove at the end
• O(N) insert/remove at the beginning or middle
• O(N) search

Deque

A deque can grow at the end or beginning. Example:

deque<int> q = {1,2,3};
deq.push_front(5); 
deq.push_back(10);

cout << deq[2] << endl;

Performance characteristics of deque

• O(1) insert/remove at the beginning or the end
• O(N) insert/remove at the middle
• O(N) search

List

A list is a doubly linked list that can be visualized as follows:

List provides fast insert/remove anywhere in the list.

Performance characteristics of list

• O(1) insert/remove anywhere
• O(N) search
• O(N) random access

Code example:

list<int> lst = {5,2,9};
lst.push_back(6);
lst.push_front(10);

list<int>::iterator foundLoc = find(lst.begin(), lst.end(), 2);
lst.insert(foundLoc,8); //{5,8,2,9}

foundLoc++; //iterator points to 9
lst.erase(foundLoc); //removes 9 

Because vector stores data in contiguous chunk of memory. So when it is brought into cache, lot of it can be cached. However, with linked lists, there can be many cache misses.

List can be used to do fast splice:

lst.splice(itr,mylist2,itr_one, itr_two);

Forward list is just like list except it is singly linked.

STL provides a thin wrapper around native arrays. They cannot be dynamically resized though.

array<int 3>a = {3,4,5};

Associative Containers

Associative containers are implemented by binary trees and are always sorted. Sorted according to "<". No push_back() or push_front().

Set provides no duplicate items. Insertion takes O(N log N). Member function find takes O(log N) time. insert function returns a pair of values (pair<set<int>::iterator, bool>ret).

set<int> st;
st.insert(3);
st.insert(1);
st.insert(2); {1,2,3}

multiset allows duplicate items. Insertion is always successful. For set and multiset, the value of the elements cannot be modified.

Properties of set/multiset

• O(log N) search
• Traverse is slow compared to vector and deque
• No random access

Map/multimap

Map and multimap deal with keys and values.

map<char,int> mymap;
mymap.insert(make_pair('a',100));

map<char,int>::iterator it = mymap.begin();

it = mymap.find('a'); //O(log(n))

//printing out:
for(it = mymap.begin() ; it != mymap.end(); it++)
{
    cout << (*it).first << "=>" << (*it).second << endl;
}

multimap allows duplicated keys. Map is sorted based on keys. Set and multimap are special cases of map/multimap where the keys are the same as values.

Unordered Associative Containers (C++11)

Unordered containers are implemented by hash tables. Finding element in hash table is O(1).

unordered_set<string> myset = {"Red", "Green", "Blue"};
unordered_set<string>::const_iterator it = myset.find("Green"); //Amortized O(1)
if(it != myset.end()) //need to check!
{
    cout << "Found " << *it << endl;
}

vector<string> myvec = {"Teal","Purple"};
myset.insert(myvec.begin(), myvec.end());

Amortized O(1) might degrade because of hash collisions. Unordered map example:

unordered_map<char, string> day = {{'S',"Sunday"}, {'M',"Monday"}};

cout << day['S'] << endl; //has no range check
cout <<day.at['S'] << endl; //has range check

day['W'] = "Wednesday"; //same as inserting. Can modify existing member
day.insert(make_pair('T',"Thursday"));

multimap and unordered_multimap can't be used for associative arrays as they don't have unique keys and don't implement the [] operator.

STL provides container adaptors stack (LIFO), queue(FIFO), and priority queue-first item has the greatest priority. Array based containers such as vector and deque might invalidate pointers(raw pointers, iterators, and references) whenever elements are added/removed.

References

Bo Qian STL Video: https://www.youtube.com/watch?v=gxZJ5JNuWMY