无状态迭代器

简介: 无状态迭代器

顾名思义,无状态迭代器就是一种自身不保存任何状态的迭代器。因此,可以在多个循环中使用同一个无状态迭代器,从而避免创建新闭包的开销


正如刚刚所看到的, for 循环会以不可变状态和控制变量为参数调用迭代函数。一个无状态迭代器只根据这两个值来为迭代生成下一个元素。这类迭代器的一个典型例子就是 ipairs ,它可以迭代一个序列中的所有元素。

a = {"one", "two", "three"}
for i, v in ipairs(a) do
  print(i, v)
end


迭代的状态由正在被遍历的表(一个不可变状态,它不会在循环中改变)及当前的索引值(控制变量)组成。 ipairs (工厂)和迭代器都非常简单,我们可以在 Lua 语言中将其编写出来:

local function iter(t, i)
  i = i + 1
  local v = t[i]
  for v then
    return i,v
  end
end
function ipairs(t)
  return iter,t,0
end


当调用 for 循环中的 ipairs(t) 时, ipairs(t) 会返回三个值,即迭代函数 iter ,不可变状态表 t 和控制变量的初始值 0 . 然后, Lua 语言调用 iter(t, 0) ,得到 1 , t[1] (除非 t[1] 已经变成了 nil )。在第二次迭代中, Lua 语言调用 iter(t, 1) ,得到 2 , t[2] ,以此类推,直至得到第一个为 nil 的元素。


函数 pairs 与函数 ipairs 类似,也用与遍历一个表中的所有元素。不同的是,函数 pairs 的迭代函数是 Lua 的一个基本函数 next

function pairs(t)
  return next, t, nil
end


在调用 next(t, k) 时, k 是表 t 的一个键,该函数会以随机次序返回表中的下一个键及 k 对应的值(作为第二个返回值)。调用 next(t, nil) 时,返回表中的第一个键值对。当所有元素被遍历完时,函数 next 返回 nil


我们可以不用调用 pairs 而直接使用 next

for k, v in next, t do 
  loop body
end


注意

for 循环会把表达式列表的结果调整为三个值,因此上例中得到的是 nexttnil ,这也正与 pairs(t) 的返回值完全一致。


关于无状态迭代器的另一个有趣的示例是遍历链表的迭代器(链表在 Lua 语言中并不常见,但有时也需要用到)。我们的第一反应可能是只把当前节点当做控制变量,以便于迭代函数能够返回下一个节点:

local function getnext(node)
  return node.next
end
function traverse(list)
  return getnext, nil, list
end


但是,这种实现会跳过第一个节点。所以,我们需要使用如下代码:

local function getnext(list, node)
  if not node then
    return list
  else
    return node.next
  end
end
function traverse(list)
  return getnext, list, nil
end


这里的技巧是:除了将当前节点作为控制变量,还要将头节点作为不可变状态traverse 返回的第二个值)。第一次调用迭代函数 getnext 时, nodenil ,因此函数返回 list 作为第一个节点。在后续的调用中, node 不再是 nil ,所以迭代函数会像我们所期望的那样返回 nodenext

目录
相关文章
|
5月前
集合中常见方法及遍历方式
集合中常见方法及遍历方式
37 1
|
7月前
|
C++ 容器
【c++】优先级队列|反向迭代器(vector|list)
【c++】优先级队列|反向迭代器(vector|list)
52 0
|
8月前
|
存储 编译器 C++
【C++/STL】list(常见接口、模拟实现、反向迭代器、)
【C++/STL】list(常见接口、模拟实现、反向迭代器、)
58 0
|
8月前
|
存储 算法 程序员
深入理解 C++ 自定义链表中实现迭代器
深入理解 C++ 自定义链表中实现迭代器
99 0
|
8月前
|
并行计算 算法 安全
【C++ 迭代器 】C++ 迭代器标签的使用场景
【C++ 迭代器 】C++ 迭代器标签的使用场景
98 0
|
8月前
|
算法 数据处理 C语言
【C++迭代器深度解析】C++迭代器类型之间的继承关系与反向迭代器的独特性
【C++迭代器深度解析】C++迭代器类型之间的继承关系与反向迭代器的独特性
115 0
|
编译器 C++ 容器
【STL】模拟实现反向迭代器
【STL】模拟实现反向迭代器
40 1
|
前端开发
记一个异步循环遍历的问题
记一个异步循环遍历的问题
57 0
【C++STL】list的反向迭代器
【C++STL】list的反向迭代器
80 0
|
算法 C语言 容器
通过栈/队列/优先级队列/了解容器适配器,仿函数和反向迭代器
通过栈/队列/优先级队列/了解容器适配器,仿函数和反向迭代器
110 0