Cpp Programming Using Stl In Competitive Programming Complete Guide

 Last Update:2025-06-22T00:00:00     .NET School AI Teacher - SELECT ANY TEXT TO EXPLANATION.    11 mins read      Difficulty-Level: beginner

Understanding the Core Concepts of CPP Programming Using STL in Competitive Programming

CPP Programming Using STL in Competitive Programming

1. Understanding the STL:

  • Containers: These are used to store and manage collections of objects. Common containers include vector, deque, list, set, multiset, map, multimap, unordered_set, unordered_multiset, unordered_map, and unordered_multimap.
  • Algorithms: The STL provides a variety of algorithms for searching, sorting, modifying, and transforming data. Examples include sort, binary_search, lower_bound, upper_bound, count, find, min_element, max_element, transform, accumulate, merge, set_union, set_intersection, set_difference, and set_symmetric_difference.
  • Iterators: Iterators are used to traverse and manipulate the elements in a container. They come in different types—input, output, forward, bidirectional, and random access.
  • Function Objects: Also known as functors, these are objects that can be called as though they were functions. They are useful for custom comparison functions and other operations.

2. Key Containers in Competitive Programming:

  • vector: A dynamic array that allows fast access to elements by index. It supports O(1) time complexity for accessing elements and resizing (on average) for adding or removing elements from the back.

    vector<int> vec = {1, 2, 3, 4};
vec.push_back(5);          // Add element to the end
vec.insert(vec.begin() + 2, 10); // Insert 10 at index 2
vec.erase(vec.begin() + 3);  // Erase element at index 3
int size = vec.size();         // Get size of vector

  • set: A collection of unique elements sorted in ascending order. Provides O(log n) time complexity for insertion, removal, and lookup.

    set<int> s = {10, 20, 30, 40};
s.insert(25);        // Insert element
s.erase(20);         // Remove element
bool found = s.count(25); // Check if element exists

  • unordered_set: A hash-based collection of unique elements. Average-case time complexity for insertion, removal, and lookup is O(1).

    unordered_set<int> us = {1, 2, 3, 4, 5};
us.insert(6);         // Insert element
us.erase(2);          // Remove element
bool found = us.count(3); // Check if element exists

  • map: A collection of key-value pairs, sorted by keys. Provides O(log n) time complexity for insertion, removal, and lookup.

    map<string, int> m = {{"apple", 1}, {"banana", 2}, {"cherry", 3}};
m["date"] = 4;       // Insert/Update element
m.erase("banana");   // Remove element
bool found = m.count("cherry"); // Check if key exists

  • unordered_map: A hash-based collection of key-value pairs. Average-case time complexity for insertion, removal, and lookup is O(1).

    unordered_map<string, int> um = {{"apple", 1}, {"banana", 2}, {"cherry", 3}};
um["date"] = 4;         // Insert/Update element
um.erase("banana");     // Remove element
bool found = um.count("cherry"); // Check if key exists

  • queue and deque: Used for FIFO operations (queue) or double-ended queues (deque) that allow insertion and removal from both ends.

    queue<int> q;
q.push(1);
q.push(2);
int front = q.front(); // Get front element
q.pop();               // Remove front element

deque<int> d = {1, 2, 3, 4};
d.push_back(5);
d.push_front(0);
d.pop_back();
d.pop_front();

  • priority_queue: A queue where the largest element is always at the front. By default, a max heap is used, but you can use a min heap with std::greater.

    priority_queue<int> pq;
pq.push(1);
pq.push(2);
pq.push(3);
int top = pq.top(); // Get top element
pq.pop();           // Remove top element

priority_queue<int, vector<int>, greater<int>> min_pq;
min_pq.push(1);
min_pq.push(2);
min_pq.push(3);
int top_min = min_pq.top(); // Get smallest element
min_pq.pop();               // Remove smallest element

3. Key Algorithms in Competitive Programming:

  • Sorting: std::sort is highly optimized and can be used with custom comparator functions.

    vector<int> v = {3, 1, 4, 2};
sort(v.begin(), v.end()); // Sort in ascending order
sort(v.rbegin(), v.rend()); // Sort in descending order

