C++ Truths

Rvalue references in constructor: when less is more

2012-03-09T01:18:00.015-07:00

I've seen a recurring mistake made by well-versed C++03 programmers when they set out to use rvalue references for the first time. In fact, as it turns out, better you are at C++03, easier it is to fall in the trap of rvalue reference anti-pattern I'm gonna talk about.

Consider the following C++03 class:


class Book {
public:
  Book(const std::string & title,
       const std::vector<std::string> & authors,
       const std::string & pub,
       const size_t & pub_day
       const std::string & pub_month,
       const size_t & pub_year)
    : _title(title),
      _authors(authors),
      _publisher(pub),
      _pub_day(pub_day),
      _pub_month(pub_month),
      _pub_year(pub_year)
     {}

     // ....
     // ....

private:
  std::string _title;
  std::vector<std::string> _authors;
  std::string _publisher;
  size_t      _pub_day;
  std::string _pub_month;
  size_t      _pub_year;
};

The Book class above is as dull as it can be. Now lets C++11'fy it! C++11 gives us shiny new rvalue references and std::move. So lets add them.


class Book {
public:
  Book(const std::string & title,
       const std::vector<std::string> & authors,
       const size_t      & pub_day
       const std::string & pub_month,
       const size_t      & pub_year)
    : _title    (title),
      _author   (author),
      _pub_day  (pub_day),
      _pub_month(pub_month),
      _pub_year (pub_year)
     {}

  Book(std::string && title,
       std::vector<std::string> && authors,
       size_t      && pub_day
       std::string && pub_month,
       size_t      && pub_year)
    : _title    (std::move(title)),
      _authors  (std::move(authors)),
      _pub_day  (pub_day),
      _pub_month(std::move(pub_month)),
      _pub_year (pub_year)
     {}

     // ....
     // ....

private:
  std::string _title;
  std::vector<std::string> _authors;
  size_t      _pub_day;
  std::string _pub_month;
  size_t      _pub_year;
};

Is our constructor optimally move-enabled? It's far from it! More often that not, programmers' legit code will end up calling the old constructor instead of the the new one, which probably means lost opportunities for optimization. It could be hard to see what's wrong in the new class to an untrained eye. We've test it to see what's really wrong with it.


std::string & toUpper(std::string & s)
{
  std::transform(s.begin(), s.end(), s.begin(), toupper);
  return s;
}
const std::string & January()
{
  static std::string jan("January");
  return jan;
}
int main(void)
{
  std::vector<std::string> authors { "A", "B", "C" };
  Book b1("Book1", authors, 1, "Jan", 2012);   // old c-tor

  size_t year = 2012
  Book b2("Book2", { "A", "B", "C" }, 1, "Jan", year); // old c-tor

  std::string month = "Mar";
  Book b3("Book3", { "Author" }, 1, toUpper(month), 2012); // old c-tor

  Book b4("Book4", { "Author" }, 1, January(), 2012); // old c-tor

  std::string book = "Book";
  Book b5(std::move(book), std::move(authors), 1, std::move(month), year); // old-ctor

  Book b6("Book", { "Author" }, 1, "Jan", 2012); // new c-tor!
}

It may come as a surprise that in all but one case above, the old constructor is called. Only in the last case, the new-ctor is called, which makes the minimum number of copies. So what's the gotcha?

As it turns out, the Book constructors are stopping the compiler from doing a better job. The first constructor takes all the parameters as const reference and the second one takes all the parameters as rvalue reference. Unless and until all the the parameters passed to the constructor are temporary objects (rvalues) or literals, the second constructor does not kick in. This implies lost optimization opportunities for parameters that are temporary (so can be moved) but won't be moved because some other parameter botched the soup. These two constructors give you very limited options: all-or-nothing.

In case of b1, authors is an lvalue and it does not bind to an rvalue ref.
In case of b2, year is an lvalue and does not bind to an rvalue ref.
In case of b3, toUpper returns a string reference; Does no good.
In case of b4, January returns a const string reference; same story!
In case of b5, year is an lvalue that prevents calling the second constructor although programmer tries to explicitly move all the string and vector parameters. In reality, the actual moves do not happen and if the remaining program depends on the moves being successful may not be very happy.

Only in case of b6, all actual parameters are rvalues or literals. Therefore, the "all-rvalue-ref" constructor is called. Note that temporary string objects will be implicitly created where string literals are used.

So lets fix it. What we really need is just one constructor that accepts all the parameters by value. As a side-effect, the overall code is much simpler.


class Book {
public:
  Book(std::string title,
       std::vector<std::string> authors,
       size_t      pub_day
       std::string pub_month,
       size_t      pub_year)
    : _title    (std::move(title)),
      _authors  (std::move(authors)),
      _pub_day  (pub_day),
      _pub_month(std::move(pub_month)),
      _pub_year (pub_year)
     {}

  // ....
  // ....
};

That's it! This is our the constructor that works optimally. All strings, vectors, integral types are passed by value. Within the constructor, the pass-by-value parameters that are on the stack-frame must be moved to the respective data members. The reason is that the lifetime of pass-by-value parameters is anyways limited to the lifetime of the constructor call itself. We want to tie their lifetime to the object and not the constructor.

This constructor does no more deep copies of than necessary. And that number really depends on how it is called. Due to pass-by-value semantics, each object individually is an opportunity for the compiler to perform a move when a temporary is involved. Lets revisit our b1 to b4 objects.

In case of b1, except for authors all other parameters are copied and moved once.
In case of b2, all strings and vectors are copied and moved once. That's what matters.
In case of b3, toUpper returns an string reference; everything else copied and moved only once.
In case of b4, January returns a const string reference; everything else copied and moved once.
In case of b5, strings are vector are moved as expected and in fact the b5 object the local parameters are created using move-constructor and moved again into the data member. Hence the object is created without any deep copies (like zero-copy).

Using pass-by-value also opens other opportunities to eliminate temporaries when functions return by value and are used as actual parameters. However, I won't discuss that in detail here.

Finally, I want to conclude saying that this whole thing assumes that a move is much cheaper than a deep-copy. This is generally true for std::vector and std::string where memory is allocated dynamically. For small strings however small-string-optimization may make copy and move practically equivalent.

Array-like access and Iterators for Homogeneous Tuples

2012-01-22T12:31:00.012-07:00

Question often comes up whether tuples can have traditional iterators? In general, the answer is: No! They cannot. That's because tuples typically contain different types and traditional iterators, which are modeled after pointers, can not dereference to objects of multiple types. However, homogeneous tuples can have iterators. So I thought it would be a fun exercise to write one. I wonder why one would use a homogeneous tuples instead of just plain arrays. But lets do it anyways because we can.

Although this exercise sounds rather naive and unnecessary, I stumbled upon two very interesting topics along the way.

A need for new iterator concepts to separate the notions of element access from iterator traversal. Yes! iterators for homogeneous tuples can't be modeled accurately using conventional iterator categories. Don't believe me? Please read on...

How inherited constructors may be simulated on compilers that don't support them today.

From this point onward a tuple is assumed to be a homogeneous tuple. First thing we need is a way of accessing tuple's contents using a run-time integer instead of a compile-time integer. We need an adapter that uses a run-time integer index to return the n-th element in a homogeneous tuple. If n is larger than the bounds of the tuple, the adapter will throw a std::out_of_range exception.

template <typename Tuple,
        size_t I = std::tuple_size<Tuple>::value-1>
class TupleAt
{
   typedef typename std::tuple_element<0, Tuple>::type T;

 public:
   static T & get(Tuple & tuple, size_t index)
   {
     return (index == I)? std::get<I>(tuple) : TupleAt<Tuple, I-1>::get(tuple, index);
   }
};

template <typename Tuple>
class TupleAt<Tuple, 0>
{
   typedef typename std::tuple_element<0, Tuple>::type T;
 public:

   static T & get(Tuple & tuple, size_t index)
   {
     if(index == 0)
       return std::get<0>(tuple);
     else
       throw std::out_of_range("Tuple iterator dereferenced out of valid range.");
   }
};

The TupleAt template takes the type of the tuple and its size as template parameters. It assumes that the type of the first element is also the type of the rest of the elements in the tuple (i.e. a homogeneous tuple). TupleAt::get function returns a reference to the n-th element in the tuple. It does that using repeated comparisons from the size of the tuple (std::tuple_size<Tuple>::value) down to zero. TupleAt is specialized for zero so that the recursion ends. If the index does not fall in the expected range, std::out_of_range exception is thrown.

Note that this access pattern is linear in complexity. For a tuple of N elements, it may take up to N comparisons to return the right element.

Array-like access to Homogeneous Tuples

I created a tuple_array class to provide array-like access to the elements of the tuple. It uses TupleAt internally.

template <typename... T>
class tuple_array : public std::tuple<T...>
{
   typedef std::tuple<T...> Tuple;
   typedef typename std::tuple_element<0, Tuple>::type HeadType;
   enum { TUPLE_SIZE = std::tuple_size<tuple>::value };

   HeadType * ref_;
   size_t last_;

 public:
   USING(tuple_array, Tuple)
   {
     ref_ = & TupleAt<tuple>::get(*this, TUPLE_SIZE-1);
     last_ = TUPLE_SIZE-1;
   }

   HeadType & operator [] (size_t index)
   {
     if(last_ != index)
     {
       ref_ = & TupleAt<tuple>::get(*this, index);
       last_ = index;
     }
     return *ref_;
   }
};

Class tuple_array inherits from std::tuple and just provides operator [] function. It always returns a reference to HeadType typedef, which is the type of the first element in the tuple. To improve efficiency, the tuple_array class caches a pointer to the last dereferenced index in the tuple. std::tuple has a zillion constructors to create a tuple. To avoid repeating the constructors in the derived tuple_array class, I wanted to use inherited constructors. However, g++ 4.7 does not support it at this moment. So I'm using a variadic template constructor to mimic the behavior of inherited constructors.

