首页 > 代码库 > MemPool
MemPool
腾讯笔试题,设计内存池,alloc和free都是O(1)。
和LRUCache类似,这里用了一个list表示可用的空间,用一个map来记录这块内存是否已分配,这样free的时候才可能O(1)。
1 class MemPool { 2 public: 3 void init(int unitSize, int maxUnitNum) { 4 long long size = unitSize * maxUnitNum; 5 buffer = new char[size]; 6 memset(buffer, 0, sizeof(char) * size); 7 for (int i = 0; i < size; ++i) { 8 available.push_back(buffer + i); 9 }10 }11 12 ~MemPool() {13 if (buffer) {14 delete[] buffer;15 }16 }17 // O(1)18 void* alloc() {19 if (available.empty()) return NULL;20 char* ans = available.front();21 available.pop_front();22 allocated[ans] = 1;23 return ans;24 }25 26 // O(1)27 void free(void *pUnit) {28 char* tmp = (char*)pUnit;29 if (allocated.find(tmp) == allocated.end()30 || allocated[tmp] == 0) return;31 available.push_back(tmp);32 allocated[tmp] = 0;33 }34 private:35 unordered_map<char*, int> allocated;36 list<char*> available;37 char* buffer;38 };
MemPool
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。