简易内存池
题目描述
- 请实现一个简易内存池，根据请求命令完成内存分配和释放。
- 内存池支持两种操作命令，REQUEST和RELEASE，其格式为：
- REQUEST=请求的内存大小表示请求分配指定大小内存，如果分配成功，返回分配到的内存首地址；如果内存不足，或指定的大小为0，则输出error。
- RELEASE=释放的内存首地址表示释放掉之前分配的内存，释放成功无需输出，如果释放不存在的首地址则输出error。
注意：
- 内存池总大小为100字节。
- 内存池地址分配必须是连续内存，并优先从低地址分配。
- 内存释放后可被再次分配，已释放的内存在空闲时不能被二次释放。
- 不会释放已申请的内存块的中间地址。
- 释放操作只是针对首地址所对应的单个内存块进行操作，不会影响其它内存块。
输入
- 首行为整数 N , 表示操作命令的个数，取值范围：0 < N <=
100。
- 接下来的N行, 每行将给出一个操作命令，操作命令和参数之间用 “=”
分割。
输出
示例 1
输入输出示例仅供调试，后台判题数据一般不包含示例
输入
2
REQUEST=10
REQUEST=20
输出
0
10
示例 2
输入输出示例仅供调试，后台判题数据一般不包含示例
输入
5
REQUEST=10
REQUEST=20
RELEASE=0
REQUEST=20
REQUEST=10
输出
0
10
30
0
解释
第一条指令，申请地址0~9的10个字节内存，返回首地址0
第二条指令，申请地址10~29的20字节内存，返回首地址10
第三条指令，释放首地址为0的内存申请，0~9地址内存被释放，变为空闲，释放成功，无需输出
第四条指令，申请20字节内存，09地址内存连续空间不足20字节，往后查找到3049地址，返回首地址30
第五条指令，申请10字节，0~9地址内存空间足够，返回首地址0
思路：
模拟，先定义个数组表示cache，用哈希表存取开始地址和其对应的长度，用来判断释放的是不是我们之前创建的。
判断申请是否合法主要有以下几种情况：
- 申请地址 + 长度 < 100
- 第一种之前没有释放过，那么就在申请地址后面申请
- 之前释放过，先判断之前释放的空间是否够存放现在申请的
- 申请地址 + 长度 > 100
- 之前没有释放过，直接输出
error
- 之前释放过，也是判断之前释放的是否能够存放现在申请的。
判断释放是否合法
- 如果在哈希表中存在，肯定合法，需要移动释放指针
- 否则输出error
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
| #include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
int main(){
int N;
cin >> N;
int reqPos = 0;
int relPos = 0;
vector<int> cache(100);
unordered_map<int, int> mp;
while(N--){
string str;
cin >> str;
int index;
for(int i = 0; i < str.size(); i++){
if(str[i] == '='){
index = i;
break;
}
}
string op = str.substr(0, index);
int len = stoi(str.substr(index + 1));
if(op == "REQUEST"){
if(len == 0){
cout << "error" << endl;
}else if(reqPos + len <= 100){
if(relPos == 0){
mp[reqPos] = len;
cout << reqPos << endl;
int end = reqPos + len;
for(int i = reqPos; i < end; i++, reqPos++){
cache[i] = 1;
}
}else if(relPos != 0){
int linkLen = 0;
int linkPos = -1;
if(relPos >= len){
for(int i = 0; i < relPos; i++){
if(cache[i] == 0){
linkLen++;
if(linkLen == len){
break;
}
}else{
linkLen = 0;
linkPos = i;
}
}
if(linkLen >= len){
mp[linkPos + 1] = len;
cout << linkPos + 1 << endl;
for(int i = linkPos + 1; i < (linkPos + 1 + len); i++){
cache[i] = 1;
}
relPos = linkPos + 1;
}else{
mp[reqPos] = len;
cout << reqPos << endl;
int end = reqPos + len;
for(int i = reqPos; i < end; i++, reqPos++){
cache[i] = 1;
}
}
}else{
mp[reqPos] = len;
cout << reqPos << endl;
int end = reqPos + len;
for(int i = reqPos; i < end; i++, reqPos++){
cache[i] = 1;
}
}
}
}else if(reqPos + len > 100 && relPos != 0){
int linkLen = 0;
int linkPos = -1;
if(relPos >= len){
for(int i = 0; i < relPos; i++){
if(cache[i] == 0){
linkLen++;
if(linkLen == len){
break;
}
}else{
linkLen = 0;
linkPos = i;
}
}
if(linkLen >= len){
mp[linkPos + 1] = len;
cout << linkPos + 1 << endl;
for(int i = linkPos + 1; i < (linkPos + 1 + len); i++){
cache[i] = 1;
}
relPos = linkPos + 1;
}else{
cout << "error" << endl;
}
}else{
cout << "error" << endl;
}
}else{
cout << "error" << endl;
}
}else if(op == "RELEASE"){
if(mp.count(len)){
int caplen = mp[len];
for(int i = len; i < caplen; i++){
cache[i] = 0;
}
relPos = len + caplen;
}else{
cout << "error" << endl;
}
}
}
return 0;
}
|