Posts Tagged ‘Metaprogramming’

Some general-purpose algorithms accept a range (e.g. two iterators) and an additional value. For example std::iota fills the specified range with sequentially increasing values, starting with a certain value V and repetitively evaluating ++V:


vector<int> aVector (5);

iota ( begin(aVector), end(aVector), 1);

// aVector is {1, 2, 3, 4, 5}

This algorithm is really simple, but how is it possible to operate on the initial value in a quite generic way? Suppose we want to reuse iota to fill the range with increasing squared values, e.g.: {1, 4, 9, 16, 25}.

Since iota accepts nothing but a value in the range, we cannot pass, say, a lambda. We have to feed it with a special value or something like that. A mimesis object (explained in Advanced C++ Metaprogramming, by Davide Di Gennaro) is something we may take inspiration from. Actually, according to Davide’s definition, a mimesis for a type T is a unary predicate that behaves like an instance of T. It generally implements operator==(const T&), operator!=(const T&) and operator “cast to T”. In other words if M is a mimesis for type T, then the fundamental property for M is:


M<T> m;

assert(m == static_cast<T>(m));

A simple example is a mimesis that identifies positive numbers:


template <typename scalar_t>;
struct positive
{
 bool operator==(const scalar_t& x) const
 {
    return x>0;
 }

 operator scalar_t() const
 {
    return 1; // an arbitrary positive number
 }
};

template <typename scalar_t>;
inline bool operator==(const scalar_t& x, const positive<scalar_t>& p)
{
    return p == x;
}

...
double arr[] = {-1.0, 2.5, 5.0};
auto it = std::find(arr, arr + 3, positive<double>()); // 2.5

With mimesis, we could unify algorithms (e.g. in the previous example we don’t need find_if anymore). You’re right, a mimesis takes more effort than a lambda, but it’s worth especially for generalizing functions that take a special value as an argument (I suggest you to read, for example, the “End of range” section in Davide’s book).

Ok, this was a very short intro. Back to our problem: How to use mimesis to generalize iota? Let’s have a look at a possible implementation of iota:

template<class ForwardIterator, class T>
void iota(ForwardIterator first, ForwardIterator last, T value)
{
    while(first != last) {
        *first++ = value;
        ++value; // pre-increment operator
    }
}

Suppose value is a mimesis that initially stores a certain int (say 1). The mimesis have to be able to perform two operations:

  • pre-increment (for line 6)
  • cast to int (for line 5)

My idea is to create a generic mimesis “holder” for iota that receives a function that performs the user’s operation, and which result will be casted to T (but you can extend it, for example, by providing also a pre-increment function):


template<typename T, typename MainFn>
struct iota_mimesis_t : MainFn
{
 template<typename TT, typename FF>;
 iota_mimesis_t(TT&& aValue, FF&& aMainFn)
    : MainFn(forward<FF>(aMainFn)), value(forward<TT>(aValue))
 {}

iota_mimesis_t& operator++()
 {
    ++value; // can be generalized
    return *this;
 }

 operator T()
 {
    return MainFn::operator()(value);
 }

 T value;
};

template<typename T, typename F>
iota_mimesis_t<T,F> iota_mimesis(T&& value, F&& fn)
{
 return iota_mimesis_t<T,F>(forward<T>(value), forward<F>(fn));
}

...

vector<int> v (5);
iota ( begin(v), end(v), iota_mimesis(1, [](int anInt){ return anInt*anInt; }));
// aVector is {1, 4, 9, 16, 25}

The key point here is to grasp the internals of iota (that are easy). Different algorithms could be more complicated, but often it’s worth striving to generalize some stuff. Mimesis could be precious allies to deal with “value-only” algorithms (think of legacy code also) and mixing them with modern lambdas can generalize even further.

This succint post is just an introduction. If you spot “lambda-unable” algorithms, try to make them “lambda-able” with mimes and be generic!