Templatovací magie: řešení sedmého progtestu PA2 2021 v jedné funkci
Written on .
Zadání vypadá celkem jednoduše. Napsat třídu, která se bude chovat analogicky k běžnému vektoru, a bude umět .begin(), , , , a , které spočítá minimum na nějakém intervalu dvou iterátorů. A k tomu ještě konstruktory defaultní, s komparátorem, s iterátory, a s iterátory a komparátorem. Člověk by řekl, že k tomu bude muset implementovat alespoň šest funkcí a nějaké konstruktory. Ale není tomu tak. Ve skutečnosti jde celá úloha splnit napsáním pouze jedné jediné funkce.
Naivní řešení není těžké napsat, v podstatě to vypadá nějak takhle:
template<typename T, typename Cmp = std::less<T>><br/>class CIntervalMin <br/>{<br/> vector<T> data;<br/> Cmp comparator;<br/><br/> public:<br/> using const_iterator = typename std::vector<T>::const_iterator;<br/><br/> // default constructor<br/> CIntervalMin() {}<br/> // constructor with comparator<br/> CIntervalMin(const Cmp & comparator) : comparator(comparator) {}<br/> // constructor - 2 iterators <br/> CIntervalMin(const_iterator begin, const_iterator end) {<br/> while(begin != end) push_back(*(begin++));<br/> }<br/> // constructor - 2 iterators + comparator<br/> CIntervalMin(const_iterator begin, const_iterator end, const Cmp & comparator) : comparator(comparator) { <br/> while(begin != end) push_back(*(begin++));<br/> }<br/> <br/> // push_back<br/> CIntervalMin & push_back(const T & val) {<br/> data.push_back(val);<br/> return *this;<br/> }<br/> // pop_back<br/> T pop_back() {<br/> T val = std::move(data.back());<br/> data.pop_back();<br/> return val;<br/> }<br/> // min<br/> T min(const_iterator st, const_iterator en) const {<br/> if (st == en) throw std::invalid_argument("invalid iterator query");<br/><br/> T min = *st;<br/> while (++st != en) {<br/> if (comparator(*st, min)) min = *st;<br/> }<br/> <br/> return min;<br/> }<br/> // begin<br/> const_iterator begin() const {<br/> return data.begin();<br/> }<br/> // end<br/> const_iterator end() const {<br/> return data.end();<br/> }<br/> // size<br/> size_t size() const {<br/> return std::distance(data.begin(), data.end());<br/> }<br/>};<br/>Vidíme, že spousta těhlech funkcí je triviálních, a v podstatě kopíruje to, jak s daty pracuje vektor. Tak proč si to trochu neulehčit? Pomocí dědění se můžeme zbavit většiny funkcí! Zároveň můžeme pro hledání minima použít std::min_element, což zase ušetří trochu psaní.
template<typename T, typename Cmp = std::less<T>><br/>class CIntervalMin : public std::vector<T><br/>{<br/> Cmp comparator;<br/><br/>public:<br/> using const_iterator = typename std::vector<T>::const_iterator;<br/><br/> // default constructor<br/> CIntervalMin() {}<br/> // constructor with comparator<br/> CIntervalMin(const Cmp & comparator) : comparator(comparator) {}<br/> // constructor - 2 iterators <br/> CIntervalMin(const_iterator begin, const_iterator end) : std::vector<T>(begin, end) { }<br/> // constructor - 2 iterators + comparator<br/> CIntervalMin(const_iterator begin, const_iterator end, const Cmp & comparator) : std::vector<T>(begin, end), comparator(comparator) { }<br/> <br/> // min<br/> T min(const_iterator st, const_iterator en) const {<br/> if (st >= en) throw std::invalid_argument("invalid iterator query");<br/><br/> return *std::min_element(st, en, comparator);<br/> }<br/>};<br/>Využili jsme toho, že dědíme z vektoru, takže push_back, , , , (a další, které ale nejsou potřeba) jsou magicky implementované za nás, a nemusíme je vůbec řešit. Tedy potřebujeme sami psát už jenom funkci pro výpočet minima, což neumí vektor jako takový, a konstruktory.
Tak to by bylo, jak to ale stáhnout na míň funkcí? Třeba u konstruktoru toho pořád píšeme opravdu hodně. A to se nám nelíbí! Vždyť můžeme použít defaultní parametry.
template<typename T, typename Cmp = std::less<T>><br/>class CIntervalMin : public std::vector<T><br/>{<br/> Cmp comparator;<br/><br/>public:<br/> using const_iterator = typename std::vector<T>::const_iterator;<br/><br/> CIntervalMin(const Cmp & comparator = Cmp()) : comparator(comparator) {}<br/> CIntervalMin(const_iterator begin, const_iterator end, const Cmp & comparator = Cmp()) : std::vector<T>(begin, end), comparator(comparator) { }<br/> <br/> // min<br/> T min(const_iterator st, const_iterator en) const {<br/> if (st >= en) throw std::invalid_argument("invalid iterator query");<br/><br/> return *std::min_element(st, en, comparator);<br/> }<br/>};<br/>Tak a je to, sedmá progtestová úloha na tři funkce. To už musí stačit, že? narrator: it didn't.
Existuje způsob, jak počet funkcí zredukovat ještě o trochu víc. Na dvě funkce se můžeme dostat ještě vcelku normálním způsobem. Postupně: konstruktory nemůžeme odstranit, ani první ani druhý. Přes defaultní parametry to už obejít nepůjde, protože nemůžeme vynechat jenom některé. A minimum. Hmmmm. To přece nemusí být funkce! On by nám stačil i funktor, volat to půjde i tak. A funktor není funkce. Takže na dvě funkce to můžeme zkrátit následovně, pomocí lambda funkce.
// min<br/>std::function<T (const_iterator st, const_iterator en)> min =<br/> [&](const_iterator st, const_iterator en) -> T {<br/> if (st >= en) throw std::invalid_argument("invalid iterator query");<br/><br/> return *std::min_element(st, en, comparator);<br/> };<br/>V tuto chvíli min už není funkce, ale proměnná. Sice jde volat identicky k normální funkci, ale funkce to vlastně není!
Tak, a co dál. Technicky vzato máme dvě funkce - a to dva konsturktory. A těch se už přece nemůžeme zbavit, vždyť mají jiné parametry. Leda bychom začali templatovat.
Použijeme něco, čemu se říká variadic template, a v podstatě nám umožní vytvořit template s předem neznámým počtem parametrů. Třeba tato funkce vezme libovolný počet libovolných parametrů.
template <typename ... Ts><br/>void foo(Ts ... args) {<br/> // ...<br/>}<br/><br/>// Valid calls:<br/>foo(1);<br/><br/>foo(2.4f);<br/><br/>foo("abc", 1, 3, "def");<br/><br/>foo(main, [](){});<br/><br/>foo();<br/>Využijeme to k tomu, abychom konstruktor, které bere různé parametry, napsali pomocí jedné jediné funkce.
Problém je v tom, jak variadic templaty použít. Běžně bychom totiž udělali různé přetížení funkce, které by byly schopné zpracovat jednotlivé použití, nebo VA_PARAMS, které ovšem nemáme kvůli omezení úlohy k dispozici. Takže jak (kvůli progtestu) tak funkce (kvůli tomu, že chceme použít jen jednu) nemůžeme použít. Specializace templatů se ale dají aplikovat nejenom na funkce, ale dokonce i na struktury. Takže to bude vypadat nějak takto.
// ctor<br/>template <typename ... Ts><br/>CIntervalMin(Ts ... args) : std::vector<T>() {<br/> // TODO: What to do here??<br/>}<br/>Přidáme strukturu, která bude každá obsahovat jeden funktor definovaný lambda funkcí. S tím, že každá konkrétní struktura se zavolá v závislosti na tom, jaké parametry náš konstruktor dostane.
template <typename ... Args><br/>struct ctorStruct { };<br/><br/>// default ctor (tato struktura se vytvoří, když `... Ts` nebude obsahovat žádný parametr<br/>// (list template typů bude prázdný)<br/>template<> struct ctorStruct<> {<br/> std::function<void ()> construct =<br/> [&]() {<br/> // ???<br/> };<br/>};<br/><br/><br/>// (cmp) ctor (vytvoří se, když `... Ts` obsahuje právě jeden parametr, který pojmenujeme Cmp)<br/>template<typename Cmp> struct ctorStruct<Cmp> {<br/> std::function<void (const Cmp & cmp)> construct =<br/> [&](const Cmp & cmp) {<br/> // ???<br/> };<br/>};<br/><br/>// (it, it) ctor<br/>template<typename It> struct ctorStruct<It, It> {<br/> std::function<void (const It & beg, const It & end)> construct =<br/> [&](const It & beg, const It & end) {<br/> // ???<br/> };<br/>};<br/><br/>// (it, it, cmp) ctor<br/>template<typename It, typename Cmp> struct ctorStruct<It, It, Cmp> {<br/> std::function<void (const It & beg, const It & end, const Cmp & cmp)> construct =<br/> [&](const It & beg, const It & end, const Cmp & cmp) {<br/> // ???<br/> };<br/>};<br/><br/>// ...<br/><br/> template <typename ... Ts><br/> CIntervalMin(Ts ... args) : std::vector<T>() {<br/> // expanduje se podle toho, jak byl konstruktor zavolaný.<br/> // CIntervalMin<std::less<int>>(std::less<int>()) způsobí expandování na<br/> // ctorStruct<std::less<int>>().construct(std::less<int>()). Legální jsou i<br/> // expandování na nula, nebo více prvků.<br/> ctorStruct<Ts...>().construct(args...);<br/> }<br/>Tohle je ta základní myšlenka. Variadic template a argument se expandují, a vytvoří se jedna ze čtyř struktur, které už obsahují funktor, který je schopný zpracovat expandované argumenty. Po troše hackování toho, aby ctor struktura mohla zapisovat do samotného objektu a obcházení toho, že comparator nemusí mít defaultní konstruktor, dojdeme k finálnímu kódu:
/// Struct used to manipulate with CIntervalMin<br/>template <typename T, typename Cmp><br/>struct CIntMinPs {<br/> /// Pointer to vector, containing nothing, or exactly one<br/> /// instance of Cmp. The instance may not have default ctor<br/> /// and we don't have access to std::optional, so it is<br/> /// used like this.<br/> std::vector<Cmp> * cmpPointer;<br/> std::vector<T> * vecPointer;<br/>};<br/><br/>template <typename ... Args><br/>struct ctorStruct { };<br/><br/>template<typename T, typename Cmp> struct ctorStruct<T, Cmp> {<br/> std::function<void (const CIntMinPs<T, Cmp> & ps)> construct =<br/> [&](const CIntMinPs<T, Cmp> & ps) {<br/> ps.cmpPointer->push_back(Cmp());<br/> };<br/>};<br/><br/>// (we need two types for comparator, as comparator in constructor might<br/>// not be the same type as the one that is stored in our class, when it<br/>// is cast-able into the target type - for example lambda function -> functor)<br/>template<typename T, typename Cmp, typename Cmp_> struct ctorStruct<T, Cmp, Cmp_> {<br/> std::function<void (const CIntMinPs<T, Cmp> & ps, const Cmp & cmp)> construct =<br/> [&](const CIntMinPs<T, Cmp> & ps, const Cmp & cmp) {<br/> ps.cmpPointer->push_back(cmp);<br/> };<br/>};<br/><br/>template<typename T, typename Cmp, typename It> struct ctorStruct<T, Cmp, It, It> {<br/> std::function<void (const CIntMinPs<T, Cmp> & ps, const It & beg, const It & end)> construct =<br/> [&](const CIntMinPs<T, Cmp> & ps, const It & beg, const It & end) {<br/> ps.cmpPointer->push_back(Cmp());<br/> std::copy(beg, end, std::back_inserter(*(ps.vecPointer)));<br/> };<br/>};<br/><br/>template<typename T, typename Cmp, typename It, typename Cmp_> struct ctorStruct<T, Cmp, It, It, Cmp_> {<br/> std::function<void (const CIntMinPs<T, Cmp> & ps, const It & beg, const It & end, const Cmp & cmp)> construct =<br/> [&](const CIntMinPs<T, Cmp> & ps, const It & beg, const It & end, const Cmp & cmp) {<br/> ps.cmpPointer->push_back(cmp);<br/> std::copy(beg, end, std::back_inserter(*(ps.vecPointer)));<br/> };<br/>};<br/><br/>template<typename T, typename Cmp = std::less<T>><br/>class CIntervalMin : public std::vector<T><br/>{<br/> std::vector<Cmp> cmp;<br/><br/>public:<br/> using const_iterator = typename std::vector<T>::const_iterator;<br/><br/><br/> template <typename ... Ts><br/> CIntervalMin(Ts ... args) : std::vector<T>() {<br/> // we need to send our vector. Better solution might be to send<br/> // constructed back_inserter instead of doing this.<br/> ctorStruct<T, Cmp, Ts...>().construct(CIntMinPs<T, Cmp>{&cmp, dynamic_cast<std::vector<T>*>(this)}, args...);<br/> }<br/><br/> std::function<T (const const_iterator & beg, const const_iterator & end)> min = <br/> [&](const const_iterator & beg, const const_iterator & end) -> T {<br/> if (end <= beg) throw std::invalid_argument("invalid iterator query");<br/> return *std::min_element(beg, end, cmp[0]); <br/> };<br/>};<br/>A to nám stačí. Sedmý progtest, pomocí jedné funkce.