Set insert执行奇怪数量的比较
Set insert执行奇怪数量的比较
提问于 2014-04-09 16:40:45
我无法解释std::set在插入新元素时所做的比较次数。下面是一个示例：
对于此代码，
struct A {
int i = 0;
bool operator()(int a, int b)
{
++i;
return a < b;
}
};
int main()
{
A a;
set<int, A> s1(a);
s1.insert(1);
cout << s1.key_comp().i << endl;
s1.insert(2);
cout << s1.key_comp().i << endl;
}输出为
0
3为什么插入第二个元素需要3次比较？o_O
回答 2
Stack Overflow用户
发布于 2014-04-09 16:58:10
这是使用红黑树实现std::set的副作用，它最初需要与标准二叉树进行更多的比较。
Stack Overflow用户
发布于 2014-04-09 16:58:22
我不知道具体是什么，因为它们将取决于您的std::set实现，但是确定两个项目的相等需要两次比较，因为这是基于not (x < y) and not (y < x)暗示x == y的事实。
根据树的优化方式，您可能会进行第一次比较，以确定它应该向左还是向右，然后进行两次比较，以检查它是否相等。
除了比较次数为O(log )外，该标准没有任何要求，其中N是set中已有的项目数。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/22957117
复制相关文章
相似问题
腾讯云开发者
