C++ Standard Library QuickRef
This quick reference assumes that you already know C++ and just want a refresher of some common techniques, particularly for tech interviews.
Contents
- Containers
- Algorithms
- Strings
Common Stuff
C++11
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
auto
Since C++11, types can be inferred during assignment by 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
.size()
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.
.empty()
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.
bits/stdc++.h
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>
Vector
#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
}
Pair
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
Map
C++11 has two kinds of maps: map (logarithmic time operations) and unordered_map (average constant time operations).
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
}
Set
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
Stack
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
Queue
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
Deque
A double-ended queue (generally pronounced “deck”).
#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 Queue
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
Sort
#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
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
lower and upper bound
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
Strings
#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"