Iterate over table in order of value

Question

Lets say I have a table like so:

{
   value = 4
},
{
   value = 3
},
{
   value = 1
},
{
   value = 2
}

and I want to iterate over this and print the value in order so the output is like so:

1
2
3
4

How do I do this, I understand how to use ipairs and pairs, and table.sort, but that only works if using table.insert and the key is valid, I need to be loop over this in order of the value.

I tried a custom function but it simply printed them in the incorrect order.

I have tried:

• Creating an index and looping that
• Sorting the table (throws error: attempt to perform __lt on table and table)
• And a combination of sorts, indexes and other tables that not only didn't work, but also made it very complicated.

I am well and truly stumped.

Answer 1

Sorting the table

This was the right solution.

(throws error: attempt to perform __lt on table and table)

Sounds like you tried to use a < b.

For Lua to be able to sort values, it has to know how to compare them. It knows how to compare numbers and strings, but by default it has idea how to compare two tables. Consider this:

local people = {
    { name = 'fred', age = 43 },
    { name = 'ted', age = 31 },
    { name = 'ned', age = 12 },
}

If I call sort on people, how can Lua know what I intend? I doesn't know what 'age' or 'name' means or which I'd want to use for comparison. I have to tell it.

It's possible to add a metatable to a table which tells Lua what the < operator means for a table, but you can also supply sort with a callback function that tells it how to compare two objects.

You supply sort with a function that receives two values and you return whether the first is "less than" the second, using your knowledge of the tables. In the case of your tables:

table.sort(t, function(a,b) return a.value < b.value end)

for i,entry in ipairs(t) do
    print(i,entry.value)
end

Answer 2

If you want to leave the original table unchanged, you could create a custom 'sort by value' iterator like this:

local function valueSort(a,b)
    return a.value < b.value;
end

function sortByValue( tbl ) -- use as iterator
    -- build new table to sort
    local sorted = {};
    for i,v in ipairs( tbl ) do sorted[i] = v end;
    -- sort new table
    table.sort( sorted, valueSort );
    -- return iterator
    return ipairs( sorted );
end

When sortByValue() is called, it clones tbl to a new sorted table, and then sorts the sorted table. It then hands the sorted table over to ipairs(), and ipairs outputs the iterator to be used by the for loop.

To use:

for i,v in sortByValue( myTable ) do
  print(v)
end

While this ensures your original table remains unaltered, it has the downside that each time you do an iteration the iterator has to clone myTable to make a new sorted table, and then table.sort that sorted table.

If performance is vital, you can greatly speed things up by 'caching' the work done by the sortByValue() iterator. Updated code:

local resort, sorted = true;

local function valueSort(a,b)
    return a.value < b.value;
end

function sortByValue( tbl ) -- use as iterator
    if not sorted then -- rebuild sorted table
        sorted = {};
        for i,v in ipairs( tbl ) do sorted[i] = v end;
        resort = true;
    end
    if resort then -- sort the 'sorted' table
        table.sort( sorted, valueSort );
        resort = false;
    end
    -- return iterator
    return ipairs( sorted );
end

Each time you add or remove an element to/from myTable set sorted = nil. This lets the iterator know it needs to rebuild the sorted table (and also re-sort it).

Each time you update a value property within one of the nested tables, set resort = true. This lets the iterator know it has to do a table.sort.

Now, when you use the iterator, it will try and re-use the previous sorted results from the cached sorted table.

If it can't find the sorted table (eg. on first use of the iterator, or because you set sorted = nil to force a rebuild) it will rebuild it. If it sees it needs to resort (eg. on first use, or if the sorted table was rebuilt, or if you set resort = true) then it will resort the sorted table.