如何安全实施"Using Uninitialized Memory For Fun And Profit"？
How to safely implement "Using Uninitialized Memory For Fun And Profit"?
我想使用 https://research.swtch.com/sparse 中描述的技巧在 C++ 中构建一个密集整数集。这种方法通过允许自身读取未初始化的内存来实现良好的性能。
如何在不触发未定义行为的情况下实现此数据结构，并且 运行 不与 Valgrand 或 ASAN 等工具冲突？
编辑：回复者似乎在关注 "uninitialized" 这个词，并在语言标准的上下文中对其进行解释。对我而言，这可能是一个糟糕的词选择 - 这里 "uninitialized" 仅表示它的值对于算法的正确运行并不重要。显然可以安全地实现这个数据结构（LLVM 在 SparseMultiSet 中实现）。我的问题是最好和最有效的方法是什么？
如果我们改写您的问题：
What code reads from uninitialized memory without tripping tools designed to catch reads from uninitialized memory?
那么答案就很明确了——不可能。您可以找到的任何执行此操作的方法都代表了 Valgrind 中的一个错误，该错误将被修复。
也许在没有 UB 的情况下可以获得相同的性能，但是您对问题设置的限制 "I would like to... use the trick... allowing itself to read uninitialized memory" 保证了 UB。任何避免 UB 的竞争方法都不会使用您如此喜欢的技巧。
如果您只是读取未初始化的内存，Valgrind 不会报错。
如果您 使用 这些数据的方式影响了 Valgrind 将会抱怨
程序的可见行为，例如使用此数据作为系统调用中的输入，或基于此数据进行跳转，或使用此数据计算另一个地址。有关详细信息，请参阅 http://www.valgrind.org/docs/manual/mc-manual.html#mc-manual.uninitvals。
因此，很可能您对 Valgrind 没有任何问题。
如果 valgrind 仍然报错，但即使使用此 uninit 数据您的算法也是正确的，那么您可以使用客户端请求将此内存声明为已初始化。
我可以看到您可以采用的四种基本方法。这些不仅适用于 C++，也适用于大多数其他低级语言，如 C，使未初始化的访问成为可能，但 allowed，最后一个甚至适用于更高级别的 "safe" 语言。
忽略标准，照常执行
这是语言律师最讨厌的一种疯狂把戏！不过请不要惊慌失措 - 后面的解决方案不会违反规则，所以如果您是遵守规则的人，请跳过这一部分。
该标准大部分使用未初始化的值 undefined 并且它允许的少数漏洞（例如，将一个未定义的值复制到另一个）并没有真正给你足够的绳索来实际上实现你想要的 - 即使在限制性稍低的 C 中（例如参见 [=73=] covering C11，它解释了在访问 indeterminiate 值时可能不会直接触发 UB 任何结果也是 不确定的 并且实际上该值可能看起来是偶然访问）。
所以你无论如何都要实现它，知道大多数或所有当前编译器只会将它编译成预期的代码，并且知道你的代码不符合标准。
至少在my test中，gcc、clang和icc都没有利用非法访问做任何疯狂的事情。当然，该测试并不全面，即使您可以构建一个测试，行为也可能会在新版本的编译器中发生变化。
如果访问未初始化内存的方法的实现在一个单独的编译单元中被编译一次，那将是最安全的——这样可以很容易地检查它是否做了正确的事情（只需检查一次程序集）并且使编译器几乎不可能（在 LTGC 之外）做任何棘手的事情，因为它无法证明是否正在访问未初始化的值。
不过，这种方法在理论上是 不安全的 并且您应该非常仔细地检查编译后的输出，如果您采用它，还应采取额外的保护措施。
如果您采用这种方法，valgrind 等工具很可能会报告未初始化的读取错误。
现在这些工具在汇编级别工作，一些未初始化的读取可能没问题（例如，参见快速标准库实现的下一项），因此它们实际上不会立即报告未初始化的读取，但是而是使用各种试探法来确定是否 实际使用了 无效值。例如，他们可能会避免报告错误，直到他们确定未初始化的值用于确定条件跳跃的方向，或根据启发式确定不是 trackable/recoverable 的其他一些操作。您 可能 能够让编译器发出读取未初始化内存但根据此启发式是安全的代码。
更有可能的是，您无法做到这一点（因为这里的逻辑相当微妙，因为它依赖于两个数组中值之间的关系），因此您可以使用 抑制 在您选择的工具中隐藏错误的选项。例如，valgrind 可以基于 stack trace 进行抑制 - 事实上，在各种标准库中已经有许多默认用于隐藏误报的抑制条目。
由于它基于堆栈跟踪工作，如果读取发生在内联代码中，您可能会遇到困难，因为每个调用站点的堆栈顶部都会不同。您可以通过确保函数未内联来避免这种情况。
使用程序集
标准中定义不明确的内容通常在汇编级别定义明确。这就是为什么编译器和标准库通常可以比用 C 或 C++ 更快地实现事物的原因：用汇编编写的 libc 例程已经针对特定的体系结构并且不必担心语言规范中的各种注意事项可以使 运行 在各种硬件上更快。
通常情况下，在汇编中实现任何大量代码都是一项代价高昂的工作，但在这里它只是少数，所以它可能是可行的，具体取决于您的目标平台数量。您甚至不需要自己编写方法 - 只需编译 C++ 版本（或使用 godbolt 并复制程序集。is_member 函数，例如 1，看起来像：
sparse_array::is_member(unsigned long):
mov rax, QWORD PTR [rdi+16]
mov rdx, QWORD PTR [rax+rsi*8]
xor eax, eax
cmp rdx, QWORD PTR [rdi]
jnb .L1
mov rax, QWORD PTR [rdi+8]
cmp QWORD PTR [rax+rdx*8], rsi
sete al
依靠calloc魔法
如果您使用 calloc2，您会明确地从底层分配器请求零内存。现在 calloc 的 正确 版本可以简单地调用 malloc 然后将 returned 内存清零，但实际实现依赖于这样一个事实OS 级别的内存分配例程（sbrk 和 mmap，几乎）通常会 return 你将内存归零到任何 OS 受保护的内存（即所有大的），以避免再次将内存清零。
作为一个实际问题，对于大型分配，这通常通过映射一个特殊的 零页 全零来实现像匿名 mmap 这样的调用来满足。当（如果有的话）内存被写入时，写时复制实际上是否分配了一个新页面。因此，由于 OS 已经需要将页面归零，因此大的归零内存区域的分配可能 免费 。
在这种情况下，在 calloc 之上实施稀疏集可能与名义上未初始化的版本一样快，同时安全且符合标准。
Calloc 注意事项
您当然应该进行测试以确保 calloc 的行为符合预期。优化的行为通常只会在您的程序初始化大量长寿命零内存大约 "up-front" 时才会发生。也就是说，优化 calloc 的典型逻辑是这样的：
calloc(N)
if (can satisfy a request for N bytes from allocated-then-freed memory)
memset those bytes to zero and return them
else
ask the OS for memory, return it directly because it is zeroed
基本上，malloc 基础设施（也是 new 和朋友的基础）有一个（可能是空的）内存池，它已经从 OS 请求并通常尝试先分配到那里。该池由来自 OS 的最后一个块请求但未分发的内存组成（例如，因为用户请求了 32 字节但分配请求来自 OS 的 1 MB 块中的块，所以剩下很多），还有分配给进程但随后通过 free 或 delete 或其他方式 returned 的内存。该池中的内存具有任意值，如果可以从该池中满足 calloc，则您不会获得魔法，因为必须进行零初始化。
另一方面，如果必须从 OS 分配内存，你就会得到魔法。所以这取决于你的用例：如果你经常创建和销毁 sparse_set 对象，你通常只会从内部 malloc 池中提取并支付归零成本。如果你有一个占用大量内存的长寿命 sparse_set 对象，它们很可能是通过询问 OS 分配的，你几乎可以免费获得清零。
好消息是，如果您不想依赖上面的 calloc 行为（实际上，在您的 OS 或您的分配器上，它甚至可能不会以这种方式进行优化)，您通常可以通过手动映射 /dev/zero 来复制行为以进行分配。在提供它的 OSes 上，这保证您获得 "cheap" 行为。
使用惰性初始化
对于完全与平台无关的解决方案，您可以简单地使用另一个跟踪数组初始化状态的数组。
首先选择一些颗粒，您将在其中跟踪初始化，并使用位图，其中每个位跟踪 sparse 数组的该颗粒的初始化状态。
例如，假设您选择的颗粒为 4 个元素，数组中元素的大小为 4 个字节（例如，int32_t 值）：您需要 1 位来跟踪每 4 个elements * 4 bytes/element * 8 bits/byte，这是分配内存中不到 1%3 的开销。
现在您只需在访问sparse之前检查此数组中的相应位即可。这会为访问 sparse 数组增加一些小成本，但不会改变整体的复杂性，而且检查速度仍然很快。
例如，您的 is_member 函数现在 looks like:
bool sparse_set::is_member(size_t i){
bool init = is_init[i >> INIT_SHIFT] & (1UL << (i & INIT_MASK));
return init && sparse[i] < n && dense[sparse[i]] == i;
}
在 x86 (gcc) 上生成的程序集现在开始于：
mov rax, QWORD PTR [rdi+24]
mov rdx, rsi
shr rdx, 8
mov rdx, QWORD PTR [rax+rdx*8]
xor eax, eax
bt rdx, rsi
jnc .L2
...
.L2:
回复
这就是与位图检查有关的所有内容。这一切都会非常快（并且通常会偏离关键路径，因为它不是数据流的一部分）。
一般来说，这种方法的成本取决于你的集合的密度，以及你调用的函数 - is_member 是这种方法的最坏情况，因为一些函数（例如，clear) 根本不受影响，而其他人（例如 iterate）可以批处理 is_init 检查，并且每 INIT_COVERAGE 个元素只执行一次（这意味着开销会再次增加示例值约为 1%）。
有时这种方法 比 OP link 中建议的方法 更快，尤其是当处理元素不在集合中时 - 在这种情况下，is_init 检查将失败并且通常会缩短剩余代码，在这种情况下，您的工作集比 sparse 数组的大小小得多（使用示例粒度的 256 倍），因此您可能会大大减少 DRAM 或外部高速缓存级别的未命中。
颗粒大小本身是此方法的重要可调参数。直观地说，当第一次访问该颗粒覆盖的元素时，较大的颗粒大小会付出较大的初始化成本，但可以节省内存和前期 is_init 初始化成本。您可以想出一个公式来找到简单情况下的最佳大小 - 但行为还取决于值的 "clustering" 和其他因素。最后，使用动态粒度来覆盖不同工作负载下的基础是完全合理的 - 但它是以可变班次为代价的。
真正懒惰的解决方案
值得注意的是 calloc 和 lazy init 解决方案之间有一个相似之处：两者都在需要时延迟初始化内存块，但是 calloc 解决方案通过带有页表和 TLB 条目的 MMU 魔术在硬件中隐式跟踪这一点，而 lazy init 解决方案在软件中执行此操作，使用位图显式跟踪已分配的颗粒.
硬件方法的优点是几乎免费（对于 "hit" 情况，无论如何），因为它使用 CPU 中始终存在的虚拟内存支持来检测未命中，但是软件案例具有便携和允许精确控制颗粒大小等优点
你实际上可以结合这些方法，做一个不使用位图的惰性方法，甚至根本不需要 dense 数组：只需分配你的 sparse 数组mmap 为 PROT_NONE，因此每当您从 sparse 数组中的未分配页面读取时都会出错。您发现错误并在 sparse 数组中分配页面，其中标记值指示每个元素的 "not present"。
这是 "hot" 案例中最快的：您不再需要任何 ... && dense[sparse[i]] == i 检查。
缺点是：
- 您的代码确实不可移植，因为您需要实现故障处理逻辑，这通常是特定于平台的。
- 您无法控制粒度：它必须是页面粒度（或其倍数）。如果你的集合非常稀疏（比如 4096 个元素中只有不到 1 个被占用）并且分布均匀，你最终会付出高昂的初始化成本，因为你需要处理错误并为每个元素初始化整页值。
- 未命中（即，对不存在的集合元素的非插入访问）要么需要分配一个页面，即使该范围内不存在任何元素，要么每次都非常慢（引发错误） .
1 此实现没有 "range checking" - 即，它不检查 i 是否大于 MAX_ELEM - 取决于你的用例你可能想检查一下。我的实现为 MAX_ELEM 使用了一个模板参数，这可能会导致代码速度稍快，但也会更加臃肿，您最好也将最大大小设置为 class 成员。
2 真的，唯一的要求是你使用在幕后调用 calloc 的东西或执行等效的零填充优化，但根据我的测试更多像 new int[size]() 这样惯用的 C++ 方法只是在分配后跟一个 memset。 gcc 将 malloc 后跟 memset 优化为 calloc，但如果您试图避免使用 C，那将无用无论如何例程！
3 准确地说，您需要 1 个额外位来跟踪 sparse 数组的每 128 位。
我想使用 https://research.swtch.com/sparse 中描述的技巧在 C++ 中构建一个密集整数集。这种方法通过允许自身读取未初始化的内存来实现良好的性能。
如何在不触发未定义行为的情况下实现此数据结构，并且 运行 不与 Valgrand 或 ASAN 等工具冲突？
编辑：回复者似乎在关注 "uninitialized" 这个词，并在语言标准的上下文中对其进行解释。对我而言，这可能是一个糟糕的词选择 - 这里 "uninitialized" 仅表示它的值对于算法的正确运行并不重要。显然可以安全地实现这个数据结构（LLVM 在 SparseMultiSet 中实现）。我的问题是最好和最有效的方法是什么？
如果我们改写您的问题：
What code reads from uninitialized memory without tripping tools designed to catch reads from uninitialized memory?
那么答案就很明确了——不可能。您可以找到的任何执行此操作的方法都代表了 Valgrind 中的一个错误，该错误将被修复。
也许在没有 UB 的情况下可以获得相同的性能，但是您对问题设置的限制 "I would like to... use the trick... allowing itself to read uninitialized memory" 保证了 UB。任何避免 UB 的竞争方法都不会使用您如此喜欢的技巧。
如果您只是读取未初始化的内存，Valgrind 不会报错。 如果您 使用 这些数据的方式影响了 Valgrind 将会抱怨 程序的可见行为，例如使用此数据作为系统调用中的输入，或基于此数据进行跳转，或使用此数据计算另一个地址。有关详细信息，请参阅 http://www.valgrind.org/docs/manual/mc-manual.html#mc-manual.uninitvals。 因此，很可能您对 Valgrind 没有任何问题。
如果 valgrind 仍然报错，但即使使用此 uninit 数据您的算法也是正确的，那么您可以使用客户端请求将此内存声明为已初始化。
我可以看到您可以采用的四种基本方法。这些不仅适用于 C++，也适用于大多数其他低级语言，如 C，使未初始化的访问成为可能，但 allowed，最后一个甚至适用于更高级别的 "safe" 语言。
忽略标准，照常执行
这是语言律师最讨厌的一种疯狂把戏！不过请不要惊慌失措 - 后面的解决方案不会违反规则，所以如果您是遵守规则的人，请跳过这一部分。
该标准大部分使用未初始化的值 undefined 并且它允许的少数漏洞（例如，将一个未定义的值复制到另一个）并没有真正给你足够的绳索来实际上实现你想要的 - 即使在限制性稍低的 C 中（例如参见 [=73=] covering C11，它解释了在访问 indeterminiate 值时可能不会直接触发 UB 任何结果也是 不确定的 并且实际上该值可能看起来是偶然访问）。
所以你无论如何都要实现它，知道大多数或所有当前编译器只会将它编译成预期的代码，并且知道你的代码不符合标准。
至少在my test中，gcc、clang和icc都没有利用非法访问做任何疯狂的事情。当然，该测试并不全面，即使您可以构建一个测试，行为也可能会在新版本的编译器中发生变化。
如果访问未初始化内存的方法的实现在一个单独的编译单元中被编译一次，那将是最安全的——这样可以很容易地检查它是否做了正确的事情（只需检查一次程序集）并且使编译器几乎不可能（在 LTGC 之外）做任何棘手的事情，因为它无法证明是否正在访问未初始化的值。
不过，这种方法在理论上是 不安全的 并且您应该非常仔细地检查编译后的输出，如果您采用它，还应采取额外的保护措施。
如果您采用这种方法，valgrind 等工具很可能会报告未初始化的读取错误。
现在这些工具在汇编级别工作，一些未初始化的读取可能没问题（例如，参见快速标准库实现的下一项），因此它们实际上不会立即报告未初始化的读取，但是而是使用各种试探法来确定是否 实际使用了 无效值。例如，他们可能会避免报告错误，直到他们确定未初始化的值用于确定条件跳跃的方向，或根据启发式确定不是 trackable/recoverable 的其他一些操作。您 可能 能够让编译器发出读取未初始化内存但根据此启发式是安全的代码。
更有可能的是，您无法做到这一点（因为这里的逻辑相当微妙，因为它依赖于两个数组中值之间的关系），因此您可以使用 抑制 在您选择的工具中隐藏错误的选项。例如，valgrind 可以基于 stack trace 进行抑制 - 事实上，在各种标准库中已经有许多默认用于隐藏误报的抑制条目。
由于它基于堆栈跟踪工作，如果读取发生在内联代码中，您可能会遇到困难，因为每个调用站点的堆栈顶部都会不同。您可以通过确保函数未内联来避免这种情况。
使用程序集
标准中定义不明确的内容通常在汇编级别定义明确。这就是为什么编译器和标准库通常可以比用 C 或 C++ 更快地实现事物的原因：用汇编编写的 libc 例程已经针对特定的体系结构并且不必担心语言规范中的各种注意事项可以使 运行 在各种硬件上更快。
通常情况下，在汇编中实现任何大量代码都是一项代价高昂的工作，但在这里它只是少数，所以它可能是可行的，具体取决于您的目标平台数量。您甚至不需要自己编写方法 - 只需编译 C++ 版本（或使用 godbolt 并复制程序集。is_member 函数，例如 1，看起来像：
sparse_array::is_member(unsigned long):
mov rax, QWORD PTR [rdi+16]
mov rdx, QWORD PTR [rax+rsi*8]
xor eax, eax
cmp rdx, QWORD PTR [rdi]
jnb .L1
mov rax, QWORD PTR [rdi+8]
cmp QWORD PTR [rax+rdx*8], rsi
sete al
依靠calloc魔法
如果您使用 calloc2，您会明确地从底层分配器请求零内存。现在 calloc 的 正确 版本可以简单地调用 malloc 然后将 returned 内存清零，但实际实现依赖于这样一个事实OS 级别的内存分配例程（sbrk 和 mmap，几乎）通常会 return 你将内存归零到任何 OS 受保护的内存（即所有大的），以避免再次将内存清零。
作为一个实际问题，对于大型分配，这通常通过映射一个特殊的 零页 全零来实现像匿名 mmap 这样的调用来满足。当（如果有的话）内存被写入时，写时复制实际上是否分配了一个新页面。因此，由于 OS 已经需要将页面归零，因此大的归零内存区域的分配可能 免费 。
在这种情况下，在 calloc 之上实施稀疏集可能与名义上未初始化的版本一样快，同时安全且符合标准。
Calloc 注意事项
您当然应该进行测试以确保 calloc 的行为符合预期。优化的行为通常只会在您的程序初始化大量长寿命零内存大约 "up-front" 时才会发生。也就是说，优化 calloc 的典型逻辑是这样的：
calloc(N)
if (can satisfy a request for N bytes from allocated-then-freed memory)
memset those bytes to zero and return them
else
ask the OS for memory, return it directly because it is zeroed
基本上，malloc 基础设施（也是 new 和朋友的基础）有一个（可能是空的）内存池，它已经从 OS 请求并通常尝试先分配到那里。该池由来自 OS 的最后一个块请求但未分发的内存组成（例如，因为用户请求了 32 字节但分配请求来自 OS 的 1 MB 块中的块，所以剩下很多），还有分配给进程但随后通过 free 或 delete 或其他方式 returned 的内存。该池中的内存具有任意值，如果可以从该池中满足 calloc，则您不会获得魔法，因为必须进行零初始化。
另一方面，如果必须从 OS 分配内存，你就会得到魔法。所以这取决于你的用例：如果你经常创建和销毁 sparse_set 对象，你通常只会从内部 malloc 池中提取并支付归零成本。如果你有一个占用大量内存的长寿命 sparse_set 对象，它们很可能是通过询问 OS 分配的，你几乎可以免费获得清零。
好消息是，如果您不想依赖上面的 calloc 行为（实际上，在您的 OS 或您的分配器上，它甚至可能不会以这种方式进行优化)，您通常可以通过手动映射 /dev/zero 来复制行为以进行分配。在提供它的 OSes 上，这保证您获得 "cheap" 行为。
使用惰性初始化
对于完全与平台无关的解决方案，您可以简单地使用另一个跟踪数组初始化状态的数组。
首先选择一些颗粒，您将在其中跟踪初始化，并使用位图，其中每个位跟踪 sparse 数组的该颗粒的初始化状态。
例如，假设您选择的颗粒为 4 个元素，数组中元素的大小为 4 个字节（例如，int32_t 值）：您需要 1 位来跟踪每 4 个elements * 4 bytes/element * 8 bits/byte，这是分配内存中不到 1%3 的开销。
现在您只需在访问sparse之前检查此数组中的相应位即可。这会为访问 sparse 数组增加一些小成本，但不会改变整体的复杂性，而且检查速度仍然很快。
例如，您的 is_member 函数现在 looks like:
bool sparse_set::is_member(size_t i){
bool init = is_init[i >> INIT_SHIFT] & (1UL << (i & INIT_MASK));
return init && sparse[i] < n && dense[sparse[i]] == i;
}
在 x86 (gcc) 上生成的程序集现在开始于：
mov rax, QWORD PTR [rdi+24]
mov rdx, rsi
shr rdx, 8
mov rdx, QWORD PTR [rax+rdx*8]
xor eax, eax
bt rdx, rsi
jnc .L2
...
.L2: 回复
这就是与位图检查有关的所有内容。这一切都会非常快（并且通常会偏离关键路径，因为它不是数据流的一部分）。
一般来说，这种方法的成本取决于你的集合的密度，以及你调用的函数 - is_member 是这种方法的最坏情况，因为一些函数（例如，clear) 根本不受影响，而其他人（例如 iterate）可以批处理 is_init 检查，并且每 INIT_COVERAGE 个元素只执行一次（这意味着开销会再次增加示例值约为 1%）。
有时这种方法 比 OP link 中建议的方法 更快，尤其是当处理元素不在集合中时 - 在这种情况下，is_init 检查将失败并且通常会缩短剩余代码，在这种情况下，您的工作集比 sparse 数组的大小小得多（使用示例粒度的 256 倍），因此您可能会大大减少 DRAM 或外部高速缓存级别的未命中。
颗粒大小本身是此方法的重要可调参数。直观地说，当第一次访问该颗粒覆盖的元素时，较大的颗粒大小会付出较大的初始化成本，但可以节省内存和前期 is_init 初始化成本。您可以想出一个公式来找到简单情况下的最佳大小 - 但行为还取决于值的 "clustering" 和其他因素。最后，使用动态粒度来覆盖不同工作负载下的基础是完全合理的 - 但它是以可变班次为代价的。
真正懒惰的解决方案
值得注意的是 calloc 和 lazy init 解决方案之间有一个相似之处：两者都在需要时延迟初始化内存块，但是 calloc 解决方案通过带有页表和 TLB 条目的 MMU 魔术在硬件中隐式跟踪这一点，而 lazy init 解决方案在软件中执行此操作，使用位图显式跟踪已分配的颗粒.
硬件方法的优点是几乎免费（对于 "hit" 情况，无论如何），因为它使用 CPU 中始终存在的虚拟内存支持来检测未命中，但是软件案例具有便携和允许精确控制颗粒大小等优点
你实际上可以结合这些方法，做一个不使用位图的惰性方法，甚至根本不需要 dense 数组：只需分配你的 sparse 数组mmap 为 PROT_NONE，因此每当您从 sparse 数组中的未分配页面读取时都会出错。您发现错误并在 sparse 数组中分配页面，其中标记值指示每个元素的 "not present"。
这是 "hot" 案例中最快的：您不再需要任何 ... && dense[sparse[i]] == i 检查。
缺点是：
- 您的代码确实不可移植，因为您需要实现故障处理逻辑，这通常是特定于平台的。
- 您无法控制粒度：它必须是页面粒度（或其倍数）。如果你的集合非常稀疏（比如 4096 个元素中只有不到 1 个被占用）并且分布均匀，你最终会付出高昂的初始化成本，因为你需要处理错误并为每个元素初始化整页值。
- 未命中（即，对不存在的集合元素的非插入访问）要么需要分配一个页面，即使该范围内不存在任何元素，要么每次都非常慢（引发错误） .
1 此实现没有 "range checking" - 即，它不检查 i 是否大于 MAX_ELEM - 取决于你的用例你可能想检查一下。我的实现为 MAX_ELEM 使用了一个模板参数，这可能会导致代码速度稍快，但也会更加臃肿，您最好也将最大大小设置为 class 成员。
2 真的，唯一的要求是你使用在幕后调用 calloc 的东西或执行等效的零填充优化，但根据我的测试更多像 new int[size]() 这样惯用的 C++ 方法只是在分配后跟一个 memset。 gcc 将 malloc 后跟 memset 优化为 calloc，但如果您试图避免使用 C，那将无用无论如何例程！
3 准确地说，您需要 1 个额外位来跟踪 sparse 数组的每 128 位。