Containers

 Containers in C++

 A Container is a data structure in C++ that stores multiple elements.

STL containers are implemented using templates → meaning you can store any data type.

 

Container Categories

C++ containers are divided into 3 main types:

---

1. Sequence Containers

Store data in a linear order.

 

Container	Features
vector	Dynamic array, fast random access
list	Doubly linked list, fast insertion/deletion
deque	Double-ended queue, fast insertion/removal at both ends
array	Static fixed-size array (C++11)
forward_list	Singly linked list (C++11)

---

 2. Associative Containers

These store data in sorted order using balanced binary search trees (Red-Black Tree).

 

Container	Stores	Features
set	unique elements	sorted, no duplicates
multiset	duplicate elements allowed	sorted
map	key–value pair, unique keys	sorted
multimap	key–value pair, duplicate keys allowed	sorted

---

 

 3. Unordered Containers (Hash-based)

These store data using hash tables → average O(1) lookup.

Container	Stores
unordered_set	unique elements
unordered_multiset	duplicates allowed
unordered_map	key–value pair, unique keys
unordered_multimap	key–value pair, duplicate keys

---

 

4. Container Adaptors

Adaptors modify the interface of existing containers.

Adaptor	Based on	Features
stack	deque or vector or list	LIFO
queue	deque or list	FIFO
priority_queue	vector (heap)	Highest priority element at top

---

---

Importance of Containers

Fast and efficient data storage
Built-in memory management
Generic programming (templates)
Reusable, reliable, optimized library code
Used in DSA, competitive programming, and projects

---

 

A. SEQUENCE CONTAINERS

---

vector

• Dynamic array
• Fast random access: O(1)
• Insertions at end: Amortized O(1)
• Insertions in middle: slow (O(n))

---

 Practical Example

#include <iostream>

#include <vector>

using namespace std;

 

int main() {

    vector<int> v = {10, 20, 30};

 

    v.push_back(40);      // add element at end

    v.pop_back();         // remove last element

    v.insert(v.begin()+1, 50); // insert at index 1

 

    cout << "Vector elements: ";

    for(int x : v) cout << x << " ";

}

---

list (Doubly Linked List)

• Insertion & deletion anywhere: O(1)
• No direct index access (no list[i])

---

Practical Example

#include <list>

#include <iostream>

using namespace std;

 

int main() {

    list<int> l = {1,2,3};

    l.push_front(0);

    l.push_back(4);

 

    l.remove(2); // delete value

 

    for(int x : l) cout << x << " ";

}

---

deque (Double-Ended Queue)

• Fast insertion & deletion at BOTH ends
• Supports indexing (unlike list)

---

Example

#include <deque>

using namespace std;

 

int main() {

    deque<int> d = {10,20};

 

    d.push_front(5);

    d.push_back(30);

 

    cout << d[0]; // index access

}

---

array (Static Array) – C++11

#include <array>

array<int, 4> arr = {1,2,3,4};

---

forward_list (Singly Linked List) – C++11

Lighter & faster than list (only next pointer).

forward_list<int> fl = {10,20,30};

fl.push_front(5);

---

 

B. ASSOCIATIVE CONTAINERS (RB Tree)

---

set

• Stores unique elements
• Auto-sorted
• Fast search: O(log n)

 Example

#include <set>

set<int> s = {5,1,3,2};

 

s.insert(4); // 1 2 3 4 5

 

for(int x : s) cout << x << " ";

---

map (Key-Value Pair)

Example

#include <map>

map<int,string> m;

 

m[1] = "Apple";

m[2] = "Banana";

 

for(auto p : m)

    cout << p.first << " -> " << p.second << endl;

---

multiset (Duplicates allowed)

multiset<int> ms = {1,1,2,2,3};

---

multimap (Duplicate keys allowed)

multimap<int,string> mm;

mm.insert({1,"A"});

mm.insert({1,"B"});

---

---

 C. UNORDERED (Hash Table)

---

unordered_set

unordered_set<int> us = {5,2,1,3};

---

unordered_map

unordered_map<string,int> marks;

marks["Amit"] = 88;

marks["Rahul"] = 92;

---

Features

• Avg. O(1) lookup
• No sorting → output in random order

---

---

D. CONTAINER ADAPTORS

---

stack → LIFO

stack<int> st;

 

st.push(10);

st.push(20);

cout << st.top(); // 20

st.pop();

---

queue → FIFO

queue<int> q;

 

q.push(1);

q.push(2);

cout << q.front(); // 1

q.pop();

---

priority_queue → Max Heap

priority_queue<int> pq;

pq.push(10);

pq.push(5);

pq.push(20);

 

cout << pq.top(); // 20 (highest)

---

---

Container Comparison

Container	Order	Duplicate	Access	Use Case
vector	indexed	yes	fast	dynamic arrays
list	linear	yes	slow	fast insertion/deletion
deque	indexed	yes	fast	queue + array
set	sorted	no	log n	unique sorted data
map	sorted	keys unique	log n	dictionary
unordered_set	random	no	O(1)	fast lookup
unordered_map	random	keys unique	O(1)	hashing
stack	LIFO	yes	top only	undo operations
queue	FIFO	yes	front/back	scheduling
priority_queue	highest first	yes	top only	ranking

---

Container usability

Use vector

• When frequent random access
• Insertions mostly at the end

Use list

• Frequent insertion/deletion in the middle

Use set

• Need unique sorted elements

Use map

• Key-value lookup in sorted order

Use unordered_map

• Fastest key-value access

Use stack/queue

• LIFO/FIFO behavior required

---