Est-ce que ruby ​​a un type de liste qui garde le contenu trié lorsque des ajouts/suppressions se produisent?

Question

J'ai besoin d'une structure de données dans Ruby qui garde ses éléments triés lorsque des éléments sont ajoutés ou supprimés et permet (au moins) la possibilité d'enlever le premier élément de la liste.

La chose la plus proche que j'ai trouvée dans les docs ruby ​​est SortedSet. Toutefois, cela ne semble pas fournir un moyen d'accéder aux éléments par leur index (ou même pop le premier élément off)

Ce sont les opérations spécifiques dont j'ai besoin:

• Ajouter un objet à la liste
• Pop premier objet hors de la liste
• Vérifiez si un objet est dans la liste
• Supprimer objet dans la liste (par objet, et non par index)

Est-ce que ruby ​​a quelque chose de prévu à cet effet, ou est-ce qu'il y a des bibliothèques que je peux récupérer et qui me le donneraient? Je pourrais en mettre un sans trop de difficulté mais je préfèrerais en utiliser une préexistante si possible.

Actuellement j'utilise Ruby 1.8, bien que passer à 1.9 serait probablement correct.

EDIT:

Comme il semble y avoir une certaine confusion, le tri j'ai besoin est pas l'ordre dans lequel les objets sont insérés. J'ai besoin que le tri soit basé sur l'opérateur <=>. Généralement, je vais faire apparaître le premier élément, le traiter (ce qui peut générer de nouveaux éléments), ajouter de nouveaux éléments à la liste, puis répéter. Les éléments ajoutés peuvent se retrouver n'importe où dans l'ordre de tri, pas seulement à la fin.

Answer 1

peut vouloir condiser ce petit bijou 1.8 compatible pour les arbres noirs rouges qui le fait (Ruby/RBTree):

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

arbre est toujours maintenu l'équilibre, les opérations sur l'arbre sont O (log N)

il y a aussi une mise en œuvre de l'arbre rouge noir ici:

http://github.com/kanwei/algorithms

Con Tainers :: RubyRBTreeMap

Answer 2

Bien inefficace (si vous l'utilisez souvent), SortedSet a une méthode to_a que vous pouvez utiliser pour accéder aux éléments:

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