#define USING(Dervied, Base)                                       \
     template<typename ...Args,                                   \
            typename = typename std::enable_if                    \
            <                                                     \
               std::is_constructible<Base, Args...>::value        \
            >::type>                                              \
   Dervied(Args &&...args)                                        \
       : Base(std::forward<Args>(args)...)                        \

The inherited constructor trick is captured in a macro, which I stole shamelessly from here. The USING macro defines a variadic template constructor and forwards all the arguments to the underlying base constructor. To avoid being overly greedy, it enables instantiation only if the base is constructible from the given parameters. std::is_constructible<Base, Args...>::value provides a neat way of checking that at compile-time.

Finally, we need a simple function to create the tuple_array. Function make_tuple_array is a factory function to create tuple_arrays from a list of arguments. Note how it uses the uniform initialization syntax without specifying the actual type. Using make_tuple_array is just like an array. However, note that element access is linear and not constant-time.

template <typename... T>
tuple_array<T...> make_tuple_array(T... args)
{
 return { std::forward< T&& >(args)... };
}

int main(void)
{
 auto ta = make_tuple_array(20, 30, 40);
 printf("%d %d %d", ta[0], ta[1], ta[2]); // prints 20 30 40
}

Iterators for Homogeneous Tuples

Now lets turn our attention to iterators.

What category would an iterator for homogeneous tuple belong? Random access? Bidirectional? It appears to me that the homogeneous tuple iterator could simply use an internal index to remember what position it is at and use the TupleAt::get to return the element when dereferenced. Arbitrary arithmetic can be performed in constant-time on the internal index to move the iterator. This indicates that the iterator is a random access iterator.

However, the dereference function is not constant-time as discussed earlier. As a result, it is not a random access iterator. Clearly, traversal is random access but element access is not. Existing iterator categories do not support this distinction. The standard random access iterator [5] requires all operations to be amortized constant time.

What we really need is a way to distinguish between the categories of element access and the categories of traversal. This is precisely the point of new iterator concepts in boost.

For now, we'll just consider that the iterator for homogeneous tuple is a random access iterator. Here is how it looks like with a lot of boilerplate overloaded operators.

template <typename Tuple>
class tuple_iterator 
  : public std::iterator<std::random_access_iterator_tag,
                         typename std::tuple_element<0, Tuple>::type>
{
   typedef typename std::tuple_element<0, Tuple>::type T;
   enum { TUPLE_SIZE = std::tuple_size<Tuple>::value };
 
   Tuple * tuple;
   int current_;
   int last_;
   T * ref_;

   T * update_ref()
   {
     if(current_ != last_)
     {
       ref_ = & TupleAt<Tuple>::get(*tuple, current_);
       last_ = current_;
     }
     return ref_;
   }

public:

   typedef int difference_type;

   explicit tuple_iterator(Tuple & t, int i = TUPLE_SIZE)
     : tuple(&t),
       current_(i),
       last_(i-1),
       ref_(&TupleAt<Tuple>::get(*tuple, last_))
   {}
   T & operator *() {
     return *update_ref();
   }
   T * operator ->() {
     return update_ref();
   }
   T & operator [] (int offset) {
     return TupleAt<Tuple>::get(*tuple, current_+offset);
   }
   tuple_iterator & operator ++ () {
     if(current_ < TUPLE_SIZE)
       ++current_;
     return *this;
   }
   tuple_iterator operator ++ (int) {
     tuple_iterator temp(*this);
     ++(*this);
     return temp;
   }
   tuple_iterator & operator -- () {
     if(current_ >= 0)
       --current_;
     return *this;
   }
   tuple_iterator operator -- (int) {
     tuple_iterator temp(*this);
     --(*this);
     return temp;
   }
   tuple_iterator operator - (int i) const {
     tuple_iterator temp(*tuple, current_-i);
     return temp;
   }
   tuple_iterator & operator -= (int i) {
     current_-=i;
     return *this;
   }
   tuple_iterator operator + (int i) const {
     tuple_iterator temp(*tuple, current_+i);
     return temp;
   }
   tuple_iterator & operator += (int i) {
     current_+=i;
     return *this;
   }
   difference_type operator - (const tuple_iterator & ti) const {
     return current_ - ti.current_;
   }
   bool operator < (const tuple_iterator &ti) const {
     return index < ti.index;
   }
   bool operator > (const tuple_iterator &ti) const {
     return index > ti.index;
   }
   bool operator <= (const tuple_iterator &ti) const {
     return index <= ti.index;
   }
   bool operator >= (const tuple_iterator &ti) const {
     return index >= ti.index;
   }
   bool operator == (tuple_iterator const & ti) const {
     return (tuple == ti.tuple) && (index == ti.index);
   }
   bool operator != (tuple_iterator const & ti) const {
     return !(*this == ti);
   }
};

template <>
class tuple_iterator <std::tuple<>>
{
 public:
   tuple_iterator(std::tuple<>, size_t i = 0) {}
};

The tuple_iterator class provides the usual typedefs (e.g., difference_type, value_type, pointer, reference, and iterator_category) and overloaded operators (e.g., *, ->, [], +, -, +=, -=, -, +, <, >, <=, >=, ==, !=) to support the requirements of random access iterator. Just like tuple_array class it caches a pointer to the last element that was dereferenced. It goes through O(N) comparisons only if the tuple iterator is dereferenced at a different index than what is cached. A specialization of tuple_iterator for empty tuple is also provided. It has no members other than a constructor because there is nothing to dereference to!

Finally, we need a way to create the begin and end iterator from a non-empty tuple. We add the corresponding functions.

template <typename... Args>
tuple_iterator <std::tuple<Args...>> begin(std::tuple <Args...> &t)
{
 return tuple_iterator <std::tuple<Args...>>(t, 0);
}

template <typename... Args>
tuple_iterator <std::tuple<Args...>> end(std::tuple <Args...> &t)
{
 return tuple_iterator <std::tuple<Args...>>(t);
}

If no index is passed to the iterator constructor, it points to the end of the tuple. The internal index of such an iterator is same as the size of the tuple. An iterator at the beginning has index = 0 -- the first element. Using the iterators is now straightforward. I do not discuss constant and reverse iterators here.

int main(void)
{
 auto tuple = std::make_tuple(10, 20, 30, 40);
 auto ta = make_tuple_array(4, 2, 1);

 std::copy(begin(tuple), end(tuple), std::ostream_iterator<int>(std::cout, " "));
 std::sort(begin(ta), end(ta));

 for(int i : ta)
 {
   std::cout << i << std::endl;
 }

 return 0;
}

I think, this rather naive exercise turned out to be quite interesting. Hopefully, you enjoyed as much as I did.

General-purpose Automatic Memoization for Recursive Functions in C++11

2012-01-12T00:09:00.025-07:00

Memoization is a widely known optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously processed inputs. Repeated calculations are avoided by reusing previously computed results, which must be cached such that look-up is faster than recomputing.

Consider a simple fibonacci program

unsigned long fibonacci(unsigned n)
{
  return (n < 2) ? n :  fibonacci(n - 1) + fibonacci(n - 2);
}

This algorithm is a frustratingly slow way of computing the Nth fibonacci number (N starting at 0). It does a lot of redundant recomputations. But the beauty of this program is that it is really simple. To speed it up without changing its logic significantly, we could use memoization.

Using some clever C++11 techniques, it is possible to memoize this function, which looks like below.

unsigned long fibonacci(unsigned n)
{
  return (n < 2) ? n :
       memoized_recursion(fibonacci)(n - 1) +
       memoized_recursion(fibonacci)(n - 2);
}

To solve this problem, I took inspiration from this post on automatic memoization. I'll go in lot more detail here including recursive functions and memory management. Here we go!

The memoize function I'm using is slightly different than that of the post above.

template <typename ReturnType, typename... Args>
std::function<ReturnType (Args...)>
memoize(ReturnType (*func) (Args...))
{
  auto cache = std::make_shared<std::map<std::tuple<Args...>, ReturnType>>();
  return ([=](Args... args) mutable  {
          std::tuple<Args...> t(args...);
          if (cache->find(t) == cache->end())
              (*cache)[t] = func(args...);
          return (*cache)[t];
  });
}

Function memoize accepts a pointer to a free function, wraps it in a lambda, and turns the lambda into a std::function. Returning a a std::function is a common C++11 idiom of returning a lambda from a function that creates it. The implementation of the lambda is pretty straight forward if you are familiar with C++11 variadic templates. It creates a tuple of arguments and checks if it exists in the cache. In that case, the stored result is returned instead of recomputing it. The cache used for mapping arguments to the return value, is allocated dynamically. A std::shared_ptr manages the memory. The lambda copies the std::shared_ptr by value. As long as there is at least one std::function alive, the cache will remain intact.

Memoized functions may be called from different places. It is quite cumbersome to pass the memoized function everywhere it is called. There should be a way to look up a memoized version of the function without loosing the state. So our next step is to make the same memoized function available from anywhere in the program. We need a map of function pointer to a memorized std::function. Specifically, we need a std::unordered_map for fast lookup.

template <typename F_ret, typename...  F_args>
std::function<F_ret (F_args...)>
memoized_recursion(F_ret (*func)(F_args...))
{
  typedef std::function<F_ret (F_args...)> FunctionType;
  static std::unordered_map<decltype(func), FunctionType> functor_map;

  if(functor_map.find(func) == functor_map.end())
    functor_map[func] = memoize(func);

  return functor_map[func];
}

Here I introduce "memoized_recursion" function that our recursive fibonacci function is calling. It has a static std::unordered_map. It simply looks up the memorized std::function based on the function pointer value. If it does not find one, it creates it and stores it for subsequent access. Function pointers are unique; so there are no collisions possible. Here is how to call it.

