Making functions: How to provide a simple interface when working with std::function

While working on the lundi project, a minor, but not negligible, issue arose: How can we spare the user from producing manually all those std::functions from their callable objects?

The hypothetical expose function template takes std::function<R(P...)> and exposes them to the lua VM. A typical use case would be:

std::function<void(int, int)> lamarck = [](int a, int b){ 
  std::cout << a << b; 
};
expose(lamarck);

That's nice and all, but why do you need to write the signature of the function you just typed? That's redundant. The thing is, lambdas are actually function objects. The preceding lambda declaration is roughly equivalent to

struct blanche {
  void operator()(int a, int b) const { 
    std::cout << a << b; 
  }
};
std::function<void(int, int)> lamarck = blanche();

Note the braces; we're not assigning a type here.

Now, we could put pretty much anything in function objects; the only thing that makes them function objects are the presence of operator(). That would be insane, of course, to provide an implicit conversion to std::function.

Nobody is keeping you from doing it, though:

template<typename R, typename... P>
std::function<R(P...)> make_function(R(func const &)(P...)) {
  return std::function<R(P...)>(func);
}

Well, that's the easy part, but what about function objects? You can't just match a function object's call signature because it's not easily accessible. You can, though, look at his operator() to work out the parameter and return types. Note that it's not possible if operator() is a template or if it's overloaded.

This is where decltype is useful:

typedef decltype(&T::operator()) ptmf_type;

ptmf_type should look (in the case of void(int, int)) like void (mytype::*)(int, int) const, which can be matched in a template to extract all the needed types. We might as well work out directly the function type:

template<typename T>
struct ptmf_traits {
  typedef void type;
};

template<typename O, typename R, typename... P>
struct ptmf_traits<R(O::*)(P...) const> {
  typedef std::function<R(P...)> type;
};

Now, you can just use ptmf_traits<decltype(&LambdaType::operator())>::type to get a function type:

template<typename Func>
ptmf_traits<decltype(&Func::operator())>::type 
make_function_from_lambda(Func const &func) {
  return func;
}

With this function, the type of the std::function produced is fully deduced from the argument type:

auto my_func = make_function_from_lambda([](int a, int b){
  std::cout << a << b;
});
// my_func's type is std::function<void(int, int)>

Of course, you need a bit of boilerplate to accept free functions and maybe some tweaking to make it do what you want, but the core idea is there. You can find a more complete version here.

You may want to follow me on twitter.

Pixel art : some updates

I've been working lately on the pixel art vectorization algorithm described by the guys at MS research.

My first attempt was available on my Github, featured some awesome characteristics such as terrible performance, ugly memory management and was basically not working. I decided to delete it, start over and adopt a more thoughtful approach.

A detailed analysis of the properties of the algorithm reveals that many steps can be cut and that some processing just boils down to very simple operations on integers. The code is still ugly but the early steps are now lightning fast. I'm still having a hard time minimizing processing time, so the work is far from being finished, but I thought it would be nice to show some results obtained so far. The picture on the left is an upscale of the original image, and the one on the right is the simplified voronoi partition of the pixels after the transformation. Each cell is a pixel. (No colors, sorry.)

In the process of debugging the output, I found the method of outputting SVG via iostreams to be super handy. A simple refresh on the browser and there it goes, no need to mess with a UI tooklit with windows, events and stuff. The only downside is that I use Inkscape to look at details and it's too damn slow. I should write a little something about that later.

You may want to follow me on twitter.

Automatic zero-initialization of C++ class instances

C++ has a very nice but not well-known feature letting you initialize a class-type object with a bunch of zeroes. It's called zero-initialization, and happens when you call for value-initialization on a class-type which does not have a user-defined constructor.

The reason it is not well-known, is simply because it is not fully implemented by some compilers widely used in the industry (namely MSVC). This is a shame, because it's a very easy way to quickly switch to dumb old C calloc/memset'd structures to classes.

void snaflu() {
  my_huge_struct *huge = static_cast(calloc(1, 
      sizeof(my_huge_struct)));
  // ...
}

void snaflu2() {
  my_huge_struct *huge = new my_huge_struct();
  // This doesn't work on VS, it's the same as new my_huge_struct;
}

Doing this was a necessity for me, since we have some structs that have several hundreds fields, and writing manually an init() method or an initializer list would be, although possible, really suboptimal and would not make it through quality reviews.

That being said, the solutions I have to offer are also suboptimal and acceptable only in specific contexts. The best solution, as always, is to get a working compiler.

A first solution would be to call a placement new on initialized memory:

