Templatovací magie: řešení sedmého progtestu PA2 2021 v jedné funkci

unix
cpp
templates

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