memorized_recursion(fibonacci)(10);

The solution is not finished yet though. Memoization obviously builds up state very fast. If many functions are memoized with a large number of parameters, the state grows explosively. There must be some way to reclaim the memory.

Remember that the memoized state grows in the lambda. The dynamically allocated map stores the cache for corresponding function. We need to access the object that is hidden inside a lambda. Lambda has a compiler-defined type and only thing you can do with it is call it. So how would we clear the cache it is building up?

The answer is surprisingly simple! Just assign the memoizer (the lambda) with another default initialized memoizer.

We already have memoize function, which returns a default initialized memoizer. We simply assign the new one in place of the old one. Here’s how the new memoized_recursion looks like

enum class Cache : unsigned int { NO_RECLAIM, RECLAIM };

template <typename F_ret, typename... F_args>
std::function<F_ret (F_args...)>
memoized_recursion(F_ret (*func)(F_args...), Cache c = Cache::NO_RECLAIM)
{
  typedef std::function<F_ret (F_args...)> FunctionType;
  static std::unordered_map<decltype(func), FunctionType> functor_map;

  if(Cache::RECLAIM == c)
    return functor_map[func] = memoize(func);

  if(functor_map.find(func) == functor_map.end())
    functor_map[func] = memoize(func);

  return functor_map[func];
}

I’m using strongly typed enums to pass programmer’s intent to clear the cache. Here is how you call it.

memoized_recursion(fibonacci, Cache::RECLAIM);

Purely Static Memoizer

Strictly speaking, using an std::unordered_map in memoized_recursion function is not necessary. It is an O(1) mapping of function pointers to their corresponding memoized function objects (lambda wrapped in a std::function). An alternative way of achieving the same mapping is using purely static memoizer. I call it pure because there is no dynamic allocation like in std::unordered_map. The functors are stored as static objects only. This is possible only if memoized_recursion can be specialized individually for all possible free functions! Note that each free function is guaranteed to have a unique pointer value and pointer values can be used as template parameters. So here is how to combine all these things in a static_memoizer.

template <typename Sig, Sig funcptr>
struct static_memoizer;

template <typename F_ret, typename... F_args, F_ret (*func)(F_args...)>
struct static_memoizer<F_ret (*)(F_args...), func>
{
  static 
  std::function<F_ret (F_args...)> & 
  get(Cache c = Cache::NO_RECLAIM)
  {
    static std::function<F_ret (F_args...)> mfunc (memoize(func));

    if(Cache::RECLAIM == c)
      mfunc = memoize(func);

    return mfunc;
  }
};

#define STATIC_MEMOIZER(func) static_memoizer<decltype(&func), &func>

The STATIC_MEMOIZER macro simplifies the use of the static_memoizer. It extracts the type of the function pointer using decltype and passes it (the type) as the first parameter of the template. The second parameter is the actual function pointer. Passing the function pointer as a template parameter is important because many functions potentially share the same signature but never the same pointer.

The static objects used by the static_memoizer are different from that of memoized_recursion. So we've to rewrite the fibonacci function to use the static_memoizer.

unsigned long fibonacci(unsigned n)
{
  return (n < 2) ? n :
       STATIC_MEMOIZER(fibonacci)::get()(n - 1) +
       STATIC_MEMOIZER(fibonacci)::get()(n - 2);
}

That's all for now. I hope you enjoyed it.

Multi-dimensional arrays in C++11

2011-10-11T21:59:00.012-06:00

What new can be said about multi-dimensional arrays in C++? As it turns out, quite a bit! With the advent of C++11, we get new standard library class std::array. We also get new language features, such as template aliases and variadic templates. So I'll talk about interesting ways in which they come together.

It all started with a simple question of how to define a multi-dimensional std::array. It is a great example of deceptively simple things. Are the following the two arrays identical except that one is native and the other one is std::array?

int native[3][4];
std::array<std::array<int, 3>, 4> arr;

No! They are not. In fact, arr is more like an int[4][3]. Note the difference in the array subscripts. The native array is an array of 3 elements where every element is itself an array of 4 integers. 3 rows and 4 columns. If you want a std::array with the same layout, what you really need is:

std::array<std::array<int, 4>, 3> arr;

That's quite annoying for two reasons. First of all, it is quite verbose. Think of three or higher dimensional arrays. It's just ugly. Worse yet, the array bounds must be spelled out in reverse order.

Fear not, help is on its way! Meet template aliases! It is a way of defining synonyms for other types including partially defined templates. With C++03 typedef, you must use a fully specialized template to create an alias. C++11 still has that restriction on typedefs but template aliases will let you create "typedefs" for template partial specializations. It is a C++11 solution for the Templated Typedef idiom. Lets try to write one for a two dimensional std::array.

template <class T, size_t ROW, size_t COL<
using Matrix = std::array<std::array<T, COL>, ROW>;
Matrix<float, 3, 4> mat;

This one is much nicer. Matrix is a template alias for a partial specialization of std::array. With that, defining a two dimensional matrix (mat) is really easy. Note that order of ROW and COL. An alias for two dimensional native array can also be defined similarly.

template <class T, size_t ROW, size_t COL>
using NativeMatrix = T[ROW][COL];
NativeMatrix<float, 3, 4> mat;

So far so good. Lets move on to multi-dimensional arrays. Using template aliases for arbitrary dimension arrays would need variadic templates. Unfortunately, it is not straightforward at all.

template <class T, size_t... DIMS>
using MultiDimArray = std::array<??? ...DIMS... ???>;
MultiDimArray<float, 3, 4, 5 , 6, 7> floats;

DIMS parameter pack can be expanded where a comma separated list is expected. However, multi-dimensional std::array definitions are hierarchical, which prevents straight-forward parameter pack expansion.

One way I could make it work was using a little meta-program.

template <class T, size_t I, size_t... J>
struct MultiDimArray 
{
  using Nested = typename MultiDimArray<T, J...>::type;
  // typedef typename MultiDimArray<T, J...>::type Nested;
  using type = std::array<Nested, I>;
  // typedef std::array<Nested, I> type;
};

template <class T, size_t I>
struct MultiDimArray<T, I> 
{
  using type = std::array<T, I>;
  // typedef std::array<T, I> type;
};

MultiDimArray<float, 3, 4, 5, 6, 7>::type floats;

MultiDimArray is a pair of meta-functions to compute nested type for multi-dimensional std::array. The most general MultiDimArray is a variadic template of unsigned integers to pass an arbitrary number of dimensions. The terminating MultiDimArray specialization defines the simplest case of single dimensional std::array. I'm using the "using" syntax instead of typedefs. The equivalent typedef are written in comments.

Similarly, MultiDimNative can also defined to create a native array of arbitrary dimensions.

template <class T, size_t I, size_t... J>
struct MultiDimNative 
{
  using Nested = typename MultiDimNative<T, J...>::type;
  using type = Nested [I];
};

template <class T, size_t I>
struct MultiDimNative<T, I> 
{
  using type = T [I];
};

MultiDimNative<double, 3, 4, 5, 6, 7>::type doubles;

To make sure that the layout of all the arrays is the same I wrote a small test program.

template <class T, size_t I, size_t J>
union data
{
  T native[I][J];
  NativeMatrix<T, I, J> native_matrix;
  Matrix<T, I, J> matrix;
  typename MultiDimArray<T, I, J>::type multidim_array;
  typename MultiDimNative<T, I, J>::type multidim_native;
};

template <class T>
void print(T & t, size_t rows, size_t columns)
{
  for(size_t i = 0;i < rows; ++i)
  {
    for(size_t j = 0;j < columns; ++j)
      printf("%d ", t[i][j]);

    printf("\n");
  }
  printf("\n");
}
int main()
{
  constexpr size_t I = 3;
  constexpr size_t J = 4;

  data<int, I, J> d;
  size_t val = 0;

  for(size_t i = 0;i < I; ++i)
  {
    for(size_t j = 0;j < J; ++j)
      d.native[i][j] = val++;
  }

  print(d.native, I, J);
  print(d.native_matrix, I, J);
  print(d.matrix, I, J);
  print(d.multidim_array, I, J);
  print(d.multidim_native, I, J);

  return 0;
}

This program defines a union of 5 different arrays, all of which have the same dimensions and layout. It populates a native two dimensional array and prints the contents using all other multi-dimensional arrays defined in the same union. As of today, only clang accepts this program.

That's it for now!

A tale of noexcept swap for user-defined classes in C++11

2011-09-03T15:22:00.018-06:00

C++11 has taken another stab at function exception specifications for the masses. The shiny new ‘noexcept’ keyword is phasing out its zombie cousin ‘throw’. The well accepted guideline for the old exception specification is: "don’t use them!" That’s good for us because now we don’t have to bother (the reasons for not using throw specification aren’t for the faint hearted anyways.) The noexcept feature does not appear to be a walk in a park either. So hold on tight!

noexcept is meta-programmable! a.k.a conditional noexcept. It is possible to conditionally specify functions to throw any exceptions. The noexcept specification of functions can be inspected at compile-time and functions can derive their own noexcept specification based on exception specifications found elsewhere in the program. Meta-programs are not off-limits here. An excellent introduction of the noexcept feature and its history can be found in June’11 Overload Journal and on Andrzej's C++ blog. I won’t repeat that here but a quick motivation is in order.

Compile-time knowledge about a move-constructor that it does not throw (i.e., annotated with noexcept(true)) can be used for improved run-time performance. For example, std::vector<T>::resize, std::vector<T>::reserve automatically use T’s move-constructor instead of a copy-constructor if T's move-constructor does not throw. Moving of T objects instead of copying would likely achieve higher performance. The standard library provides std::move_if_noexcept function that does move only if it is guaranteed to not fail. Otherwise, it simply resorts to copy-construction. More on this can be found here. I'll return to the topic of writing noexcept move-ctor towards the end of this post.

