Ruby:想要一个保存顺序的类似Set的对象

Question

...或者是一个防止重复输入的数组.

Ruby中是否存在某种对象:

• 响应[],[] =和<<
• 默默地删除重复的条目
• 是可枚举的(或至少支持find_all)
• 保留插入条目的顺序

？

据我所知,一个数组支持第1,3和4点; 而Set则支持1,2和3(但不支持4).并且SortedSet不会这样做,因为我的条目没有实现<=>.

Answer 1

从Ruby 1.9开始,内置Hash对象保留了插入顺序.例如:

h = {}
h[:z] = 1
h[:b] = 2
h[:a] = 3
h[:x] = 0
p h.keys     #=> [:z, :b, :a, :x]

h.delete :b
p h.keys     #=> [:z, :a, :x]

h[:b] = 1
p h.keys     #=> [:z, :a, :x, :b]

因此,您可以true为任何键设置任何值(如简单),现在您有一个有序集.您可以使用或者测试一个键h.key?(obj),如果您始终将每个键设置为具有真值,则可以h[obj].要删除密钥,请使用h.delete(obj).要将有序集转换为数组,请使用h.keys.

因为Ruby 1.9 Set库恰好是基于Hash构建的,所以您当前可以将其Set用作有序集.(例如,该to_a方法的实现只是@hash.keys.)但是,请注意,该库不保证此行为,并且将来可能会更改.

require 'set'
s = Set[ :f, :o, :o, :b, :a, :r ]  #=> #<Set: {:f, :o, :b, :a, :r}>
s << :z                            #=> #<Set: {:f, :o, :b, :a, :r, :z}>
s.delete :o                        #=> #<Set: {:f, :b, :a, :r, :z}>
s << :o                            #=> #<Set: {:f, :b, :a, :r, :z, :o}>
s << :o                            #=> #<Set: {:f, :b, :a, :r, :z, :o}>
s << :f                            #=> #<Set: {:f, :b, :a, :r, :z, :o}>
s.to_a                             #=> [:f, :b, :a, :r, :z, :o]

Answer 2

据我所知,没有一个,并且其数学性质的Set意味着无序(或者至少,在实现上,意味着不保证顺序 - 事实上它通常被实现为哈希表,所以它确实搞乱了顺序).

但是,直接扩展数组或将其子类化为执行此操作并不困难.我刚试了一下这个有效:

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

似乎涵盖了所有的基础.我使用了OReilly的方便的Ruby Cookbook作为参考 - 他们有一个"确保排序数组保持排序"的配方,这是类似的.

Answer 3

我喜欢这个解决方案,虽然它需要active_support的OrderedHash

require 'active_support/ordered_hash'

class OrderedSet < Set

  def initialize enum = nil, &block
    @hash = ActiveSupport::OrderedHash.new
    super
  end

end

=)