Radionica sa sanitajzerom: jedna pogrešna linija

U zaglavlju lista.h iz postavke u dve funkcije je napravljena po jedna greška. Verzija se bira makroom VERZIJA na početku datoteke main.cpp.

VERZIJA Izmena
1 u funkciji obrisi_sa_pocetka naredba delete stari; se izvršava pre pocetak_ = stari->sledeci;
2 u funkciji ucesljaj izbrisan je red druga.pocetak_ = nullptr;

Za obe verzije predvideti šta će se desiti, prevesti program bez i sa sanitajzerom, pokrenuti ga na probnom ulazu i pročitati izveštaj: tip greške, liniju gde je pročitana memorija i mesto gde je blok oslobođen. Zatim vratiti ispravan kod.

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

Pitanja za razmišljanje: Šta verzija 1 radi bez sanitajzera, i zašto to zavisi od računara i standardne biblioteke (nedefinisano ponašanje)? Koji deo invarijante liste je narušen u verziji 2?

Ulaz

U prvom redu učitava se broj n $(0 \le n \le 1000)$, a zatim n celih brojeva. Nakon toga učitava se broj m $(0 \le m \le 1000)$, a zatim m celih brojeva. Brojevi se dodaju u dve liste funkcijom umetni_sortirano.

Izlaz

U prvom redu ispisati prvu listu posle poziva ucesljaj. U drugom redu ispisati je posle brisanja prvog elementa (ako lista nije prazna). U trećem redu ispisati vrednost prazna() za drugu listu.

Primer

Ulaz

3
5 1 3
2
4 2

Izlaz

1 2 3 4 5
2 3 4 5
1

Postavka

lista.h

#ifndef LISTA_H
#define LISTA_H

#include <cassert>
#include <cstddef>

// Jednostruko povezana lista iz glave 4.
//
// Lista je vlasnik svojih cvorova: alocira ih sa new, a oslobadja ih
// destruktor. Kopiranje je zabranjeno; duboko kopiranje prikazano je samo
// u glavi 3, na primeru dinamickog niza.
//
// Tip T mora da podrzava kopiranje. Funkcije pronadji i obrisi(x) dodatno
// zahtevaju operatore == i !=, a umetni_sortirano i ucesljaj operatore
// < i <=.
//
// Invarijanta:
//   Ako se krene od pocetak_ i prate pokazivaci sledeci, posle tacno
//   velicina_ cvorova stize se do nullptr. Svaki cvor na tom putu alocirala
//   je lista i nijedan se ne pojavljuje dva puta.

template <typename T>
struct Cvor {
    T podatak;
    Cvor* sledeci;

    Cvor(const T& p, Cvor* s) : podatak(p), sledeci(s) {}
};

template <typename T>
class Lista {
public:
    Lista() : pocetak_(nullptr), velicina_(0) {}
    ~Lista();

    Lista(const Lista&) = delete;
    Lista& operator=(const Lista&) = delete;

    bool prazna() const { return pocetak_ == nullptr; }
    std::size_t velicina() const { return velicina_; }
    Cvor<T>* pocetak() const { return pocetak_; }

    void dodaj_na_pocetak(const T& x);
    void umetni_iza(Cvor<T>* c, const T& x);
    void umetni_ispred(Cvor<T>* c, const T& x);
    void umetni_sortirano(const T& x);

    void obrisi_sa_pocetka();
    void obrisi_iza(Cvor<T>* c);
    bool obrisi(const T& x);
    void isprazni();

    Cvor<T>* pronadji(const T& x) const;

    void ucesljaj(Lista& druga);

private:
    Cvor<T>* pocetak_;
    std::size_t velicina_;
};


// -----------------------------------------------------------------------------
// Definicije funkcija clanica
// -----------------------------------------------------------------------------

template <typename T>
Lista<T>::~Lista()
{
    isprazni();
}

template <typename T>
void Lista<T>::dodaj_na_pocetak(const T& x)
{
    Cvor<T>* novi = new Cvor<T>(x, pocetak_);
    pocetak_ = novi;
    ++velicina_;
}

