Search
This is an old revision of the document!
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.
pjc::list
list
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).
list.hpp
Archiv s testy, hlavičkou list.hpp a CMakeLists.txt najdete zde.
CMakeLists.txt
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.
.cpp
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ě.
prev == nullptr
next == nullptr
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.
tail
next
Implementaci si můžete zjednodušit vhodným použití funkcí z dvou hlaviček, <utility> a <algorithm>.
namespace
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.
list::iterator
K této deklaraci
class list { class iterator { iterator& operator--(); }; };
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
operator const_iterator() const
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.
BiDirectional
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 <-------------------------
head | | _____V__ ________ ________ ________ / nod/ | / node | / node | / node | |\--/-- | |------ | |------ | |------ | | \/lue | | value | | value | | value | | /\xt | | next | -->| next | -->| next | --| |/pre\ |<-- | prev |<-- | prev |<-- | prev | | |-------- |-------- |-------- |-------- | nullptr <--------------------------
head.next
head | | ________ ____V___ ________ ________ / node | / node | / node | / node | |------ | |------ | |------ | |------ | | value | | value | | value | | value | | next | -->| next | -->| next | -->| next | --| |-- | prev |<-- | prev |<-- | prev |<-- | prev | | | |-------- |-------- |-------- |-------- | ----------------------> nullptr <-------------------------
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:
[.long]
Release
RelWithDebInfo
./tests "[.long]"
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).
vector.[ch]pp
vector.cpp vector.hpp