B0

<algorithm> quiz

• Implement in-place function rotating supplied sequence to the left, having following interface:

template<typename It>
void rotate(It first, It new_first, It last);
/* first        -- iterator pointing to the first element */
/* new_first    -- iterator pointing to the element, that should become first after rotation is finished */
/* last         -- iterator pointing past the last element */

• Implement Insertion Sort without loops, using only utilitiies provided by STL.

• Implement sliding procedure which allows you to move given range around the whole sequence (like dragging UI along the line)

template <typename _RanIt> 
_RanIt slide(_RanIt first, _RanIt last, _RanIt pivot)
/* first        -- iterator pointing to the first element */

/* last         -- iterator pointing past the last element */
/* pivot        -- iterator pointing to the element, where first element of the supplied subsequence should arrive at */

• Implement gathering procedure which can be seen similar to the previous slide procedure: it gathers all elements in the given range for which supplied `predicate` value returns true and slides them towards the target position designated by the pivot iterator

template <typename _BiIt, typename UnPred> 
_BiIt gather(_BiIt first, _BiIt last, _BiIt pivot, UnPred pred)

/* first        -- iterator pointing to the first element */

/* last         -- iterator pointing past the last element */
/* pivot        -- iterator pointing to the element, where first element of the supplied subsequence should arrive at */
/* pred         -- predicate selecting which elements should be gathered */

• Implement QuickSort without loops, using only utilitiies provided by STL.

Hint: following utilities may be especially helpful for the described tasks: `std::rotate`, `std::upper_bound`, `std::next`, `std::nth_element`