Does Ruby uniq keep order?

Question

The documentation says nothing about this ( http://www.ruby-doc.org/core-2.2.0/Array.html#method-i-uniq ).

Also, is a naive search O (n ^ 2) or something else like hashmap used? In the latter case, should I understand that my elements must have the correct hash and eql? when do I want to highlight them?

Answer 1

Given the code (in C) for Array#uniq

 rb_ary_uniq(VALUE ary) { VALUE hash, uniq, v; long i; if (RARRAY_LEN(ary) <= 1) return rb_ary_dup(ary); if (rb_block_given_p()) { hash = ary_make_hash_by(ary); uniq = ary_new(rb_obj_class(ary), RHASH_SIZE(hash)); st_foreach(RHASH_TBL(hash), push_value, uniq); } else { hash = ary_make_hash(ary); uniq = ary_new(rb_obj_class(ary), RHASH_SIZE(hash)); for (i=0; i<RARRAY_LEN(ary); i++) { st_data_t vv = (st_data_t)(v = rb_ary_elt(ary, i)); if (st_delete(RHASH_TBL(hash), &vv, 0)) { rb_ary_push(uniq, v); } } } ary_recycle_hash(hash); return uniq; } 

In the general case ( else block), it creates a hash from the array (which combines the key without preserving the order). Then it creates a new empty array with the desired size. Finally, it goes through the first array, and when it finds the key in the hash, it removes that key and clicks it on an empty array.

Therefore, the order is preserved.

I would say that complexity is O (complexity (ary_make_hash) + N) in time, which is probably O (N)