2. úkol: Knihovna pro práci s maticemi - deadline 31.12.2017 23:59
Základní idea
Představme si, že pracujeme na programu, který provádí výpočty na maticích celých
čísel a na základě pozorování jeho chování jsme zjistili, že:
- Rozměry matice je vhodné mít dané dynamicky.
- Často dochází k jejich kopírování, aniž by se obsah výsledné matice změnil.
- Hojně se využívají dva specifické typy matic:
- Skalární násobky jednotkové matice - všechny její prvky obsahují stejné číslo. Tuto matici budeme dále nazývat filled.
- Skalární násobky matice jedniček - všechny její prvky na diagonále obsahují stejné číslo, ostatní jsou 0. Tuto matici budeme dále nazývat diagonal.
- Často se využívá transpozice matic.
- V prostředí, kde program pracuje, potřebujeme optimalizovat využití paměti.
Rozhraní
Základním objektem programu je třída mat
, je možné s ní pracovat pomocí následujících metod:
- Statická metoda
filled(size_t height, size_t width, int value)
: vytvoří novou filled matici.
- Statická metoda
zero(size_t height, size_t width)
: vytvoří novou nulovou matici.
- Statická metoda
diagonal(size_t size, int value)
: vytvoří novou diagonal matici (šířku a výšku má pochopitelně stejnou).
- Statická metoda
identity(size_t size)
: vytvoří novou jednotkovou matici.
- Konstruktor
mat(size_t height, size_t width)
: vytvoří novou obecnou matici zadaných rozměrů. Počáteční hodnoty jejích prvků nejsou zadáním specifikovány.
- Copy konstruktor a operátor přiřazení: z hlediska uživatele třídy se tváří jako kopírování hodnotou, interně to však bude složitější - viz níže.
- Metody
size_t height()
a size_t width()
: vrací výšku resp. šířku matice.
- Metoda
int get(size_t row, size_t col)
: vrací prvek na daném řádku a sloupci, indexuje se od 0.
- Metoda
void set(size_t row, size_t col, int value)
: nastaví prvek na daném řádku a sloupci, indexuje se od 0.
- Metoda
mat transposition()
: vytvoří novou matici, která je transpozicí té aktuální.
- Operátory:
==
a !=
: vrací true
, pokud mají matice stejné rozměry a hodnoty, jinak false
.
+
, -
a *
: vrací novou matici, která je součtem, rozdílem či násobkem daných dvou matic.
+=
, -=
a *=
: přiřadí výsledek příslušné operace do matice na levé straně.
Hodnocení
Celkový počet bodů za úkol je 25, přičemž až 20 je možné získat za splnění základního zadání.
Dalších 5 bodů lze získat za splnění jednoho z níže uvedených rozšíření
Základní zadání (20 bodů)
- Všechny matice jsou ve skutečnosti uložené na haldě, třída
mat
umožňuje s nimi pouze jednoduše pracovat, jako by se jednalo o hodnotové typy.
- Pokud přiřazujeme jednu instanci třídy
mat
do jiné, ihned matici neklonujeme, ale zkopírujeme pouze odkaz.
- Až ve chvíli, kdy zapisujeme data do instance třídy
mat
, která sdílí ukazatel na matici s někým jiným, musíme danou matici zkopírovat a změny provést v kopii
(tato sémantika se nazývá copy-on-write).
- Pro matice na haldě je potřeba použít běhový polymorfismus - ve filled a diagonal maticích tím značně ušetříme paměť
(stačí si pamatovat jen rozměry a jednu hodnotu pro každou takovou matici).
- Operace porovnání, sčítání, odčítání a násobení nemusejí být časově zoptimalizované (tj. klidně prvky projděte jeden po druhém).
Transpozice musí být zvlášť ošetřena alespoň pro filled a diagonal matice.
- Dbejte na vhodné rozdělení funkcionality, rozšiřitelnost a čitelnost kódu.
- Pokud dojde k neplatné operaci, např. sčítání nekompatibilních matic, přístup k neplatnému poli matice apod. (porovnání nekompatibilních matic se nepočítá,
to vrací
false
), vyhoďte výjimku pomocí throw std::exception("Nejaka hlaska");
- Zápis do diagonal či filled matice není považován za chybu. Očekávanou sémantikou je převod takové matice na obecnou a provedení změny na ní.
Rozšíření (5 bodů)
Vyberte si jedno z následujících rozšíření:
- Vytvořte třídu
mat
jako šablonu, tedy template <typename T> mat
(použití: mat<float> fMat(3,3);
), kde T
může být libovolný číselný typ.
Můžete tedy očekávat, že na něm budou všechny potřebné aritmetické operace a bude možné na něj implicitně zkonvertovat např. 0 a 1.
- Vyberte si dvě z operací uvedených níže a zoptimalizujte je s využitím běhového polymorfismu. U binárních operací dejte pozor na to, že polymorfní může být levý i pravý operand. Operace:
- Porovnání
- Sčítání nebo odčítání (tj. nelze si vybrat jen sčítání a odčítání, ale lze např. sčítání a porovnání)
- Násobení
- Transpozice obecné matice - ošetření transpozice již transponované matice (která po transpozici nebyla změněna)
Testovací vstupy
Níže přiložený program by se měl v pořádku zkompilovat a úspěšně v Debug režimu proběhnout, aniž by byl porušen jakýkoliv assert
:
Poznámky
- Počet odkazů na každou matici na haldě si můžete buď ukládat přímo do ní, nebo využít
std::shared_ptr
.
Obě možnosti mají své pro a proti, v případě té druhé (kterou vřele doporučuji pro procvičení práce s tímto typem ukazatele) se může hodit třída
std::enable_shared_from_this
.
- Zejména v případě druhého rozšíření se může stát, že výpočet každého pole matice, resp. přístup k němu bude probíhat přes několik virtuálních volání.
To by pro reálné použití takovéto knihovny mohl být výkonnostní problém, my se tím však nebudeme zabývat. Cílem úkolu je zejména procvičit si běhový polymorfismus
a zapouzdřenost.
- Pozor na to, že pokud budete chtít alokovat pole pomocí chytrého ukazatele
std::shared_ptr
, má to určitá úskalí - je potřeba dodat vlastní
deleter
a přístup k prvkům je taky trochu problematický. Doporučuji proto pro pole použít spíše std::unique_ptr