Лабораторная работа 7

Цель

Цель работы:

• повысить навыки написания обобщенного кода
• усвоить "внутренности" STL библиотеки
• узнать об инженерной составляющую, которая позволяет повысить эффективность кода за счет различных приемов (в частности об амортизированной сложности)
• получить навыки написания итераторов для пользовательского контейнера

Теоретическая часть

Реализация собственных итераторов

Итератор – это такой объект, который позволяет перебирать элементы контейнера, переходя от одного элемента к другому. Контейнеры поддерживают определенный тип итератора, который наделен своим собственным набором доступных операций. Библиотека итераторов в STL помогает соединить контейнеры STL вместе с алгоритмами STL. При этом и контейнеры и алгоритмы не завязаны друг на друга, связь осуществляется только через итераторы.

Эти наборы отличаются и зависят от различных категорий итераторов:

• InputIterator (Входной)
• OutputIterator (Выходной)
• ForwardIterator (Однонаправленный)
• BidirectionalIterator (Двунаправленный)
• RandomAccessIterator (Произвольного доступа)

Подробнее - https://en.cppreference.com/w/cpp/iterator

Чтобы реализовать собственный итератор, который будет совместим со стандартной библиотекой, его следует наследовать от класса std::iterator.

template<typename ValueType>
class Iterator : public std::iterator<std::random_access_iterator_tag, ValueType> {
    // ...
};

Здесь мы указываем, что наш итератор является итератором произвольного доступа - https://en.cppreference.com/w/cpp/named_req/RandomAccessIterator

Реализация методов и внутренней работы итераторов лежит на разработчке, и сильно зависит от того, для какого контейнера реализовывается данный итератор. Например, для реализация итератора для класса vector будет очень похожа на работу с обычными указателями. Реализация же итератора для map будет более сложной и будет сильно зависеть от реализации структуры данных контейнера.

Амортизированная сложность

Чтобы правильно реализовать класс vector, необзоимо необходимо узнать об амортизированной сложности метода push_back. Нет смысла пересказывать то, что уже хорошо описано. Поэтому предлагается самостоятельно ознакомится с этим понятием по ссылкам:

• Выделение памяти под vector
• Амортизированная сложность

Задание

1. Реализуйте аналог std::vector.
2. Обеспечте амортизированную сложность O(1) добавления элемента в конец вектора.
3. Реализуте модульные тесты для вашего класса. Миниальное покрытие кода должно превышать 85%.
4. Проверьте код на наличие утечек памяти.
5. Использовать std::vector запрещается.
6. Следует использовать стандартные типы исключений из библиотеки <stdexcept>.
7. Проверьте, что ваша реализация правильно работает со стандартными алгоритмами STL (std::sort, std::copy_if, std::find_if).

Методы для реализации

template <class T>
class vector
{
public:
    vector();
    Конструктор копирования
    vector(size_t, const T&);
    ~vector();
    оператор присваивания

    operator[]
    at
    front
    back
    data

    begin
    end

    empty
    size
    reserve
    capacity

    clear
    insert
    push_back
    pop_back
    swap
};