Filling std::array in-place (emplace_array)

Take this local std::array:

std::array<int, 100> values;

According to the rules of C++, its elements are uninitialized (also the case for data members). If we wish to initialize values with all zeros, we can use aggregate initialization syntax:

std::array<int, 100> values = {}; // all zeros

However, to fill the array with a value other than zero would require quite a bit of typing:

std::array<int, 100> values = { 1, 1, 1, 1, … }; // keep going...

Even then, if we increase the size of the array, we must add extra values to the initializer list, or some elements will be zero-initialized.

Thankfully, there is a better solution:

std::array<int, 100> values; // uninitialized
values.fill(1); // efficient: no initial content

This is efficient for non-class types, which are uninitialized by default, but is less efficient for class types that have a well-defined value after initialization.

std::array<std::string, 100> values; // initialized to ""
values.fill("1"); // inefficient: overwrites initial content

Ideally, all elements would be initialized to "1". One option is to use std::vector instead of std::array:

constexpr auto size = 100u;
std::vector<std::string> values;
values.reserve(size);
for (size_t i = 0; i < size; ++i)
{
    values.emplace_back("1");
}

But what if we want the compile-time efficiency offered by the stack-allocated std::array? Is our only option an enormous initializer list?

std::array<std::string, 100> values = { "1", "1", "1", … }; // ...

Well, yes, but we can make the compiler do the work for us!

The solution

#include <array>
#include <cstddef>
#include <type_traits>

template<std::size_t N, typename T, typename... Ts>
struct array_emplacer
{
    template<
        typename... Args,
        typename = std::enable_if_t<(
            sizeof...(Args),
            sizeof...(Ts) + 1 < N
        )>
    >
    static std::array<T, N> emplace(Args const&... args)
    {
        return array_emplacer<N, T, T, Ts...>::emplace(args...);
    }

    template<
        typename... Args,
        typename = std::enable_if_t<(
            sizeof...(Args),
            sizeof...(Ts) + 1 == N
        )>,
        typename = void
    >
    static std::array<T, N> emplace(Args const&... args)
    {
        return std::array<T, N>{ T(args...), Ts(args...)... };
    }
};

template<typename T, std::size_t N, typename... Args>
std::array<T, N> emplace_array(Args const&... args)
{
    return array_emplacer<N, T>::emplace(args...);
}

Now filling our array on initialization is easy:

auto values = emplace_array<std::string, 100>("1");

In fact, we can pass any number of arguments to use for intialization, just like functions like std::vector::emplace_back:

auto values = emplace_array<std::string, 100>(3u, '9')

How does it work?

Look at this line:

        return std::array<T, N>{ T(args...), Ts(args...)... };

We see that emplace_array is generating an initializer list by somehow creating a parameter pack, Ts, which expands to N – 1 copies of the argument, T. The parameter pack, Args, is expanded into each copy of the call to T's constructor, thereby constructing the array elements in-place.

Ts is generated using template recursion.

        return array_emplacer<N, T, T, Ts...>::emplace(args...);

Here, emplace recursively calls a version of itself, increasing the number of T's by one each time. Note that template parameter lists may only contain one template parameter pack, and emplace already has a template parameter pack, Args. Thus, Ts is accumulated by recursively defining the class template, array_emplacer. Since emplace is a static member of array_emplacer, it has access to its template parameters.

