Differences

This shows you the differences between two versions of the page.

--- courses:b6b36pjc:ukoly:flatset [2018/09/29 23:27]
horenmar removed
+++ courses:b6b36pjc:ukoly:flatset [2018/12/18 00:13]
horenmar Autoupdate to version 9c79607
@@ Line 2: / Line 2: @@
 {{page>courses:b6b36pjc:styles#ukoly&noheader&nofooter}}
-===== Flatset =====
+====== Flatset ======
-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,
+Poslední povinný domácí úkol bude implementace datové struktury, které se
-ale má horší asymptotickou složitost pro insert a erase.
+ří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ší.
-''flat_set'' funguje tak, že si interně udržuje seřazené pole obsahující všechny
+Interně ''flat_set'' funguje tak, že si udržuje seřazené pole obsahující
-prvky uvnitř. To znamená, že když hledáme prvek, tak můžeme použít binární
+všechny prvky. To znamená, že pokud hledáme nějaký prvek, můžeme použít
-vyhledávání, tudíž ''flat_set::find'' má stejnou logaritmickou složitost jako
+binární vyhledávání. Znamená to ale taky to, že asymptotická složitost
-''std::set'' (ale v praxi je rychlejší). Znamená to ale taky, že asymptotická
+''flat_set::insert'' i ''flat_set::erase'' je lineární a ne logaritmická
-složitost ''flat_set::insert'' i ''flat_set::erase'' je lineární((Tudíž ''flat_set''
+jako u ''std::set::insert'', respektive ''std::set::erase''((Tudíž
-je vhodný pro případy, kdy potřebujeme často iterovat a hledat, ale ne měnit
+''flat_set'' je vhodný pro případy, kdy se bude často hledat a iterovat,
-jaké prvky set obsahuje)).
+ale nevhodný pro případy, kdy se často mění jeho obsah)).
-==== Implementace ====
+===== Implementace =====
-Nebudeme po vás chtít implementaci která je kompletně kompatibilní se ''std::set'',
-stačí následující podmnožina:
+Nebudeme po vás chtít implementaci, která kompletně kopíruje rozhraní
+''std::set'', stačí podmnožina popsaná tímto útržkem:
 <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:
+    using iterator = ...;
-    // iterator
+    using const_iterator = ...;
-    // const_iterator
+    using size_type = ...;
-    // size_type
+    using value_type = ...;
-    // value_type
-    // Special member functions
+    // Speciální member funkce se chovají běžným stylem
     flat_set();
     flat_set(Comparator const& cmp);
@@ Line 41: / Line 39: @@
     flat_set& operator=(flat_set && rhs);
     ~flat_set();
-    // Constructs flat_set from elements in range [first, last)
+    // 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);
@@ Line 48: / Line 48: @@
-    // Insert overloads
+    // 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);
-    // Inserts [first, last) range of elements
+    // Vloží prvky z [first, last), alokuje pouze jednou pokud je to možné
     template <typename InputIterator>
     void insert(InputIterator first, InputIterator last);
-    // Erase overloads
+    // Smaže prvek na který ukazuje i, vrátí iterátor k dalšímu prvku
-    // 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
+    // Smaže všechny prvky z [from, to), vrátí iterátor k dalšímu prvku
-    iterator erase(const_iterator first, const_iterator last);
+    iterator erase(const_iterator from, const_iterator to);
-    // Deletes element equal to key if it is present, returns how many elements were deleted
+    // 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);
-    // Iterator member functions
+    // Běžné funkce k vytvoření iterátorů
     iterator begin() noexcept;
     iterator end() noexcept;
@@ Line 71: / Line 73: @@
     const_iterator cend() const noexcept;
-    // The usual queries
     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();
-    // Lookup member functions
+    // Vrátí iterátor ukazující na prvek ekvivalentní s v, nebo end(),
-    // Returns iterator to element equivalent to v, or an end iterator if such element is not present
+    // pokud takový prvek není uvnitř setu
     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
+    // 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;
-    // Returns iterator to first element that is greater than t, end iterator if no such element is present
+    // 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);
 };
-// Lexicographical comparisons
+// 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);
-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<''
+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? ====
+Odevzdejte hlavičkový soubor ''flatset.hpp'', ve kterém implementujete
+''flat_set''.
-''.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.
+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á. Pro ''flat_set::insert'' a ''flat_set::find'',
+''flat_set'' má k dispozici buďto ''operator<'', nebo speciální komparátor,
-je ale potřeba porovnání na rovnost (aby se nevyskytovali duplictní prvky).
+který se stejným způsobem chová. To znamená, že se nemůžete spolehnout
-Standardní knihovna pro tyto účely předpokládá, že ''a == b'' iff
+na existenci ''operator=='' u vašeho prvku, a musíte si vystačit s ''<''.
-''!(a < b)'' a ''!(b < a)''.
+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 ====
-Argumenty šablon mohou mít hodnotu která se použije, pokud není jiná specifikovaná:
+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>
@@ Line 148: / Line 174: @@
 ==== 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í              | 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.