Here is the quick note on all the data structures we discussed, all in one place.
| Data Structure | Underlying Structure | Operation | Time Complexity | Key Characteristic |
|---|---|---|---|---|
std::vector | Dynamic Array | Access by index [i] | O(1) | Fast random access. |
| Add/Remove at End | Amortized O(1) | Can be slow when resizing. | ||
| Add/Remove at Middle | O(n) | Requires shifting elements. | ||
std::unordered_map | Hash Table | Access, Insert, Delete | Average: O(1) | Extremely fast on average. Unordered. |
std::unordered_set | Worst: O(n) | Can be slow due to hash collisions. | ||
std::map | Balanced Binary Search Tree(Red-Black Tree) | Access, Insert, Delete | O(logn) | Guaranteed performance. Keys are sorted. |
std::set | Balanced Binary Search Tree(Red-Black Tree) | Access, Insert, Delete | O(logn) | Guaranteed performance. Keys are sorted. |
std::queue | Double-Ended Queue (deque) | push, pop, front | O(1) | First-In, First-Out (FIFO) access. |
std::stack | Double-Ended Queue (deque) | push, pop, top | O(1) | Last-In, First-Out (LIFO) access. |