Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is ipairs reliable on unsorted arrays?

I'm wondering if anyone can confirm whether you can trust ipairs() to; return all indices in order, for a table that's index-complete but unsorted.

We have code all over our project that clones tables using pairs(), however any arrays cloned come out unordered. I'm not sure if this is a problem however.

Compare:

A = {10, 20, 30, 40, 50, 60}

to:

B = {[1] = 10, [2] = 20, [3] = 30, [4] = 40, [5] = 50, [6] = 60}

If you loop these with pairs(), the first one is ordered while the other is not. (On a side note, B is suddenly sorted if you do a couple of back inserts)

Back to the original question. It seems B above iterates all values in order using ipairs(), but is this always guaranteed?

like image 774
CalvinE Avatar asked Dec 18 '14 14:12

CalvinE


3 Answers

Yep, it will.

ipairs() will iterates from index 1 to n continuously, and break in the first index which is not continuously.

For example:

B = {[1] = 10, [2] = 20, [3] = 30, [4] = 40, [5] = 50, [6] = 60}    

for i,v in ipairs(B) do
    print(i,v)
end

will print:
1   10
2   20
3   30
4   40
5   50
6   60

But,

B = {[1] = 10, [2] = 20, [3] = 30, [5] = 40, [6] = 50, [7] = 60}    

for i,v in ipairs(B) do
    print(i,v)
end

will print
1   10
2   20
3   30

Because 1,2,3 is continuously, but break in 4, so ipairs stop.

like image 112
Tim Avatar answered Oct 26 '22 00:10

Tim


A Lua table has no order.

It is simply a set of non-nil keys, each associated with a single non-nil value.


Implementations do optimize the storage of "number"-typed keys with positive integer values beginning at 1 and ending at a point their choosing, growing and shrinking internal structures with time-memory trade-offs for the various table operations.

pairs operates on all the key-value pairs in a table.

ipairs operates on a conceptual sequence of contiguous positive integer-valued keys with 1 and ending just before the first nil value. Other key-value pairs are ignored. So, your answer is "Yes, by design" as long as your idea of "index-complete" matches.

table.sort does the same. Other key-value pairs are ignored.

The default table length operator (#) is more restrictive. It operates on tables that have a "sequence", which are tables with no "number"-typed keys with positive integer values (an empty sequence) or all of their "number"-typed keys with positive integer values are a contiguous sequence, starting at 1. If you use the default table length operator on a non-sequence, you get undefined behavior.

like image 36
Tom Blodget Avatar answered Oct 25 '22 23:10

Tom Blodget


Yes, it's guaranteed that ipairs iterate a table with integer keys from 1 in order. Whether the table is sorted doesn't matter.

From Reference Manual: ipairs:

for i,v in ipairs(t) do body end

will iterate over the pairs (1,t[1]), (2,t[2]), ..., up to the first integer key absent from the table.

like image 3
Yu Hao Avatar answered Oct 26 '22 00:10

Yu Hao