在编译时使用Constexpr填充数组

Question

我希望使用constexpr填充枚举类型的数组。该数组的内容遵循一定的模式。

我有一个将ASCII字符集分为四类的枚举类型。

enum Type {
    Alphabet,
    Number,
    Symbol,
    Other,
};

constexpr Type table[128] = /* blah blah */;

我希望有一个由128个Type组成的数组。它们可以被放在一个结构中。 数组的索引将与ASCII字符相对应，而值将是每个字符的Type。

这样我就可以查询此数组以找出ASCII字符属于哪个类别。例如：

char c = RandomFunction();
if (table[c] == Alphabet) 
    DoSomething();

我想知道是否有可能在不使用冗长宏的情况下实现这一点。

目前，我通过以下方式初始化表格。

constexpr bool IsAlphabet (char c) {
    return ((c >= 0x41 && c <= 0x5A) ||
            (c >= 0x61 && c <= 0x7A));
}

constexpr bool IsNumber (char c) { /* blah blah */ }

constexpr bool IsSymbol (char c) { /* blah blah */ }

constexpr Type whichCategory (char c) { /* blah blah */ }

constexpr Type table[128] = { INITIALIZE };

INITIALIZE是一些非常冗长宏代码的入口点。类似于这样：

#define INITIALIZE INIT(0)
#define INIT(N) INIT_##N
#define INIT_0 whichCategory(0), INIT_1
#define INIT_1 whichCategory(1), INIT_2
//...
#define INIT_127 whichCategory(127)

我希望有一种方法可以填充这个数组，或者创建一个包含该数组的结构，而不需要使用宏；也许可以尝试类似下面的方式：

struct Table {
    Type _[128];
};

constexpr Table table = MagicFunction();

那么问题是如何编写这个MagicFunction？

注意：我知道之类的，但这个问题更多的是一个“这是否可能？”而不是“这是否是最好的方法？”。

任何帮助都将不胜感激。

谢谢。

- Jimmy Lu

---

你知道ASCII只有[0 .. 127]的范围吗？而且char的符号是由实现定义的。你目前的方法非常危险。哦，最后但并非最不重要的是，C++标准根本不要求使用ASCII编码。它也可以是EBCDIC。 - Xeo

好消息是，因为数组可以使用打包扩展进行初始化，所以你所要求的确实是可行的。你只需要多次调用该函数即可 :p - Matthieu M.

@DyP: ((c >= 0x41 && c <= 0x5A) || (c >= 0x61 && c <= 0x7A)) 来自 IsAlphabet -- 这假设了 ASCII 中存在的十进制排序。符号很重要，因为 OP 传递字面值 > 127，这可能映射到负的 char。 - Xeo

@BeyondSora：非常抱歉，昨天我没有时间好好回答这个问题。幸运的是，Xeo做到了（尽管他有点脾气 :p）。索引生成与打包扩展相结合是生成各种初始化列表的绝妙技巧（正如您在此处所见），因此我指出了一个事实，即由于数组接受初始化列表，因此您很棒。 - Matthieu M.

@DyP：在EBCDIC中，0x41根本没有映射到任何符号，并且字母在代码页中的位置很奇怪。请参见这里。 - Xeo

Answer 1

忽略所有问题，索引来拯救：

template<unsigned... Is> struct seq{};
template<unsigned N, unsigned... Is>
struct gen_seq : gen_seq<N-1, N-1, Is...>{};
template<unsigned... Is>
struct gen_seq<0, Is...> : seq<Is...>{};

template<unsigned... Is>
constexpr Table MagicFunction(seq<Is...>){
  return {{ whichCategory(Is)... }};
}

constexpr Table MagicFunction(){
  return MagicFunction(gen_seq<128>{});
}

实时示例。

- Xeo

---

@Steven：添加了一个链接到Lounge<C++>的维基条目。它基本上构建了一个列表 [0 .. 127] 并扩展它，调用 whichCategory(0), whichCategory(1), ..., whichCategory(127) 并将其作为初始化参数传递给 Table._（注意内部数组初始化的双 {}）。 - Xeo

我不知道你可以返回这种形式的东西 { /*...*/ }，这是C++11中的新特性还是一直都在标准中存在？ - Jimmy Lu

@BeyondSora：新手入门C++11，称为列表初始化（也更不正式、更常见地称为统一初始化）。 - Xeo

为什么要使用双花括号？ - Yola

这个答案在C++14中已经过时，因为C++14允许你在constexpr函数内构建整个数组。 - Omnifarious

Answer 2

在C++17中，::std::array已经升级以更加支持 constexpr，您可以像在C++14中那样编写代码，但无需使用一些看起来很可怕的技巧来绕过某些关键地方缺乏 constexpr 的限制。下面是代码示例：

