Matrica preko dinamičkog niza

Napisati šablon klase Matrica<T> koja predstavlja matricu proizvoljnih dimenzija. Elementi se čuvaju red po red u jednom nizu tipa DinamickiNiz<T> iz zaglavlja dinamicki_niz.h (element (i, j) je na poziciji i * kolone + j).

template <typename T>
class Matrica {
public:
    Matrica(std::size_t redovi, std::size_t kolone, const T& vrednost = T());
    std::size_t redovi() const;
    std::size_t kolone() const;
    T& operator()(std::size_t i, std::size_t j);
    const T& operator()(std::size_t i, std::size_t j) const;
    void dodaj_red(const DinamickiNiz<T>& red);
    Matrica transponovana() const;
};

Funkcija dodaj_red dodaje novi red na dno matrice u amortizovanom vremenu $O(\text{kolone})$.

Pitanja za razmišljanje: Da li je klasi Matrica potreban destruktor, konstruktor kopije i operator dodele? Zašto? Zašto bi dodavanje nove kolone bilo skupo?

Ulaz

U prvom redu učitavaju se dimenzije r i k $(1 \le r, k \le 100)$, a zatim r redova sa po k celih brojeva. Nakon toga učitava se broj d $(0 \le d \le 100)$, a zatim d redova sa po k brojeva koji se dodaju pozivom dodaj_red.

Izlaz

Ispisati matricu, zatim red --, zatim transponovanu matricu u kojoj je element (0, 0) postavljen na -2, zatim red -- i ponovo originalnu matricu (ona ne sme biti izmenjena).

Primer

Ulaz

2 3
1 2 3
4 5 6
1
7 8 9

Izlaz

1 2 3
4 5 6
7 8 9
--
-2 4 7
2 5 8
3 6 9
--
1 2 3
4 5 6
7 8 9

Postavka

main.cpp

#include <iostream>

#include "dinamicki_niz.h"

namespace matf {

    // Matrica proizvoljnih dimenzija; elementi se cuvaju u jednom
    // dinamickom nizu, red po red.
    template <typename T>
    class Matrica {
    private:
        // Ovde ide vasa implementacija

    public:
        Matrica(std::size_t redovi, std::size_t kolone, const T& vrednost = T());

        std::size_t redovi() const;
        std::size_t kolone() const;

        T& operator()(std::size_t i, std::size_t j);
        const T& operator()(std::size_t i, std::size_t j) const;

        // Dodaje novi red na dno matrice; red ima tacno kolone() elemenata.
        void dodaj_red(const DinamickiNiz<T>& red);

        Matrica transponovana() const;
    };

    // Ovde ide vasa implementacija

} // namespace matf

template <typename T>
void ispisi(const matf::Matrica<T>& m)
{
    for (std::size_t i = 0; i < m.redovi(); ++i) {
        for (std::size_t j = 0; j < m.kolone(); ++j)
            std::cout << m(i, j) << " ";
        std::cout << std::endl;
    }
}

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

    matf::Matrica<int> m(r, k);
    for (std::size_t i = 0; i < r; ++i)
        for (std::size_t j = 0; j < k; ++j)
            std::cin >> m(i, j);

    std::size_t d;
    std::cin >> d;
    for (std::size_t i = 0; i < d; ++i) {
        DinamickiNiz<int> red;
        for (std::size_t j = 0; j < k; ++j) {
            int x;
            std::cin >> x;
            red.dodaj(x);
        }
        m.dodaj_red(red);
    }

    ispisi(m);
    std::cout << "--" << std::endl;

    // Kopija mora biti nezavisna od originala.
    matf::Matrica<int> t = m.transponovana();
    matf::Matrica<int> kopija = m;
    kopija = t;
    kopija(0, 0) = -1;
    t(0, 0) = -2;

    ispisi(t);
    std::cout << "--" << std::endl;
    ispisi(m);

    return 0;
}

Rešenje

main.cpp

#include <iostream>

#include "dinamicki_niz.h"

namespace matf {