// c mora da pokazuje na cvor ove liste.
template <typename T>
void Lista<T>::umetni_iza(Cvor<T>* c, const T& x)
{
    assert(c != nullptr);
    Cvor<T>* novi = new Cvor<T>(x, c->sledeci);
    c->sledeci = novi;
    ++velicina_;
}

// Novi cvor se umece iza c, a podaci se rasporede tako da redosled bude
// kao da je umetnut ispred c. Posle poziva c pokazuje na novi element.
template <typename T>
void Lista<T>::umetni_ispred(Cvor<T>* c, const T& x)
{
    assert(c != nullptr);
    umetni_iza(c, c->podatak);
    c->podatak = x;
}

// Ako je lista bila sortirana, ostaje sortirana.
template <typename T>
void Lista<T>::umetni_sortirano(const T& x)
{
    if (prazna() || x <= pocetak_->podatak) {
        dodaj_na_pocetak(x);
        return;
    }

    Cvor<T>* prethodni = pocetak_;
    while (prethodni->sledeci != nullptr && prethodni->sledeci->podatak < x)
        prethodni = prethodni->sledeci;
    umetni_iza(prethodni, x);
}

// TODO: Verzija se bira u main.cpp, makroom VERZIJA, pre ukljucivanja ovog
// zaglavlja. Verzija 1 ove funkcije je NEISPRAVNA.
template <typename T>
void Lista<T>::obrisi_sa_pocetka()
{
    assert(!prazna());
    Cvor<T>* stari = pocetak_;
#if VERZIJA == 1
    delete stari;
    pocetak_ = stari->sledeci;
#else
    pocetak_ = stari->sledeci;   // pre delete, dok je stari jos ispravan
    delete stari;
#endif
    --velicina_;
}

template <typename T>
void Lista<T>::obrisi_iza(Cvor<T>* c)
{
    assert(c != nullptr);
    Cvor<T>* stari = c->sledeci;
    assert(stari != nullptr);
    c->sledeci = stari->sledeci;
    delete stari;
    --velicina_;
}

// Brise prvo pojavljivanje x. Vraca false ako x nije u listi.
template <typename T>
bool Lista<T>::obrisi(const T& x)
{
    if (prazna())
        return false;
    if (pocetak_->podatak == x) {
        obrisi_sa_pocetka();
        return true;
    }

    Cvor<T>* prethodni = pocetak_;
    while (prethodni->sledeci != nullptr && prethodni->sledeci->podatak != x)
        prethodni = prethodni->sledeci;

    if (prethodni->sledeci == nullptr)
        return false;
    obrisi_iza(prethodni);
    return true;
}

template <typename T>
void Lista<T>::isprazni()
{
    while (!prazna())
        obrisi_sa_pocetka();
}

template <typename T>
Cvor<T>* Lista<T>::pronadji(const T& x) const
{
    for (Cvor<T>* p = pocetak_; p != nullptr; p = p->sledeci)
        if (p->podatak == x)
            return p;
    return nullptr;
}

// Ucesljava dve sortirane liste. Posle poziva ova lista sadrzi sve
// elemente, a druga je prazna. Cvorovi se ne kopiraju, samo se drugacije
// povezuju.
template <typename T>
void Lista<T>::ucesljaj(Lista& druga)
{
    Cvor<T>* a = pocetak_;
    Cvor<T>* b = druga.pocetak_;
    Cvor<T>* poslednji = nullptr;   // poslednji cvor rezultata

    while (a != nullptr && b != nullptr) {
        Cvor<T>* manji;
        if (a->podatak <= b->podatak) {
            manji = a;
            a = a->sledeci;
        } else {
            manji = b;
            b = b->sledeci;
        }

        // Prvi cvor rezultata nema prethodnika, pa se menja pocetak_.
        if (poslednji == nullptr)
            pocetak_ = manji;
        else
            poslednji->sledeci = manji;
        poslednji = manji;
    }

    Cvor<T>* ostatak = (a != nullptr) ? a : b;
    if (poslednji == nullptr)
        pocetak_ = ostatak;
    else
        poslednji->sledeci = ostatak;

    // Svaki cvor sme da pripada samo jednoj listi, inace bi ga oba
    // destruktora oslobodila.
    velicina_ += druga.velicina_;
    // TODO: Verzija 2 ove funkcije je NEISPRAVNA.
#if VERZIJA != 2
    druga.pocetak_ = nullptr;
#endif
    druga.velicina_ = 0;
}

