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(logn)O(\log n)
- Pop: O(logn)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(logn)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(logn)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(logn)O(\log n) | O(1)O(1) | By Priority |
| Set | std::set, std::unordered_set | O(logn)O(\log n) | O(logn)O(\log n) | Sorted |
| Map | std::map, std::unordered_map | O(logn)O(\log n) | O(logn)O(\log n) | By Key |