Skip to content

C++ STL Full Tutorial: Pairs, Vectors, Sets, Maps & More for DSA

Convert to note

Understanding the C++ Skeleton

  • #include <bits/stdc++.h>: Includes all standard libraries (like math.h, string.h) in one go, saving time.
  • using namespace std: Allows direct use of cout, cin instead of writing std::cout, std::cin each time.
  • Functions:
    • void: Performs an action (e.g., printing) but returns nothing.
    • return type (int, double, etc.): Returns a value. Example: int sum(int a, int b) { return a + b; }

Introduction to Pairs

  • Definition: pair<int, int> p = {1, 3}; stores two values together.
  • Access: p.first returns 1, p.second returns 3.
  • Nesting: Store 3+ values by nesting: pair<int, pair<int, int>> p = {1, {3, 4}};
    • Access: p.first → 1, p.second.first → 3, p.second.second → 4.
  • Pair Array: Can store pairs in an array: pair<int, int> arr[] = {{1, 2}, {3, 4}, {5, 6}}; Access arr[1].second gives 4.

Containers (The Core of STL)

Vectors

A dynamic array that can resize automatically.

Declaration & Initialization

vector<int> v;                    // Empty vector
v.push_back(1);                   // Adds 1 at the end
v.emplace_back(2);                // Faster alternative to push_back

vector<int> v(5, 100);            // 5 elements, each 100
vector<int> v(5);                  // 5 elements with garbage/0
vector<int> v1(v);                 // Copy v into v1
  • Vector of Pairs: vector<pair<int, int>> vec; Use vec.push_back({1, 2}); or vec.emplace_back(1, 2); (auto-wraps as pair)

Accessing Elements

  • Index: v[0], v[3] (like an array).
  • Iterator: Points to memory addresses. 
    vector<int>::iterator it = v.begin();  // Points to first element
cout << *(it);                         // Prints value at that address
it++;                                  // Moves to next element
it = it + 2;                           // Jumps 2 positions
    • v.end() → points right after the last element.
    • v.rend() and v.rbegin() → reverse iterators (rarely used).
  • Shortcut: v.back() → last element.

Printing a Vector

  • Traditional loop: for(int i = 0; i < v.size(); i++) cout << v[i] << " ";
  • Using iterators: for(auto it = v.begin(); it != v.end(); it++) cout << *(it) << " ";
  • For-each loop: for(auto it : v) cout << it << " ";

Deletion (erase)

vector<int> v = {10, 20, 12, 23, 35};
v.erase(v.begin() + 1);            // Removes 20 → {10, 12, 23, 35}

// Erase range: [start, end) – end is NOT included
v.erase(v.begin() + 2, v.begin() + 4);  // Removes 12, 23 → {10, 20, 35}

Insertion (insert)

vector<int> v(2, 100);              // {100, 100}
v.insert(v.begin(), 300);           // {300, 100, 100}
v.insert(v.begin() + 1, 2, 10);    // {300, 10, 10, 100, 100}

// Insert another vector:
vector<int> copy(2, 50);            // {50, 50}
v.insert(v.begin(), copy.begin(), copy.end()); // {50, 50, 300, 10, 10, 100, 100}

Other Useful Functions

  • v.size() → number of elements.
  • v.pop_back() → deletes last element.
  • v.swap(v2) → swaps entire vectors.
  • v.clear() → empties the vector.
  • v.empty() → returns true if empty.

Lists

A dynamic container with front operations (doubly linked list internally).

  • Declaration: list<int> ls;
  • Key difference: ls.push_front(5); adds to beginning cheaply (vectors require costly insert).
  • Other functions (begin, end, size, clear, empty) work exactly like vectors.

Deque

Similar to lists and vectors, supports push_front, push_back, pop_front, pop_back, front, back, etc.

Stacks (LIFO – Last In, First Out)

stack<int> st;
st.push(1);    st.push(2);    st.push(3);
st.emplace(5);                 // Alternative to push