// Custom comparator for structs
struct Point {
    int x, y;
};
vector<Point> points = {{1,2}, {1,1}, {2,1}};
sort(points.begin(), points.end(), [](const Point &a, const Point &b) {
    return a.x < b.x || (a.x == b.x && a.y < b.y);
});

  • Searching: Binary search functions like std::binary_search, std::lower_bound, and std::upper_bound are useful for searching in sorted arrays or vectors.

    vector<int> v = {1, 2, 4, 5, 6};
bool found = binary_search(v.begin(), v.end(), 4); // Check if 4 is present
auto lb = lower_bound(v.begin(), v.end(), 3); // First element not less than 3
auto ub = upper_bound(v.begin(), v.end(), 3); // First element greater than 3

  • Set Operations: Functions such as std::set_union, std::set_intersection, std::set_difference, and std::set_symmetric_difference are useful for operations on sorted containers.

    vector<int> a = {1, 2, 4, 5, 6}, b = {2, 4, 6, 8};
vector<int> result(10);
auto it = set_union(a.begin(), a.end(), b.begin(), b.end(), result.begin());
result.resize(it - result.begin()); // Resize result to fit actual size

  • Transformations and Accumulations: Functions like std::transform and std::accumulate are useful for applying operations across containers.

    vector<int> v = {1, 2, 3, 4};
int sum = accumulate(v.begin(), v.end(), 0); // Sum of elements

vector<int> doubled(v.size());
transform(v.begin(), v.end(), doubled.begin(), [](int x) { return x * 2; });

  • Heap Operations: Functions like std::make_heap, std::push_heap, std::pop_heap, and std::sort_heap are useful for heap operations.

    vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
make_heap(v.begin(), v.end());
pop_heap(v.begin(), v.end()); // Move largest element to end
v.pop_back();                 // Remove largest element
push_heap(v.begin(), v.end()); // Push last element into heap
sort_heap(v.begin(), v.end());  // Sort heap into sorted vector

4. Best Practices for Using STL in Competitive Programming:

  • Familiarize Yourself with Common Functions: Spending time understanding the capabilities and complexities of STL functions can save time during competitions.

  • Custom Comparators: Knowing how to create custom comparison functions for sorting and set operations is crucial for handling complex data types.

  • Efficient Data Structures: Choosing the right data structure for the problem can mean the difference between passing and failing time constraints.

  • Template Metaprogramming: Advanced usage of templates can help write more generic and reusable code, though it’s usually best to stick to basic STL features in competitive settings.

  • Avoid Unnecessary Copying: Use iterators and references instead of copying data to avoid performance penalties.

  • Debugging: Be aware of how STL functions modify the data structures they operate on. Debugging STL code can be challenging when unexpected modifications occur.

  • Precomputation: When possible, precompute values or structures that can be reused across test cases to minimize runtime.

Online Code run

🔔 Note: Select your programming language to check or run code at

💻 Run Code Compiler

Step-by-Step Guide: How to Implement CPP Programming Using STL in Competitive Programming

Table of Contents

  1. Introduction to STL
  2. Commonly Used STL Containers
    • Vector
    • List
    • Deque
    • Set/Multiset
    • Map/Multimap
    • Priority Queue/Heap
  3. Commonly Used STL Algorithms
    • Sort
    • Binary Search
    • Lower/Upper Bound
    • Min/Max
    • Accumulate
    • Reverse
    • Unique
  4. Example Problems
    • Problem 1: Using Vector for Dynamic Arrays
    • Problem 2: Using Map for Counting Frequencies
    • Problem 3: Using Set for Unique Elements
    • Problem 4: Using Sort and Binary Search
  5. Tips and Tricks
  6. Conclusion

1. Introduction to STL

STL (Standard Template Library) is a powerful set of C++ template classes to provide common programming data structures and functions such as vectors, lists, queues, stacks, and associative arrays (sets and maps).

2. Commonly Used STL Containers

Vector

A dynamic array, useful when you need a resizable array.

#include <vector>
#include <iostream>
using namespace std;

int main() {
    vector<int> v;  // Declare a vector of integers

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

    for(int i = 0; i < v.size(); i++) 
        cout << v[i] << ' ';  // Output: 10 20 30
    return 0;
}

List

Doubly linked list, allows for insertion and deletion in constant time.

#include <list>
#include <iostream>
using namespace std;

int main() {
    list<int> l;  // Declare a list of integers

    l.push_back(20); 
    l.push_back(30); 
    l.push_front(10); 

    for(auto it = l.begin(); it != l.end(); it++) 
        cout << *it << ' ';  // Output: 10 20 30
    return 0;
}

