{{page>courses:b6b36pjc:styles#common&noheader&nofooter}}
{{page>courses:b6b36pjc:styles#ukoly&noheader&nofooter}}

====== Flatset ======

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''((Tudíž
''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)).


===== Implementace =====

Nebudeme po vás chtít implementaci, která kompletně kopíruje rozhraní
''std::set'', stačí podmnožina popsaná tímto útržkem:
<code cpp>
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);
</code>
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í
{{:courses:b6b36pjc:ukoly:flatset.zip|zde}}.

Odevzdejte hlavičkový soubor ''flatset.hpp'', ve kterém implementujete
''flat_set''.

===== Rady =====

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šit((Pro
zajímavost, soubor s referenčním řešením má 150 řádků)).

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.

==== Porovnání prvků ====

''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*}


==== Defaultní argumenty pro argumenty šablon ====

Podobně jako u argumentů funkce, argumenty šablon mohou mít výchozí
hodnoty, které se použijí, pokud uživatel explicitně nespecifikuje jinou:
<code cpp>
#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
}
</code>


==== Range constructor ====

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).

==== Užitečné hlavičky ====

Silně doporučujeme prohlédnout si
  * [[http://en.cppreference.com/w/cpp/header/vector|<vector>]]
  * [[http://en.cppreference.com/w/cpp/header/algorithm|<algorithm>]]
  * [[http://en.cppreference.com/w/cpp/header/functional|<functional>]]

===== Hodnocení =====

<HTML><style>
.content table td, .content table th {
    padding: 0.20em 0.75em;
}
</style></HTML>

^ **Sekce**                       ^ Body ^
| Základní funkcionalita                              | 2.5  |
| Správné zacházení s referencemi                     | 0.5  |
| Správná algoritmická složitost operací((Vyžaduje optimalizovaný range constructor))              | 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.