ruby 是否有一个列表类型可以在添加/删除发生时保持内容排序？

Question

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

我在 ruby​​ 文档中找到的最接近的东西是 SortedSet 。但是，这似乎没有提供任何通过索引访问元素的方法（甚至弹出第一个元素）

这些是我需要的特定操作：

• 将对象添加到列表中 从
• 列表中弹出第一个对象
• 检查是否存在对象在列表中
• 从列表中删除对象（按对象，而不是按索引）

ruby​​ 是否为此内置了任何东西，或者是否有任何我可以获取的库可以将其提供给我？我可以毫不费力地实现一个，但如果可能的话，我宁愿使用预先存在的一个。

目前我使用的是 Ruby 1.8，不过切换到 1.9 可能没问题。

编辑：

由于似乎存在一些混乱，我需要的排序不是对象插入的顺序。我需要基于 <=> 运算符进行排序。一般来说，我会弹出第一个元素，处理它（可能会生成新元素），将新元素添加到列表中，然后重复。添加的元素可能会出现在排序顺序中的任何位置，而不仅仅是末尾。

Answer 1

可能需要考虑这个与 1.8 兼容的红黑树 gem，它可以做到这一点（Ruby/RBTree）：

http://www.geocities.co.jp/SiliconValley-PaloAlto/3388/rbtree/README.html

树总是保持平衡，树上的操作是 O(log N ）

这里还有一个红黑树实现：

http://github.com/kanwei/algorithms

::RubyRBTreeMap

Answer 2

尽管效率较低（如果您经常使用它），SortedSet 有一个 to_a 方法，您可以使用它来访问项目：

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