cout << st.top();               // Prints 5 (last element)
st.pop();                       // Removes 5
cout << st.top();               // Now prints 3

cout << st.size();              // 3
cout << st.empty();             // 0 (false)
  • Only functions: push, pop, top. No indexing.
  • Time complexity: All operations are O(1).

Queues (FIFO – First In, First Out)

queue<int> q;
q.push(1);    q.push(2);    q.push(4);

q.back() += 5;                   // Adds 5 to 4 → now 9
cout << q.back();                // Prints 9
cout << q.front();               // Prints 1
q.pop();                         // Removes 1
cout << q.front();               // Now prints 2
  • Time complexity: All operations O(1).

Priority Queue (Max-Heap by Default)

  • Default: Largest element at top.
priority_queue<int> pq;
pq.push(5);    pq.push(2);    pq.push(8);    pq.push(10);
cout << pq.top();                // 10
pq.pop();                        // Removes 10
cout << pq.top();                // 8
  • Min-Heap: Store smallest at top. 
    priority_queue<int, vector<int>, greater<int>> pq;
pq.push(5);    pq.push(2);    pq.push(8);    pq.push(10);
cout << pq.top();                // 2
  • Time complexity: push and pop O(log n), top O(1).

Sets (Sorted + Unique)

Stores elements in sorted order, no duplicates.

set<int> s;
s.insert(1);    s.emplace(2);    s.insert(2);    // 2 not stored again
s.insert(4);    s.insert(3);                     // Now {1, 2, 3, 4}

Key Functions

  • s.find(3) → returns iterator to 3. If not found, returns s.end().
  • s.erase(5) → erases element 5 (maintains sorted order).
  • s.count(1) → returns 1 (since unique), returns 0 if not present.
  • s.erase(iterator) → erases by address.
  • s.erase(start_iterator, end_iterator) → erases a range ([start, end)).
  • Time complexity: All operations O(log n).
  • lower_bound / upper_bound: See linked video explanation.

Multiset (Sorted, Allows Duplicates)

multiset<int> ms;
ms.insert(1);    ms.insert(1);    ms.insert(1);   // Stores all 3 ones

ms.erase(1);                              // Erases ALL occurrences

// Erase only one occurrence:
ms.erase(ms.find(1));                     // Erases only one 1
ms.erase(ms.find(1), ms.find(1) + 2);     // Erases two 1s
  • ms.count(1) returns the number of occurrences (3 in first example).

Unordered Set (Unique, Not Sorted)

  • Properties: Unique values, randomized order.
  • Time complexity: Average O(1), worst-case O(n).
  • Note: lower_bound and upper_bound functions do NOT work.

Maps (Key-Value Pairs, Unique + Sorted Keys)

Stores unique keys in sorted order, mapped to a value.

  • Declaration: map<key_type, value_type> m;
  • Examples: 
    map<int, int> mpp;
mpp[1] = 2;           // Stores key 1 with value 2
mpp.insert({2, 4});   // Key 2, value 4
mpp.emplace(3, 1);    // Key 3, value 1

map<pair<int, int>, int> mpp2;  // Key is a pair
mpp2[{2, 3}] = 10;     // Stores pair(2,3) mapping to 10
  • Keys must be unique; values can repeat.
  • Internally stored as sorted key-value pairs.

For a more comprehensive reference, see the Comprehensive Overview of Data Structures and Algorithms Using Python or the Comprehensive Guide to Core Data Structures and Algorithms. To solidify your understanding, check the Comprehensive C++ Basics and Interview Prep with Striver's Resources. For deeper insight into specific techniques, explore Understanding Data Structures Through C Language: A Comprehensive Guide and Mastering Two Pointer & Sliding Window Techniques in DSA Interviews.

Keep this summary

Save it to LunaNotes and it becomes a real note in your library — editable, searchable, and ready to turn into flashcards or a diagram. Free to start.

