Project

General

Profile

Actions

Feature #11323

open

Documentation update on how uniq works / guarantee of order

Added by wilburlo (Daniel Lo) over 9 years ago. Updated over 9 years ago.

Status:
Open
Assignee:
-
Target version:
-
[ruby-core:69836]

Description

Greetings,

I was looking at Array.uniq and I was wondering how the code made the array unique.

There are 2 different possible outcomes for making an array unique.

For example:
[1,2,1]

The first value is kept and all subsequent duplicate values are removed: [1,2]
or
The array is made unique, order is not retained: [2,1]

Would the ruby team consider adding a guarantee of order (first seen/first kept) is adding this to the Array.uniq specification? This is what happens in practice (irb), having this as part of the specification would be nice.

I looked at the code http://ruby-doc.org/core-2.2.1/Array.html#method-i-uniq however, I wasn't able to determine exactly how it worked. :(

Thank you!

Regards,

Daniel Lo

Updated by 0x0dea (D.E. Akers) over 9 years ago

Array#uniq is implemented using a hash table; since hashes in Ruby preserve insertion order, so too does Array#uniq. The following simplified translation to Ruby should help clarify what's going on in rb_ary_uniq():

class Array
  def uniq
    hash = {}
    each { |val| hash[val] = val }
    hash.values
  end
end

There is precedent in Array's documentation for mentioning that a method is order-preserving, and it seems that #uniq should certainly do so.

Actions

Also available in: Atom PDF

Like0
Like0