如何存储编译时动态分配的内存以便它可以在运行时间内使用？

Question

比如说，我有一个 constexpr 变量，它包含所有小于 2¹⁶.

的素数

constexpr auto primes = [] {
    constexpr int N = 1 << 16;
    std::array<int, 6542> ret;
    bool not_prime[N] = {};
    int prime_cnt = 0;
    for (int i = 2; i < N; i++) {
        if (!not_prime[i]) {
            ret[prime_cnt++] = i;
            for (int j = 2 * i; j < N; j += i) not_prime[j] = true;
        }
    }
    return ret;
}();

这里我手动指定了ret的数组大小。当我想改变N时，我不得不重新运行这个循环，看看最后的prime_cnt值是多少，手动指定。特别是，如果我增加N，我必须首先给出一个上限猜测以避免段错误。

在 C++20 中，我们可以在编译时动态分配内存，因此我们现在有了 constexpr 向量。所以我们不再需要担心上界问题。但是这样的值不能在运行时间内使用，也就是说，这个代码是无效的。

constexpr auto primes = [] {
    constexpr int N = 1 << 16;
    std::vector<int> ret;
    bool not_prime[N] = {};
    for (int i = 2; i < N; i++) {
        if (!not_prime[i]) {
            ret.push_back(i);
            for (int j = 2 * i; j < N; j += i) not_prime[j] = true;
        }
    }
    return ret;  // invalid here
}();

那么问题来了，这样一个vector怎么存储呢？

一个明显的解决方案是将这个过程分成两个阶段。第一个计算数组大小，第二个进行正常计算。但这需要额外的代码和计算资源。有没有一种优雅而自动的方式来实现这个目标？

Answer 1

创建一个生成 vector 的 lambda，并使用另一个 lambda 生成 array

#include <array>
#include <vector>
#include <algorithm>

constexpr auto primes_num_vector = [] {
  constexpr int N = 1 << 16;
  std::vector<int> ret;
  bool not_prime[N] = {};
  for (int i = 2; i < N; i++) {
    if (!not_prime[i]) {
      ret.push_back(i);
      for (int j = 2 * i; j < N; j += i) not_prime[j] = true;
    }
  }
  return ret;
};

constexpr auto primes = [] {
  std::array<int, primes_num_vector().size()> ret;
  std::ranges::copy(primes_num_vector(), ret.begin());
  return ret;
}();

Answer 2

A std::vector 使用动态分配，在 constexpr 中任何动态分配都必须由 delete 匹配。所以你不能 constexpr 那样 std::vector。

但没有什么能阻止您使用 std::array。 N以下的素数可以在constexpr中计算出来，然后你可以用它来给std::array一个compile-time的大小：

#include <vector>
#include <array>

constexpr std::size_t num_primes(std::size_t N) {
    std::size_t num = N - 2;
    for (std::size_t i = 2; i < N; ++i) {
        for (std::size_t j = 2; j * j <= i; ++j) {
            if (i % j == 0) {
                --num;
                break;
            } 
        }
    }
    return num;
}

constexpr auto primes = [] {
    constexpr int N = 1 << 16;
    std::array<std::size_t, num_primes(N)> ret;
    std::size_t pos = 0;
    bool not_prime[N] = {};
    for (int i = 2; i < N; i++) {
        if (!not_prime[i]) {
            ret[pos++] = i;
            for (int j = 2 * i; j < N; j += i) not_prime[j] = true;
        }
    }
    return ret;  // invalid here no more
}();

#include <iostream>
int main() {
    for (const auto & x : primes) {
        std::cout << " " << x;
    }
    std::cout << std::endl;
}

该代码非常愚蠢，因为它对所有素数进行了两次计算，一次是通过可怕的低效除法测试，一次是通过筛子。优化这个留给 reader.

提示：合并这两个函数，在创建筛子的同时计算素数。然后创建数组并通过遍历筛子来填充它。或者，在创建筛子期间创建一个向量，然后将该向量复制到数组中。只要vector在constexpr中被破坏，整体就是一个constexpr.

如何存储编译时动态分配的内存以便它可以在运行时间内使用？

How do I store the compile-time dynamically allocated memory so that it can be used in run-time?

c++

constexpr

c++20

如何存储编译时动态分配的内存以便它可以在 运行 时间内使用？

How do I store the compile-time dynamically allocated memory so that it can be used in run-time?

c++

constexpr

c++20

如何存储编译时动态分配的内存以便它可以在运行时间内使用？