Ruby: хотите подобный множеству объект, который сохраняет порядок

Question

... или, альтернативно, массив, который предотвращает повторяющиеся записи.

Есть ли в Ruby какой-то объект, который:

• отвечает на [], [] = и << </li>
• молча отбрасывает повторяющиеся записи
• является Enumerable (или, по крайней мере, поддерживает find_all)
• сохраняет порядок, в котором были вставлены записи

Насколько я могу судить, Массив поддерживает точки 1, 3 и 4; в то время как набор поддерживает 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 в настоящее время построена на хэше, в настоящее время вы можете использовать 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

Мне нравится это решение, хотя оно требует OrderedHash active_support

require 'active_support/ordered_hash'

class OrderedSet < Set

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

end

=)

Answer 3

Насколько я знаю, такого не существует, и 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

Кажется, чтобы охватить все базы. Я использовал удобную Ruby Cookbook от OReilly в качестве справочного материала - у них есть рецепт «Убедиться, что отсортированный массив остается отсортированным», что похоже.

Answer 4

Вы можете использовать Hash для хранения значений, и иметь значение приращения, сохраненное в значении каждой пары Hash. Затем вы можете получить доступ к набору отсортированным образом, хотя и медленно, путем доступа к объектам через их значения.

Я постараюсь добавить сюда код позже, чтобы объяснить подробнее.

Я знаю, что доступ через значения намного медленнее, чем по ключам.

Обновление 1: в Ruby 1.9 элементы Hash повторяются в порядке их вставки.

Answer 5

Не то, чтобы я знал, но это не было бы трудно свернуть свое собственное. Просто создайте подкласс Array и используйте Set для поддержания ограничения уникальности.

Один вопрос о тихом отбрасывании. Как это повлияет на # [] =? Если бы я пытался перезаписать существующую запись чем-то, что уже было сохранено где-то еще, следует ли вообще удалять элемент, который будет удален? Я думаю, что в любом случае в будущем могут возникнуть неприятные сюрпризы.