C++ STL

Vector
Deque
List
Array
Set
Multiset
Map
Multimap
Resources

Vector

[ | | | | =>

[Fast] Insert at back: O(1)
[Slow] Insert in beginning or middle: O(n)
[Slow] Search: O(n)

#include <vector>
vector<int> vec;
vec.push_back(5);
vec.at(0); //Throws range_error exception
vec.empty(); //bool Check if empty
vec.size();
vector<int> vec2(vec); // Copy constructor copies vec into vec2
vec.clear();
vec.swap(vec2);

Iterators

for(vector<int>::iterator itr = vec.begin(); itr!=vec.end(); itr++){
cout << *itr << endl; // *itr gives value stored
}

Alternatively for C++11,

for(auto it:vec) // Use &it for reference, if one wants changes in values
cout << it << endl;

Deque

<= | | | | =>

[Fast] Insert at front and back: O(1)
[Slow] Insert in middle: O(n)
[Slow] Search: O(n)

Implementation similar to vector

#include<deque>
deque<int> deq = {4,6,7};
deq.push_front(3);
deq.push_back(8);

List

[ ] <-> [ ] <-> [ ]

[Fast] Insert and Remove anywhere: O(1)
[Slow] Search: O(n)

Implementation

#include<list>
list<int> listt = {5,2,9};
listt.push_back(2);
listt.push_front(1);

Find

list<int>::iterator itr = find(listt.begin(), listt.end(),2); //itr -> 2

Insert

listt.insert(itr, 8); // Inserts in front of itr
itr++
listt.erase(itr)

Splice: Copies elements from list2 (from itr_a to itr_b) to list1 at itr

list1.splice(itr,list2,itr_a,itr_b);

Array

Thin layer around the naked array.

int a[3] = {3,4,5};
array<int,3> a = {3,4,5}; // Array container of type (int,3)

Limitations

Size is fixed : array<int,fixed_size>;
array<int,3> and array<int,4> are different types.

Usage

a.swap();
a.size();
a.begin();
a.end();

Set

[Slow] Insert O(log(n))
[Fast] Search O(log(n))

Non duplicate data
Value of elements cannot be modified

Do not use sets for simpler problems as insertion takes time and will cause performance issues.

#include<set>
set<int> myset;
myset.insert(2);
set<int>::iterator it;
it = myset.find(7);

pair<set<int>::iterator, bool> ret; // ret.second='false' if already exists
ret = myset.insert(3);

Insert via hint.

myset.insert(itr,9);

'itr' is hint. O(log(n)) => O(1). The better the hint, the better the performance.
Erase

myset.erase(itr);
myset.erase(7); // By value!

Multiset

[Fast] Search O(log(n))
[Slow] Traversing
A set that allows duplicate items
Value of elements cannot be modified

multiset<int> myset;

Map

[Fast] Find O(log(n))
No duplicate key
Keys cannot be modified
Type of itr: pair<char,int>

Implementation

map<char,int> mymap;

Insertion

mymap.insert(pair<char,int>('a',100));
mymap.insert(make_pair('z',200));
mymap.insert(itr,pair<char,int>('a',300)); // itr is a hint.

Multimap

Allows duplicate keys
Keys cannot be modified
Type of itr: pair<char,int>

(*itr).first = 'd'; // Error

Resources

Associative containers