Deque

Double-ended queue, allows for efficient insertion and deletion at both ends.

#include <deque>
#include <iostream>
using namespace std;

int main() {
    deque<int> dq;  // Declare a deque of integers

    dq.push_back(20); 
    dq.push_back(30); 
    dq.push_front(10); 

    for(auto it = dq.begin(); it != dq.end(); it++) 
        cout << *it << ' ';  // Output: 10 20 30
    return 0;
}

Set/Multiset

Set stores unique elements in a sorted manner. Multiset stores duplicate elements in a sorted manner.

#include <set>
#include <iostream>
using namespace std;

int main() {
    set<int> s;  // Declare a set of integers

    s.insert(20); 
    s.insert(30); 
    s.insert(10); 
    s.insert(10);  // Duplicate value will be ignored

    for(auto it = s.begin(); it != s.end(); it++) 
        cout << *it << ' ';  // Output: 10 20 30
    return 0;
}

Map/Multimap

Map stores key-value pairs, the keys are unique and sorted. Multimap stores duplicate keys.

#include <map>
#include <iostream>
using namespace std;

int main() {
    map<string, int> m;  // Declare a map with string keys and int values

    m["apple"] = 10; 
    m["banana"] = 20; 
    m["apple"] = 5;    // Overwriting previous value

    for(auto it = m.begin(); it != m.end(); it++) 
        cout << it->first << " " << it->second << endl;  // Output: apple 5 banana 20
    return 0;
}

Priority Queue/Heap

Priority queue is a special kind of queue where elements are ordered by priority. By default it is a max-priority queue.

#include <queue>
#include <iostream>
using namespace std;

int main() {
    priority_queue<int> pq;  // Declare a max-priority queue

    pq.push(10); 
    pq.push(20); 
    pq.push(30);

    while(!pq.empty()) {
        cout << pq.top() << ' ';  // Output: 30 20 10
        pq.pop();
    }
    return 0;
}

3. Commonly Used STL Algorithms

Sort

Sorts the elements in a container.

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    vector<int> v = {10, 20, 5, 15};

    sort(v.begin(), v.end());

    for(int i = 0; i < v.size(); i++) 
        cout << v[i] << ' ';  // Output: 5 10 15 20
    return 0;
}

Binary Search

Used to search for an element in a sorted array/container.

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    vector<int> v = {10, 20, 5, 15};

    sort(v.begin(), v.end());

    bool found = binary_search(v.begin(), v.end(), 15);
    cout << "Found: " << found << endl;  // Output: Found: 1

    found = binary_search(v.begin(), v.end(), 25);
    cout << "Found: " << found;  // Output: Found: 0
    return 0;
}

Lower/Upper Bound

Finds the first element not less/greater than a given value.

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    vector<int> v = {1, 5, 5, 10, 15};

    auto lower = lower_bound(v.begin(), v.end(), 5);
    auto upper = upper_bound(v.begin(), v.end(), 5);

    cout << "Lower bound index: " << (lower - v.begin()) << endl;  // Output: Lower bound index: 1
    cout << "Upper bound index: " << (upper - v.begin()) << endl;  // Output: Upper bound index: 3

    return 0;
}

Min/Max

Finds the minimum and maximum values in a range.

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    vector<int> v = {8, 3, 7, 2, 5};

    cout << "Min: " << *min_element(v.begin(), v.end()) << endl;  // Output: Min: 2
    cout << "Max: " << *max_element(v.begin(), v.end()) << endl;  // Output: Max: 8

    return 0;
}

Accumulate

Sums up elements in a range.

#include <vector>
#include <numeric>
#include <iostream>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3, 4, 5};

    int sum = accumulate(v.begin(), v.end(), 0);
    cout << "Sum: " << sum << endl;  // Output: Sum: 15

    return 0;
}

Reverse

Reverses a range.

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3, 4, 5};

    reverse(v.begin(), v.end());

    for(int i = 0; i < v.size(); i++) 
        cout << v[i] << ' ';  // Output: 5 4 3 2 1
    return 0;
}

Unique

Removes consecutive duplicates from a sorted range.

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    vector<int> v = {1, 2, 2, 3, 3, 3, 4, 5};

    auto last = unique(v.begin(), v.end());

    for(auto it = v.begin(); it != last; it++) 
        cout << *it << ' ';  // Output: 1 2 3 4 5
    return 0;
}