But the post is about swapping, so lets talk about that. Here is how the std::pair::swap is declared in C++11.

void pair::swap(pair& p)
  noexcept(noexcept(swap(first, p.first)) &&
           noexcept(swap(second, p.second)));

It basically says that pair's swap will throw if either swapping of first or second member throws. The swapping of first and second possibly resolve to their own namespace-level swap via ADL or else they simply pick up std::swap (because pair::swap is declared in std namespace). This declaration seems to indicate a few things.

For a user-defined type it is now much more preferable to have its own namespace-level swap overload instead of using vanilla std::swap. The namespace-level swap function, being an extension of the type’s interface, is vastly more efficient and often can be written in way that it does not throw. The std::swap function, on the other hand, may throw because it uses a copy-constructor and copy-assignment operator while swapping two objects. If you are like me, your member copy-assignment operator will use copy-and-swap idiom for strong exception safety. That means std::swap will create and destroy 3 copies. What a waste! Moreover, that increases the chance of throwing. Bottom line: If T has a member swap, a swap function should be added in the same namespace as of T.

There are some assumptions buried in the above reasoning: (1) move-constructor is not available for a user-defined T, and (2) it is possible to implement member swap of T that does not throw and you can actually say so.

As far as move-constructor being not available is concerned, I think, there are large number of C++03 libraries, which will acquire move-semantics slowly than you might desire. Till then std::swap will, unfortunately, use copy-ctor and copy-assign. A legacy class with a copy-ctor won’t get an automatic move-ctor because it would do wrong things.

The noexcept specification of the user-defined swap better be accurate. Can we really write a nothrow member swap and say so confidently? Obviously, it depends on the members of the user-defined type that we’re swapping. To me, it’s all uphill from here.

Lets look at how standard library uses noexcept for some of its own classes. We already saw std::pair before. How about std::tuple, which is a generalization of a struct and that’s why may be user-defined classes should follow the same basic principle. Tuple’s member swap is declared as

void tuple::swap(tuple& rhs) noexcept(see below)
// The expression inside noexcept is equivalent to the
// logical AND of the following expressions:

noexcept(swap(declval<T&>(), declval<T&>()))
// where Ti is ith type in the variadic list of types.

Tuple’s member swap inspects the noexcept specifications of its members’ swap functions and derives its own specification from that. That makes sense. If swapping of any of the member throws, the tuple’s swap throws. The declval function belongs to same clique as std::move, std::forward, etc. It is a way to obtain rvalue reference of a type without using a constructor. It suffices to say that declval<T> returns "T&&" and declval<T&> returns "T & &&", which is the same as "T &."

Consider a typical C++03 user-defined legacy class that manages its own resources.

namespace L 
{
struct legacy 
{
  legacy();                             // Does not throw
  legacy(const legacy &);               // This may throw
  legacy & operator = (const legacy &); // This may throw (strong exception safe)
  ~legacy() throw();                    // Does not throw
  void swap(legacy &) throw();          // Does not throw
};
} // namespace L

The above legacy class is well-designed except for the fact that it does not have any namespace-level swap. To make it a better citizen in C++11, it needs a namespace-level swap. Interestingly enough, there is substantial code out there that has a specialization of the std::swap in the std namespace. Considering the popularity of this anti-pattern, it probably makes sense to add a swap in two places. It is not too much work in the first place and that may help people who always use a qualified swap (std::swap) habitually.

namespace L 
{
  void swap(legacy &, legacy &) noexcept;
}

namespace std 
{
  template <>
  void swap(L::legacy &, L::legacy &) noexcept;
}

Let’s try to use this modernized legacy class in our C++11 class: Modern.

namespace M 
{
struct Modern 
{
  int count;
  std::string str;
  std::array<L::legacy, 5> data;
  /// default-ctor, copy-ctor, copy-assign, move-ctor, move-assign are defined = default.
  void swap(Modern & p) 
    noexcept(noexcept(swap(std::declval<int &>(),
                           std::declval<int &>())) &&
             noexcept(swap(std::declval<std::string &>(),
                           std::declval<std::string &>())) &&
             noexcept(swap(std::declval<std::array<L::legacy, 5> &>(),
                           std::declval<std::array<L::legacy, 5> &>())));
};
} // namespace M

That’s one awful looking swap. My eyes bleed when I look at it.

It is doing exactly the same thing as std::tuple. It simply checks whether swapping two integers, two strings, and two arrays throw or not. If it does, then member swap of Modern throws. You can skip checks for integer swapping but what’s left is not pretty at all.

Couple of important things to note here:

Because we added namespace-level swap for the L::legacy class, we dodged several problems.If we did not have free swap, the compiler will instantiate std::swap if it is in the scope. Note, however, that vanilla std::swap may throw defeating the purpose of Modern::swap. If no swap is to be found, compiler issues an error.

We hope that swap of std::string and std::array do not throw. As mentioned in [container.requirements.general], std::string::swap does not throw but std::array<T> swap may throw if an unqualified call to swap(T &, T &) throws. Once again, the namespace-level swap will be chosen here, if available. If that does not exist, a specialization of std::swap will be chosen. If none of them exist, std::swap will be instantiated giving our Modern::swap a nothrow(false) specification.

I like my strong exception safety in my little copy-assignment operator so I don’t want my swap to throw but I don’t want my program to std::terminate() if an exception is really thrown. With all that in mind, I would rewrite the swap as follows.

void Modern::swap(Modern &) noexcept 
{
  static_assert(noexcept(swap(std::declval<int &>(),
                              std::declval<int &>())) &&
                noexcept(swap(std::declval<std::string &>(),
                              std::declval<std::string &>())) &&
                noexcept(swap(std::declval<std::array<L::legacy, 5> &>(),
                              std::declval<std::array<L::legacy, 5> &>())), 
                "throwing swap");
  //.... remaining swap code
}

This is not unlike what’s proposed by others but there’s more. The static assert looks awful and looks redundant. There is already a standard library utility that does the same thing: std::tuple. As mentioned before, std::tuple’s swap throws if any member swap throws. We use it here to make our job a lot easier.

void Modern::swap(Modern & that) noexcept 
{
  typedef std::tuple<int, std::string, std::array <L::legacy, 5> > MemberTuple;
  static MemberTuple *t = 0;
  static_assert(noexcept(t->swap(*t)), "throwing swap");
  // .... remaining swap code
}

If you an enthusiastically paranoid C++ programmer, you may want to use conditional noexcept with a little meta-function (is_nothrow_swappable_all) to save typing.

template<typename... T>
struct is_nothrow_swappable_all
{
  static std::tuple<T...> *t = 0;
  enum { value = noexcept(t->swap(*t)) };
};

void Modern::swap(Modern & that) 
   noexcept(is_nothrow_swappable_all<int, std::string, std::array<L::legacy, 5> >::value);

The "remaining swap code" section above is also rather important. The recommended (by Dave and Howard) way to write it is to use unqualified swap but bring std::swap in the scope:

void Modern::swap(Modern & that) 
  noexcept(is_nothrow_swappable_all<int, std::string, std::array<L::legacy, 5> >::value);
{
  using std::swap;
  swap(this->count, that->count);
  swap(this->str, that->str);
  swap(this->data, that->data);
}

The appropriate swap (namespace-level via ADL or std::swap) will be chosen depending upon availability. That’s exactly what tuple’s swap noexcept checker is going to do for us.

Back to the move-constructor, as promised! As mentioned before, noexcept specification of a move-ctor may have performance implications. So you want to get it right. For the M::Modern class we could have defaulted the move-ctor (= default). That will give it a noexcept(false) specification automatically because internally it uses L::legacy’s copy constructor, which throws. As a consequence, std::vector::resize is not as fast as it can be. We can do better.

Implementing a move-ctor using the default-construct-and-swap idiom turns out be quite handy. Default-construct-and-swap does what it says by first delegating to a noexcept default constructor followed by a swap. To implement a noexcept move-ctor this way, you really need to make sure that swap does not throw. As always, you can rely on a conditional noexcept. I'm using std::is_nothrow_constructible type trait to test the obvious!

Modern::Modern(Modern && m) 
  noexcept(std::is_nothrow_constructible<Modern>::value &&
           noexcept(m.swap(m)))
  : Modern()           
{
  swap(m);
}

As long as Modern's default constructor and member swap are noexcept, the move-ctor is noexcept.

Finally, the move-assign operator can be simply implemented as a single swap operation but for some classes that may not be accurate.

Modern::operator = (Modern && m) noexcept
{
  swap(m);
}

Acknowledgements: I want to thank Howard Hinnant (former Library Working Group chair) for reviewing this article and providing me valuable feedback. Any inaccuracies and mistakes left in the article are strictly mine.

Compile-time regex matcher using constexpr

2011-07-26T13:10:00.003-06:00

With my growing constexpr fascination, I thought of using it for something that would be really hard using template meta-programs. How about implementing a compile-time regular expression matcher? Fortunately, a simple regular expression matcher has already been written by Rob Pike. I just rewrote it using constexpr: single return statement in functions, no modifications to the parameters, abundant ternery operators, and recursion. Here we go...

constexpr int match_c(const char *regexp, const char *text);
constexpr int matchhere_c(const char *regexp, const char *text);
constexpr int matchstar_c(int c, const char *regexp, const char *text);
constexpr int matchend_c(const char * regexp, const char * text);

constexpr int matchend_c(const char * regexp, const char * text)
{
  return matchhere_c(regexp, text) ? 1 : 
         (*text == '\0') ? 0 : matchend_c(regexp, text+1);
}

constexpr int match_c(const char *regexp, const char *text)
{
  return (regexp[0] == '^') ? matchhere_c(regexp+1, text) : 
                              matchend_c(regexp, text);
}

