Functions | |
template<typename IT , typename IsEqual > | |
int | BinarySearch (const IT &begin, const IT &end, const typename std::iterator_traits< IT >::value_type &key) |
template<typename IT , typename Compare = std::less_equal<typename std::iterator_traits<IT>::value_type>> | |
IT | MaxKthElement (const IT &begin, const IT &end, unsigned int k) |
template<typename IT , typename Distance = std::minus<typename std::iterator_traits<IT>::value_type>> | |
std::pair< int, int > | MaxDistance (const IT &begin, const IT &end) |
template<typename Container , typename IT , typename Compare = std::greater_equal<typename std::iterator_traits<IT>::value_type>> | |
Container | MaxMElements (const IT &begin, const IT &end, const int m) |
template<typename IT , typename Distance = std::minus<typename std::iterator_traits<IT>::value_type>, typename Compare = std::greater<typename std::iterator_traits<IT>::value_type>> | |
std::pair< int, int > | MaxSubSequence (const IT &begin, const IT &end) |
Function Documentation
int SHA_Search::BinarySearch | ( | const IT & | begin, |
const IT & | end, | ||
const typename std::iterator_traits< IT >::value_type & | key | ||
) |
Binary Search Iteratively proceed a dichotomic search within a sorted collection on the first occurence of the key passed as parameter.
- Complexity
- O(log(N)).
- Template Parameters
-
IT type using to go through the collection.
- Parameters
-
begin,end iterators to the initial and final positions of the sequence to be sorted. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last. key the key value to be searched.
- Returns
- The vector index of the first found key, -1 otherwise.
Definition at line 43 of file binary.hxx.
std::pair<int, int> SHA_Search::MaxDistance | ( | const IT & | begin, |
const IT & | end | ||
) |
MaxDistance Identifies the two indexes of the array with the maximal distance.
Known as the simple stock market problem with the default functor (std::minus): It finds i and j that maximizes Aj - Ai, where i < j. In other words, maximizes the benefice of a resell given an array of prices varying over time.
- Complexity
- O(N * O(f(a, b))), with f(a,b) the functor used; is O(1) for the default std::minus.
- Template Parameters
-
Iterator type using to go through the collection. Distance functor type computing the distance between two elements.
- Parameters
-
begin,end iterators to the initial and final positions of the sequence to be sorted. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
- Returns
- indexes of the array with the maximal distance, <-1,-1> in case of error.
- Todo:
- return iterators instead.
Definition at line 48 of file max_distance.hxx.
IT SHA_Search::MaxKthElement | ( | const IT & | begin, |
const IT & | end, | ||
unsigned int | k | ||
) |
Kth Smallest / Biggest element - Order Statitstics Find the kth smallest/biggest element contained within [begin, end[.
- Warning
- this method is not stable (does not keep order with element of the same value).
- this method changes the elements order between your iterators.
- Complexity
- recursively look on the choosen partition: N + N/2 + N/4 + N/8 + ... = O(N).
- Template Parameters
-
IT Random-access iterator type. Compare functor type (std::less_equal to find kth smallest element, std::greater_equal to find the kth biggest one).
- Parameters
-
begin,end - ITs to the initial and final positions of the sequence to be sorted. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last. k the zero-based kth element - 0 for the biggest/smallest.
- Returns
- the kth smallest IT element of the array, the end IT in case of failure.
Definition at line 50 of file kth_max_element.hxx.
Container SHA_Search::MaxMElements | ( | const IT & | begin, |
const IT & | end, | ||
const int | m | ||
) |
Max M Elements Identify the m maximal/minimal values sorted in decreasing/increasing order.
using this algorithm with the size of the vector as the number of elements to be found will give you a bubble sort algorithm in O(Nē).
- Complexity
- O(N * m * O(f(a, b))) with:
- m number of elements to be looking for
- f(a, b) the compare functor used: O(1) for the default std::greater_equal
- Template Parameters
-
Container type used to return the elements. IT type using to go through the collection. Compare functor type.
- Parameters
-
begin,end iterators to the initial and final positions of the sequence to be sorted. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last. m the numbers of max elements value to be found.
- Returns
- a vector of sorted in decreasing/increasing order of the m maximum/minimum elements, an empty array in case of failure.
Definition at line 53 of file max_m_elements.hxx.
std::pair<int, int> SHA_Search::MaxSubSequence | ( | const IT & | begin, |
const IT & | end | ||
) |
Max Sub Sequence Identify the subarray with the maximum/minimum sum.
The algorithm can be seen as an elicitation of the MaxDistance one. One of the problem resolved by this algorithm is: "Given an array of gains/losses over time, find the period that represents the best/worst cummulative gain." The algorithm uses the fact that the sum operator is a transitive function.
- Complexity
- O(N * (O(f(a, b)) + O(g(a, b))) with:
- f(a, b) the distance functor used; is O(1) for the default std::minus.
- g(a, b) the compare functor used; is O(1) for the default std::greater.
- Template Parameters
-
IT type using to go through the collection. Distance functor type computing the distance between two elements. Compare functor type.
- Parameters
-
begin,end iterators to the initial and final positions of the sequence to be sorted. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
- Returns
- indexes of the array with the maximum/minimum sum, <-1,-1> in case of error.
- Todo:
- return iterators instead.
Definition at line 55 of file max_sub_sequence.hxx.