Третья группа — различия между версиями

Материал из SEWiki
Перейти к: навигация, поиск
(Задания)
Строка 136: Строка 136:
  
 
Реализовать контейнер семантически эквивалентный std::stack. На его основе (!) реализовать контейнер семантически эквивалентный std::queue, операции по добавлению в конец и чтению из начала для которого будут иметь сложность ''amortized O(1)''.
 
Реализовать контейнер семантически эквивалентный std::stack. На его основе (!) реализовать контейнер семантически эквивалентный std::queue, операции по добавлению в конец и чтению из начала для которого будут иметь сложность ''amortized O(1)''.
 +
 +
== Unordered Map ==
 +
 +
https://www.dropbox.com/sh/9dye3j9z3iwzwex/SbSKsDzz_K

Версия 13:06, 13 февраля 2013

Общее

Задания

Компиляция

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

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

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

Обертка над 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