我正在寻找一个数据类,它可以使数据保持有序,但也允许以我想要的任何顺序进行访问。
基本上我正在寻找一个队列,它允许我以随机顺序访问项目并保持顺序(int 从最低到最高)。添加项目时,它不必求助于所有内容(O(n*log(n)) 操作),而只是快速插入和删除它(O(log (n)))。我知道存在这样的数据结构(基于二叉树的队列),但 C++ 提供吗?我当前的应用程序要求我可以做一些事情,比如从项目队列/列表中获得中间或获得第二高优先级的项目。 c++ 是否为此设置了默认数据类?还是我必须自己制作?
顺便说一句,这是 c++ 98
最佳答案
我认为 vector plus heap 就是您要找的东西。
vector<int> v;
// insert elements
v.push_back(3);
push_heap(v.begin(), v.end());
v.push_back(2);
push_heap(v.begin(), v.end());
v.push_back(4);
push_heap(v.begin(), v.end());
// get the second big
sort_heap(v.begin(), v.end());
cout << v[v.size() - 2] << endl;
// insert elements
make_heap(v.begin(), v.end());
v.push_back(7);
push_heap(v.begin(), v.end());
// get the second big
sort_heap(v.begin(), v.end());
cout << v[v.size() - 2] << endl;
插入速度很快。但是每次在你想要访问不是最大的项目之前,你必须对堆进行排序,因为堆只给你最大的。在此之后和新插入之前,您必须调用 make_heap
再次使 vector 成为堆。
关于c++是否有默认数据类以合理的速度进行基于排序索引的访问?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26544610/