STL - Sequence Containers and Adaptors

Tags:  cppstl

Sequence Containers

Common member functions in sequential containers:

The emplace member functions (like emplace_back, emplace_front, emplace_front, emplace etc.) perform insertions slightly faster than regular push or insert functions as they construct the new element in-place (instead of constructing the element and then copying it to that place). These are particularly useful for bulky composite types where copying is expensive. They take single list of variadic arguments required for that composite object

Adaptors for Sequence Containers

They provide a wrapper interface for sequential containers. These are:


Vectors

For vectors, refer here


Singly Linked-List

Element Access: .front() to access first element in the list

Iterators: .before_begin()

The list goes in only one direction i.e. forward. So, we can only do itr++ , but NOT itr-- (where itr is an iterator pointing to some element in the list)

Capacity: Note that .size() function is NOT provided

Modifiers:

forward_list Demo
forward_list
void printList (forward_list<int> &ll) {
if (ll.empty()) {
cout << "List is empty";
} else {
for (auto &num : ll) cout << num << " -> ";
}
cout << endl;
}
int main () {
forward_list<int> ll{7, 1, 3, 5};
printList(ll); // 7 -> 1 -> 3 -> 5 ->
cout << "First element: " << ll.front() << endl; // First element: 7
ll.push_front(10), ll.push_front(20);
printList(ll); // 20 -> 10 -> 7 -> 1 -> 3 -> 5 ->
ll.emplace_front(11), ll.emplace_front(22);
printList(ll); // 22 -> 11 -> 20 -> 10 -> 7 -> 1 -> 3 -> 5 ->
ll.pop_front();
printList(ll); // 11 -> 20 -> 10 -> 7 -> 1 -> 3 -> 5 ->
// same as ll.push_front(420)
ll.insert_after(ll.before_begin(), 420);
printList(ll); // 420 -> 11 -> 20 -> 10 -> 7 -> 1 -> 3 -> 5 ->
ll.insert_after(ll.begin(), 123);
printList(ll); // 420 -> 123 -> 11 -> 20 -> 10 -> 7 -> 1 -> 3 -> 5 ->
// Inserting at end of list: O(N) time
// Step 1: Finding location of last element
auto itr = ll.before_begin(); // Handles any empty list case
while (next(itr) != ll.end()) {
itr++;
}
cout << "Last element: " << *itr << endl; // Last element: 5
// Step 2: Insert after this last element
ll.insert_after(itr, 99);
printList(ll); // 420 -> 123 -> 11 -> 20 -> 10 -> 7 -> 1 -> 3 -> 5 -> 99 ->
// same as ll.pop_front()
ll.erase_after(ll.before_begin());
printList(ll); // 123 -> 11 -> 20 -> 10 -> 7 -> 1 -> 3 -> 5 -> 99 ->
ll.erase_after(ll.begin());
printList(ll); // 123 -> 20 -> 10 -> 7 -> 1 -> 3 -> 5 -> 99 ->
// Deleting from end of list: O(N) time
// Step 1: Find location of second-last element
itr = ll.before_begin();
// Check next element exists before checking next-of-next
while (next(itr) != ll.end() && next(next(itr)) != ll.end()) {
itr++;
}
cout << "Second-last element: " << *itr << endl; // Second-last element: 5
// Step 2: Delete the element after second-last element
ll.erase_after(itr);
printList(ll); // 123 -> 20 -> 10 -> 7 -> 1 -> 3 -> 5 ->
// insert_after(pos, count, val)
ll.insert_after(ll.before_begin(), 3, 8);
printList(ll); // 8 -> 8 -> 8 -> 123 -> 20 -> 10 -> 7 -> 1 -> 3 -> 5 ->
vector<int> v1{9, 6, 4};
ll.insert_after(ll.before_begin(), v1.begin(), v1.end()); // insert(pos, start, end)
printList(ll); // 9 -> 6 -> 4 -> 8 -> 8 -> 8 -> 123 -> 20 -> 10 -> 7 -> 1 -> 3 -> 5 ->
ll.clear();
printList(ll); // List is empty
ll.emplace_front(101);
ll.emplace_after(ll.begin(), 512);
printList(ll); // 101 -> 512 ->
return 0;
}

Doubly-Linked List

Element Access:

Iterators: .begin() , .end() , .rbegin(), .rend()

The list goes in both directions. So, we can do itr++ as well as itr-- (where itr is an iterator pointing to some element in the list)

Capacity: .size() function is available (wasn’t available in forward_list)

Modifiers:

