弹出Lua数组中的第一个元素

Question

我有一个Lua中的数组x。我想将head = x [1]设置为rest =数组的其余部分，以便rest [1] = x [2] ， rest [2] = x [3]，等等。

我该如何做到这一点？

（注意：我不在乎原始数组是否被改变。在JavaScript中，我会执行head = x.shift()，并且x将包含其余元素。）

- Jason S

Answer 1

head = table.remove(x, 1)

“弹出”有些不准确，因为它暗示这是一个廉价的操作，而移除表格的第一个元素需要重新定位其余内容 - 这就是 JavaScript 和其他一些语言中使用“shift”的原因。

- Miles

---

注意，对于任何较大的数组，这是一个非常缓慢的操作；请考虑一下为什么您想要这样做，并重新考虑一下。 - daurnimator

你的意思是“任何不合理大小的数组”，B-) - Nas Banov

不要重新考虑这个问题的动机，而是考虑使用除了数组之外的其他数据结构。一个链表（在Lua中很容易创建）可以使这个操作变得便宜，但每个节点需要更多的存储空间。 - Phrogz

Answer 2

您想要table.remove:

local t = {1,2,3,4}
local head = table.remove(t,1)
print( head )
--> 1
print( #t )
--> 3
print( t[1] )
--> 2

---

正如 @daurnimator 所指出的，这需要 Lua 运行时中数组的底层实现投入大量的工作，需要移动所有的表元素。如果您可以将数组表示为倒序，将数组中的最后一项称为 head，那么调用 table.remove() 将会是一个廉价的弹出操作。

local t = {4,3,2,1}
local head = table.remove(t)
print(head)
--> 1
print( #t )
--> 3
print( t[#t] )
--> 2

或者，您可以选择将元素序列表示为链表。在这种情况下，从列表头部弹出项目也是一项廉价操作（但将项目推入末尾不是，除非您在列表中跟踪“尾巴”）：

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

特别注意

local head,rest = numbers.val, numbers.rest

它不修改任何数据结构，只是为您提供了一个特定链中链接的rest句柄。

- Phrogz

Answer 3

在Lua中，将元素x插入序列通常是非常耗时的操作...

例如：S={a,b,c,d,e,f} 变为 S={a,b,c,x,d,e,f}

...因为d必须移动到索引5，e移动到索引6等等。

是否存在另一种形式为S的序列，其中S[a]=b，S[b]=c，S[c]=d，S[d]=e和S[e]=f？这样，您只需要输入：

S[c]=x S[x]=d

然后，瞬间，x就在c之后、d之前，仅需两个操作。

- Tim Crinion

---

最近发现我所说的是一种“链表”。 - Tim Crinion