#endif

main.cpp

#include <iostream>

#define VERZIJA 1

#include "lista.h"

template <typename T>
void ucitaj(Lista<T>& l)
{
    int n;
    std::cin >> n;
    for (int i = 0; i < n; ++i) {
        T x;
        std::cin >> x;
        l.umetni_sortirano(x);
    }
}

template <typename T>
void ispisi(const Lista<T>& l)
{
    for (Cvor<T>* p = l.pocetak(); p != nullptr; p = p->sledeci)
        std::cout << p->podatak << " ";
    std::cout << std::endl;
}

int main()
{
    Lista<int> a;
    Lista<int> b;
    ucitaj(a);
    ucitaj(b);

    a.ucesljaj(b);
    ispisi(a);

    if (!a.prazna())
        a.obrisi_sa_pocetka();
    ispisi(a);

    std::cout << b.prazna() << std::endl;
    return 0;
}

Rešenje

lista.h

#ifndef LISTA_H
#define LISTA_H

#include <cassert>
#include <cstddef>

// Jednostruko povezana lista iz glave 4.
//
// Lista je vlasnik svojih cvorova: alocira ih sa new, a oslobadja ih
// destruktor. Kopiranje je zabranjeno; duboko kopiranje prikazano je samo
// u glavi 3, na primeru dinamickog niza.
//
// Tip T mora da podrzava kopiranje. Funkcije pronadji i obrisi(x) dodatno
// zahtevaju operatore == i !=, a umetni_sortirano i ucesljaj operatore
// < i <=.
//
// Invarijanta:
//   Ako se krene od pocetak_ i prate pokazivaci sledeci, posle tacno
//   velicina_ cvorova stize se do nullptr. Svaki cvor na tom putu alocirala
//   je lista i nijedan se ne pojavljuje dva puta.

template <typename T>
struct Cvor {
    T podatak;
    Cvor* sledeci;

    Cvor(const T& p, Cvor* s) : podatak(p), sledeci(s) {}
};

template <typename T>
class Lista {
public:
    Lista() : pocetak_(nullptr), velicina_(0) {}
    ~Lista();

    Lista(const Lista&) = delete;
    Lista& operator=(const Lista&) = delete;

    bool prazna() const { return pocetak_ == nullptr; }
    std::size_t velicina() const { return velicina_; }
    Cvor<T>* pocetak() const { return pocetak_; }

    void dodaj_na_pocetak(const T& x);
    void umetni_iza(Cvor<T>* c, const T& x);
    void umetni_ispred(Cvor<T>* c, const T& x);
    void umetni_sortirano(const T& x);

    void obrisi_sa_pocetka();
    void obrisi_iza(Cvor<T>* c);
    bool obrisi(const T& x);
    void isprazni();

    Cvor<T>* pronadji(const T& x) const;

    void ucesljaj(Lista& druga);

private:
    Cvor<T>* pocetak_;
    std::size_t velicina_;
};


// -----------------------------------------------------------------------------
// Definicije funkcija clanica
// -----------------------------------------------------------------------------

template <typename T>
Lista<T>::~Lista()
{
    isprazni();
}

template <typename T>
void Lista<T>::dodaj_na_pocetak(const T& x)
{
    Cvor<T>* novi = new Cvor<T>(x, pocetak_);
    pocetak_ = novi;
    ++velicina_;
}

// c mora da pokazuje na cvor ove liste.
template <typename T>
void Lista<T>::umetni_iza(Cvor<T>* c, const T& x)
{
    assert(c != nullptr);
    Cvor<T>* novi = new Cvor<T>(x, c->sledeci);
    c->sledeci = novi;
    ++velicina_;
}

// Novi cvor se umece iza c, a podaci se rasporede tako da redosled bude
// kao da je umetnut ispred c. Posle poziva c pokazuje na novi element.
template <typename T>
void Lista<T>::umetni_ispred(Cvor<T>* c, const T& x)
{
    assert(c != nullptr);
    umetni_iza(c, c->podatak);
    c->podatak = x;
}