list Demo
list
void printList (list<int> &dl) {
if (dl.empty()) {
cout << "List is empty";
} else {
cout << "== ";
for (auto &num : dl) cout << num << " == ";
}
cout << endl;
}
int main () {
list<int> dl{7, 1, 4, 3, 5};
printList(dl); // == 7 == 1 == 4 == 3 == 5 ==
cout << "Size: " << dl.size() << endl; // Size: 5
cout << "First element: " << dl.front() << endl; // First element: 7
cout << "Last element: " << dl.back() << endl; // Last element: 5
cout << "Reverse: ";
// Reverse traversal:
for (auto itr = dl.rbegin(); itr != dl.rend(); itr++) {
cout << *itr << ", ";
}
cout << endl; // Reverse: 5, 3, 4, 1, 7,
dl.push_front(10);
dl.emplace_front(20);
printList(dl); // == 20 == 10 == 7 == 1 == 4 == 3 == 5 ==
dl.push_back(15);
dl.emplace_back(25);
printList(dl); // == 20 == 10 == 7 == 1 == 4 == 3 == 5 == 15 == 25 ==
dl.pop_front();
printList(dl); // == 10 == 7 == 1 == 4 == 3 == 5 == 15 == 25 =
dl.pop_back();
printList(dl); // == 10 == 7 == 1 == 4 == 3 == 5 == 15 ==
auto thirdPosition = next(next(dl.begin()));
dl.insert(thirdPosition, 24);
printList(dl); // == 10 == 7 == 24 == 1 == 4 == 3 == 5 == 15 ==
auto thirdLastPosition = prev(prev(dl.end()));
dl.insert(thirdLastPosition, 77);
printList(dl); // == 10 == 7 == 24 == 1 == 4 == 3 == 77 == 5 == 15 ==
// insert(pos,count,val)
dl.insert(dl.begin(), 3, 2);
printList(dl); // == 2 == 2 == 2 == 10 == 7 == 24 == 1 == 4 == 3 == 77 == 5 == 15 ==
vector<int> v1{1, 2, 4};
dl.insert(dl.begin(), v1.begin(), v1.end()); // insert(pos,start,end)
printList(dl);
// == 1 == 2 == 4 == 2 == 2 == 2 == 10 == 7 == 24 == 1 == 4 == 3 == 77 == 5 == 15 ==
dl.erase(dl.begin()); // same as dl.pop_front();
printList(dl);
// == 2 == 4 == 2 == 2 == 2 == 10 == 7 == 24 == 1 == 4 == 3 == 77 == 5 == 15 ==
dl.clear();
printList(dl); // List is empty
return 0;
}

Double-ended Queue

How is deque different from vector or list :

Element Access:

Iterators: .begin() , .end() , .rbegin(), .rend()

Capacity: .size() available. Also, .shrink_to_fit() to free-up unused space

Modifiers:

deque Demo
deque
void printDQ (deque<int> &dq) {
if (dq.empty()) {
cout << "DQ is empty";
} else {
for (auto &num : dq) cout << num << ", ";
}
cout << endl;
}
int main () {
deque<int> dq{7, 1, 4, 3, 5};
printDQ(dq); // 7, 1, 4, 3, 5,
cout << "Size: " << dq.size() << endl; // Size: 5
cout << "dq.at(2) = " << dq.at(2) << endl; // dq.at(2) = 4
cout << "dq[3] = " << dq[3] << endl; // dq[3] = 3
cout << "First element: " << dq.front() << endl; // First element: 7
cout << "Last element: " << dq.back() << endl; // Last element: 5
cout << "Reverse: ";
for (auto itr = dq.rbegin(); itr != dq.rend(); itr++) {
cout << *itr << ", ";
}
cout << endl; // Reverse: 5, 3, 4, 1, 7,
dq.push_front(10);
dq.emplace_front(20);
printDQ(dq); // 20, 10, 7, 1, 4, 3, 5,
dq.push_back(15);
dq.emplace_back(25);
printDQ(dq); // 20, 10, 7, 1, 4, 3, 5, 15, 25,
dq.pop_front();
printDQ(dq); // 10, 7, 1, 4, 3, 5, 15, 25,
dq.pop_back();
printDQ(dq); // 10, 7, 1, 4, 3, 5, 15,
auto thirdPosition = next(next(dq.begin()));
dq.insert(thirdPosition, 24);
printDQ(dq); // 10, 7, 24, 1, 4, 3, 5, 15,
auto thirdLastPosition = prev(prev(dq.end()));
dq.insert(thirdLastPosition, 77);
printDQ(dq); // 10, 7, 24, 1, 4, 3, 77, 5, 15,
// insert(pos,count,val)
dq.insert(dq.begin(), 3, 2);
printDQ(dq); // 2, 2, 2, 10, 7, 24, 1, 4, 3, 77, 5, 15,
vector<int> v1{1, 2, 4};
// insert(pos,start,end)
dq.insert(dq.begin(), v1.begin(), v1.end());
printDQ(dq); // 1, 2, 4, 2, 2, 2, 10, 7, 24, 1, 4, 3, 77, 5, 15,
// same as dq.pop_front();
dq.erase(dq.begin());
printDQ(dq); // 2, 4, 2, 2, 2, 10, 7, 24, 1, 4, 3, 77, 5, 15,
dq.clear();
printDQ(dq); // DQ is empty
return 0;
}

