Третья группа

Материал из SEWiki
Перейти к: навигация, поиск

Общее

Задания

Компиляция

Сортировка слиянием

Выделение памяти

Расширяющийся массив

Обертка над FILE

String

Smart FILE

Streams

Наследуясь от класса OutputStream реализовать Иерархию классов FileOutputStream, StringOutputStream, ConsoleOutputStream имеющие соответствующую функциональность.

struct OutputStream
{
    virtual void print( std::string const& s ) = 0;

    virtual void print( int t ) 
    {
        char buff[16] = {};
        sprintf(buff, "%d", t);
        print(buff);
    }

    virtual void print( double t ) 
    {
        char buff[16] = {};
        sprintf(buff, "%f", t);
        print(buff);
    }

    virtual void flush() = 0;

    virtual ~OutputStream() {}
};


Rationals


// Rational.h

class Rational {

    Rational & operator+=( Rational const& b );

    Rational & operator-=( Rational const& b );

    Rational & operator/=( Rational const& b );

    Rational & operator*=( Rational const& b );

    Rational operator-() const;

    double to_double() const;

    int nom();
    int den();

};

ostream & operator<<(ostream & os, Rational const& r);
istream & operator>>(istream & is, Rational & r);

Rational  operator+( Rational a, Rational const& b );
Rational  operator-( Rational a, Rational const& b );
Rational  operator/( Rational a, Rational const& b );
Rational  operator*( Rational a, Rational const& b );

bool operator==( Rational const& a, Rational const& b );
bool operator!=( Rational const& a, Rational const& b );
bool operator<( Rational const& a, Rational const& b );
bool operator<=( Rational const& a, Rational const& b );
bool operator>( Rational const& a, Rational const& b );
bool operator>=( Rational const& a, Rational const& b );
~                                                                

Smart-Pointers

scoped_ptr: http://www.boost.org/doc/libs/1_52_0/libs/smart_ptr/scoped_ptr.htm

shared_ptr: http://www.boost.org/doc/libs/1_52_0/libs/smart_ptr/shared_ptr.htm

Array/Bool-Array/Stack

template <class T, size_t Size>
    struct Array
{

    T &      operator[]( size_t i );
    T const& operator[]( size_t i ) const;

    size_t  size() const;
    void resize( size_t size );
    
};

template < class T, size_t Size, template < class, size_t > class Storage >
    struct Stack
{

    T const& top() const;
    T &      top();

    void push(T const& t);

    void pop();

};


Mergesort | Stack/Queue

К выполнению предлагаются любое из двух заданий:

Реализовать процедуру сортировки, основанную на алгоритме merge-sort, принимающую на вход bidirectional (!) итераторы указывающие на начало и окончание сортируемого интервала.

template<typename _BidirIt, typename _Comp>
  void mergesort(_BidirIt begin, _BidirIt end, _Comp c);

Реализовать контейнер семантически эквивалентный std::stack. На его основе (!) реализовать контейнер семантически эквивалентный std::queue, операции по добавлению в конец и чтению из начала для которого будут иметь сложность amortized O(1).

Unordered Map

https://www.dropbox.com/sh/9dye3j9z3iwzwex/SbSKsDzz_K

Proximity Iterator

https://www.dropbox.com/sh/ldbnv7z4urkqcxy/nsP4Hj0YWo

Algorithms

Предлагается реализовать следующие алгоритмы STL для двух категорий итераторов: RandomAccessIterator и ForwardIterator

std::rotate // in-place
std::reverse // in-place
std::random_shuffle // in-place

Пример реализации std::rotate для RandomAccessIterator: https://www.dropbox.com/s/82q3l2pxuvfrnlo/rotate.cc

std::bind/std::mem_fn

https://www.dropbox.com/s/gjzafi0ocb6pcc6/assignment.cc?m