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¹⁾.

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();
    explicit 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);

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šit²⁾.

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

• <vector>
• <algorithm>
• <functional>

Připomínáme, že z úlohy musíte získat alespoň 40% možných bodů, tj. alespoň 2.0.