什么是用于获取按c ++中的值排序的列表中元素的序号位置的算法或代码

Question

这类似于最近的一个问题.

我将维护已排序的值列表.我将在列表中插入任意值的项目.每次我插入一个值,我想确定它在列表中的顺序位置(是第1,第2,第1000).什么是最有效的数据结构和算法来实现这一目标？显然有很多算法可以让你这样做,但我没有看到任何方法可以使用简单的STL或QT模板功能轻松做到这一点.理想情况下,我想了解现有的开源C++库或可以执行此操作的示例代码.

我可以想象如何为此目的修改B树或类似的算法,但似乎应该有一个更简单的方法.

EDIT3:

Mike Seymour很好地证实,正如我在原帖中写的那样,使用简单的STL确实无法完成这项任务.所以我正在寻找一个好的btree,平衡树或类似的开源c ++模板,它可以在没有修改或尽可能少修改的情况下完成--Pavel Shved表明这是可能的,但我不想深入实现平衡树我.

(历史应该显示我使用make_heap将Mathieu的代码修改为O(log N)的不成功的努力)

编辑4:

我仍然给信贷帕维尔用于指出B树能够给一个解决方案,这一点,我不得不提,实现这种功能,但并不实现是最简单的方法定制 B-树的C++自己的模板是使用内存数据库.这将为您提供log n并且相当容易实现.

Answer 1

二叉树很好用.它的修改也很简单:只需在每个节点中保留其子树中的节点数.

插入节点后,通过从根到该节点再次执行搜索.并递归更新索引:

if (traverse to left subtree)
  index = index_on_previous_stage;
if (traverse to right subtree)
  index = index_on_previous_stage + left_subtree_size + 1;
if (found)
  return index + left_subtree_size;

这将花费O(log N)时间,就像插入一样.

Answer 2

我想你可以std::set在这里.它为您提供排序行为,还返回插入值的迭代器的位置.从那个位置你可以得到索引.例如:

std::set<int> s;
std::pair<std::set<int>::iterator, bool> aPair = s.insert(5);
size_t index = std::distance(s.begin(), aPair.first) ;