Stack

Element Access: .top() returns reference to first i.e. top-most element

Capacity: .size() , .empty()

Iterators: NONE provided

Modifiers:

stack Demo
stack
void printTop (stack<int> &stk) {
if (stk.empty()) cout << "Stack is empty" << endl;
else cout << "Top element: " << stk.top() << endl;
}
int main () {
vector<int> v1{7, 1, 4, 3, 5};
stack<int> stk;
printTop(stk); // Stack is empty
cout << "Inserting elements..." << endl;
for (int num : v1) {
stk.push(num);
printTop(stk);
}
// Inserting elements...
// Top element: 7
// Top element: 1
// Top element: 4
// Top element: 3
// Top element: 5
cout << "Size: " << stk.size() << endl; // Size: 5
cout << "Removing elements..." << endl;
while (!stk.empty()) {
printTop(stk);
stk.pop();
}
// Removing elements...
// Top element: 5
// Top element: 3
// Top element: 4
// Top element: 1
// Top element: 7
return 0;
}

Queue

Element Access:

Capacity: .size() , .empty()

Iterators: NONE provided

Modifiers:

queue Demo
queue
void printFrontAndBack (queue<int> &q) {
if (q.empty()) cout << "Queue is empty" << endl;
else cout << "Front: " << q.front() << ", Back: " << q.back() << endl;
}
int main () {
vector<int> v1{7, 1, 4, 3, 5};
queue<int> q;
printFrontAndBack(q); // Queue is empty
cout << "Inserting elements..." << endl;
for (int num : v1) {
q.push(num);
printFrontAndBack(q);
}
// Inserting elements...
// Front: 7, Back: 7
// Front: 7, Back: 1
// Front: 7, Back: 4
// Front: 7, Back: 3
// Front: 7, Back: 5
cout << "Size: " << q.size() << endl; // Size: 5
cout << "Removing elements..." << endl;
while (!q.empty()) {
printFrontAndBack(q);
q.pop();
}
// Removing elements...
// Front: 7, Back: 5
// Front: 1, Back: 5
// Front: 4, Back: 5
// Front: 3, Back: 5
// Front: 5, Back: 5
return 0;
}

Heap

Declaration:

Element access: .top() returns reference to the highest priority element (stored topmost at the root of Heap tree)

Capacity: .size()

Iterators: NONE provided

Modifiers:

After each insertion/deletion, to maintain the sorted Heap property, the elements are re-organized internally by the adaptor itself.

priority_queue Demo
priority_queue
// Max-Heap and Min-Heap templates
template <typename T>
using max_heap = priority_queue<T>;
template <typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <typename Type, typename Container, typename Comparator>
void printElementAtTop (priority_queue<Type, Container, Comparator>& pq) {
if (pq.empty()) cout << "Heap is empty" << endl;
else cout << "Top of Heap: " << pq.top() << endl;
}
int main () {
vector<int> v1{7, 1, 4, 3, 5};
min_heap<int> smol;
printElementAtTop(smol); // Heap is empty
cout << "Inserting elements into Min-Heap..." << endl;
for (int num : v1) {
smol.push(num);
printElementAtTop(smol);
}
// Inserting elements into Min-Heap...
// Top of Heap: 7
// Top of Heap: 1
// Top of Heap: 1
// Top of Heap: 1
// Top of Heap: 1
cout << "Size: " << smol.size() << endl; // Size: 5
cout << "Removing elements from Min-Heap..." << endl;
while (!smol.empty()) {
printElementAtTop(smol);
smol.pop();
}
// Removing elements from Min-Heap...
// Top of Heap: 1
// Top of Heap: 3
// Top of Heap: 4
// Top of Heap: 5
// Top of Heap: 7
max_heap<int> big;
printElementAtTop(big); // Heap is empty
cout << "Inserting elements into Max-Heap..." << endl;
for (int num : v1) {
big.push(num);
printElementAtTop(big);
}
// Inserting elements into Max-Heap...
// Top of Heap: 7
// Top of Heap: 7
// Top of Heap: 7
// Top of Heap: 7
// Top of Heap: 7
cout << "Size: " << big.size() << endl; // Size: 5
cout << "Removing elements from Max-Heap..." << endl;
while (!big.empty()) {
printElementAtTop(big);
big.pop();
}
// Removing elements from Max-Heap...
// Top of Heap: 7
// Top of Heap: 5
// Top of Heap: 4
// Top of Heap: 3
// Top of Heap: 1
return 0;
}

Also refer: is_heap() , make_heap(), push_heap() , pop_heap() , sort_heap()