⚙️ ft_containers: C++ STL의 철학과 설계를 코드로 재구현하다

C++ Module 시리즈가 C++의 각 요소를 부위별로 단련하는 과정이었다면, ft_containers는 그 모든 근육을 동원하여 C++ 표준 템플릿 라이브러리(STL)라는 거대한 산을 직접 쌓아 올리는, C++ 여정의 최종장이다.

이 프로젝트의 목표는 vector, map, stack, set이라는 STL의 핵심 컨테이너들을 C++98 표준의 제약 속에서 밑바닥부터 재구현하는 것이다.

이는 단순한 모방을 넘어, STL의 아름다운 설계 이면에 숨겨진 자료구조, 알고리즘, 그리고 템플릿 메타프로그래밍의 정수를 이해하고, C++ 언어의 철학을 코드로 증명해내는 과정이었다.

정말 어렵고, 무엇보다 iterate 라는 개념을 이해하는 아주 고생스러운(..) 그러나 확실한(!) 길이 었다.

📜 컨테이너별 핵심 설계와 시간 복잡도

각 컨테이너는 저마다의 뚜렷한 설계 철학과 성능적 약속(시간 복잡도)을 가지고 있다.

  1. ft::vector: 동적 배열과 상각 분석 (Amortized Analysis)
    • 핵심 설계: 내부에 실제 데이터가 담기는 동적 배열 포인터와 함께, 원소의 개수(size)와 할당된 메모리 공간(capacity)을 별도로 관리한다.
    • 성능 보장: push_back 시 size가 capacity에 도달하면, 기존보다 더 큰(일반적으로 2배) 메모리 공간을 새로 할당하고 모든 원소를 복사한다. 이 재할당(reallocation) 과정 자체는 O(n)의 비용이 들지만, 이러한 비용이 매우 드물게 발생하므로 전체 push_back 연산의 평균 시간 복잡도는 상각 O(1)(Amortized O(1))이 된다. 이 원리를 직접 구현하는 것이 vector의 핵심이다. 또한, 재할당 시 기존의 모든 이터레이터가 무효화(invalidate)되는 현상을 이해하는 것 또한 중요하다.
  2. ft::stack: 컨테이너 어댑터 (Container Adapter)
    • 핵심 설계: stack은 스스로 데이터를 저장하는 자료구조가 아니다. 대신 기존의 다른 컨테이너(Sequence Container, 기본값은 deque이나 이 과제에서는 vector를 사용)의 인터페이스를 제한하여 LIFO(Last-In, First-Out) 정책을 따르도록 감싸는 어댑터 디자인 패턴의 전형이다. 내부 컨테이너의 push_back, pop_back, back 등의 함수를 각각 push, pop, top이라는 이름으로 외부에 노출시킨다.
  3. ft::map & ft::set: 자가 균형 이진 탐색 트리 (Red-Black Tree)
    • 핵심 설계: 이 두 연관 컨테이너(Associative Container)의 심장은 레드-블랙 트리(Red-Black Tree)이다. 레드-블랙 트리는 삽입, 삭제 시 특정 규칙(모든 노드는 Red 혹은 Black, 루트는 Black, Red 노드의 자식은 Black 등)에 따라 스스로 노드를 회전시키고 색상을 변경하여 트리의 높이가 한쪽으로 치우치지 않도록(균형을 맞추도록) 유지한다.
    • 성능 보장: 이 자가 균형 메커니즘 덕분에 트리의 높이가 항상 O(log n)으로 유지되며, 이는 곧 삽입(insert), 삭제(erase), 탐색(find) 연산이 최악의 경우에도 O(log n)의 시간 복잡도를 가짐을 보장한다. map은 <Key, Value> 쌍을, set은 Key 자체를 노드에 저장한다는 점 외에는 동일한 트리 구조를 기반으로 한다. 실질 구현 시에도 set에 의해 덧붙여진 코드를 제외하면 판박이었다. 물론, 레드-블랙 트리가 얼마나 어려운지를 이해하고, 그 부분의 구현 성공만 해도(…) 말이 안될 수준이긴하다. 정확히는 만드는 것은 원하는 그 구조로 만들면 되나 이를 이해해서 머릿속에 그려내는 것 자체가 매우 어려웠다.

🧠 STL의 근간을 이루는 고급 C++ 기법

ft_containers를 구현하기 위해서는 C++의 고급 문법과 디자인 패턴에 대한 깊은 이해가 필수적이다.

  1. 이터레이터 시스템 (The Iterator System) 이터레이터는 단순히 ‘포인터 같은 객체’를 넘어, 컨테이너(데이터)와 알고리즘(로직)을 분리하는 STL의 핵심 디자인 패턴이다.
    • iterator_traits: 템플릿 기반의 범용 알고리즘이 어떤 종류의 이터레이터가 들어와도 그 이터레이터의 속성(값 타입, 포인터 타입, 이터레이터 카테고리 등)을 알아낼 수 있도록 통일된 인터페이스를 제공하는 메커니즘이다. iterator_traits를 직접 구현하고 활용하는 것은 STL의 설계 사상을 이해하는 데 매우 중요하다.
    • 이터레이터 카테고리: vector의 RandomAccessIterator, map의 BidirectionalIterator 등 각 컨테이너의 특성에 맞는 이터레이터를 구현하며, 각 카테고리가 제공하는 연산의 차이를 이해해야 한다.
  2. 템플릿 메타프로그래밍과 SFINAE (Substitution Failure Is Not An Error) “치환 실패는 오류가 아니다”라는 SFINAE는 C++ 템플릿의 컴파일 타임 동작을 제어하는 강력한 기법이다.
    • enable_if: SFINAE를 활용한 대표적인 도구로, 특정 타입 조건이 참일 때만 해당 템플릿 함수나 생성자가 오버로딩 후보군에 포함되도록 만든다. 예를 들어, vector의 vector(size_type n, ...) 생성자와 이터레이터 범위를 받는 vector(InputIterator first, ...) 생성자는, InputIterator 자리에 정수 타입이 들어올 경우 모호함이 발생한다. 이때 enable_if를 사용하여 “두 번째 인자가 정수 타입이 아닐 경우에만 이 생성자를 활성화하라” 와 같은 제약을 컴파일 타임에 걸어줌으로써 문제를 해결한다. 이 부분을 구현 요구사항의 이해가 특히나 어려웠다.
  3. 메모리 관리자 (Allocator) std::allocator를 템플릿 인자로 받아 컨테이너의 메모리 할당/해제, 객체의 생성/소멸을 직접 제어한다. 이는 컨테이너의 핵심 로직과 메모리 관리 정책을 분리하는 설계이며, 이를 통해 C++의 RAII 원칙을 더욱 깊이 이해하게 된다.

✨ 성찰 및 배운 점

ft_containers는 C++ 언어의 문법적 숙달을 넘어, 잘 설계된 라이브러리의 이면에 얼마나 깊은 컴퓨터 과학적 원리와 설계적 고민이 담겨 있는지를 깨닫게 한 프로젝트였다.

  • 추상화에서 구체화로: 매일 사용하던 STL 컨테이너가 더 이상 마법 같은 ‘블랙박스’가 아닌, 성능과 안정성을 위해 치밀하게 계산된 자료구조와 C++ 기법들의 집합체임을 이해하게 되었다.
  • C++98의 제약이 준 선물: auto, 스마트 포인터, 무브 시맨틱스 등 현대 C++의 편리한 기능 없이 순수 C++98로 구현하는 과정은 고통스러웠지만, 덕분에 C++의 가장 근본적인 원리(RAII, 이터레이터, 템플릿 동작 방식)를 더욱 명확하게 파고들 수 있는 기회가 되었다.
  • 설계자로서의 성장: 이 프로젝트를 완수했다는 것은 단순히 STL을 복제할 수 있다는 의미를 넘어, 성능, 인터페이스, 재사용성을 모두 고려하는 라이브러리 설계자의 관점을 경험했다는 것을 의미한다. 물론 이걸 보았다고 현존하는 라이브러리나 알고리즘을 이해하는데 아주 큰 영향을 줬다! 라고 말하는 건 오만할 것이다… 그러나 최소한 기본 데이터 자료들, 특히나 다양한 프레임 워크에서 일반적으로 사용되는 벡터, map, set 과 같은 것들의 이해도를 높이고 활용 방식을 디테일하게 이해했단 차원에선 개인적으로 C++ 를 사용한 프로젝트 중엔 실용적이진 않으나, 가장 재미있던 과제였다고, 개인적으로 생각한다.