使用constexpr进行编译时哈希

Question

我在一本书中找到了一个编译时创建SDBM哈希的例子/类。不幸的是，它无法编译（无论是使用c++11还是c++14都是如此）。我得到了“error: call to non-constexpr function”的错误。我尝试了一些方法，但似乎无法使其工作。所以这是我的问题：

1. 为什么它不能工作，如何修复？（对于一个非常具体的情况，我很抱歉，我知道这是一个通用的问题）

以下是完整的（不起作用的）示例供您测试：

#include <iostream>

template <int stringLength>
struct SDBMCalculator
{
    static inline int Calculate(const char* const stringToHash, int& value)
    {
            int character = SDBMCalculator<stringLength - 1>::Calculate(stringToHash, value);
            value = character + (value << 6) + (value << 16) - value;
            std::cout << static_cast<char>(character) << std::endl << value << std::endl << std::endl;
            return stringToHash[stringLength - 1];
    }

    static inline int CalculateValue(const char* const stringToHash)
    {
            int value = 0;
            int character = SDBMCalculator<stringLength>::Calculate(stringToHash, value);
            value = character + (value << 6) + (value << 16) - value;
            std::cout << static_cast<char>(character) << std::endl << value << std::endl << std::endl;
            return value;
    }
};

template <>
struct SDBMCalculator<1>
{
    static inline int Calculate(const char* const stringToHash, int& value)
    {
            return stringToHash[0];
    }
};


int main()
{
  constexpr int eventID = SDBMCalculator<5>::CalculateValue("Hello");
  std::cout << eventID << std::endl;
}

非常感谢您的时间和努力！

- llh

---

我能说的唯一一件事就是重复错误信息：您正在调用未标记为constexpr的函数。您的Calculate和CalculateValue函数不是constexpr。在计算constexpr值时，您不能调用非constexpr函数。 - CygnusX1

你可能想要使用 const。由于你在运行时提供了参数，因此函数的值在编译时不确定。 - Ron

Answer 1

根据 http://en.cppreference.com 的说法：

constexpr变量必须满足以下要求：

其初始化的完整表达式（包括所有隐式转换、构造函数调用等）必须是常量表达式。

在赋值表达式中：

constexpr int eventID = SDBMCalculator<5>::CalculateValue("Hello");

我们使用的CalculateValue没有标记为constexpr。

那么我们有两个选择：

1. 将constexpr更改为const 2. 尝试将CalculateValue变成一个constexpr函数

由于第一个选择非常无聊，让我们专注于第二个选择，以更好地理解常量表达式的工作原理！

因此，我们从将CalculateValue标记为constexpr开始。

static constexpr inline int CalculateValue(const char* const stringToHash)

现在CalculateValue必须只调用constexpr函数。因此，我们还必须将Calculate变为constexpr。

static constexpr inline int Calculate(const char* const stringToHash, int& value)

这会导致许多编译器错误。

幸运的是，我们可以注意到流不适合放入constexpr中，因为对流的操作没有标记为constexpr。( operator<< 就像普通函数一样，它不是constexpr的)。

所以让我们从中移除 std::cout ！

好了，就快完成了。我们还必须使 SDBMCalculator<1> 中的 Calculate 也是 constexpr，因为它可能被两个计算函数调用。

最终代码如下：

#include <iostream>

template <int stringLength>
struct SDBMCalculator
{
    static constexpr inline int Calculate(const char* const stringToHash, int& value)
    {
            int character = SDBMCalculator<stringLength - 1>::Calculate(stringToHash, value);
            value = character + (value << 6) + (value << 16) - value;
            return stringToHash[stringLength - 1];
    }

    static constexpr inline int CalculateValue(const char* const stringToHash)
    {
            int value = 0;
            int character = SDBMCalculator<stringLength>::Calculate(stringToHash, value);
            value = character + (value << 6) + (value << 16) - value;
            return value;
    }
};

template <>
struct SDBMCalculator<1>
{
    static constexpr inline int Calculate(const char* const stringToHash, int& value)
    {
            return stringToHash[0];
    }
};


int main()
{
  constexpr int eventID = SDBMCalculator<5>::CalculateValue("Hello");
  std::cout << eventID << std::endl;
}

当然，它无法编译！我们得到以下错误信息：

error: shift expression '(4723229 << 16)' overflows [-fpermissive]

value = character + (value << 6) + (value << 16) - value;

这是因为编译器不希望在常量表达式中发生溢出。

我们可以在编译代码时添加-fpermissive标志来忽略此错误（但这样会不安全）。

g++ example.cpp -o example.exe -fpermissive

现在它编译并且运行得很好！ 常量表达式修饰符使得编译器在编译时计算哈希值。

这很好，因为我们不会浪费运行时资源，但如果你使用大量这样的模板和constexpr，并让编译器计算所有这些东西，编译速度将会极慢！

我希望你现在更好地理解了constexpr的行为 :)

- Piotr Styczyński

---

非常感谢您详细的回答！非常好，我希望我能选择两个答案。我觉得人们应该先阅读CygnusX1的答案，然后再来看您的答案，如果他们想要/需要更多的背景信息的话。 - llh

关于溢出部分的注意事项。错误不是因为编译时，而是因为在有符号整数上溢出 << 是未定义行为。constexpr 只允许编译器在编译时检测 UB。你真正应该做的是使用 unsigned int 。溢出它具有明确定义的行为，并且在运行时和编译时都可以正常工作，没有任何错误/警告。 - CygnusX1

Answer 2

阅读错误消息：在评估constexpr值时，您正在调用非constexpr函数。您尝试过修复吗？

当您将所有相关函数设置为constexpr时，您将获得一些需要注意的额外错误。一些备注：

• Make sure you compile with -std=c++14. C++11 is not good enough for this.
• remove all operations on std::cout from within SDBMCalculator functions - those are not permitted at compile-time

• change int into unsigned int in all relevant computations. When left shift overflows on int type you get an undefined behavior. Left shift on unsigned type is computed modulo its maximum value+1 instead.

  error: shift expression ‘(4723229 << 16)’ overflows
  constexpr int eventID = SDBMCalculator<5>::CalculateValue("Hello")
  

通过以上所有修复，您的代码将能够正常工作。我得到了以下结果：

2873473298

- CygnusX1

---

@Ron 使用有符号整数时，行为是未定义的。没有可以更改的功能。 - n. m.

@n.m. 我明白了，感谢你。 - Ron

快速而痛苦的答案。谢谢。学到了东西。 - llh