Feature #11323
openDocumentation update on how uniq works / guarantee of order
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.