10

...或者一个防止重复条目的数组。

Ruby中是否有某种对象：

  • 响应 []、[]= 和 <<
  • 静默删除重复条目
  • 是可枚举的（或至少支持 find_all）
  • 保留插入条目的顺序
?

据我所知，数组支持点 1、3 和 4；而 Set 支持 1、2 和 3（但不支持 4）。并且 SortedSet 不会这样做，因为我的条目没有实现 <=>。

4

5 回答 5

13

从 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.9Set库恰好是基于 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]
于 2013-01-22T21:47:13.510 回答
7

据我所知，没有一个，并且 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 作为参考——他们有一个类似的“确保排序数组保持排序”的配方。

于 2009-04-21T18:25:08.523 回答
6

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

require 'active_support/ordered_hash'

class OrderedSet < Set

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

end

=)

于 2011-12-09T20:56:32.947 回答
1

您可以使用 Hash 来存储值，并在每个 Hash 对的值中存储一个递增值。然后，您可以通过对象的值访问对象，以排序的方式访问该集合，尽管速度很慢。

稍后我将尝试在此处添加一些代码以进一步解释。

我知道通过值访问比通过键慢得多。

更新 1：在 Ruby 1.9 中，Hash 元素按其插入顺序进行迭代。

于 2009-04-21T22:57:34.670 回答
0

不是我所知道的，但自己动手并不难。只需继承 Array 并使用 Set 来维护您的唯一性约束。

一个关于无声丢弃的问题。这将如何影响#[]=？如果我试图用已经存储在其他地方的东西覆盖现有条目，它是否应该删除将要删除的元素？我认为任何一种方式都可能在未来提供令人讨厌的惊喜。

于 2009-04-21T18:24:33.050 回答