¿Ruby tiene un tipo de lista que mantiene los contenidos ordenados a medida que se suceden/eliminan?

Question

Necesito una estructura de datos en Ruby que mantenga sus elementos ordenados a medida que los elementos se agregan o eliminan y permite (al menos) la capacidad de extraer el primer elemento de la lista.

Lo más parecido que he encontrado en ruby ​​docs es SortedSet. Sin embargo, esto no parece proporcionar ninguna forma de acceder a los elementos por su índice (o incluso insertar el primer elemento de descuento)

Estas son las operaciones específicas que necesito:

• Agregar objeto a la lista
• Pop primer objeto fuera de la lista
• Comprobar si un objeto está en la lista
• Retire el objeto de la lista (por objeto, no por índice)

¿El rubí tiene algo incorporado para esto, o hay alguna biblioteca que pueda agarrar que me la proporcione? Podría implementar uno sin demasiada dificultad, pero prefiero usar uno preexistente si es posible.

Actualmente estoy usando Ruby 1.8, aunque cambiar a 1.9 probablemente estaría bien.

EDIT:

Dado que parece que hay cierta confusión, la clasificación que necesito no es el orden en que los objetos se insertan. Necesito que la clasificación se base en el operador <=>. En general, apareceré el primer elemento, procesándolo (lo que puede generar nuevos elementos), agregando nuevos elementos a la lista y luego repitiendo. Los elementos que se agregan pueden terminar en cualquier lugar del orden de clasificación, no solo al final.

Answer 1

lo desea, puede condiser esta joya compatible con 1.8 de árbol rojo-negro que hace esto (Rubí/RBTree):

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

árbol siempre se mantiene equilibrada, las operaciones en el árbol son O (log N)

también hay una aplicación árbol rojo-negro aquí:

http://github.com/kanwei/algorithms

Con recipientes :: RubyRBTreeMap

Answer 2

Aunque ineficaz (si lo usa a menudo), SortedSet tiene un método to_a que se puede utilizar para acceder a los artículos:

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