腾讯笔试题，设计内存池，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
     
       allocated;36         list
      
        available;37         char* buffer;38 };