Ruby: Want a Set-like object which preserves order

Answer 1

Not that I know of, but it wouldn't be hard to roll your own. Just subclass Array and use a Set to maintain your uniqueness constraint.

One question about silent dropping. How would this affect #[]=? If I was trying to overwrite an existing entry with something which was already stored elsewhere, should it remove the would-be-removed element anyway? I think either way could provide nasty surprises down the road.

Answer 2

There isn't one as far as I know, and Set by its mathematical nature is meant to be unordered (or at least, implementationally, meant not to guarantee order - in fact its usually implemented as a hash table so it does mess up order).

However, it's not hard to either extend array directly or subclass it to do this. I just tried it out and this works:

class UniqueArray < Array
  def initialize(*args)
    if args.size == 1 and args[0].is_a? Array then
      super(args[0].uniq)
    else
      super(*args)
    end
  end

  def insert(i, v)
    super(i, v) unless include?(v)
  end

  def <<(v)
    super(v) unless include?(v)
  end

  def []=(*args)
    # note: could just call super(*args) then uniq!, but this is faster

    # there are three different versions of this call:
    # 1. start, length, value
    # 2. index, value
    # 3. range, value
    # We just need to get the value
    v = case args.size
      when 3 then args[2]
      when 2 then args[1]
      else nil
    end

    super(*args) if v.nil? or not include?(v)
  end
end

Seems to cover all the bases. I used OReilly's handy Ruby Cookbook as a reference - they have a recipe for "Making sure a sorted array stays sorted" which is similar.

Answer 3

You could use a Hash to store the values, and have an incrementing value stored in the value of each Hash pair. Then you can access the set in a sorted manner, albeit slowly, by accessing the objects via their values.

I'll try to add some code in here later to explain further.

I am aware accessing via values is much slower than by keys.

Update 1: In Ruby 1.9, Hash elements are iterated in their insertion order.