use c++ 11 constexpr for std::map initialization

Question

I want to initialize a std::map with the keys being a constexpr. Consider the following C++11 MWE:

#include <map>
using std::map;

constexpr unsigned int str2int(const char* str, const int h = 0) {
    return !str[h] ? 5381 : (str2int(str, h + 1) * 33) ^ str[h];
}

const map<unsigned int, const char*> values = {
    {str2int("foo"), "bar"},
    {str2int("hello"), "world"}
};

int main() { return 0; }

While the code compiles which recent clang and gcc, the resulting binary will contain the strings of the key type:

Why are the keys contained in the binary even though they are used as constexpr's? Any way to work around this behavior?

Of course the map initialization will occur at runtime. But shouldn't the values in the binary be replaced with the constexpr's at compiletime?

Note: This is of course a simplified example. I know there are different boost structures which may be more suitable for this use case. I'm especially interested in why this is happening.

[Edit]

The behavior occurs no matter if optimizations are enabled or not. The following code compiles with bar being the only user defined string in the string table:

#include <map>
#include <iostream>
#include <string>

using namespace std;

constexpr unsigned int str2int(const char* str, const int h = 0) {
  return !str[h] ? 5381 : (str2int(str, h + 1) * 33) ^ str[h];
}

int main() {
  string input;
  while(true) {
    cin >> input;
    switch(str2int(input.c_str())) {
      case str2int("quit"):
      return 0;
      case str2int("foo"):
      cout << "bar" << endl;
    }
  }
}

To verify the results I was using a small shell script

$ for x in "gcc-mp-7" "clang"; do 
  $x --version|head -n 1
  $x -lstdc++ -std=c++11 -Ofast constexpr.cpp -o a
  $x -lstdc++ -std=c++1z -Ofast constexpr.cpp -o b
  strings a|grep hello|wc -l
  strings b|grep hello|wc -l
done

gcc-mp-7 (MacPorts gcc7 7.2.0_0) 7.2.0
       1
       0
Apple LLVM version 8.1.0 (clang-802.0.38)
       1
       0

Answer 1

Declaring only as const is not enough. The strings are included in the binary because:

const map<unsigned int, const char*> values

is const, but not constexpr. It will run 'str2int' when your program starts, not at compile time. Being const will only guarantee you that it will not allow further modifications, but makes no compile time compromises.

It seams you're searching for the Serge Sans Paille's Frozen constexpr containers -- https://github.com/serge-sans-paille/frozen

Although I don't know if it will work on C++11, if you want performance gains, it definitely worths a try.

You can create maps that are hashed at compile time and will give you the additional benefit of producing a perfect hash function -- allowing all keys to be accessed in O(1) time (constant time).

It is a very competent substitute for gperf indeed.

Clang and GCC, currently, impose a limit on the number of keys you are able to process at compile time. Producing a map with 2048 keys turned out OK on my 1G RAM VPS only with clang. GCC is currently even worse and will eat all your RAM much sooner.

Answer 2

this thread isn't really fresh, but to stick to c++11 is still required sometimes :|

how about using a constexpr function to set the keys:

constexpr int makeKey(const char* s) { // c++ refused 'auto' here
  return str2int(s); // using str2int from above
}

const std::map<unsigned int, const char*> values = {
    {k0, "bar"}, // these require another declaration (see above) 
    {k1, "world"}, 
    {makeKey("its"), "me"} // this initialization is 'single source'
};

'single source' keys simplify the maintenance of such maps once they become bigger ...

My small test program

...

int main(int argc, char** argv) {

  for(int i(1);i<argc;++i)  {
    const std::map<unsigned int, const char*>::const_iterator cit(values.find(str2int(argv[i])));
    std::cout << argv[i] << " gets " << (cit==values.cend()?"nothing":cit->second) << std::endl;
  }

  return 0;
}

works fine and does not contain any of the key strings if compiled with gcc 7.5 using

--std=c++11 -O0

Answer 3

Older thread, but you could also use C++ 17 compatible constexpr hash-map: constexpr-hash-map.

This is essentialy a header-only hash-map-like structure made by myself in order to faciliate construction and retrieval (including lookup) in compile time in constexpr context.

The library has got specialization for the const char* to be able to compare keys in compile-time, so it would work for the main question.

Answer 4

I cannot reproduce with neither g++ (trunk) or clang++ (trunk). I used the following flags: -std=c++1z -Ofast. I then checked the contents of the compiled binary with strings: neither "foo" or "hello" were there.

Have you compiled with optimizations enabled?

Regardless, your use of str2int does not force compile-time evaluation. In order to force it, you can do:

constexpr auto k0 = str2int("foo");
constexpr auto k1 = str2int("hello");

const map<unsigned int, const char*> values = {
    {k0, "bar"},
    {k1, "world"}
};

Answer 5

Cannot reproduce your issue using --std=c++11 -O2 in GCC 7.2, clang 5.0 or MSVC 17.

DEMO

Are you building with debug symbols on (-g)? That could be what you're seeing.

Answer 6

template<unsigned int x>
using kuint_t = std::integral_constant<unsigned int, x>;

const map<unsigned int, const char*> values = {
  {kuint_t<str2int("foo")>::value, "bar"},
  {kuint_t<str2int("hello")>::value, "world"}
};

that should force compile time evaluation.

In c++14 it is a bit less verbose:

template<unsigned int x>
using kuint_t = std::integral_constant<unsigned int, x>;
template<unsigned int x>
kuint_t<x> kuint{};

const map<unsigned int, const char*> values = {
  {kuint<str2int("foo")>, "bar"},
  {kuint<str2int("hello")>, "world"}
};

and in c++17:

template<auto x>
using k_t = std::integral_constant<std::decay_t<decltype(x)>, x>;
template<auto x>
k_t<x> k{};

const map<unsigned int, const char*> values = {
  {k<str2int("foo")>, "bar"},
  {k<str2int("hello")>, "world"}
};

it works with most primitive type constants without a type-specific version.