Версия 23:14, 24 апреля 2015

Осенний Семестр

TBD

Весенний Семестр

#2 Vector

Part One

Implement vector-alike container matching performance requirements of the `std::vector`.

It should contain implementation for the following methods matching behaviour of the ones of `std::vector`:

• push_back
• pop_back
• insert
• clear
• resize
• back
• size
• begin/rbegin
• end/rend

As a reference consider en.cppreference.com.

Part Two

Implement specialization of already implemented (template-) container for the simple type `bool` being as compact as possible.

#3 Throwing Vector

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 (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 exception-safe.

Following members of your `vector` implementation should be reconsidered to match corresponding 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 memory header closely.

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

make_shared

Implement `make_shared` utility having signature:

template<typename T>
std::shared_ptr<T> make_shared(/* ? */);

that accepts single argument and creates an object of type `T` and supplies caller with `shared_ptr` pointing to it.

NB: Your implementation must comply with all of the following tests:

template<typename T>
std::shared_ptr<T> make_shared(/* ? */);

struct Y 
{
    Y(int& a) {}
    Y(const int & a) {}
  
  private:
    Y(const Y&);
};

struct X
{
  X(Y&& a) {}
  X(Y& a) {}
  X(const Y& a) {}
};


int main(int ARGC, char *ARGV[])
{
  auto _1 = make_shared<Y>(Y(0)); // X(Y&&);

  Y y(0);
  auto _2 = make_shared<Y>(y);    // X(Y&);

  const Y cy(1);
  auto _3 = make_shared<X>(cy);   // X(const Y&);
}