C++ (until C++20)

lvalues & rvalues + Move Semantics

:::note Resources

Some of the following are super obvious logically, but listing them for completeness.

✓ lvalue = lvalue / rvalue
✕ rvalue = lvalue / rvalue
✓ lvalue reference = lvalue
✕ lvalue reference = rvalue
✓ const lvalue reference = lvalue / rvalue
✓ rvalue reference = rvalue
std::move(lvalue) will be rvalue

Object Oriented Programming

A derived class must specify the class(es) from which it intends to inherit. It does so in a class derivation list, which is a colon followed by a comma-separated list of base classes each of which may have an optional access specifier.

In C++, dynamic binding (sometimes known as run-time binding) happens when a virtual function is called through a reference (or a pointer) to a base class.

Any nonstatic member function, other than a constructor, may be virtual.

The virtual keyword appears only on the declaration inside the class and may not be used on a function definition that appears outside the class body.

A function that is declared as virtual in the base class is implicitly virtual in the derived classes as well.

Language Features

Attribute specifier sequence

`[[maybe_unused]]`

Suppresses warnings on unused entities. Link: https://en.cppreference.com/w/cpp/language/attributes/maybe_unused

int main() {
    /* repeat something 10 times */
    for (int _ [[maybe_unused]] : views::iota(0, 10)) {
        // ...
    }
}

User-defined Literals

Note that a literal should start with an underscore _. We declare a new literal by this pattern:

[returnType] operator "" _[name]([parameters]) { [body] }

Note that parameters can be only one of these:

(const char *) (unsigned long long int) (long double) (char) (wchar_t) (char16_t) (char32_t) (const char *, size_t) (const wchar_t *, size_t) (const char16_t *, size_t) (const char32_t *, size_t)

Literals also can used with templates.

std::vector<uint64_t> operator "" _v(unsigned long long int x) {
    return vector<uint64_t> {x};
}

int main() {
    auto v = 36_v;
    std::cout << v.size() << ' ' << v[0] << std::endl;  // 1 36
}

Some Features

`std::views`

Header <ranges>

#include <iostream>
#include <ranges>

int main() {
    {
        int a[] = {1, 2, 3, 4, 5};
        for (auto& x : a) std::cout << x << ' ';                        // 1 2 3 4 5
        for (auto& x : a | std::views::reverse) std::cout << x << ' ';  // 5 4 3 2 1
    }
    {
        for (auto x : std::views::iota(3, 9)) std::cout << x << ' ';    // 3 4 5 6 7 8
    }
}

`std::nth_element`

std::nth_element ➝ Finds n^th element and partitions the array around it. Link

`std::min`

Instead of int a = min(x1,min(x2,min(x3,min(x4,x5))));, int a = min({x2,x2,x3,x4,x5}); can be done.

Standard Template Library (STL)

`std::array`

Header <array>

template<   class T,
            std::size_t N   > struct array;

Not sure if this is in C++ standard or just GCC implementation, but std::array<int, N> is an alias of int* for any N which is size_t.

`std::set`

Header <set>

template<   class Key,
            class Compare = std::less<Key>,
            class Allocator = std::allocator<Key>   > class set;

#include <set>

#include <iostream>
using std::cout, std::endl;

int main() {
    {
        std::set<int> s = {3, 1, 2, 5, 4, 6};

        auto it = s.begin(); // `it` is std::_Rb_tree_const_iterator<int> in GCC

        for (auto& value : s) { cout << value << ' '; } cout << endl;   // 1 2 3 4 5 6

        std::set<int, std::greater<int>> s_greater = {3, 1, 2, 5, 4, 6};
        for (auto& value : s_greater) { cout << value << ' '; } cout << endl;   // 6 5 4 3 2 1
    }

    // custom comparator
    {
        std::vector<int> order = {3, 4, 2, 5, 0, 1};
        auto cmp = [&](int x, int y) { return order[x] < order[y]; };
        std::set<int, decltype(cmp)> s(cmp);
    }

    // emplace -> returns iterator to the newly inserted element
    {
        std::set<int> set;
        for (int i = 0; i < 10; ++i) { set.emplace(i); }
    }

    // emplace_hint -> returns iterator to the newly inserted element
    {
        std::set<int> set;
        for (int i = 0; i < 10; ++i) { set.emplace_hint(set.end(), i); }
    }

    // merge -> complexity: N * log(size() + N), where N is size of passed in set / multiset.
    // No elements are copied or moved, only the internal pointers of the container nodes are repointed.
    {
        std::set<char> p{ 'C', 'B', 'B', 'A' }, q{ 'E', 'D', 'E', 'C' };
        p.merge(q);
        // at this point p -> { A, B, C, D, E }, q -> { C }
    }

    // count -> returns 0 / 1
    // find -> returns iterator
    // contains -> returns bool
    {
        // self-explanatory
    }

    {
        std::set<int> set = {3, 1, 2, 9, 2, 7};
        auto it1 = set.lower_bound(3);  // find >= 3
        auto it2 = set.upper_bound(3);  // find > 3
        cout << *it1 << ' ' << *it2 << endl;    // 3 7
    }
}

`std::multimap`

Header <map>

template<   class Key,
            class T,
            class Compare = std::less<Key>,
            class Allocator = std::allocator<std::pair<const Key, T> >   > class multimap;

`std::list`

Header <list>

template<   class T,
            class Allocator = std::allocator<T>   > class list;

#include <list>
#include <iostream>

