47. STL Sequence Containers

Definition

The STL (Standard Template Library) provides sequence containers as fundamental data structures for storing collections of elements in order. Unlike fixed-size C-style arrays, C++ sequence containers offer flexibility in data manipulation — adding, removing, and accessing elements efficiently.

The main containers in this category are vector, deque, list, forward_list, and array. Each container has unique characteristics that make it suitable for particular use cases.

Iterator Basics

Before discussing containers, it is important to understand iterators — objects that act as "pointers" for traversing container elements.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> nums = {10, 20, 30, 40, 50};

    // Using a manual iterator
    vector<int>::iterator it;
    for (it = nums.begin(); it != nums.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    // Range-based for (more modern and clean)
    for (const auto& num : nums) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Important methods on iterators:
- begin() → points to the first element
- end() → points to the position after the last element
- ++it → moves to the next element
- --it → moves to the previous element
- *it → accesses the pointed-to value

vector — Dynamic Array

vector is the most frequently used container. It is based on a dynamic array; elements are stored sequentially in contiguous memory. It supports random access with O(1) time.

Code Example

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    vector<string> name;

    // Add elements at the end
    name.push_back("Mike");
    name.push_back("John");
    name.push_back("Anna");

    // Access by index
    cout << "First name: " << name[0] << endl;
    cout << "Last name: " << name.at(name.size() - 1) << endl;

    // Remove the last element
    name.pop_back();

    // Insert at a specific position
    name.insert(name.begin() + 1, "Dana");

    // Size and capacity
    cout << "Size: " << name.size() << endl;
    cout << "Capacity: " << name.capacity() << endl;

    // Reserve capacity for optimization
    vector<int> scores;
    scores.reserve(100); // allocate for 100 elements

    for (const auto& n : name) {
        cout << n << " ";
    }
    cout << endl;

    return 0;
}

Code Explanation

• push_back() adds an element at the end of the vector, automatically adjusting capacity if needed.
• pop_back() removes the last element.
• insert() inserts an element at a specific position — this operation is slow, O(n), because elements must be shifted.
• size() returns the number of elements; capacity() returns the number of slots already allocated.
• reserve() pre-allocates memory to avoid repeated reallocation.

Everyday Use Cases

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> grade;

    // Student grade input system
    grade.push_back(85);
    grade.push_back(92);
    grade.push_back(78);
    grade.push_back(95);
    grade.push_back(88);

    // Computing the average
    double total = 0;
    for (int n : grade) {
        total += n;
    }
    cout << "Average grade: " << total / grade.size() << endl;

    // Finding the highest grade
    int max = grade[0];
    for (int n : grade) {
        if (n > max) max = n;
    }
    cout << "Highest grade: " << max << endl;

    return 0;
}

Conclusion

Vector is the default choice for most cases because of its flexibility and efficiency. Use reserve() when you already know the number of elements to optimize performance.

deque — Double-Ended Queue

deque allows adding and removing elements from both ends efficiently, unlike vector, which is only optimal at the end.

Code Example

#include <iostream>
#include <deque>
#include <string>
using namespace std;

int main() {
    deque<string> history;

    // Add from the back
    history.push_back("google.com");
    history.push_back("github.com");
    history.push_back("stackoverflow.com");

    // Add from the front
    history.push_front("localhost:3000");

    // Access elements
    cout << "First page: " << history.front() << endl;
    cout << "Last page: " << history.back() << endl;

    // Remove from the front
    history.pop_front();

    // Iterate
    for (const auto& url : history) {
        cout << url << endl;
    }

    return 0;
}

Code Explanation

• push_front() and pop_front() work efficiently, O(1), on a deque.
• front() and back() access the elements at the ends without removing them.
• Deque does not store elements in contiguous memory, so random access is slightly slower than on a vector.

Everyday Use Cases

#include <iostream>
#include <deque>
using namespace std;

int main() {
    deque<int> undoStack;

    // Simulating user actions
    undoStack.push_back(10); // typed '1'
    undoStack.push_back(20); // typed '2'
    undoStack.push_back(30); // typed '3'

    // Undo
    if (!undoStack.empty()) {
        cout << "Undo action: " << undoStack.back() << endl;
        undoStack.pop_back();
    }

    // Redo by adding to the front
    undoStack.push_front(30);

    for (int action : undoStack) {
        cout << "Action: " << action << endl;
    }

    return 0;
}

Conclusion

Deque is suitable for cases that need efficient access from both ends, such as browser history or undo/redo systems.

list — Doubly Linked List

