V tomto úkolu budete implementovat oboustranně spojený spojový seznam,
viz Wikipedia, ve
stylu standardní knihovny. To znamená, že dostanete hlavičkový soubor
definující třídu pjc::list
, včetně jejího rozhraní, a sadu testů, které
ověří, zda vaše implementace funguje tak, jak má. Váš úkol pak bude
naimplementovat jednotlivé metody třídy list
tak, aby všechny testy
prošly.
Pro usnadnění implementace jsou testy rozděleny do 5 částí, které na sobě staví a z nichž každá testuje jinou část vaší implementace. Díky tomu můžete pracovat dle testů bez toho, aby se na vás vyvalily chyby, které zatím ani nemůžete opravit.
Seznam metod, které musíte implementovat najdete v hlavičce list.hpp
.
Co jednotlivé metody mají dělat pak najdete v téže hlavičce, ve formátu tzv. Doxygen
komentářů1).
Archiv s testy, hlavičkou list.hpp
a CMakeLists.txt
najdete
zde.
Jeden nebo více .cpp
souborů, které implementují funkce deklarované v
souboru list.hpp
tak, aby testy procházely a neztrácela se paměť. Při práci
na úkolu soubor list.hpp
neměňte.
Sekce | Body |
---|---|
Basic functionality (stage1) | 2.5 |
Iterators (stage2) | 2.5 |
Copy, move, compare (stage3) | 2.5 |
Reverse | 1.0 |
Split | 1.5 |
Merge | 1.5 |
Sort | 1.0 |
Remove | 1.0 |
Split: algorithmic complexity | 0.5 |
Merge: algorithmic complexity | 0.5 |
Sort: algorithmic complexity | 0.5 |
Doporučujeme o listu přemýšlet a pohybovat se v něm podobně jako ve
stromu, to jest rekurzivně. Prakticky to znamená, že by se člověk při
průchodu listu neměl orientovat dle velikosti, ale dle struktury –
to že jsme v prvním uzlu se pozná tak, že platí prev == nullptr
a naopak poslední uzel se pozná dle toho tak, že platí next == nullptr
.
Ostatní uzly jsou prostě někde v listu a není důležité, kde přesně.
Stejně tak vám doporučujeme vždy aktualizovat ukazatele prvků v listu, i
v případě, že to není striktně potřeba. Například když smažete
poslední uzel v listu, tak krom přesunutí ukazatele tail
doporučujeme
vynulovat i ukazatel next
předposledního (nově posledního) uzlu listu.
Implementaci si můžete zjednodušit vhodným použití funkcí z dvou hlaviček, <utility> a <algorithm>.
namespace
, musí v něm být i definice.
split
, zkontrolujte, zda nemáte stejný problém, jako je předveden na 6. cvičení v sekci další příklady, konkrétně tracker_in_a_jar
.
Jako sort doporučujeme Merge sort. Pro spojové seznamy je velmi vhodný, protože umožňuje seřadit celý list bez přesouvání prvků samotných a nepotřebuje mnoho extra paměti.
Vaše implementace by měla být tzv. "stabilní", ale přímo v testech to nekontrolujeme, pouze testujeme, zda se asymptotická složitost vaší implementace jeví rozumná.
Metody vnořených tříd (například list::iterator
) se definují stejně
jako metody tříd, ale je potřeba si uvědomit, že k jejich plné
identifikaci je potřeba zmínit i (všechny) vnější třídy.
K této deklaraci
class list { class iterator { iterator& operator--(); }; };tedy patří tato definice
list::iterator& list::iterator::operator--() { ... }
Specifikace list::iterator
obsahuje i operátor přetypování, tj.
operator const_iterator() const
. V definici je potřeba plně
specifikovat všechny typy, takže ve výsledku k němu patří tato definice
list::iterator::operator list::const_iterator() const { ... }
Nezapomeňte, že iterátory listu jsou tzv. BiDirectional
, a tudíž musí
být možné iterátor přesunout zpátky k předchozímu prvku. Toto platí i
pro iterátor vzniklý voláním funkce list::end
.
Dávejte si pozor na přístup ke smazané paměti, protože jakmile nějaký kus paměti uvolníte, už k němu nesmíte přistoupit. To znamená, že například při mazání listu je potřeba nejdříve přesunout hlavu, a až pak smazat první prvek.
Malá ilustrace (node je celá struktura reprezentující uzel v listu a šipky jsou ukazatele):
Začneme se správně zkonstruovaným listem, který má 4 prvky.
head | | _____V__ ________ ________ ________ / node | / node | / node | / node | |------ | |------ | |------ | |------ | | value | | value | | value | | value | | next | -->| next | -->| next | -->| next | --| |-- | prev |<-- | prev |<-- | prev |<-- | prev | | | |-------- |-------- |-------- |-------- | ----------------------> nullptr <-------------------------Pokud smažeme uzel, na který ukazuje head, dostaneme se do tohoto stavu:
head | | _____V__ ________ ________ ________ / nod/ | / node | / node | / node | |\--/-- | |------ | |------ | |------ | | \/lue | | value | | value | | value | | /\xt | | next | -->| next | -->| next | --| |/pre\ |<-- | prev |<-- | prev |<-- | prev | | |-------- |-------- |-------- |-------- | nullptr <--------------------------A z něho už nemůžeme pokračovat s mazáním, protože nemůžeme přistoupit k hodnotě
head.next
. Správně musíme nejdříve posunout hlavu:
head | | ________ ____V___ ________ ________ / node | / node | / node | / node | |------ | |------ | |------ | |------ | | value | | value | | value | | value | | next | -->| next | -->| next | -->| next | --| |-- | prev |<-- | prev |<-- | prev |<-- | prev | | | |-------- |-------- |-------- |-------- | ----------------------> nullptr <-------------------------A pak teprve můžeme smazat první uzel.
head | | _______ ______V_ ________ ________ / nod/ | / node | / node | / node | |\--/--| |------ | |------ | |------ | | \/lue| | value | | value | | value | | /\xt | | next | -->| next | -->| next | --| |/pre\ | |- | prev |<-- | prev |<-- | prev | | |------- | |-------- |-------- |-------- | --------> nullptr <-------------------------
Testy v 5. kroku jsou časově náročné, a je potřeba je spouštět pouze
pokud byly zkompilovány s optimalizacemi. Jsou proto schovány za tagem
[.long]
. V případě, že používáte CMake+CTest, pak se vám automaticky
dají do sady testů, pokud jste konfigurovali build buďto v Release
,
nebo v RelWithDebInfo
. V ostatních případech si je musíte spustit
manuálně, například takto:
./tests "[.long]"Silně doporučujeme ho spouštět pouze v optimalizované binárce, tj. konfigurovat v Release módu.
TIP: Obzvlášť na linuxu (a asi i Macu) doporučujeme psát kolem tagů uvozovky,
protože hranaté závorky jsou interpretované shellem jako pattern souboru (tedy
např. vector.[ch]pp
se rozvine na vector.cpp vector.hpp
, pokud oba soubory existují).
Pokud žádný takový soubor neexistuje, některé shelly skončí s chybou (zsh),
jiné to pak vezmou tak, jak to je, bez rozbalování (bash).