题目重点：allocation基址是身份，整理移动会使外部指针失效。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练地址[0,size)、正长度、malloc返回base，失败None；free仅完整已分配base，双free false。
- 代码为正确基线：按已分配段排序推导gaps，firstfit或bestfit；不声称满足logn轮次。compact只重排抽象区间并返回relocation map，调用者必须更新全部指针。
解题路线
- gaps遍历升序used，保留cursor输出空段；first-fit选最早足够空段，best-fit选最小足够容量并按base平局。free删allocation后相邻空段自然合并。
- 要求logn时需地址有序结构找邻接并合并，以及大小有序结构找best-fit；两个索引同步更新。Python普通sorted list插入移动O(n)，bisect不能让全操作自动logn。
- raw pointer稳定与移动compaction冲突。可使用handle→新地址间接层、可重定位引用更新或禁止移动有引用块；只有返回relocation map不是完整数据搬运实现。
手动走一遍
容量10，分3/3/3，释放中间3，只剩gap3和tail1，申请4失败，虽总空闲4。compact把最后块从6移到3，relocation{0:0,6:3}；旧地址6不能继续free新对象。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
class Allocator:
def __init__(self,size):
if size<0:raise ValueError("nonnegative capacity")
self.size=size;self.used={}
def gaps(self):
cursor=0;result=[]
for start,length in sorted(self.used.items()):
if start>cursor:result.append((cursor,start-cursor))
cursor=start+length
if cursor<self.size:result.append((cursor,self.size-cursor))
return result
def malloc(self,size,best_fit=False):
if size<=0:raise ValueError("positive allocation")
candidates=[(a,n) for a,n in self.gaps() if n>=size]
if not candidates:return None
address,length=min(candidates,key=(lambda pair:(pair[1],pair[0])) if best_fit else (lambda pair:pair[0]))
self.used[address]=size;return address
def free(self,address):
if address not in self.used:return False
del self.used[address];return True
def compact(self):
# Relocation map must be applied to every external pointer by the caller.
result={};new={};cursor=0
for address,size in sorted(self.used.items()):result[address]=cursor;new[cursor]=size;cursor+=size
self.used=new;return result
复杂度
m活跃块，基线malloc/compact O(m logm)、free期望O(1)、空间O(m)；实际数据搬运另Ω(移动字节)。双平衡索引可使正常alloc/free O(logm)，compaction仍线性以上。
易错点与追问
容易失分的边界
- free内部指针会误释放不属于整块的内存。
- 只维护大小索引无法方便合并地址相邻空块。
继续深挖
- 日志/事务如何保证双索引更新失败后仍一致？
- 要求所有地址稳定时怎样通过页级映射减少碎片而不移动用户虚址？
