C++ Day 39

STL Containers (Deep Understanding & Real Usage)

Till now, you already know arrays, vectors, loops, and STL algorithms.
Today, we go one step deeper and understand STL containers, which are the backbone of modern C++ programming.

In real projects and competitive coding, choice of container matters a lot.

---

1. What are STL Containers?

STL containers are data structures provided by C++ to store data efficiently.

They handle:

• memory management

• resizing

• element access

• performance optimization

You focus on logic, not memory handling.

---

2. Categories of STL Containers

STL containers are mainly divided into:

1. Sequence Containers

2. Associative Containers

3. Unordered Containers

4. Container Adapters

---

3. Sequence Containers

These store data in sequence.

3.1 Vector

Most used container in C++.

vector<int> v;

Key Features:

• Dynamic size

• Contiguous memory

• Fast random access

• Slower insertion in middle

Example:

v.push_back(10);
v.push_back(20);
v.push_back(30);

When to Use Vector:

• When index access is needed

• When size changes frequently

• Competitive programming

---

3.2 Deque (Double Ended Queue)

deque<int> dq;

Features:

• Fast insertion at front and back

• Random access supported

• Slightly slower than vector

dq.push_front(5);
dq.push_back(10);

---

3.3 List (Doubly Linked List)

list<int> lst;

Features:

• Non-contiguous memory

• Fast insertion and deletion anywhere

• No random access

lst.push_back(1);
lst.push_front(0);

Use when frequent insert/delete in middle is required.

---

4. Associative Containers (Ordered)

These store data in sorted order.

4.1 Set

set<int> s;

Properties:

• Stores unique elements

• Sorted automatically

• Implemented using Red-Black Tree

s.insert(5);
s.insert(1);
s.insert(5); // ignored

---

4.2 Multiset

multiset<int> ms;

Allows duplicate values.

ms.insert(5);
ms.insert(5);

---

4.3 Map

Stores key-value pairs.

map<int, string> mp;

Example:

mp[1] = "Apple";
mp[2] = "Banana";

• Keys are unique

• Automatically sorted by key

---

5. Unordered Containers

These use hashing.

5.1 Unordered Set

unordered_set<int> us;

• Unique elements

• No order

• Faster than set in most cases

---

5.2 Unordered Map

unordered_map<int, int> ump;

Used heavily in frequency counting.

ump[x]++;

Average complexity is O(1).

---

6. Container Adapters

These provide restricted access.

6.1 Stack

stack<int> st;

LIFO (Last In First Out)

st.push(10);
st.pop();

---

6.2 Queue

queue<int> q;

FIFO (First In First Out)

---

6.3 Priority Queue

priority_queue<int> pq;

• Max heap by default

pq.push(5);
pq.push(10);

For min heap:

priority_queue<int, vector<int>, greater<int>> pq;

---

7. Choosing the Right Container

Requirement	Container
Fast access by index	vector
Insert/delete in middle	list
Unique sorted data	set
Key-value pair	map
Fast lookup	unordered_map
Max/Min element	priority_queue

---

8. Real-World Example

Counting frequency of numbers:

unordered_map<int, int> freq;

for(int x : v)
    freq[x]++;

Used in:

• interview problems

• data analysis

• competitive coding

---

9. Common Mistakes

• Using map instead of unordered_map unnecessarily

• Using vector when frequent middle insertion is needed

• Forgetting that set/map are sorted

• Expecting index access in list or set

---

10. Summary (Day 39)

Today you learned:

• Types of STL containers

• Differences between them

• When to use which container

• Real-world usage patterns

• Performance considerations