void snaflu() {
  my_huge_struct *huge = new (calloc(1, 
      sizeof(my_huge_struct))) my_huge_struct;
  // use...
  huge->~my_huge_struct();
  free(huge);
}

This has several advantages, the main one being that it is quite simple, and very similar to the first technique. The second is that it does not require a modification of the instanciated class.

The main drawback is that it's ugly.

The second one is that allocating arrays became suddenly super complicated :

void multiSnaflu(int count) {
  my_huge_struct *huges = new (calloc(count,
      sizeof(my_huge_struct))) my_huge_struct[count];
}

Wait, C++ doesn't have a placement-delete (or a destructor) for arrays. We would have to hand-destruct them after usage, which would imply a lot of boring stuff like keeping in memory the quantity of objects contained, and iterating upon them.
A vector would be a nicer solution, but writing an allocator is not really what one could call a "simple solution".

Another solution, more intrusive, is to overload the new-handler of your class.

struct my_huge_struct {
  void *operator new(size_t size) {
    void *mem = ::operator new(size);
    std::memset(mem, 0, size);
    return mem;
  }
};

This will initialize all scalar values to 0 before the construction of the object (as long as the bit pattern for zero is indeed 0 on your platform). All automatic members also inherits from this behavior.
Note that this is absolutely not standard, and that it works only in the sense that the constructor should take no action about your scalars.

For more lisibility, a parent class could prove useful :

struct ZeroInitialized {
  void *alloc_zero(size_t size) {
    void *mem = ::operator new(size);
    std::memset(mem, 0, size);
    return mem;
  }
  void *operator new(size_t size) { return alloc_zero(size); }
  void *operator new[](size_t size) { return alloc_zero(size); }
  // Yep, we also need this one for arrays
};

struct my_huge_struct : public ZeroInitialized {
  // ...
};

Also note that scope-bound objects will not be zero-initialized with this technique. The quick answer is to use auto_ptrs to manage the score binding. The long answer is longer, and I'm not even sure about it. I may come back on it later.

You may want to follow me on twitter.

Using reverse iterators with c++11 range-based "for" loops

The range-based for loop is a handy c++11 language construct that allows you to simply iterate over, well, anything iterable :

void makeSnaflu(const std::vector<int>& vec) {
  for(int x : vec)
    doFooBar(x);
}

Unfortunately, a sheer number of STL classes and containers allow iterating in a reverse order using reverse_iterators, but there is no support for them in the range-based for loop.


However, this could be fixed easily by creating a proxy template which uses some c++11 features. This template proxy assumes the class provides reverse iterators via rbegin() and rend(), in the same manner that the range-based for loop assumes the object passed provides begin() and end():

template<class Cont>
class const_reverse_wrapper {
  const Cont& container;

public:
  const_reverse_wrapper(const Cont& cont) : container(cont){ }
  decltype(container.rbegin()) begin() const { return container.rbegin(); }
  decltype(container.rend()) end() const { return container.rend(); }
};

template<class Cont>
class reverse_wrapper {
  Cont& container;

public:
  reverse_wrapper(Cont& cont) : container(cont){ }
  decltype(container.rbegin()) begin() { return container.rbegin(); }
  decltype(container.rend()) end() { return container.rend(); }
};

template<class Cont>
const_reverse_wrapper<Cont> reverse(const Cont& cont) {
  return const_reverse_wrapper<Cont>(cont);
}

template<class Cont>
reverse_wrapper<Cont> reverse(Cont& cont) {
  return reverse_wrapper<Cont>(cont);
}

Here decltype() is super handy when it comes to allow the rbegin() and rend() to return pretty much anything they like.


Now you can easily iterate to string in a reverse order:

std::string stressed = "stressed no tips";
for(char c : reverse(stressed))
  std::cout << c;
std::cout << std::endl;

You may want to follow me on twitter.

MinGW std::thread fix

I talked earlier about a basic fix for MinGW enabling the use of std::thread and friends in MinGW. Since I will probably use them a lot, I wrote a small header file which does the work for you. It is available on github as a gist : https://gist.github.com/1154023

Since I believe people are too lazy to click links, and also because I want my blog to appear to have a lot of code in it, you will also find it just below:

/* Only use the code below if we have GCC with no support for GNU
 * threads 
 */
#if !defined(_GLIBCXX_HAS_GTHREADS) && defined(__GNUG__)

/* The boost thread library is used as a replacement for the
 * standard thread library. We'll consider it to be fully 
 * compatible with the missing library. See http://www.open-std.org/
 * ...jtc1/sc22/wg21/docs/papers/2008/n2497.html
 */