4. Example Problems

Problem 1: Using Vector for Dynamic Arrays

Problem Statement: Given a sequence of numbers, find the sum of all even numbers.

#include <vector>
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    
    for(int i = 0; i < n; i++) 
        cin >> v[i];

    int sum = 0;
    for(int i = 0; i < n; i++) 
        if(v[i] % 2 == 0) 
            sum += v[i];

    cout << "Sum of even numbers: " << sum;
    return 0;
}

Input:

5
1 2 3 4 5

Output:

Sum of even numbers: 6

Problem 2: Using Map for Counting Frequencies

Problem Statement: Count the frequency of each character in a string.

#include <map>
#include <iostream>
using namespace std;

int main() {
    string s;
    cin >> s;
    map<char, int> freq;

    for(char c : s) 
        freq[c]++;

    for(auto it = freq.begin(); it != freq.end(); it++) 
        cout << it->first << " " << it->second << endl;
    return 0;
}

Input:

hello

Output:

e 1
h 1
l 2
o 1

Problem 3: Using Set for Unique Elements

Problem Statement: Find the unique numbers in a given sequence.

#include <set>
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    set<int> s;

    for(int i = 0; i < n; i++) {
        int x; 
        cin >> x;
        s.insert(x);
    }

    for(auto it = s.begin(); it != s.end(); it++) 
        cout << *it << ' ';
    return 0;
}

Input:

5
1 2 2 3 3

Output:

1 2 3

Problem 4: Using Sort and Binary Search

Problem Statement: Given two sorted arrays, find common elements.

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> v1(n), v2(m);
    
    for(int i = 0; i < n; i++) 
        cin >> v1[i];
    for(int i = 0; i < m; i++) 
        cin >> v2[i];

    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());

    for(int i = 0; i < n; i++) {
        if(binary_search(v2.begin(), v2.end(), v1[i]))
            cout << v1[i] << ' ';
    }
    return 0;
}

Input:

5 5
1 2 3 4 5
4 5 6 7 8

Output:

4 5

5. Tips and Tricks

  • Use push_back() for dynamic arrays.
  • Utilize sets and maps to maintain unique elements and maintain order.
  • Take advantage of sort(), lower_bound(), and upper_bound() for efficient searching.
  • Be cautious of the time complexity of your STL operations; e.g.,map and set provide logarithmic time complexity for insertion, deletion, and lookup.

6. Conclusion

STL is an essential part of competitive programming in C++ due to its efficiency and convenience. Understanding the basic containers and algorithms provided by STL can greatly enhance your problem-solving capabilities. Practice regularly to become proficient with these tools. Happy coding!

Top 10 Interview Questions & Answers on CPP Programming Using STL in Competitive Programming

1. What is STL and why should it be used in competitive programming?

Answer: The Standard Template Library (STL) is a collection of templates that implement popular and commonly used data structures and algorithms in C++. In competitive programming, using STL can significantly speed up the development process, reducing the likelihood of bugs from manually writing such structures. It provides well-optimized implementations of algorithms which often comply with the time complexity required by competitive problems.

2. How do you use vectors in C++ STL?

Answer: Vectors in STL are dynamic arrays that allow random access and fast insertions/deletions at the end but relatively slow in the beginning or middle. You start by including the vector header file #include <vector>, then declare a vector: std::vector<int> v;. Common operations include:

  • v.push_back(x): Adds element x at the end.
  • v.pop_back(): Removes the last element.
  • v.size(): Returns number of elements.
  • v.empty(): Checks if vector is empty.
  • v.clear(): Clears all elements.
  • v[i]: Access element at index i.
  • Iterating through a vector can be done using range-based for loops or iterators.

3. What are the methods to sort an array or vector in STL?

Answer: Sorting in STL can be done using the std::sort function. For sorting a vector:

#include <vector>
#include <algorithm>

std::vector<int> v = {4,2,5,1,3};
std::sort(v.begin(), v.end()); // Sorts ascending
// Use std::greater comparator for descending order
std::sort(v.begin(), v.end(), std::greater<int>());

You can specify custom comparators for more complex sorting logic by defining a function or functor.

4. How can we perform binary search using STL?

