C++ set::insert 的复杂度

声明:本页面是StackOverFlow热门问题的中英对照翻译,遵循CC BY-SA 4.0协议,如果您需要使用它,必须同样遵循CC BY-SA许可,注明原文地址和作者信息,同时你必须将它归于原作者(不是我):StackOverFlow 原文地址: http://stackoverflow.com/questions/12776485/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me): StackOverFlow

提示:将鼠标放在中文语句上可以显示对应的英文。显示中英文
时间:2020-08-27 16:36:54  来源:igfitidea点击:

complexity of set::insert

c++stlsettime-complexity

提问by bibbsey

I have read that insert operation in a set takes only log(n) time. How is that possible?

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

To insert, first we have find the location in the sorted array where the new element must sit. Using binary search it takes log(n). Then to insert in that location, all the elements succeeding it should be shifted one place to the right. It takes another n time.

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

My doubt is based on my understanding that set is implemented as an array and elements are stored in sorted order. Please correct me if my understanding is wrong.

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

回答by cdhowie

std::setis commonly implemented as a red-black binary search tree. Insertion on this data structure has a worst-case of O(log(n)) complexity, as the tree is kept balanced.

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