Save to LunaNotes

Or summarise for another video.

32K+ people have turned 65K+ videos into notes

“Very useful tool. I'm using it for the last couple weeks and I'm loving it so far. Makes learning on YouTube a great experience.”
Bhai Chrome Web Store review

This summary and transcript were automatically generated using AI with the Free YouTube transcript summary tool by LunaNotes.

Related summaries

Comprehensive Guide to Core Data Structures and Algorithms

Comprehensive Guide to Core Data Structures and Algorithms

Explore foundational concepts in data structures, computational complexity, and advanced algorithms. This guide covers arrays, linked lists, stacks, queues, priority queues, union-find, trees, hash tables, Fenwick trees, suffix arrays, balanced BSTs, and indexed priority queues, with insights on implementation and performance optimization.

MTH104 Finite Sets, Classes, & Power Sets Explained

MTH104 Finite Sets, Classes, & Power Sets Explained

Learn the definition of finite sets and key theorems for counting elements in unions, intersections, and complements. This lecture also covers classes of sets, subclasses, and power sets with clear examples for MTH104 students.

Comprehensive Guide to Data Structures: Arrays to Graphs Explained

Comprehensive Guide to Data Structures: Arrays to Graphs Explained

Explore fundamental concepts of data structures from arrays, lists, stacks, queues to trees and graphs. Learn definitions, real-world examples, implementation strategies, and algorithmic insights for efficient data organization and manipulation.

Permutations & Combinations S1 Intro | Factorials, Restrictions, Arrangements

Permutations & Combinations S1 Intro | Factorials, Restrictions, Arrangements

This introductory video launches a comprehensive series on permutations and combinations for A-Level Math S1. It clearly explains the core difference between permutations (order matters) and combinations (order doesn't), then covers fundamental concepts like factorial notation, arranging objects with repeats, and solving problems with restrictions (items together/apart, fixed positions) using worked examples.

8 Essential LeetCode Patterns to Solve Coding Problems Efficiently

8 Essential LeetCode Patterns to Solve Coding Problems Efficiently

After solving over 500 LeetCode problems, the key insight is to focus on repeating patterns rather than individual solutions. This video outlines 8 fundamental patterns—including sliding window, subset, modified binary search, and two-pointer—that can simplify complex coding challenges and improve problem-solving speed.

Most viewed summaries

A Comprehensive Guide to Using Stable Diffusion Forge UI

A Comprehensive Guide to Using Stable Diffusion Forge UI

Explore the Stable Diffusion Forge UI, customizable settings, models, and more to enhance your image generation experience.

Kolonyalismo at Imperyalismo: Ang Kasaysayan ng Pagsakop sa Pilipinas

Kolonyalismo at Imperyalismo: Ang Kasaysayan ng Pagsakop sa Pilipinas

Tuklasin ang kasaysayan ng kolonyalismo at imperyalismo sa Pilipinas sa pamamagitan ni Ferdinand Magellan.

Mastering Inpainting with Stable Diffusion: Fix Mistakes and Enhance Your Images

Mastering Inpainting with Stable Diffusion: Fix Mistakes and Enhance Your Images

Learn to fix mistakes and enhance images with Stable Diffusion's inpainting features effectively.

Pamamaraan at Patakarang Kolonyal ng mga Espanyol sa Pilipinas

Pamamaraan at Patakarang Kolonyal ng mga Espanyol sa Pilipinas

Tuklasin ang mga pamamaraan at patakaran ng mga Espanyol sa Pilipinas, at ang epekto nito sa mga Pilipino.

How to Install and Configure Forge: A New Stable Diffusion Web UI

How to Install and Configure Forge: A New Stable Diffusion Web UI

Learn to install and configure the new Forge web UI for Stable Diffusion, with tips on models and settings.

Found this summary useful?

Take it with you. One click puts it in your own LunaNotes library.

Save to LunaNotes

Start taking better notes today with LunaNotes

Start for free