CourseWare Wiki
Switch Term
Winter 2021 / 2022
Winter 2020 / 2021
Winter 2019 / 2020
Winter 2018 / 2019
Older
Search
Log In
b181
courses
b6b36pjc
ukoly
flatset
Warning
This page is located in archive. Go to the latest version of this
course pages
.
Differences
This shows you the differences between two versions of the page.
View differences:
Side by Side
Inline
Go
Link to this comparison view
Both sides previous revision
Previous revision
2018/12/31 12:50 jerabma7 Autoupdate to version 9f1ab748bf98
2018/12/18 00:13 horenmar Autoupdate to version 9c79607
2018/09/29 23:27 horenmar removed
2018/09/28 00:46 jerabma7 Autoupdate to version 067132858275
2018/09/12 12:44 external edit
Go
Next revision
Previous revision
2018/12/31 12:50 jerabma7 Autoupdate to version 9f1ab748bf98
2018/12/18 00:13 horenmar Autoupdate to version 9c79607
2018/09/29 23:27 horenmar removed
2018/09/28 00:46 jerabma7 Autoupdate to version 067132858275
2018/09/12 12:44 external edit
Go
courses:b6b36pjc:ukoly:flatset [2018/09/29 23:27]
horenmar
removed
courses:b6b36pjc:ukoly:flatset [2018/12/31 12:50]
jerabma7
Autoupdate to version 9f1ab748bf98
Line 2:
Line 2:
{{page>courses:b6b36pjc:styles#ukoly&noheader&nofooter}}
{{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>
<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>
template <typename T, typename Comparator>
class flat_set {
class flat_set {
public:
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();
flat_set(Comparator const& cmp);
flat_set(Comparator const& cmp);
Line 41:
Line 39:
flat_set& operator=(flat_set && rhs);
flat_set& operator=(flat_set && rhs);
~flat_set();
~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>
template <typename InputIterator>
flat_set(InputIterator first, InputIterator last);
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 const& v);
std::pair<iterator, bool> insert(T&& 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>
template <typename InputIterator>
void insert(InputIterator first, InputIterator last);
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);
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);
size_type erase(value_type const& key);
-
//
Iterator member functions
+
//
Běžné funkce k vytvoření iterátorů
iterator begin() noexcept;
iterator begin() noexcept;
iterator end() noexcept;
iterator end() noexcept;
Line 71:
Line 73:
const_iterator cend() const noexcept;
const_iterator cend() const noexcept;
-
// The usual queries
bool empty() const;
bool empty() const;
size_type size() const;
size_type size() const;
size_type capacity() 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);
void reserve(size_type c);
+
+
// Vymaže všechny prvky ze setu
void clear();
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);
iterator find(T const& v);
const_iterator find(T const& v) const;
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);
iterator lower_bound(T const& t);
const_iterator lower_bound(T const& t) const;
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);
iterator upper_bound(T const& t);
const_iterator upper_bound(T const& t) const;
const_iterator upper_bound(T const& t) const;
+
// Prohodí obsah dvou setů (včetně komparátoru)
void swap(flat_set& o);
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);
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>
template <typename T>
void swap(flat_set<T> const& a, flat_set<T> const& b);
void swap(flat_set<T> const& a, flat_set<T> const& b);
</code>
</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í
Potřebné hlavičkové soubory a testy ke stažení
{{:courses:b6b36pjc:ukoly:flatset.zip|zde}}.
{{: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 =====
===== 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ů ====
==== 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 ====
==== 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>
<code cpp>
#include <iostream>
#include <iostream>
Line 146:
Line 171:
</code>
</code>
+
+
==== Range constructor ====
+
+
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).
==== Užitečné hlavičky ====
==== Užitečné hlavičky ====
+
Silně doporučujeme prohlédnout si
Silně doporučujeme prohlédnout si
* [[http://en.cppreference.com/w/cpp/header/vector|<vector>]]
* [[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/algorithm|<algorithm>]]
* [[http://en.cppreference.com/w/cpp/header/functional|<functional>]]
* [[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í((Vyžaduje optimalizovaný range constructor)) | 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.
courses/b6b36pjc/ukoly/flatset.txt
· Last modified: 2018/12/31 12:50 by
jerabma7