flat_set
je vhodný pro případy, kdy se bude často hledat a iterovat,
ale nevhodný pro případy, kdy se často mění jeho obsah
Poslední povinný domácí úkol bude implementace datové struktury, které se
říká flatset, v STL stylu. Výhoda flatsetu oproti std::set
je
rychlejší výhledávání i iterace seřazených prvků, nevýhoda pak je, že
vkládání a mazání prvků je časově náročnější.
Interně flat_set
funguje tak, že si udržuje seřazené pole obsahující
všechny prvky. To znamená, že pokud hledáme nějaký prvek, můžeme použít
binární vyhledávání. Znamená to ale taky to, že asymptotická složitost
flat_set::insert
i flat_set::erase
je lineární a ne logaritmická
jako u std::set::insert
, respektive std::set::erase
1).
Nebudeme po vás chtít implementaci, která kompletně kopíruje rozhraní
std::set
, stačí podmnožina popsaná tímto útržkem:
template <typename T, typename Comparator> class flat_set { public: using iterator = ...; using const_iterator = ...; using size_type = ...; using value_type = ...; // Speciální member funkce se chovají běžným stylem flat_set(); flat_set(Comparator const& cmp); flat_set(flat_set const& rhs); flat_set(flat_set && rhs); flat_set& operator=(flat_set const& rhs); flat_set& operator=(flat_set && rhs); ~flat_set(); // Konstruktory co vytvoří flat_set z prvků definovaných jako // [first, last). Alokují pouze jednou pokud je to možné. template <typename InputIterator> flat_set(InputIterator first, InputIterator last); template <typename InputIterator> flat_set(InputIterator first, InputIterator last, Comparator const& cmp); // Vloží prvek do setu, buďto pomocí kopie, nebo pomocí přesunu. std::pair<iterator, bool> insert(T const& v); std::pair<iterator, bool> insert(T&& v); // Vloží prvky z [first, last), alokuje pouze jednou pokud je to možné template <typename InputIterator> void insert(InputIterator first, InputIterator last); // Smaže prvek na který ukazuje i, vrátí iterátor k dalšímu prvku iterator erase(const_iterator i); // Smaže všechny prvky z [from, to), vrátí iterátor k dalšímu prvku iterator erase(const_iterator from, const_iterator to); // Iterátory předané dovnitř erase odkazují dovnitř setu. // Smaže prvek rovný klíči pokud existuje. // Vrátí kolik prvků bylo smazáno size_type erase(value_type const& key); // Běžné funkce k vytvoření iterátorů iterator begin() noexcept; iterator end() noexcept; const_iterator begin() const noexcept; const_iterator end() const noexcept; const_iterator cbegin() const noexcept; const_iterator cend() const noexcept; bool empty() const; size_type size() const; size_type capacity() const; // Zajistí, aby se do instance flat_setu dalo vložit c prvků // aniž by byla potřeba realokace void reserve(size_type c); // Vymaže všechny prvky ze setu void clear(); // Vrátí iterátor ukazující na prvek ekvivalentní s v, nebo end(), // pokud takový prvek není uvnitř setu iterator find(T const& v); const_iterator find(T const& v) const; // Vrátí iterátor k prvnímu prvku, který není menší nežli t, // nebo end() pokud takový prvek neexistuje. iterator lower_bound(T const& t); const_iterator lower_bound(T const& t) const; // Vrátí iterátor k prvnímu prvku, který je větší nežli t, // nebo end() pokud takový prvek neexistuje. iterator upper_bound(T const& t); const_iterator upper_bound(T const& t) const; // Prohodí obsah dvou setů (včetně komparátoru) void swap(flat_set& o); }; // porovnání probíhá lexikograficky bool operator==(flat_set const& a, flat_set const& b); bool operator!=(flat_set const& a, flat_set const& b); bool operator< (flat_set const& a, flat_set const& b); bool operator<=(flat_set const& a, flat_set const& b); bool operator>=(flat_set const& a, flat_set const& b); bool operator> (flat_set const& a, flat_set const& b); // Prohodí obsah dvou setů (včetně komparátoru) template <typename T> void swap(flat_set<T> const& a, flat_set<T> const& b);Pokud není specifikováno, jaký komparátor má
flat_set
použít,
používá se operator<
.
Potřebné hlavičkové soubory a testy ke stažení zde.
Odevzdejte hlavičkový soubor flatset.hpp
, ve kterém implementujete
flat_set
.
Jak můžete vidět na bodovém ohodnocení, tento úkol je míněn jako signifikantně jednodušší než ostatní dva velké úkoly. To ovšem platí pouze v případě, že na implementaci půjdete chytře – doporučujeme tedy začít rozmyšlením si, jak si implementaci co nejvíce zjednodušit2).
Pokud použijete přiložený CMakeLists.txt, budou se vám kompilovat dvě sady testů, “basics” a “full”. Testy z “basics” sady slouží jako rychlá kontrola funkcionality během vývoje, zatímco testy ze sady “full” pak jsou ty testy, na kterých bude váš flatset kontrolován v Brute.
flat_set
má k dispozici buďto operator<
, nebo speciální komparátor,
který se stejným způsobem chová. To znamená, že se nemůžete spolehnout
na existenci operator==
u vašeho prvku, a musíte si vystačit s <
.
Jedna z možností je předpokládat, že
\begin{align*} a = b &\iff \big(\neg (a < b) \wedge \neg (b < a)\big) \\ \end{align*}
Podobně jako u argumentů funkce, argumenty šablon mohou mít výchozí hodnoty, které se použijí, pokud uživatel explicitně nespecifikuje jinou:
#include <iostream> template <int a, int b = 2> struct tester { static bool equal() { return a == b; } }; int main() { std::cout << tester<2>::equal() << '\n'; // 1 std::cout << tester<1, 1>::equal() << '\n'; // 1 }
Range constructor, tj. flat_set(Iterator first, Iterator last)
, by měl mít
algoritmickou složitost O(N * log N). Pokud ho implementujete pomocí range
insertu, získáte ve výsledku insertion sort, který má složitost kvadratickou.
Vhodným postupem může být prvky zkopírovat, setřídit a odstranit duplicity (máme
set, ne multiset).
Silně doporučujeme prohlédnout si
Sekce | Body |
---|---|
Základní funkcionalita | 2.5 |
Správné zacházení s referencemi | 0.5 |
Správná algoritmická složitost operací3) | 0.5 |
Optimalizovaný insert dle kategorie iterátorů | 0.5 |
Optimalizovaný konstruktor dle kategorie iterátorů | 0.5 |
Optimalizované implementace range konstruktoru | 0.5 |
Připomínáme, že z úlohy musíte získat alespoň polovinu možných bodů, tj. alespoň 2.5.