我正在实现埃拉托色尼筛法。我坚持第一步:决定使用哪种数据结构。简而言之，Eratosthenes 的筛选以一系列连续数字(例如 2,3,4,5,...99, 100)开始。然后，某些数字被划掉，不再考虑。什么是最好的数据结构？限制(示例中的 100)直到运行时才知道，尽管 2 始终是起始数字。
我见过几种不同的解决方案。限制 n 的类型为 mpz_class
bool primes[n] bool* primes std::vector<bool> primes std::bitset<n> primes vector 带有参数 int 或 unsigned char 因为它们会比 bool n+1 元素( as seen here )我想这是 n 的值将位于最后一个元素，并且循环内需要较少的减法。 其中一些信息来自这个 Code Review question。 @Jamal 指出“实际上 std::vector 确实存在问题”，但没有详细说明。此外，我在某处表示
unsigned char 的大小保证等于或小于 than bool 使其成为更好的选择。 最佳答案
tl; 博士测量是唯一确定的方法，但这是我对此的看法:
一般来说
bool primes[n] - 一个简单的 bool 数组 - 问题是，它具有固定大小，因此如果在编译时不知道 n，则它不可用。请注意，某些编译器将允许 VLA，但这不是标准，应该避免。 bool* primes = new bool[n] - 也是一个简单的数组，只是动态分配。 std::vector<bool> primes - 本质上是 bool* 的包装器。可以实现为空间高效的位集。 std::bitset<n> primes - 节省空间的存储，但遗憾的是也具有固定大小。 std::vector<int> 或 std::vector<usigned char> - 与 3) 相同，只是它没有作为 bitset 的优化实现。 如果要求
n 直到运行时才知道，它可以归结为一些 std::vector 或动态分配的数组。如果 n 有一个合理的上限，人们仍然可以考虑静态数组。位集 vs 数组/vector
简而言之:位集针对空间进行了优化，本质上每个字节存储 8 个 bool 值，但它们需要按位运算来提取信息，这需要一些在数组/vector 中不需要的 cpu 周期。另见 this question
但是，我不确定位集的较高信息密度对缓存性能有多大影响。
bool vector 与无符号字符 vector
如果
std::vector<bool> 没有实现为空间高效的位集，它可能比 std::vector<unsigned char> 占用更多的内存，因为 sizeof bool 可以大于 1，因此大于 sizeof (unsigned char) 。 (另见 here )如果有一个节省空间的实现
std::vector<unsigned char> 需要更多的内存，但可能更快。vector 的性能
sd
std::vector::operator[] 不执行边界检查，因此与 bool* 相比，不会为数组访问增加太多性能开销(如果有的话)。此外，您还可以享受某些实现在 Debug模式下(并且仅在 Debug模式下)进行边界检查的好处。 std::vector 绝对比数组更易于使用。结论
如果有足够的可用内存，
std::vector<unsigned char> 可能是最好的方法。但最终对不同
n 进行基准测试并进行优化将是唯一可以确定的方法。关于c++ - 用于筛选的最佳数据结构是什么(即某些被划掉的数字列表)？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/58899973/