什么是算法或code在列表排序值在C元素的获取顺序位置++ [英] What’s An Algorithm or code for the obtaining ordinal position of an element in a list sorted by value in c++

问题描述

这是类似于<一href="http://stackoverflow.com/questions/1746402/whats-a-qt-or-open-source-c-template-for-ordinal-sorting">recent问题。

我会保持排序值的列表。我将插入的任意值物品进入名单。每次我插入值，我想，以确定在列表中的顺序位置（这是第一，第二，第1000）。什么是最有效的数据结构和算法实现这个目标？很显然，许多算法，它可以让你做到这一点，但我看不出有什么方法可以轻松地做到这一点使用简单的STL或QT模板的功能。理想情况下，我想了解一下现有的开源C ++库或抽样code可以做到这一点。

I will be maintaining sorted a list of values. I will be inserting items of arbitrary value into the list. Each time I insert a value, I would like to determine its ordinal position in the list (is it 1st, 2nd, 1000th). What is the most efficient data structure and algorithm for accomplishing this? There are obviously many algorithms which could allow you to do this but I don't see any way to easily do this using simple STL or QT template functionality. Ideally, I would like to know about existing open source C++ libraries or sample code that can do this.

我能想象如何修改B-树或类似的算法用于此目的，但它看起来应该有一个更简单的方法。

I can imagine how to modify a B-tree or similar algorithm for this purpose but it seems like there should be an easier way.

EDIT3：

迈克·西摩pretty的很好的印证，正如我写在我原来的职位，确实是有没有办法用简单的STL来完成这个任务。所以，我正在寻找一个良好的B树，平衡树或类似的开源C ++模板，可以实现无需修改或用最少的修改可能 - 帕维Shved显示这是可能的，但我倒是preFER没有潜入实施平衡树自己。

Mike Seymour pretty well confirmed that, as I wrote in my original post, that there is indeed no way to accomplish this task using simple STL. So I'm looking for a good btree, balanced-tree or similar open source c++ template which can accomplish without modification or with the least modification possible - Pavel Shved showed this was possible but I'd prefer not to dive into implementing a balanced tree myself.

（历史上应该显示我的努力失败修改马修的code是为O（log N）采用make_heap）

(the history should show my unsuccessful efforts to modify Mathieu's code to be O(log N) using make_heap)

修改4：

我还是给信贷帕维尔的指出，B树可以给 解决方案，这一点，我不得不提及的是最简单的方法来实现这种功能，但并不实现的自定义 B树的C ++自己的模板是<一个href="http://stackoverflow.com/questions/1870146/how-fast-would-a-sqlite-join-be-compared-to-a-custom-tree-search">use在内存数据库。这将使你登录n和是的非常的容易实现。

I still give credit to Pavel for pointing out that btree can give a solution to this, I have to mention that simplest way to achieve this kind of functionality without implementing a custom btree c++ template of your own is to use an in-memory database. This would give you log n and is fairly easy to implement.

推荐答案

二叉树是罚款与此有关。它的修改很容易，以及：只保留每个节点的节点数目的子树。

Binary tree is fine with this. Its modification is easy as well: just keep in each node the number of nodes in its subtree.

在插入一个节点，从根本步行到节点再次进行搜索。并递归更新索引：

After you inserted a node, perform a search for it again by walking from root to that node. And recursively update the index:

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）的时间，就像插入。

This will take O(log N) time, just like inserting.

这篇关于什么是算法或code在列表排序值在C元素的获取顺序位置++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！