/* matchhere: search for regexp at beginning of text */
constexpr int matchhere_c(const char *regexp, const char *text)
{
  return (regexp[0] == '\0') ? 1 : 
         (regexp[1] == '*') ? matchstar_c(regexp[0], regexp+2, text) :
         (regexp[0] == '$' && regexp[1] == '\0') ? (*text == '\0') :
         (*text!='\0' && (regexp[0]=='.' || regexp[0]==*text)) ? 
          matchhere_c(regexp+1, text+1) : 0;
}

/* matchstar: search for c*regexp at beginning of text */
constexpr int matchstar_c(int c, const char * regexp, const char *text)
{
  return matchhere_c(regexp, text) ? 1 : 
         (*text != '\0' && (*text == c || c == '.')) ? 
           matchstar_c(c, regexp, text+1) : 0;
}

#define TO_STR_IMPL(R) #R
#define TO_STR(R) TO_STR_IMPL(R)

int main(void)
{
  static_assert(match_c(TO_STR(REGEX), TO_STR(TEXT)), "...");

  return 0;
}

To compile it, as of today, you need g++ 4.6 or better. You've to pass REGEX and TEXT as #defines while compilation. For instance, -D REGEX=o$ -D TEXT=Foo It matches!

I used two macros TO_STR and To_STR_IMPL to convert the REGEX and TEXT into string literals. #R is basically using the preprocessor stringification technique. For some reason I need two separate TO_STR macros for TEXT substitution and stringification. Seems like the gcc preprocessor can't do those two things in a single macro.

Have fun!

Want speed? Use constexpr meta-programming!

2011-07-19T18:33:00.013-06:00

It's official: C++11 has two meta-programming languages embedded in it! One is based on templates and other one using constexpr. Templates have been extensively used for meta-programming in C++03. C++11 now gives you one more option of writing compile-time meta-programs using constexpr. The capabilities differ, however.

The meta-programming language that uses templates was discovered accidently and since then countless techniques have been developed. It is a pure functional language which allows you to manipulate compile-time integral literals and types but not floating point literals. Most people find the syntax of template meta-programming quite abominable because meta-functions must be implemented as structures and nested typedefs. Compile-time performance is also a pain point for this language feature.

The generalized constant expressions (constexpr for short) feature allows C++11 compiler to peek into the implementation of a function (even classes) and perform optimizations if the function uses constants (literals) only. Constants can be integral, floating point, as well as string literals. The signature of constexpr functions is just like regular C++ functions but the body has several restrictions, such as only one return statement is allowed. Nevertheless, the syntax of constexpr functions is significantly friendlier than that of template-based meta-functions. Contrary to the design of templates, designers of generalized constant expressions are well-aware of its meta-programming capabilities.

In my view, the most interesting aspect of constexpr is its speed. constexpr functions can perform compile-time computations at lightening speed. To compare the performance I implemented an is_prime algorithm in 3 different ways. Here is the algorithm in regular C++:


static bool IsPrime(size_t number)
{
  if (number <= 1)
    return false;

  for (size_t i = 2; i*i <= number; ++i)
    if (number % i == 0)
      return false;

  return true;
}

Here is the a template version of the same algorithm. Obviously, it is implemented as a collection of meta-functions in terms of structures.


struct false_type 
{
  typedef false_type type;
  enum { value = 0 };
};

struct true_type 
{
  typedef true_type type;
  enum { value = 1 };
};

template<bool condition, class T, class U>
struct if_
{
  typedef U type;
};

template <class T, class U>
struct if_<true, T, U>
{
  typedef T type;
};

template<size_t N, size_t c> 
struct is_prime_impl
{ 
  typedef typename if_<(c*c > N),
                       true_type,
                       typename if_<(N % c == 0),
                                    false_type,
                                    is_prime_impl<N, c+1> >::type >::type type;
  enum { value = type::value };
};

template<size_t N> 
struct is_prime
{
  enum { value = is_prime_impl<N, 2>::type::value };
};

template <>
struct is_prime<0>
{
  enum { value = 0 };
};

template <>
struct is_prime<1>
{
  enum { value = 0 };
};

The above meta-program is a recursive implementation because that's how pure functional languages work. The is_prime_impl meta-function does all the heavy lifting. To prevent infinite regression, lazy instantiation technique is used. All I can say at this point is you've to stare at the code to make sense out of it.

And that's precisely the point: C++03 meta-programs are often unreadable and hard to comprehend. Not anymore! Here is the constexpr version of the same algorithm.


constexpr bool is_prime_recursive(size_t number, size_t c)
{
  return (c*c > number) ? true : 
           (number % c == 0) ? false : 
              is_prime_recursive(number, c+1);
}

constexpr bool is_prime_func(size_t number)
{
  return (number <= 1) ? false : is_prime_recursive(number, 2);
}

Well, I agree, although this version uses friendlier syntax, is not quite easy to read. Just like the previous one, it is recursive. I would say just get used to it! You can't live without recursion in C++ meta-programming world. Secondly, every function has a single return statement and the codifying logic for detecting primality requires abundant use of the ternary operator.

As long as parameter number is an integral constant, this constexpr version will compute the result at compile-time (C++11 compilers only). And when the number is a run-time integer, this same function is perfectly capable of computing the result at run-time. So you don't need two different versions of the same program: one for compile-time and another for run-time. One implementation does it all!


int main(void)
{
   static_assert(is_prime_func(7), "...");  // Computed at compile-time
   int i = 11;
   int j = is_prime_func(i)); // Computed at run-time
}

Now that we have the implementations, lets talk performance. Take 4256233. This is 30,000th prime number! How long does the template version take to check if it is prime? It cannot! Yes, g++ 4.7 fails to compile is_prime<4256233>::value because the computation exceeds the default (900) limit of the recursive template instantiations. So I used -ftemplate-depth-2100 allowing 2100 recursive instantiations! Does it work? Yes! How long does it take? About 1 second! That's not bad at all, you say. How fast is constexpr? About 0.154 seconds!

Seems like templates are not too far behind. Wrong! How about fifth million prime number! It is 86028121. I could not get it to work with g++ 4.7. Somewhere in the range of 9300 recursive instantiations g++ seg-faults. That's brutal! isn't it? 9000+ recursive instantiations? There has to be a better way.

So how long does the constexpr take for our fifth million prime number? 0.220 seconds! That's right! This large prime number makes almost no impact on constexpr compilation time. What could be the reason? There are no template instantiations. C++ compilers always did compile-time computations whenever it was possible. constexpr now allows user-defined abstractions to hide those computations behind functions and yet allow compilers to see through them.
By the way, I had to increase to depth of default allowed constexpr recursion using -fconstexpr-depth=9300. The compiler bails out after this limit and resorts to run-time computation. Remember, the function is perfectly good for run-time computation as well (unlike templates version).

I hope this little exercise will convince you that constexpr is the way to go for static meta-programming in C++ as long as you are dealing with literals (integral, floating point numbers, and strings). It is not clear whether constexpr functions are suitable for manipulating complex meta-programmable types, such as mpl::vector and related meta-functions, such as mpl::contains, mpl::push_back, and so on. If you are interested in playing with the above example more, here is the code: is_prime.cpp and prime-test.sh

BoostCon'11 video on LEESA: Language for Embedded Query and Traversal

2011-06-10T00:58:00.005-06:00

BoostCon'11, held in Aspen, Colorado, was a fantastic conference this year. Not only because I got a chance to present my work on LEESA but also because of the breadth and depth of the topics covered.

LEESA, as you may recall, is an embedded language in C++ to simplify XML programming. LEESA's programming model sits on top of the APIs generated by modern XML data binding tools. LEESA gives you XPath-like syntax (wildcards, child-axis, descendant-axis, tuples) to simplify data extraction from an XML object model.

I had a privilege to talk at length about LEESA in BoostCon'11. In the 1hr 41 minutes long video, I'm talking everything from why you need LEESA, how its implemented using cool C++ techniques, such as templates, meta-programming, compile-time and run-time performance, and what direction it may take in future. Here are the slides of the presentation.

Generic Transpose using boost tuples

2010-04-05T18:17:00.006-06:00

Recently, while working on LEESA I faced an interesting problem of creating a transpose using generic programming. The problem is pretty straight forward. Suppose you are given a tuple of 2 vectors i.e. tuple<vector<int>, vector<long> >. Assuming both the vectors are of the same size, how would create a vector <tuple<int, long> > containing the data from the earlier two vectors? Of course, the size of the tuple may vary.

Lets call the function transpose. A brute force solution would be to overload transpose function N times such that each one takes different size of tuple. Here's one that takes a three parameter tuple.


template <class C1, class C2, class C3> // Assuming all Cs are STL containers
std::vector<tuple<C1::value_type, C2::value_type, C3::value_type> >
transpose (tuple<C1, C2, C3> const &) { ... }
}

The implementation is fairly straight forward for those who have seen tuples in the past. We basically need a loop with three forward iterators that iterate over the source containers and populate a resultant tuple in each iteration. The resultant tuple is pushed into the vector that is returned at the end.

However, implementing this in a more generic fashion is quite a lot of fun! A bit of metaprogramming and a byte of compile-time hierarchy generation gets the job done. Lets begin!

First we need to extract out the value_types from the containers and create the type of the resultant tuple. Here is a small metaprogram that does half the job.


template <>
struct GetTransposeCons<tuples::null_type>
{
  typedef tuples::null_type type;
};

template <class TupleOfVectors>
struct GetTransposeCons
{
  typedef typename TupleOfVectors::head_type Head;
  typedef typename TupleOfVectors::tail_type Tail;
  typedef typename
    tuples::cons<typename remove_reference<Head>::type::value_type,
                 typename GetTransposeCons<Tail>::type> type;
};

