Automatsko smanjivanje kapaciteta

Klasi DinamickiNiz<T> dodati funkciju članicu

void obrisi_poslednji_i_smanji(std::size_t faktor);

koja briše poslednji element, a zatim prepolovljava kapacitet kada niz postane „previše prazan”, tj. kada je posle brisanja velicina * faktor <= kapacitet. Kapacitet nikada ne sme da padne ispod 1.

U postavci klasa već broji realokacije u članu broj_realokacija_ (videti povecaj_kapacitet). Smanjivanje kapaciteta je takođe realokacija i treba da se broji.

Uporediti dve politike:

faktor = 2: kapacitet se prepolovljava kada veličina padne na polovinu kapaciteta;
faktor = 4: kapacitet se prepolovljava kada veličina padne na četvrtinu kapaciteta.

Za obe politike izmeriti broj realokacija u scenariju: napuniti niz do 16 elemenata (kapacitet 16), zatim 1000 puta naizmenično dodaj pa obrisi_poslednji_i_smanji.

Pitanja za razmišljanje: Zašto je politika 1/2 loša? Gde se niz nalazi odmah posle rasta kapaciteta? Zašto kod politike 1/4 amortizovana cena ostaje $O(1)$? (Posle svake realokacije niz je popunjen do polovine, pa i do sledećeg rasta i do sledećeg smanjivanja mora proći broj operacija srazmeran kapacitetu.)

Ulaz

Učitavaju se tri broja: faktor (2 ili 4), n i k $(0 \le n, k \le 10^5)$.

Program kreće od praznog niza kapaciteta 4, dodaje n elemenata, zatim k puta poziva dodaj pa obrisi_poslednji_i_smanji(faktor), i na kraju briše sve elemente pozivima obrisi_poslednji_i_smanji(faktor).

Izlaz

Posle svake od tri faze ispisati u jednom redu: ukupan broj realokacija, veličinu i kapacitet niza.

Primer

Ulaz

2 16 1000

Izlaz

2 16 16
2002 16 16
2006 0 1

Primer

Ulaz

4 16 1000

Izlaz

2 16 16
3 16 32
8 0 1

Postavka

`dinamicki_niz.h`

#ifndef DINAMICKI_NIZ_H
#define DINAMICKI_NIZ_H

#include <cassert>
#include <cstddef>

// Dinamicki niz iz glave 3.
//
// Implementacija namerno koristi new[]/delete[] i sama upravlja kopiranjem
// (destruktor, konstruktor kopije, operator dodele), kao sto je opisano u
// glavi. U aplikativnom kodu umesto ove klase koristi se std::vector.
//
// Zbog nacina na koji se alocira memorija, tip T mora da podrzava:
//   1. podrazumevano konstruisanje (new T[n]);
//   2. operator dodele.
// Funkcija pronadji dodatno zahteva operator ==.
//
// Invarijanta:
//   0 <= velicina_ <= kapacitet_, elementi ukazuje na blok od kapacitet_
//   objekata tipa T, a pozicije 0, ..., velicina_ - 1 sadrze elemente niza.
//   Pored toga, kapacitet_ > 0, jer rast udvostrucava kapacitet.
//   broj_realokacija_ broji sve realokacije (rast i smanjivanje).
template <typename T>
class DinamickiNiz {
private:
    T* elementi;
    std::size_t velicina_;
    std::size_t kapacitet_;
    std::size_t broj_realokacija_;

    void povecaj_kapacitet();

public:
    DinamickiNiz(std::size_t pocetni_kapacitet = 4);
    ~DinamickiNiz();

    DinamickiNiz(const DinamickiNiz& drugi);
    DinamickiNiz& operator=(const DinamickiNiz& drugi);

    std::size_t velicina() const;
    std::size_t kapacitet() const;
    std::size_t broj_realokacija() const;
    bool prazan() const;

    T& operator[](std::size_t indeks);
    const T& operator[](std::size_t indeks) const;

