具有随机存取的快速排序数据结构？

-1

我想添加几个对象的结构，其允许这样的：具有随机存取的快速排序数据结构？

插入的对象，立即下令对整个结构中添加，所以我有一个int的降序排列;能够改变对象排序的int（我的意思是：说对象编号2，现在具有5的整数，所以它重新排序结构）;
快速结构，因为它将完全迭代60次;
能够按位置直接访问对象;
只需要重复从上到下：更高的INT，降低INT
无需删除，但可以成为有用的后面。

有关如何使用该结构的一些说明会很好，因为我对C++标准库知之甚少。

来源

2013-01-05 GigaBass

您可以使用std :: map或平衡二叉树的任何实现，它使您可以快速（O（logN））访问键以及有序键。更改订单只需删除旧密钥并插入新密钥即可。 –

谢谢，我会看看地图！ – GigaBass

您要存储多少个元素？如果代码编写得很好，你会惊讶于在现代处理器上1/60秒内可以进行多少插入/删除操作。 –

所有你所列出的操作（按索引查找除外）可以由标准二叉搜索树支持，并由整数值键入。这使您能够按排序顺序遍历元素，并在任何插入过程中保持对象的排序。正如@njr所提到的，您还可以通过从二叉搜索树中删除对象，更改其优先级，然后将它们重新插入二叉搜索树来更新优先级。

为了支持通过索引随机访问，你应该考虑寻找到order statistic trees，在二叉搜索树变体，除了所有其他业务支持非常快速的通过其指标（O（log n）的）元素的查找。也就是说，您可以非常高效地查询排序顺序中的第15个元素或第17个元素等。顺序统计树不是C++标准库的一部分，但this older question包含可将您链接到实现的答案。

希望这会有所帮助！

来源

2013-01-05 19:10:11 templatetypedef

正是我想要的！谢谢！ – GigaBass

使用一组或一个地图

对于要求1 - 提供自定义的排序函数

对于2 - 删除该项目，并再次将其添加（或提供一种包装，这是否）

3没有意义（列表有多大，处理器/内存有多快）

For 4 - 你确定你需要这个吗？这似乎是一种奇怪的，试图通过位置来访问它时，位置可以突然改变（一些项目被添加或删除）

5 - 同1

来源

2013-01-05 16:41:58 nishantjr

3 - 迭代。 4 - 位置很少会改变 – GigaBass

速度有多快？保持代码尽可能简单，在必要时进行优化。 – nishantjr

其实，这很好，我会看看Charles指出的地图。谢谢 – GigaBass

具有随机存取的快速排序数据结构？

回答

相关问题