Poslední povinný domácí úkol bude 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í¹⁾.

Nebudeme po vás chtít implementaci která je kompletně kompatibilní se std::set, stačí následující podmnožina:

/**
 * 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);

Potřebné hlavičkové soubory a testy ke stažení zde.

.hpp soubor ve kterém implementujete flat_set.

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.

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 nevyskytovali duplictní prvky). Standardní knihovna pro tyto účely předpokládá, že a == b iff !(a < b) a !(b < a).

Argumenty šablon mohou mít hodnotu která se použije, pokud není jiná specifikovaná:

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

Silně doporučujeme prohlédnout si

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