    T& poslednji();
    const T& poslednji() const;

    void dodaj(const T& vrednost);
    void umetni(std::size_t indeks, const T& vrednost);
    void obrisi(std::size_t indeks);
    void obrisi_poslednji();

    // Brise poslednji element i prepolovljava kapacitet kada velicina
    // padne na 1/faktor kapaciteta (faktor je 2 ili 4).
    void obrisi_poslednji_i_smanji(std::size_t faktor);

    std::size_t pronadji(const T& vrednost) const;
};


// -----------------------------------------------------------------------------
// Definicije funkcija clanica
//
// Definicije funkcija sablona moraju biti vidljive prevodiocu na mestu gde se
// sablon instancira, pa se nalaze u zaglavlju, a ne u posebnom .cpp fajlu.
// -----------------------------------------------------------------------------

template <typename T>
DinamickiNiz<T>::DinamickiNiz(std::size_t pocetni_kapacitet)
    : elementi(new T[pocetni_kapacitet]),
      velicina_(0),
      kapacitet_(pocetni_kapacitet),
      broj_realokacija_(0)
{
    // Pri kapacitetu 0 udvostrucavanje bi dalo ponovo 0, pa bi dodaj
    // pisalo izvan bloka.
    assert(pocetni_kapacitet > 0);
}

template <typename T>
DinamickiNiz<T>::~DinamickiNiz()
{
    delete[] elementi;
}

template <typename T>
DinamickiNiz<T>::DinamickiNiz(const DinamickiNiz<T>& drugi)
    : elementi(new T[drugi.kapacitet_]),
      velicina_(drugi.velicina_),
      kapacitet_(drugi.kapacitet_),
      broj_realokacija_(0)
{
    for (std::size_t i = 0; i < velicina_; ++i)
        elementi[i] = drugi.elementi[i];
}

template <typename T>
DinamickiNiz<T>& DinamickiNiz<T>::operator=(const DinamickiNiz<T>& drugi)
{
    if (this == &drugi)
        return *this;

    // Novi blok se obezbedjuje i popunjava pre oslobadjanja starog.
    T* novi = new T[drugi.kapacitet_];

    for (std::size_t i = 0; i < drugi.velicina_; ++i)
        novi[i] = drugi.elementi[i];

    delete[] elementi;

    elementi = novi;
    velicina_ = drugi.velicina_;
    kapacitet_ = drugi.kapacitet_;

    return *this;
}

template <typename T>
std::size_t DinamickiNiz<T>::velicina() const
{
    return velicina_;
}

template <typename T>
std::size_t DinamickiNiz<T>::kapacitet() const
{
    return kapacitet_;
}

template <typename T>
std::size_t DinamickiNiz<T>::broj_realokacija() const
{
    return broj_realokacija_;
}

template <typename T>
bool DinamickiNiz<T>::prazan() const
{
    return velicina_ == 0;
}

template <typename T>
T& DinamickiNiz<T>::operator[](std::size_t indeks)
{
    assert(indeks < velicina_);
    return elementi[indeks];
}

template <typename T>
const T& DinamickiNiz<T>::operator[](std::size_t indeks) const
{
    assert(indeks < velicina_);
    return elementi[indeks];
}

template <typename T>
T& DinamickiNiz<T>::poslednji()
{
    // Posle provere oduzimanje ne moze da ode ispod nule.
    assert(velicina_ > 0);
    return elementi[velicina_ - 1];
}

template <typename T>
const T& DinamickiNiz<T>::poslednji() const
{
    assert(velicina_ > 0);
    return elementi[velicina_ - 1];
}

template <typename T>
void DinamickiNiz<T>::povecaj_kapacitet()
{
    std::size_t novi_kapacitet = 2 * kapacitet_;

    T* novi = new T[novi_kapacitet];

    for (std::size_t i = 0; i < velicina_; ++i)
        novi[i] = elementi[i];

    delete[] elementi;

    elementi = novi;
    kapacitet_ = novi_kapacitet;
    ++broj_realokacija_;
}

