Author: June Hong

The C++ Standard Template Library (STL) is a collection of powerful and flexible generic classes and functions designed to manage common data structures and algorithms. It provides efficient, reusable implementations of many data structures, which makes it easier to write high-performance code. Below is a detailed overview of common data structures and their corresponding STL components.

1. Arrays

Description:

• Fixed-size, sequential containers for elements of the same type.
• Used for storing data in contiguous memory.

STL Component:

• std::array (C++11)
• std::vector

Operations:

• Random access: O(1)O(1)
• Insertion/Deletion: O(n)O(n) for shifting elements.

Example:

#include <iostream>
#include <array>

int main() {
    std::array<int, 5> arr = {1, 2, 3, 4, 5};
    for (const auto& val : arr) {
        std::cout << val << " ";
    }
    return 0;
}

2. Linked List

Description:

• Sequential data structure with nodes that hold data and a pointer to the next node.

STL Component:

• std::list (Doubly Linked List)
• std::forward_list (Singly Linked List)

Operations:

• Insertion/Deletion at any position: O(1)O(1)
• Traversal: O(n)O(n)

Example:

#include <iostream>
#include <list>

int main() {
    std::list<int> lst = {10, 20, 30};
    lst.push_back(40);   // Add to the end
    lst.push_front(5);   // Add to the beginning

    for (const auto& val : lst) {
        std::cout << val << " ";
    }
    return 0;
}

3. Stack

Description:

• Last-In-First-Out (LIFO) data structure.

STL Component:

• std::stack (adaptor over std::deque)

Operations:

• Push: O(1)O(1)
• Pop: O(1)O(1)
• Top (peek): O(1)O(1)

Example:

#include <iostream>
#include <stack>

int main() {
    std::stack<int> st;
    st.push(10);
    st.push(20);
    st.push(30);

    while (!st.empty()) {
        std::cout << st.top() << " ";
        st.pop();
    }
    return 0;
}

4. Queue

Description:

• First-In-First-Out (FIFO) data structure.

STL Component:

• std::queue (adaptor over std::deque)
• std::deque (Double-Ended Queue)

Operations:

• Enqueue: O(1)O(1)
• Dequeue: O(1)O(1)
• Front/Back: O(1)O(1)

Example:

#include <iostream>
#include <queue>

int main() {
    std::queue<int> q;
    q.push(10);
    q.push(20);
    q.push(30);

    while (!q.empty()) {
        std::cout << q.front() << " ";
        q.pop();
    }
    return 0;
}

5. Priority Queue

Description:

• Specialized queue where elements are dequeued in priority order (not FIFO).
• Default is a max-heap.

STL Component:

• std::priority_queue

Operations:

• Push: O(log⁡n)O(\log n)
• Pop: O(log⁡n)O(\log n)
• Top: O(1)O(1)

Example:

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;
    pq.push(10);
    pq.push(20);
    pq.push(15);

    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }
    return 0;
}

Output:

20 15 10

6. Set

Description:

• Ordered container for unique elements.

STL Component:

• std::set
• std::unordered_set (Hash-based)

Operations:

• Insertion/Deletion/Find: O(log⁡n)O(\log n) for std::set, O(1)O(1) for std::unordered_set.

Example:

#include <iostream>
#include <set>

int main() {
    std::set<int> s;
    s.insert(10);
    s.insert(20);
    s.insert(20); // Ignored as duplicate

    for (const auto& val : s) {
        std::cout << val << " ";
    }
    return 0;
}

7. Map

Description:

• Key-value pairs with unique keys.

STL Component:

• std::map (Ordered)
• std::unordered_map (Hash-based)
• std::multimap (Allows duplicate keys)

Operations:

• Insertion/Deletion/Access: O(log⁡n)O(\log n) for std::map, O(1)O(1) for std::unordered_map.

Example:

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> m;
    m[1] = "One";
    m[2] = "Two";

    for (const auto& pair : m) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    return 0;
}

8. Graph

Description:

• A network of nodes (vertices) connected by edges.
• Can be represented using adjacency lists or matrices.

STL Component:

• std::vector<std::vector<int>> (Adjacency List)
• std::set or std::map for weighted edges.

Example: Adjacency List

#include <iostream>
#include <vector>

int main() {
    std::vector<std::vector<int>> graph(5);

    // Add edges
    graph[0].push_back(1);
    graph[1].push_back(2);
    graph[2].push_back(3);

    // Print adjacency list
    for (int i = 0; i < graph.size(); i++) {
        std::cout << i << ": ";
        for (int neighbor : graph[i]) {
            std::cout << neighbor << " ";
        }
        std::cout << std::endl;
    }
    return 0;
}

9. Hash Tables

Description:

• Containers for key-value pairs with hash-based lookups.

STL Component:

• std::unordered_map
• std::unordered_set

Operations:

• Insertion/Deletion/Access: O(1)O(1)

Example:

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> umap;
    umap["Apple"] = 10;
    umap["Banana"] = 20;

    for (const auto& pair : umap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    return 0;
}

Summary of Common Data Structures and STL

Data Structure	STL Component	Insertion	Lookup	Order
Array	std::array, std::vector	O(1)O(1)	O(1)O(1)	Sequential
Linked List	std::list, std::forward_list	O(1)O(1)	O(n)O(n)	Sequential
Stack	std::stack	O(1)O(1)	O(1)O(1)	LIFO
Queue	std::queue, std::deque	O(1)O(1)	O(1)O(1)	FIFO
Priority Queue	std::priority_queue	O(log⁡n)O(\log n)	O(1)O(1)	By Priority
Set	std::set, std::unordered_set	O(log⁡n)O(\log n)	O(log⁡n)O(\log n)	Sorted
Map	std::map, std::unordered_map	O(log⁡n)O(\log n)	O(log⁡n)O(\log n)	By Key