shared_ptrを使ったツリー構造

ポインタを使ったツリーデータ構造は自動的に解放されないがshared_ptrを使って自動的に不要となった部分を解放させることができる

#include <boost/shared_ptr.hpp>
#include <stdio.h>
using namespace std;
using boost::shared_ptr;

struct CharTree {
    shared_ptr<CharTree> parent;
    char c;

    CharTree(shared_ptr<CharTree> parent, char c):
        parent(parent), c(c) {
        printf("Construct %c\n", c);
    }
    CharTree(CharTree *parent, char c):
        parent(parent), c(c) {
        printf("Construct %c\n", c);
    }

    ~CharTree() {
        printf("Destruct %c\n", c);
    }
};

int main() {
    /*
    [作るツリー]

      A-B-G-H-I
       \
        C-D-E-F-J-K
               \
                L-M
    */
    shared_ptr<CharTree> root(new CharTree(NULL, 'A'));
    shared_ptr<CharTree> leaf1(new CharTree(root, 'B'));
    shared_ptr<CharTree> leaf2(new CharTree(root, 'C'));
    leaf2 = shared_ptr<CharTree>(new CharTree(leaf2, 'D'));
    leaf2 = shared_ptr<CharTree>(new CharTree(leaf2, 'E'));
    leaf2 = shared_ptr<CharTree>(new CharTree(leaf2, 'F'));
    leaf1 = shared_ptr<CharTree>(new CharTree(leaf1, 'G'));
    leaf1 = shared_ptr<CharTree>(new CharTree(leaf1, 'H'));
    leaf1 = shared_ptr<CharTree>(new CharTree(leaf1, 'I'));
    leaf1 = shared_ptr<CharTree>(new CharTree(leaf2, 'J'));
    leaf1 = shared_ptr<CharTree>(new CharTree(leaf1, 'K'));
    leaf1 = shared_ptr<CharTree>(new CharTree(leaf2, 'L'));
    leaf1 = shared_ptr<CharTree>(new CharTree(leaf1, 'M'));
}

出力結果

Construct A
Construct B
Construct C
Construct D
Construct E
Construct F
Construct G
Construct H
Construct I
Construct J
Destruct I
Destruct H
Destruct G
Destruct B
Construct K
Construct L
Destruct K
Destruct J
Construct M
Destruct M
Destruct L
Destruct F
Destruct E
Destruct D
Destruct C
Destruct A