#include <array>

enum Type {
    Alphabet,
    Number,
    Symbol,
    Other,
};

constexpr ::std::array<Type, 128> MagicFunction()
{
   using result_t = ::std::array<Type, 128>;
   result_t result = {Other};
   result[65] = Alphabet;
   //....
   return result;
}

const ::std::array<Type, 128> table = MagicFunction();

需要注意的是，MagicFunction 仍然需要遵守相对宽松的 constexpr 规则。主要来说，它不能修改任何全局变量或使用 new（这意味着修改全局状态，即堆）或其他类似的操作。

- Omnifarious

---

我来到这里尝试用以下方式填充一个 std::array<std::pair<X,Y>>：result[65] = std::make_pair(x, y)。但是这样做行不通，但是 result[65].first = x; result[65].second = y; 可以。 - mxmlnkn

Answer 3

在我看来，做这件事情最好的方法就是编写一个小型安装程序，用于生成 table。然后你可以抛弃这个安装程序，或者将其与生成的源代码一起提交。

这个问题的棘手之处与另一个问题重复：使用模板元编程创建和初始化值数组是否可行？

关键在于，无法编写类似以下代码的东西：

Type table[256] = some_expression();

在文件作用域，因为全局数组只能使用字面（源级）初始化列表进行初始化。即使你可以以某种方式使该函数返回一个std::initializer_list，也无法使用constexpr函数的结果来初始化全局数组，因为其构造函数未声明为constexpr。

因此，你需要让编译器为你生成数组，通过将其作为模板类的静态const数据成员。经过一两层我无法写出的元编程后，你将会得到一行类似于下面的代码：

template <int... Indices>
Type DummyStruct<Indices...>::table[] = { whichCategory(Indices)... };

其中Indices是一个参数包，看起来像0,1,2,... 254,255。你可以使用递归辅助模板或者Boost库中的某些东西来构建该参数包。然后你就可以编写代码了。

constexpr Type (&table)[] = IndexHelperTemplate<256>::table;

但是，当表只有256个条目且除非ASCII本身发生变化否则永远不会改变时，为什么要这样做呢？正确的方式 就是 最简单的方式：预先计算所有256个条目并显式地编写出表格，不使用模板、constexpr或任何其他神奇的东西。

- Quuxplusone

---

在我看来，硬编码是不好的，因为如果那些值很复杂（在更一般的情况下），理解它们的逻辑非常重要。如果有n个预生成的阶乘值，那么如何确保没有复制粘贴错误或某些值上的错误呢？ - Isaac Pascual

如果有n行复杂的元编程来计算值，谁能确保代码中没有复制粘贴错误或漏洞？我们的目标始终是减少错误的可能性。对于像三行factorial函数这样的东西，也许你可以通过编写代码而不是数据来最小化错误的可能性。对于OP实际遇到的问题——一个128字节的分类表——我仍然坚信编写数据而不是代码是最小化错误可能性的最佳方法。（但请注意，自2012年以来，constexpr编程已经变得更加强大和自然。） - Quuxplusone

我更喜欢看到数据背后的东西，而不是硬编码的数字。 - Isaac Pascual

Answer 4

在C++14中实现这一点的方法如下：

#include <array>

enum Type {
    Alphabet,
    Number,
    Symbol,
    Other,
};

constexpr ::std::array<Type, 128> MagicFunction()
{
   using result_t = ::std::array<Type, 128>;
   result_t result = {Other};
   const result_t &fake_const_result = result;
   const_cast<result_t::reference>(fake_const_result[65]) = Alphabet;
   //....
   return result;
}

const ::std::array<Type, 128> table = MagicFunction();

不需要聪明的模板操作了。不过，因为C++14没有对标准库中需要和不需要使用constexpr进行彻底的审查，所以必须使用涉及到const_cast的可怕黑客技巧。

当然，MagicFunction最好不要修改任何全局变量或违反constexpr规则，但这些规则现在相当自由。例如，您可以随意修改所有本地变量，尽管通过引用传递它们或取它们的地址可能不那么顺利。

请看我的其他回答，了解C++17，它允许您放弃一些丑陋的技巧。

- Omnifarious

---

你甚至可以在 MagicFunction 中使用 for 循环。 - aschepler

我收到一个有关result未初始化声明的错误。 std :: array <Type，128> result {};可以工作 - 我猜Type {}是Alphabet。 - aschepler

@user1754322 - 请查看这个问题：https://dev59.com/JXI-5IYBdhLWcg3w0MDx - Omnifarious

嗯...这个在C++14下无法编译。你需要一个constexpr reference operator[]( size_type pos );，它只存在于C++17中：http://en.cppreference.com/w/cpp/container/array/operator_at - Tim Rae

@TimRae - 完成了. :-) - Omnifarious