内存管理: Buddy system

/* Buddy system algorithm */

/* Written by Kai Wang */
using namespace std;

#include <cstring>
#include <cmath>
#include <sstream>
#include <iostream>
#include <vector>
#include <utility>

#define FOR(i, a, b) for (int i=(a); i<=(b); i++)
#define REP(i, a)       for (int i=0; i<(a); i++)
#define all(a)             (a).begin(), (a).end()
#define sz(a)                   (int)((a).size())
#define mp                              make_pair
#define y                                  second
#define x                                   first

#define MEMO_SIZE                              21

int main() {

    /* first of pair is rank of block size, 
       second is it's process */
    vector<pair<int, char> > memo;

    /* 2 MB, '*' indicates empty block  */
    memo.insert(memo.begin(), mp(MEMO_SIZE, '*'));

    string cmd;
    while (cin>>cmd) {
        cout<<cmd<<" ";
        char wh=cmd[0]; cin>>cmd;
        cout<<cmd<<endl;
        char op=cmd[0];
        stringstream ss(cmd.substr(1));
        int size; ss>>size;
        int r=floor(log2(size*1024))+1;
        typeof(memo.begin()) it;
        if (op=='+') {
            it=find(all(memo), mp(r, '*'));
            /* found an empty block of rank r */
            if (it!=memo.end()) {
                it->y=wh;
                goto next;
            }
            /* divide the first available larger block */
            FOR(i, r+1, MEMO_SIZE) {
                it=find(all(memo), mp(i, '*'));
                if (it==memo.end())
                    continue;
                int time=i-r;
                while (time--) {
                    it=memo.erase(it);
                    it=memo.insert(it, mp(i-1, '*'));
                    it=memo.insert(it, mp(i-1, '*'));
                    i--;
                }
                it->y=wh;
                break;
            }
        } else {
            it=find(all(memo), mp(r, wh));
            it->y='*';
            /* try merge neighbour block, left first, than right */
            while (it->y=='*') {
                int id=it-memo.begin();
                if (id>=1 && memo[id-1].x==r && memo[id-1].y=='*') {
                    it--;
                    it=memo.erase(it);
                    it=memo.erase(it);
                    it=memo.insert(it, mp(r+1, '*'));
                    r++;
                    goto next_try;
                } else if (id<MEMO_SIZE && memo[id+1].x==r &&
                           memo[id+1].y=='*') {
                    it=memo.erase(it);
                    it=memo.erase(it);
                    it=memo.insert(it, mp(r+1, '*'));
                    r++;
                    goto next_try;
                }
                break;
next_try:;
            }
        }
next:
        REP(i, sz(memo)) {
            cout<<(int)pow(2, memo[i].x)/1024<<memo[i].y;
            if (i==sz(memo)-1)
                cout<<endl;
            else
                cout<<"  ";
        }
        cout<<endl;
    }
    return 0;
}