// Ako je lista bila sortirana, ostaje sortirana.
template <typename T>
void Lista<T>::umetni_sortirano(const T& x)
{
    if (prazna() || x <= pocetak_->podatak) {
        dodaj_na_pocetak(x);
        return;
    }

    Cvor<T>* prethodni = pocetak_;
    while (prethodni->sledeci != nullptr && prethodni->sledeci->podatak < x)
        prethodni = prethodni->sledeci;
    umetni_iza(prethodni, x);
}

template <typename T>
void Lista<T>::obrisi_sa_pocetka()
{
    assert(!prazna());
    Cvor<T>* stari = pocetak_;
    pocetak_ = stari->sledeci;   // pre delete, dok je stari jos ispravan
    delete stari;
    --velicina_;
}

template <typename T>
void Lista<T>::obrisi_iza(Cvor<T>* c)
{
    assert(c != nullptr);
    Cvor<T>* stari = c->sledeci;
    assert(stari != nullptr);
    c->sledeci = stari->sledeci;
    delete stari;
    --velicina_;
}

// Brise prvo pojavljivanje x. Vraca false ako x nije u listi.
template <typename T>
bool Lista<T>::obrisi(const T& x)
{
    if (prazna())
        return false;
    if (pocetak_->podatak == x) {
        obrisi_sa_pocetka();
        return true;
    }

    Cvor<T>* prethodni = pocetak_;
    while (prethodni->sledeci != nullptr && prethodni->sledeci->podatak != x)
        prethodni = prethodni->sledeci;

    if (prethodni->sledeci == nullptr)
        return false;
    obrisi_iza(prethodni);
    return true;
}

template <typename T>
void Lista<T>::isprazni()
{
    while (!prazna())
        obrisi_sa_pocetka();
}

template <typename T>
Cvor<T>* Lista<T>::pronadji(const T& x) const
{
    for (Cvor<T>* p = pocetak_; p != nullptr; p = p->sledeci)
        if (p->podatak == x)
            return p;
    return nullptr;
}

// Ucesljava dve sortirane liste. Posle poziva ova lista sadrzi sve
// elemente, a druga je prazna. Cvorovi se ne kopiraju, samo se drugacije
// povezuju.
template <typename T>
void Lista<T>::ucesljaj(Lista& druga)
{
    Cvor<T>* a = pocetak_;
    Cvor<T>* b = druga.pocetak_;
    Cvor<T>* poslednji = nullptr;   // poslednji cvor rezultata

    while (a != nullptr && b != nullptr) {
        Cvor<T>* manji;
        if (a->podatak <= b->podatak) {
            manji = a;
            a = a->sledeci;
        } else {
            manji = b;
            b = b->sledeci;
        }

        // Prvi cvor rezultata nema prethodnika, pa se menja pocetak_.
        if (poslednji == nullptr)
            pocetak_ = manji;
        else
            poslednji->sledeci = manji;
        poslednji = manji;
    }

    Cvor<T>* ostatak = (a != nullptr) ? a : b;
    if (poslednji == nullptr)
        pocetak_ = ostatak;
    else
        poslednji->sledeci = ostatak;

    // Svaki cvor sme da pripada samo jednoj listi, inace bi ga oba
    // destruktora oslobodila.
    velicina_ += druga.velicina_;
    druga.pocetak_ = nullptr;
    druga.velicina_ = 0;
}

#endif

main.cpp

#include <iostream>

#include "lista.h"

template <typename T>
void ucitaj(Lista<T>& l)
{
    int n;
    std::cin >> n;
    for (int i = 0; i < n; ++i) {
        T x;
        std::cin >> x;
        l.umetni_sortirano(x);
    }
}

template <typename T>
void ispisi(const Lista<T>& l)
{
    for (Cvor<T>* p = l.pocetak(); p != nullptr; p = p->sledeci)
        std::cout << p->podatak << " ";
    std::cout << std::endl;
}

int main()
{
    Lista<int> a;
    Lista<int> b;
    ucitaj(a);
    ucitaj(b);

    a.ucesljaj(b);
    ispisi(a);

    if (!a.prazna())
        a.obrisi_sa_pocetka();
    ispisi(a);

    std::cout << b.prazna() << std::endl;
    return 0;
}