c++是否有默认数据类以合理的速度进行基于排序索引的访问？

Question

我正在寻找一个数据类，它可以使数据保持有序，但也允许以我想要的任何顺序进行访问。

基本上我正在寻找一个队列，它允许我以随机顺序访问项目并保持顺序(int 从最低到最高)。添加项目时，它不必求助于所有内容(O(n*log(n)) 操作)，而只是快速插入和删除它(O(log (n)))。我知道存在这样的数据结构(基于二叉树的队列)，但 C++ 提供吗？我当前的应用程序要求我可以做一些事情，比如从项目队列/列表中获得中间或获得第二高优先级的项目。 c++ 是否为此设置了默认数据类？还是我必须自己制作？

顺便说一句，这是 c++ 98

Answer 1

我认为 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 成为堆。