使用C++11的constexpr对std::map进行初始化

21

我希望用constexpr初始化一个包含键值的std::map。考虑以下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; }

尽管使用最近的clang和gcc编译代码,但生成的二进制文件将包含密钥类型的字符串:

C String Literals

为什么密钥包含在二进制文件中,即使它们被用作常量表达式?有没有办法解决这个问题?

当然,map初始化将在运行时发生。但是,在编译时,二进制文件中的值不应该被constexpr替换吗?

注:这当然是一个简化的例子。我知道有不同的boost结构可能更适合这种用例。我特别想知道为什么会发生这种情况。

[编辑]

无论是否启用优化,此行为都会发生。 以下代码编译时, bar 是字符串表中唯一的用户定义字符串:

#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;
    }
  }
}

为了验证结果,我使用了一个小的shell脚本。

$ 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

2
constexpr 意味着编译器可以在编译时使用结果。但这并不意味着所有的计算都必须在编译时完成。C++ 缺乏强制编译时评估的可能性,这是可怕的。一些编译器会抱怨“表达式过于复杂”... - Klaus
2
你使用优化编译了吗?clang在生成的汇编代码中没有这些关键字。 - Rakete1111
请查看编辑。 - muffel
“using namespace std;”是一个不好的编程习惯,永远不要使用它。 - tambre
5
我只使用它来保持多词表达的清晰简洁。 - muffel
6个回答

4
只声明为const是不够的。字符串被包含在二进制文件中,原因如下:
const map<unsigned int, const char*> values

是const,但不是constexpr。它会在程序启动时运行'str2int',而不是在编译时。const只能保证它不允许进一步的修改,但不会在编译时做出任何妥协。
看起来你正在寻找Serge Sans Paille的Frozen constexpr容器 -- https://github.com/serge-sans-paille/frozen 虽然我不知道它是否适用于C++11,但如果你想要性能提升,它绝对值得一试。
你可以创建在编译时进行哈希的映射,并且还能获得产生完美哈希函数的额外好处 -- 允许以O(1)时间(常数时间)访问所有键。
它确实是gperf的一个非常有竞争力的替代品。
目前,Clang和GCC对您能够在编译时处理的键的数量有限制。在我的1G RAM VPS上,使用clang生成具有2048个键的映射效果还不错。GCC目前甚至更糟糕,会更早地消耗掉你的所有RAM。

3
这个线程已经不是最新的了,但有时仍需要坚持使用c++11 :|
使用constexpr函数来设置键,怎么样?
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'
};

“单来源”键简化了这些映射的维护,一旦它们变得更大...

我的小型测试程序

...

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;
}

如果使用gcc 7.5编译,并添加参数

--std=c++11 -O0
,该程序可以正常运行且不含有任何关键字符串。


2

虽然这是一篇较旧的帖子,但您也可以使用兼容C++ 17的constexpr哈希映射constexpr-hash-map

这实质上是一个由我自己制作的仅包含头文件的哈希映射结构,旨在方便在constexpr上下文中进行构建和检索(包括查找)。

该库专门为const char*进行了特化,以便能够在编译时比较键,因此它适用于主要问题。


2
在回答中链接到自己的库是可以的,但在这种情况下最好明确披露你的关系。此外,链接是答案的补充(并且通常有助于提高其质量),但答案本身仍应包含解释/解决方案/示例。请[编辑]您的答案并添加一些解释(特别是您的库如何工作)。您可以在帮助中心找到有关编写良好答案的更多信息。 - YurkoFlisk

1
我无法使用g++(trunk)或clang++(trunk)进行复制。我使用了以下标志:-std=c++1z -Ofast。然后,我使用strings检查了编译二进制文件的内容:没有出现"foo""hello"
您是否启用了优化编译?
无论如何,您对str2int的使用不会强制进行编译时评估。为了强制执行它,您可以这样做:
constexpr auto k0 = str2int("foo");
constexpr auto k1 = str2int("hello");

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

我尝试了你所说的,而且似乎(奇怪的是)--std=C++1z选项也可以为我修复代码。不幸的是 - 如问题所述 - 我需要在某个出现问题的项目中使用C++11。有什么办法可以在C++11中修复它吗? - muffel
1
你确定不是 -Ofast 修复了代码吗? - Vittorio Romeo
是的,我再次尝试使用macOS 10.13.1上的gcc 7.2.0和clang-802.0.38。如果我使用--std=C++1z,两者都会省略关键字符串。 - muffel

1
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"}
};

这应该强制进行编译时评估。

中,它稍微不那么冗长:

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"}
};

而在中:

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"}
};

它可以使用大多数原始类型常量而无需特定于类型的版本。


1

在GCC 7.2、clang 5.0或MSVC 17中使用--std=c++11 -O2无法重现您的问题。

演示

您是否开启了调试符号(-g)进行构建?这可能是您看到的原因。


奇怪,看一下我的编辑底部我是如何测试的。也许我漏掉了什么? - muffel
如果您尝试使用“-O2”会怎样?“objdump -sghCd”输出什么? - rustyx

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接