ft_container

커스텀 allocator 지원
RAII 원칙 준수: 리소스 획득은 초기화(Resource Acquisition Is Initialization)
- 객체가 생성될 때 리소스(메모리)를 획득하고, 소멸될 때 자동으로 해제
- 소멸자에서 destroy()와 deallocate()를 호출하여 메모리 누수 방지
- 예시: vector의 소멸자에서 할당된 모든 요소를 destroy()하고 메모리를 deallocate()
예외 안전성 보장: 예외 발생 시에도 리소스가 안전하게 관리된다
- at(): 범위를 벗어나면 std::out_of_range 예외 발생
- reserve(): 너무 큰 크기 요청 시 std::length_error 예외 발생
- 예외 발생 시에도 기존 데이터의 무결성 유지 (Basic Guarantee)

템플릿 프로그래밍

SFINAE (Substitution Failure Is Not An Error) 활용
enable_if를 통한 템플릿 특수화
is_integral 타입 트레이트

파일 구조

ft_containers/
├── Vector.hpp          # vector 컨테이너 구현
├── List.hpp            # list 컨테이너 구현
├── Deque.hpp           # deque 컨테이너 구현
├── Stack.hpp           # stack 컨테이너 어댑터
├── Queue.hpp           # queue 컨테이너 어댑터
├── Map.hpp             # map 연관 컨테이너
├── Set.hpp             # set 연관 컨테이너
├── MultiMap.hpp        # multimap 연관 컨테이너
├── MultiSet.hpp        # multiset 연관 컨테이너
├── iterator.hpp        # 반복자 베이스 클래스 및 유틸리티
├── utility.hpp         # 유틸리티 함수 및 타입 트레이트
├── Btree.hpp           # 이진 탐색 트리 구현 (map/set 기반)
├── compile.sh          # 컴파일 스크립트
└── test/               # 테스트 파일들
    ├── vectorTest.cpp
    ├── listTest.cpp
    ├── mapTest.cpp
    ├── setTest.cpp
    ├── dequeTest.cpp
    ├── stackTest.cpp
    ├── queueTest.cpp
    ├── multimapTest.cpp
    ├── multisetTest.cpp
    └── test.hpp

사용 방법

기본 사용 예제

#include "Vector.hpp"
#include "List.hpp"
#include "Map.hpp"
#include <iostream>

int main() {
    // Vector 사용 예제
    ft::vector<int> vec;
    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(3);

    for (ft::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // List 사용 예제
    ft::list<std::string> lst;
    lst.push_back("Hello");
    lst.push_back("World");
    lst.push_front("ft");

    // Map 사용 예제
    ft::map<std::string, int> mp;
    mp["one"] = 1;
    mp["two"] = 2;
    mp["three"] = 3;

    ft::map<std::string, int>::iterator it = mp.find("two");
    if (it != mp.end()) {
        std::cout << "Found: " << it->first << " = " << it->second << std::endl;
    }

    return 0;
}

컴파일

# 컴파일 스크립트 사용
./compile.sh

# 또는 직접 컴파일
g++ -std=c++98 -Wall -Wextra -Werror your_file.cpp

구현 세부사항

Vector

메모리 할당: 동적 배열 할당
성장 전략: 현재 크기의 1.5배로 확장
반복자 무효화: 재할당 시 모든 반복자 무효화
예외 안전성: 기본 보장 (Basic Guarantee)

List

구조: 이중 연결 리스트
더미 노드: 순환 리스트 구조 (_tip 노드)
특수 연산:
- splice: O(1) 리스트 병합
- merge: 정렬된 리스트 병합
- sort: 버블 정렬 알고리즘
- reverse: O(n) 역순 변환

Map/Set

구조: 이진 탐색 트리 (B-tree)
균형: AVL 트리 또는 Red-Black 트리 (구현에 따라 다름)
정렬: 키/값의 비교 함수를 통한 자동 정렬
반복자: 중위 순회 (in-order traversal)

Iterator

베이스 클래스:
- BaseIter<T>: vector, deque용
- ListBaseIter<T>: list용
- BtreeBaseIter<E, Compare, isMulti>: map/set용
역방향 반복자: ReverseIterator, ConstReverseIterator 래퍼

Utility

pair: 키-값 쌍 구조체
less: 비교 함수 객체
enable_if: SFINAE를 위한 타입 트레이트
is_integral: 정수 타입 판별
swap: 값 교환 함수
distance: 반복자 간 거리 계산

Allocator

프로젝트는 표준 std::allocator를 사용하며, 커스텀 allocator도 지원한다.

template <class T>
class allocator
{
public:
    T* allocate(size_t n);           // 메모리 할당
    void deallocate(T*, size_t);     // 메모리 해제
    void construct(T*, const T&);    // 객체 생성
    void destroy(T*);                // 객체 소멸
};

테스트

test/ 디렉토리에 각 컨테이너별 테스트 파일이 포함되어 있다. 각 테스트는 표준 라이브러리와의 동작 일치성을 검증한다.

주의사항

C++98 표준 준수
표준 라이브러리(std::) 사용 금지 (컨테이너 구현 시)
메모리 누수 없이 구현
예외 안전성 보장
반복자 무효화 규칙 준수

라이선스

이 프로젝트는 교육 목적으로 작성되었다.