lower_bound and upper_bound are built-in binary search functions.
lower_bound - a function that, in logarithmic time, finds the smallest element in a sorted array that is greater than or equal to the given value k.
It takes the bounds of the array and the value of k as arguments.
Returns an iterator to the found element, or to the end (not included) of the array if no such element exists.
You can read more in the documentation.
upper_bound - a function that in logarithmic time in a sorted array finds the smallest element that is strictly greater than the given value k.
It takes the bounds of the array and the value of k as arguments.
Returns an iterator to the found element, or to the end (not included) of the array if no such element exists.
You can read more in documentation.
It is worth clarifying that the use of these functions on a set or multiset does not work in logarithmic time due to the lack of iterators in the above random access collections.
However, these collections have corresponding built-in methods (that is, you need to use them "through a dot").
Examples:
vector a = { 0, 1, 3, 5, 7 };
vector::iterator it;
it = lower_bound(a.begin(), a.end(), 4);
// *it == 5
it = lower_bound(a.begin(), a.end(), 5);
// *it == 5
it = lower_bound(a.begin(), a.end(), 8);
// it == a.end()
it = upper_bound(a.begin(), a.end(), 4);
// *it == 5
it = upper_bound(a.begin(), a.end(), 5);
// *it == 7
it = upper_bound(a.begin(), a.end(), -1);
// *it == 0
// by subtracting iterators, you can get the index of the found element
int ind = lower_bound(a.begin(), a.end(), 4) - a.begin();
// ind == 3
// need to use methods instead of functions for set and similar collections
set s{ 1, 3, 5 };
set::iterator sit;
sit = s.lower_bound(3);
// *sit == 3
sit = s.upper_bound(3);
// *sit == 5
|
unique - a function that compresses all sequences of identical consecutive elements into one in linear time.
As an argument, it is passed the boundaries of the array, within which it is necessary to apply compression.
An iterator is returned to the new end (not inclusive) of the array. You should be careful with elements after the new end but before the old one, as they will have an undefined value.
You can read more in documentation.
If you're using this function on a vector, it's convenient to resize using the returned result (more on that below).
Examples:
vector a = { 3, 3, 3, 2, 3, 3, 1, 1, 4, 5, 5 };
unique(a.begin(), a.end());
// a = [3, 2, 3, 1, 4, 5, ?, ?, ?, ?, ?]
// using the unique function is convenient to do
// auxiliary array for coordinate compression
a = { 235, 10, 41, 10, 41, 41, 235, 500, 500 };
sort(a.begin(), a.end());
// a = [10, 10, 41, 41, 41, 235, 235, 500, 500]
a.resize(unique(a.begin(), a.end()) - a.begin());
// a = [10, 41, 235, 500]
|
merge - a function that merges two sorted arrays, namely, in linear time it gets a sorted array, which consists of the elements of the first and second array.
It takes 5 arguments: two bounds for each array and the left bound of the destination (where the elements of the resulting array will be placed).
More details can be found in the documentation.
Examples:
// source arrays must be sorted
vector a = { 1, 3, 5, 7 };
vector b = { 2, 4, 6 };
// need destination to be large enough
vector c(7);
merge(a.begin(), a.end(), b.begin(), b.end(), c.begin());
// c = [1, 2, 3, 4, 5, 6, 7]
// elements can be repeated
a = {1, 2, 4, 4};
b = { 2, 3, 3, 3, 4, 4 };
c.resize(10);
merge(a.begin(), a.end(), b.begin(), b.end(), c.begin());
// c = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]
This function is very useful in the context of merge sort.
|
nth_element is a function that allows you to find the nth element in an array in sorted order in linear time.
The function takes the left end of the array, an iterator to the position whose value in sorted order is to be found, and the right end of the array.
After applying the function, the required value will be located at the place indicated by the iterator, while the remaining values will acquire a chaotic order, but to the left of the nth there will be values no more than it, and to the right no less. That is, it should be understood that this function destroys the original order of the elements.
You can read more in the documentation (https://www.cplusplus.com/reference/algorithm/nth_element/).
Example:
vector a = { 4, 0, 3, 9, 2, 1, 8, 5, 6, 7 };
// look for element at index 4
// pay attention to the order of the arguments
nth_element(a.begin(), a.begin() + 4, a.end());
// a = [#, #, #, #, 4, $, $, $, $, $]
// where # <= 4 and 4 <= $
|
A permutation of length n is an ordered collection without repetitions of the numbers 1, 2, ..., n. For example, [3, 1, 2] and [5, 4, 3, 2, 1] are permutations, but [1, 2, 1, 3] and [1, 2, 4] are not.
If the task is reduced to the fact that it is necessary to iterate over all permutations of length n, then you can use a convenient mechanism in C ++, which is called "next_permutation".
You can read more about it in documentation, but the point is that this function changes the passed array to subsequent permutation in lexicographic order (which is generally clear and its name).
To use next_permutation, you need to include the algorithm library (i.e. write #include <algorithm> at the beginning of the program)
Examples:
vector arr;
arr = { 1, 2, 3 }; // array is [1, 2, 3]
next_permutation(arr.begin(), arr.end()); // pass the entire array to the function
// array is now [1, 3, 2]
arr = { 2, 3, 1 }; // array is [2, 3, 1]
next_permutation(arr.begin(), arr.end()); // pass the entire array to the function
// array is now [3, 1, 2]
next_permutation(arr.begin() + 1, arr.begin() + 3); // it is possible to apply a function to a part of an array, but in practice this is rarely needed
// array is now [3, 2, 1]
In this case, the function has a boolean return value that is true if the next permutation was generated and false if there was no next one (the case when the maximum permutation in lexicographic order is passed to the function).
This makes it possible to use the function in a loop, which will allow us to iterate over all permutations at once. Due to 0-indexing, in practice it is often more convenient to work with a permutation of numbers from 0 to n - 1, although a permutation formally contains numbers from 1 to n. But fortunately, this does not lead to additional overlays in the code, because the next_permutation function is adapted to 0-indexed permutations (and even duplicate elements in an array, but you can find out more on your own).
In general, the code for iterating over all permutations looks like this:
intn; // permutation size
vectorperm(n); // perm is short for "permutation", i.e. "permutation"
for (int i = 0; i < n; i++)
perm[i] = i; // initialize initial permutation 0, 1, ..., n - 1
do {
// inside the loop we process the current permutation
} while (next_permutation(perm.begin(), perm.end())); // if there is no next permutation, then end the loop
This code runs in O(n! * f(n)), where f(n) is the time it takes you to process one particular permutation.
|