Tuesday, August 16, 2011

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++)

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 << " ";
  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.

No comments:

Post a Comment