使用位集和共享静态数组将std :: set专门用于（u）int8和chars是否合法

Question

这主要是语言律师的问题，我怀疑大多数实现都会麻烦，特别是因为这可能会增加每个用户的编译时间。

话虽如此：如果对std :: set的某些实现是针对每个实例和共享的256个值的静态数组使用位集实现的（由于键为const，这是安全的），根据该标准，这是否合法？

Answer 1

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

或者set<char>，set<uint8_t>您需要 32 个八位位组来存储表示潜在成员的 256 位，并具有非常快的设置操作的优点。因为set<int>你会消耗太多内存，而且恕我直言，如果你有非常多的集合，这才是合理的。

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

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