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