我读过一个集合中的插入操作只需要log（n）时间，这怎么可能呢？要插入，首先我们要在排序数组中找到新元素必须所在的位置，使用二分查找需要log（n），然后要插入到那个位置，它后面的所有元素都应该向右移动一个位置，这又需要n次。我的怀疑是基于我的理解，集合是作为数组实现的，元素是按排序顺序存储的。如果我的理解有错，请纠正我。
cvxl0en21#
std::set通常被实现为红-黑二叉搜索树，在这种数据结构上的插入具有O（log（n））复杂度的最坏情况，因为树保持平衡。
std::set
a6b3iqyw2#
当插入到一个集合中时，东西不会被移动。它通常不会被存储为向量或数组，而是一个二叉树。你所做的就是添加一个新的叶子节点，这需要O（1）。所以总的插入需要O（log（n））。
2条答案
按热度按时间cvxl0en21#
std::set通常被实现为红-黑二叉搜索树，在这种数据结构上的插入具有O（log（n））复杂度的最坏情况，因为树保持平衡。a6b3iqyw2#
当插入到一个集合中时，东西不会被移动。它通常不会被存储为向量或数组，而是一个二叉树。你所做的就是添加一个新的叶子节点，这需要O（1）。所以总的插入需要O（log（n））。