hw.md

Домашнее задание 1

• map - красно-черное дерево/BST
• hashtable
• set - красно-черное дерево/BST
• unordered_set
• dynamic_bitset
• развернутый список
• forward_list, list, queue, stack
• префиксное дерево

map

Реализуйте аналог стандартного контейнера std::map<Key, T, Cmp>.

template <class Key, class T, class Cmp>
class map
{
public:
    map();
    ~map();
    map(const map&);
    map& operator=(const map&);
    
    begin
    end
    
    size
    empty
    
    operator[]
    at
    
    insert
    erase
    swap
    clear
    
    find
};

unordered_map

Реализуйте аналог стандартного контейнера std::unordered_map<Key, Value, Hash, EqualKey>. Продемонстрируйте работу вашего класса (необходимо вызвать каждый метод). Проверьте ваш код на утечки памяти. Реализуйте юнит-тесты к классу.

template <class Key, class T, class Hash, class EqualKey>
class unordered_map
{
public:
    unordered_map();
    ~unordered_map();
    unordered_map(const unordered_map&);
    unordered_map& operator=(const unordered_map&);
    
    begin
    end
    
    size
    empty
    
    operator[]
    at
    
    insert
    erase
    swap
    clear
    
    find
};

set

Реализуйте аналог стандартного контейнера std::set<Value, Cmp>. Продемонстрируйте работу вашего класса (необходимо вызвать каждый метод). Проверьте ваш код на утечки памяти. Реализуйте юнит-тесты к классу.

template <class T, class Cmp>
class set
{
public:
    set();
    ~set();
    set(const set&);
    set& operator=(const set&);
    
    begin
    end
    
    size
    empty
    
    has
    
    insert
    erase
    swap
    clear
    
    find
};

unordered_set

Реализуйте аналог стандартного контейнера std::unordered_set<Value, Hash, EqualKey>. Продемонстрируйте работу вашего класса (необходимо вызвать каждый метод). Проверьте ваш код на утечки памяти. Реализуйте юнит-тесты к классу.

template <class T, class Hash, class EqualKey>
class unordered_set
{
public:
    unordered_set();
    ~unordered_set();
    unordered_set(const unordered_set&);
    unordered_set& operator=(const unordered_set&);
    
    begin
    end
    
    size
    empty
    
    has
    
    insert
    erase
    swap
    clear
    
    find
};

dynamic_bitset

Реализуйте аналог контейнера boost::dynamic_bitset. Продемонстрируйте работу вашего класса (необходимо вызвать каждый метод). Проверьте ваш код на утечки памяти. Реализуйте юнит-тесты к классу.

class dynamic_bitset
{
public:
    class reference
    {
    public:
        // An automatically generated copy constructor.

        reference& operator=(bool value);
        reference& operator=(const reference& rhs);

        reference& operator|=(bool value);
        reference& operator&=(bool value);
        reference& operator^=(bool value);
        reference& operator-=(bool value);

        bool operator~() const;
        operator bool() const;
        reference& flip();
    };

    explicit dynamic_bitset(size_type num_bits, unsigned long value = 0);

    dynamic_bitset(const dynamic_bitset& b);

    void swap(dynamic_bitset& b);

    dynamic_bitset& operator=(const dynamic_bitset& b);

    void clear();
    void pop_back();
    void push_back(bool bit);

    dynamic_bitset& operator&=(const dynamic_bitset& b);
    dynamic_bitset& operator|=(const dynamic_bitset& b);
    dynamic_bitset& operator^=(const dynamic_bitset& b);
    dynamic_bitset& operator-=(const dynamic_bitset& b);
    dynamic_bitset& operator<<=(size_type n);
    dynamic_bitset& operator>>=(size_type n);
    dynamic_bitset operator<<(size_type n) const;
    dynamic_bitset operator>>(size_type n) const;

    dynamic_bitset& set(size_type n, bool val = true);
    dynamic_bitset& set();
    dynamic_bitset& reset(size_type n);
    dynamic_bitset& reset();
    dynamic_bitset& flip(size_type n);
    dynamic_bitset& flip();
    bool all() const;
    bool any() const;
    bool none() const;
    dynamic_bitset operator~() const;
    size_type count() const noexcept;

