C++设置比较慢？

Question

我不得不使用一种数据结构,它将元素保持在某种顺序,以便我可以查询最少元素并有效地插入新元素set ( C++ stl).所以我选择了 .这需要log(n)时间,插入和log(n)用于删除至少元件.

所以我写了以下程序:

#include<iostream>
#include<set>
#include<stdio.h>
using namespace std;
int main()
{
   set<int>s1,s2;
   set<int>::iterator it;
   int tmp,i;
   for(i=1;i<=1000000;i++)s1.insert(i);
   for(i=1;i<=1000000;i++)
   {
      it=s1.begin();
      s2.insert(*it);
      s1.erase(s1.begin());
   }
return 0;
}

但这需要1.67我的机器上的秒数(我的核心3)我期望更少,O(log(1000000)*1000000)即2*10^7我尝试优先级队列也给了我相同的性能.那么我应该实现自己的堆以使其更快或有其他方式吗？

Answer 1

你正在做的是平衡二叉搜索树可能遭受的最难的事情之一.您将插入项目保留在树的最右侧,并从最左侧继续删除项目,使树始终必须重新平衡.