===== Úkol 2 (Flatset) =====

Úkol 2 je implementace šablonového flatsetu v STL stylu.

Oproti ''std::set'' i ''std::unordered_set'', ''flat_set'' potřebuje méně paměti,
ale má horší asymptotickou složitost pro insert a erase.

''flat_set'' funguje tak, že si interně udržuje seřazené pole obsahující všechny
prvky uvnitř. To znamená, že když hledáme prvek, tak můžeme použít binární
vyhledávání, tudíž ''flat_set::find'' má stejnou logaritmickou složitost jako
''std::set'' (ale v praxi je rychlejší). Znamená to ale taky, že asymptotická
složitost ''flat_set::insert'' i ''flat_set::erase'' je lineární((Tudíž ''flat_set''
je vhodný pro případy, kdy potřebujeme často iterovat a hledat, ale ne měnit
jaké prvky set obsahuje)).


==== Implementace ====
Nebudeme po vás chtít implementaci která je kompletně kompatibilní se ''std::set'',
stačí následující podmnožina:
<code cpp>
/**
 * Note that when the value of an element is changed so that the comparator orders it differently, the behavior is undefined.
 */
template <typename T, typename Comparator>
class flat_set {
public:
    // These types need to be accesible from the outside:
    // iterator
    // const_iterator
    // size_type
    // value_type

    // Special member functions
    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();
    // Constructs flat_set from elements in range [first, last)
    template <typename InputIterator>
    flat_set(InputIterator first, InputIterator last);
    template <typename InputIterator>
    flat_set(InputIterator first, InputIterator last, Comparator const& cmp);


    // Insert overloads
    std::pair<iterator, bool> insert(T const& v);
    std::pair<iterator, bool> insert(T&& v);
    // Inserts [first, last) range of elements
    template <typename InputIterator>
    void insert(InputIterator first, InputIterator last);

    // Erase overloads
    // Deletes element pointed-to by i, returns iterator to the next element
    iterator erase(const_iterator i);
    // Deletes elements in range [first, last), returns iterator to the next element
    iterator erase(const_iterator first, const_iterator last);
    // Deletes element equal to key if it is present, returns how many elements were deleted
    size_type erase(value_type const& key);

    // Iterator member functions
    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;

    // The usual queries
    bool empty() const;
    size_type size() const;
    size_type capacity() const;

    void reserve(size_type c);
    void clear();

    // Lookup member functions
    // Returns iterator to element equivalent to v, or an end iterator if such element is not present
    iterator find(T const& v);
    const_iterator find(T const& v) const;

    // Returns iterator to first element that is not less than t, end iterator if no such element is present
    iterator lower_bound(T const& t);
    const_iterator lower_bound(T const& t) const;

    // Returns iterator to first element that is greater than t, end iterator if no such element is present
    iterator upper_bound(T const& t);
    const_iterator upper_bound(T const& t) const;

    void swap(flat_set& o);
};

// Lexicographical comparisons
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);

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

==== Co odevzdat? ====

''.hpp'' soubor ve kterém implementujete ''flat_set''.

===== Rady =====
Implementaci si buďto můžete udělat velmi snadnou, nebo velmi složitou.
Doporučujeme začít rozmyšlením si, jak si implementaci udělat jednoduchou.

==== Porovnání prvků ====
''flat_set'' má k dispozici buďto ''operator<'' nebo speciální komparátor,
který se stejným způsobem chová. Pro ''flat_set::insert'' a ''flat_set::find'',
je ale potřeba porovnání na rovnost (aby se nevyskytovaly duplictní prvky).
Standardní knihovna pro tyto účely předpokládá, že ''a == b'' iff
''!(a < b)'' a ''!(b < a)''.


==== Defaultní argumenty pro argumenty šablon ====
Argumenty šablon mohou mít hodnotu která se použije, pokud není jiná specifikovaná:
<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>


==== 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>]]