Структури от данни и програмиране 2015/16 (КН, 2 поток)

Това е домашно №1 за студентите, посещаващи семинарните упражнения на гр.8. Срокът е до края на семестъра, като дотогава са позволени неограничен брой предавания. За всяко предадено по-рано домашно ще давам кратка обратна връзка. Домашното се води за 20т., като има възможности за бонус (т.е. изкарване на >100%).

Част 1: Имплементация (5т.)

Напишете структура от данни Tester, която да представлява опростен контейнер от данни от тип int и поддържа задължително поне следните операции:

class Tester
{
public:
    // конструира структурата и я запълва с count на брой числа.
    // Стойността на съдържаните числа няма значение.
    Tester(size_t count = 0);

    // ако не управлявате ръчно динамичната памет, можете да ги оставите
    // по подразбиране със синтаксиса " ...(const Tester& other) = default;"
    Tester(const Tester& other);
    Tester& operator=(const Tester& other);

    // премахва всички съдържани в структурата данни, оставяйки я празна
    void clear();

    // добавя числото x в "края" на структурата
    void push_back(int x);

    // добавя числото x на позиция position в структурата,
    // премествайки всички числа след нея с една позиция вдясно
    // Ако позицията е невалидна (position > size), нека
    // добавянето бъде на позиция position % size
    void insertAt(size_t position, int x);

    // премахва числото, намиращо се на позиция position,
    // премествайки всички числа след нея с една позиция вляво
    // Ако позицията е невалидна (position > size), нека
    // премахването бъде от позиция position % size
    void removeAt(size_t position);

    // БОНУС (2т.): move-конструктор и move-оператор за присвояване
    Tester(Tester&& other);
    Tester& operator=(Tester&& other);
}

Тук начинът на представяне на данните може да бъде последователен (масив) или свързан (списък). Можете да използвате стандартната библиотека (забележете приликата с методите, характерни за повечето контейнери в нея), можете да използвате и други готови реализации на контейнери.

Можете да добавяте колкото искате public и private методи и данни, стига да не променяте съществуващия интерфейс. Позволено е и да шаблонизирате този клас, ако имате нужда.

Част 2: Тестване (12т.)

Реализирайте две версии на горната структура от данни - една, в която елементите да са с последователно представяне в паметта и една със свързано представяне. Използвайки стандартните библиотеки <chrono> и <random> (изискват поне C++11), анализирайте бързодействието на двете структури от данни в следните ситуации:
- конструиране с n елемента
- последователно добавяне на n елемента в "края" на структурата
- последователно добавяне на n елемента на произволни позиции
- последователно премахване на n елемента от произволни позиции
- обикновено присвояване с operator= (copy assignment) - тук има значение колко елемента се съдържат в момента на присвояване
- БОНУС: присвояване с "преместване" (move assignment)

Имплементирайте функции, който тестват двете структури по горните няколко теста и изчисляват точно коя операция колко време отнема при даден брой елементи (напр. double testRandomInsert(size_t n)) Тези функции могат да бъдат член-функции, могат да бъдат и външни за структурите. Сравнете кои операции какво време отнемат в зависимост от размера на структурата - напр. кога конструирането е по-бързо с 100 елемента - при свързаното или последователното представяне в паметта? Ами при 20 милиона елемента? Защо?

Добра идея е да компилирате в 64-битов Release режим, както и да отмервате времето в милисекунди (в секунди е твърде неточно). Добавянето на допълнителни смислени тестове също ще бъде възнаградено с бонус.

Част 3: Синтезиране на резултатите (3т.)

Съберете в един файл резултатите от всички тестове върху двете структури от данни. Можете да направите само по 5-6 теста, стига те да покриват широк интервал - например 10-100-1000-10000-1млн.-10млн. операции. Добавете и кратко обяснение за получените времена - няма нужда да пишете есета, с няколко думи ще ви разбера.
БОНУС (2т.): Напишете за всяка операция колко точно е нейната сложност по време в зависимост от представянето в паметта.

Относно предаването: предавайте само един-единствен файл с име <фак.номер>.zip. В него включете всички файлове, съдържащи ваш код, както и файла с резултати.