Nađi grešku u realokaciji

U zaglavlju dinamicki_niz.h funkcija povecaj_kapacitet data je u četiri neispravne verzije. Verzija se bira makroom VERZIJA na početku datoteke main.cpp.

Pre pokretanja predvideti šta će se desiti. Prevesti bez i sa sanitajzerom i pokrenuti na probnom ulazu. Zapisati koji deo invarijante je prekršen i ispraviti grešku.

g++ -std=c++17 -Wall -Wextra -g main.cpp
g++ -std=c++17 -Wall -Wextra -g -fsanitize=address,undefined main.cpp

Imati u vidu da se rezultati mogu razlikovati od računara do računara (nedefinisano ponašanje).

Ulaz

U prvom redu učitava se broj elemenata n $(0 \le n \le 10^5)$, a u drugom n celih brojeva.

Izlaz

U prvom redu ispisati zbir učitanih brojeva. U drugom redu ispisati veličinu i kapacitet niza.

Primer

Ulaz

20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Izlaz

210
20 32

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.
template <typename T>
class DinamickiNiz {
private:
    T* elementi;
    std::size_t velicina_;
    std::size_t kapacitet_;

    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;
    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();

    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)
{
    // 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_)
{
    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>
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];
}

// TODO: Cetiri NEISPRAVNE verzije realokacije. Verzija se bira u main.cpp,
// makroom VERZIJA, pre ukljucivanja ovog zaglavlja.
template <typename T>
void DinamickiNiz<T>::povecaj_kapacitet()
{
    std::size_t novi_kapacitet = 2 * kapacitet_;
    T* novi = new T[novi_kapacitet];

#if VERZIJA == 1
    delete[] elementi;
    for (std::size_t i = 0; i < velicina_; ++i)
        novi[i] = elementi[i];
    elementi = novi;
    kapacitet_ = novi_kapacitet;
#elif VERZIJA == 2
    for (std::size_t i = 0; i < velicina_; ++i)
        novi[i] = elementi[i];
    delete[] elementi;
    elementi = novi;
#elif VERZIJA == 3
    for (std::size_t i = 0; i < velicina_; ++i)
        novi[i] = elementi[i];
    delete[] elementi;
    kapacitet_ = novi_kapacitet;
#elif VERZIJA == 4
    for (std::size_t i = 0; i <= velicina_; ++i)
        novi[i] = elementi[i];
    delete[] elementi;
    elementi = novi;
    kapacitet_ = novi_kapacitet;
#else
#error "VERZIJA mora biti 1, 2, 3 ili 4"
#endif
}

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_;
}

#endif

main.cpp

// Promeniti VERZIJA na 1, 2, 3 i 4 i za svaku verziju:
//   1. prevesti bez sanitajzera i pokrenuti,
//   2. prevesti sa -fsanitize=address,undefined i procitati izvestaj.

#define VERZIJA 1

#include <iostream>

#include "dinamicki_niz.h"

int main()
{
    int n;
    std::cin >> n;

    DinamickiNiz<int> niz;
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        niz.dodaj(x);
    }

    long long zbir = 0;
    for (std::size_t i = 0; i < niz.velicina(); ++i)
        zbir += niz[i];

    std::cout << zbir << std::endl;
    std::cout << niz.velicina() << " " << niz.kapacitet() << std::endl;

    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.
template <typename T>
class DinamickiNiz {
private:
    T* elementi;
    std::size_t velicina_;
    std::size_t kapacitet_;

    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;
    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();

    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)
{
    // 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_)
{
    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>
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;
}

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_;
}

#endif

main.cpp

#include <iostream>

#include "dinamicki_niz.h"

int main()
{
    int n;
    std::cin >> n;

    DinamickiNiz<int> niz;
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        niz.dodaj(x);
    }

    long long zbir = 0;
    for (std::size_t i = 0; i < niz.velicina(); ++i)
        zbir += niz[i];

    std::cout << zbir << std::endl;
    std::cout << niz.velicina() << " " << niz.kapacitet() << std::endl;

    return 0;
}