Given a TupleOfVectors, it produces a cons-list, which is the underlying representation of boost tuples. remove_reference is not strictly needed here, but we'll see its use at the end. This metaprogram produces type cons<int, cons<float, cons<double, tuples::null_type> > > if we give tuple<vector<int>, vector<float>, vector<double> > as the input. The cons-list is practically as useful as the tuple itself. You can print it using tuple's I/O functionality, convert it into a regular tuple and so on so forth.

But promise is a promise, we have to create a tuple! Lets write simple mapping from cons list to tuples. We create many(!) specializations of cons-list to do the mapping.


template <class T>
struct GetTransposeTuple;

template <class T0>
struct GetTransposeTuple<cons<T0, null_type> >
{
  typedef tuples::tuple<T0> type;
};

template <class T0, class T1>
struct GetTransposeTuple<cons<T0, cons<T1, null_type> > >
{
  typedef tuples::tuple<T0, T1> type;
};

template <class T0, class T1, class T2>
struct GetTransposeTuple<cons<T0, cons<T1, cons<T2, null_type> > > >
{
  typedef tuples::tuple<T0, T1, T2> type;
};

I've not found a better way to do it. May be boost tuples have a simpler way to create an equivalent tuple type from cons-list like it does the other way round. tuple::inherited returns the underlying cons-list. Reverse mapping would be nice to have.

With that now we can write a slightly complicated metafunction that converts a TupleOfVectors to a tuple of value_types. Here is how it looks.


typedef typename GetTransposeTuple<
  typename GetTransposeCons<TupleOfVectors>::type
    >::type ValueTypeTuple;

Lets proceed with the hierarchy generation part. Hierarchy generation is quite idiomatic in C++ template metaprogramming while working on list of types as in tuples. Whenever there is a need to generate code that does something useful at run-time (not just compile-time) hierarchy generation comes quite handy. It is applicable when a single class can encapsulate the necessary run-time code for a single type in the cons-list (actually any other type-list for that matter). Rest is just the coordination of the generated classes. It's that simple!

In the case of generic transpose, there needs to be a class for each type in the tuple. Each class does the following things.

1. Hold a reference to the source vector.
2. Hold an iterator to that vector.
3. Extract the value iterator is pointing to and advance the iterator.
4. Copy the value into the <span style="font-weight:bold;">right</span> position in the resultant tuple.

Finally, the resultant tuple is pushed in the resultant vector, which is returned when all the iterators reach the end.

The gist of hierarchy generation is in its inheritance expression.


template <class TupleOfVectors,
          class ValueTypeTuple = /* we saw earlier */,
          unsigned int TUPLE_INDEX = 0>
struct Transposer
  : Transposer <typename TupleOfVectors::tail_type,
                ValueTypeTuple,
                TUPLE_INDEX + 1>
{ ... };

template <class ValueTypeTuple,
          unsigned int INDEX>
struct Transposer <tuples::null_type, ValueTypeTuple, INDEX>
{ ... };

Transposer inherits from another instantiation of itself. The first and the third template parameters change progressively. The recursion ends only when the TupleOfVectors is exhausted and that's when the null_type specialization of the Transposer comes into picture. Note that the ValueTypeTuple remains unchanged throughout the hierarchy but the INDEX into that ValueTypeTuple increases. That is, if the derived Transposer copies the value in slot #i then its immediate base Transposer copies the value in slot #i+1. We don't care what the slot number is for the Transposer of null_type specialization.

Lets now write the body of the Transposer. Here are some typedef that come handy in the implementation of the Transposer template.


  typedef typename TupleOfVectors::head_type Head;
  typedef typename TupleOfVectors::tail_type Tail;
  typedef typename remove_reference<Head>::type HeadContainer;
  typedef Transposer<Tail, ValueTypeTuple, TUPLE_INDEX + 1> super;
  typedef ValueTypeTuple TransposeTuple;
  typedef std::vector<ValueTypeTuple> Transpose;

The class template has two private members.


  HeadContainer const & head_container_;
  typename HeadContainer::const_iterator head_iter_;

Note that the HeadContainer is gonna be different in every instantiation of the Transposer. The constructor looks like this


  Transposer(TupleOfVectors const & tuple)
    : super(tuple.get_tail()),
      head_container_(tuple.get_head()),
      head_iter_(head_container_.begin())
  {}

Each constructor takes what it needs from the TupleOfVectors and passes the rest of it to its base class. Tuple expects such use and provides the right API (get_head, get_tail) to achieve that. The reference to the container is assigned to the head_container_ member and the iterator is also initialized. The same happens in all the constructors except the last one that is a specialization of null_type. Its constructor is no-op.


template <class ValueTypeTuple,
          unsigned int INDEX>
struct Transposer <tuples::null_type, ValueTypeTuple, INDEX>
{
protected:
  void populate_tuple(ValueTypeTuple &) {}
  Transposer (tuples::null_type const &) {}
};

With this much setup, everything that is needed to begin transpose procedure is arranged neat and tidy. Now we write the final get_transpose method that creates the transpose.


  Transpose get_transpose ()
  {
    Transpose tran;
    tran.reserve(head_container_.size());
    for(typename HeadContainer::const_iterator iter = head_container_.begin();
        iter != head_container_.end();
        ++iter)
    {
      ValueTypeTuple vtuple;
      this->populate_tuple(vtuple);
      tran.push_back(vtuple);
    }
    return tran;
  }

protected:

  void populate_tuple(ValueTypeTuple & vtuple)
  {
    if(head_iter_ == head_container_.end())
      throw std::runtime_error("Container bound exceeded.");
    else
    {
      vtuple.get<TUPLE_INDEX>() = *head_iter_++;
      super::populate_tuple (vtuple);
    }
  }

get_transpose method has a loop that iterates over all the elements of the head_container. For each iteration, it creates a default initialized ValueTypeTuple, which needs to be populated with one sample from each of the source containers. We do that in the populate_tuple method, which receives the tuple as a non-const reference. It does #3 and #4 bullets mentioned earlier. It extracts one data sample from the container using the iterator, advances the iterator, and then copies that data sample into the "right place" in the tuple. The "right place" is nothing but the INDEX parameter that was passed while creating the hierarchy. Once again, tuple provided the right API to assign the Nth entry in a tuple provided N is known at compile-time. Finally, the same procedure has to happen in every class in the hierarchy. We simply call the base class's populate_tuple function and pass the partially populated ValueTypeTuple by reference. Note that populate_tuple throws runtime_error exception if some iterator hits end of the container in the middle of transpose procedure.

Finally, we implement the transpose function in terms of Transposer template.


template <class TupleOfVectors>
typename Transposer<TupleOfVectors>::Transpose
transpose (TupleOfVectors const & tupleofv)
{
  return Transposer<TupleOfVectors>(tupleofv).get_transpose();
}

Here is how we use it.


  int arr[5] = {10, 20, 30, 40, 50};
  std::vector<int> vint(arr, arr+5);
  std::list<float> lfloat(arr, arr+5);
  std::vector<long> vlong(arr, arr+5);

  Transposer<TupleOfV>::Transpose tran 
    = transpose(make_tuple(cref(vint), cref(lfloat), cref(vlong)));

To avoid unnecessary copies of the source vectors, we make use of cref reference_wrapper. In such cases, each entry is a const-reference to the original container, which causes problems in the GetTransposeCons metafunction if we don't use remove_reference.

The complete source code is available here.

Faster meta-programs using gcc 4.5 and C++0x

2010-03-03T20:54:00.021-07:00

One of the practical issues with C++ meta-programming is its speed. C++ programs that use heavy meta-programming can be notoriously slow to compile on contemporary compilers. Things are changing, however. Check the following comparison of gcc 4.5 against gcc 4.4.3.

The first graph is obtained from a program that creates a binary tree of template instantiations. The x-axis shows the number of instantiations when value of N goes from 8 to 17. I could not build up patience for gcc 4.4.3 beyond 16363 instantiations (N=13). On the other hand, gcc 4.5 does pretty good and its increase in compilation time is indeed linear as mentioned here. Here is the program that creates a binary tree of template instantiations.


template 
struct Binary 
{
  enum { value = 1 +
         Binary::value +
         Binary::value };
};

template
struct Binary<0, A, B> 
{
  enum { value = 1 };
};

int main(void) 
{
  static const int N = 10;
  const int instantiations = Binary::value;
}

The second graph is obtained from a program that finds an intersection of two MPL vectors. Again gcc 4.5 shows linear increase in compilation time as opposed to gcc 4.4.3. Here is the intersection program.


template <class V1, class V2>
struct Intersection 
{
  typedef typename
     boost::mpl::copy_if<V1,
     boost::mpl::contains<V2, boost::mpl::placeholders::_1> >::type type;
};

While all that is already exciting, it fades in comparison to the performance of variadic templates in C++0x. The green line in the second graph shows negligible effect on performance with the increasing number of template parameters. Here is my intersection metaprogram using variadic templates.


struct null_type {};
template <typename... Arg> struct vector {};

template <typename V> struct front;
template <typename V> struct pop_front;

template <typename Head, typename... Tail>
struct front <vector <Head, Tail...> > 
{
  typedef Head type;
};

template <>
struct front <vector <> > 
{
  typedef null_type type;
};

template <typename Head, typename... Tail>
struct pop_front <vector <Head, Tail...> > 
{
  typedef vector<Tail...> type;
};

template <>
struct pop_front <vector <> > 
{
  typedef vector<> type;
};

template <typename Vector, typename T> struct push_back;

template <typename T, typename... Args>
struct push_back < vector<Args...>, T> 
{
  typedef vector<Args..., T> type;
};

template <typename Vector> struct size;

template <typename... Args>
struct size <vector <Args...> > 
{
  typedef size type;
  enum { value = sizeof...(Args) };
};

template <typename Vector, typename What> struct contains;

