diff options
Diffstat (limited to 'Data/DefaultContent/Libraries/containers/README.md')
-rw-r--r-- | Data/DefaultContent/Libraries/containers/README.md | 202 |
1 files changed, 0 insertions, 202 deletions
diff --git a/Data/DefaultContent/Libraries/containers/README.md b/Data/DefaultContent/Libraries/containers/README.md deleted file mode 100644 index cba8776..0000000 --- a/Data/DefaultContent/Libraries/containers/README.md +++ /dev/null @@ -1,202 +0,0 @@ -# Lua-ADT(5.1分支和5.2分支) -封装的lua数据结构, 元组(tuple)、动态数组(vector)、双向链表(list)、队列(queue)、栈(stack)。 -纯lua方法封装,没有使用oop,延续lua的简洁的风格。封装的数据结构能安全使用,在语言层面过滤掉非法操作,使其使用更加简单高效。 - -所有的类型都支持#获取长度. -> eg. -```lua - local tuple = require("tuple") - local v = tuple.create({2,3,6}) - print(#v) - ---3 -``` - -### 元组(tuple) -需要用table的动态数组初始化(不支持hashtable),只对外公开遍历,修改关闭。 - -遍历: -```lua - local tuple = require("tuple") - local v = tuple.create({2,3,6}) - - for i,v in ipairs(v) do --只支持ipairs遍历,抛弃了pairs(因为原则上我们是数组,不存在key) - print(i,v) - end - ---1 2 - ---2 3 - ---3 6 - - print(v) --重写了__tostring,方便快速浏览数据 - ---2,3,6 - - v[2] = 9 --因为对修改关闭了所以这地方修改会抛出错误 - ---lua: .\tuple.lua:33: >> Dee: Limited access - ---stack traceback: - ---[C]: in function 'error' -``` - -### 动态数组(vector) -实现高效的遍历和修改,但是新增和删除都不是线性时间复杂度。基本上就是lua table的数组,但是lua的table我们会一不小心就搞成不连续的。比如: -```lua - local t = {2,4} - t[4] = 9 - - print(#t) -- 2 -``` -#### 方法: - * add --尾添加(高效的操作) - * insert --插入(会有内存整理) - * addRange --尾添加一个表, - * removeAt - * remove - * contains - * indexOf - * sort - * find - -#### eg. -```lua - local vector = require("vector") - local v = vector.create() - - v:add(4) - v:add(5) - v:add(6) - v:add(7) - - for i,v in ipairs(v) do - print(i,v) - end - ---1 4 - ---2 5 - ---3 6 - ---4 7 - - print(v) - ---4,5,6,7 - - v[4] = 9 --修改值 - - print(v) - ---4,5,6,9 - - v[7] = 9 - ---lua: .\vector.lua:101: outrange of vector - ---stack traceback: - --- [C]: in function 'assert' -``` - -### 双向链表(list) -弥补动态数组增删的不足,提供增删效率,但是遍历和修改效率比较低 - -#### 方法: - * addFirst --头添加 - * addLast --尾添加 - * addBefore --node前添加 - * addAfter --node后添加 - * removeNode --删除node - * remove --根据值移除 - * find --查找node -#### eg. -```lua - local vector = require("list") - local v = list.create() - - v.addFirst(1) - v.addLast(2) - print(v) - ---1,2 - - local node = v.find(1) - node.value = 9 - print(v) - ---9,2 - - v.removeNode(node) - print(v) - ---2 - - v.addLast(10) - v.addLast(20) - v.addLast(30) - print(v) - ---2,10,20,30 - - for _,i,v in ipairs(v) do --第一个参数是node, i: index, v: value - print(i,v) - end - ---1 2 - ---2 10 - ---3 20 - ---4 30 -``` -### 栈(stack) -FILO先进后出, 对修改关闭,关闭遍历,只能通过方法修改数据 -#### 方法: - * push --添加 - * pop --移除 - * peek --返回栈顶数据 - * clear --清空 -#### eg. -```lua - local stack = require("stack") - local v = stack.create() - - v.push(1) - v.push(2) - v.push(5) - - print(v) - ---5,2,1 - print(v.len) - ---3 - v.pop() - print(v) - ---2,1 - v.clear() - print(v.len) - ---0 -``` -### 队列(queue) -FIFO,先进先出,因为是队首删除所以不能使用table.remove -#### 方法: - * enqueue --添加 - * dequeue --移除 - * peek --返回栈顶数据 - * clear --清空 - * #queue --获取长度 -#### eg. -```lua -local queue = require("queue") --- lua table -local cnt = 10000 * 1 - -local t = {} -for i=1,cnt do -t[i] = i -end - -local time = os.clock() -while #t > 0 do --- table.remove(t) - table.remove(t, 1) -end -print(os.clock() - time) ----1.037s - -local v = queue.create() - -for i=1,cnt do - v.enqueue(i) -end - - -local time1 = os.clock() -while v.len > 10 do - v.dequeue() -end -print(os.clock() - time1) ----0.005s -``` -1w条数据,lua table直接删除表头的耗时1.037s,queue耗时0.005s,而且queue整理内存的步长可以调整,耗时可以进步一提高. - |