algorithm

The <algorithm> header in C++20 includes a wide range of functions that are essential for various operations on containers like arrays, lists, and vectors. Some of the key components and functions included in this header are:

Non-modifying Sequence Operations:
- std::for_each: Apply a function to a range of elements.
- std::count and std::count_if: Count elements in a range.
- std::find, std::find_if, and std::find_if_not: Find elements in a range.
- std::search: Search for a subsequence in a range.
Modifying Sequence Operations:
- std::copy, std::copy_if, std::copy_n, and std::copy_backward: Copy elements.
- std::move and std::move_backward: Move elements.
- std::fill and std::fill_n: Assign a value to a range of elements.
- std::transform: Apply a function and store the result.
- std::replace, std::replace_if: Replace values in a range.
- std::swap_ranges: Swap ranges of elements.
Partitioning Operations:
- std::partition: Reorder elements in a range so that they satisfy a predicate.
- std::stable_partition: Stable version of std::partition.
- std::partition_copy: Copy elements that satisfy a predicate into another range.
- std::partition_point: Find the partition point.
Sorting Operations:
- std::sort: Sort elements in a range.
- std::stable_sort: Stable sort elements.
- std::partial_sort: Partially sort elements in a range, up to the K'th element.
```
  int Kth = 4;
  std::vector<int> arr = {5, 812, 4, 74, 68, 7, 48, 45};
  std::partial_sort(arr.begin(), arr.begin() + Kth, arr.end());
```
- std::partial_sort_copy: Copies elements from an input range to an output range, Simultaneously sorts the elements copied to the output range. Only the first n elements of the output range are guaranteed to be sorted. is efficient for finding a specific number of smallest or largest elements without sorting the entire input range.
```
  int Kth = 4;
  std::vector<int> numbers = {64, 25, 12, 22, 11, 90};
  std::vector<int> result(Kth); // We want the 4 smallest elements

  std::partial_sort_copy(numbers.begin(), numbers.end(), result.begin(),result.end());
```
- std::nth_element algorithm partially sorts a range so that the element at the position pointed to by the middle iterator is the same as it would be if the entire range was sorted. The elements before the middle iterator are less than or equal to the middle element, and the elements after it are greater than or equal to the middle element.
```
std::vector<int> numbers = {3, 7, 4, 9, 2, 5, 8, 1, 6};
auto middle = numbers.begin() + numbers.size() / 2;
std::nth_element(numbers.begin(), middle, numbers.end());
```
In this case, std::nth_element rearranges the vector such that the element at the middle position is the same as it would be in a sorted array. The elements before middle are less than or equal to the element at middle, and the elements after it are greater than or equal to it.

After executing this code, you got:
```
3 2 1 4 5 6 8 9 7
```
Here, the middle element (numbers[4] or 5 in a zero-indexed vector) is placed at its correct position if the vector were fully sorted, but the other elements around it are not fully sorted.
```
std::nth_element(numbers.begin(), middle, numbers.end(), std::greater_equal<int>());
```
In this example, std::greater_equal<int>() is used as the comparison function, which means that the elements are arranged in a way that the middle element is the same as it would be in a reverse-sorted array.

After executing this code, you got:
```
6 7 8 9 5 4 2 1 3
```
Here, the middle element (5) is correctly placed as it would be in a reverse-sorted array, with the elements before it greater than or equal to it and the elements after it less than or equal to it.
- std::priority_queue: use heap for finding max/min value
```
	std::priority_queue<int, std::vector<int>, std::greater<int>> q2;
	for (int n : {1, 8, 5, 6, 3, 4, 0, 9, 7, 2})
		q2.push(n);
		
```
using custom_comparator:
```
    	
	  auto comparator = [](int left, int right) {
	    return (left ^ 1) < (right ^ 1);
	  };

	  std::priority_queue<int, std::vector<int>, decltype(comparator)>
	      q_custom_comparator(comparator);
	  for (int n : {1, 8, 5, 6, 3, 4, 0, 9, 7, 2})
	    q_custom_comparator.push(n);
```
Here decltype is used to deduce the type of the comparator function (the lambda) so that it can be used as the third template argument when defining the

