Popping the first element off an array
Solution 1
"Pop" is a bit of a misnomer, as it implies a cheap operation, and removing the first element of an table requires relocating the rest of the contents--hence the name "shift" in JavaScript and some other languages.
Solution 2
You want table.remove
:
local t = {1,2,3,4}
local head = table.remove(t,1)
print( head )
--> 1
print( #t )
--> 3
print( t[1] )
--> 2
As @daurnimator points out, this requires a lot of effort by the underlying implementation of arrays in the Lua runtime, shifting all the table elements. If you can instead represent your arrays backwards, calling the last item in the array head
, then the call to table.remove()
will be a cheap pop:
local t = {4,3,2,1}
local head = table.remove(t)
print(head)
--> 1
print( #t )
--> 3
print( t[#t] )
--> 2
Alternatively, you may choose to represent your sequence of elements as a linked list. In this case, popping an item off the head of the list is also a cheap operation (but pushing one onto the end is not, unless you keep track of the 'tail' in your list):
local setm,getm = setmetatable,getmetatable
local linkedlist=setm({__index={
tail = function(l) while l.rest do l=l.rest end return l end, -- N.B. O(n)!
push = function(l,v,t) t=l:tail() t.rest=setm({val=v},getm(l)) return t end,
cram = function(l,v) return setm({val=v,rest=l},getm(l)) end,
each = function(l,v)
return function() if l then v,l=l.val,l.rest return v end end
end
}},{ __call=function(lmeta,v,...)
local head,tail=setm({val=v},lmeta) tail=head
for i,v in ipairs{...} do tail=tail:push(v) end
return head
end })
local numbers = linkedlist(1,2,3,4)
for n in numbers:each() do print(n) end
--> 1
--> 2
--> 3
--> 4
local head,rest = numbers.val, numbers.rest
print(head)
--> 1
for n in rest:each() do print(n) end
--> 2
--> 3
--> 4
local unrest = rest:cram('99')
for n in unrest:each() do print(n) end
--> 99
--> 2
--> 3
--> 4
Note in particular that
local head,rest = numbers.val, numbers.rest
does not modify any data structures but just gives you a rest
handle on a particular link in the chain.
Related videos on Youtube
Jason S
Updated on December 01, 2020Comments
-
Jason S almost 3 years
I have an array
x
in Lua. I would like to sethead = x[1]
andrest =
the rest of the array, so thatrest[1] = x[2]
,rest[2] = x[3]
, etc.How can I do this?
(note: I don't care if the original array gets mutated. In Javascript I would do
head = x.shift()
andx
would contain the remaining elements.) -
daurnimator almost 13 yearsNote, for an array of any reasonable size, this is a VERY slow operation; try and reconsider why you want to do this...
-
Nas Banov almost 8 years@daurnimator you mean "array of any unreasonable size" B-)
-
Phrogz about 7 yearsInstead of reconsidering the motivation for this, instead consider perhaps using a data structure other than an array. A linked list (easy to create in Lua) makes this a cheap operation, at the expense of more storage needed for each node.
-
Tim Crinion almost 3 yearsRecently found out that what I was talking about is called a "linked list".