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(), .end(), .push_back(), .size(), .pop_back() a .min(), 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>>
class CIntervalMin
{
vector<T> data;
Cmp comparator;

public:
using const_iterator = typename std::vector<T>::const_iterator;

// default constructor
CIntervalMin() {}
// constructor with comparator
CIntervalMin(const Cmp & comparator) : comparator(comparator) {}
// constructor - 2 iterators
CIntervalMin(const_iterator begin, const_iterator end) {
while(begin != end) push_back(*(begin++));
}
// constructor - 2 iterators + comparator
CIntervalMin(const_iterator begin, const_iterator end, const Cmp & comparator) : comparator(comparator) {
while(begin != end) push_back(*(begin++));
}

// push_back
CIntervalMin & push_back(const T & val) {
data.push_back(val);
return *this;
}
// pop_back
T pop_back() {
T val = std::move(data.back());
data.pop_back();
return val;
}
// min
T min(const_iterator st, const_iterator en) const {
if (st == en) throw std::invalid_argument("invalid iterator query");

T min = *st;
while (++st != en) {
if (comparator(*st, min)) min = *st;
}

return min;
}
// begin
const_iterator begin() const {
return data.begin();
}
// end
const_iterator end() const {
return data.end();
}
// size
size_t size() const {
return std::distance(data.begin(), data.end());
}
};

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>>
class CIntervalMin : public std::vector<T>
{
Cmp comparator;

public:
using const_iterator = typename std::vector<T>::const_iterator;

// default constructor
CIntervalMin() {}
// constructor with comparator
CIntervalMin(const Cmp & comparator) : comparator(comparator) {}
// constructor - 2 iterators
CIntervalMin(const_iterator begin, const_iterator end) : std::vector<T>(begin, end) { }
// constructor - 2 iterators + comparator
CIntervalMin(const_iterator begin, const_iterator end, const Cmp & comparator) : std::vector<T>(begin, end), comparator(comparator) { }

// min
T min(const_iterator st, const_iterator en) const {
if (st >= en) throw std::invalid_argument("invalid iterator query");

return *std::min_element(st, en, comparator);
}
};