Why decltype is Needed:
1. Lambda Functions Have Unique Types:
  - Lambda functions in C++ have unique, unnamed types generated by the compiler. These types are not directly accessible by name, so you cannot simply specify the type of the lambda in the template parameters of std::priority_queue.
2. Specifying the Comparator Type:
  - The std::priority_queue requires the type of the comparator as its third template argument to define how the elements should be ordered. Since the type of a lambda is unnamed and complex, decltype is used to deduce and retrieve this type.
How decltype Works Here:
- decltype(comparator):
  - decltype is used to deduce the exact type of the comparator lambda function. This allows std::priority_queue to know the type of the comparator it should use.
- Initialization:
  - When you initialize the std::priority_queue, you need to pass the comparator to its constructor so that it knows how to compare the elements.
  - Using decltype(comparator) allows the std::priority_queue to correctly store and use the lambda for comparison.
using custom struct:
```
// Define the cell struct
struct cell {
    int index;
    float cost;
};

// Define a custom comparison functor
struct CompareCell {
    bool operator()(const cell &a, const cell &b) {
	return a.cost > b.cost; // Min-heap: smallest cost has highest priority
    }
};
```
In your main:
- The first parameter is the type of elements stored (cell).
- The second parameter is the underlying container type (std::vector).
- The third parameter is the comparison functor (CompareCell).
```
  std::priority_queue<cell, std::vector<cell>, CompareCell> pq;
```
Binary Search Operations (on sorted ranges):
- std::lower_bound and std::upper_bound: Find bounds in a sorted range.
- std::binary_search: Test if a value exists in a sorted sequence.
- std::equal_range: Get the range of equal elements.
Set Operations (on sorted ranges):
- std::merge: Merge two sorted ranges.
- std::set_union, std::set_intersection, std::set_difference, std::set_symmetric_difference: Perform set operations.

Heap Operations:

std::make_heap

std::vector<int> v = {6, 10, 7, 17, 10, 15};
// min heap
std::make_heap(v.begin(), v.end(), std::greater_equal());

// max heap (default one)
 // std::make_heap(v.begin(), v.end(), std::less_equal());
std::make_heap(v.begin(), v.end());

std::cout << "The maximum element of heap is: "<< v.front();

std::pop_heap remove the largest element from max heap

// put the max is at the bottom of the array
std::pop_heap(v.begin(), v.end());
// removing it
v.pop_back();

std::push_heap: Inserts the element at the position last - 1 into the heap

 // Adding a new element to the end of array
  v.push_back(100);
  std::cout << (std::is_heap(v.begin(), v.end()) ? "it is a heap" : "it is not a heap")<< std::endl;

  std::push_heap(v.begin(), v.end());
  std::cout << (std::is_heap(v.begin(), v.end()) ? "it is a heap" : "it is not a heap")<< std::endl;

std::sort_heap: converts the heap into a sorted range. The heap property is no longer maintained.

Min/Max Operations:
- std::min, std::max, std::minmax: Find minimum, maximum, and both.
- std::min_element, std::max_element, std::minmax_element: Find elements.
Comparison Operations:
- std::lexicographical_compare: Compare sequences.
- std::equal: Test if two ranges are equal.
Permutation and Shuffle Operations:
- std::next_permutation, std::prev_permutation: Generate permutations,
- std::random_shuffle, std::shuffle: Reorders the elements such that each possible permutation of those elements has equal probability of appearance.
Numeric Operations:
- std::iota: Fill a range with successive increments of a start value.
- std::accumulate: Sum up elements.
- std::inner_product: Compute the inner product of two ranges.
- std::adjacent_difference: Compute the difference between adjacent elements.
- std::reduce, std::transform_reduce, std::inclusive_scan, std::exclusive_scan: Parallel versions of numeric operations (C++17 and above).
Other Operations:
- std::ranges::sort, std::ranges::copy: Range versions of algorithm functions (C++20).

