===== Ú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:
/**
* Note that when the value of an element is changed so that the comparator orders it differently, the behavior is undefined.
*/
template
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
flat_set(InputIterator first, InputIterator last);
template
flat_set(InputIterator first, InputIterator last, Comparator const& cmp);
// Insert overloads
std::pair insert(T const& v);
std::pair insert(T&& v);
// Inserts [first, last) range of elements
template
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
void swap(flat_set const& a, flat_set 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í
{{: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á:
#include
template
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
}
==== Užitečné hlavičky ====
Silně doporučujeme prohlédnout si
* [[http://en.cppreference.com/w/cpp/header/vector|]]
* [[http://en.cppreference.com/w/cpp/header/algorithm|]]
* [[http://en.cppreference.com/w/cpp/header/functional|]]