Tables
Introduction
The table type implements associative arrays. An associative array is an array that can be indexed not only with numbers, but also with strings or any other value of the language, except nil. Moreover, tables have no fixed size; you can add as many elements as you want to a table dynamically. Tables are the main (in fact, the only) data structuring mechanism in Lua, and a powerful one. We use tables to represent ordinary arrays, symbol tables, sets, records, queues, and other data structures, in a simple, uniform, and efficient way. Lua uses tables to represent packages as well.
Tables in Lua are neither values nor variables; they are objects. If you are familiar with arrays in Java or Scheme, then you have a fair idea of what we mean. However, if your idea of an array comes from C or Pascal, you have to open your mind a bit. You may think of a table as a dynamically allocated object; your program only manipulates references (or pointers) to them. There are no hidden copies or creation of new tables behind the scenes. Moreover, you do not have to declare a table in Lua; in fact, there is no way to declare one. You create tables by means of a constructor expression, which in its simplest form is written as {}:
a = {} -- create a table and store its reference in `a'
k = "x"
a[k] = 10 -- new entry, with key="x" and value=10
a[20] = "great" -- new entry, with key=20 and value="great"
print(a["x"]) --> this will print 10
k = 20
print(a[k]) --> this will print "great"
a["x"] = a["x"] + 1 -- increments entry "x"
print(a["x"]) --> this will print 11
A table is always anonymous. There is no fixed relationship between a variable that holds a table and the table itself:
a = {}
a["x"] = 10
b = a -- `b' refers to the same table as `a'
print(b["x"]) --> This will print 10
b["x"] = 20
print(a["x"]) --> This will print 20
a = nil -- now only `b' still refers to the table
b = nil -- now there are no references left to the table
When a program has no references to a table left, Lua memory management will eventually delete the table and reuse its memory. Each table may store values with different types of indices and it grows as it needs to accommodate new entries:
a = {} -- empty table
-- create 1000 new entries
for i=1,1000 do a[i] = i*2 end
print(a[9]) --> This will print 18
a["x"] = 10
print(a["x"]) --> This will print 10
print(a["y"]) --> This will print nil
Notice the last line: Like global variables, table fields evaluate to nil if they are not initialized. Also like global variables, you can assign nil to a table field to delete it. That is not a coincidence: Lua stores global variables in ordinary tables. To represent records, you use the field name as an index. Lua supports this representation by providing a.name as syntactic sugar for a["name"]. So, we could write the previous example in a cleanlier manner as
a = {}
for i=1,1000 do a[i] = i*2 end
print(a[9])
a.x = 10 -- same as a["x"] = 10
print(a.x) -- same as print(a["x"])
print(a.y) -- same as print(a["y"])
For Lua, the two forms are equivalent and can be intermixed freely; but for a human reader, each form may signal a different intention. A common mistake for beginners is to confuse a.x with a[x]. The first form represents a["x"], that is, a table indexed by the string "x". The second form is a table indexed by the value of the variable x. See the difference:
a = {}
x = "y"
a[x] = 10 -- put 10 in field "y"
print(a[x]) --> 10 -- value of field "y"
print(a.x) --> nil -- value of field "x" (undefined)
print(a.y) --> 10 -- value of field "y"
Table Constructors
Table constructors are expressions that create and initialize tables. They are a distinctive feature of Lua and one of its most useful and versatile mechanisms.
The simplest constructor is the empty constructor, {}, which creates an empty table. Constructors also initialize arrays (called also sequences or lists). For instance, the statement
days = {"Sunday", "Monday", "Tuesday", "Wednesday",
"Thursday", "Friday", "Saturday"}
will initialize days[1] with the string "Sunday" (the first element has always index 1, not 0), days[2] with "Monday", and so on:
days = {"Sunday", "Monday", "Tuesday", "Wednesday",
"Thursday", "Friday", "Saturday"}
print(days[4])
Will result in:
Wednesday
For those that really want their arrays starting at 0, it is not difficult to write the following:
days = {[0]="Sunday", "Monday", "Tuesday", "Wednesday",
"Thursday", "Friday", "Saturday"}
Now, the first value, "Sunday", is at index 0. That zero does not affect the other fields, but "Monday" naturally goes to index 1, because it is the first list value in the constructor; the other values follow it. Despite this facility, I do not recommend the use of arrays starting at 0 in Lua. Remember that most functions assume that arrays start at index 1, and therefore will not handle such arrays correctly. You can always put a comma after the last entry. These trailing commas are optional, but are always valid:
a = {[1]="red", [2]="green", [3]="blue",}
Such flexibility makes it easier to write programs that generate Lua tables, because they do not need to handle the last element as a special case. Finally, you can always use a semicolon instead of a comma in a constructor. We usually reserve semicolons to delimit different sections in a constructor, for instance to separate its list part from its record part:
{x=10, y=45; "one", "two", "three"}
Arrays
We implement arrays in Lua simply by indexing tables with integers. Therefore, arrays do not have a fixed size, but grow as we need. Usually, when we initialize the array we define its size indirectly. For instance, after the following code
a = {} -- new array
for i=1, 1000 do
a[i] = 0
end
any attempt to access a field outside the range 1-1000 will return nil, instead of zero. You can start an array at index 0, 1, or any other value:
-- creates an array with indices from -5 to 5
a = {}
for i=-5, 5 do
a[i] = 0
end
However, it is customary in Lua to start arrays with index 1. The Lua libraries adhere to this convention; so, if your arrays also start with 1, you will be able to use their functions directly. We can use constructors to create and initialize arrays in a single expression:
squares = {1, 4, 9, 16, 25, 36, 49, 64, 81}
Such constructors can be as large as you need (well, up to a few million elements).
Matrices and Multi-Dimensional Arrays
There are two main ways to represent matrices in Lua. The first one is to use an array of arrays, that is, a table wherein each element is another table. For instance, you can create a matrix of zeros with dimensions N by M with the following code:
mt = {} -- create the matrix
for i=1,N do
mt[i] = {} -- create a new row
for j=1,M do
mt[i][j] = 0
end
end
Because tables are objects in Lua, you have to create each row explicitly to create a matrix. On the one hand, this is certainly more verbose than simply declaring a matrix, as you do in C or Pascal. On the other hand, that gives you more flexibility. For instance, you can create a triangular matrix changing the line
for j=1,M do
in the previous example to
for j=1,i do
With that code, the triangular matrix uses only half the memory of the original one. The second way to represent a matrix in Lua is by composing the two indices into a single one. If the two indices are integers, you can multiply the first one by a constant and then add the second index. With this approach, the following code would create our matrix of zeros with dimensions N by M:
mt = {} -- create the matrix
for i=1,N do
for j=1,M do
mt[i*M + j] = 0
end
end
If the indices are strings, you can create a single index concatenating both indices with a character in between to separate them. For instance, you can index a matrix m with string indices s and t with the code m[s..':'..t], provided that both s and t do not contain colons (otherwise, pairs like ("a:", "b") and ("a", ":b") would collapse into a single index "a::b"). When in doubt, you can use a control character like `\0´ to separate the indices.
Quite often, applications use a sparse matrix, a matrix wherein most elements are 0 or nil. For instance, you can represent a graph by its adjacency matrix, which has the value x in position m,n only when the nodes m and n are connected with cost x; when those nodes are not connected, the value in position m,n is nil. To represent a graph with ten thousand nodes, where each node has about five neighbors, you will need a matrix with a hundred million entries (a square matrix with 10,000 columns and 10,000 rows), but approximately only fifty thousand of them will not be nil (five non-nil columns for each row, corresponding to the five neighbors of each node). Many books on data structures discuss at length how to implement such sparse matrices without wasting 400 MB of memory, but you do not need those techniques when programming in Lua. Because arrays are represented by tables, they are naturally sparse. With our first representation (tables of tables), you will need ten thousand tables, each one with about five elements, with a grand total of fifty thousand entries. With the second representation, you will have a single table, with fifty thousand entries in it. Whatever the representation, you only need space for the non-nil elements.
