std::set 插入成员函数的有效实现是什么？因为数据结构基于 std::less 对元素进行排序（需要为元素类型定义运算符 <），所以在概念上很容易检测到重复。
它在内部实际上是如何工作的？它是否利用了红背树数据结构（在 Josuttis 的书中提到的实现细节）？
标准数据结构的实现可能会有所不同......
我有一个问题，我被迫拥有一组（一般来说）应该是唯一的整数。集合的长度各不相同，所以我需要动态数据结构（根据我的狭隘知识，这将事情缩小到列表、集合）。元素不一定需要排序，但可能没有重复。由于候选集总是有很多重复项（集很小，最多 64 个元素），与 std::list 和另一种算法相比，尝试使用 insert 成员函数将重复项插入 std::set 会导致大量开销那可能不会诉诸对元素进行排序？
附加：输出集具有 27 个元素的固定大小。抱歉，我忘记了这个......这适用于问题的特殊情况。对于其他情况，长度是任意的（小于输入集）。
如果您要一次创建整个集合，您可以尝试使用std::vector来保存元素、std::sort对它们进行排序并std::unique删除重复项。
std::set::insert如果您使用“位置”插入并获得正确的位置，则复杂度为 O(log n)，或摊销 O(1)（参见例如http://cplusplus.com/reference/stl/set/insert/）。
底层机制是依赖于实现的。它通常是一棵红黑树，但这不是强制性的。您应该查看您最喜欢的实现的源代码，以了解它在做什么。
对于小集合，由于空间局部性，例如对向量的简单线性搜索可能会更便宜。但是插入本身将需要复制以下所有元素。唯一确定的方法是分析每个选项。
当您只提前知道 64 个可能的值时，只需取一个位字段并翻转实际看到的元素的位。这在 n+O(1) 步骤中有效，而且你不能得到比这更少的。
插入std::set大小为 m 的 a 需要 O(log(m)) 时间和比较，这意味着std::set为此目的使用 a 将花费 O(n*log(n)) 并且如果常数大于 for 我不会感到惊讶只需对输入进行排序（这需要额外的空间），然后丢弃重复项。
用 an 做同样的事情std::list平均需要 O(n^2) 时间，因为在列表中找到插入位置需要 O(n)。
一次将一个元素插入到 anstd::vector中也需要 O(n^2) 平均时间——在 O(log(m)) 中找到插入位置是可行的，但元素需要我移动以腾出空间。如果最终结果中的元素数量远小于输入，则下降到 O(n*log(n))，几乎没有空间开销。
如果你有 C++11 编译器或使用 boost，你也可以使用哈希表。我不确定插入特性，但如果结果中的元素数量与输入大小相比很小，那么您只需要 O(n) 时间 - 与位字段不同，您不需要先验地知道潜在的元素或结果的大小（尽管知道大小会有所帮助，因为您可以避免重新散列）。