    reference operator[](size_type pos);
    bool operator[](size_type pos) const;

    unsigned long to_ulong() const;

    size_type size() const noexcept;
    size_type num_blocks() const noexcept;
    bool empty() const noexcept;
};

forward_list

Реализуйте аналог контейнера std::forward_list. Продемонстрируйте работу вашего класса (необходимо вызвать каждый метод). Проверьте ваш код на утечки памяти. Реализуйте юнит-тесты к классу.

template <class T>
class forward_list
{
public:
    кострукторы
    декструктор
    оператор присваивания
    
    before_begin
    begin
    end
    
    empty
    size
    
    front
    
    push_front
    pop_front
    insert_after
    erase_after
    clear
    swap
    
    remove
    remove_if
    unique
    sort
    reverse
};

list

Реализуйте аналог контейнера std::list. Продемонстрируйте работу вашего класса (необходимо вызвать каждый метод). Проверьте ваш код на утечки памяти. Реализуйте юнит-тесты к классу.

template <class T>
class list
{
public:
    кострукторы
    декструктор
    оператор присваивания
    
    begin
    end
    
    empty
    size
    
    front
    back
    
    push_front
    pop_front
    push_back
    pop_back
    insert
    erase
    clear
    swap
    
    remove
    remove_if
    unique
    sort
};

deque

Реализуйте аналог контейнера std::deque. Продемонстрируйте работу вашего класса (необходимо вызвать каждый метод). Проверьте ваш код на утечки памяти. Реализуйте юнит-тесты к классу.

template <class T>
class deque
{
public:
    кострукторы
    декструктор
    оператор присваивания
    
    begin
    end
    
    empty
    size
    
    front
    back
    
    push_front
    pop_front
    push_back
    pop_back
    insert
    erase
    clear
    swap
};

stack

Реализуйте аналог контейнера std::stack. Продемонстрируйте работу вашего класса (необходимо вызвать каждый метод). Проверьте ваш код на утечки памяти. Реализуйте юнит-тесты к классу.

template <class T>
class stack
{
public:
    кострукторы
    декструктор
    оператор присваивания
    
    empty
    size
    
    push
    pop
    top
    
    swap
};

queue

Реализуйте аналог контейнера std::queue. Продемонстрируйте работу вашего класса (необходимо вызвать каждый метод). Проверьте ваш код на утечки памяти. Реализуйте юнит-тесты к классу.

template <class T>
class queue
{
public:
    кострукторы
    декструктор
    оператор присваивания
    
    empty
    size
    
    push
    pop
    front
    
    swap
};

Unrolled linked list

Реализуйте контейнер развернутый список. Сравните его производительность с std::vector и std::list. Продемонстрируйте работу вашего класса (необходимо вызвать каждый метод). Проверьте ваш код на утечки памяти. Реализуйте юнит-тесты к классу.

Методы, которые необходимо реализовать:

template<class T, int BucketSize>
class unrolled_linked_list
{
public:
    
    unrolled_linked_list();
    unrolled_linked_list(const unrolled_linked_list&);
    ~unrolled_linked_list();
    
    operator=
    
    begin
    end
    
    size
    empty
    
    operator[]
    at
    front
    back
    
    push_back
    pop_back
    insert
    erase
    swap
    clear
};

Префиксное дерево

Реализуйте класс префиксного дерева. Сравните его производительность с std::map<std::string, T>. Продемонстрируйте работу вашего класса (необходимо вызвать каждый метод). Проверьте ваш код на утечки памяти. Реализуйте юнит-тесты к классу.

template <class T, class KeyType=wchar_t>
class trie
{
public:
    trie();
    trie(const trie&);
    ~trie();
    
    operator=
    
    begin
    end
    
    size
    empty
    
    insert
    erase
    swap
    clear
    
    find
    get_value
    
    struct search_iterator
    {
        bool get_value(T* out_value = nullptr) const;
        bool has_value() const;
        bool advance(const std::basic_string<KeyType>& sub_key);
        bool advance(const KeyType* sub_key);
    };
};