Compile-time population of data structures other than arrays?

Question

In C++, you can do this:

static const char * [4] = {
   "One fish",
   "Two fish",
   "Red fish",
   "Blue fish"
};

... and that gives you a nice read-only array data-structure that doesn't take any CPU cycles to initialize at runtime, because all the data has been laid out for you (in the executable's read-only memory pages) by the compiler.

But what if I'd rather be using a different data structure instead of an array? For example, if I wanted my data structure to have fast lookups via a key, I'd have to do something like this:

static std::map<int, const char *> map;

int main(int, char **)
{
   map.insert(555, "One fish");
   map.insert(666, "Two fish");
   map.insert(451, "Red fish");
   map.insert(626, "Blue fish");

   [... rest of program here...]
}

... which is less elegant and less efficient as the map data structure is getting populated at run-time, even though all the necessary data was known at compile time and therefore that work could have (theoretically) been done then.

My question is, is there any way in C++ (or C++11) to create a read-only data structure (such as a map) whose data is entirely set up at compile time and thus pre-populated and ready to use at run-time, the way an array can be?

Answer 1

If you want a map (or set), consider instead using a binary tree stored as an array. You can assert that it's ordered properly at runtime in debug builds, but in optimized builds you can just assume everything is properly arranged, and then can do the same sorts of binary search operations that you would in std::map, but with the underlying storage being an array. Just write a little program to heapify the data for you before pasting it into your program.

Answer 2

Not easily, no. If you tried to do your first example using malloc, obviously it wouldn't work at compile time. Since every single standard container utilizes new (well, std::allocator<T>::allocate(), but we'll pretend that it's new for now), we cannot do this at compile time.

That having been said, it depends on how much pain you are willing to go through, and how much you want to push back to compile time. You certainly cannot do this using only standard library features. Using boost::mpl on the other hand...

#include <iostream>

#include "boost/mpl/map.hpp"
#include "boost/mpl/for_each.hpp"
#include "boost/mpl/string.hpp"
#include "boost/mpl/front.hpp"
#include "boost/mpl/has_key.hpp"

using namespace boost::mpl;

int main()
{
    typedef string<'One ', 'fish'> strone;
    typedef string<'Two ', 'fish'> strtwo;
    typedef string<'Red ', 'fish'> strthree;
    typedef string<'Blue', 'fish'> strfour;

    typedef map<pair<int_<555>, strone>,
        pair<int_<666>, strtwo>,
        pair<int_<451>, strthree>,
        pair<int_<626>, strfour>> m;

    std::cout << c_str<second<front<m>::type>::type>::value << "\n";
    std::cout << has_key<m, int_<666>>::type::value << "\n";
    std::cout << has_key<m, int_<111>>::type::value << "\n";
}

Answer 3

It's worth mentioning, that your problem stems from the fact you are using map. Maps are often overused. The alternative solution to a map is a sorted vector/array. Maps only become "better" than maps when used to store data that is of unknown length, or (and only sometimes) when the data changes frequently.

The functions std::sort, std::lower_bound/std::upper_bound are what you need. If you can sort the data yourself you only need one function, lower_bound, and the data can be const.