template <typename T>
void DinamickiNiz<T>::dodaj(const T& vrednost)
{
    if (velicina_ == kapacitet_)
        povecaj_kapacitet();

    elementi[velicina_] = vrednost;
    ++velicina_;
}

template <typename T>
void DinamickiNiz<T>::umetni(std::size_t indeks, const T& vrednost)
{
    assert(indeks <= velicina_);

    if (velicina_ == kapacitet_)
        povecaj_kapacitet();

    // Pomeranje ide zdesna nalevo, da se ne bi prepisali elementi
    // koji tek treba da budu pomereni.
    for (std::size_t i = velicina_; i > indeks; --i)
        elementi[i] = elementi[i - 1];

    elementi[indeks] = vrednost;
    ++velicina_;
}

template <typename T>
void DinamickiNiz<T>::obrisi(std::size_t indeks)
{
    assert(indeks < velicina_);

    for (std::size_t i = indeks; i + 1 < velicina_; ++i)
        elementi[i] = elementi[i + 1];

    --velicina_;
}

template <typename T>
void DinamickiNiz<T>::obrisi_poslednji()
{
    assert(velicina_ > 0);
    --velicina_;
}

// Vraca indeks prvog elementa jednakog vrednosti, odnosno velicina()
// ako takvog elementa nema (po uzoru na std::find, koji tada vraca end()).
template <typename T>
std::size_t DinamickiNiz<T>::pronadji(const T& vrednost) const
{
    for (std::size_t i = 0; i < velicina_; ++i)
        if (elementi[i] == vrednost)
            return i;

    return velicina_;
}

template <typename T>
void DinamickiNiz<T>::obrisi_poslednji_i_smanji(std::size_t faktor)
{
    // Ovde ide vasa implementacija
}

#endif

`main.cpp`

#include <iostream>

#include "dinamicki_niz.h"

template <typename T>
void ispisi_stanje(const DinamickiNiz<T>& niz)
{
    std::cout << niz.broj_realokacija() << " "
              << niz.velicina() << " "
              << niz.kapacitet() << std::endl;
}

int main()
{
    std::size_t faktor, n, k;
    std::cin >> faktor >> n >> k;

    DinamickiNiz<int> niz;

    for (std::size_t i = 0; i < n; ++i)
        niz.dodaj(0);
    ispisi_stanje(niz);

    for (std::size_t i = 0; i < k; ++i) {
        niz.dodaj(0);
        niz.obrisi_poslednji_i_smanji(faktor);
    }
    ispisi_stanje(niz);

    while (!niz.prazan())
        niz.obrisi_poslednji_i_smanji(faktor);
    ispisi_stanje(niz);

    return 0;
}

Rešenje

`dinamicki_niz.h`

#ifndef DINAMICKI_NIZ_H
#define DINAMICKI_NIZ_H

#include <cassert>
#include <cstddef>

// Dinamicki niz iz glave 3.
//
// Implementacija namerno koristi new[]/delete[] i sama upravlja kopiranjem
// (destruktor, konstruktor kopije, operator dodele), kao sto je opisano u
// glavi. U aplikativnom kodu umesto ove klase koristi se std::vector.
//
// Zbog nacina na koji se alocira memorija, tip T mora da podrzava:
//   1. podrazumevano konstruisanje (new T[n]);
//   2. operator dodele.
// Funkcija pronadji dodatno zahteva operator ==.
//
// Invarijanta:
//   0 <= velicina_ <= kapacitet_, elementi ukazuje na blok od kapacitet_
//   objekata tipa T, a pozicije 0, ..., velicina_ - 1 sadrze elemente niza.
//   Pored toga, kapacitet_ > 0, jer rast udvostrucava kapacitet.
//   broj_realokacija_ broji sve realokacije (rast i smanjivanje).
template <typename T>
class DinamickiNiz {
private:
    T* elementi;
    std::size_t velicina_;
    std::size_t kapacitet_;
    std::size_t broj_realokacija_;