#include <boost/thread/thread.hpp>
#include <boost/thread/mutex.hpp>
#include <boost/thread/recursive_mutex.hpp>
#include <boost/thread/locks.hpp>
#include <boost/thread/condition_variable.hpp>

/* Only classes are copied. Use boost directly or a real standard
 * library if you want free functions.
 */

namespace std {
  using boost::thread;
  
  using boost::mutex;
  using boost::timed_mutex;
  using boost::recursive_mutex;
  using boost::recursive_timed_mutex;
  
  using boost::lock_guard;
  using boost::unique_lock;
  
  using boost::condition_variable;
  using boost::condition_variable_any;
}

#endif /* Crippled GCC */

You may want to follow me on twitter.

SFINAE and type trait-based overloading, take two

Today I thought back about my previous post on SFINAE and found that this has_const_iterator dichotomy was actually quite ugly and ineffective.

First, the print_r function has two overloads based on if the argument has a const_iterator or not. In a real-world implementation, we would also check for operator[], iterator, and also the C++11-like begin() and end(), because in fact you could name you iterators whatever you like to. One should also take into account that other special types may need special treatement, like smart pointers. Are we going to add an argument to print_r() for each type we want to support ?

Secondly, the fact that there is no default specialization of the template make it looks poorly TMP-ish. Also, that char(*)[!(has_const_iterator::value)] = 0 is really ugly.

But the real problem is not here. It is that the struct has_const_iterator is actually of no use at all. One could just use the type traits directly as function arguments with default values :

template <typename T> void print_r(const T& v, 
    typename T::const_iterator* x = 0)

and

template <typename T> void print_r(const T& t, ...)

We can make a begin()/end() version by using some C++11 features :

template <typename T> void print_r(const T& v,
    decltype(v.begin())* x = 0, decltype(v.end())* y = 0) {
  // ...blah...
  for(auto iter = v.begin(); iter != v.end(); iter++) {
    // etc.

Wow, this is getting nicer !
Now the problem is that using decltypes and default arguments like that seem not to please the compilers too much. If you add other overloads, GCC will complain based on how you place the different templates, and MSVC won't know how to choose between the different 1 overloads(yes, really). We could fix that by using trait types and a set of capability-detecting functions. But I'll do that later.

You may want to follow me on twitter.

Using SFINAE to recurse into collection types

Last week, during an interview, I have been asked about TMP. The question was "How would you create a function that takes a vector and prints it to the console ? It should do so recursively."

I though about SFINAE and using type traits, but was totally unable to come up with code. I never wrote any TMP code, in fact, I just read some books and articles about it. So the interviewer came up with his solution, which was to embed to type argument into a function parameter template, and create a "default function" for built-ins. That would look like that:

template <typename T> void print_r(const T& t) {
  std::cout << t;
}
 
template <typename T> void print_r(const std::vector<T>& v) {
  typedef typename std::vector<T>::const_iterator iter_t;
  for(iter_t iter = v.begin(); iter != v.end(); iter++)
    print_r(*iter);
}

Yes, of course it works. But the problem here is that it only works for std::vector, and you would have to write such a function for every collection type in the template library. Not sexy. And C++ does not have a generic collection hierarchy like C# has (which would be stupid anyway.) Since I won't give up so easily, I wrote my code using SFINAE. These functions detects the presence of const_iterators and recurse into the collection if such a type is present :

template <typename T>
struct has_const_iterator {
  typedef char yes[1];
  typedef char no[2];
 
  template <typename C>
  static yes& test(typename C::const_iterator*);
 
  template <typename>
  static no& test(...);
  static const bool value = sizeof(test<T>(0)) == sizeof(yes);
};
 
template <typename T> void print_r(const T& t, 
    char(*)[!(has_const_iterator::value)] = 0) {
  std::cout << t;
}
 
template <typename T> void print_r(const T& v, 
    char(*)[has_const_iterator<T>::value] = 0) {
  std::cout << "[";
  typedef typename T::const_iterator iter_t;
  for(iter_t iter = v.begin(); iter != v.end(); iter++) {
        if(iter != v.begin()) std::cout << " ";
    print_r(*iter);
  }
  std::cout << "]";
}

Okay, this is longer, but much more flexible. Now we can use these function templates with pretty much any container type which has a const_iterator, even proxy or hand-made classes.
The only problem is that the char(*)[has_const_iterator::value] = 0 is quite bulky. This can be improved (but not shortened) by using enable_if from boost or the new(future) standard library.

You may want to follow me on twitter.