The Wayback Machine - https://web.archive.org/web/20170701102117/http://www.macieira.org:80/blog/2011/07/initialising-an-array-with-cx0x-using-constexpr-and-variadic-templates/

«

»

Jul 21

Initialising an array with C++0x using constexpr and variadic templates

When I wrote the blog on improving QString further, I said:

If you can, use the following C++0x expression, which is read-only and sharable:

  static const auto s = QStringLiteral("Hello, World\n");

That above actually does work and does produce a read-only and sharable QStringData containing the UTF-16 “Hello, World\n” string. However, what I didn’t say (because I hadn’t realised at the time) was that the actual s variable wasn’t the QStringData, but a pointer to it. As I discussed yesterday, whenever you have an initialised pointer, the compiler must generate a relocation to make it work on Position-Independent libraries.

To do that, we could simply write something like:

  static const auto s = (QConstStringData<13>)
    { /* insert here the other fields */, u"Hello, World\n" };

The other fields are constant and aren’t part of the parameter, so why not use a nice, constexpr constructor? (By the way, I came across this blog on constexpr).

The code

So I wrote the following class:

template <int N> struct QConstStringData
{
    int size;
    char16_t data[N + 1];
    constexpr inline QConstStringData(const char16_t str[N + 1])
        : size(N), data(str) {}
};

Sounds right, doesn’t it? Well, that doesn’t compile. I cannot initialise a member of type char16_t [N] from a variable of type const char16_t (note how the parameter decayed to a pointer). So needed to somehow initialise by copying the contents. Since we’re in a constexpr constructor, there are even more constraints: no body and I can only call constexpr functions.

So I tried the following, just to test, with a string of N = 2:

    constexpr inline QConstStringData(const char16_t str[N + 1])
        : size(N), data({ str[0], str[1] }) {}

That compiled and initialised my object just fine in memory, without load-time code being run. That told me I was in the right path.

So the next problem was: how to make that iteration work for any value of N? The solution was to use variadic templates, using a technique I used to implement one version of the New Signal-Slot connection syntax, which in turn I learned by reading the code to std::tuple.

Here’s the full code listing and I’ll discuss it below.

template <int...> struct IndexList {};
 
template <typename IndexList, int Right> struct Append;
template <int... Left, int Right> struct Append<IndexList<Left...>, Right>
{ typedef IndexList<Left..., Right> Result; };
 
template <int N> struct Indexes
{
    typedef typename Append<typename Indexes<N - 1>::Result,
                            N - 1>::Result Result;
};
template <> struct Indexes<0> { typedef IndexList<> Result; };
 
template <typename Char, typename IndexList> struct DataContainer;
template <typename Char, int... I>
struct DataContainer<Char, IndexList<I...> >
{
    enum { N = sizeof...(I) };
    Char data[N + 1];
    constexpr inline DataContainer(const Char str[N + 1])
        : data({ str[I]... }) {}
};
 
template <int N> struct QConstStringData2
{
    typedef typename Indexes<N>::Result IndexList;
    typedef DataContainer<char16_t, IndexList> Data;
    int size;
    Data data;
    constexpr inline QConstStringData2(const char16_t str[N])
        : size(N), data(str) {}
};
 
static const auto s1 = QConstStringData2<5>(u"Hello");

Analysis

You’ll notice that the constructor of the class didn’t change, but the type changed instead. Like I said above: I can call constexpr functions and the one that suited me to call was the constructor of the data member. Sounds like I just passed the problem along to another function, didn’t it? I’m actually using a bit (or a lot) of Template metaprogramming now.

Well, the trick is in what the actual type of the data member is. While my original type has a template parameter of just one integer, the member has a type of DataContainer<char16_t, IndexList<0, 1, 2, …, N - 1>>. Note that it's not valid C++ to write it like that -- if it were, the code would be a lot simpler. Getting that list going is exactly what the rest of the code does.

Line 1 defines a simple structure with a variadic template parameter and no contents, called IndexList. We never actually instantiate this type: it's just a container for the indices we're going to use to copy.

Lines 3-5 define a structure called Append that takes two parameters: the first one (typename IndexList) is a type, which is supposed to be an instantiation of IndexList; the second is an integer (int Right). This struct is supposed to append the integer value of Right to the template arguments of IndexList.

It does so on lines 4 and 5, which define a partial template specialisation of the Append structure. The definition is:

template <int... Left, int Right> struct Append<IndexList<Left...>, Right>

Which tells the compiler to apply this particular specialisation's body (line 5) whenever the first template parameter is an IndexList instantiation containing a variadic number of integers and the second template parameter is one integer. Given that, the body is easy: we simply typedef the IndexList<Left..., Right> as Result. Note the use of the "unpacking operator ...", which is applied to the right of the parameter name: it tells the compiler to expand with the actual values. This operator will appear again.

Now that we have a type to hold our indices and we have a way of appending items to that list via template metaprogramming, we need to do go from one integer (N) to the list of 0…N-1. That's the structure Indexes defined from line 7 to 12.

This is another template structure: it has only one template parameter, the integer which we want to expand. The trick here is to realise that the list containing N items (0…N-1) is the same as the list containing N-1 items (0…N-2) with N-1 appended. So lines 9-10 do the appending, using the previously-defined Append class, and recursively referring to this structure itself.

    typedef typename Append<typename Indexes<N - 1>::Result,
                            N - 1>::Result Result;

We simply typedef the result of appending N-1 to the result of this very class when the template argument is N-1.

As any recursive algorithm, we need to tell the compiler where to stop. This is where the full template specialisation on line 12 comes from: it defines the contents of the list with N = 0 elements, an IndexList<>

template <> struct Indexes<0> { typedef IndexList<> Result; };

The last class we must look at is the DataContainer class. It has two template parameters: the first is a typename Char which I only added so I could use this code for QByteArray in the future. The second one is the interesting one: it's supposed to be the IndexList containing the indices 0…N-1. So we use a partial template specialisation (the same trick we used on line 4) so we can match all uses of DataContainer when the second parameter is an instantiation of IndexList where the parameters are variadic sequence of integers (int... I).

This variadic parameter is used on line 21 to (finally!) initialise the array:

        : data({ str[I]... }) {}

We see here again the second use of the "unpacking operator" -- the three dots applied to the right of a template parameter. It also appears on line 18, to the right of "sizeof". The sequence str[I]... will expand to str[0], str[1], ..., str[N - 1], which is what we wanted.

Page optimized by WP Minify WordPress Plugin