귀여운 배추에게 weight balanced tree라는 자료구조를 소개받아서, 기본 문제를 하나 풀어 봤습니다.

이 문제는 persistent bbst를 구현할 수 있으면 되는 문제고, 그 구현은 wbt가 가장 깔끔하다고 합니다.

구현은 어제 20시쯤부터 시작했습니다. 다음과 같은 시행착오들을 겪었습니다.

1. std::vector 이슈

C++에서 new node()와 같이 새 객체를 하나하나 만드는 것은 오래 걸립니다. 이 시간은 std::vector를 이용해서 최적화해줄 수 있습니다. 그래서 저는 보통 vector.push_back으로 메모리를 할당해주는 편입니다. 그런데, 다음과 같은 문제가 발생했습니다.

struct t {
    vector<t>* p = nullptr;
    int test = 1557;
    void f() { 
		    for(int i = 0; i <= 100; i++)
	        p.push_back(t()); 
        assert(test == 1557);
    }
}

int main() {
    vector<t> v(1);
    v[0].p = &v;
    v[0].f();
}

위 코드를 실행하면 assertion failed가 나오게 됩니다.

그 이유는, p.push_back이 실행되면서 vector가 메모리 할당을 다시 하게 되면, 이 객체의 메모리 주소도 변경되므로 더 이상 this->p 나 this->test가 올바른 값을 가지고 있지 않기 때문입니다.

그래서 어쩔 수 없이 포인터 기반으로 구현해야 했습니다.

2. 저능 이슈

node* join(node* l, node* r) {
    if(l->p) l = copy_(l);
    if(r->p) l = copy_(r);
    node* ret = new node(this, l, r, nullptr, 0, T());
    ret->pull();
    return ret;
}

위와 같은 코드를 짰습니다.

여기까지 완료하는 데 3시간 반이 걸렸습니다. 즉, 이 시점에서 시간이 23시 30분 정도였습니다.

3. 메모리 초과

사용되지 않는 노드를 해제해주는 것(가비지 컬렉션)을 구현하지 않았는데, 그 때문인지 메모리 초과를 받게 되었습니다. 그래서, std::shared_ptr를 활용하여 다시 구현했습니다.

4. 틀렸습니다