如果是一次性操作,我会使用a std::vector后跟a std::sort.
就渐近复杂性而言,两个解决方案应该是等价的:在集合中插入是O(log(n)),并且对N个元素执行此操作,因此它是O(N log(N))(证明).
另一方面,在向量中插入(假设您事先知道大小)是O(N),并且排序是O(N log(N)),因此全局它是O(N log(N)).
但是:向量需要一次性分配(或者,如果您不知道最终大小,它应该在典型实现的O(log(N))重新分配中达到最终大小); 另一方面,如果实现为RB树,则需要为每个节点分配一个集合,这意味着您必须调用分配器N次 - 并且在POD容器中的分配器调用可能是其中之一瓶颈.此外,树通常具有较少的缓存局部性并使用更多内存,因此所有这些开销可能会损害性能.
此外,big-O表示法显示了函数时间依赖性,但隐藏了乘法常量; 不要相信我的话,但是我几乎可以肯定,由于为每个元素做了额外的簿记,N*set插入最终将花费不止一个(树插入通常需要一些努力恢复RB树属性).
在另一方面,如果你要保持你的数据结构排序(由新数据来)设定通常是正确的解决方案.
但是,一如既往,当有疑问的个人资料.