Is ipairs reliable on unsorted arrays?

Question

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?

Babita

Answer 1

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.

Triserial

Great explanation. If I understand you correctly; it's because of the Lua implementation I use, that A = {10, 20, 30, 40, 50, 60} end up ordered when looping with pairs(). But is not part of the standard. – Babita

@CalvinE, the traversal order may change when you run the program again, if you're running Lua 5.2. – Stirrup

Answer 2

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.

Tegument

Answer 3

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.

Turoff

Thanks for the reference, exactly what I was looking for. Though Tom's elaboration on implementations gave me a deeper understanding and earned the "solution" this time. – Babita