Geek Answers Handbook

Does ruby ​​have a list type that stores content sorted as it is added / removed?

I need a data structure in Ruby that keeps its elements sorted as elements are added or removed and allows (at least) the ability to pull the first element from the list.

The closest I found in ruby ​​docs is SortedSet . However, this does not seem to give any access to the elements by their index (or even pops the first element)

These are the specific operations I need:

  • Add item to list
  • Place the first object from the list
  • Check if the object is in the list
  • Remove an object from the list (by object, not by index)

Is there anything in Ruby for this, or are there any libraries that I can grab to give this to me? I could implement one without much difficulty, but I would prefer to use the pre-existing one, if possible.

I am currently using Ruby 1.8, although switching to 1.9 is likely to be fine.

EDIT:

Since there seems to be some confusion, the sorting I need is not the order in which the objects are inserted. I need a sort based on the <=> operator. Typically, I will pull out the first element, processing it (which can generate new elements), adding new elements to the list, and then repeating. Added items can end anywhere in the sort order, and not just at the end.

+7
ruby sortedlist
source share
2 answers

you may need to configure this 1.8-compatible red ebony stone that does this (Ruby / RBTree):

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

Wood

always balanced; tree operations - O (log N)

an implementation of red ebony is also implemented here:

http://github.com/kanwei/algorithms

Containers :: RubyRBTreeMap

+4
source share

Although it is inefficient (if you use it often), SortedSet has a to_a method that can be used to access elements:

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

More articles:


All Articles