template <typename What, typename Head, typename... Tail>
struct contains < vector<Head, Tail...>, What> : 
  std::conditional < std::is_same<Head, What>::value,
                     std::true_type,
                     contains < vector<Tail...>, What> >::type
{
  typedef contains type;
};

template <typename What>
struct contains <vector<>, What> 
{
  typedef contains type;
  enum { value = 0 };
};

template <class V1, class V2>
struct Intersection;

template <class V1, class V2, unsigned int N>
struct Intersection_impl
{
  typedef typename front<V2>::type Head;
  typedef typename pop_front<V2>::type Tail;
  typedef typename Intersection<V1, Tail>::type I;

  typedef typename 
    std::conditional<contains<V1, Head>::value,
                     typename push_back<I, Head>::type,
                     I >::type type;
};

template <class V1, class V2>
struct Intersection_impl <V1, V2, 0> 
{
  typedef vector<> type;
};

template <class V1, class V2>
struct Intersection 
{
  typedef typename Intersection_impl<V1, V2, 
          size<V1>::value * size<V2>::value>::type type;
};

So long story short, seems like better days are ahead for C++ meta-programming!

Modifying temporaries

2009-08-11T22:39:00.005-06:00

Temporary objects are created and destroyed all the time in a C++ program. A simple example would be a function that returns by value. A temporary is as good as a const object because it makes little sense (usually) to change a temporary object, which is unnamed and has a very short time span. (Note: A temporary can be bound to a const reference in which case the scope of the temporary is the same as that of the reference.) However, as it turns out, in C++ you can change temporaries ... if they are of class type! You can call non-const member functions on a temporary. This is quite similar to binding a temporary to a non-const reference and changing it. Section 3.10.10 in C++ ISO/IEC 14882:1998 standard clearly mentions this exception. There are at least two practical use of such an exception. One is the "Named Parameter" idiom and the other one is the Move Constructor idiom. In case of the named parameter idiom, the member functions might prefer to return the object by non-const reference instead of a by value. Here is an example:

class X
{
public:
int a;
char b;
X() : a(0), b(0) {}
X setA(int i) { a = i; return *this; } // non-const function
X setB(char c) { b = c; return *this; } // non-const function
};

std::ostream & operator << (std::ostream & o, X const & x)
{
o << x.a << " " << x.b;
return o;
}

X createX() // returns X by value.
{
return X();
}

int main (void)
{
// The following code uses the named parameter idiom.
std::cout << createX().setA(10).setB('Z') << std::endl;
}

LEESA: A new way of typed XML programming in C++

2009-03-21T13:43:00.015-06:00

Some of my recent research work has focused on developing a highly generic and reusable library for complex object structure traversal, which is best exemplified by schema driven XML programming. I'm glad to present a research paper called LEESA: Embedding Strategic and XPath-like Object Structure Traversals in C++, which will be published in the proceedings of IFIP Working Conference on Domain Specific Languages (DSL WC), 2009 at Oxford, UK. LEESA stands for Language for Embedded quEry and traverSAl. LEESA has advanced the state-of-the-art of the typed XML programming in standard C++ to a level where many benefits of static type analysis can be maintained while enjoying a succinct syntax similar to that of XPath. Below, a quick motivating example of LEESA that sorts and prints the names of the authors in a XML book catalog is shown.

Catalog() >> Book() >> Author() >> Sort(Author(), LastNameComparator) >> ForEach(Author(), print);

The key thing to be noted here is that it is not a string encoded query. In fact, the C++ compiler checks the compatibility of this expression against the book catalog XML schema at compile-time! LEESA uses Expression templates idiom to achieve this highly intuitive, XPath-like syntax. Overall, LEESA's implementation is an exciting combination of generic programming, operator overloading, expression templates, C++ metaprogramming, Boost MPL, C++0x Concepts, and heck a lot of template hackery to make all the things work together! Interesting details are presented in the paper mentioned above.

The source code of LEESA is available. However, LEESA's current implementation is based on Universal Data Model (UDM 3.2.1) -- a full-fledged code generator for model-driven development that can be used as a XML schema compiler. Other code generators could be used provided they are extended to produce the necessary layers of abstraction described in the paper.

In the upcoming posts, I plan to document some of my experiences of developing LEESA.

Int-to-type idiom and infinite regress

2008-09-21T14:57:00.005-06:00

A new writeup on Int-to-type idiom has been posted on More C++ Idioms wikibook. It is used to achieve static dispatching based on constant integral values. I'll finish the writeup of the idiom here with special attention to how int-to-type idiom can lead to infinite series of type instantiations and why. The idiomatic form of the Int-to-type idiom is given below.

template <int I>
struct Int2Type
{
enum { value = I };
typedef Int2Type<I> type;
typedef Int2Type<I+1> next;
};

The type typedef defined inside the template is the type itself. I.e, Int2Type<10>::type is same as Int2Type<10>. The next typedef gives the following type in order. However, compiler is not required to instantiate the next type unless and until two things happen: (1) an instance of the type is created or (2) an associated type is accessed at compile-time. For example, Int2Type<10> will be instantiated if one the following two things are written.

Int2Type<10> a; // a variable declaration.
typedef Int2Type<10>::type INT10; // accessing an associated type.

For kicks, lets see what happens if we add "::type" in the typedef of next.

template <int I>
struct Int2Type
{
enum { value = I };
typedef Int2Type<I> type;
typedef typename Int2Type<I+1>::type next; // Note change here.
};
int main (void)
{
Int2Type<10> i; // This instantiation will trigger an infinite chain.
}

For each instantiation of the Int2Type template, its "next" type is also instantiated because we are accessing the associated type defined inside the template. This leads to an infinite series of instantiations of the template with no end. Obviously, C++ compiler stops after predefined number of recursive instantiations with an error message. More formally, this problem is also known as infinite regress where the original problem reappears in the solution to the problem.

copy elision and copy-and-swap idiom

2008-09-16T21:50:00.002-06:00

An updated writeup of the copy-and-swap idiom is now available on the More C++ Idioms wikibook. A comparison of two different styles of assignment operator is shown. First version accepts the parameter as pass-by-const-reference whereas the second version accepts it as pass-by-value. For some classes pass-by-value turns out to be more efficient as a copy of the object is elided when the right hand side is a rvalue.

linked list using std::pair (infinite regression)

2008-08-31T21:36:00.003-06:00

Defining a node of a linked-list using std::pair sounds as simple as drinking a Starbucks's white chocolate mocha. But it really isn't. Give it a try! The constraint is to use std::pair's first or second as a pointer to the structure itself, like in any linked-list's node. As far as I know, it is impossible unless you resort to ugly casts from void pointers. The problem is actually quite well known and gives rise to something known as infinite regress, where the problem you want to solve reappears in the solution to the problem.

typedef std::pair<int, /* Pointer to this pair!! */ > Node;

The closest thing I could come up with is something like the one below.

struct Node : std::pair <int, Node *>
{};

Node n;
n.second = &n; // A cyclic linked-list.

return void

2008-07-09T10:52:00.002-06:00

I thought it would be interesting to discuss a subtle C/C++ interview question I learned recently. Question is deceptively simple: "Can you write a return statement in a function that returns void?" The answer is "Yes! You can return void!" The following program seems to be a valid C/C++ program.

static void foo (void) { }
static void bar (void) {
return foo(); // Note this return statement.
}
int main (void) {
bar();
return 0;
}

I tested it using gcc4 and VS9. With -ansi and -pedantic compiler options for gcc, it throws just a warning pointing at line #5.

return_void.c:5: warning: return with a value, in function returning void

Although use of such a feature is not clear in a C program, it is particularly useful while using templates. Consider,

template <class T>
T FOO (void) {
return T(); // Default construction
}

template <class T>
T BAR (void) {
return FOO<T>(); // Syntactic consistency. Same for int, void and everything else.
}

int main (void) {
BAR<void>();
}

It suddenly makes sense when templates are in picture. Take home point: Syntactic consistency is of paramount importance for supporting generic programming and writing generic libraries.

Non-Virtual Interface and the Fragile Base Class Interface Problem

2008-06-14T09:22:00.002-06:00

A new writeup on Non-Virtual Interface (NVI) idiom has been written on More C++ Idioms wikibook. In the writeup, I discuss the relationship of NVI with the Fragile Base Class (FBC) problem, which can silently break perfectly good derived classes because of some innocuous changes in the base class.

RSS Feed for More C++ Idioms Wikibook

2008-05-12T17:19:00.003-06:00

The open-content wikibook "More C++ Idioms" has grown quite a bit from it inception. Whenever I get time, I try to add more contents in the book. So I always wanted to track the changes happening in the book in a convenient manner. Today, I put together a RSS feed for the book, which publishes recent changes made to the book. Thanks to the excellent technical support provided by existing wikibookians (if that is a word). The feed is formatted like two column GUI-based diff utilities (kdiff3, Beyond-compare). Frankly, it is not as readable and enjoyable as regular blog entries but at least it will help interested readers to know what new content is being added to the book and how the book making progress towards completion.

Redirecting C++ Truths feed

2008-04-22T13:26:00.003-06:00

Dear readers,

Thanks for your continued interest in the C++ Truths blog and a steady stream of feedback comments. For quite some time now, I'm interested in learning accurate statistics about the readers of this blog. Recently, I came across, FeedBurner, which seems to be a popular choice for centralized feed processing and maintaining feed analytics such as subscriber count, live hits and many more things. Therefore, I have decided to redirect all the future contents on C++ Truths blog to the CppTruths feed. Existing atom and rss feeds shall be discontinued soon. I encourage you to subscribe to the new feed source and help me find the real subscriber count. In return, I promise to be more regular and frequent in posting more C++ truths, which you love to read!!

- Sumant.

Function Template Overload Resolution and Specialization Anomaly

2008-01-04T11:47:00.001-07:00

