Recap of C++ features relevant to competitive programming

When it comes to competitive programming, having a good understanding of the C++ programming language can give you a significant advantage. C++ is a powerful language that offers a wide range of features and techniques that can help you solve coding challenges quickly and efficiently. In this article, we will recap some of the most relevant C++ features for competitive programming.

Standard Input/Output

Efficiently reading input and printing output is crucial in competitive programming. C++ provides the iostream library, which allows you to interact with standard input and output easily.

To read input, you can use std::cin or std::getline for reading strings. Similarly, std::cout is used for standard output. Remember to include the <iostream> header at the beginning of your code.

#include <iostream>

int main() {
    int n;
    std::cin >> n;
    std::cout << "You entered: " << n << std::endl;
    return 0;
}

Standard Template Library (STL)

The Standard Template Library (STL) is a powerful library that provides various data structures and algorithms. Understanding and utilizing the STL can save you a lot of time and effort.

Some important STL containers for competitive programming include:

• std::vector: A dynamic array that allows you to add or remove elements easily.
• std::set: A container that stores unique elements in a sorted order.
• std::map: A container that stores key-value pairs, where keys are unique.
• std::queue: A container that follows the FIFO (First-In-First-Out) order.
• std::stack: A container that follows the LIFO (Last-In-First-Out) order.

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>

int main() {
    // Vector
    std::vector<int> vec = {1, 2, 3};
    vec.push_back(4);
    
    // Set
    std::set<int> mySet = {3, 2, 1};
    mySet.insert(4);
    
    // Map
    std::map<std::string, int> myMap;
    myMap["Alice"] = 25;
    myMap["Bob"] = 30;
    
    // Queue
    std::queue<int> myQueue;
    myQueue.push(1);
    myQueue.push(2);
    
    // Stack
    std::stack<int> myStack;
    myStack.push(1);
    myStack.push(2);
}

Algorithms

C++ provides numerous algorithms in the STL that can simplify complex operations. Some commonly used algorithms in competitive programming include:

• std::sort: Sorts elements in a given range.
• std::reverse: Reverses the order of elements in a range.
• std::binary_search: Searches for a specific value in a range.
• std::lower_bound and std::upper_bound: Returns iterators pointing to the lower/upper bound of a given value.

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> vec = {3, 1, 4, 2};
    std::sort(vec.begin(), vec.end());
    
    if (std::binary_search(vec.begin(), vec.end(), 3)) {
        std::cout << "3 found in vec!" << std::endl;
    }
    
    /* Output:
       1 2 3 4 */
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

Custom Sorting

Sometimes, you may need to sort elements based on a custom criteria. C++ allows you to define custom comparison functions for sorting purposes.

#include <iostream>
#include <algorithm>
#include <vector>

bool customSort(int a, int b) {
    /* Sort in descending order */
    return a > b;
}

int main() {
    std::vector<int> vec = {3, 1, 4, 2};
    std::sort(vec.begin(), vec.end(), customSort);
    
    /* Output:
       4 3 2 1 */
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

Conclusion

Having a good understanding of the C++ language and its features can greatly enhance your capabilities in competitive programming. This recap covered some of the most relevant features, including standard input/output, the Standard Template Library (STL), various algorithms, and custom sorting. Practice utilizing these features, and you'll be well-equipped to tackle coding challenges efficiently and effectively.