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

Материал из SEWiki
Перейти к: навигация, поиск
(→‎Весенний Семестр)
Строка 1: Строка 1:
−
= Осенний Семестр =
+
== <algorithm> quiz ==
  
−
TBD
+
* Implement ''in-place'' function ''rotating'' supplied sequence to the left, having following interface:
  
−
= Весенний Семестр =
+
<source lang="cpp">
 +
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 */
 +
</source>
  
−
== #2 Vector ==
+
* Implement [http://en.wikipedia.org/wiki/Insertion_sort Insertion Sort] '''without''' loops, using only utilitiies provided by STL.
  
−
==== Part One ====
+
* Implement ''sliding'' procedure which allows you to move given range around the whole sequence (like dragging UI along the line)
  
−
Implement vector-alike container matching performance requirements of the `std::vector`.
+
[[Файл:Stdbea slide.png]]
  
−
It should contain implementation for the following methods matching behaviour of the ones of `std::vector`:
+
<source lang="cpp">
 +
template <typename _RanIt>
 +
_RanIt slide(_RanIt first, _RanIt last, _RanIt pivot)
 +
/* first        -- iterator pointing to the first element */
  
−
* ''push_back''
+
/* last        -- iterator pointing past the last element */
−
* ''pop_back''
+
/* pivot        -- iterator pointing to the element, where first element of the supplied subsequence should arrive at */
−
* ''insert''
+
</source>
−
* ''clear''
+
−
* ''resize''
+
−
* ''back''
+
−
* ''size''
+
−
* ''begin/rbegin''
+
−
* ''end/rend''
+
  
−
As a reference consider [http://en.cppreference.com/w/cpp/container/vector en.cppreference.com].
+
* 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
  
−
==== Part Two ====
+
[[Файл:Stdbea gather.png]]
  
−
Implement '''specialization''' of already implemented (template-) container for the simple type `'''bool'''` being ''as compact as possible''.
+
<source lang="cpp">
 +
template <typename _BiIt, typename UnPred>
 +
_BiIt gather(_BiIt first, _BiIt last, _BiIt pivot, UnPred pred)
  
−
== #3 Throwing Vector ==
+
/* first        -- iterator pointing to the first element */
  
−
Now you've got an insight what the C++ exceptions are, implement all error handling inside your implementation of the `vector`, relying ''solely'' upon the exceptions mechanism.
 
−
 
−
That means: no more `_Exit`s, `abort`s, etc. Exceptions '''only'''.
 
−
 
−
== #4 Deque ==
 
−
 
−
Implement double-ended queue matching interface of thereof inside STL ([http://en.cppreference.com/w/cpp/container/deque std::deque]) and ''matching'' its performance requirements.
 
−
 
−
At the very least, it should contain following members:
 
−
 
−
* ''push_back''
 
−
* ''pop_back''
 
−
* ''push_front''
 
−
* ''pop_front''
 
−
* ''insert''
 
−
* ''clear''
 
−
* ''resize''
 
−
* ''back''
 
−
* ''front''
 
−
* ''size''
 
−
* ''begin/rbegin''
 
−
* ''end/rend''
 
−
 
−
'''NB''': Implementing deque matching performance requirements of the STL one, try to minimize ''unused'' memory 'committed' by your implementation.
 
−
 
−
If you consider that it's impossible, be ready to assure your point.
 
−
 
−
== #5 Exceptions Guarantees ==
 
−
 
−
==== Main ====
 
−
 
−
Reconsider your own `vector` implementation towards making it ''[http://en.wikipedia.org/wiki/Exception_safety exception-safe]''.
 
−
 
−
Following members of your `vector` implementation should be reconsidered to match corresponding ''[http://en.wikipedia.org/wiki/Exception_safety exception-safety guarantees]'':
 
−
 
−
* '''operator=''' / strong
 
−
* '''push_back''' / strong
 
−
 
−
==== Extra ====
 
−
 
−
Try match your implementation on the functions predefined inside STL.
 
−
 
−
Try to reduce boilerplate inside your implementation relying on the standard-library defined functions.
 
−
 
−
''Hint'': see [http://en.cppreference.com/w/cpp/header/memory memory] header closely.
 
−
 
−
== <algorithm> quiz ==
 
−
 
−
* Implement ''in-place'' function ''rotating'' supplied sequence to the left, having following interface:
 
−
 
−
<source lang="cpp">
 
−
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 */
 
/* 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 */
 
</source>
 
</source>
−
 
−
* Implement [http://en.wikipedia.org/wiki/Insertion_sort Insertion Sort] '''without''' loops, using only utilitiies provided by STL.
 
−
 
−
* TBD
 

Версия 02:30, 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 */
Источник — «http://mit.spbau.ru/sewiki/index.php?title=B0&oldid=5765»