Feb 01, 2024 · 45 mins read
C++ Data Structures Handbook
A handbook of built-in data structures and their methods with examples and complexity analysis.
Umakant Vashishtha
C++ Data Structures Handbook
C++ Data Structures Handbook
This is a handbook of built-in data structures and their methods with examples and complexity analysis for quick review.
Table of Contents
- C++ Data Structures Handbook
Vector
Definition
A vector is a sequence container that encapsulates dynamic size arrays.
Declaration
vector<T> v;
// vector of size n with all elements as 0
vector<T> v(n);
// vector of size n with all elements as x
vector<T> v(n, x);
// vector initialized from an array
vector<T> v(arr, arr + n);
// vector initialized from another vector
vector<T> v(v1);
// vector initialized from another vector between two iterators
vector<T> v(v1.begin(), v1.end());
Methods
| Method | Description | Complexity |
|---|---|---|
v.size(): unsigned_int |
Returns the number of elements in the vector. | O(1) |
v.at(i) |
Returns a reference to the element at position i in the vector. | O(1) |
v.push_back(x) |
Adds a new element at the end of the vector, after its current last element. | O(1) |
v.pop_back() |
Removes the last element in the vector, effectively reducing the container size by one. | O(1) |
v.insert(it, x) |
Inserts a new element before the element at the specified position in the vector. | O(n) |
v.back() |
Returns a reference to the last element in the vector. | O(1) |
v.front() |
Returns a reference to the first element in the vector. | O(1) |
v.begin() |
Returns an iterator pointing to the first element in the vector. | O(1) |
v.end() |
Returns an iterator pointing to the past-the-end element in the vector. | O(1) |
v.clear() |
Removes all elements from the vector. | O(n) |
v.capacity() |
Returns the number of elements that the vector has currently allocated space for. | O(1) |
v.empty() |
Returns whether the vector is empty. | O(1) |
Operations on Vector
- Iterating over a vector
for (auto it = v.begin(); it != v.end(); it++) {
cout << *it << endl;
}
for (const auto &x : v) {
cout << x << endl;
}
- Sorting a vector
sort(v.begin(), v.end()); // ascending order - less<int>() is default
sort(v.begin(), v.end(), greater<int>()); // descending order
// sort a part of vector
sort(v.begin() + 1, v.begin() + 4);
- Reverse a vector
reverse(v.begin(), v.end()); // reverse the vector
// reverse a part of vector
reverse(v.begin() + 1, v.begin() + 4);
Queue
Definition
A queue is a container adaptor that provides FIFO (first-in-first-out) data structure.
Declaration
deque<T> q;
Methods
| Method | Description | Complexity |
|---|---|---|
q.push(x) |
Adds a new element at the end of the queue, after its current last element. | O(1) |
q.pop() |
Removes the next element in the queue, effectively reducing its size by one. | O(1) |
q.front() |
Returns a reference to the next element in the queue. | O(1) |
q.back() |
Returns a reference to the last element in the queue. | O(1) |
q.empty() |
Returns whether the queue is empty. | O(1) |
q.size() |
Returns the number of elements in the queue. | O(1) |
Operations on Queue
- Iterating over a queue
while (!q.empty()) {
cout << q.front() << endl;
q.pop();
}
Stack
Definition
A stack is a container adaptor that provides LIFO (last-in-first-out) data structure.
Declaration
stack<T> s;
Methods
| Method | Description | Complexity |
|---|---|---|
s.push(x) |
Adds a new element at the top of the stack, above its current top element. | O(1) |
s.pop() |
Removes the top element in the stack, effectively reducing its size by one. | O(1) |
s.top() |
Returns a reference to the top element in the stack. | O(1) |
s.empty() |
Returns whether the stack is empty. | O(1) |
s.size() |
Returns the number of elements in the stack. | O(1) |
Operations on Stack
- Iterating over a stack
while (!s.empty()) {
cout << s.top() << endl;
s.pop();
}
Set
Definition
A set is an associative container that contains a sorted set of unique objects of type Key.
Declaration
set<T> s;
// set initialized from an array
set<T> s(arr, arr + n);
// set initialized from another set
set<T> s(s1);
// set initialized from another set between two iterators
set<T> s(s1.begin(), s1.end());
Methods
| Method | Description | Complexity |
|---|---|---|
s.insert(x) |
Inserts a new element in the set. | O(log n) |
s.erase(x) |
Removes the element x from the set. | O(log n) |
s.find(x) |
Returns an iterator pointing to the element x in the set if found, else returns an iterator pointing to the end of the set. | O(log n) |
s.lower_bound(x) |
Returns an iterator pointing to the first element in the set which is not less than x. | O(log n) |
s.upper_bound(x) |
Returns an iterator pointing to the first element in the set which is greater than x. | O(log n) |
s.empty() |
Returns whether the set is empty. | O(1) |
s.size() |
Returns the number of elements in the set. | O(1) |
Operations on Set
- Iterating over a set
for (auto it = s.begin(); it != s.end(); it++) {
cout << *it << endl;
}
for (const auto &x : s) {
cout << x << endl;
}
- Sorting: Set is always sorted in ascending order
Unordered Set
Definition
An unordered set is an associative container that contains a set of unique objects of type Key.
Declaration
unordered_set<T> s;
// unordered set initialized from an array
unordered_set<T> s(arr, arr + n);
// unordered set initialized from another unordered set
unordered_set<T> s(s1);
// unordered set initialized from another unordered set between two iterators
unordered_set<T> s(s1.begin(), s1.end());
Methods
| Method | Description | Complexity |
|---|---|---|
s.insert(x) |
Inserts a new element in the unordered set. | O(1) |
s.erase(x) |
Removes the element x from the unordered set. | O(1) |
s.find(x) |
Returns an iterator pointing to the element x in the unordered set if found, else returns an iterator pointing to the end of the unordered set. | O(1) |
s.empty() |
Returns whether the unordered set is empty. | O(1) |
s.size() |
Returns the number of elements in the unordered set. | O(1) |
Operations on Unordered Set
- Iterating over an unordered set
for (auto it = s.begin(); it != s.end(); it++) {
cout << *it << endl;
}
for (const auto &x : s) {
cout << x << endl;
}
Map
Definition
A map is an associative container that contains a sorted set of unique objects of type Key and mapped with type Value.
Declaration
map<K, V> m;
// map initialized from another map
map<K, V> m(m1);
// map initialized from another map between two iterators
map<K, V> m(m1.begin(), m1.end());
Methods
| Method | Description | Complexity |
|---|---|---|
m.insert({x, y}) |
Inserts a new element in the map. | O(log n) |
m.erase(x) |
Removes the element x from the map. | O(log n) |
m.find(x) |
Returns an iterator pointing to the element x in the map if found, else returns an iterator pointing to the end of the map. | O(log n) |
m.lower_bound(x) |
Returns an iterator pointing to the first element in the map which is not less than x. | O(log n) |
m.upper_bound(x) |
Returns an iterator pointing to the first element in the map which is greater than x. | O(log n) |
m.empty() |
Returns whether the map is empty. | O(1) |
m.size() |
Returns the number of elements in the map. | O(1) |
Operations on Map
- Iterating over a map
for (auto it = m.begin(); it != m.end(); it++) {
cout << it->first << " " << it->second << endl;
}
for (const auto &x : m) {
cout << x.first << " " << x.second << endl;
}
- Sorting: Map is always sorted in ascending order
Unordered Map
Definition
An unordered map is an associative container that contains a set of unique objects of type Key and mapped with type Value.
Declaration
unordered_map<K, V> m;
// unordered map initialized from another unordered map
unordered_map<K, V> m(m1);
// unordered map initialized from another unordered map between two iterators
unordered_map<K, V> m(m1.begin(), m1.end());
Methods
| Method | Description | Complexity |
|---|---|---|
m.insert({x, y}) |
Inserts a new element in the unordered map. | O(1) |
m.erase(x) |
Removes the element x from the unordered map. | O(1) |
m.find(x) |
Returns an iterator pointing to the element x in the unordered map if found, else returns an iterator pointing to the end of the unordered map. | O(1) |
m.empty() |
Returns whether the unordered map is empty. | O(1) |
m.size() |
Returns the number of elements in the unordered map. | O(1) |
Operations on Unordered Map
- Iterating over an unordered map
for (auto it = m.begin(); it != m.end(); it++) {
cout << it->first << " " << it->second << endl;
}
for (const auto &x : m) {
cout << x.first << " " << x.second << endl;
}
Multiset
Definition
A multiset is an associative container that contains a sorted set of objects of type Key.
Declaration
multiset<T> s;
// multiset initialized from an array
multiset<T> s(arr, arr + n);
// multiset initialized from another multiset
multiset<T> s(s1);
// multiset initialized from another multiset between two iterators
multiset<T> s(s1.begin(), s1.end());
Methods
| Method | Description | Complexity |
|---|---|---|
s.insert(x) |
Inserts a new element in the multiset. | O(log n) |
s.erase(x) |
Removes the element x from the multiset. | O(log n) |
s.find(x) |
Returns an iterator pointing to the element x in the multiset if found, else returns an iterator pointing to the end of the multiset. | O(log n) |
s.lower_bound(x) |
Returns an iterator pointing to the first element in the multiset which is not less than x. | O(log n) |
s.upper_bound(x) |
Returns an iterator pointing to the first element in the multiset which is greater than x. | O(log n) |
s.empty() |
Returns whether the multiset is empty. | O(1) |
s.size() |
Returns the number of elements in the multiset. | O(1) |
Operations on Multiset
- Iterating over a multiset
for (auto it = s.begin(); it != s.end(); it++) {
cout << *it << endl;
}
for (const auto &x : s) {
cout << x << endl;
}
- Sorting: Multiset is always sorted in ascending order
Priority Queue
Definition
A priority queue is a container adaptor that provides constant time lookup of the largest (by default) element, at the expense of logarithmic insertion and extraction.
Declaration
priority_queue<T> pq; // priority queue with descending order
// priority queue with ascending order
priority_queue<T, vector<T>, greater<T>> pq;
Methods
| Method | Description | Complexity |
|---|---|---|
pq.push(x) |
Adds a new element at the end of the priority queue, after its current last element. | O(log n) |
pq.pop() |
Removes the next element in the priority queue, effectively reducing its size by one. | O(log n) |
pq.top() |
Returns a reference to the top element in the priority queue. | O(1) |
pq.empty() |
Returns whether the priority queue is empty. | O(1) |
pq.size() |
Returns the number of elements in the priority queue. | O(1) |
Operations on Priority Queue
- Iterating over a priority queue
while (!pq.empty()) {
cout << pq.top() << endl;
pq.pop();
}
Deque
Definition
A deque is a sequence container that encapsulates dynamic size arrays.
Declaration
deque<T> dq;
// deque of size n with all elements as 0
deque<T> dq(n);
// deque of size n with all elements as x
deque<T> dq(n, x);
// deque initialized from an array
deque<T> dq(arr, arr + n);
// deque initialized from another deque
deque<T> dq(dq1);
// deque initialized from another deque between two iterators
deque<T> dq(dq1.begin(), dq1.end());
Methods
| Method | Description | Complexity |
|---|---|---|
dq.size(): unsigned_int |
Returns the number of elements in the deque. | O(1) |
dq.at(i) |
Returns a reference to the element at position i in the deque. | O(1) |
dq.push_back(x) |
Adds a new element at the end of the deque, after its current last element. | O(1) |
dq.pop_back() |
Removes the last element in the deque, effectively reducing the container size by one. | O(1) |
dq.push_front(x) |
Adds a new element at the beginning of the deque, before its current first element. | O(1) |
dq.pop_front() |
Removes the first element in the deque, effectively reducing the container size by one. | O(1) |
dq.back() |
Returns a reference to the last element in the deque. | O(1) |
dq.front() |
Returns a reference to the first element in the deque. | O(1) |
dq.begin() |
Returns an iterator pointing to the first element in the deque. | O(1) |
dq.end() |
Returns an iterator pointing to the past-the-end element in the deque. | O(1) |
dq.clear() |
Removes all elements from the deque. | O(n) |
dq.empty() |
Returns whether the deque is empty. | O(1) |
Operations on Deque
- Iterating over a deque
for (auto it = dq.begin(); it != dq.end(); it++) {
cout << *it << endl;
}
for (const auto &x : dq) {
cout << x << endl;
}
- Sorting a deque
sort(dq.begin(), dq.end()); // ascending order - less<int>() is default
sort(dq.begin(), dq.end(), greater<int>()); // descending order
// sort a part of deque
sort(dq.begin() + 1, dq.begin() + 4);
- Reverse a deque
reverse(dq.begin(), dq.end()); // reverse the deque
// reverse a part of deque
reverse(dq.begin() + 1, dq.begin() + 4);
