Below is a concise cheat sheet for the most important functions in the C+
+ `<algorithm>` library, tailored for a CS exam. The `<algorithm>`
library provides a collection of functions for common tasks like sorting,
searching, and manipulating containers (like arrays, vectors, etc.). I’ll
focus on the most commonly used functions, explain how to use them,
and provide examples. This cheat sheet is designed to be compact for
quick reference during your exam.
---
### C++ `<algorithm>` Library Cheat Sheet
#### **1. Sorting Functions**
These functions sort elements in a range (e.g., arrays, vectors).
- **sort(first, last)**
- Sorts the range `[first, last)` in **ascending order**.
- **Usage**: `sort(arr.begin(), arr.end());` (for vectors) or `sort(arr, arr +
n);` (for arrays).
- **Example**:
```cpp
#include <algorithm>
int arr[5] = {5, 2, 9, 1, 3};
sort(arr, arr + 5); // Sorts array
// arr is now {1, 2, 3, 5, 9}
```
- **sort(first, last, comp)**
- Sorts with a custom comparator (e.g., descending order).
- **Usage**: `sort(arr.begin(), arr.end(), greater<int>());` (descending).
- **Example**:
```cpp
#include <algorithm>
int arr[5] = {5, 2, 9, 1, 3};
sort(arr, arr + 5, greater<int>()); // Descending order
// arr is now {9, 5, 3, 2, 1}
```
**Custom Comparator Example**:
```cpp
bool cmp(int a, int b) { return a > b; } // For descending
sort(arr, arr + 5, cmp);
```
- **stable_sort(first, last)** / **stable_sort(first, last, comp)**
- Like `sort`, but preserves the relative order of equal elements.
- **Example**:
```cpp
pair<int, int> arr[3] = {{1, 2}, {1, 1}, {2, 3}};
stable_sort(arr, arr + 3, [](pair<int, int> a, pair<int, int> b) {
return a.first < b.first;
});
// arr is now {{1, 2}, {1, 1}, {2, 3}} (order of {1, 2} and {1, 1}
preserved)
```
#### **2. Searching Functions**
These functions help find elements in a range.
- **binary_search(first, last, value)**
- Checks if `value` exists in a **sorted** range `[first, last)`. Returns
`true`/`false`.
- **Usage**: `binary_search(arr.begin(), arr.end(), val);`
- **Example**:
```cpp
int arr[5] = {1, 2, 3, 5, 9};
bool found = binary_search(arr, arr + 5, 3); // true
found = binary_search(arr, arr + 5, 4); // false
```
- **lower_bound(first, last, value)**
- Returns an iterator to the first element **not less than** `value` in a
sorted range.
- **Usage**: `lower_bound(arr.begin(), arr.end(), val);`
- **Example**:
```cpp
int arr[5] = {1, 2, 2, 4, 5};
auto it = lower_bound(arr, arr + 5, 2); // Points to arr[1] (first 2)
int pos = it - arr; // pos = 1
```
- **upper_bound(first, last, value)**
- Returns an iterator to the first element **greater than** `value` in a
sorted range.
- **Usage**: `upper_bound(arr.begin(), arr.end(), val);`
- **Example**:
```cpp
int arr[5] = {1, 2, 2, 4, 5};
auto it = upper_bound(arr, arr + 5, 2); // Points to arr[3] (4)
int pos = it - arr; // pos = 3
```
- **find(first, last, value)**
- Returns an iterator to the first occurrence of `value` in `[first, last)`.
Returns `last` if not found.
- Works on unsorted ranges.
- **Usage**: `find(arr.begin(), arr.end(), val);`
- **Example**:
```cpp
int arr[5] = {5, 2, 9, 1, 3};
auto it = find(arr, arr + 5, 9); // Points to arr[2]
if (it != arr + 5) cout << "Found at index: " << (it - arr); // 2
```
#### **3. Min/Max Functions**
Find minimum or maximum elements.
- **min(a, b)** / **max(a, b)**
- Returns the smaller/larger of two values.
- **Example**:
```cpp
int x = min(5, 3); // 3
int y = max(5, 3); // 5
```
- **min_element(first, last)** / **max_element(first, last)**
- Returns an iterator to the smallest/largest element in `[first, last)`.
- **Example**:
```cpp
int arr[5] = {5, 2, 9, 1, 3};
auto min_it = min_element(arr, arr + 5); // Points to 1
auto max_it = max_element(arr, arr + 5); // Points to 9
cout << *min_it << " " << *max_it; // 1 9
```
#### **4. Container Manipulation**
Functions to modify or analyze ranges.
- **reverse(first, last)**
- Reverses the order of elements in `[first, last)`.
- **Example**:
```cpp
int arr[5] = {1, 2, 3, 4, 5};
reverse(arr, arr + 5);
// arr is now {5, 4, 3, 2, 1}
```
- **swap(a, b)**
- Swaps two values.
- **Example**:
```cpp
int a = 5, b = 3;
swap(a, b);
// a = 3, b = 5
```
- **fill(first, last, value)**
- Assigns `value` to all elements in `[first, last)`.
- **Example**:
```cpp
int arr[5];
fill(arr, arr + 5, 7);
// arr is now {7, 7, 7, 7, 7}
```
- **count(first, last, value)**
- Counts occurrences of `value` in `[first, last)`.
- **Example**:
```cpp
int arr[5] = {2, 2, 3, 2, 5};
int cnt = count(arr, arr + 5, 2); // 3 (three 2's)
```
- **unique(first, last)**
- Removes consecutive duplicates in a **sorted** range. Returns an
iterator to the new end.
- **Example**:
```cpp
int arr[6] = {1, 2, 2, 3, 3, 3};
auto new_end = unique(arr, arr + 6); // arr becomes {1, 2, 3, ?, ?, ?}
int new_size = new_end - arr; // 3
```
#### **5. Permutations**
Generate permutations of a range.
- **next_permutation(first, last)**
- Rearranges the range into the next lexicographically greater
permutation. Returns `false` if no such permutation exists.
- Range must be sorted initially to get all permutations.
- **Example**:
```cpp
int arr[3] = {1, 2, 3};
do {
cout << arr[0] << arr[1] << arr[2] << " ";
} while (next_permutation(arr, arr + 3));
// Output: 123 132 213 231 312 321
```
- **prev_permutation(first, last)**
- Rearranges into the previous lexicographically smaller permutation.
- **Example**:
```cpp
int arr[3] = {3, 2, 1};
do {
cout << arr[0] << arr[1] << arr[2] << " ";
} while (prev_permutation(arr, arr + 3));
// Output: 321 312 231 213 132 123
```
#### **6. Set Operations (on Sorted Ranges)**
These work on sorted ranges and are useful for problems involving sets.
- **set_union(first1, last1, first2, last2, result)**
- Computes the union of two sorted ranges and stores the result in
`result`.
- **Example**:
```cpp
int a[3] = {1, 2, 3}, b[3] = {2, 3, 4};
int res[5];
auto end = set_union(a, a + 3, b, b + 3, res);
// res contains {1, 2, 3, 4}, size = 4
```
- **set_intersection(first1, last1, first2, last2, result)**
- Computes the intersection of two sorted ranges.
- **Example**:
```cpp
int a[3] = {1, 2, 3}, b[3] = {2, 3, 4};
int res[3];
auto end = set_intersection(a, a + 3, b, b + 3, res);
// res contains {2, 3}, size = 2
```
#### **7. Heap Operations**
Turn a range into a heap (useful for priority queues).
- **make_heap(first, last)**
- Converts the range into a max-heap.
- **Example**:
```cpp
int arr[5] = {3, 1, 4, 1, 5};
make_heap(arr, arr + 5); // arr becomes a max-heap: {5, 1, 4, 1, 3}
```
- **push_heap(first, last)** / **pop_heap(first, last)**
- Add/remove an element to/from the heap.
- **Example**:
```cpp
int arr[5] = {5, 1, 4, 1, 3};
pop_heap(arr, arr + 5); // Moves largest (5) to end: {4, 1, 3, 1, 5}
```
---
### Tips for Exam
- **Iterators**: Most functions work with iterators (`begin()`, `end()` for
containers; `arr`, `arr + n` for arrays).
- **Sorting First**: Functions like `binary_search`, `lower_bound`,
`upper_bound`, `unique`, and set operations require the range to be
sorted.
- **Custom Comparators**: Use for custom sorting (e.g., `sort(arr, arr + n,
greater<int>())` for descending).
- **Vectors vs. Arrays**: Examples above use arrays, but replace `arr, arr
+ n` with `v.begin(), v.end()` for vectors.
This cheat sheet covers the essentials of the `<algorithm>` library for a
CS exam. Practice these examples to get comfortable with the syntax and
behavior! Good luck on your exam!
