One structure to rule them all
Most languages give you a toolbox of data structures: arrays, lists, dictionaries, sets, records, objects, modules. Lua gives you one: the table. A table is an associative array, a collection of key and value pairs where both can be almost anything. With it you build every other structure. A list is a table with keys 1, 2, 3. A record is a table with string keys. A set is a table whose values are all true. An object is a table with fields and methods. Even the standard libraries are tables: string.upper is the field upper of the table string, and the global variables live in a table.
This is Lua's "mechanisms, not policies" at its clearest. One well-engineered structure, with an implementation tuned for both array-like and dictionary-like use, replaces half a dozen. Learning tables well is most of learning Lua.
Constructors, keys and references
Definition— Table
A value of type table: a mutable mapping from keys to values. Any value except nil (and the float NaN) can be a key; any value except nil can be a value, and assigning nil to a key removes it. Tables are created by constructors, the curly braces { ... }, and are objects: variables hold references to them, so assignment and argument passing share the same table, and == compares identity.
A constructor can mix three kinds of field. Plain expressions get consecutive integer keys starting at 1. name = value uses the string "name" as the key. [expression] = value uses any expression as the key.
-- One constructor, many shapes.
local list = { "Ana", "Bilal", "Chen" } -- keys 1, 2, 3
local record = { name = "Dagny", age = 34 } -- keys "name" and "age"
local mixed = { "first", "second", kind = "pair", [10] = "ten", ["two words"] = true }
print(list[1], list[3], list[4]) -- missing keys give nil
print(record.name, record["age"]) -- t.name is sugar for t["name"]
print(mixed[2], mixed.kind, mixed[10], mixed["two words"])
-- Any value except nil can be a key: numbers, strings, booleans, even tables.
local seen = {}
local point = { x = 1, y = 2 }
seen[point] = "a table as a key"
seen[true] = "a boolean key"
print(seen[point], seen[true])
-- Float keys with integer values are the same key as the integer.
local t = {}
t[2] = "two"
print(t[2.0], t["2"]) -- but the string "2" is a different key
-- Tables are objects: assignment copies the reference, not the table.
local a = { 1, 2, 3 }
local b = a
b[1] = 100
print(a[1], a == b, { 1 } == { 1 }) -- equality is identity
-- Assigning nil removes a key.
record.age = nil
for k, v in pairs(record) do print("left:", k, v) endIt printed:
Ana Chen nil
Dagny 34
second pair ten true
a table as a key a boolean key
two nil
100 true false
left: name DagnyPoints to fix in your mind:
t.nameis exactlyt["name"], a convenience for keys that are valid identifiers.t[name], without quotes, uses the value of the variablenameas the key: a frequent beginner mix-up.- Missing keys give
nil, never an error. That makes lookups convenient and typos silent; lesson 5 shows how metatables can make a table complain instead. - Number keys are normalised:
t[2.0]is the same slot ast[2]. But"2"is a string, a different key, and Lua does not convert keys. - Tables as keys work by identity:
seen[point]finds the value only with that very table, not with another table that happens to have the same contents. - Shared references. After
local b = a, changingb[1]changesa[1], because there is only one table. Two separately constructed tables are never equal, even if their contents are.
Sequences and the length operator
A table whose keys are exactly 1, 2, …, n is called a sequence, and most of the table library works on sequences. Internally Lua stores such keys in a compact array part, so lists are as fast as arrays in other scripting languages, and in Lua 5.5 large arrays use considerably less memory than before.
local fruits = { "mango", "papaya", "guava" }
table.insert(fruits, "lychee") -- append
table.insert(fruits, 1, "cashew") -- insert at position 1, shifting the rest
local removed = table.remove(fruits, 2) -- remove position 2 and return it
print(#fruits, removed, table.concat(fruits, ", "))
for i, fruit in ipairs(fruits) do -- in order, 1 to the first nil
io.write(i, "=", fruit, " ")
end
print()
table.sort(fruits) -- in place, using <
print(table.concat(fruits, " "))
table.sort(fruits, function(x, y) return #x < #y or (#x == #y and x < y) end)
print(table.concat(fruits, " "))
print(table.unpack({ 10, 20, 30 })) -- a list's elements as separate values
local packed = table.pack("a", nil, "c") -- keeps a count in n, even with nils
print(packed.n, packed[1], packed[2], packed[3])
-- A "hole" makes the length operator unreliable.
local holes = { 1, 2, nil, 4 }
print("#holes =", #holes)
local count = 0
for _ in pairs(holes) do count = count + 1 end
print("non-nil values:", count)It printed:
4 mango cashew, papaya, guava, lychee
1=cashew 2=papaya 3=guava 4=lychee
cashew guava lychee papaya
guava cashew lychee papaya
10 20 30
3 a nil c
#holes = 2
non-nil values: 3The table library's main functions:
table.insert(t, v)appends;table.insert(t, pos, v)inserts and shifts later elements up.table.remove(t)removes and returns the last element;table.remove(t, pos)removes at a position and shifts down. Together with insert, this makes a sequence a ready-made stack.table.concat(t, sep, i, j)joins elements (strings or numbers) into one string. This is the efficient way to build large strings.table.sort(t, less)sorts in place, using<or a function that says whether its first argument should come before its second. The function must be a consistent "less than": returningtruefor equal elements can makesortraise an error ("invalid order function"). The sort is not stable, so break ties explicitly, as the second sort does by length and then alphabetically.table.unpack(t)returns the elements as separate values, andtable.pack(...)does the reverse, recording the count in fieldn.
Borders, and why holes hurt
Definition— Length of a table
For a table t, #t returns a border: an index n such that t[n] is not nil and t[n + 1] is nil (or 0 if t[1] is nil). A sequence has exactly one border, its length. A table with holes (nil values between non-nil ones) has several borders, and #t may return any of them.
{ 1, 2, nil, 4 } has two borders, 2 and 4, and Lua 5.5 printed 2 here; another Lua version, or the same table built in a different order, may give 4. Both are correct by the definition, which is exactly why you should never rely on # for a table with holes. If a list may contain nils, store its length yourself, as table.pack does with n.
Three ways to iterate
for i = 1, #t do ... endvisits positions 1 to the length.for i, v in ipairs(t) do ... endvisits 1, 2, 3, … and stops at the first nil.for k, v in pairs(t) do ... endvisits every key, including non-integer ones, in an unspecified order that can change from run to run of the same program or between versions. Never rely on it for output: collect the keys and sort them, as the next program does.
During a pairs traversal you may change or clear (set to nil) existing fields, but you must not add new keys.
What a table costs
Knowing roughly how tables are built tells you which operations are cheap. Every table has two parts. The array part is a plain C array holding the values for keys 1 to some size n, stored in order, with no keys at all: t[i] is a direct index. The hash part is a hash table for every other key: strings, floats, booleans, tables, and integers outside the array part's range. Lua decides the array part's size when it rehashes, which happens only when a table runs out of room: it counts the integer keys and picks the largest power of two n such that more than half of the slots 1 to n would be in use.
That design gives these costs for a table of n elements:
| Operation | Cost | Why |
|---|---|---|
t[i] for i in the array part, t.name | constant | an array index, or one hash lookup |
t[#t + 1] = v, table.insert(t, v) | constant on average | an occasional rehash doubles the space, so its cost is spread thin |
table.insert(t, 1, v), table.remove(t, 1) | proportional to n | every later element must shift by one |
#t | proportional to log n at worst | Lua binary-searches for a border when it cannot read it off directly |
pairs over the whole table | proportional to n | it visits every slot of both parts |
table.sort(t) | proportional to n log n | a quicksort variant |
Two consequences matter in everyday code. First, appending is cheap and removing from the front is not, which is why the queue below keeps two indices instead of calling table.remove(t, 1). Second, building a big table one element at a time triggers a series of rehashes, each copying everything so far. The total is still proportional to n, but when you know the final size, Lua 5.5's table.create(n) reserves the space once. The paper The Implementation of Lua 5.0 (2005), by Lua's three authors, describes this design in detail; the source file ltable.c is the current word.
Counting words: dictionaries, sets and a first pattern
Counting is to tables what "hello world" is to languages. This program also uses a pattern: gmatch("%a+") returns an iterator over every run of letters in a string. Lua's patterns are a deliberately small relative of regular expressions: %a is a letter, %d a digit, %s whitespace, %w a letter or digit, + means one or more, * zero or more, - zero or more but as few as possible, and % escapes special characters. They have no alternation (|), which keeps the implementation tiny; for full regular expressions, Lua programmers use the LPeg library, a parsing library written by Roberto Ierusalimschy.
local text = [[
The sea was calm, the sky was clear, and the boats of the
village went out before dawn, as the boats of the village always had.]]
-- Count words: a table from word to count.
local counts = {}
for word in text:lower():gmatch("%a+") do -- %a+ : a run of letters
counts[word] = (counts[word] or 0) + 1
end
-- pairs visits keys in no particular order, so collect and sort them.
local words = {}
for word in pairs(counts) do words[#words + 1] = word end
table.sort(words, function(a, b)
if counts[a] ~= counts[b] then return counts[a] > counts[b] end
return a < b
end)
for i = 1, 5 do
print(string.format("%-8s %d", words[i], counts[words[i]]))
end
-- A set is a table whose values are all true.
local stop = { the = true, of = true, ["and"] = true, as = true, was = true }
local kept = {}
for _, w in ipairs(words) do
if not stop[w] then kept[#kept + 1] = w end
end
print(#words .. " distinct words, " .. #kept .. " after removing stop words")
print(table.concat(kept, " ", 1, 4))It printed:
the 6
boats 2
of 2
village 2
was 2
17 distinct words, 12 after removing stop words
boats village always beforeThe idioms here are everywhere in Lua code:
counts[word] = (counts[word] or 0) + 1counts, treating a missing key as 0.words[#words + 1] = wordappends to a sequence, the same astable.insert(words, word)and a little faster.- Sort the keys before printing, with a comparison function that orders by count (largest first) and then alphabetically, so the output is the same every time.
- A set is a table of
truevalues, andstop[w]tests membership in constant time. A key that is a Lua keyword, such asand, must be written in bracket form in a constructor,["and"] = true, and read asstop["and"]. table.concat(kept, " ", 1, 4)joins just the first four elements.
Matrices, queues and copies
-- A matrix is a table of rows.
local grid = {}
for r = 1, 3 do
grid[r] = {}
for c = 1, 4 do grid[r][c] = r * c end
end
for _, row in ipairs(grid) do print(table.concat(row, "\t")) end
-- A queue with two indices: constant-time push and pop at both ends.
local queue = { first = 1, last = 0 }
local function push(q, v) q.last = q.last + 1; q[q.last] = v end
local function pop(q)
if q.first > q.last then return nil end
local v = q[q.first]
q[q.first] = nil -- let the value be collected
q.first = q.first + 1
return v
end
push(queue, "Lagos"); push(queue, "Lima"); push(queue, "Lyon")
print(pop(queue), pop(queue), pop(queue), pop(queue))
-- Copying: the library has no copy function, so write a shallow one.
local function shallow_copy(t)
local c = {}
for k, v in pairs(t) do c[k] = v end
return c
end
local settings = { theme = "dark", sizes = { 12, 14 } }
local mine = shallow_copy(settings)
mine.theme = "light"
mine.sizes[1] = 99 -- the inner table is shared
print(settings.theme, mine.theme, settings.sizes[1])
-- table.move copies a range; table.create (Lua 5.5) preallocates space.
local digits = table.create(10)
for i = 1, 10 do digits[i] = i - 1 end
local tail = table.move(digits, 8, 10, 1, {})
print(#digits, table.concat(tail, ","))It printed:
1 2 3 4
2 4 6 8
3 6 9 12
Lagos Lima Lyon nil
dark light 99
10 7,8,9- Matrices are tables of rows. Each row must be created (
grid[r] = {}) before its cells are set;grid[r][c]on a missing row is an error ("attempt to index a nil value"), not an automatic creation. - Queues.
table.remove(t, 1)works as a "dequeue", but it shifts every remaining element, which costs time proportional to the length. A queue with two indices,firstandlast, makes both ends constant time; clearingq[q.first]lets the garbage collector reclaim the value. - Copying. There is no built-in copy, because "copy" has no single right meaning. A shallow copy, as here, shares nested tables: changing
mine.sizes[1]changedsettings.sizes[1]. Write a recursive deep copy when you need independence, and decide what it should do with cycles and metatables. table.move(a, f, e, t, dest)copies a range of elements, efficiently, andtable.create(n)(new in Lua 5.5) creates an empty table with room for n sequence elements, avoiding repeated resizing when you know the size in advance. On older Lua versions, simply use{}.
Lua frees tables automatically, with a garbage collector, once nothing refers to them. You never free memory yourself, but you can keep memory alive by accident: a table stored in a long-lived cache or global stays reachable, and everything it refers to stays with it.
Misconception
"Lua arrays start at 1 because of a whim; I can just start mine at 0." You can store a value at index 0, since any key is allowed, but #, ipairs, table.insert, table.concat, table.sort and table.unpack all assume sequences start at 1, and a value at 0 is invisible to them. The convention goes back to Lua's origins in data-entry languages for engineers, many of whom were not professional programmers and for whom counting from one was natural. Follow the convention, and convert at the boundary when you exchange indices with C or with zero-based data.
Exercises
1. Tables, the one data structure
Warm-upComputationalWhat does this program print?
local t = { "a", "b", x = "c", "d" }
print(#t .. t[3])
2. Tables, the one data structure
CoreComputationalWhat does this program print?
local a = { n = 1 }
local b = a
local c = { n = 1 }
b.n = 2
print(a.n .. " " .. tostring(a == b) .. " " .. tostring(a == c))
3. Tables, the one data structure
CoreComputationalWhat does this program print?
local key = "colour"
local t = { colour = "red", key = "blue" }
print(t.key .. " " .. t[key])
4. Tables, the one data structure
CoreComputationalWhat number does this program print?
local t = { 10, 20, nil, 40 }
local sum = 0
for _, v in ipairs(t) do sum = sum + v end
print(sum)
5. Tables, the one data structure
CoreComputationalWhat does this program print?
local s = { "a", "b", "c" }
table.insert(s, 2, "x")
table.remove(s)
table.insert(s, "y")
print(table.concat(s))
6. Tables, the one data structure
StretchComputationalWhat number does this program print?
local n = 0
for digits in ("phone 555-0199, room 12"):gmatch("%d+") do
n = n + #digits
end
print(n)
7. Tables, the one data structure
CoreComputationalThis program collects every key that pairs visits, converts each to a string and sorts them. Which keys does it find? Give each one as it is printed.
local t = { "x", "y", name = "z", [5] = "w" }
local keys = {}
for k in pairs(t) do keys[#keys + 1] = tostring(k) end
table.sort(keys)
print(table.concat(keys, " "))
8. Tables, the one data structure
Warm-upHumanA report prints word counts by looping over a counts table with pairs. Why should it collect the keys and sort them first?
Further reading and resources
- Reference Manual: Table ConstructorsThe exact rules for list, record and bracketed fields in a constructor.
- Reference Manual: The Length OperatorThe definition of a border and why the length of a table with holes is not unique.
- Reference Manual: Table ManipulationEvery function in the table library.
- Reference Manual: PatternsLua's pattern language, used by find, match, gmatch and gsub.