list is a doubly linked list — each element has a pointer to the element before and after it. Insert and delete anywhere are very efficient, O(1), but it does not support random access.

Code Example

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> list;

    list.push_back(30);
    list.push_back(10);
    list.push_front(50);
    list.push_front(20);

    // Sort by default
    list.sort();

    // Remove elements with a specific value
    list.remove(30);

    // Merge two lists
    list<int> other = {40, 15, 25};
    other.sort();
    list.merge(other);

    // Reverse
    list.reverse();

    for (const auto& val : list) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}

Code Explanation

• sort() sorts the elements in ascending order (the default).
• remove(val) removes all elements with the value val.
• merge() combines two already-sorted lists.
• reverse() reverses the order of the elements.

Everyday Use Cases

#include <iostream>
#include <list>
#include <string>
using namespace std;

int main() {
    list<string> playlist;
    playlist.push_back("Lagu A");
    playlist.push_back("Lagu B");
    playlist.push_back("Lagu C");
    playlist.push_back("Lagu D");

    // Song playback system
    auto it = playlist.begin();
    cout << "Memutar: " << *it << endl;

    ++it;
    cout << "Next: " << *it << endl;

    // Insert after song B
    auto pos = playlist.begin();
    ++pos;
    playlist.insert(pos, "Lagu B (Remix)");

    for (const auto& lagu : playlist) {
        cout << " -> " << lagu;
    }
    cout << endl;

    return 0;
}

Conclusion

List is ideal for frequent insert/delete operations at random positions, such as a music playlist or a priority queue system.

forward_list — Singly Linked List

forward_list is a singly linked list — it can only be traversed forward. It is more memory-efficient than list but has more limited features.

Code Example

#include <iostream>
#include <forward_list>
using namespace std;

int main() {
    forward_list<int> flist = {10, 20, 30};

    // Insert after a specific element
    flist.insert_after(flist.begin(), 15);

    // Remove after a specific element
    flist.erase_after(flist.begin());

    // Push front (there is no push_back)
    flist.push_front(5);

    for (const auto& val : flist) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}

Code Explanation

• insert_after() and erase_after() operate at the position after an iterator.
• There is no size() — using distance() is required.
• It saves memory because each node stores only one pointer.

Everyday Use Cases

#include <iostream>
#include <forward_list>
using namespace std;

int main() {
    forward_list<string> task;
    task.push_front("Pay electricity bill");
    task.push_front("Beli groceries");
    task.push_front("Send email");

    cout << "Task list:" << endl;
    int i = 1;
    for (const auto& t : task) {
        cout << i++ << ". " << t << endl;
    }

    return 0;
}

Conclusion

Forward_list saves memory and is suitable for lists that only need forward traversal, such as a data processing pipeline.

array — Fixed-Size Array (C++11)

array is a wrapper around a C-style array that adds STL features such as iterators, size(), and .at() access.

Code Example

#include <iostream>
#include <array>
using namespace std;

int main() {
    array<int, 5> arr = {5, 3, 1, 4, 2};

    cout << "Size: " << arr.size() << endl;
    cout << "First element: " << arr.front() << endl;
    cout << "Last element: " << arr.back() << endl;

    // Access with bounds checking
    cout << "arr.at(2): " << arr.at(2) << endl;

    // Iterate
    for (const auto& val : arr) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}

Code Explanation

• The array size must be known at compile time (the second template parameter).
• .at() performs bounds checking and throws std::out_of_range if the index is invalid.
• It is stored on the stack, not the heap — access is very fast.

Everyday Use Cases

#include <iostream>
#include <array>
using namespace std;

int main() {
    array<double, 7> suhuMingguan = {30.5, 31.2, 29.8, 32.1, 30.0, 28.9, 31.5};

    double total = 0;
    for (double s : suhuMingguan) {
        total += s;
    }
    double average = total / suhuMingguan.size();

    cout << "This week's average temperature: " << average << "°C" << endl;
    cout << "Highest temperature: ";
    double max = suhuMingguan[0];
    for (double s : suhuMingguan) {
        if (s > max) max = s;
    }
    cout << max << "°C" << endl;

    return 0;
}

Conclusion

std::array is the best choice for fixed-size arrays because it is safer and has more features than a C-style array.

Container Comparison

*After finding the position with an iterator.

Summary

The choice of container depends on the requirements:
- Vector: the default for most cases
- Deque: insert/delete from both ends
- List: frequent insert/delete at random positions
- Forward_list: memory-efficient, forward traversal only
- Array: a safer replacement for C-style arrays

Understanding the characteristics of each container allows us to write more efficient, targeted C++ code.