```cpp #include #include #include #include #include #include struct Command { Command(std::string op, std::size_t arg) : op(op), arg(arg) {} std::string op; std::size_t arg; }; class Solution { public: std::string simulate_allocator(long long n, std::string operations) { used_slots.clear(); free_slots.clear(); std::vector commands = parse_operations(operations); std::uint64_t memory_size = static_cast(n); free_slots[0] = memory_size; // all the memory is free std::vector results; for (const auto& command : commands) { if (command.op == "malloc") { std::size_t ptr = allocate(command.arg); if (ptr == FAIL) { results.push_back(-1); } else { results.push_back(static_cast(ptr)); } } else if (command.op == "free") { release(command.arg); } } std::string out = "["; for (std::size_t i = 0; i < results.size(); ++i) { if (i > 0) out += ", "; out += std::to_string(results[i]); } out += "]"; return out; } private: static constexpr std::size_t FAIL = static_cast(-1); std::vector parse_operations(std::string operations) { std::vector commands; std::istringstream ss(operations); char ch; std::string op; std::size_t bytes; ss >> ch; // process [ while (ss >> ch) { if (ch != '[') continue; ss >> ch; // skip the opening quote std::getline(ss, op, '"'); ss >> ch; // skip , ss >> bytes; ss >> ch; // skip ] std::cout << "op = " << op << ", bytes = " << bytes << '\n'; commands.push_back(Command(op, bytes)); ss >> ch; } return commands; } std::size_t allocate(std::size_t alloc_size) { for (auto it = free_slots.begin(); it != free_slots.end(); ++it) { if (it->second >= alloc_size) { std::size_t start = it->first; std::size_t space = it->second; used_slots[start] = alloc_size; free_slots.erase(it); if (space > alloc_size) { free_slots[start + alloc_size] = space - alloc_size; } return start; } } return FAIL; } void release(std::size_t ptr) { auto it = used_slots.find(ptr); if (it == used_slots.end()) return; std::size_t start = it->first; std::size_t size = it->second; used_slots.erase(it); std::size_t new_start = start; std::size_t new_size = size; // Merge with right neighbor auto right = free_slots.find(start + size); if (right != free_slots.end()) { new_size += right->second; free_slots.erase(right); } // Merge with left neighbor auto left = free_slots.lower_bound(start); if (left != free_slots.begin()) { --left; if (left->first + left->second == start) { new_start = left->first; new_size += left->second; free_slots.erase(left); } } free_slots[new_start] = new_size; } std::map used_slots; std::map free_slots; // [XXX__XXX__XXXXX___XXXX] --> I need to find the first slot which is empty (enough) // -- therefore I need to be able to iterate over all the empty spaces // I think having two maps -- one for available memory (memory starts) // and one for used slots (memory starts) }; ```

Quick Overview

Implement A Contiguous Memory Allocator With Free-Block Coalescing