Využili jsme toho, že dědíme z vektoru, takže push_back, pop_back, size, begin, end (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>>
class CIntervalMin : public std::vector<T>
{
Cmp comparator;

public:
using const_iterator = typename std::vector<T>::const_iterator;

CIntervalMin(const Cmp & comparator = Cmp()) : comparator(comparator) {}
CIntervalMin(const_iterator begin, const_iterator end, const Cmp & comparator = Cmp()) : std::vector<T>(begin, end), comparator(comparator) { }

// min
T min(const_iterator st, const_iterator en) const {
if (st >= en) throw std::invalid_argument("invalid iterator query");

return *std::min_element(st, en, comparator);
}
};

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
std::function<T (const_iterator st, const_iterator en)> min =
[&](const_iterator st, const_iterator en) -> T {
if (st >= en) throw std::invalid_argument("invalid iterator query");

return *std::min_element(st, en, comparator);
};

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>
void foo(Ts ... args) {
// ...
}

// Valid calls:
foo(1);

foo(2.4f);

foo("abc", 1, 3, "def");

foo(main, [](){});

foo();

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 VA_PARAMS (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
template <typename ... Ts>
CIntervalMin(Ts ... args) : std::vector<T>() {
// TODO: What to do here??
}

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>
struct ctorStruct { };

// default ctor (tato struktura se vytvoří, když `... Ts` nebude obsahovat žádný parametr
// (list template typů bude prázdný)
template<> struct ctorStruct<> {
std::function<void ()> construct =
[&]() {
// ???
};
};


// (cmp) ctor (vytvoří se, když `... Ts` obsahuje právě jeden parametr, který pojmenujeme Cmp)
template<typename Cmp> struct ctorStruct<Cmp> {
std::function<void (const Cmp & cmp)> construct =
[&](const Cmp & cmp) {
// ???
};
};

// (it, it) ctor
template<typename It> struct ctorStruct<It, It> {
std::function<void (const It & beg, const It & end)> construct =
[&](const It & beg, const It & end) {
// ???
};
};

// (it, it, cmp) ctor
template<typename It, typename Cmp> struct ctorStruct<It, It, Cmp> {
std::function<void (const It & beg, const It & end, const Cmp & cmp)> construct =
[&](const It & beg, const It & end, const Cmp & cmp) {
// ???
};
};

// ...

template <typename ... Ts>
CIntervalMin(Ts ... args) : std::vector<T>() {
// expanduje se podle toho, jak byl konstruktor zavolaný.
// CIntervalMin<std::less<int>>(std::less<int>()) způsobí expandování na
// ctorStruct<std::less<int>>().construct(std::less<int>()). Legální jsou i
// expandování na nula, nebo více prvků.
ctorStruct<Ts...>().construct(args...);
}

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
template <typename T, typename Cmp>
struct CIntMinPs {
/// Pointer to vector, containing nothing, or exactly one
/// instance of Cmp. The instance may not have default ctor
/// and we don't have access to std::optional, so it is
/// used like this.
std::vector<Cmp> * cmpPointer;
std::vector<T> * vecPointer;
};

template <typename ... Args>
struct ctorStruct { };

template<typename T, typename Cmp> struct ctorStruct<T, Cmp> {
std::function<void (const CIntMinPs<T, Cmp> & ps)> construct =
[&](const CIntMinPs<T, Cmp> & ps) {
ps.cmpPointer->push_back(Cmp());
};
};

// (we need two types for comparator, as comparator in constructor might
// not be the same type as the one that is stored in our class, when it
// is cast-able into the target type - for example lambda function -> functor)
template<typename T, typename Cmp, typename Cmp_> struct ctorStruct<T, Cmp, Cmp_> {
std::function<void (const CIntMinPs<T, Cmp> & ps, const Cmp & cmp)> construct =
[&](const CIntMinPs<T, Cmp> & ps, const Cmp & cmp) {
ps.cmpPointer->push_back(cmp);
};
};

template<typename T, typename Cmp, typename It> struct ctorStruct<T, Cmp, It, It> {
std::function<void (const CIntMinPs<T, Cmp> & ps, const It & beg, const It & end)> construct =
[&](const CIntMinPs<T, Cmp> & ps, const It & beg, const It & end) {
ps.cmpPointer->push_back(Cmp());
std::copy(beg, end, std::back_inserter(*(ps.vecPointer)));
};
};

template<typename T, typename Cmp, typename It, typename Cmp_> struct ctorStruct<T, Cmp, It, It, Cmp_> {
std::function<void (const CIntMinPs<T, Cmp> & ps, const It & beg, const It & end, const Cmp & cmp)> construct =
[&](const CIntMinPs<T, Cmp> & ps, const It & beg, const It & end, const Cmp & cmp) {
ps.cmpPointer->push_back(cmp);
std::copy(beg, end, std::back_inserter(*(ps.vecPointer)));
};
};

template<typename T, typename Cmp = std::less<T>>
class CIntervalMin : public std::vector<T>
{
std::vector<Cmp> cmp;

public:
using const_iterator = typename std::vector<T>::const_iterator;


template <typename ... Ts>
CIntervalMin(Ts ... args) : std::vector<T>() {
// we need to send our vector. Better solution might be to send
// constructed back_inserter instead of doing this.
ctorStruct<T, Cmp, Ts...>().construct(CIntMinPs<T, Cmp>{&cmp, dynamic_cast<std::vector<T>*>(this)}, args...);
}

std::function<T (const const_iterator & beg, const const_iterator & end)> min =
[&](const const_iterator & beg, const const_iterator & end) -> T {
if (end <= beg) throw std::invalid_argument("invalid iterator query");
return *std::min_element(beg, end, cmp[0]);
};
};

A to nám stačí. Sedmý progtest, pomocí jedné funkce.

Previous Index Home
RSS feed