    // Matrica proizvoljnih dimenzija; elementi se cuvaju u jednom
    // dinamickom nizu, red po red.
    template <typename T>
    class Matrica {
    private:
        // Element (i, j) je na poziciji i * kolone_ + j. Kopiranje i
        // oslobadjanje obavlja DinamickiNiz, pa Matrici ne trebaju
        // destruktor, konstruktor kopije ni operator dodele (pravilo nule).
        DinamickiNiz<T> elementi;
        std::size_t redovi_;
        std::size_t kolone_;

    public:
        Matrica(std::size_t redovi, std::size_t kolone, const T& vrednost = T());

        std::size_t redovi() const;
        std::size_t kolone() const;

        T& operator()(std::size_t i, std::size_t j);
        const T& operator()(std::size_t i, std::size_t j) const;

        // Dodaje novi red na dno matrice; red ima tacno kolone() elemenata.
        void dodaj_red(const DinamickiNiz<T>& red);

        Matrica transponovana() const;
    };

    template <typename T>
    Matrica<T>::Matrica(std::size_t redovi, std::size_t kolone, const T& vrednost)
        : elementi(redovi * kolone > 0 ? redovi * kolone : 1),
          redovi_(redovi),
          kolone_(kolone)
    {
        for (std::size_t i = 0; i < redovi * kolone; ++i)
            elementi.dodaj(vrednost);
    }

    template <typename T>
    std::size_t Matrica<T>::redovi() const
    {
        return redovi_;
    }

    template <typename T>
    std::size_t Matrica<T>::kolone() const
    {
        return kolone_;
    }

    template <typename T>
    T& Matrica<T>::operator()(std::size_t i, std::size_t j)
    {
        assert(i < redovi_ && j < kolone_);
        return elementi[i * kolone_ + j];
    }

    template <typename T>
    const T& Matrica<T>::operator()(std::size_t i, std::size_t j) const
    {
        assert(i < redovi_ && j < kolone_);
        return elementi[i * kolone_ + j];
    }

    // Redovi se cuvaju jedan za drugim, pa je novi red samo nastavak niza:
    // amortizovano O(kolone).
    template <typename T>
    void Matrica<T>::dodaj_red(const DinamickiNiz<T>& red)
    {
        assert(red.velicina() == kolone_);
        for (std::size_t j = 0; j < kolone_; ++j)
            elementi.dodaj(red[j]);
        ++redovi_;
    }

    template <typename T>
    Matrica<T> Matrica<T>::transponovana() const
    {
        Matrica<T> rezultat(kolone_, redovi_);
        for (std::size_t i = 0; i < redovi_; ++i)
            for (std::size_t j = 0; j < kolone_; ++j)
                rezultat(j, i) = (*this)(i, j);
        return rezultat;
    }

} // namespace matf

template <typename T>
void ispisi(const matf::Matrica<T>& m)
{
    for (std::size_t i = 0; i < m.redovi(); ++i) {
        for (std::size_t j = 0; j < m.kolone(); ++j)
            std::cout << m(i, j) << " ";
        std::cout << std::endl;
    }
}

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

    matf::Matrica<int> m(r, k);
    for (std::size_t i = 0; i < r; ++i)
        for (std::size_t j = 0; j < k; ++j)
            std::cin >> m(i, j);

    std::size_t d;
    std::cin >> d;
    for (std::size_t i = 0; i < d; ++i) {
        DinamickiNiz<int> red;
        for (std::size_t j = 0; j < k; ++j) {
            int x;
            std::cin >> x;
            red.dodaj(x);
        }
        m.dodaj_red(red);
    }

    ispisi(m);
    std::cout << "--" << std::endl;

    // Kopija mora biti nezavisna od originala.
    matf::Matrica<int> t = m.transponovana();
    matf::Matrica<int> kopija = m;
    kopija = t;
    kopija(0, 0) = -1;
    t(0, 0) = -2;

    ispisi(t);
    std::cout << "--" << std::endl;
    ispisi(m);

    return 0;
}