B0 — различия между версиями
(Новая страница: «== Осенний Семестр == TBD == Весенний Семестр == === #2 Vector === ==== Part One ==== Implement vector-alike container matching…») |
|||
(не показано 17 промежуточных версий этого же участника) | |||
Строка 1: | Строка 1: | ||
− | + | = Осенний Семестр = | |
TBD | TBD | ||
− | + | = Весенний Семестр = | |
− | + | == #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)
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`
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;
}