Skip to content
LumenaryAcademy
Foundations 55 min

Tables, the one data structure

Arrays, dictionaries, records, sets, queues and matrices, all built from one idea, with the table library and a first pattern.

Code tested · 4AI-draftedAwaiting review by a computer scientist
MotivationH

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.

DefinitionsH

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.

lua
-- 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) end

It printed:

text
Ana	Chen	nil
Dagny	34
second	pair	ten	true
a table as a key	a boolean key
two	nil
100	true	false
left:	name	Dagny

Points to fix in your mind:

  • t.name is exactly t["name"], a convenience for keys that are valid identifiers. t[name], without quotes, uses the value of the variable name as 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 as t[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, changing b[1] changes a[1], because there is only one table. Two separately constructed tables are never equal, even if their contents are.
Worked examplesH

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.

lua
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:

text
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:	3

The 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": returning true for equal elements can make sort raise 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, and table.pack(...) does the reverse, recording the count in field n.

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 ... end visits positions 1 to the length.
  • for i, v in ipairs(t) do ... end visits 1, 2, 3, … and stops at the first nil.
  • for k, v in pairs(t) do ... end visits 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.

ComputationC

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:

OperationCostWhy
t[i] for i in the array part, t.nameconstantan array index, or one hash lookup
t[#t + 1] = v, table.insert(t, v)constant on averagean occasional rehash doubles the space, so its cost is spread thin
table.insert(t, 1, v), table.remove(t, 1)proportional to nevery later element must shift by one
#tproportional to log n at worstLua binary-searches for a border when it cannot read it off directly
pairs over the whole tableproportional to nit visits every slot of both parts
table.sort(t)proportional to n log na 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.

Worked examplesH

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.

lua
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:

text
the      6
boats    2
of       2
village  2
was      2
17 distinct words, 12 after removing stop words
boats village always before

The idioms here are everywhere in Lua code:

  • counts[word] = (counts[word] or 0) + 1 counts, treating a missing key as 0.
  • words[#words + 1] = word appends to a sequence, the same as table.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 true values, and stop[w] tests membership in constant time. A key that is a Lua keyword, such as and, must be written in bracket form in a constructor, ["and"] = true, and read as stop["and"].
  • table.concat(kept, " ", 1, 4) joins just the first four elements.
Worked examplesH

Matrices, queues and copies

lua
-- 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:

text
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, first and last, makes both ends constant time; clearing q[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] changed settings.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, and table.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

Exercises

1. Tables, the one data structure

Warm-upComputational

What does this program print?

local t = { "a", "b", x = "c", "d" }
print(#t .. t[3])

2. Tables, the one data structure

CoreComputational

What 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

CoreComputational

What does this program print?

local key = "colour"
local t = { colour = "red", key = "blue" }
print(t.key .. " " .. t[key])

4. Tables, the one data structure

CoreComputational

What 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

CoreComputational

What 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

StretchComputational

What 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

CoreComputational

This 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, " "))

Write elements separated by commas. Order and repeats don’t matter — just like in a set!

8. Tables, the one data structure

Warm-upHuman

A report prints word counts by looping over a counts table with pairs. Why should it collect the keys and sort them first?

Choose one

Further reading and resources