I recently realized that function template overloading and function template specialization can interact with each other in complex ways giving rise to quite surprising C++ programs. Consider,

template<class T> // (a) a base template
void f( T ) {
std::cout << "f(T)\n";
}

template<>
void f<>(int*) { // (b) an explicit specialization
std::cout << "f(int *) specilization\n";
}

template<class T> // (c) another, overloads (a)
void f( T* ) {
std::cout << "f(T *)\n";
}

int main (void) {
int *p = 0;
f(p);
}

Output of the above program is "f(T *)" (i.e. (c) is invoked in main). Now simply swap the order in which (b) and (c) are written. The output of the program changes! This time it invokes (b) giving output as "f(int *) specilization".

The reason behind it is that when the integer full specilization (b) of f is defined in the order shown above, it is a full specialization of (a). But (c) is a better match as it is an overloaded primary template defined afterwards and we get "f(T *)" as an output.

When (b) is defined after (c), (b) is an integer full specilization of (c) and hence the specilization is chosen as expected.

An excerpt from the book "C++ Templates - The Complete Guide" helps explain what is really happening here.

"Partial specialization doesn't introduce a completely new template: It is an extension of an existing template (the primary template). When a CLASS template is looked up, only primary templates are considered at first. If, after the selection of a primary template, it turns out that there is a partial specialization of that template with a template argument pattern that matches that of the instantiation, its definition (in other words, its body) is instantiated instead of the definition of the primary template. (Full template specializations work exactly the same way.)"

(Added this para on May-05-2008)
Note that the above paragraph applies to class templates only. But when full specializations are in consideration, the above paragraph applies to function templates as well. Full function template specialization is supported by C++98 standard but not partial function template specialization. A better alternative to partial function template specialization is to use plain old function overloading. Having said that, as far as I know, there are efforts begin made towards standardizing partial function template specialization for C++09 standard. (please see comments for more discussion on this.)

The program clearly shows that the order of definition of specilizations and overloads affects primary template lookup. As a result, interestingly enough, you can define the f<>(int *) full specialization twice in the program. One after (a) and another one after (c) and program compiles just fine!

template<class T> // (a) a base template
void f( T ) {
std::cout << "f(T)\n";
}

template<>
void f<>(int*) { // (b) an explicit specialization
std::cout << "f(int *) specilization\n";
}

template<class T> // (c) another, overloads (a)
void f( T* ) {
std::cout << "f(T *)\n";
}

template<>
void f<>(int*) { // (d) another identical explicit specialization
std::cout << "f(int *) another specilization\n";
}

int main (void) {
int *p = 0;
f(p);
}

What is the output here? Any guesses?

This program is an example of complexity that results due to orthogonality of C++ language. In simple terms, number of C++ features can co-exist and their interplay can baffle any uninitiated C++ programmer! I wonder how complex it would be once we have partial function template specialization support in standard C++ in 2009.

using std::copy on std::map iterator pair

2007-11-28T01:14:00.000-07:00

Sometimes it is useful to be able iterate over all the elements of a std::map using standard algorithms like std::copy(), std::count(), std::min_element(), std::max_element(). These standard functions do not work out of the box using std::map::iterator. For example, if you want to print all the elements of a map to standard output, you can't use the following popular copy-ostream_iterator idiom.

std::map <std::string, int> m;
std::copy (m.begin(), m.end(), std::ostream_iterator<int>(std::cout, "\n"));
// does not compile

This is because value_type of the map::iterator is a pair. In other words, if iter is a map<T,U>::iterator then *iter gives pair<T,U> and not U. If we could somehow get hold of pair::second (i.e. type U) instead of pair<T,U> all the above mentioned algorithms can be used out of the box.

The approach I took to solve this problem is to write an iterator adaptor that behaves likes any general bidirectional_iterator. In general, this approach allows map iterators to be used wherever Iterator-Pair idiom is useful. The code given below is kind of long but quite straight forward and idiomatic in nature.

#include <map>
#include <iostream>
#include <algorithm>
#include <string>
#include <list>
#include <iterator>

template <class BiDirIter>
class StdMapIteratorAdaptor
/* To make the custom iterator behave like a standard iterator by exposing
required iterator_traits */
: public
std::iterator <std::bidirectional_iterator_tag,
typename BiDirIter::value_type::second_type>
{
BiDirIter iter_;
public:

explicit StdMapIteratorAdaptor(BiDirIter const & iter = BiDirIter())
: iter_(iter) {}

bool operator == (StdMapIteratorAdaptor const & rhs) const {
return (iter_ == rhs.iter_);
}

bool operator != (StdMapIteratorAdaptor const & rhs) const {
return !(*this == rhs);
}

/* Return type is const to make it work with map::const_iterator */
typename BiDirIter::value_type::second_type const & operator * () {
return iter_->second;
}

typename BiDirIter::value_type::second_type const & operator * () const {
return iter_->second;
}

typename BiDirIter::value_type::second_type const * operator -> () const {
return &(iter_->second);
}

// Pre-increment
StdMapIteratorAdaptor & operator ++ () {
++iter_;
return *this;
}

// Post-increment
const StdMapIteratorAdaptor operator ++ (int) {
StdMapIteratorAdaptor temp (iter_);
++iter_;
return temp;
}

// Pre-decrement
StdMapIteratorAdaptor & operator -- () {
--iter_;
return *this;
}

// Post-decrement
const StdMapIteratorAdaptor operator -- (int) {
StdMapIteratorAdaptor temp (iter_);
--iter_;
return temp;
}
};

/* An helper function to save some typing of tedious nested C++ types
It is very similar to std::make_pair function */
template <class BiDirIter>
StdMapIteratorAdaptor <BiDirIter>
make_map_iterator_adaptor (BiDirIter const & iter)
{
return StdMapIteratorAdaptor<BiDirIter> (iter);
}

int main(void)
{
typedef std::map <std::string, int> StrIntMap;
StrIntMap months;

months["january"] = 31;
months["february"] = 28;
months["march"] = 31;
months["april"] = 30;
months["may"] = 31;
months["june"] = 30;
months["july"] = 31;
months["august"] = 31;
months["september"] = 30;
months["october"] = 31;
months["november"] = 30;
months["december"] = 31;

StrIntMap const & m = months;

StdMapIteratorAdaptor <StrIntMap::const_iterator> begin (m.begin());
StdMapIteratorAdaptor <StrIntMap::const_iterator> end (m.end());
std::copy(begin, end, std::ostream_iterator <int> (std::cout, " "));
std::cout << std::endl;

std::list<int> l(make_map_iterator_adaptor(m.begin()),
make_map_iterator_adaptor(m.end()));

std::copy (l.begin(), l.end(), std::ostream_iterator <int> (std::cout, " "));
std::cout << std::endl;
std::copy (make_map_iterator_adaptor(months.begin()),
make_map_iterator_adaptor(months.end()),
std::ostream_iterator <int> (std::cout, " "));

return 0;
}

New book on modern C++ idioms

2007-08-14T17:38:00.000-06:00

For quite some time now, I am hoping to come across a book on modern C++ idiom as comprehensive as the Purple book by James Coplien! Finally, I got bored of the long wait and a thought came to my mind - This is Web 2.0 and open knowledge era. Why don't I start writing myself? and ask the world to contribute to it? So here we go! A new free, open book on modern C++ idioms called More C++ Idioms is taking shape on en.wikibooks.org And everyone's invited!

const overload functions taking char pointers

2007-07-17T13:11:00.000-06:00

Always have two overloaded versions of functions that take
char * and const char * parameters. Declare (but don't define if not needed)
a function that takes const char* as a parameter when you have defined
a function that accepts a non-const char* as a parameter.

#include <iostream>
#include <iomanip>

static void foo (char *s) {
std::cout << "non-const " << std::hex << static_cast <void *>(s) << std::endl;
}
static void foo (char const *s) {
std::cout << "const " << std::hex << static_cast <void const *>(s) << std::endl;
}

int main (void)
{
char * c1 = "Literal String 1";
char const * c2 = "Literal String 1";
foo (c1);
foo (c2);
foo ("Literal String 1");
//*c1 = 'l'; // This will cause a seg-fault on Linux.
std::cout << c2 << std::endl;

return 0;
}

Because of default conversion rule from string literal to char *,
the call to foo using in-place literal goes completely undetected
through the eyes of compiler's type system.

Interestingly enough, the addresses of all the identical string literals
is the same, irrespective of whether it is assigned to const or non-const.
Internally though, they are stored on the const DATA page and modifying
them causes a seg-fault.

Future of C++ track @ ACCU

2007-07-06T15:30:00.000-06:00

Recently held ACCU 2007 conference had a track dedicated to C++ called: Future of C++ Track. I have listed the presentations in that track and some other related presentations for a quick reference.

* An Outline of C++0x (Bjarne Stroustrup)
* Generalizing Constant Expressions in C++ (Jens Maurer)
* C++0x Initilaisation: Lists and a Uniform Syntax (Bjarne Stroustrup)
* An Introduction to the Rvalue Reference in C++0x (Howard Hinnant)
* C++ has no useful purpose (Russel Winder)
* C++ Modules (David Vandevoorde)
* Support for Numerical Programming in C++ (Walter Brown)
* C++ Threads (Lawrence Crowl)
* Standard Library report (Alisdair Meredith)
* Concepts: An Introduction to Concepts in C++0x (Doug Gregor) (OOPSLA06 paper)

iterator tags idiom and compile-time algorithm selection

2007-05-06T20:39:00.001-06:00

Compile-time algorithm selection can be done using function overloading and traits idiom. It is a quite useful technique in generic programming. In this technique usually a set of "selector" types are used to select one among many overloaded functions. Note that the number of parameters to these overloaded functions is same but there is a "selector" type at the end of the parameter list. A use of that technique based on standard defined iterator tags is shown here.