int main() {
    {
        std::list<char> list;
        auto print_list = [&]() { for (auto& x : list) std::cout << x << ' '; std::cout << std::endl; };

        list.assign(6, 'c');
        print_list();   // c c c c c c

        const std::string string = "qwerty";
        list.assign(string.begin(), string.end());
        print_list();   // q w e r t y

        list.assign({'a', 'b', 'c', 'x', 'y', 'z'});
        print_list();   // a b c x y z
    }

    {
        std::list<int> list = {3, 4, 1, 2};
        std::cout << list.front() << ' ' << list.back() << std::endl;           // 3 2

        list.front() = 30;
        list.back() = 20;
        for (auto& x : list) std::cout << x << ' '; std::cout << std::endl;     // 30 4 1 20
    }

    // insert, push_back, pop_back, push_front, pop_front
    {

    }
}

`std::iterator`

std::begin and std::end functions

#include <array>
#include <iterator>
#include <vector>

int main() {
    int c_array[5] = {};
    std::array<int, 5> cpp_array = {};
    std::vector<int> cpp_vector(5);

    int* c_array_begin = std::begin(c_array);       // = c_array + 0
    int* c_array_end = std::end(c_array);           // = c_array + 5

    int* cpp_array_begin = std::begin(cpp_array);   // = cpp_array.begin();
    int* cpp_array_end = std::end(cpp_array);       // = cpp_array.end();

    std::vector<int>::iterator cpp_vector_begin = std::begin(cpp_vector); // = cpp_vector.begin();
    std::vector<int>::iterator cpp_vector_end = std::end(cpp_vector);     // = cpp_vector.end();
}

Custom definition of std::hash

template<> struct std::hash<std::list<int>::iterator> {
    size_t operator()(list<int>::iterator const& it) const noexcept {
        return hash<int*>()(&*it); // assuming that iterators contain data at different addresses
    }
};

void solve() {
    int n; string s; cin >> n >> s;
    list<int> l; for (auto const& c : s) l.push_back(c - '0');
    unordered_set<list<int>::iterator> p[10];
    // ... ... ...

Utilities

`std::numeric_limits`

#include <numeric>

auto x1 = std::numeric_limits<int32_t>::min() // x1 = -2^31 = -2147483648
auto x2 = std::numeric_limits<int32_t>::max() // x2 = 2^31-1 = 2147483647

Random Number Generator

static unsigned short rndint() {
    static unsigned long long seed = 5;
    return ((unsigned int)((seed = seed * 25214903917ULL + 11ULL) >> 16));
}

`std::midpoint`

// template< class T >
// constexpr T midpoint( T a, T b ) noexcept;
// (since C++20)

#include <numeric>

auto x1 = std::numeric_limits<int32_t>::max(); // x1 = 2147483647
auto x2 = std::midpoint(x1, x1 - 2); // x2 = 2147483646

// template< class T >
// constexpr T* midpoint( T* a, T* b );
// (since C++20)

#include <numeric>

std::array<int32_t, 7> x1 = {5, 9, 2, 3, 1, 4, 6};
int* x2 = std::midpoint(std::next(x1.begin(), 2), x1.end()); // *x2 = 1

Disjoint Set (Union-Find)

#include <iostream>
#include <vector>
#include <array>
#include <format>

class DisjointSet {
    std::vector<int32_t> _parent;

    [[nodiscard]] int32_t _get_root(int32_t element) const {
        while (_parent[element] >= 0) {
            element = _parent[element];
        }
        return element;
    }

    int32_t _get_root_and_reassign_parents(int32_t element) {
        auto root = _get_root(element);
        while (true) {
            auto& parent = _parent[element];
            if (parent < 0) {
                break;
            }
            element = parent;
            parent = root;
        }
        return root;
    }

public:
    explicit DisjointSet(int32_t size) {
        _parent.assign(size, -1);
    }

    /**
     * @return `true` if u, v are not already in same set.
     */
    bool merge(int32_t u, int32_t v) {
        auto root_u = _get_root_and_reassign_parents(u);
        auto root_v = _get_root_and_reassign_parents(v);

        if (root_u == root_v) {
            return false;
        }

        if (_parent[root_u] > _parent[root_v]) {
            std::swap(root_u, root_v);
        }

        _parent[root_u] += _parent[root_v];
        _parent[root_v] = u;
        return true;
    }

    bool is_same_set(int32_t u, int32_t v) {
        auto root_u = _get_root_and_reassign_parents(u);
        auto root_v = _get_root_and_reassign_parents(v);

        return root_u == root_v;
    }
};

int main() {
    auto disjoint_set = DisjointSet(5);
    disjoint_set.merge(2, 3);
    disjoint_set.merge(3, 5);
    std::cout << disjoint_set.is_same_set(2, 5); // 1
}

Files

#include <iostream>
#include <fstream>

int main() {
    std::ifstream ifile("hello.txt");

    if (!ifile) {
        std::cerr << "Failed to open file!" << std::endl;
        return 0;
    }

    std::string str;

    // Rrad word by word by trimming whitespace
    while (ifile >> str) {
        std::cout << str << ' ';
    }

    // Can also line by line by trimming new line characters
    while (std::getline(ifile, str)) {
        std::cout << str << std::endl;
    }

    ifile.close();

    std::ofstream ofile("hello.txt");
    if (!ofile) {
        std::cerr << "Failed to create file!" << std::endl;
        return 0;
    }

    ofile << "Hello, World!";

    ofile.close();
}