c++ - set::insert 的复杂度

Question

我已经读过集合中的插入操作只需要 log(n) 时间。这怎么可能？

要插入，首先我们在排序数组中找到新元素必须位于的位置。使用二分查找需要 log(n)。然后要插入到那个位置，它后面的所有元素都应该向右移动一个位置。又需要n次。

我的怀疑是基于我的理解，即 set 是作为数组实现的，并且元素是按排序顺序存储的。如果我的理解有误，请纠正我。

Answer 1

std::set通常实现为红黑二叉搜索树。由于树保持平衡，因此在此数据结构上的插入具有 O(log(n)) 复杂度的最坏情况。