std::ranges::transform

std::ranges::transform is a function in C++20 that applies a given function to each element in a range and stores the result in another range. It's part of the Ranges library, which provides a more modern and flexible way to work with sequences of data.

Here's a basic explanation and some examples:

Explanation

Function: std::ranges::transform(InputRange, OutputIterator, UnaryOperation)
Parameters:
- InputRange: The range of elements to transform.
- OutputIterator: Where to store the results of the transformation.
- UnaryOperation: A function or function object that will be applied to each element in the input range.

Example 1: Simple Transformation

#include <iostream>
#include <vector>
#include <ranges>

int main() {
    std::vector<int> input = {1, 2, 3, 4};
    std::vector<int> output(input.size());

    std::ranges::transform(input, output.begin(), [](int x) { return x * x; });

    for (int val : output) {
        std::cout << val << ' ';
    }
}

In this example, each element of input is squared and stored in output.

Example 2: Using Different Input and Output Types

#include <iostream>
#include <string>
#include <vector>
#include <ranges>

int main() {
    std::vector<std::string> input = {"Hello", "World"};
    std::vector<size_t> output(input.size());

    std::ranges::transform(input, output.begin(), [](const std::string& s) { return s.size(); });

    for (auto val : output) {
        std::cout << val << ' ';
    }
}

Here, std::ranges::transform calculates the length of each string in input and stores it in output.

Example 3: In-Place Transformation

#include <iostream>
#include <vector>
#include <ranges>

int main() {
    std::vector<int> data = {1, 2, 3, 4};

    std::ranges::transform(data, data.begin(), [](int x) { return x + 10; });

    for (int val : data) {
        std::cout << val << ' ';
    }
}

In this example, each element in data is increased by 10. The transformation is done in-place.

Notes

std::ranges::transform is a more flexible and "range-aware" version of the traditional std::transform.
It works well with the new range-based for loops and other range utilities in C++20.

std::back_inserter

std::back_inserter is a convenient way to append elements to a container that supports push back operations, such as std::vector, std::list, etc. When used with std::ranges::transform, it allows you to transform elements from one range and automatically append the results to another container.

Here's an example demonstrating how you can use std::ranges::transform with std::back_inserter:

Example: Transform with Back Inserter

#include <iostream>
#include <vector>
#include <ranges>
#include <iterator> // For std::back_inserter

int main() {
    std::vector<int> input = {1, 2, 3, 4};
    std::vector<int> output; // Notice, we don't need to pre-size the output vector

    // Apply transformation and append results to 'output'
    std::ranges::transform(input, std::back_inserter(output), [](int x) { return x * 2; });

    // Print the transformed output
    for (int val : output) {
        std::cout << val << ' ';
    }
}

Explanation:

std::vector<int> output;: Initially, output is an empty vector.
std::ranges::transform(..., std::back_inserter(output), ...);: For each element in input, the lambda function is applied, and the result is appended to the end of output.
The lambda function here simply multiplies each element by 2.
Printing the Results: The transformed elements in output are then printed.

This approach is particularly useful when you don't know the size of the output container in advance or when you want to append the transformed elements to an existing container.

code

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

algorithms.md

algorithms.md

algorithm

Why `decltype` is Needed:

How `decltype` Works Here:

std::ranges::transform

Explanation

Example 1: Simple Transformation

Example 2: Using Different Input and Output Types

Example 3: In-Place Transformation

Notes

std::back_inserter

Example: Transform with Back Inserter

Explanation:

Files

algorithms.md

Latest commit

History

algorithms.md

File metadata and controls

algorithm

Why decltype is Needed:

How decltype Works Here:

std::ranges::transform

Explanation

Example 1: Simple Transformation

Example 2: Using Different Input and Output Types

Example 3: In-Place Transformation

Notes

std::back_inserter

Example: Transform with Back Inserter

Explanation:

Why `decltype` is Needed:

How `decltype` Works Here: