Blog

C/C++ 디자인 패턴 (8) — 컴포지트(Composite)

디렉터리 크기를 구하려면 안에 든 파일 크기를 더하고, 하위 디렉터리가 있으면 그 안으로 다시 들어가야 한다. 파일과 디렉터리를 별개 타입으로 다루면 순회하는 코드마다 “이게 파일인가 디렉터리인가”를 분기해야 한다. 컴포지트(Composite)는 개별 객체(Leaf)와 객체 묶음(Composite)이 같은 인터페이스를 갖게 해서, 클라이언트가 트리의 한 노드든 전체 트리든 똑같이 다루게 한다. 이 글에서는 파일 시스템 트리로 기본형을 만들고, std::variant를 쓴 값 기반 컴포지트, 부모 포인터와 집계값 캐시, 순환 방지, C의 first-child/next-sibling 트리를 차례로 다룬다.

메뉴 시스템 예제로 공통 기반 클래스와 add()의 위치(투명성 vs 안전성)를 다룬 내용은 설계 기법 (8) 메뉴 시스템에 있다.

이 시리즈의 다른 글

구조

참여자역할예제
ComponentLeaf와 Composite의 공통 인터페이스Node (size(), print())
Leaf자식이 없는 말단 객체File
Composite자식을 보관하고, 연산을 자식에게 재귀적으로 위임Dir
ClientComponent 인터페이스로만 트리를 다룸main()

기본형: 파일 시스템 트리

// fs.cpp — 파일과 디렉터리를 같은 인터페이스(Node)로 다룬다
#include <iostream>
#include <memory>
#include <string>
#include <vector>

class Node {
public:
	explicit Node(std::string name) : name_(std::move(name)) {}
	virtual ~Node() = default;
	virtual long size() const = 0;
	virtual void print(int depth) const = 0;
	const std::string &name() const { return name_; }
protected:
	std::string name_;
};

class File : public Node {                                    // Leaf
public:
	File(std::string n, long bytes) : Node(std::move(n)), bytes_(bytes) {}
	long size() const override { return bytes_; }
	void print(int d) const override
	{ std::cout << std::string(d * 2, ' ') << name_ << " (" << bytes_ << ")\n"; }
private:
	long bytes_;
};

class Dir : public Node {                                     // Composite
public:
	using Node::Node;
	Dir &add(std::unique_ptr<Node> n) { children_.push_back(std::move(n)); return *this; }
	long size() const override
	{
		long total = 0;
		for (const auto &c : children_)
			total += c->size();                            // 자식이 파일이든 디렉터리든 같은 호출
		return total;
	}
	void print(int d) const override
	{
		std::cout << std::string(d * 2, ' ') << name_ << "/ [" << size() << "]\n";
		for (const auto &c : children_)
			c->print(d + 1);
	}
private:
	std::vector<std::unique_ptr<Node>> children_;
};

int main()
{
	auto bin = std::make_unique<Dir>("bin");
	bin->add(std::make_unique<File>("ls", 142312)).add(std::make_unique<File>("cat", 35280));
	auto etc = std::make_unique<Dir>("etc");
	etc->add(std::make_unique<File>("hosts", 221));

	Dir root("usr");
	root.add(std::move(bin)).add(std::move(etc)).add(std::make_unique<File>("README", 1024));
	root.print(0);

	const Node &leaf = File("x", 7), &tree = root;               // 클라이언트는 구분하지 않는다
	std::cout << "leaf=" << leaf.size() << " tree=" << tree.size() << '\n';
}
$ g++ -std=c++20 -Wall -Wextra -O2 -o fs fs.cpp && ./fs
usr/ [178837]
  bin/ [177592]
    ls (142312)
    cat (35280)
  etc/ [221]
    hosts (221)
  README (1024)
leaf=7 tree=178837

Dir::size()는 자식이 파일인지 디렉터리인지 묻지 않고 size()를 부른다. 마지막 줄처럼 클라이언트도 리프 하나와 트리 전체를 같은 타입으로 다룬다.

std::variant로 만든 값 기반 컴포지트

노드 종류가 고정돼 있다면 상속과 힙 포인터 없이 std::variant로 재귀 구조를 표현할 수 있다. std::vector는 C++17부터 불완전 타입을 원소로 허용하므로 Dir 안에 std::vector<Node>를 둘 수 있다.

// variant_tree.cpp — 상속 없이 std::variant로 만든 값 기반 컴포지트
#include <iostream>
#include <string>
#include <variant>
#include <vector>

struct File;
struct Dir;
using Node = std::variant<File, Dir>;

struct File { std::string name; long bytes; };
struct Dir  { std::string name; std::vector<Node> children; };   // vector는 불완전 타입 허용(C++17)

template <class... F> struct overloaded : F... { using F::operator()...; };

long size(const Node &n)
{
	return std::visit(overloaded{
		[](const File &f) { return f.bytes; },
		[](const Dir &d) {
			long t = 0;
			for (const auto &c : d.children)
				t += size(c);
			return t;
		},
	}, n);
}

int count_files(const Node &n)
{
	if (auto *d = std::get_if<Dir>(&n)) {
		int c = 0;
		for (const auto &ch : d->children)
			c += count_files(ch);
		return c;
	}
	return 1;
}

int main()
{
	Node root = Dir{"usr", {
		Dir{"bin", {File{"ls", 142312}, File{"cat", 35280}}},
		Dir{"etc", {File{"hosts", 221}}},
		File{"README", 1024},
	}};
	Node copy = root;                                    // 값 의미: 트리 전체가 깊게 복사된다
	std::get<Dir>(copy).children.push_back(File{"NEW", 1});

	std::cout << "root size=" << size(root) << " files=" << count_files(root) << '\n'
		  << "copy size=" << size(copy) << " files=" << count_files(copy) << '\n';
}
$ g++ -std=c++20 -Wall -Wextra -O2 -o variant_tree variant_tree.cpp && ./variant_tree
root size=178837 files=4
copy size=178838 files=5

대입 한 줄로 트리 전체가 깊게 복사되고, 복사본에 파일을 추가해도 원본은 그대로다. 대신 새 노드 종류를 추가하면 모든 std::visit 지점을 고쳐야 한다.

구분상속 + unique_ptrstd::variant
새 노드 종류 추가클래스 하나 추가variant와 모든 visit 수정
새 연산 추가모든 클래스에 가상 함수 추가함수 하나 추가
복사clone() 직접 구현기본 복사가 깊은 복사
메모리노드마다 힙 할당자식 벡터 단위 할당

부모 포인터, 캐시, 순환 방지

실제 트리에는 “경로를 구한다”, “집계값을 캐시한다”, “잘못된 이동을 막는다” 같은 요구가 붙는다. 셋 다 자식이 부모를 알아야 풀린다.

// parent_cache.cpp — 부모 포인터로 경로를 만들고, 크기 캐시를 위로 무효화한다
#include <iostream>
#include <memory>
#include <stdexcept>
#include <string>
#include <vector>

class Dir;

class Node {
public:
	explicit Node(std::string n) : name_(std::move(n)) {}
	virtual ~Node() = default;
	virtual long size() const = 0;
	std::string path() const;
	Dir *parent() const { return parent_; }
protected:
	friend class Dir;
	std::string name_;
	Dir *parent_ = nullptr;                    // 소유하지 않는 역참조
	void invalidateUp();
};

class Dir : public Node {
public:
	using Node::Node;
	Node &add(std::unique_ptr<Node> n)
	{
		for (Node *p = this; p; p = p->parent())   // 자기 조상을 자식으로 넣는 순환 방지
			if (p == n.get())
				throw std::logic_error("cycle: '" + n->path() + "' is an ancestor of '" + path() + "'");
		n->parent_ = this;
		children_.push_back(std::move(n));
		invalidateUp();
		return *children_.back();
	}
	std::unique_ptr<Node> detach(const Node &n)
	{
		for (auto it = children_.begin(); it != children_.end(); ++it)
			if (it->get() == &n) {
				auto out = std::move(*it);
				children_.erase(it);
				out->parent_ = nullptr;
				invalidateUp();
				return out;
			}
		return nullptr;
	}
	long size() const override
	{
		if (!cached_) {
			++recomputes;
			long t = 0;
			for (const auto &c : children_)
				t += c->size();
			cache_ = t;
			cached_ = true;
		}
		return cache_;
	}
	static inline int recomputes = 0;
private:
	friend class Node;
	std::vector<std::unique_ptr<Node>> children_;
	mutable long cache_ = 0;
	mutable bool cached_ = false;
};

class File : public Node {
public:
	File(std::string n, long b) : Node(std::move(n)), bytes_(b) {}
	long size() const override { return bytes_; }
	void resize(long b) { bytes_ = b; invalidateUp(); }
private:
	long bytes_;
};

std::string Node::path() const { return parent_ ? parent_->path() + "/" + name_ : name_; }
void Node::invalidateUp()
{
	for (Dir *p = dynamic_cast<Dir *>(this) ? static_cast<Dir *>(this) : parent_; p; p = p->parent_)
		p->cached_ = false;
}

int main()
{
	Dir root("");
	auto &usr = static_cast<Dir &>(root.add(std::make_unique<Dir>("usr")));
	auto &bin = static_cast<Dir &>(usr.add(std::make_unique<Dir>("bin")));
	auto &ls = static_cast<File &>(bin.add(std::make_unique<File>("ls", 142312)));
	std::cout << ls.path() << '\n';

	for (int q = 1; q <= 3; ++q) {
		Dir::recomputes = 0;
		long s = root.size();
		std::cout << "query " << q << ": size=" << s << " recomputes=" << Dir::recomputes << '\n';
	}

	ls.resize(150000);
	Dir::recomputes = 0;
	std::cout << "after resize size=" << root.size() << " recomputes=" << Dir::recomputes << '\n';

	try {
		auto moved = usr.parent()->detach(usr);          // root에서 usr를 떼어
		bin.add(std::move(moved));                       // 자기 자손 밑에 넣으려 하면
	} catch (const std::exception &e) {
		std::cout << "error: " << e.what() << '\n';
	}
}
$ g++ -std=c++20 -Wall -Wextra -O2 -fsanitize=address -o parent_cache parent_cache.cpp && ./parent_cache
/usr/bin/ls
query 1: size=142312 recomputes=3
query 2: size=142312 recomputes=0
query 3: size=142312 recomputes=0
after resize size=150000 recomputes=3
error: cycle: 'usr' is an ancestor of 'usr/bin'

첫 질의에서 디렉터리 3개가 한 번씩 계산되고, 이후 질의는 캐시만 읽는다. 파일 크기가 바뀌면 그 위 조상들만 다시 계산되고, 자기 조상을 자손 밑에 넣으려는 시도는 예외로 막혔다.

깊은 트리: 재귀 대신 명시적 스택

컴포지트의 연산은 자연스럽게 재귀가 되지만, 깊이가 스레드 스택 크기를 넘으면 순회와 소멸 모두 스택을 넘친다. 한 줄로 이어진 100만 단계 트리로 확인했다.

// deep.cpp — 아주 깊은 트리에서 재귀 순회·재귀 소멸은 스택을 넘친다
#include <cstdlib>
#include <iostream>
#include <memory>
#include <string>
#include <vector>

struct Node {
	long bytes = 1;
	std::vector<std::unique_ptr<Node>> children;
	~Node()                                     // 재귀 소멸을 피하려면 자식을 먼저 평탄화해서 해제
	{
		std::vector<std::unique_ptr<Node>> pending = std::move(children);
		while (!pending.empty()) {
			auto n = std::move(pending.back());
			pending.pop_back();
			for (auto &c : n->children)
				pending.push_back(std::move(c));
			n->children.clear();               // n은 여기서 자식 없이 해제된다
		}
	}
};

long size_recursive(const Node &n)
{
	long t = n.bytes;
	for (const auto &c : n.children)
		t += size_recursive(*c);
	return t;
}

long size_iterative(const Node &root)
{
	long t = 0;
	std::vector<const Node *> stack{&root};      // 명시적 스택
	while (!stack.empty()) {
		const Node *n = stack.back();
		stack.pop_back();
		t += n->bytes;
		for (const auto &c : n->children)
			stack.push_back(c.get());
	}
	return t;
}

int main(int argc, char **argv)
{
	int depth = std::atoi(argv[1]);
	bool recursive = argc > 2 && std::string(argv[2]) == "recursive";

	auto root = std::make_unique<Node>();
	Node *cur = root.get();
	for (int i = 1; i < depth; ++i) {            // 한 줄로 이어진 깊은 트리
		cur->children.push_back(std::make_unique<Node>());
		cur = cur->children.back().get();
	}
	std::cout << (recursive ? "recursive" : "iterative") << " depth=" << depth << " size="
		  << (recursive ? size_recursive(*root) : size_iterative(*root)) << std::endl;
}
$ g++ -std=c++20 -Wall -Wextra -O0 -o deep deep.cpp && ./deep 1000000 && ./deep 1000 recursive && ./deep 1000000 recursive; echo "exit=$?"
iterative depth=1000000 size=1000000
recursive depth=1000 size=1000
bash: line 1: 34587 Segmentation fault      (core dumped) ./deep 1000000 recursive
exit=139

재귀 버전은 깊이 1000에서는 동작하지만 100만에서는 SIGSEGV(139)로 죽는다. 기본 소멸자도 자식의 소멸자를 재귀적으로 부르므로, 예제처럼 자식을 벡터로 옮겨 가며 해제해야 같은 문제를 피한다.

C 구현: first-child / next-sibling

C에서는 자식 배열 대신 첫 자식과 다음 형제 포인터 두 개로 임의 개수의 자식을 표현하는 방식이 흔하다. 노드 구조체 하나가 리프와 컴포지트를 겸한다.

/* tree.c — C 컴포지트: first_child / next_sibling 링크로 만든 트리 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct node {
	char name[16];
	long bytes;                        /* 리프만 의미 있음 */
	int is_dir;
	struct node *parent, *first_child, *next_sibling;
};

static struct node *node_new(const char *name, int is_dir, long bytes)
{
	struct node *n = calloc(1, sizeof(*n));
	if (!n)
		abort();
	snprintf(n->name, sizeof(n->name), "%s", name);
	n->is_dir = is_dir;
	n->bytes = bytes;
	return n;
}

static struct node *node_add(struct node *dir, struct node *child)
{
	child->parent = dir;
	child->next_sibling = dir->first_child;      /* 앞에 끼우기 */
	dir->first_child = child;
	return child;
}

static long node_size(const struct node *n)    /* 리프와 컴포지트를 같은 함수로 */
{
	long total = n->is_dir ? 0 : n->bytes;
	for (const struct node *c = n->first_child; c; c = c->next_sibling)
		total += node_size(c);
	return total;
}

static void node_print(const struct node *n, int depth)
{
	printf("%*s%s%s [%ld]\n", depth * 2, "", n->name, n->is_dir ? "/" : "", node_size(n));
	for (const struct node *c = n->first_child; c; c = c->next_sibling)
		node_print(c, depth + 1);
}

static void node_free(struct node *n)
{
	struct node *c = n->first_child;
	while (c) {
		struct node *next = c->next_sibling;
		node_free(c);
		c = next;
	}
	free(n);
}

int main(void)
{
	struct node *root = node_new("usr", 1, 0);
	struct node *bin = node_add(root, node_new("bin", 1, 0));
	node_add(bin, node_new("ls", 0, 142312));
	node_add(bin, node_new("cat", 0, 35280));
	node_add(root, node_new("README", 0, 1024));

	node_print(root, 0);
	node_free(root);
	return 0;
}
$ gcc -std=c11 -Wall -Wextra -O2 -fsanitize=address -o tree tree.c && ./tree
usr/ [178616]
  README [1024]
  bin/ [177592]
    cat [35280]
    ls [142312]

앞에 끼워 넣기 때문에 출력 순서가 추가 순서의 역순이다. 리눅스 커널의 디바이스 트리 노드(struct device_node)도 parent, child, sibling 포인터로 같은 구조를 이룬다.

주의사항

  • 소유는 위에서 아래로만: 부모가 자식을 unique_ptr로 소유하고, 자식의 부모 포인터는 소유하지 않는 원시 포인터로 둔다. 양방향을 shared_ptr로 만들면 순환 참조로 해제되지 않는다.
  • 재귀 깊이: 사용자 입력으로 트리가 만들어진다면(파서, 파일 시스템 탐색) 깊이를 제한하거나 처음부터 반복 순회로 작성한다. 최적화 수준에 따라 한계 깊이가 달라지므로 “이 정도면 괜찮다”는 값을 믿지 않는다.
  • 캐시 무효화 누락: 리프를 바꾸는 모든 경로(크기 변경, 추가, 제거, 이동)가 조상 캐시를 무효화해야 한다. 하나라도 빠지면 틀린 값이 조용히 나온다.
  • 순환 검사 비용: 예제의 순환 검사는 조상을 따라 올라가므로 O(깊이)다. 노드 이동이 잦지 않다면 충분하다.
  • 가상 함수의 기본 인자: virtual void print(int depth = 0)처럼 기반에 기본 인자를 두면, 파생 클래스 객체로 직접 부를 때는 적용되지 않아 컴파일 에러가 난다. 기본 인자는 비가상 래퍼에 둔다.

마무리

컴포지트는 재귀적인 데이터 구조를 재귀적인 연산으로 다루게 해 주는 패턴이다. 노드 종류가 열려 있으면 상속, 닫혀 있으면 std::variant가 잘 맞는다. 다음 글에서는 객체를 감싸 기능을 덧붙이는 데코레이터(Decorator)를 다룬다.

참고

Tags: , , , , , , , , , , , , ,

답글 남기기