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

Материал из SEWiki
Перейти к: навигация, поиск
(Новая страница: «== Осенний Семестр == TBD == Весенний Семестр == === #2 Vector === ==== Part One ==== Implement vector-alike container matching…»)
 
 
(не показано 17 промежуточных версий этого же участника)
Строка 1: Строка 1:
== Осенний Семестр ==
+
= Осенний Семестр =
  
 
TBD
 
TBD
  
== Весенний Семестр ==
+
= Весенний Семестр =
  
=== #2 Vector ===
+
== #2 Vector ==
  
 
==== Part One ====
 
==== Part One ====
Строка 19: Строка 19:
 
* ''resize''
 
* ''resize''
 
* ''back''
 
* ''back''
 +
* ''size''
 
* ''begin/rbegin''
 
* ''begin/rbegin''
 
* ''end/rend''
 
* ''end/rend''
Строка 27: Строка 28:
  
 
Implement '''specialization''' of already implemented (template-) container for the simple type `'''bool'''` being ''as compact as possible''.
 
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 ([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 */
 +
</source>
 +
 +
* Implement [http://en.wikipedia.org/wiki/Insertion_sort 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]]
 +
 +
<source lang="cpp">
 +
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 */
 +
</source>
 +
 +
* 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]]
 +
 +
<source lang="cpp">
 +
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 */
 +
</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`
 +
 +
 +
 +
== make_shared ==
 +
 +
Implement `make_shared` utility having signature:
 +
 +
<source lang=cpp>
 +
template<typename T>
 +
std::shared_ptr<T> make_shared(/* ? */);
 +
</source>
 +
 +
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:
 +
 +
<source lang=cpp>
 +
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&);
 +
}
 +
 +
</source>
 +
 +
 +
== inherit ==
 +
 +
<source lang=cpp>
 +
 +
#include <iostream>
 +
 +
 +
struct NIL {};
 +
 +
template<class H, class T = NIL>
 +
  struct cons {
 +
    typedef T tail_type;
 +
    typedef H head_type;
 +
  };
 +
 +
template<class L>
 +
  struct inherit : L::head_type, inherit<typename L::tail_type> {};
 +
 +
template<> struct inherit<NIL> {};
 +
 +
 +
struct A {
 +
  void foo() { std::cout << "class A::foo\n"; }
 +
};
 +
 +
struct B {
 +
  void foo() { std::cout << "class B::foo\n"; }
 +
};
 +
 +
struct C {
 +
  void foo() { std::cout << "class C::foo\n"; }
 +
};
 +
 +
typedef cons< A, cons< B, cons< C > > > A_B_C;
 +
 +
template<typename T>
 +
struct D : inherit<T> {
 +
 +
  void foo() {
 +
    /* ? */
 +
  }
 +
 +
};
 +
 +
 +
int main(int ARGC, char *ARGV[]) {
 +
 +
  D<A_B_C> d;
 +
 +
  d.foo();
 +
 +
  return 0;   
 +
}
 +
</source>

Текущая версия на 12:07, 15 мая 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)

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`


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&);
}


inherit

#include <iostream>


struct NIL {};

template<class H, class T = NIL>
  struct cons {
    typedef T tail_type;
    typedef H head_type;
  };

template<class L>
  struct inherit : L::head_type, inherit<typename L::tail_type> {};

template<> struct inherit<NIL> {};


struct A {
  void foo() { std::cout << "class A::foo\n"; } 
};

struct B {
  void foo() { std::cout << "class B::foo\n"; } 
};

struct C {
  void foo() { std::cout << "class C::foo\n"; } 
};

typedef cons< A, cons< B, cons< C > > > A_B_C;

template<typename T>
struct D : inherit<T> {

  void foo() {
    /* ? */
  }
 
};


int main(int ARGC, char *ARGV[]) {

  D<A_B_C> d;

  d.foo();

  return 0;    
}