B0 — различия между версиями

Материал из SEWiki
Перейти к: навигация, поиск
(quiz)
Строка 40: Строка 40:
 
/* pred        -- predicate selecting which elements should be gathered */
 
/* pred        -- predicate selecting which elements should be gathered */
 
</source>
 
</source>
 +
 +
* Implement [http://en.wikipedia.org/wiki/Quicksort 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`

Версия 02:32, 31 марта 2015

<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)

Stdbea slide.png

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

Stdbea gather.png

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`