Ruby有一种列表类型可以在添加/删除时保持内容排序吗？

Question

13

我需要一个在 Ruby 中保持元素排序并允许添加或删除元素的数据结构，并且至少能弹出列表中的第一个元素。

在 Ruby 文档中最接近的可能是 SortedSet。但是，这似乎没有提供通过索引访问元素的任何方法（甚至无法弹出列表中的第一个元素）。

这些是我需要的具体操作：

Ruby 中是否有任何内置功能可实现此操作，或者是否可以获取任何库来实现此操作？如果可能，我宁愿使用现有的代码库而不是自己编写一个。

目前我正在使用 Ruby 1.8，尽管切换到1.9可能也可以。

编辑：

由于似乎存在一些困惑，我需要的排序不是插入对象的顺序。我需要根据 <=> 操作符对排序进行排序。通常，我将弹出第一个元素，然后处理它（可能会生成新元素），将新元素添加到列表中，然后重复。被添加的元素可能出现在排序顺序的任何位置，而不仅仅是在末尾。

- Herms

首先，你的链接无效。（它是指向你本地硬盘的链接，这样是行不通的；如果可以，请发布一个外部链接。）其次，你可能需要自己编写类似于这样的代码，我还没有看到现成的库可以做到这一点。不过，我很想看看你能做出什么。祝你好运！ :) - Sasha Chedygov

哎呀，我完全忘记了我正在使用本地文档的副本。 - Herms

2个回答

1

虽然效率不高（如果经常使用），但SortedSet有一个to_a方法，可以用来访问其中的项：

s = SortedSet.new
s << 1
s << 0
s << 3
puts s.to_a[0] # => 0

- Theo

那个方法可以用，但对于我正在做的事情来说效率极低（访问之间有很多变化）。 - Herms

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jspcal · Accepted Answer

5

您可能想考虑使用这个与1.8兼容的红黑树gem（Ruby/RBTree）：http://www.geocities.co.jp/SiliconValley-PaloAlto/3388/rbtree/README.html。该树始终保持平衡，对树的操作为O(log N)。此外，还有一个红黑树实现在这里：http://github.com/kanwei/algorithms。Containers::RubyRBTreeMap。

- jspcal

没想过要寻找树形结构（尽管现在想起来似乎很明显）。看起来完美无缺。 - Herms

你用过其中任何一个吗？有没有想法哪个更好一些？ - Herms

已经使用了第一个，第二个更新一些，看起来也很不错。 - jspcal

第二个看起来总体不错，但第一个的API更好一些（包括shift/unshift）。看起来第二个的Heap类很不错，但我无法使排序正常工作。我会尝试使用它们两个。 - Herms

请注意，RBTree有很大的可能被纳入标准的Ruby库中（请参见http://redmine.ruby-lang.org/issues/show/2348）。 - Marc-André Lafortune

1

最终创建了一个简单的RBTree包装类来实现队列：http://blog.aherrman.com/2010/01/sortedqueue-in-ruby.html - Herms