    void povecaj_kapacitet();

public:
    DinamickiNiz(std::size_t pocetni_kapacitet = 4);
    ~DinamickiNiz();

    DinamickiNiz(const DinamickiNiz& drugi);
    DinamickiNiz& operator=(const DinamickiNiz& drugi);

    std::size_t velicina() const;
    std::size_t kapacitet() const;
    std::size_t broj_realokacija() const;
    bool prazan() const;

    T& operator[](std::size_t indeks);
    const T& operator[](std::size_t indeks) const;

    T& poslednji();
    const T& poslednji() const;

    void dodaj(const T& vrednost);
    void umetni(std::size_t indeks, const T& vrednost);
    void obrisi(std::size_t indeks);
    void obrisi_poslednji();

    // Brise poslednji element i prepolovljava kapacitet kada velicina
    // padne na 1/faktor kapaciteta (faktor je 2 ili 4).
    void obrisi_poslednji_i_smanji(std::size_t faktor);

    std::size_t pronadji(const T& vrednost) const;
};


// -----------------------------------------------------------------------------
// Definicije funkcija clanica
//
// Definicije funkcija sablona moraju biti vidljive prevodiocu na mestu gde se
// sablon instancira, pa se nalaze u zaglavlju, a ne u posebnom .cpp fajlu.
// -----------------------------------------------------------------------------

template <typename T>
DinamickiNiz<T>::DinamickiNiz(std::size_t pocetni_kapacitet)
    : elementi(new T[pocetni_kapacitet]),
      velicina_(0),
      kapacitet_(pocetni_kapacitet),
      broj_realokacija_(0)
{
    // Pri kapacitetu 0 udvostrucavanje bi dalo ponovo 0, pa bi dodaj
    // pisalo izvan bloka.
    assert(pocetni_kapacitet > 0);
}

template <typename T>
DinamickiNiz<T>::~DinamickiNiz()
{
    delete[] elementi;
}

template <typename T>
DinamickiNiz<T>::DinamickiNiz(const DinamickiNiz<T>& drugi)
    : elementi(new T[drugi.kapacitet_]),
      velicina_(drugi.velicina_),
      kapacitet_(drugi.kapacitet_),
      broj_realokacija_(0)
{
    for (std::size_t i = 0; i < velicina_; ++i)
        elementi[i] = drugi.elementi[i];
}

template <typename T>
DinamickiNiz<T>& DinamickiNiz<T>::operator=(const DinamickiNiz<T>& drugi)
{
    if (this == &drugi)
        return *this;

    // Novi blok se obezbedjuje i popunjava pre oslobadjanja starog.
    T* novi = new T[drugi.kapacitet_];

    for (std::size_t i = 0; i < drugi.velicina_; ++i)
        novi[i] = drugi.elementi[i];

    delete[] elementi;

    elementi = novi;
    velicina_ = drugi.velicina_;
    kapacitet_ = drugi.kapacitet_;

    return *this;
}

template <typename T>
std::size_t DinamickiNiz<T>::velicina() const
{
    return velicina_;
}

template <typename T>
std::size_t DinamickiNiz<T>::kapacitet() const
{
    return kapacitet_;
}

template <typename T>
std::size_t DinamickiNiz<T>::broj_realokacija() const
{
    return broj_realokacija_;
}

template <typename T>
bool DinamickiNiz<T>::prazan() const
{
    return velicina_ == 0;
}

template <typename T>
T& DinamickiNiz<T>::operator[](std::size_t indeks)
{
    assert(indeks < velicina_);
    return elementi[indeks];
}

template <typename T>
const T& DinamickiNiz<T>::operator[](std::size_t indeks) const
{
    assert(indeks < velicina_);
    return elementi[indeks];
}

template <typename T>
T& DinamickiNiz<T>::poslednji()
{
    // Posle provere oduzimanje ne moze da ode ispod nule.
    assert(velicina_ > 0);
    return elementi[velicina_ - 1];
}