The template recursion is terminated by using std::enable_if to selectively enable a terminating version of emplace when we have exactly N copies of T. We use the comma operator to redundantly include Args in the expression to activate SFINAE (substitution only involves the function template's own arguments; N and T are arguments of array_emplacer).

Finally, thanks to return value optimization, all modern compilers will optimize away all copies of the returned std::array<T, N>, so that this:

auto values = emplace_array<std::string, 5>("1");

produces the exact same compiled code as this:

std::array<std::string, 5> values = { "1", "1", "1", "1", "1" };

Limitations

In practice this solution is less than ideal. It works fine for small values of N, but as N increases, so do our problems.

First, code bloat. Compilers may be able to optimize the aggregate initialization down to a simple loop which constructs each element of the array. On the other hand, they may not, so be wary (and perhaps use std::vector instead).

Secondly, when it comes to recursion, compilers generally have limits. My version of GCC has a default maximum template instantiation depth of 900, meaning that compilation will fail for values of N larger than 898.

Thirdly, the complexity of recursion in our template metaprogram is O(n), which means that compile times will increase linearly as the size of our array increases. This is bad news.

Coming soon: emplace_array 2.0

While the first issue may always be a problem, the other problems are soluble. In my next post, I will show how we can use more advanced TMP techniques to reduce the complexity to an acceptable O(log n).

How to get a type_index without RTTI

Have you ever wondered why the typeid operator only works when run-time type information (RTTI) is enabled?  Sure, RTTI is necessary when deducing the concrete types of polymorphic objects at runtime, but why should typeid(T) require RTTI when T is known at compile time?  Surely something as simple as converting T to unique integer ID should be possible?  Here I will show how to create your own CTTI (compile time type information) type_id function.

Note: The Boost libraries project offers a more comprehensive solution in Boost.TypeIndex, which not only provides an RTTI-less type_index, but also type names in string form (I assume they are using some compiler-specific Voodoo magic).  If you are unable or unwilling to use Boost, or are just interested for academic reasons, then continue reading!

Roll your own type_index

We want to be able to do something like this.

auto id = type_id<int>();

Our task is to produce a distinct value for each and every type.  One solution is to use a static local variable within a function template.

template<typename T>
int* type_id()
{
    static int id;
    return &id;
};

Thanks to the One Definition Rule, the linker must ensure that there is a single definition of each function template instance across all translation units, and since memory addresses must be unique, we now have a unique identifier for every possible type! This is the same principle that is used to implement the singleton pattern (though I wouldn't recommend it).

However, ideally we would like the same ID for regular, const, volatile and reference versions of a type (this is what typeid does).  We can use the relevant type traits templates to strip these off.

template<typename T>
int* type_id()
{
    using t = std::remove_cv_t<std::remove_reference_t<T>>;
    return type_id_with_cvr<t>();
};

template<typename T>
int* type_id_with_cvr()
{
    static int id;
    return &id;
};

But we aren't quite finished. Using the int* directly as a type index is less than ideal, the main problem being that arbitrary pointers cannot be compared using operator< and company. We can address this by creating a nice type-safe type_index wrapper class. And while we're at it, let's also add a specialization for std::hash so that we can use type_index objects as keys in unordered associative containers.

#include <functional>
#include <type_traits>

class type_index
{
private:
    int* id;
    type_index(int* id) : id(id) {}

public:
    bool operator==(type_index const& t) const
    { return id == t.id; }
    bool operator!=(type_index const& t) const
    { return id != t.id; }
    bool operator<(type_index const& t) const
    { return std::less<int*>()(id, t.id); }
    bool operator<=(type_index const& t) const
    { return !(t > *this); }
    bool operator>(type_index const& t) const
    { return t < *this; }
    bool operator>=(type_index const& t) const
    { return !(*this < t); }

    std::size_t hash_code() const { return std::hash<int*>()(id); }

    template<typename T>
    friend type_index type_id()
    {
        using t = std::remove_cv_t<std::remove_reference_t<T>>;
        return type_id_with_cvr<t>();
    };

    template<typename T>
    friend type_index type_id_with_cvr()
    {
        static int id;
        return &id;
    };
};

namespace std
{
    template<>
    struct hash<type_index>
    {
        std::size_t operator()(type_index const& t) const
        {
            return t.hash_code();
        }
    };
}

Now we're ready to roll! Keep in mind that the type_index for a given type will only be unique within the current program. Sharing type_index objects over shared library boundaries is not possible.

Note: If you do not have C++14, you will have to implement your own type traits helper types (remove_cv_t and remove_reference_t).  If you do not have C++11, you will have to implement your own type traits constructs from scratch (or find an existing implementation).