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.

C++11 standard library threads with MinGW

When trying to compile a C++11-enable application under MinGW, I ran into a strange error.

bougabouga.cpp:42:1: error: 'mutex' in namespace 'std' does not name a type

What ? Did my fellow programmer, who gave me this code, made a typo ? Or forgot to #include some files ? Not at all. Let's consider this simple piece of code :

#include <mutex>
std::mutex mutex;

Well, isn't that something simple. But still, it won't compile, complaining about this missing std::mutex we just added to the namespace chain. So let's see what happens in this header file :

On line 50, we may have found our culprit :

#if defined(_GLIBCXX_HAS_GTHREADS) && defined(_GLIBCXX_USE_C99_STDINT_TR1)

This macro wraps the entire source file. So, do we have them ? The answer is yes, we have this stdint macro, but no, we don't have GNU threads. Simply because MinGW has no support for these. So instead of issuing an error, this header file happily discards all its content. This is unexpected behaviour, but it will be helpful when the time comes to make a workaround for that.

And this workaround is, as always, to rely on good ol' boost. Many classes of the standard thread library (If not all, but I did not have read the specs) can be easily replaced with the boost ones. So, a fix header file would look like that :

#include <boost/thread.hpp>

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


Isn't that pretty ? You don't even have to change your code. Now you have several options : either you add it to a central header file (If you're the StdAfx.h type, you're lucky), or you add it either manually or with a script to your source files, or you modify your gcc header files (they are useless anyway). Keep in mind that you will still need to add the boost thread library at link time.

You may want to follow me on twitter.

libnoise MinGW builds

Libnoise is an open-source noise-generating library for c++. I needed a build for a MinGW project, but unfortulately, for windows users, the homepage says it's buildable under "Microsoft Visual C++ 5.0 under Microsoft Windows 2000 Service Pack 4". MinGW users can get lost.

Actually using MSYS and some tweaking it's easy to build it using gcc and pals.

The DLL is available for download here : http://www.unix-junkies.org/kbok/libnoise-0.3.dll

For the curious, here's how I did it:
 - Install MinGW, libtool, and bash.
 - Remove the last line in src/Makefile (The include thing) This is a hack, and isn't necessary to build.
 - Rename the library name to give it a proper DLL extension. A replace-all will do.
 - Do a mingw32-make and let make crash miserably in the include/ dir. At that time the DLL will already be there, so we don't care anymore.

You may want to follow me on twitter.