编程题:对象池(object_pool)
Java有废料回收(GC)的功能,可以回收无法再使用的内存、对象等资源。但C++就要自己负责释放动态分配的资源。身为一名软件开发者,我感到肩上的担子更重了。那么资源管理是怎样实现的呢?我查到一种用**空闲链表(free list)** 技术实现 **对象池(object pool)** 的入门级方案。
比方说有容量为C对象池Object pool[C + 1](0号是哑元不用),用空闲链表把它管起来。C++的链表听说要用深受爱戴和尊敬的**指针**,但指针才刚讲,来不及了,我先用数组索引模拟指针。
- 建立空闲链表的**头索引、后继数组**:int head = 1, next[C + 1];
- head为0表示没有空闲单元了,否则表示下个空闲单元的**索引**
- 初始化:next[1] = 2; next[2] = 3; ... next[C] = 0;
模拟使用:
- 分配对象:new
- 如果head == 0,没有可用单元,返回0即可。
- 如果head != 0,那么用p保存head现值,将head改为next[head],返回p表示可以使用pool[p]对象。
- 引用对象:ref p
- 如果p有效(在[1, C]的范围内,并且已经分配)输出ok
- 否则error
- 释放对象:delete p
- 如果p == 0,输出head即可。C/C++都是这样规定,允许free(NULL)或delete nullptr)。
- 如果p != 0,即请求归还pool[p]单元:
- 如果p有效(在[1, C]的范围内,并且已经分配),把它放到空闲链表的头部:next[p] = head; head = p;。
- 无效则输出error
目的:练习数组、循环、事件模拟、空闲链表技术;辅助理解指针。
#### 输入规格
- 首行设定对象池容量capacity C,C是正整数,小于65536。
- 后续有若干行的分配、释放请求,处理到EOF为止。请求数量小于65536。
- new分配操作
- ref x引用x号单元
- delete x释放x号单元
#### 输出规格
- 首行输出:capacity <C> # head=1
- 之后逐条处理操作:
- 原样输出操作和参数、空格、#、空格、**操作结果**
- 操作结果有以下几种:
- 分配:new # return <p>, head=<h>输出分配的单元索引p,分配之后的空闲头索引h。
- 如果没有空闲单元,返回0。
- 引用:ref <p> # ok或ref <p> # error
- 释放:
- delete <p> # head=<h>,其中p是释放的单元索引,h是调整后的空闲头索引。
- 如p无效则输出error
#### 样例输入
in
capacity 2
new
ref 1
new
new
delete 2
ref 2
delete 2
delete 9
delete 0
new
delete 1
new
delete 1
delete 2
#### 样例输出
out
capacity 2 # head=1
new # return 1, head=2
ref 1 # ok
new # return 2, head=0
new # return 0, head=0
delete 2 # head=2
ref 2 # error
delete 2 # error
delete 9 # error
delete 0 # head=2
new # return 2, head=0
delete 1 # head=1
new # return 1, head=0
delete 1 # head=1
delete 2 # head=2
答案:若无答案欢迎评论
比方说有容量为C对象池Object pool[C + 1](0号是哑元不用),用空闲链表把它管起来。C++的链表听说要用深受爱戴和尊敬的**指针**,但指针才刚讲,来不及了,我先用数组索引模拟指针。
- 建立空闲链表的**头索引、后继数组**:int head = 1, next[C + 1];
- head为0表示没有空闲单元了,否则表示下个空闲单元的**索引**
- 初始化:next[1] = 2; next[2] = 3; ... next[C] = 0;
模拟使用:
- 分配对象:new
- 如果head == 0,没有可用单元,返回0即可。
- 如果head != 0,那么用p保存head现值,将head改为next[head],返回p表示可以使用pool[p]对象。
- 引用对象:ref p
- 如果p有效(在[1, C]的范围内,并且已经分配)输出ok
- 否则error
- 释放对象:delete p
- 如果p == 0,输出head即可。C/C++都是这样规定,允许free(NULL)或delete nullptr)。
- 如果p != 0,即请求归还pool[p]单元:
- 如果p有效(在[1, C]的范围内,并且已经分配),把它放到空闲链表的头部:next[p] = head; head = p;。
- 无效则输出error
目的:练习数组、循环、事件模拟、空闲链表技术;辅助理解指针。
#### 输入规格
- 首行设定对象池容量capacity C,C是正整数,小于65536。
- 后续有若干行的分配、释放请求,处理到EOF为止。请求数量小于65536。
- new分配操作
- ref x引用x号单元
- delete x释放x号单元
#### 输出规格
- 首行输出:capacity <C> # head=1
- 之后逐条处理操作:
- 原样输出操作和参数、空格、#、空格、**操作结果**
- 操作结果有以下几种:
- 分配:new # return <p>, head=<h>输出分配的单元索引p,分配之后的空闲头索引h。
- 如果没有空闲单元,返回0。
- 引用:ref <p> # ok或ref <p> # error
- 释放:
- delete <p> # head=<h>,其中p是释放的单元索引,h是调整后的空闲头索引。
- 如p无效则输出error
#### 样例输入
in
capacity 2
new
ref 1
new
new
delete 2
ref 2
delete 2
delete 9
delete 0
new
delete 1
new
delete 1
delete 2
#### 样例输出
out
capacity 2 # head=1
new # return 1, head=2
ref 1 # ok
new # return 2, head=0
new # return 0, head=0
delete 2 # head=2
ref 2 # error
delete 2 # error
delete 9 # error
delete 0 # head=2
new # return 2, head=0
delete 1 # head=1
new # return 1, head=0
delete 1 # head=1
delete 2 # head=2
答案:若无答案欢迎评论