将std::set专门用于(U)使用位集和共享静态数组的int8和字符是否合法

Question

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

Answer 1

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

对于set<char>或set<uint8_t>，您需要32个二进制八位数来存储表示潜在成员的256位，这具有非常快的集合操作的优势。对于set<int>，你会消耗太多的内存，只有当你有大量填充的集合时，这才是合理的。

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

• 由于C++17，有一个公开的假设，即数据结构使用nodes，因为有一个extract()成员应该返回(未指定的)专用类型node_type的值。不确定这个需求意味着什么，但我认为它可以用与上面的迭代器问题类似的方式解决。

• 你需要遵守复杂性要求(参见NathanOlivier对你的问题的评论)。困难来自于共享数组的排序。但是，如果您使用两个共享数组(一个用于将值转换为位偏移量，另一个用于将位偏移量转换为值)，或者一个由对组成的数组，则可以在O(1)中插入任何内容。

Answer 2

编辑:犯了一个错误。C++17中不允许使用代理迭代器。

我认为这是不可能的。首先:该实现将拥有所有的复杂性保证，并且对于大多数实现来说，它将比需求更好。

第二:在使用标准容器时，不允许创建代理迭代器，因为它们必须在某些点返回真实的引用。( @Christophe提到的std::bitset不是一个容器，在它的定义中有一个代理引用。向量< bool >是违反保证的著名示例。)因此不可能使用该实现。

编辑: Tanks to @NicolBolas指出代理迭代器仍然是不允许的。

Answer 3

Cristophe's answer包含了一个重要的观点：

这指出了处理有状态比较器的一个具有挑战性的问题(当排序关系不是固定的关系，但可以从外部控制并在运行时动态更改时)。尽管一般的C++人员使用frowned upon，但我在标准中找不到禁止关联容器的有状态比较器的任何东西(但我并没有太仔细地研究)。如果您管理比较器的状态和集合的内容，使排序要求永远不会被违反，那么它在实践中是有效的(至少对我来说是有效的)。

因此，我的结论是，在任意比较器的最一般情况下，std::set 不能专门用于使用bitset和任何支持共享静态数据的小型整数类型。