c++ - 使用 bitset 和共享静态数组将 std::set 专门用于 (u)int8 和 chars 是否合法

Question

这主要是语言律师类的问题，我怀疑大多数实现会打扰，尤其是因为它可能会增加每个用户的编译时间。

话虽如此:如果 std::set 的某些实现是使用每个实例的 bitset 和共享的 256 个值的静态数组实现的(因为键是 const 是安全的)，那么根据(如果版本很重要，那么假设 C++20 ) 标准？

Answer 1

只要您遵守 [set] 部分中的标准规范，我认为没有任何限制会禁止您进行专门的实现。 .

对于 set<char>或 set<uint8_t>您需要 32 个八位字节来存储代表潜在成员的 256 位，具有非常快速的集合操作的优势。对于set<int>你会消耗太多的内存，如果你有非常填充的集合，这只有在恕我直言是合理的。

话虽如此，有一些挑战需要克服:

• 您需要组织将值映射到位位置的数组，使其与提供的比较器一致(构建成本，除非您可以共享它)
• 你必须实现一个迭代器(但这不是一个真正的问题，因为位图和位偏移可以做到)。
• 从 C++17 开始，有一个公开的假设，即数据结构使用 nodes因为有一个 extract() 应该返回(未指定)专用类型 node_type 的值的成员.不确定这个要求意味着什么，但我认为它可以通过与上述迭代器问题类似的方式来解决。
• 您需要遵守复杂性要求(请参阅 NathanOlivier 对您的问题的评论)。困难来自共享数组的排序。但是，如果您使用两个共享数组(一个将值转换为位偏移量，一个将位偏移量转换为值)或一个对数组，您可以在 O(1) 中插入任何内容。