Answer: Binary search is performed using the std::binary_search, std::lower_bound, and std::upper_bound functions.

  • std::binary_search(v.begin(), v.end(), x): Returns true if x is present.
  • std::lower_bound(v.begin(), v.end(), x): Returns iterator to first element not less than x.
  • std::upper_bound(v.begin(), v.end(), x): Returns iterator to first element greater than x.

These functions require the container to already be sorted.

5. What is the difference between list and vector STL containers?

Answer: The main differences lie in memory usage and performance characteristics.

  • List: A doubly linked list allowing insertion/deletion from any position in constant time, but random access is costly.
  • Vector: A dynamic array offering constant time access to any element, but insertions/deletions are expensive when not done at the end.

Use list when frequent insertions/deletions happen at any position; use vector when random access and appending/popping from end are frequent.

6. How do we initialize a set and what operations does it support?

Answer: Sets in STL are ordered collections of unique elements implemented as balanced trees. Include with #include <set> and initialize like: std::set<int> s;. Supported operations:

  • s.insert(x): Inserts x.
  • s.erase(x): Removes x.
  • s.find(x): Returns iterator to position of x.
  • s.size(): Gets size.
  • s.empty(): Checks emptiness.

Iterating over a set will yield its elements in sorted order.

7. Can you explain how to use map and multimap effectively in competitive programming?

Answer: Maps store unique key-value pairs sorted by keys, while multimaps allow duplicate keys.

#include <map>
#include <iostream>

std::map<std::string, int> m; // Sorted by key
m["apple"] = 5;
m["banana"] = 3;

// Iterate through map
for(const auto& p : m)
    std::cout << p.first << ": " << p.second << '\n';

m.find("apple") returns an iterator to first match key else .end().

Multimaps are useful when multiple values can have the same key and the order of insertion matters, but only for equal keys.

8. What is the purpose of the priority_queue STL and what operations does it perform efficiently?

Answer: Priority queues (std::priority_queue) are max-heaps by default but can be turned into min-heaps. They provide efficient access to the highest (or lowest) element. Include: #include <queue>.

Operations:

  • pq.push(x): Inserts x.
  • pq.pop(): Removes the topmost element.
  • pq.top(): Accesses the largest element.
  • pq.size(): Check size.
  • pq.empty(): Checks emptiness.

For a min-heap, define the priority queue like this: std::priority_queue<int, std::vector<int>, std::greater<int>> pq;.

9. How do you use the deque container in STL?

Answer: Deque (Double-ended Queue) is similar to a vector, but inserts and deletions are fast even at the beginning. Include: #include <deque>.

Example usage:

std::deque<int> dq = {3, 2, 1};
dq.push_front(0); // Add to front
dq.push_back(4);  // Add to back
dq.pop_front();   // Remove from front
dq.pop_back();    // Remove from back

Deques offer fast access to any position, though not as fast as vectors due to internal architecture.

10. How would you use algorithm functions such as min_element, max_element, accumulate, and count in your competitive program?

Answer: Algorithm functions operate on iterators providing powerful utilities.

  • std::min_element(arr.begin(), arr.end()): Returns iterator pointing to the minimum element.
  • std::max_element(arr.begin(), arr.end()): Points to the maximum element.
  • std::accumulate(arr.begin(), arr.end(), init_val): Computes the cumulative sum/difference/product etc., starting from init_val.
  • std::count(arr.begin(), arr.end(), value): Counts occurrences of value.

Example:

#include <vector>
#include <numeric>
#include <algorithm>

std::vector<long long> numbers = {1, 2, 3, 4, 5};

long long total = std::accumulate(numbers.begin(), numbers.end(), 0LL); // Sums numbers initializing to 0LL to prevent overflow
auto min_it = std::min_element(numbers.begin(), numbers.end());       // Finds min element
auto max_it = std::max_element(numbers.begin(), numbers.end());       // Finds max element
int freq_of_two = std::count(numbers.begin(), numbers.end(), 2);      // Counts occurrences of 2

std::cout << "Total Sum: "   << total   << "\n";
std::cout << "Min Element: " << *min_it << "\n";
std::cout << "Max Element: " << *max_it << "\n";
std::cout << "Count of 2: "  << freq_of_two << "\n";

These functions make it easier to handle basic computations and manipulations on sequences with less code complexity.

You May Like This Related .NET Topic

📥 Download Code ▶️ Watch Online 📖 Read Description

Login to post a comment.