This is a simplified quick reference of a few things from the C++ Standard Library.
In case of any mistakes below, please please file an issue on the GitHub repo.
C++11 is a version of C++ with several (awesome) new features (some of which are used in this page). I've tried to mention which feature came with C++11 when I discuss the feature.
To compile code as C++11, pass a -std=c++11 flag to your compiler.
g++ -std=c++11 file.cpp
Since C++11, types can be inferred using auto.
// instead of
int x = 5;
// can use
auto x = 5;
// This is more useful in cases like:
map<char, int>::iterator it = mymap.begin();
// vs
auto it = mymap.begin(); // type inferred
All containers support a O(1) .size() that reports the number of elements in the container.
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.size(); // = 3
map<int, int> mp;
mp[2] = 4;
mp[3] = 9;
mp.size(); // = 2
// etc.
All containers support a .empty() that reports whether they are empty or not.
vector<int> v;
v.push_back(10);
v.empty(); // = false
vector<int> v2;
v2.empty(); // true
map<int, int> mp;
mp[2] = 4;
mp.empty(); // = false
map<int, int> mp2;
mp2.empty(); // = true
// etc.
When not writing production code, instead of including all the respective header files required, just the <bits/stdc++.h> header file can be included. (Might not work on Macs.)
#include <bits/stdc++.h>
#include <vector>
// initialization
vector<int> vec;
vector<int> vec2 = {1, 2, 3, 4}; // C++11
// insertion, O(1) avg
vec.push_back(42);
vec.push_back(7);
// access, O(1)
vec[0]; // = 42
// iteration
for (int i = 0; i < vec.size(); ++i) {
vec[i]; // = 42, 7
}
// C++11 style iteration
for (int x: vec) {
x; // = 42, 7
}
Pairs are containers with two elements.
#include <utility>
pair<int, int> p(5, 10);
p.first; // 5
p.second; // 10
p.first = 10;
p.first; // 10
// another way to initialize in C++11
auto p2 = make_pair(5, 10); // types are inferred
C++11 has two kinds of maps: map (logarithmic time operations)and unordered_map (average constant time operations).
Note: unordered_maps cannot have keys that can't be hashed. For example, a pair<int, int> as the key will not work. They can still be used in normal maps, though.
#include <map>
// initialization
// O(log n) insert, access, delete
map<int, int> mp;
// O(1) insert, access, delete
// same signatures as normal map<>
unordered_map<int, int> omp;
// map<> keys are sorted in ascending order
// you can choose descending order:
map<int, int, std::greater<int> > mp2;
// #include <functional> for std::greater
// default is std::less<int>
// insertion, O(log n)
mp[2] = 4;
mp[3] = 9;
// access, O(log n)
mp[2]; // = 4
// check for existence, O(log n)
mp.find(2) != mp.end(); // true
mp.find(234) != mp.end(); // false
mp.count(2); // = 1
mp.count(234); // = 0
// deletion, O(log n)
mp.erase(2); // removes {2: 4}
// iteration
for (auto it = mp.begin(); it != mp.end(); ++it) {
// iterator is a pair of (key, value)
it->first; // key
it->second; // value
}
// C++11 style iteration
for (auto kv: mp) {
// to avoid making copies, use:
// (auto &kv: mp)
kv.first; // key
kv.second; // value
}
C++11 has two kinds of sets: set (logarithmic time operations) and unordered_set (average constant time operations).
#include <set>
// O(log n) insert, access, delete
set<int> st;
// O(1) insert, access, delete
unordered_set<int> ost;
// insertion, O(log n)
st.insert(42);
st.insert(7);
// check existence, O(log n)
st.find(42) != st.end(); // true
st.find(234) != st.end(); // false
st.count(42); // = 1
st.count(234); // = 0
// iteration
for (auto it = st.begin(); it != st.end(); ++it) {
*it; // = 7, 42
}
// C++ 11 style iteration
for (int x: st) {
x; // = 7, 42
}
// deletion, O(log n)
st.erase(7); // removes 7
Stacks are LIFO (last in first out) containers.
#include <stack>
// initialization
stack<int> stk;
// insertion, O(1)
stk.push(42);
// access, O(1)
stk.top(); // = 42
// size, O(1)
stk.size(); // = 1
// deletion, O(1)
stk.pop(); // removes 42
// size
stk.size(); // = 0
A FIFO (first in first out) container.
#include <queue>
// initialization
queue<int> q;
// insertion, O(1)
q.push(42);
q.push(7);
q.push(0);
// access, O(1)
q.front(); // = 42
q.back(); // = 0
// front -> [42, 7, 0] <- back
// size
q.size(); // = 3
// deletion, O(1)
q.pop(); // removes 42
q.front(); // = 7
q.pop(); // removes 7
// size
q.size(); // = 1
A double-ended queue.
#include <deque>
deque<int> dq;
// insertion, O(1)
dq.push_back(3);
dq.push_back(4);
dq.push_front(2);
dq.push_front(1);
// front -> [1, 2, 3, 4] <- back
// access, O(1)
dq.front(); // = 1
dq.back(); // = 4
// iteration
// can also iterate and access using [] operator
for (int i = 0; i < dq.size(); ++i) {
dq[i]; // = 1, 2, 3, 4
}
// deletion, O(1)
dq.pop_front(); // removes 1
dq.pop_back(); // removes 4
Priority queues are essentially heaps.
#include <queue>
// initialization
priority_queue<int> pq; // max-heap
priority_queue<int, vector<int>, greater<int> > min_pq; // min-heap
// insertion, O(log n)
pq.push(7);
pq.push(42);
pq.push(3);
// access, O(1)
pq.top(); // = 42, because max-heap
// delete, O(log n)
pq.pop(); // removes 42
pq.top(); // = 7
#include <algorithm>
// ^ for sort
#include <functional>
// ^ for greater<>
vector<int> vec;
// ascending order, O(n log n)
sort(vec.begin(), vec.end());
// descending order, O(n log n)
sort(vec.begin(), vec.end(), std::greater<int>());
Binary search assumes that the vector you give it is sorted. If not sorted, you will need to sort it first.
#include <vector>
#include <algorithm>
vector<int> v = {1, 2, 4, 4, 6, 10}; // C++11 style
// O(n log n) for vectors, arrays
binary_search(v.begin(), v.end(), 4); // = true
binary_search(v.begin(), v.end(), 42); // = false
The following functions take logarithmic time on arrays, vectors, etc. but NOT on maps, sets, etc.
Lower bound returns an iterator pointing to the first element which is not less than the given element.
#include <vector>
#include <algorithm>
vector<int> v = {1, 2, 2, 5};
// returns iterator to first 2
auto it = lower_bound(v.begin(), v.end(), 2);
it - v.begin(); // = 1, since index is 1
// returns iterator to 5
auto it2 = lower_bound(v.begin(), v.end(), 3);
it2 - v.begin(); // = 3
// returns end iterator if nothing found
lower_bound(v.begin(), v.end(), 100) == v.end(); // true
Upper bound returns an iterator pointing to the first element which is greater than the given element.
#include <vector>
#include <algorithm>
vector<int> v = {1, 2, 2, 5};
// returns iterator to 5
auto it = upper_bound(v.begin(), v.end(), 2);
it - v.begin(); // = 3, since index is 3
// also returns iterator to 5
auto it2 = upper_bound(v.begin(), v.end(), 3);
it2 - v.begin(); // = 3
// returns end iterator if nothing found
upper_bound(v.begin(), v.end(), 100) == v.end(); // true
#include <string>
// initialization
string s;
// equivalent to string s = "";
// concatenation
string s2 = "wor" + "ld";
// appending (many versions available)
s += 'H'; // char
s += "ello"; // C-string
s += s2; // C++ string
// s = "Helloworld"
// inserting at a position (many versions available)
s.insert(5, "@@");
// s = "Hello@@world"
// erasing (many versions available)
s.erase(5, 2); // delete 2 chars from pos 5
// s = "Helloworld"
// substring
string part = s.substr(1, 4); // from pos 1, 4 chars
// part = "ello"