C++ Basics

Header Files

Files with a .h or .hpp extension that contain declarations of functions, classes, variables, and other constructs. They allow code to be shared across multiple source files by including the header file using the #include directive.

Namespace

Used to organize code and prevent name conflicts. They provide a way to group related classes, functions, and variables under a unique identifier. The scope resolution operator :: is used to access elements within a namespace.

The std namespace contains all the standard library functions and objects.

#include <iostream>

int main() {
    std::cout << "Hello, World!" << std::endl;
    return 0;
}

To avoid repeatedly specifying the namespace, using namespace directive can be used. This directive brings all the names from the specified namespace into the current scope. Might lead to name conflicts in large projects.

#include <iostream>
using namespace std;

int main() {
    cout << "Hello, World!" << endl;
    return 0;
}

Standard Library

Containers

Container classes are used to store and manage collections of data.

Sequential

Store elements in a linear order.

• std::vector
  Dynamic array that can grow or shrink in size.
• std::deque
  Double-ended queue that allows insertion and deletion at both ends.
• std::list
  Doubly linked list for efficient insertion and deletion.
• std::stack
  Adapts other containers to provide stack (LIFO) functionality.
• std::queue
  Adapts other containers to provide queue (FIFO) functionality.
• std::priority_queue
  Provides a container adapter that maintains elements in a priority order.

Associative

Store elements in a sorted order and allow fast retrieval based on keys.

• std::set
  Stores unique elements in sorted order.
• std::map
  Stores key-value pairs with unique keys in sorted order.

Unordered

Store elements in an unsorted order but provide faster average lookup times using hash tables.

• std::unordered_set
  Stores unique elements without any specific order.
• std::unordered_map
  Stores key-value pairs without any specific order.

Utility

Provide specialized ways to group or manage data.

• std::pair
  Groups two values together, which can be of different types.
• std::tuple
  Groups multiple values together, which can be of different types.
• std::string
  Represents a sequence of characters and provides various operations for string manipulation.

Algorithms

Sorting

• std::sort
  Sorts elements in ascending order in a range. $O(N \log N)$ average.
• std::stable_sort
  Sorts elements in a range while preserving the relative order of equivalent elements.
• std::partial_sort
  Rearranges elements so that the smallest k elements are sorted, and the rest remain unsorted.
• std::nth_element
  Partially sorts elements such that the element at the nth position is the one that would be in that position in a fully sorted range, with all smaller elements before it and all larger elements after it.

Searching

• std::binary_search
  Checks if a value exists in a sorted range. Returns true if the value is found.
• std::lower_bound
  Finds the first position in a sorted range where a value can be inserted without violating the order.
• std::upper_bound
  Finds the first position in a sorted range where a value can be inserted after all equivalent elements.
• std::equal_range
  Returns a pair of iterators defining the range of elements equivalent to a given value in a sorted range.

Permutations

• std::next_permutation
  Rearranges elements into the next lexicographically greater permutation. Returns false if no such permutation exists.
• std::prev_permutation
  Rearranges elements into the next lexicographically smaller permutation. Returns false if no such permutation exists.

Other

• std::find
  Searches for a specific value in a range.
• std::accumulate
  Computes the sum of elements in a range.
• std::reverse
  Reverses the order of elements in a range.
• std::unique
  Removes consecutive duplicate elements in a range. Returns an iterator to the new logical end.
• std::count
  Counts the occurrences of a specific value in a range.
• std::count_if
  Counts the number of elements in a range that satisfy a given predicate.
• std::min_element
  Finds the smallest element in a range.
• std::max_element
  Finds the largest element in a range.
• std::distance
  Calculates the number of elements between two iterators.
• std::rotate
  Rotates the elements in a range such that a specified element becomes the first.
• std::shuffle
  Randomly rearranges the elements in a range using a random number generator.
• std::fill
  Assigns a specified value to all elements in a range.
• std::iota
  Fills a range with sequentially increasing values starting from a given value.
• std::merge
  Merges two sorted ranges into a single sorted range.
• std::copy
  Copies elements from one range to another.

Iterators

Allow traversal of elements in a container. They provide a way to access elements sequentially without exposing the underlying representation. Common types of iterators:

• std::begin and std::end
  Used to obtain iterators pointing to the beginning and end of a container.
• std::advance
  Moves an iterator forward by a specified number of steps.

Mathematical Functions

• std::abs
  Returns the absolute value of a number.
• std::ceil
  Rounds a number up to the nearest integer.
• std::floor
  Rounds a number down to the nearest integer.
• std::round
  Rounds a number to the nearest integer.
• std::sqrt
  Computes the square root of a number.
• std::pow
  Raises a number to a specified power.
• std::log
  Computes the natural logarithm of a number.
• std::log10
  Computes the base-10 logarithm of a number.
• std::sin, std::cos, std::tan
  Compute the sine, cosine, and tangent of an angle (in radians).
• std::asin, std::acos, std::atan
  Compute the arcsine, arccosine, and arctangent of a value.
• std::hypot
  Computes the length of the hypotenuse of a right triangle given its two sides.
• std::exp
  Computes the exponential function $e^x$.
• std::fmod
  Computes the remainder of division of two floating-point numbers.
• std::gcd
  Computes the greatest common divisor (GCD) of two integers.
• std::lcm
  Computes the least common multiple (LCM) of two integers.

Utilities

• std::function
  Encapsulates callable objects like functions, lambdas, and functors.
• std::unique_ptr and std::shared_ptr
  Smart pointers for managing dynamic memory.

Input/Output

• std::cin and std::cout
  Used for console input and output.
• std::fstream
  Used for file input and output.