template <typename T>
const T& DinamickiNiz<T>::poslednji() const
{
    assert(velicina_ > 0);
    return elementi[velicina_ - 1];
}

template <typename T>
void DinamickiNiz<T>::povecaj_kapacitet()
{
    std::size_t novi_kapacitet = 2 * kapacitet_;

    T* novi = new T[novi_kapacitet];

    for (std::size_t i = 0; i < velicina_; ++i)
        novi[i] = elementi[i];

    delete[] elementi;

    elementi = novi;
    kapacitet_ = novi_kapacitet;
    ++broj_realokacija_;
}

template <typename T>
void DinamickiNiz<T>::dodaj(const T& vrednost)
{
    if (velicina_ == kapacitet_)
        povecaj_kapacitet();

    elementi[velicina_] = vrednost;
    ++velicina_;
}

template <typename T>
void DinamickiNiz<T>::umetni(std::size_t indeks, const T& vrednost)
{
    assert(indeks <= velicina_);

    if (velicina_ == kapacitet_)
        povecaj_kapacitet();

    // Pomeranje ide zdesna nalevo, da se ne bi prepisali elementi
    // koji tek treba da budu pomereni.
    for (std::size_t i = velicina_; i > indeks; --i)
        elementi[i] = elementi[i - 1];

    elementi[indeks] = vrednost;
    ++velicina_;
}

template <typename T>
void DinamickiNiz<T>::obrisi(std::size_t indeks)
{
    assert(indeks < velicina_);

    for (std::size_t i = indeks; i + 1 < velicina_; ++i)
        elementi[i] = elementi[i + 1];

    --velicina_;
}

template <typename T>
void DinamickiNiz<T>::obrisi_poslednji()
{
    assert(velicina_ > 0);
    --velicina_;
}

// Vraca indeks prvog elementa jednakog vrednosti, odnosno velicina()
// ako takvog elementa nema (po uzoru na std::find, koji tada vraca end()).
template <typename T>
std::size_t DinamickiNiz<T>::pronadji(const T& vrednost) const
{
    for (std::size_t i = 0; i < velicina_; ++i)
        if (elementi[i] == vrednost)
            return i;

    return velicina_;
}

template <typename T>
void DinamickiNiz<T>::obrisi_poslednji_i_smanji(std::size_t faktor)
{
    assert(velicina_ > 0);
    --velicina_;

    // Uslov kapacitet_ > 1 cuva invarijantu kapacitet_ > 0. Kako je
    // velicina_ <= kapacitet_ / faktor <= kapacitet_ / 2, elementi staju
    // u prepolovljen blok.
    if (kapacitet_ <= 1 || velicina_ * faktor > kapacitet_)
        return;

    std::size_t novi_kapacitet = kapacitet_ / 2;

    T* novi = new T[novi_kapacitet];

    for (std::size_t i = 0; i < velicina_; ++i)
        novi[i] = elementi[i];

    delete[] elementi;

    elementi = novi;
    kapacitet_ = novi_kapacitet;
    ++broj_realokacija_;
}

#endif

`main.cpp`

#include <iostream>

#include "dinamicki_niz.h"

template <typename T>
void ispisi_stanje(const DinamickiNiz<T>& niz)
{
    std::cout << niz.broj_realokacija() << " "
              << niz.velicina() << " "
              << niz.kapacitet() << std::endl;
}

int main()
{
    std::size_t faktor, n, k;
    std::cin >> faktor >> n >> k;

    DinamickiNiz<int> niz;

    for (std::size_t i = 0; i < n; ++i)
        niz.dodaj(0);
    ispisi_stanje(niz);

    for (std::size_t i = 0; i < k; ++i) {
        niz.dodaj(0);
        niz.obrisi_poslednji_i_smanji(faktor);
    }
    ispisi_stanje(niz);

    while (!niz.prazan())
        niz.obrisi_poslednji_i_smanji(faktor);
    ispisi_stanje(niz);

    return 0;
}